AABBTreeBuilder.h

Go to the documentation of this file.

// Jolt Physics Library (https://github.com/jrouwe/JoltPhysics)
// SPDX-FileCopyrightText: 2021 Jorrit Rouwe
// SPDX-License-Identifier: MIT
 
#pragma once
 
#include <Jolt/TriangleSplitter/TriangleSplitter.h>
#include <Jolt/Geometry/AABox.h>
#include <Jolt/Core/NonCopyable.h>
 
JPH_NAMESPACE_BEGIN
 
struct AABBTreeBuilderStats
{
    TriangleSplitter::Stats mSplitterStats;                         
 
    float                   mSAHCost = 0.0f;                        
    int                     mMinDepth = 0;                          
    int                     mMaxDepth = 0;                          
    int                     mNodeCount = 0;                         
    int                     mLeafNodeCount = 0;                     
 
    int                     mMaxTrianglesPerLeaf = 0;               
 
    int                     mTreeMinTrianglesPerLeaf = 0;           
    int                     mTreeMaxTrianglesPerLeaf = 0;           
    float                   mTreeAvgTrianglesPerLeaf = 0.0f;        
};
 
class JPH_EXPORT AABBTreeBuilder
{
public:
    class Node
    {
    public:
        JPH_OVERRIDE_NEW_DELETE
 
        static constexpr uint cInvalidNodeIndex = ~uint(0);
 
        inline uint         GetTriangleCount() const                { return mNumTriangles; }
 
        inline bool         HasChildren() const                     { return mChild[0] != cInvalidNodeIndex || mChild[1] != cInvalidNodeIndex; }
 
        uint                GetMinDepth(const Array<Node> &inNodes) const;
 
        uint                GetMaxDepth(const Array<Node> &inNodes) const;
 
        uint                GetNodeCount(const Array<Node> &inNodes) const;
 
        uint                GetLeafNodeCount(const Array<Node> &inNodes) const;
 
        uint                GetTriangleCountInTree(const Array<Node> &inNodes) const;
 
        void                GetTriangleCountPerNode(const Array<Node> &inNodes, float &outAverage, uint &outMin, uint &outMax) const;
 
        float               CalculateSAHCost(const Array<Node> &inNodes, float inCostTraversal, float inCostLeaf) const;
 
        void                GetNChildren(const Array<Node> &inNodes, uint inN, Array<const Node *> &outChildren) const;
 
        AABox               mBounds;
 
        uint                mTrianglesBegin; // Index into mTriangles
        uint                mNumTriangles = 0;
 
        uint                mChild[2] = { cInvalidNodeIndex, cInvalidNodeIndex };
 
    private:
        friend class AABBTreeBuilder;
 
        float               CalculateSAHCostInternal(const Array<Node> &inNodes, float inCostTraversalDivSurfaceArea, float inCostLeafDivSurfaceArea) const;
 
        void                GetTriangleCountPerNodeInternal(const Array<Node> &inNodes, float &outAverage, uint &outAverageDivisor, uint &outMin, uint &outMax) const;
    };
 
                            AABBTreeBuilder(TriangleSplitter &inSplitter, uint inMaxTrianglesPerLeaf = 16);
 
    Node *                  Build(AABBTreeBuilderStats &outStats);
 
    const Array<Node> &     GetNodes() const                        { return mNodes; }
 
    const Array<IndexedTriangle> &GetTriangles() const              { return mTriangles; }
 
private:
    uint                    BuildInternal(const TriangleSplitter::Range &inTriangles);
 
    TriangleSplitter &      mTriangleSplitter;
    const uint              mMaxTrianglesPerLeaf;
    Array<Node>             mNodes;
    Array<IndexedTriangle>  mTriangles;
};
 
JPH_NAMESPACE_END