八叉樹 - 移動對象影響什麼細胞？

Question

我想使用八叉樹作爲OGL場景表示，並且在那裏有一些移動對象。我也想用這個八叉樹來加速碰撞檢測。有沒有什麼好的算法可以爲你提供八叉樹路徑（移動物體穿透的所有單元/路徑）？

假設我有一個移動物體，我知道速度（所以兩個位置，移動的開始和一幀中移動的結束）。

我的想法是簡單地通過整個樹並執行包含移動對象和其他單元的單元的碰撞檢測。這會給我所有人，但這不是一個矯枉過正的？ 謝謝！

Answer 1

如果您有移動物體的開始和結束位置，那麼您就有一條射線來定義物​​體的運動。八叉樹中的一個節點是一個長方體，它是一個相當簡單的多面體。您可以將碰撞/相交測試視爲光線立方體相交測試。

查看此頁面上的對象，對象交叉路口算法：

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

該網頁指向Github上的代碼射線多面體路口：

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

首先一個簡單的例子，假設你的物體只是沿着那條運動線行進的一個點。然後，您可以使用ray-cuboid交叉找到對象的路徑。如果八叉樹的節點不包含射線，那麼搜索更深入到該節點的子節點沒有任何意義。 （從上到下搜索整個八叉樹，首先破壞了創建八叉樹的目的。）即使您的對象是一個有許多頂點的複雜事物，編寫代碼以爲運動中的一個點執行簡單的射線/立方體相交將具有啓發性。

計算幾何圖書Schneider和Eberly對計算機圖形學的幾何工具有很好的線處理多面體交集，包括一個易於理解的僞代碼頁面。如果您要花費很多時間編碼3D幾何圖形，則需要在書架上放置該書的副本。 Eberly先生也有一些在他的網站有幫助的PDF文件：

https://www.geometrictools.com/

如果您創建八叉樹，使得每個節點都有一個指向其近鄰，那麼這可能會加快搜索了一下。但我不會建議在開始時實施 - 首先創建簡單的東西，而不是一次處理多個實施任務。舉一個稍微複雜的例子，如果你有一個三角形的三個頂點取向，以便三角形的表面法線與運動方向平行，那麼三角形與八叉樹立方體節點的交點測試將會是直截了當;測試從每個頂點開始並平行於運動方向的射線 - 長方體相交。

從那裏你的方法可能會有所不同，這取決於移動物體的複雜性和你對「碰撞」檢測的需求。例如，您可能不僅允許將交叉點視爲碰撞，而且還可以將一個對象視爲非常接近另一個對象。我不知道你的應用程序是什麼，你的對象可能有多複雜，對象是否近似凸出等等，但是你可以考慮測試與對象凸包的碰撞，或者用包含球體/立方體的測試對象中的所有點。