単体と点の最接近点を求める その2

3次元空間内の単体(線分、三角形、四面体)と原点の最接近点を求めるコードを書きました。
前回は三角形までやりましたが、それの続きです。今回はあっさり終わります。
ヘッダ画像とデモは前回の使い回しです。

>> Run Demo (HTML5+JS)

 

前回までで三角形と原点の最接近点を求める方法が分かりました。
疑似コードを書いておくとこんな感じになります。

これに四面体と原点との最接近点を返す関数を追加します。方法は比較的シンプルで、三角形のときの手法の拡張です。
三角形の場合は次のように考えました:

・各辺の法線ベクトルを求める
・各辺と原点の内外判定を行い、
 ・原点が外側にある辺があれば、辺と原点の最接近点を求める
 ・求めた全ての点で最も原点に近いものを返す
・全ての辺に対して原点が内側にあれば、原点を三角形上に射影した点を返す

四面体では次のように考えます:

・各面(=三角形)の法線ベクトルを求める
・各面と原点の内外判定を行い、
 ・原点が外側にある面があれば、三角形と原点の最接近点を求める
 ・求めた全ての点で最も原点に近いものを返す
・全ての面に対して原点が内側にあれば、原点は四面体内部にあるので、原点を返す

見ての通り、三角形の場合とほぼ同じですが、四面体の場合は、点の配置によっては「表裏がひっくり返る」ことがあるので注意する必要があります。何のこっちゃ?と思うかもしれませんが、下の二つの四面体を見てください。

左の四面体で、外側から見て反時計回りに三角形の頂点を見ていくと、
・1→2→3
・1→3→4
・1→4→2
・2→4→3
の4つがあります。

一方、右の四面体はというと、
・1→3→2
・1→4→3
・1→2→4
・2→3→4
と、全ての面が逆向きになっていることが分かります。この違いを考慮しないと、面に対する原点の内外判定がおかしなことになってしまいます。

ではどうやって四面体が反転しているのを検出するか、というのが問題になりますが、これはベクトルの外積を使うと簡単にできます。三角形 v_1, v_2, v_3 の法線ベクトル (v_2-v_1)\times(v_3-v_1) は、常に「v_1, v_2, v_3 が反時計回りに見える方向に飛び出す」という性質があります。上の図の左の四面体だと4の逆方向、右の四面体だと4の方向です。

つまり、((v_2-v_1)\times(v_3-v_1))\cdot(v_4-v_1) ※1これは3次の行列式と深く関係しています の符号を見れば、四面体が反転しているかどうかが判別できます。左の四面体が正常で、右の四面体が反転したものとすると、

((v_2-v_1)\times(v_3-v_1))\cdot(v_4-v_1)>0 ならばv_1v_2 を入れ替える

という処理を挟めば、反転した四面体も正常に処理できるようになります。

以上に気を付けると、全体の疑似コードは次のようになります。

注釈   [ + ]

1. これは3次の行列式と深く関係しています

Leave a Reply