我有一組組成任意幾何的三角形（從 OFF 檔案中讀取）。每個三角形由三個頂點定義，它們是 3D 點。我有一個觀察點，我想從物件中洗掉所有不可見的頂點，這意味著連接觀察點和頂點的線段不與任何三角形相交。
需要注意的是，單個物件中的頂點和三角形的數量是 10^4 中的另一個。一個簡單的方法是遵循 [1] 接受的答案，它使用簽名的卷。我已經實作了它，但它包括兩個嵌套的 for 回圈：對于每個頂點，我需要檢查到觀察點的線是否與任何三角形相交。當然，當它與一個相交時，我打破了外觀，但它仍然導致對簽名卷函式的 192M 呼叫。
一些有效的演算法 [2] 假設一條無限線，而不是一條線段，這會導致洗掉頂點，即使相交是與更遠的三角形。關于如何有效解決這個問題的任何想法？
[1] 3D 中線與三角形的交點
[2] M?ller 和 Trumbore，《快速、最小存盤射線三角交點》，圖形工具雜志，第一卷。2，1997 年，第 21–28
uj5u.com熱心網友回復：
您的問題陳述實際上是一個光線跟蹤問題：查找一堆點是否被幾何體遮擋。因此，您可以應用任何光線追蹤技巧來加快速度；即在您的模型上建立一些空間索引并使用該空間索引跟蹤光線。一些最常見的空間索引是 BVH、BSP 樹或 kd 樹。
如果近似解決方案足夠好，您可以從有利位置柵格化幾何圖形，然后針對生成的 Z 緩沖區測驗所有頂點。
請注意，這兩種方法中的任何一種都會過濾頂點（這是您要求的）。然而，一些三角形可能是可見的，即使它們的所有頂點都被遮擋。這些三角形也將被洗掉，即使它們是可見的。光柵化方法很容易修改以過濾三角形而不是頂點。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505871.html
上一篇：多個排序陣列中的第K個最小元素
下一篇：鏈接桶的最佳組合