線條和三角形之間的交點在3D中

Question

我在三維空間中有一條線和一個三角形。換句話說，對於三角形，我有3個點（[x，y，z]），對於這條線我有兩個點（也是[x，y，z]）。

我需要弄清楚一種方法，希望使用C++來判斷這條線是否穿過三角形。平行於三角形且具有多於一個共同點的線應被視爲「不相交」。

我已經做了一些代碼，但它不起作用，並且即使當視覺表示清楚地顯示交叉點時，我也總是得到錯誤。

ofVec3f P1, P2; 
P1 = ray.s; 
P2 = ray.s + ray.t; 

ofVec3f p1, p2, p3; 
p1 = face.getVertex(0); 
p2 = face.getVertex(1); 
p3 = face.getVertex(2); 

ofVec3f v1 = p1 - p2; 
ofVec3f v2 = p3 - p2; 

float a, b, c, d; 

a = v1.y * v2.z - v1.z * v2.y; 
b = -(v1.x * v2.z - v1.z * v2.x); 
c = v1.x * v2.y - v1.y * v2.x; 
d = -(a * p1.x + b * p1.y + c * p1.z); 

ofVec3f O = P1; 
ofVec3f V = P2 - P1; 

float t; 

t = -(a * O.x + b * O.y + c * O.z + d)/(a * V.x + b * V.y + c * V.z); 

ofVec3f p = O + V * t; 

float xmin = std::min(P1.x, P2.x); 
float ymin = std::min(P1.y, P2.y); 
float zmin = std::min(P1.z, P2.z); 

float xmax = std::max(P1.x, P2.x); 
float ymax = std::max(P1.y, P2.y); 
float zmax = std::max(P1.z, P2.z); 


if (inside(p, xmin, xmax, ymin, ymax, zmin, zmax)) { 
    *result = p.length(); 
    return true; 
} 
return false; 

這裏是）內部的定義（

bool primitive3d::inside(ofVec3f p, float xmin, float xmax, float ymin, float ymax, float zmin, float zmax) const { 
    if (p.x >= xmin && p.x <= xmax && p.y >= ymin && p.y <= ymax && p.z >= zmin && p.z <= zmax) 
     return true; 

    return false; 
} 

Answer 1

要查找的線和在3D一個三角形之間的交叉點，按照這種方法：

• 計算平面支撐三角形，

• 與支撐三角形的平面相交的線條：

  • 如果沒有交點，那麼與三角形沒有交點。

  • 如果有交叉點，驗證交點確實在於三角形：

    • 三角形與正常支撐的三角形的平面一起的每個邊緣判斷半空間包圍的內部（相應的邊界平面可以從法線和邊緣頂點導出），
    • 驗證交點位於所有邊緣半空間的內部。

下面是詳細的計算示例代碼，應該工作：在貼有問題的代碼

// Compute the plane supporting the triangle (p1, p2, p3) 
//  normal: n 
//  offset: d 
// 
// A point P lies on the supporting plane iff n.dot(P) + d = 0 
// 
ofVec3f v21 = p2 - p1; 
ofVec3f v31 = p3 - p1; 

ofVec3f n = v21.getCrossed(v31); 
float d = -n.dot(p1); 

// A point P belongs to the line from P1 to P2 iff 
//  P = P1 + t * (P2 - P1) 
// 
// Find the intersection point P(t) between the line and 
// the plane supporting the triangle: 
//  n.dot(P) + d = 0 
//     = n.dot(P1 + t (P2 - P1)) + d 
//     = n.dot(P1) + t n.dot(P2 - P1) + d 
// 
//  t = -(n.dot(P1) + d)/n.dot(P2 - P1) 
// 
ofVec3f P21 = P2 - P1; 
float nDotP21 = n.dot(P21); 

// Ignore line parallel to (or lying in) the plane 
if (fabs(nDotP21) < Epsilon) 
    return false; 

float t = -(n.dot(P1) + d)/nDotP21; 
ofVec3f P = P1 + t * P21; 

// Plane bounding the inside half-space of edge (p1, p2): 
//  normal: n21 = n x (p2 - p1) 
//  offset: d21 = -n21.dot(p1) 
// 
// A point P is in the inside half-space iff n21.dot(P) + d21 > 0 
// 

// Edge (p1, p2) 
ofVec3f n21 = n.cross(v21); 
float d21 = -n21.dot(p1); 

if (n21.dot(P) + d21 <= 0) 
    return false; 

// Edge (p2, p3) 
ofVec3f v32 = p3 - p2; 
ofVec3f n32 = n.cross(v32); 
float d32 = -n32.dot(p2); 

if (n32.dot(P) + d32 <= 0) 
    return false; 

// Edge (p3, p1) 
ofVec3f n13 = n.cross(-v31); 
float d13 = -n13.dot(p3); 

if (n13.dot(P) + d13 <= 0) 
    return false; 

return true; 

一些評論：

• 的預定義的操作ofVec3f（.dot()和.cross() for geometric pro管道等）應該是首選的時候（更可讀，避免執行錯誤等），
• 代碼最初遵循上面的方法，但只檢查交點是否在3D軸 - 線段[P1，P2]的對齊邊界框。這與其他可能的錯誤相結合可以解釋爲什麼結果不正確。
• 可以驗證交點是否位於（整個）三角形的3D軸對齊邊界框中。雖然這不足以保證相交，但它可以用來清楚地顯示不相交的點，並避免進一步複雜的計算。

Answer 2

1）如果你只是想知道行是否相交的三角（無需交叉口）：

令P1，P2，P3表示你的三角形

選兩個點q1，q2在兩個方向很遠的線上。設SignedVolume（a，b，c，d）表示四面體a，b，c，d的有符號體積。

如果SignedVolume（Q1，P1，P2，P3）從SignedVolume不同（Q2，P1，P2，P3）AND SignedVolume（Q1，Q2，P1，P2），SignedVolume（Q1，Q2，P2，P3）和SignedVolume（q1，q2，p3，p1）具有相同的符號，則存在交集。

SignedVolume（A，B，C，d）=（1/6）*點（交叉（BA，CA），DA）

2）現在如果你想的交叉點，當測試在1）穿過

寫入參數形式的直線的方程：p（T）= Q1 + T *（Q2-Q1）

收件的平面的方程：點（p，N） - （p，p1）= 0其中N =交叉（p2-p1，p3-p1）

將p（t）注入到平面方程中：dot（q1 + T *（Q2-Q1），N-P1）= 0

推斷噸= -dot（Q1，N-P1）/點（Q1，Q2-Q1）

交點是Q1 + t *（q2-q1）