4面体の内部か外部か
3D Model を扱っていると、指定した点が物体の内部にあるか外部にあるかを判断したくなることがあります。この場合、どのようなロジックが考えられるでしょうか。
物体の最小単位として4面体を対象とし、下図の点が内部か外部かを判断するロジックについて考えてみます。
実はロジックとしてはいたってシンプルで、指定した点と4面体の頂点のうちの3点を使って4面体を4つ作成します。
この4つの4面体の体積をそれぞれ求め、その合計値が元の4面体の体積と同じになれば内部、異なっていれば外部になるわけです。
言われてみれば「なるほど！」なんですが、なかなか自分では思いつかないというケースも多いと思います。結局のところ、3D Model を扱う際に要求されるセンスは「いかにシンプルなロジックを思いつくか」ではないかという気がしています。
というわけでロジックとしては以上なんですが、ここで終わったら呆気ないのでプログラムを作成してみました。まずは4面体の体積を求める計算式が必要ですが、これはサラスの公式という便利なものがあります。
空間上の4点 $ O(0,0,0), A(x_1,y_1,z_1), B(x_2,y_2,z_2), C(x_3,y_3,z_3) $ に対して4面体 $ OABC $ の体積 $ V $ は次式になります。
$$ V = \frac{1}{6} |y_1\,z_2\,x_3+z_1\,x_2\,y_3+x_1\,y_2\,z_3−z_1\,y_2\,x_3−x_1\,z_2\,y_3−y_1\,x_2\,z_3| $$
サラスの公式を使って4面体の体積を求めるサブルーチンを VB.Net で作成してみました。（C# で使いたい人はコンバートしてください）
Public Shared Sub Cal_TetrahedronVolume(ByVal XP1 As Single, ByVal YP1 As Single, ByVal ZP1 As Single,
ByVal XP2 As Single, ByVal YP2 As Single, ByVal ZP2 As Single,
ByVal XP3 As Single, ByVal YP3 As Single, ByVal ZP3 As Single,
ByVal XP4 As Single, ByVal YP4 As Single, ByVal ZP4 As Single,
ByRef Tetrahedron_Volume As Single)
'----------------------------------------------------------------
' 空間上の4点の座標値から、4面体の体積を求める（サラスの公式）
'----------------------------------------------------------------
' XP1,YP1,ZP1 ～ XP4,YP4,ZP4 : 各頂点の座標
'----------------------------------------------------------------
Dim XP10 As Single, YP10 As Single, ZP10 As Single
Dim XP20 As Single, YP20 As Single, ZP20 As Single
Dim XP30 As Single, YP30 As Single, ZP30 As Single
Dim Sarrus_Formula(5) As Single
XP10 = XP2 - XP1 : YP10 = YP2 - YP1 : ZP10 = ZP2 - ZP1
XP20 = XP3 - XP1 : YP20 = YP3 - YP1 : ZP20 = ZP3 - ZP1
XP30 = XP4 - XP1 : YP30 = YP4 - YP1 : ZP30 = ZP4 - ZP1
Sarrus_Formula(0) = YP10 * ZP20 * XP30
Sarrus_Formula(1) = ZP10 * XP20 * YP30
Sarrus_Formula(2) = XP10 * YP20 * ZP30
Sarrus_Formula(3) = ZP10 * YP20 * XP30
Sarrus_Formula(4) = XP10 * ZP20 * YP30
Sarrus_Formula(5) = YP10 * XP20 * ZP30
Tetrahedron_Volume = (Sarrus_Formula(0) + Sarrus_Formula(1) + Sarrus_Formula(2) -
Sarrus_Formula(3) - Sarrus_Formula(4) - Sarrus_Formula(5)) / 6
Tetrahedron_Volume = Math.Abs(Tetrahedron_Volume)
End Sub
指定した点が4面体の内部か外部か判断するサブルーチン。
Public Shared Sub Tetrahedron_InOutJudge(ByVal XP1 As Single, ByVal YP1 As Single, ByVal ZP1 As Single,
ByVal XP2 As Single, ByVal YP2 As Single, ByVal ZP2 As Single,
ByVal XP3 As Single, ByVal YP3 As Single, ByVal ZP3 As Single,
ByVal XP4 As Single, ByVal YP4 As Single, ByVal ZP4 As Single,
ByVal XP0 As Single, ByVal YP0 As Single, ByVal ZP0 As Single,
ByRef Judge_Result As Integer)
'---------------------------------------------------------------------------
' 指定した点が4面体の内部に存在するかどうか判定する
'
' Judge_Result=1 : 4面体の内側
' Judge_Result=0 : 4面体の外側
'
' 4面体を4つ作成し、各体積の合計が全体の体積に等しいときに内部と判断する
'---------------------------------------------------------------------------
' XP1,YP1,ZP1 ～ XP4,YP4,ZP4 : 各頂点の座標
' XP0,YP0,ZP0 : 判定したい点の座標
'---------------------------------------------------------------------------
Dim EachVolume(3) As Single, Tetrahedron_Volume(1) As Single
'全体の体積
Call Cal_TetrahedronVolume(XP1, YP1, ZP1, XP2, YP2, ZP2, XP3, YP3, ZP3,
XP4, YP4, ZP4, Tetrahedron_Volume(0))
If Tetrahedron_Volume(0) = 0 Then
Judge_Result = 0
Exit Sub
End If
'各体積
Call Cal_TetrahedronVolume(XP1, YP1, ZP1, XP2, YP2, ZP2, XP3, YP3, ZP3,
XP0, YP0, ZP0, EachVolume(0))
Call Cal_TetrahedronVolume(XP1, YP1, ZP1, XP2, YP2, ZP2, XP4, YP4, ZP4,
XP0, YP0, ZP0, EachVolume(1))
Call Cal_TetrahedronVolume(XP1, YP1, ZP1, XP3, YP3, ZP3, XP4, YP4, ZP4,
XP0, YP0, ZP0, EachVolume(2))
Call Cal_TetrahedronVolume(XP2, YP2, ZP2, XP3, YP3, ZP3, XP4, YP4, ZP4,
XP0, YP0, ZP0, EachVolume(3))
Tetrahedron_Volume(1) = EachVolume(0) + EachVolume(1) + EachVolume(2) + EachVolume(3)
'差が 0.01% 以内のときに内部と判断する
If (Tetrahedron_Volume(1) - Tetrahedron_Volume(0)) / Tetrahedron_Volume(0) < 0.0001 Then
Judge_Result = 1
Else
Judge_Result = 0
End If
End Sub
格子分割した3次元空間に物体を配置し、物体内部の格子点を計算領域から除外して物体周りの流れ計算を行う場合などに使える手法になります。
（注）これらのコードはあくまでサンプルとして作成したものなので、これを使った結果損害が出たとしても当社は責任を負いません。使用はあくまで自己責任で。
