ある点がモデルに内包されるかどうかの判別

プログラミングカテゴリに投稿しようか迷ういましたがこちらに投稿させていただきます。

やりたいのは、3D空間で一つのベクトルによって表現されるある点が、三角形のメッシュの集合としてあらわされるある閉じたモデル(要は一般的な3Dモデルデータのことですが)の内部にあるか外部にあるかを判別するアルゴリズムがしりたいです。 その情報が載っているサイトでもいいです 英語でも構いません 一応ここでいう内部とは各面の法線ベクトルの反対方向に存在する閉じた空間のことです。

-ここから蛇足-
Blenderなどの3Dモデリングツールではおなじみのboolean演算ですが、なんとなく一から作ってみようと思っていろいろ調べてみたんですが、三角形メッシュ vs 三角形メッシュ の衝突判定と交線を求めるアルゴリズムは調べてすぐ出てきたんですが、メッシュのモデル内包判定とかVertex のモデル内包判定とか調べても出たなかったので・・・ なのでぶっちゃけbooleanのアルゴリズムについて詳しく書いてあるページがあればそういう情報も大歓迎です

No.4 回答者： berokanda 回答日時： 2013/12/17 03:35

プログラミングのことは全くわかりませんが、

以下のようにしたらどうでしょう？

メッシュが有限個しかなくて全体で向き付け
可能な閉曲面になっていて、内部が空集合で
ないとします。

点Oを1つ固定します。

十分大きな正数Rをとって、すべてのメッシュが
中心O半径Rの球Bの内部にすっぽり入るように
します。

判定したい点Aを1つ固定します。

A自身がいずれかのメッシュを構成する三角形
に含まれたらそこで判定終了なのでどれにも
含まれないとしてよいです。

単位ベクトルu（uの長さが1）を1つ固定して、
U={A+tu|t≧0}を考えます。
（Aを始点とする半直線）

メッシュを構成する三角形のうち、Uと共有点を
もつもの全体Xを考えます。

A+tuが共有点を与えるとき、0<t<2Rなるtだけ
考えればよいです。

Xに属する三角形のうち、Uとの共有点がその
三角形の頂点または辺の上にある場合は
「uを少し動かし」て、Xに属する三角形のうち
Uとの共有点があるものはすべてその三角形
の内部にもち、頂点や辺では決して共有点を
もたないようにしておきます。

このときのXの個数を数えて、偶数ならAは外側、
奇数ならAは内側と判定できます。

なぜそうかというと、Uの上を点が動いていくと
して、1つのメッシュを構成する三角形の内部
を突き抜けると、それは外部から内部へ突き
抜けるか内部から外部へ突き抜けるかどちら
か一方だからです。球Bの外はもちろん外部
ですがAから出発してUに沿って進み、偶数回
突き抜けて球Bの外部に到達すればAは外部
だったということになりますから。

上述の説明で共有点の有無の判定と「uを少し
動かし」の部分は、テクニックが必要な気がし
ます。それと、球より直方体とかのほうが扱い
やすいかも。

この回答へのお礼

回答ありがとうございました！ なるほど・・・こんなに単純に実現できるとは思いませんでした・・・ この方法はペイントツールなんかの塗りつぶしなんかにも使われてますねそういえば 盲点でした

お礼日時：2013/12/21 16:30

No.3 回答者： ask-it-aurora 回答日時： 2013/12/16 21:53

<回答No.2

すみません．ちょっと考えればこの方法は元の形が凸の時しかうまくいきませんね．勘違いでした，無視してください．
## 正四面体を考えながら読んでたので，アホな勘違いをしました ^^;

No.2 回答者： ask-it-aurora 回答日時： 2013/12/16 21:47

ここは数学カテゴリですし，実際のモデリングツールがどのようにデータを扱うのかわからないので，できるだけ抽象的に問題とその解答を書きます．加えて計算量がどれくらいになるのかもよくわからないので無視します．

[概略] 3次元実ベクトル空間V上の3点 a, b, c ∈ V が―つまり三角形の頂点たちが―与えられたとき，それを含む最小の（アフィン）平面 π = π(a, b, c) が決まる．さらに各（アフィン）平面 π に対して半空間ーつまり内側― H(π) が決まる．そして点 x がモデルに内包されるとは三角形から決まる半空間たち{ H_i(π_i) ; 1 ≦ i ≦ r }の共通部分に含まれることである．

[三角形の与える（アフィン）平面] ここから実際に定式化していきます．アフィン幾何学のコトバを使うのが自然だと思うので，それらを説明しながら定式化します．（といっても別に難しいことをするわけではありません．今はベクトルと違って始点と終点をもつ有向線分を扱わなければならないだけで，それを可能にするのがアフィン幾何学です．）
3点 a, b, c ∈ Vが与えられたとき，それらを含む最小の（アフィン）平面 π は平面上の点 p ∈ A と n ∈ V を用いいて次のように書けます．ただし B( ・, ・)はVの標準内積．
π = π(p, n) = { p + v ∈ A ; v ∈ V, B(n, v) = 0 }
## 実装するときに，もし頂点 a, b, c が与えられているのなら
p = a, n = (b - a)×(c - a)
とすればよいでしょう．

[三角形の内側] （アフィン）平面 π = π(p, n) が与えられたとき，その内側―つまり半空間―は次のように書けます．
H = H(π) = { p + v ∈ A ; v ∈ V, B(n, v) < 0 }

[モデルの内側] 以上の準備のもとに本題に取り組みます．モデルを構成する各三角形に対して半空間 H_i ( 1 ≦ i ≦ r ) が定まります．点 x ∈ A がモデルの内側にいるとは
x ∈ ∩H_i
が成り立つことです．

アルゴリズムというには計算工夫のまったくない方法ですが，これで一応，計算機で実装することはできるのではないでしょうか．

この回答へのお礼

回答ありがとうございました！ ちょっと難しくて分りませんでしたが…

お礼日時：2013/12/21 16:37

No.1 回答者： ddtddtddt 回答日時： 2013/12/16 21:46

　3D領域の表面が、三角形メッシュのSurfaceで構成されるという事でいいですか？。

　あなたの応用に役立つかどうかわかりませんが、また面倒臭いので自分ではコーディングした事はないですが、立体角を使用する方法はどうですか？。参考URLを揚げます。

　　http://hooktail.sub.jp/vectoranalysis/GaussSolid …

　三角形Surfaceの頂点座標を完全に把握できる場合には、上記方法はプログラミングと非常に相性が良いはずです。まぁ～難しそうな事は書いてますが、2Dで言えば次のような事です。

　(1)2D領域内部の点から領域境界を全て見渡そうとし、境界上のある点から出発して同じ点に戻ったら、360°首を回す破目になった（← 死んじゃいそう(^^)）。

　(2)2D領域外部の点から領域境界を全て見渡そうとし、境界上のある点から出発して同じ点に戻ったら、首は同じ位置だった（← 右見て、左見て、正面向いたら回転角0°(^^)）。

この回答へのお礼

回答ありがとうございました！ なるほど・・・内部にある場合と外部にある場合で首を回転させる角度が違うわけですね・・・ 参考になりました 試してみます！

お礼日時：2013/12/21 16:28