如何高效地檢測光線和網格的交點檢測？

Question

我在OpenGL ES應用程序中爲iPhone提供了幾個3D模型，並且在某些時候我希望用戶觸摸屏幕並對其執行操作。問題是要識別屏幕上呈現的內容中的哪些被觸摸。爲了達到這個目的，我計算了OpenGL常見問題解答中提出的拾取光線，現在我想檢測它是否與任何模型相交。

我擡頭看看irrlicht源代碼，發現我可以計算光線和每個單個模型三角形之間的交集（他們通過計算光線是否先與三角形平面相交，然後通過查看相交點落入三角形，但是如here所述，存在更有效的方式）。

我的問題是：我真的需要爲每個模型的每個三角形做所有這些計算嗎？沒有更好的方法（可能不是那麼精確）來達到類似的結果嗎？

Answer 1

你很對，有更好的方法來通過樹。一種方法是圍繞對象構建一個octtree。然後，如果射線與8個線段中的一個相交，則可以檢查它的8個子線中的哪一個相交，等等，直到剩下幾個三角形進行相交測試爲止。另一種方法是建立一個K-d tree。

有很多種方法可以有效地處理這個問題。在ray tracing acceleration structures上查找信息。