我想使用八叉树作为OGL场景表示，并且我有一些移动的对象。我还想使用这个八叉树来加速碰撞检测。有没有好的算法可以为您提供八叉树中的路径（该路径的所有单元格/节点），移动物体会穿透？
假设我有一个移动物体，我知道速度（所以两个位置，运动的开始和运动的结束在一个帧中）。
我的想法是简单地遍历整个树，并对包含移动物体的细胞和其余细胞进行碰撞检测。那会给我所有这些，但这不是矫枉过正吗？谢谢！
如果你有移动物体的起点和终点位置，那么你就有一条射线来定义你的物体的运动。八叉树中的一个节点是一个长方体，它是一个相当简单的多面体。您可以将碰撞/相交测试视为射线-长方体相交测试。
查看此页面上的对象-对象交集算法：
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 个顶点组成的三角形，使三角形的表面法线平行于运动方向，那么三角形与八叉树的长方体节点的相交测试将很简单;测试射线-长方体相交，以发现从每个顶点开始并平行于运动方向的光线。
从那里开始，您的方法可能会有所不同，具体取决于移动物体的复杂性和您对"碰撞"检测的需求。例如，您不仅可以允许将相交视为碰撞，还可以允许将一个对象视为另一个对象的非常接近的传递。我不知道你的应用程序是什么，你的对象有多复杂，对象是否近似凸，等等，但你可以考虑测试与对象的凸包的碰撞，或者可能与包含对象中所有点的球体/立方体的碰撞。