2025·
C#BVHSpatial AccelerationCollision DetectionGPU Instancing
Code Example — BVH Generation
Bounding Volume Hierarchy generation for 3D meshes — collision and ray-cast acceleration structures.
The BVHGeneration script is designed to create Bounding Volume Hierarchy (BVH) data for a given 3D mesh. In this case, the generated BVH structures are instanced on the GPU and used for efficient spatial queries for collision between particles and complex 3D meshes. BVHs allow efficient elimination of large, non-relevant areas of a mesh, significantly reducing the number of intersection tests required, helping to efficiently resolve collisions.
using System;
using System.Collections.Generic;
using UnityEngine;
public class BVHGeneration : MonoBehaviour
{
// Public variables exposed in the inspector
[Header("References")]
public GameObject bvhTargetObject; // the object the BVH tree will be generated for
[Header("Settings")]
public int maxTrisPerLeafNode; // Maximum number of triangles per leaf node
public bool generateBVH; // Used to initate the generation of the BVH data by the user
[Header("Debug Settings")]
public bool debugNodes; // Toggle to debug nodes
public int debugNodeDepth = 0; // Depth of the nodes to debug
// Private variables
private Mesh targetMesh; // Mesh of the test object
private Vector3[] verts; // Array of vertices in the mesh
// Enum to represent the axis
private enum AxisEnum
{
x,
y,
z
}
// Lists to hold BVH data
private List<int> leafNodeTris = new List<int>(); // List of triangle indexes in leaf nodes only, used for assembling tri indices array for use on the GPU
private List<BVHNodeGPU> GPUBVHNodes = new List<BVHNodeGPU>(); // List of BVH nodes, structured for use on the GPU
// Instance of BVHSaveAndLoad class
private BVHSaveAndLoad BVHSaveAndLoad;
// Lists to manage BVH nodes
[Header("BVH Nodes Management")]
private List<BVHNode> nodes = new List<BVHNode>(); // All generated BVH nodes
private List<BVHNode> nodesToSplitNow = new List<BVHNode>(); // Nodes that need immediate splitting
private List<BVHNode> nodesToSplitLater = new List<BVHNode>(); // Nodes deferred for splitting to maintain loop integrity
private List<BVHNode> nodesToRemoveFromSplitList = new List<BVHNode>(); // Nodes to remove from 'nodesToSplitNow' after splitting, maintain loop integrity
// BVH node
[Serializable] public class BVHNode
{
public Vector3 minBounds; // min bounds of the node AABB
public Vector3 maxBounds; // min bounds of the node AABB
public uint leftChildIndex = uint.MaxValue; // the index of the left child node
public uint rightChildIndex = uint.MaxValue; // the index of the right child node
public uint startTriangleIndex; // the index of the nodes first triangle index in triangle indices
public uint triangleCount; // the number of triangles within the node
public List<NodeTriangle> tris; // list of triangles within the node
}
// GPU version of a BVH node, restructured to remove list of tris so it works on GPU (the tri indices are combined into one single buffer anyway, so we only need the start index and tri count to be able to access all of the nodes tris)
[Serializable] public struct BVHNodeGPU
{
public Vector3 minBounds;
public Vector3 maxBounds;
public uint leftChildIndex;
public uint rightChildIndex;
public uint startTriangleIndex;
public uint triangleCount;
}
// triangle data required for triangles in a node
[Serializable] public struct NodeTriangle
{
// index to vertices in "verts"
public int index1;
public int index2;
public int index3;
public Vector3 centroid;
// min and max bounds of the triangle
public float minX;
public float maxX;
public float minY;
public float maxY;
public float minZ;
public float maxZ;
}
private void Start()
{
BVHSaveAndLoad = GetComponent<BVHSaveAndLoad>();
}
void Update()
{
// Check if BVH generation test is enabled
if (generateBVH)
{
// Update the mesh reference from the test object
targetMesh = bvhTargetObject.GetComponent<MeshFilter>().sharedMesh;
// Generate the BVH for the mesh
GenerateBVH(targetMesh);
// Populate leaf node triangles and GPU BVH nodes list
ConvertBVHDataForGPU();
// Save the generated BVH data to a binary file
SaveBVHData(targetMesh);
// Disable the BVH generation test toggle
generateBVH = false;
}
// Check if node debugging is enabled
if (debugNodes)
{
// Debug nodes at the specified node depth
DebugNodes(debugNodeDepth);
// Disable the node debugging toggle
debugNodes = false;
}
}
/// <summary>
/// Saves the BVH (Bounding Volume Hierarchy) data for the given mesh.
/// </summary>
/// <param name="mesh">The mesh for which the BVH data is being saved.</param>
void SaveBVHData(Mesh mesh)
{
// Create a new BVHData instance
BVHSaveAndLoad.BVHData bVHData = new BVHSaveAndLoad.BVHData();
// Set the mesh index in the BVHData instance. The mesh name is used to lookup the mesh index, if not alread created, a new mesh index will be generated
bVHData.meshIndex = BVHSaveAndLoad.GetMeshIndex(mesh.name);
// Convert and assign GPU BVH nodes list to an array
bVHData.Nodes = GPUBVHNodes.ToArray();
// Convert and assign leaf node triangle indices list to an array
bVHData.TriangleIndexes = leafNodeTris.ToArray();
// Assign the vertices of the test mesh to the BVHData instance
bVHData.Vertices = targetMesh.vertices;
// Save the BVH data to binary file, using the BVHSaveAndLoad instance
BVHSaveAndLoad.SaveBVHData(bVHData);
}
/// <summary>
/// Converts BVH data into a format suitable for GPU processing by populating the lists of leaf node triangles and GPU BVH nodes.
/// </summary>
void ConvertBVHDataForGPU()
{
// Clear existing data
GPUBVHNodes.Clear();
leafNodeTris.Clear();
int leafNodeTriCount = 0;
// Iterate through each node in the list
for (int i = 0; i < nodes.Count; i++)
{
BVHNode node = nodes[i];
// Check if the current node is a leaf node (this is true where the index is set to "uint.MaxValue")
if (node.leftChildIndex == uint.MaxValue)
{
// Update the start triangle index and triangle count for the leaf node
node.startTriangleIndex = (uint)leafNodeTriCount;
node.triangleCount = (uint)node.tris.Count;
// Add the indices of each triangle in the leaf node to the leafNodeTris list
foreach (var tri in node.tris)
{
leafNodeTris.Add(tri.index1);
leafNodeTris.Add(tri.index2);
leafNodeTris.Add(tri.index3);
leafNodeTriCount += 3;
}
}
// Create a GPU BVH node from the current node
BVHNodeGPU bvhNodeGPU = new BVHNodeGPU
{
minBounds = node.minBounds,
maxBounds = node.maxBounds,
leftChildIndex = node.leftChildIndex,
rightChildIndex = node.rightChildIndex,
startTriangleIndex = node.startTriangleIndex,
triangleCount = node.triangleCount
};
// Add the GPU BVH node to the list
GPUBVHNodes.Add(bvhNodeGPU);
}
}
/// <summary>
/// Generates the root BVH node from the given mesh.
/// </summary>
/// <param name="mesh">The mesh for which the BVH root node is generated.</param>
/// <returns>The generated root BVH node.</returns>
BVHNode GenerateRootNode(Mesh mesh)
{
// Create a new BVH node and add it to the nodes and nodesToSplitNow lists
BVHNode node = new BVHNode();
nodes.Add(node);
nodesToSplitNow.Add(node);
// Extract vertex and triangle indices from the mesh
int[] triIndices = mesh.triangles;
verts = mesh.vertices;
// List to hold triangle centroids
List<NodeTriangle> nodeTriangles = new List<NodeTriangle>();
// Calculate the axis-aligned bounding box (AABB) for the root node
CalculateAABBRootNode(triIndices, verts, out node.minBounds, out node.maxBounds);
// Assemble the centroid list from the triangle indices
for (int i = 0; i < triIndices.Length; i += 3)
{
int vertIndex1 = triIndices[i];
int vertIndex2 = triIndices[i + 1];
int vertIndex3 = triIndices[i + 2];
NodeTriangle nodeTriangle = new NodeTriangle
{
index1 = vertIndex1,
index2 = vertIndex2,
index3 = vertIndex3,
centroid = (verts[vertIndex1] + verts[vertIndex2] + verts[vertIndex3]) / 3,
minX = Mathf.Min(verts[vertIndex1].x, verts[vertIndex2].x, verts[vertIndex3].x),
maxX = Mathf.Max(verts[vertIndex1].x, verts[vertIndex2].x, verts[vertIndex3].x),
minY = Mathf.Min(verts[vertIndex1].y, verts[vertIndex2].y, verts[vertIndex3].y),
maxY = Mathf.Max(verts[vertIndex1].y, verts[vertIndex2].y, verts[vertIndex3].y),
minZ = Mathf.Min(verts[vertIndex1].z, verts[vertIndex2].z, verts[vertIndex3].z),
maxZ = Mathf.Max(verts[vertIndex1].z, verts[vertIndex2].z, verts[vertIndex3].z)
};
// Add the calculated triangle centroid to the list
nodeTriangles.Add(nodeTriangle);
}
// Assign the list of triangle centroids to the node
node.tris = nodeTriangles;
return node;
}
/// <summary>
/// Generates the BVH (Bounding Volume Hierarchy) from the given mesh.
/// </summary>
/// <param name="mesh">The mesh to generate the BVH for.</param>
void GenerateBVH(Mesh mesh)
{
// Clear existing nodes and nodes to split
nodes.Clear();
nodesToSplitNow.Clear();
// Generate the root node from the mesh
GenerateRootNode(mesh);
int currentDepth = 0;
// Continue splitting nodes until there are none left to split
while (nodesToSplitNow.Count > 0)
{
currentDepth++;
// Split each node in the current list of nodes to be split
foreach (BVHNode nodeToSplit in nodesToSplitNow)
{
// Get the optimal slice position and axis for splitting the node
(float slicePos, AxisEnum axis) = GetSlicePositionAndAxis(nodeToSplit);
// Split the node at the determined slice position
SplitNodeAtCut(nodeToSplit, axis, slicePos);
}
// Remove nodes that have been split from the current list
foreach (BVHNode splitNode in nodesToRemoveFromSplitList)
{
nodesToSplitNow.Remove(splitNode);
}
nodesToRemoveFromSplitList.Clear();
// Add nodes that need to be split in the next iteration
nodesToSplitNow.AddRange(nodesToSplitLater);
nodesToSplitLater.Clear();
// Break if the depth exceeds the maximum allowed value to prevent infinite loops
if (currentDepth > 30)
{
Debug.LogError("Error: BVH generation exceeded maximum tree depth. Breaking loop to prevent infinite iteration.");
break;
}
}
}
/// <summary>
/// Evaluates the split plane for a given axis and updates the lowest cost and slice position if a better split is found.
/// </summary>
/// <param name="node">The BVH node to split.</param>
/// /// <param name="axis">The axis to split on.</param>
/// <param name="slicePos">The position of the slice, on the given axis.</param>
/// <param name="lowestCost">The current lowest cost for the given axis, updated if a better split is found.</param>
/// <param name="lowestCostSlice">The slice position corresponding to the lowest cost, updated if a better split is found.</param>
void EvaluateSlice(BVHNode node, AxisEnum axis, float slicePos, ref float lowestCost, ref float lowestCostSlice)
{
if ((axis == AxisEnum.x && (slicePos <= node.minBounds.x || slicePos >= node.maxBounds.x)) ||
(axis == AxisEnum.y && (slicePos <= node.minBounds.y || slicePos >= node.maxBounds.y)) ||
(axis == AxisEnum.z && (slicePos <= node.minBounds.z || slicePos >= node.maxBounds.z)))
{
return;
}
// Calculate sliced AABB bounds for children A and B
Vector3 childAMin = node.minBounds;
Vector3 childAMax = node.maxBounds;
Vector3 childBMin = node.minBounds;
Vector3 childBMax = node.maxBounds;
if (axis == AxisEnum.x)
{
childAMax.x = slicePos;
childBMin.x = slicePos;
}
else if (axis == AxisEnum.y)
{
childAMax.y = slicePos;
childBMin.y = slicePos;
}
else if (axis == AxisEnum.z)
{
childAMax.z = slicePos;
childBMin.z = slicePos;
}
// Assemble triangle lists for each child
List<NodeTriangle> childATris = new List<NodeTriangle>();
List<NodeTriangle> childBTris = new List<NodeTriangle>();
// Assemble list of triangles that intersect the AABBs
foreach (var tri in node.tris)
{
Vector3 vert1 = verts[tri.index1];
Vector3 vert2 = verts[tri.index2];
Vector3 vert3 = verts[tri.index3];
// if triangle intersects the child A bounding box, add the tri to child A tris
if (TriangleAABBIntersection.TriangleIntersectsAABB(vert1, vert2, vert3, childAMin, childAMax))
{
childATris.Add(tri);
}
// if triangle intersects the child B bounding box, add the tri to child B tris
else if (TriangleAABBIntersection.TriangleIntersectsAABB(vert1, vert2, vert3, childBMin, childBMax))
{
childBTris.Add(tri);
}
}
if (childATris.Count != 0 && childBTris.Count != 0)
{
// Clip the node A bounds based on an AABB that encapsulates all of its triangles
Vector3 min = Vector3.positiveInfinity;
Vector3 max = Vector3.negativeInfinity;
CalculateAABBForTriangles(childATris, ref min, ref max, false);
childAMin = min;
childAMax = max;
// Clip the node B bounds based on an AABB that encapsulates all of its triangles
min = Vector3.positiveInfinity;
max = Vector3.negativeInfinity;
CalculateAABBForTriangles(childBTris, ref min, ref max, false);
childBMin = min;
childBMax = max;
float costAtSplit = CalculateSAHCost(node.minBounds, node.maxBounds, childAMin, childAMax, childBMin, childBMax, childATris.Count, childBTris.Count);
if (costAtSplit < lowestCost)
{
lowestCost = costAtSplit;
lowestCostSlice = slicePos;
}
}
}
/// <summary>
/// Evaluates the cost of splitting a BVH node along a given axis at various positions,
/// and updates the lowest cost and corresponding slice position if a better split is found.
/// </summary>
/// <param name="node">The BVH node to evaluate splits for.</param>
/// <param name="axis">The axis to split along (x, y, or z).</param>
/// <param name="lowestCost">Reference to the current lowest cost, updated if a better split is found.</param>
/// <param name="lowestCostSlice">Reference to the slice position corresponding to the lowest cost, updated if a better split is found.</param>
void EvaluateSlices(BVHNode node, AxisEnum axis, ref float lowestCost, ref float lowestCostSlice)
{
// Iterate through each triangle in the node
foreach (var tri in node.tris)
{
// Evaluate the cost of splitting at the centroid position of the triangle
float slicePos = axis switch
{
AxisEnum.x => tri.centroid.x,
AxisEnum.y => tri.centroid.y,
AxisEnum.z => tri.centroid.z,
_ => throw new ArgumentOutOfRangeException()
};
EvaluateSlice(node, axis, slicePos, ref lowestCost, ref lowestCostSlice);
// Evaluate the cost of splitting at each vertex position of the triangle
int[] indices = { tri.index1, tri.index2, tri.index3 };
foreach (int index in indices)
{
slicePos = axis switch
{
AxisEnum.x => verts[index].x,
AxisEnum.y => verts[index].y,
AxisEnum.z => verts[index].z,
_ => throw new ArgumentOutOfRangeException()
};
EvaluateSlice(node, axis, slicePos, ref lowestCost, ref lowestCostSlice);
}
}
}
/// <summary>
/// Determines the optimal slice position and axis for splitting a BVH node by evaluating the cost of splits along the x, y, and z axes.
/// </summary>
/// <param name="node">The BVH node to evaluate for splitting.</param>
/// <returns>A tuple containing the optimal slice position and the corresponding axis.</returns>
(float, AxisEnum) GetSlicePositionAndAxis(BVHNode node)
{
// Initialize variables for the lowest cost and slice positions
float lowestCostXSlice = float.PositiveInfinity;
float lowestCostYSlice = float.PositiveInfinity;
float lowestCostZSlice = float.PositiveInfinity;
float lowestCostX = float.PositiveInfinity;
float lowestCostY = float.PositiveInfinity;
float lowestCostZ = float.PositiveInfinity;
// Evaluate slices for each axis
EvaluateSlices(node, AxisEnum.x, ref lowestCostX, ref lowestCostXSlice);
EvaluateSlices(node, AxisEnum.y, ref lowestCostY, ref lowestCostYSlice);
EvaluateSlices(node, AxisEnum.z, ref lowestCostZ, ref lowestCostZSlice);
// Determine the lowest cost and corresponding axis
float lowestCost = Mathf.Min(lowestCostX, lowestCostY, lowestCostZ);
// If no viable slice was found, log a message and draw the bounds for debugging
if (lowestCost == float.PositiveInfinity)
{
Debug.Log("No viable slices, tri count: " + node.tris.Count);
DrawBounds(node.minBounds, node.maxBounds, bvhTargetObject.transform, 2, Color.blue);
}
// Return the slice position and axis corresponding to the lowest cost
if (lowestCost == lowestCostX)
{
return (lowestCostXSlice, AxisEnum.x);
}
else if (lowestCost == lowestCostY)
{
return (lowestCostYSlice, AxisEnum.y);
}
else
{
return (lowestCostZSlice, AxisEnum.z);
}
}
/// <summary>
/// Splits a BVH node at the specified slice position along the given axis, creating two child nodes.
/// </summary>
/// <param name="node">The BVH node to split.</param>
/// <param name="axis">The axis along which to split the node (x, y, or z).</param>
/// <param name="slicePos">The position along the axis at which to split the node.</param>
void SplitNodeAtCut(BVHNode node, AxisEnum axis, float slicePos)
{
// Create two new BVH nodes for the split
BVHNode nodeA = new BVHNode();
BVHNode nodeB = new BVHNode();
// Lists to hold triangles for each child node
List<NodeTriangle> childATris = new List<NodeTriangle>();
List<NodeTriangle> childBTris = new List<NodeTriangle>();
// Calculate the bounds for the child nodes based on the split axis
switch (axis)
{
case AxisEnum.x:
nodeA.minBounds = node.minBounds;
nodeA.maxBounds = new Vector3(slicePos, node.maxBounds.y, node.maxBounds.z);
nodeB.minBounds = new Vector3(slicePos, node.minBounds.y, node.minBounds.z);
nodeB.maxBounds = node.maxBounds;
break;
case AxisEnum.y:
nodeA.minBounds = node.minBounds;
nodeA.maxBounds = new Vector3(node.maxBounds.x, slicePos, node.maxBounds.z);
nodeB.minBounds = new Vector3(node.minBounds.x, slicePos, node.minBounds.z);
nodeB.maxBounds = node.maxBounds;
break;
case AxisEnum.z:
nodeA.minBounds = node.minBounds;
nodeA.maxBounds = new Vector3(node.maxBounds.x, node.maxBounds.y, slicePos);
nodeB.minBounds = new Vector3(node.minBounds.x, node.minBounds.y, slicePos);
nodeB.maxBounds = node.maxBounds;
break;
}
// Distribute triangles between the child nodes based on their intersection with the new bounds
foreach (var tri in node.tris)
{
Vector3 vert1 = verts[tri.index1];
Vector3 vert2 = verts[tri.index2];
Vector3 vert3 = verts[tri.index3];
if (TriangleAABBIntersection.TriangleIntersectsAABB(vert1, vert2, vert3, nodeA.minBounds, nodeA.maxBounds))
{
childATris.Add(tri);
}
else if (TriangleAABBIntersection.TriangleIntersectsAABB(vert1, vert2, vert3, nodeB.minBounds, nodeB.maxBounds))
{
childBTris.Add(tri);
}
}
// Calculate and update the AABB bounds for the child nodes based on their triangles
Vector3 min = Vector3.positiveInfinity;
Vector3 max = Vector3.negativeInfinity;
CalculateAABBForTriangles(childATris, ref min, ref max, true);
nodeA.minBounds = min;
nodeA.maxBounds = max;
min = Vector3.positiveInfinity;
max = Vector3.negativeInfinity;
CalculateAABBForTriangles(childBTris, ref min, ref max, true);
nodeB.minBounds = min;
nodeB.maxBounds = max;
// Assign the triangle lists to the child nodes
nodeA.tris = childATris;
nodeB.tris = childBTris;
// Add the child nodes to the node list and update the parent node's child indices
nodes.Add(nodeA);
node.leftChildIndex = (uint)nodes.Count - 1;
nodes.Add(nodeB);
node.rightChildIndex = (uint)nodes.Count - 1;
// Mark the parent node for removal from the list of nodes to be split
nodesToRemoveFromSplitList.Add(node);
// If the child nodes have more triangles than allowed per leaf, add them to the list to be split later
if (nodeA.tris.Count > maxTrisPerLeafNode)
{
nodesToSplitLater.Add(nodeA);
}
if (nodeB.tris.Count > maxTrisPerLeafNode)
{
nodesToSplitLater.Add(nodeB);
}
}
/// <summary>
/// Calculates the axis-aligned bounding box (AABB) for a list of triangles and updates the minimum and maximum bounds.
/// </summary>
/// <param name="nodeTriangles">The list of triangles to calculate the AABB for.</param>
/// <param name="min">Reference to the minimum bounds, updated by this function.</param>
/// <param name="max">Reference to the maximum bounds, updated by this function.</param>
/// <param name="actualSplit">Indicates whether the calculation is for an actual split, used for debugging purposes.</param>
void CalculateAABBForTriangles(List<NodeTriangle> nodeTriangles, ref Vector3 min, ref Vector3 max, bool actualSplit)
{
// Iterate through each triangle in the list
for (int i = 0; i < nodeTriangles.Count; i++)
{
// Update the minimum and maximum x bounds based on the triangle's x bounds
min.x = Mathf.Min(min.x, nodeTriangles[i].minX);
max.x = Mathf.Max(max.x, nodeTriangles[i].maxX);
// Update the minimum and maximum y bounds based on the triangle's y bounds
min.y = Mathf.Min(min.y, nodeTriangles[i].minY);
max.y = Mathf.Max(max.y, nodeTriangles[i].maxY);
// Update the minimum and maximum z bounds based on the triangle's z bounds
min.z = Mathf.Min(min.z, nodeTriangles[i].minZ);
max.z = Mathf.Max(max.z, nodeTriangles[i].maxZ);
}
// If there are no triangles and this is an actual split, log a debug message
if (nodeTriangles.Count == 0 && actualSplit)
{
Debug.LogWarning("No triangles found during AABB calculation.");
}
}
/// <summary>
/// Calculates the axis-aligned bounding box (AABB) for the root node of the BVH using the given triangle indices and vertices.
/// </summary>
/// <param name="triIndices">The array of triangle indices to calculate the AABB for.</param>
/// <param name="verts">The array of vertices.</param>
/// <param name="minBounds">Output parameter for the minimum bounds of the AABB.</param>
/// <param="maxBounds">Output parameter for the maximum bounds of the AABB.</param>
void CalculateAABBRootNode(int[] triIndices, Vector3[] verts, out Vector3 minBounds, out Vector3 maxBounds)
{
// Initialize the minimum and maximum bounds
minBounds = Vector3.positiveInfinity;
maxBounds = Vector3.negativeInfinity;
// Iterate through each triangle index in the array
foreach (int tri in triIndices)
{
// Get the vertex corresponding to the current triangle index
Vector3 vertex = verts[tri];
// Update the minimum bounds
minBounds = Vector3.Min(minBounds, vertex);
// Update the maximum bounds
maxBounds = Vector3.Max(maxBounds, vertex);
}
}
/// <summary>
/// Calculates the Surface Area Heuristic (SAH) cost for splitting a BVH node into two child nodes.
/// </summary>
/// <param name="parentMin">The minimum bounds of the parent node.</param>
/// <param name="parentMax">The maximum bounds of the parent node.</param>
/// <param name="childAMin">The minimum bounds of the first child node.</param>
/// <param name="childAMax">The maximum bounds of the first child node.</param>
/// <param name="childBMin">The minimum bounds of the second child node.</param>
/// <param name="childBMax">The maximum bounds of the second child node.</param>
/// <param name="triCountA">The number of triangles in the first child node.</param>
/// <param name="triCountB">The number of triangles in the second child node.</param>
/// <returns>The SAH cost for the split.</returns>
public float CalculateSAHCost(Vector3 parentMin, Vector3 parentMax, Vector3 childAMin, Vector3 childAMax, Vector3 childBMin, Vector3 childBMax, int triCountA, int triCountB)
{
// Calculate the surface area of the parent node's AABB
float surfaceAreaParent = CalculateAABBSurfaceArea(parentMin, parentMax);
// Calculate the proportion of the parent node's surface area occupied by the first child node
float surfaceAreaChildAProportionOfParent = CalculateAABBSurfaceArea(childAMin, childAMax) / surfaceAreaParent;
// Calculate the proportion of the parent node's surface area occupied by the second child node
float surfaceAreaChildBProportionOfParent = CalculateAABBSurfaceArea(childBMin, childBMax) / surfaceAreaParent;
// Calculate the SAH cost using the proportions of the surface areas and the number of triangles in each child node
float cost = surfaceAreaChildAProportionOfParent * triCountA + surfaceAreaChildBProportionOfParent * triCountB;
// Return the calculated SAH cost
return cost;
}
/// <summary>
/// Calculates the surface area of an axis-aligned bounding box (AABB) given its minimum and maximum bounds.
/// </summary>
/// <param name="minBounds">The minimum bounds of the AABB.</param>
/// <param name="maxBounds">The maximum bounds of the AABB.</param>
/// <returns>The surface area of the AABB.</returns>
float CalculateAABBSurfaceArea(Vector3 minBounds, Vector3 maxBounds)
{
// Calculate the extents (width, height, depth) of the AABB
Vector3 extents = maxBounds - minBounds;
// Calculate the surface area using the formula: 2 * (width * height + height * depth + depth * width)
float surfaceArea = 2 * (extents.x * extents.y + extents.y * extents.z + extents.z * extents.x);
// Return the calculated surface area
return surfaceArea;
}
/// <summary>
/// Debugs the BVH nodes at a specified depth by drawing their bounds and triangles.
/// </summary>
/// <param name="nodeDepth">The depth of the nodes to debug.</param>
void DebugNodes(int nodeDepth)
{
// Get the root node
BVHNode rootNode = nodes[0];
// Initialize lists to hold parent and child nodes
List<BVHNode> parentNodes = new List<BVHNode>();
List<BVHNode> childNodes = new List<BVHNode> { rootNode };
// Iterate through the specified depth
for (int depth = 0; depth < nodeDepth; depth++)
{
// Transfer child nodes to parent nodes
parentNodes.Clear();
parentNodes.AddRange(childNodes);
childNodes.Clear();
// Add children of the current parent nodes to the childNodes list
foreach (BVHNode parentNode in parentNodes)
{
if (parentNode.leftChildIndex != uint.MaxValue)
{
childNodes.Add(nodes[(int)parentNode.leftChildIndex]);
childNodes.Add(nodes[(int)parentNode.rightChildIndex]);
}
}
}
// Draw the bounds and triangles of the child nodes
for (int i = 0; i < childNodes.Count; i++)
{
Color color = (i % 2 == 0) ? Color.green : Color.red;
color.a = 0.5f;
// Draw the triangles of the node
DebugTris(childNodes[i].tris, verts, bvhTargetObject.transform, 5, color);
// Draw the bounds of the node
color.a = 1f;
DrawBounds(childNodes[i].minBounds, childNodes[i].maxBounds, bvhTargetObject.transform, 5, color);
}
// Log a message if no nodes are found at the specified depth
if (childNodes.Count == 0)
{
Debug.Log("No nodes at this depth");
}
}
/// <summary>
/// Draws the axis-aligned bounding box (AABB) with the specified minimum and maximum bounds.
/// </summary>
/// <param name="min">The minimum bounds of the AABB.</param>
/// <param name="max">The maximum bounds of the AABB.</param>
/// <param name="objectTransform">The transform of the object to which the AABB is relative.</param>
/// <param name="duration">The duration for which the lines should be visible.</param>
/// <param name="color">The color of the lines.</param>
void DrawBounds(Vector3 min, Vector3 max, Transform objectTransform, float duration, Color color)
{
// Calculate the transformed positions of the eight corners of the AABB
Vector3 corner1 = objectTransform.TransformPoint(new Vector3(min.x, min.y, min.z));
Vector3 corner2 = objectTransform.TransformPoint(new Vector3(min.x, min.y, max.z));
Vector3 corner3 = objectTransform.TransformPoint(new Vector3(min.x, max.y, max.z));
Vector3 corner4 = objectTransform.TransformPoint(new Vector3(min.x, max.y, min.z));
Vector3 corner5 = objectTransform.TransformPoint(new Vector3(max.x, min.y, min.z));
Vector3 corner6 = objectTransform.TransformPoint(new Vector3(max.x, min.y, max.z));
Vector3 corner7 = objectTransform.TransformPoint(new Vector3(max.x, max.y, max.z));
Vector3 corner8 = objectTransform.TransformPoint(new Vector3(max.x, max.y, min.z));
// Draw bottom square of the AABB
Debug.DrawLine(corner1, corner2, color, duration);
Debug.DrawLine(corner2, corner6, color, duration);
Debug.DrawLine(corner6, corner5, color, duration);
Debug.DrawLine(corner5, corner1, color, duration);
// Draw top square of the AABB
Debug.DrawLine(corner4, corner3, color, duration);
Debug.DrawLine(corner3, corner7, color, duration);
Debug.DrawLine(corner7, corner8, color, duration);
Debug.DrawLine(corner8, corner4, color, duration);
// Draw vertical lines connecting the top and bottom squares
Debug.DrawLine(corner1, corner4, color, duration);
Debug.DrawLine(corner2, corner3, color, duration);
Debug.DrawLine(corner6, corner7, color, duration);
Debug.DrawLine(corner5, corner8, color, duration);
}
/// <summary>
/// Draws the triangles and their centroids for debugging purposes.
/// </summary>
/// <param name="tris">The list of triangles to debug.</param>
/// <param name="verts">The array of vertices.</param>
/// <param name="objectTransform">The transform of the object to which the triangles are relative.</param>
/// <param name="duration">The duration for which the lines should be visible.</param>
/// <param name="color">The color of the lines and centroids.</param>
void DebugTris(List<NodeTriangle> tris, Vector3[] verts, Transform objectTransform, float duration, Color color)
{
// Iterate through each triangle in the list
for (int i = 0; i < tris.Count; i++)
{
// Transform the vertices of the triangle to world space
Vector3 vert1 = objectTransform.TransformPoint(verts[tris[i].index1]);
Vector3 vert2 = objectTransform.TransformPoint(verts[tris[i].index2]);
Vector3 vert3 = objectTransform.TransformPoint(verts[tris[i].index3]);
// Transform the centroid of the triangle to world space
Vector3 centroid = objectTransform.TransformPoint(tris[i].centroid);
// Draw the edges of the triangle
Debug.DrawLine(vert1, vert2, color, duration);
Debug.DrawLine(vert2, vert3, color, duration);
Debug.DrawLine(vert3, vert1, color, duration);
// Draw the centroid of the triangle
DebugExtensions.DrawPosition(centroid, 0.01f, color, duration, true);
}
}