Ray-triangle intersetion

Question

我該如何測試射線和三角形，以及它是否存在如何獲得從射線原點到交點的距離？ 我可以使用哪些優化，如果在我的程序中，我必須檢查1個射線〜10000個三角形？

Answer 1

單個多邊形射線相交測試是微不足道的，只需確保射線至少穿過其一側（單獨檢查它們）或穿過由它們兩側之間的三角形定義的平面。優化進入不檢查多邊形射線沒有任何交叉的機會。取決於您工作的維度有多高，面積有多大，以及您處理最典型優化的多邊形數量是quadtrees，octrees和kd-trees。這也大致是實施難度的順序（儘管四元組和八元組非常相似）。

Answer 2

可能是我第一次需要實現它，我看了看這些幻燈片，我發現它非常有用。

http://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/raycast/sld016.htm

首先確保你瞭解它是如何工作的，那麼你可以做很多不同的優化。例如：

if (dot(V, N) >= 0)  // no intersection - ray points away from the triangle face 
if (dot(P0, N) + d < 0) // no intersection - ray origin is behind the triangle face 

另一個想法是我找到了光線和臉部的交點。我曾經在2D中檢查三角形內的點，而我正在用正常的最大絕對值對軸進行調零...如果abs（Nx）> abs（Ny）> abs（Nz）我將執行檢查YZ飛機。

我可以建議另一個簡單的實現優化找到外接圓的中心和半徑（很好取決於你是否需要經常做，你可以選擇像質心這樣的easer中心）。現在這個點和半徑定義了一個三角形周圍的邊界球。現在你可以做更快的射線球體剔除。

http://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/raycast/sld012.htm

不解決整個多項式你不需要光/球的交點只是檢查存在的根源。

你可以做很多其他的優化，例如：如果你的頂點和法線可以以更多的SSE友好結構排列，那麼你一次可以做4次檢查。這大概可以快2.5倍左右。