查找包含點的2D網格中的多邊形

Question

我有一個3D多邊形網格和相應的2D多邊形網格（實際上來自UV map），我正用它來將幾何圖形映射到2D平面上。考慮到飛機上的一個點，我怎樣纔能有效地找到它所在的多邊形，以便將該2D點映射回3D？

我能想到的最佳方法是將多邊形存儲在2D區間樹中，並使用它來獲取候選多邊形。有一個更簡單的方法嗎？

爲了澄清，這不是着色器。我實際上正在進行2D物理模擬並將其渲染爲3D網格。對於繪製每個對象，我需要弄清楚3D中的哪個點對應於它的真實2D位置。*

Answer 1

我看過的三角形網格的一種方法如下：選擇一個三角形，想象每個邊定義了一半的空間。對於給定的邊，半空間邊界是包含邊的線，半空間不包含三角形。選擇一個邊緣，其相應的半空間包含您的目標點。然後選擇邊緣另一側的三角形，然後重複該過程。

使用這種方法，您最終會到達包含您的目標點的三角形。

這種方法比實現2D間隔樹有爭議簡單，儘管搜索的效率較低（如果n是三角形的數量，它是O（√ N），而不是O（log n）的，另外，它應該只要多邊形凸出來就可以工作

Answer 2

所以，如果我試圖剛剛實現的東西，我可能會開始全局搜索所有三角形 - 計算重心的座標每個三角形的2d點，找出重心座標都爲正的三角形，然後用它們映射到3d（把3d位置乘以stu位置），我會先做，並且只有在速度不夠快我會嘗試更復雜的東西嗎？

如果可以通過三角形而不是2d點進行迭代，那麼重心方法可能會足夠快。但是似乎你在任意位置有一堆需要被映射的2d點，並且這些點會在幀之間改變位置？

如果你有這種情況，你可能會通過實現每幀本地更新大大加速。每個2d點都會記住它所在的三角形。將其設置爲當前三角形。測試新位置是否在當前三角形內。如果不是，那麼你需要將網格移動到最接近目標2d點的相鄰三角形。每個邊緣相鄰的三角形由邊上的兩個公共點和另一個點組成。查找哪個邊緣相鄰三角形的其他點最接近目標，並將其設置爲當前。然後迭代 - 似乎它應該很快找到它？你也可以爲每個三角形緩存一個最大尺寸，所以如果這個點已經移動了很多，你可以迭代到下一個鄰居而不進行重心計算（最大尺寸需要是這樣的距離，如果你比那更遠距離任何三角點的距離都不可能在三角形內部，這是最大邊緣的長度）。

但正如您在評論中提到的那樣，您可能會遇到具有凹陷，孔洞或單獨連接組件的網格問題，您可能會陷入局部最小值。有幾種方法可以解決這個問題。我認爲最簡單的方法是保留所有訪問過的三角形列表（可能是三角形上的一個標記，或者設置<三角形索引>），並拒絕重新訪問三角形。如果您發現您訪問了當前三角形的所有鄰居，則可以返回到全局搜索。這種失敗可能不常見，因此它不應該太多地損害你的表現。

這種每幀更新可以非常快，甚至可能是一個體面的方法來計算初始包含三角形 - 只需選擇一個隨機的三角形並從那裏走（從檢查所有n個三角形到只有那些與目標大致成直線）。如果速度不夠快，你可以做的是保持2D網格點的k-d樹（或類似物）以及每個網格點的單個觸摸三角形索引。要對迭代進行種子處理，請在k-d樹中找到距離目標2d點最近的點，將相鄰三角形設置爲當前值，然後進行迭代。