// Jolt Physics Library (https://github.com/jrouwe/JoltPhysics) // SPDX-FileCopyrightText: 2021 Jorrit Rouwe // SPDX-License-Identifier: MIT #include #include JPH_NAMESPACE_BEGIN uint AABBTreeBuilder::Node::GetMinDepth(const Array &inNodes) const { if (HasChildren()) { uint left = inNodes[mChild[0]].GetMinDepth(inNodes); uint right = inNodes[mChild[1]].GetMinDepth(inNodes); return min(left, right) + 1; } else return 1; } uint AABBTreeBuilder::Node::GetMaxDepth(const Array &inNodes) const { if (HasChildren()) { uint left = inNodes[mChild[0]].GetMaxDepth(inNodes); uint right = inNodes[mChild[1]].GetMaxDepth(inNodes); return max(left, right) + 1; } else return 1; } uint AABBTreeBuilder::Node::GetNodeCount(const Array &inNodes) const { if (HasChildren()) return inNodes[mChild[0]].GetNodeCount(inNodes) + inNodes[mChild[1]].GetNodeCount(inNodes) + 1; else return 1; } uint AABBTreeBuilder::Node::GetLeafNodeCount(const Array &inNodes) const { if (HasChildren()) return inNodes[mChild[0]].GetLeafNodeCount(inNodes) + inNodes[mChild[1]].GetLeafNodeCount(inNodes); else return 1; } uint AABBTreeBuilder::Node::GetTriangleCountInTree(const Array &inNodes) const { if (HasChildren()) return inNodes[mChild[0]].GetTriangleCountInTree(inNodes) + inNodes[mChild[1]].GetTriangleCountInTree(inNodes); else return GetTriangleCount(); } void AABBTreeBuilder::Node::GetTriangleCountPerNode(const Array &inNodes, float &outAverage, uint &outMin, uint &outMax) const { outMin = INT_MAX; outMax = 0; outAverage = 0; uint avg_divisor = 0; GetTriangleCountPerNodeInternal(inNodes, outAverage, avg_divisor, outMin, outMax); if (avg_divisor > 0) outAverage /= avg_divisor; } float AABBTreeBuilder::Node::CalculateSAHCost(const Array &inNodes, float inCostTraversal, float inCostLeaf) const { float surface_area = mBounds.GetSurfaceArea(); return surface_area > 0.0f? CalculateSAHCostInternal(inNodes, inCostTraversal / surface_area, inCostLeaf / surface_area) : 0.0f; } void AABBTreeBuilder::Node::GetNChildren(const Array &inNodes, uint inN, Array &outChildren) const { JPH_ASSERT(outChildren.empty()); // Check if there is anything to expand if (!HasChildren()) return; // Start with the children of this node outChildren.push_back(&inNodes[mChild[0]]); outChildren.push_back(&inNodes[mChild[1]]); size_t next = 0; bool all_triangles = true; while (outChildren.size() < inN) { // If we have looped over all nodes, start over with the first node again if (next >= outChildren.size()) { // If there only triangle nodes left, we have to terminate if (all_triangles) return; next = 0; all_triangles = true; } // Try to expand this node into its two children const Node *to_expand = outChildren[next]; if (to_expand->HasChildren()) { outChildren.erase(outChildren.begin() + next); outChildren.push_back(&inNodes[to_expand->mChild[0]]); outChildren.push_back(&inNodes[to_expand->mChild[1]]); all_triangles = false; } else { ++next; } } } float AABBTreeBuilder::Node::CalculateSAHCostInternal(const Array &inNodes, float inCostTraversalDivSurfaceArea, float inCostLeafDivSurfaceArea) const { if (HasChildren()) return inCostTraversalDivSurfaceArea * mBounds.GetSurfaceArea() + inNodes[mChild[0]].CalculateSAHCostInternal(inNodes, inCostTraversalDivSurfaceArea, inCostLeafDivSurfaceArea) + inNodes[mChild[1]].CalculateSAHCostInternal(inNodes, inCostTraversalDivSurfaceArea, inCostLeafDivSurfaceArea); else return inCostLeafDivSurfaceArea * mBounds.GetSurfaceArea() * GetTriangleCount(); } void AABBTreeBuilder::Node::GetTriangleCountPerNodeInternal(const Array &inNodes, float &outAverage, uint &outAverageDivisor, uint &outMin, uint &outMax) const { if (HasChildren()) { inNodes[mChild[0]].GetTriangleCountPerNodeInternal(inNodes, outAverage, outAverageDivisor, outMin, outMax); inNodes[mChild[1]].GetTriangleCountPerNodeInternal(inNodes, outAverage, outAverageDivisor, outMin, outMax); } else { outAverage += GetTriangleCount(); outAverageDivisor++; outMin = min(outMin, GetTriangleCount()); outMax = max(outMax, GetTriangleCount()); } } AABBTreeBuilder::AABBTreeBuilder(TriangleSplitter &inSplitter, uint inMaxTrianglesPerLeaf) : mTriangleSplitter(inSplitter), mMaxTrianglesPerLeaf(inMaxTrianglesPerLeaf) { } AABBTreeBuilder::Node *AABBTreeBuilder::Build(AABBTreeBuilderStats &outStats) { TriangleSplitter::Range initial = mTriangleSplitter.GetInitialRange(); // Worst case for number of nodes: 1 leaf node per triangle. At each level above, the number of nodes is half that of the level below. // This means that at most we'll be allocating 2x the number of triangles in nodes. mNodes.reserve(2 * initial.Count()); mTriangles.reserve(initial.Count()); // Build the tree Node &root = mNodes[BuildInternal(initial)]; // Collect stats float avg_triangles_per_leaf; uint min_triangles_per_leaf, max_triangles_per_leaf; root.GetTriangleCountPerNode(mNodes, avg_triangles_per_leaf, min_triangles_per_leaf, max_triangles_per_leaf); mTriangleSplitter.GetStats(outStats.mSplitterStats); outStats.mSAHCost = root.CalculateSAHCost(mNodes, 1.0f, 1.0f); outStats.mMinDepth = root.GetMinDepth(mNodes); outStats.mMaxDepth = root.GetMaxDepth(mNodes); outStats.mNodeCount = root.GetNodeCount(mNodes); outStats.mLeafNodeCount = root.GetLeafNodeCount(mNodes); outStats.mMaxTrianglesPerLeaf = mMaxTrianglesPerLeaf; outStats.mTreeMinTrianglesPerLeaf = min_triangles_per_leaf; outStats.mTreeMaxTrianglesPerLeaf = max_triangles_per_leaf; outStats.mTreeAvgTrianglesPerLeaf = avg_triangles_per_leaf; return &root; } uint AABBTreeBuilder::BuildInternal(const TriangleSplitter::Range &inTriangles) { // Check if there are too many triangles left if (inTriangles.Count() > mMaxTrianglesPerLeaf) { // Split triangles in two batches TriangleSplitter::Range left, right; if (!mTriangleSplitter.Split(inTriangles, left, right)) { // When the trace below triggers: // // This code builds a tree structure to accelerate collision detection. // At top level it will start with all triangles in a mesh and then divides the triangles into two batches. // This process repeats until until the batch size is smaller than mMaxTrianglePerLeaf. // // It uses a TriangleSplitter to find a good split. When this warning triggers, the splitter was not able // to create a reasonable split for the triangles. This usually happens when the triangles in a batch are // intersecting. They could also be overlapping when projected on the 3 coordinate axis. // // To solve this issue, you could try to pass your mesh through a mesh cleaning / optimization algorithm. // You could also inspect the triangles that cause this issue and see if that part of the mesh can be fixed manually. // // When you do not fix this warning, the tree will be less efficient for collision detection, but it will still work. JPH_IF_DEBUG(Trace("AABBTreeBuilder: Doing random split for %d triangles (max per node: %u)!", (int)inTriangles.Count(), mMaxTrianglesPerLeaf);) int half = inTriangles.Count() / 2; JPH_ASSERT(half > 0); left = TriangleSplitter::Range(inTriangles.mBegin, inTriangles.mBegin + half); right = TriangleSplitter::Range(inTriangles.mBegin + half, inTriangles.mEnd); } // Recursively build const uint node_index = (uint)mNodes.size(); mNodes.push_back(Node()); uint left_index = BuildInternal(left); uint right_index = BuildInternal(right); Node &node = mNodes[node_index]; node.mChild[0] = left_index; node.mChild[1] = right_index; node.mBounds = mNodes[node.mChild[0]].mBounds; node.mBounds.Encapsulate(mNodes[node.mChild[1]].mBounds); return node_index; } // Create leaf node const uint node_index = (uint)mNodes.size(); mNodes.push_back(Node()); Node &node = mNodes.back(); node.mTrianglesBegin = (uint)mTriangles.size(); node.mNumTriangles = inTriangles.mEnd - inTriangles.mBegin; const VertexList &v = mTriangleSplitter.GetVertices(); for (uint i = inTriangles.mBegin; i < inTriangles.mEnd; ++i) { const IndexedTriangle &t = mTriangleSplitter.GetTriangle(i); mTriangles.push_back(t); node.mBounds.Encapsulate(v, t); } return node_index; } JPH_NAMESPACE_END