Ray和三維人臉交叉口

Question

我具有由n點（v1，v2，v3，...，vn）所定義的三維人臉，在三維座標，和我有方程的射線：

P=P0+t(P1-P0)。

其中0<=t<=1。

現在，如何找到這個光線和臉部之間的交點（或缺乏）？

另外，如果有一個現有的C＃實現，這將是非常好的？

編輯：3D面可凹或凸。所有的點都是共面的。

Answer 1

我想你的3D多邊形是平面的（否則就不是一個真正的多邊形，這不是很好定義）。因此，您可以找到該平面的二維正交基準。這意味着您可以使用任何二維三角算法（您可以在網上找到許多c＃實現），並使用您的正交基準返回到3D。 通過這種方式，您將獲得3D三角形，並且可以通過運行多個光線 - 三角形相交測試輕鬆進行光線多邊形相交測試。

另一種方法是執行射線平面相交計算。取交點P，用上面標準正交基的二維座標表示。另外，與以前的解決方案一樣，使用相同的基礎以2D表示您的多邊形。然後運行任何「點在多邊形」2D算法，你會得到你的結果。

更新：這裏是 您可以在平面P1上任意兩點數學，P2（例如兩個多邊形的點），並採取向量u = P2 - P1。規範化它，它是第一個基礎向量。然後你採取飛機的正常N並且計算v = cross_product（u，N）並且歸一化v這是第二個基本向量。請注意，兩個矢量都有單位長度，它們彼此正交。因此它們形成了一個正交基準。

現在將p1定義爲飛機的原點。然後翻譯，以任何點Q的2D多邊形（Q可以是多邊形的頂點之一，或多邊形的平面上的任何其他點）：

x = dot_product(q - p1, u) 
y = dot_product(q - p1, v) 

這裏x，y是該點的二維座標。

所以翻譯的一切2D和做你的二維算法後，你可以把任何2D點（x，y）的回3D這樣的：

q = p1 + x * u + y * v 

這裏*是標量向量積（X， y是標量，u，v是向量）。

Alex。

Answer 2

你是一個光線 - 多邊形相交算法後，這裏的圖形寶石條目的鏈接吧：http://www-graphics.stanford.edu/courses/cs348b-98/gg/intersect.html

Answer 3

如果你的點不是共面的（也就是說不是全部位於一個平面上），那麼你需要將表面細分爲一組平面，然後爲每個平面做線多邊形交點。更好的是，定義一個三角形列表，然後在線 - 三角形交集結果上進行搜索。

但是，您不會說您的點是否定義了多面體（即由三角形構成）或爲曲面定義了一組控制點。前者由上述處理。如果它是一個曲面，我認爲這是一個不可解決的問題，也就是說，確定由一組點定義的直線和曲面的交點的問題並不是微不足道的解決方案。您可以做的最好的方法是使用迭代過程來找到相交點，但即使這樣也會導致搜索不穩定（即從未完成的搜索）。

我認爲轉換爲一組三角形是最好的答案。