sha*_*eve 14 algorithm physics kdtree game-physics
我目前正在为物理引擎(Hobby项目)编写KDTree.
KDTree不包含点数.相反,它包含Axis Aligned边界框,它绑定环境中的不同对象.
我的问题是决定如何在KDTree节点满了时拆分它们.我正在尝试2种方法:
方法1:始终将节点在最大轴上精确地分成两半.
方法2:查找包含对象的节点区域.拆分平面上的节点,该节点将该区域在其最大轴上分成两半.示例 - 如果所有对象都集中在节点的底部,则它按长度方式分割,从而将底部分成两部分.
所以我在这里寻找的是分割我的KD-Tree节点的更好方法.考虑到这将是一个物理引擎,决策需要足够简单,以便实时进行.
cel*_*ion 23
"表面区域启发式"(SAH)被认为是构建kd树的最佳分裂方法,至少在光线追踪社区内.我们的想法是添加平面,使两个子空间的表面区域相等,每个子区域的对象数量加权.
关于这个主题的一个很好的参考是Ingo Wald的论文,特别是第7.3章"高质量的BSP结构",它更好地解释了SAH.
我目前找不到一个好的链接,但是你应该四处寻找关于"binned"SAH的论文,这是真正的SAH的近似但更快.
所有这一切,边界体积层次结构(BVH)又名AABB树,现在似乎比kd树更受欢迎.同样,Ingo Wald的出版物页面是一个很好的起点,可能是"基于SAH的快速构建边界体积层次结构"的论文,尽管自从我阅读它以来已经有一段时间了.
该OMPF论坛也是一个不错的地方来讨论这些事情.
希望有所帮助.祝好运!