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 NonCopyable
    {
    public:
        JPH_OVERRIDE_NEW_DELETE
 
                            Node();
                            ~Node();
 
        inline uint         GetTriangleCount() const                { return uint(mTriangles.size()); }
 
        inline bool         HasChildren() const                     { return mChild[0] != nullptr || mChild[1] != nullptr; }
 
        uint                GetMinDepth() const;
 
        uint                GetMaxDepth() const;
 
        uint                GetNodeCount() const;
 
        uint                GetLeafNodeCount() const;
 
        uint                GetTriangleCountInTree() const;
 
        void                GetTriangleCountPerNode(float &outAverage, uint &outMin, uint &outMax) const;
 
        float               CalculateSAHCost(float inCostTraversal, float inCostLeaf) const;
 
        void                GetNChildren(uint inN, Array<const Node *> &outChildren) const;
 
        AABox               mBounds;
 
        IndexedTriangleList mTriangles;
 
        Node *              mChild[2];
 
    private:
        friend class AABBTreeBuilder;
 
        float               CalculateSAHCostInternal(float inCostTraversalDivSurfaceArea, float inCostLeafDivSurfaceArea) const;
 
        void                GetTriangleCountPerNodeInternal(float &outAverage, uint &outAverageDivisor, uint &outMin, uint &outMax) const;
    };
 
                            AABBTreeBuilder(TriangleSplitter &inSplitter, uint inMaxTrianglesPerLeaf = 16);
 
    Node *                  Build(AABBTreeBuilderStats &outStats);
 
private:
    Node *                  BuildInternal(const TriangleSplitter::Range &inTriangles);
 
    TriangleSplitter &      mTriangleSplitter;
    const uint              mMaxTrianglesPerLeaf;
};
 
JPH_NAMESPACE_END