多面體/球面射線相交確定？

Question

我正在尋找任何C++庫，它允許我獲取線和多面體/球體（其中線由兩個3D點和有限數量的3D點的多面體組成）之間的3D碰撞點

至於我的驚訝，我似乎無法找到這樣的圖書館（或我不知道要搜索哪些詞組）。我看過的大多數碰撞庫都是從2005/2006開始的（但沒有說過如何獲得碰撞點座標，其中大部分是用於可視化事物和檢查邊界，或者是兩個3d物體之間的碰撞等等。對我來說是過度殺傷 - 我只是想要一條線和一個3D對象[多面體/球體]之間的3D碰撞點）

那麼..哪些庫是最新的截至2013年，並利用新技術來實現最好的表現？

或者是否有我的情況的代碼示例？

我有時候喜歡重新發明輪子，但不是在這種情況下，我希望它將它用於遊戲插件 - 所以可靠和快速的東西是優先考慮的。

Answer 1

什麼是快速，高效的重複取決於有多少對象有，等沒有太多的點建立一個八叉樹或其他一些空間劃分如果你只是要測試一些對象。您可能會考慮嘗試找到包圍多面體的（邊界）球體（原點+半徑），然後測試以確定是否首先相交。或者一個軸對齊的邊界框（AABB）。

然後，您可以轉向更昂貴的多面體測試 - 這可能需要針對每個「前置」三角形進行測試。那麼如果物體不是凸的，就像網格一樣，在這種情況下你需要最小距離的光線。

參見：CGAL，Geometric Tools。

Answer 2

你檢查出http://clb.demon.fi/MathGeoLib/nightly/usermanual.html#features

這似乎是的Set of efficient 3D intersection algorithms