0

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

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

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

4

1 回答 1

3

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

查看此页面上的对象-对象相交算法：

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

该页面指向 Github 上用于射线多面体相交的代码：

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

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

Schneider 和 Eberly的计算几何书籍Geometric Tools for Computer Graphics很好地处理了多面体交集，包括一页易于理解的伪代码。如果您要花费大量时间编写 3D 几何图形，则您需要在书架上放一本该书。Eberly 在他的网站上还有许多有用的 PDF：

https://www.geometrictools.com/

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

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

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

于 2016-02-22T05:43:01.367 回答