3Dの線と三角間の交差

Question

3D空間のどこかに線と三角形があります。言い換えれば、私は三角形の3点（それぞれ[x、y、z]）とその線の2つの点（[x、y、z]）を持っています。

私は、線が三角形を横切るかどうかを判断するために、C++を使ってうまくいけばよい方法を見つけ出す必要があります。三角形に平行で、複数の点が共通する線は、「交差しない」と数えます。

私はすでにいくつかのコードを作っていますが、それはうまくいかず、視覚的な表現が明確に交差点を示しても、私は常にfalseになります。

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()の幾何学的プロ
• このコードは、最初は上記の方法に従っていますが、交点が3D軸にあることを確認するだけです（この場合、線分[P1、P2]の一列整列された境界ボックス。可能性のある他のエラーと組み合わされて、なぜ結果が正しくないのか説明することができます。
• 交点が（全体の）三角形の3D軸に沿った境界ボックスにあることを確認できます。交差点を保証するには十分ではありませんが、交差しない点を明示的に切り抜き、さらに複雑な計算を避けるために使用できます。

Answer 2

1）あなただけのラインが交差点を必要とせずに三角形を（）と交差かどうかを知りたい場合は、次の

は、P1、P2、P3あなたの三角形

は2ピック表すと両方の方向に非常に遠く離れたライン上の点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（、B、C、D）=（1/6）*ドット（クロス（BA、CA）、DA）

2）今、あなたは交差点を、必要な場合と、テスト中 - ドット（P、N）：P（T）= Q1 + T *（Q2-Q1）

は、平面の方程式を書く：1）

パラメトリック形式の行の式を書く通過【数1】ここで、N =クロス（p2-p1、p3-p1）

面の方程式にp（t）を注入する：dot（q1 + T×（Q2-Q1）、N-P1）= 0

推定T = -dot（q1は、N-P1）/ドット（Q1、Q2-Q1）

交点Q1であり+ t *（q2-q1）