全局
MeshBVH
SerializedBVH
MeshBVHVisualizer
ExtendedTriangle
OrientedBox
Raycaster
StaticGeometryGenerator
GenerateMeshBVHWorker

MeshBVH

MeshBVH是基于三维三角形网格的加速数据结构,用于快速进行光线追踪、碰撞检测等操作。该结构是基于BVH(包围盒层次结构)的,但是在BVH的基础上进行了一些优化,比如使用了SAH(表面面积启发式)算法进行节点划分,采用了ray-primitive相交测试等。

组件

MeshBVH由两个主要组件组成:

八叉树(Octree)

八叉树是用于划分三角形网格的空间层次结构。该结构将空间划分为八个子区域,每个子区域由一个边长相等的正方体表示,所有正方体共同组成了一个立方体。在八叉树中,一个非叶子节点的每个子节点又是一个八叉树,直到划分到叶子节点,该节点被包含在对应的正方体内部,且所有该节点上的三角形都被分配到该节点中。

BVH节点(BVH Node)

BVH节点用于保存网格中的每个三角形的包围盒信息。每个节点有两个子节点,分别对应该节点的左右子树。对于叶子节点,保存在该节点中的三角形信息包括:三角形顶点坐标、表面法向量、纹理坐标等。

算法

MeshBVH采用SAH算法进行节点的划分,以减小节点之间的重叠量。同时,该结构还使用了ray-primitive相交测试,加速了光线追踪和碰撞检测操作。

SAH

表面面积启发式(SAH)算法是一种用于决定如何划分节点的贪心算法。对于每个候选的划分平面,SAH计算划分总代价(总表面积+子节点代价之和),然后选择总代价最小的划分位置作为该节点的划分平面。

ray-primitive相交测试

ray-primitive相交测试是一种用于检测光线和物体之间是否相交的方法。该方法通过计算光线与三角形的交点来确定是否相交,同时还可以计算出相交点的坐标、法向量等信息。

参考资料

  1. Real-Time Collision Detection, Christer Ericson.
  2. What's New in Three.js: MeshBVH and ND-Array Buffers