algorithm - 八叉树 - 移动物体会影响哪些细胞？

Question

我想使用八叉树作为 OGL 场景表示，并且其中有一些移动对象。我还想用这个八叉树来加速碰撞检测。是否有任何好的算法可以为您提供移动物体将穿透的八叉树路径(此类路径的所有单元格/节点)？

假设我有一个我知道速度的移动物体(所以两个位置，一帧中的运动开始和运动结束)。

我的想法是简单地遍历整个树并对包含移动对象的单元格和其余单元格执行碰撞检测。那会给我所有的人，但这不是矫枉过正吗？谢谢!

Answer 1

如果您有移动物体的开始和结束位置，那么您就有一条定义物体运动的射线。八叉树中的一个节点是一个长方体，它是一个相当简单的多面体。您可以将碰撞/相交测试视为射线-长方体相交测试。

查看此页面上的对象-对象交集算法:

http://www.realtimerendering.com/intersections.html#II247

该页面指向 Github 上关于射线-多面体相交的代码:

https://github.com/erich666/GraphicsGems/blob/master/gemsii/RayCPhdron.c

从一个简单的例子开始，假设您的对象只是一个沿着运动射线移动的点。然后你可以使用射线-长方体相交找​​到物体的路径。如果八叉树的一个节点不包含射线，则没有必要更深入地搜索该节点的子节点。 (从上到下搜索整个八叉树首先违背了创建八叉树的目的。)即使您的对象是具有许多顶点的复杂事物，也可以编写代码为运动中的一个点进行简单的射线/长方体相交将具有指导意义。

Schneider 和 Eberly 合着的计算几何书籍计算机图形学几何工具对线多面体相交有很好的处理，包括一页易于理解的伪代码。如果您打算花很多时间编写 3D 几何体代码，那么您会希望书架上放一本那本书。 Eberly 在他的网站上还有许多有用的 PDF:

https://www.geometrictools.com/

如果您创建八叉树，使每个节点都有一个指向其直接邻居的指针，那么这可能会稍微加快搜索速度。不过，我不建议一开始就实现——首先创建一些简单的东西，而不是一次处理多个实现任务。

举一个稍微复杂一点的例子，如果你有一个由 3 个顶点组成的三角形，三角形的表面法线平行于运动方向，那么三角形与八叉树的长方体节点的相交测试将很简单;测试从每个顶点开始并平行于运动方向的射线与长方体的交点。

从那里开始，您的方法可能会有所不同，具体取决于移动物体的复杂性和您对“碰撞”检测的需求。例如，您可能不仅允许交叉路口被视为碰撞，而且还允许将一个对象非常接近地传递到另一个对象。我不知道你的应用程序是什么，你的对象有多复杂，对象是否近似凸等，但你可以考虑测试与对象的凸包的碰撞，或者可能与包含的球体/立方体对象中的所有点。