3D点が3D多面体の中にあるかどうかをテスト

Question

三角形メッシュで表される境界で定義された3D多面体を考えると、与えられた3D点が多面体の内部に属するかどうかを決定するアルゴリズムはどのように実装できますか？

Answer 1

この機能を実装する方法はいくつかあります。

最も簡単なのは、ポイントから始まって任意の方向に向かって無限光線（または非常に長いセグメント）を作成し、次に光線と三角形の間の交差点の数を数えることです。交点の数が奇数の場合、点は多面体の内部にあります。今

Inside(Polyhedron P, point q) 
    Segment S = [q, q+(0,0,1e30)] 
    count = 0 
    For each triangle T of P 
     If Intersect(S,T) 
      count = count + 1 
     End if 
    End for 
    return odd(count) 
End 

セグメントと三角形との交点が存在するか否かを計算する関数：ここで二つの大きな落とし穴がある

Orient3d(a,b,c,d) 
     // Computes the sign of the signed volume 
     // of the tetrahedron (a,b,c,d) 
     return Sign(dot(cross(b-a,c-a),d-a)) 
    End 

：

Intersect([q1,q2],(t1,t2,t3)) 
    s1 = orient3d(q1,t1,t2,t3) 
    s2 = orient3d(q2,t1,t2,t3) 
    // Test whether the two extermities of the segment 
    // are on the same side of the supporting plane of 
    // the triangle 
    If(s1 == s2) 
    return false 
    End if 
    // Now we know that the segment 'straddles' the supporing 
    // plane. We need to test whether the three tetrahedra formed 
    // by the segment and the three edges of the triangle have 
    // the same orientation 
    s3 = orient3d(q1,q2,t1,t2) 
    s4 = orient3d(q1,q2,t2,t3) 
    s5 = orient3d(q1,q2,t3,t1) 
    return (s3 == s4 AND s4 == s5) 
End 

最後に、orient3d機能：

1. Orient3dコンピューティング時に浮動小数点精度が不十分な場合はどうなりますか？

2. 選択したセグメントが 頂点または三角形のエッジを正確に通過するとどうなりますか？

については、任意の精密算術[1]を使用しなければならない。 [2]のリファレンス[1]（Jonathan Shewchuk）の著者が公開しているorient3d（）の実装があります。私自身のプログラミングライブラリであるGeogramの実装もあります[3]。

2の場合は、より厄介です。記号的な摂動を実装するのが最良の方法です[4]。つまり、ポイントが時間によってパラメータ化された軌道に沿って移動していることを考慮し、時間がゼロになるときの位置の制限をとることによって、orient3d（）がゼロを返す構成を明確にすることです（別の言い方をすれば、位置が答えを与えない場合は、時刻t = 0の「速度ベクトル」を見てください）。オリジナルの参考文献[4]は、 "ポリゴンの点"テスト（問題の2D版）のorient2d（）の記号的な混乱を示しています。

注：怠惰で、象徴的な摂動を実装したくない場合は、orient3d（）テストのいずれかがゼロを返すたびにランダムな方向を選ぶことができます（永久には検索されないという保証はありません実際には起こりそうもない）。とにかく、プロトタイピングのためだけにそれを使用し、最後に象徴的な摂動を実装することをお勧めします。

[1] https://people.eecs.berkeley.edu/~jrs/papers/robustr.pdf

[2] https://www.cs.cmu.edu/~quake/robust.html

[3]

[4] http://dl.acm.org/citation.cfm?id=77639