Jim's GameDev Blog

UE4 的 kDopTree

2017-6-15

UE4 中的 kDopTree 是使用二叉树对空间中的三角形进行划分,并使用 Ray-Slab Intersection 进行线段和包围盒碰撞检测,最终对线段和包围盒中的三角形进行相交检测。其目的是为了加快离线生成 SDF 的速度。下面会对这个算法的细节进行说明和总结。

以下分析是基于 UE4 的 14.15版本

构建 kDopTree

在三维空间中使用一维的方式进行构建,也就是说只考虑其中的一根轴(x轴 或 y轴 或 z轴),那么挑选哪根轴呢?首先计算所有三角形的几何中心的平均数,得到的值就可以近似认为是模型的几何中心,然后计算所有三角形偏离几何中心的方差,方差越大说明三角形更越偏离几何中心。因为几何中心是个三维值,所以方差也是三维的,分别对应 x轴、y轴、z轴,挑选最大方差对应的轴来进行二叉树的构建。

为什么选择最大的方差呢?其实无论选择哪个都不会影响到最终结果的正确性,我觉得这么做是为了后面加快碰撞检测的速度。因为方差越大,三角形越偏离几何中心,也就是说所有的三角形位置在整体上来看就越平坦,碰撞检测时就可以减少线段和多个 AABB 以及多个三角形同时发生相交的概率。

挑选构建轴之后就要开始构建 kDopTree 了。先将所有三角形坐标按照构建轴进行大致排序,偏大的值放到靠近数组右边,偏小的值靠近数组的左边,然后对数组左边部分和右边部分重复这个操作,这其实就像二分排序一样。每一次二分排序都会形成一个二叉树节点,节点需要记录一个 AABB 包围盒,AABB 的大小是所有当前排序三角形的包围盒(二叉树当前节点的子节点下所有三角形的三维范围)。最后,当需要排序的三角形数量少到一定值时(UE4 中是4个三角形),就认为不需要再继续排序了,这时就可以生成叶子节点,叶子节点需要记录包含了哪些三角形和一个 AABB 包围盒。

至此 kDopTree 构建完成。

kDopTree 简图

碰撞检测

使用 kDopTree 对线段和三角形进行碰撞检测。

在 kDopTree 中已经构建好了包围盒层级关系,检测线段和父级 AABB 是否相交,如果相交再继续迭代子 AABB 直到找到叶节点,最后使用叶子节点上记录的三角形和线段进行碰撞检测。

关于线段和 AABB 的碰撞检测可以参考 Slab-based-Intersection

最后是线段和三角形的碰撞检测。先判断线段是否和三角形所在平面相交,根据平面方程 Ax + By + Cz + D = 0 判断线段两点是否在平面同侧(排除掉这个情况),求出线段和平面的交点,并判断交点是否在三角形内。上文中说了,kDopTree 的叶节点上有四个三角形,所以需要对四个三角形进行同样的检测,挑选一个和线段距离最近的交点。

至此完成碰撞检测。

进一步加速计算

在 UE4 中,使用了 SIMD 进一步加快了计算速度,简单来说,就是可以将一条线段同时和四个 AABB 进行相交检测,可以同时和四个三角形进行相交检测,这也是为什么 kDopTree 的叶节点选择四个三角形的原因。