三角形の交線はどうやって計算するのでしょうか？

質問

多面体の重なりについて計算したいのですが，検索すると三角形に分割した後に三角形の重なりを計算すれば良い……と言う記事を複数発見しました．
しかし，どのようにすれば三角形の交わりを求められるのかが見つかりません．
（手元の参考書には，3点を通る平面と直線の交わりなどは書いてあるのですが……）

・三角形同士の交線の計算
・三角形と四角形の交線の計算

の以上2点に関する資料を，何方か御教示願えませんでしょうか．
以上です
宜しくお願いします

回答No.1

chie65536（@chie65535） · ベストアンサー

＞（手元の参考書には，3点を通る平面と直線の交わりなどは書いてあるのですが……）

＞・三角形同士の交線の計算

「三角形ＡＢＣと三角形ａｂｃが交わる」
とは
「三角形ＡＢＣと直線ａｂが交わる
または
三角形ＡＢＣと直線ａｃが交わる
または
三角形ＡＢＣと直線ｂｃが交わる」
と言う事。

考え方を変えれば
「三点ＡＢＣを通る平面と直線ａｂが交わる
または
三点ＡＢＣを通る平面と直線ａｃが交わる
または
三点ＡＢＣを通る平面と直線ｂｃが交わる」
かつ
「三点ａｂｃを通る平面と直線ＡＢが交わる
または
三点ａｂｃを通る平面と直線ＡＣが交わる
または
三点ａｂｃを通る平面と直線ＢＣが交わる」
と言う事。

なので、手元の参考書の「3点を通る平面と直線の交わり」が判定できれば良い。

＞・三角形と四角形の交線の計算

「三角形ＡＢＣと四角形ａｂｃｄが交わる」
とは
「三角形ＡＢＣと、三角形ａｂｃまたは三角形ａｃｄが交わる」
と言う事。

なので「三角形同士の重なり」の計算を２回行うだけ。

簡単に言うと「どんな多角形も、分割すれば三角形の集まり」なので「三角形同士の交線の計算」を行うだけになる。

そして「多面体同士の重なり」は「互いの表面を三角形に分解した時、三角形同士が重なっているかどうか」で判定出来ます。

なお、三角形に分解した時、すべての三角形について、３つの頂点座標を調べ
「Ｘ座標の最大が、もう一方の多面体のＸ座標の最小よりも小さい」
かつ
「Ｙ座標の最大が、もう一方の多面体のＹ座標の最小よりも小さい」
かつ
「Ｚ座標の最大が、もう一方の多面体のＺ座標の最小よりも小さい」
と言う場合は重ならないのが明らかなので、その三角形を除外できます。

除外は、以下のようにします。

２つの多面体について、その多面体がスッポリぴったり入る直方体を作って、その２つの直方体が重なった領域を求めます。

その領域は８つの頂点を持つ直方体で、その頂点座標は「どっちかの多面体の頂点座標の、Ｘ、Ｙ、Ｚ座標の最小値か最大値」で出来ています。

なので、この直方体を求めるには「多面体の各頂点の座標のＸ、Ｙ、Ｚ座標を大小比較するだけ」で求まります。

この時「２つの直方体が重なった領域がない」のなら、多面体は重なっていません。

次に「２つの直方体が重なった領域の中にない三角形」は、重なりようが無いので、すべて除外します。

どちらの多面体でも、最低１個は三角形が残りますから、あとは前述の方法で「三角形同士の重なり」を計算すれば良いです。