![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
プログラミングカテゴリに投稿しようか迷ういましたがこちらに投稿させていただきます。
やりたいのは、3D空間で一つのベクトルによって表現されるある点が、三角形のメッシュの集合としてあらわされるある閉じたモデル(要は一般的な3Dモデルデータのことですが)の内部にあるか外部にあるかを判別するアルゴリズムがしりたいです。 その情報が載っているサイトでもいいです 英語でも構いません 一応ここでいう内部とは各面の法線ベクトルの反対方向に存在する閉じた空間のことです。
-ここから蛇足-
Blenderなどの3Dモデリングツールではおなじみのboolean演算ですが、なんとなく一から作ってみようと思っていろいろ調べてみたんですが、三角形メッシュ vs 三角形メッシュ の衝突判定と交線を求めるアルゴリズムは調べてすぐ出てきたんですが、メッシュのモデル内包判定とかVertex のモデル内包判定とか調べても出たなかったので・・・ なのでぶっちゃけbooleanのアルゴリズムについて詳しく書いてあるページがあればそういう情報も大歓迎です
A 回答 (4件)
- 最新から表示
- 回答順に表示
No.4
- 回答日時:
プログラミングのことは全くわかりませんが、
以下のようにしたらどうでしょう?
メッシュが有限個しかなくて全体で向き付け
可能な閉曲面になっていて、内部が空集合で
ないとします。
点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を少し
動かし」の部分は、テクニックが必要な気がし
ます。それと、球より直方体とかのほうが扱い
やすいかも。
回答ありがとうございました! なるほど・・・こんなに単純に実現できるとは思いませんでした・・・ この方法はペイントツールなんかの塗りつぶしなんかにも使われてますねそういえば 盲点でした
No.3
- 回答日時:
<回答No.2
すみません.ちょっと考えればこの方法は元の形が凸の時しかうまくいきませんね.勘違いでした,無視してください.
## 正四面体を考えながら読んでたので,アホな勘違いをしました ^^;
No.2
- 回答日時:
ここは数学カテゴリですし,実際のモデリングツールがどのようにデータを扱うのかわからないので,できるだけ抽象的に問題とその解答を書きます.加えて計算量がどれくらいになるのかもよくわからないので無視します.
[概略] 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
が成り立つことです.
アルゴリズムというには計算工夫のまったくない方法ですが,これで一応,計算機で実装することはできるのではないでしょうか.
No.1
- 回答日時:
3D領域の表面が、三角形メッシュのSurfaceで構成されるという事でいいですか?。
あなたの応用に役立つかどうかわかりませんが、また面倒臭いので自分ではコーディングした事はないですが、立体角を使用する方法はどうですか?。参考URLを揚げます。
http://hooktail.sub.jp/vectoranalysis/GaussSolid …
三角形Surfaceの頂点座標を完全に把握できる場合には、上記方法はプログラミングと非常に相性が良いはずです。まぁ~難しそうな事は書いてますが、2Dで言えば次のような事です。
(1)2D領域内部の点から領域境界を全て見渡そうとし、境界上のある点から出発して同じ点に戻ったら、360°首を回す破目になった(← 死んじゃいそう(^^))。
(2)2D領域外部の点から領域境界を全て見渡そうとし、境界上のある点から出発して同じ点に戻ったら、首は同じ位置だった(← 右見て、左見て、正面向いたら回転角0°(^^))。
回答ありがとうございました! なるほど・・・内部にある場合と外部にある場合で首を回転させる角度が違うわけですね・・・ 参考になりました 試してみます!
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
高校教科書の問題
-
正八角形で・・・・
-
数学Aについて質問です。 1. 正...
-
Wordで三角柱を作成したいので...
-
合同と=の違い
-
エクセルで文書の改訂記号を作...
-
三角形ABCと三角形DEFの重心は...
-
スマホでこの画像の4G左側にあ...
-
円に外接する三角形
-
中学マッチ棒
-
高校数学・図形 辺の値が二つ...
-
この問題の解説で PQは弦BCの垂...
-
正八角形の全ての頂点を結ぶ直...
-
複素平面上の三角形の相似について
-
三角形折りの卓上札に両面印刷...
-
中2数学です。 角Xの大きさの求...
-
ロバの橋について
-
三角関数で分からない問題があ...
-
中学で習う証明問題の解き方(合...
-
垂心はなぜHで表すのか?
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
数学Aについて質問です。 1. 正...
-
エクセルで文書の改訂記号を作...
-
正八角形で・・・・
-
正八角形の三個の頂点を結んで...
-
Aに直線3本で三角形7個
-
数Iについてです。 「角A<90°は...
-
垂心はなぜHで表すのか?
-
合同と=の違い
-
高校教科書の問題
-
Wordで三角柱を作成したいので...
-
スマホでこの画像の4G左側にあ...
-
三角形折りの卓上札に両面印刷...
-
この世に「絶対」なんてない。 ...
-
四角形の重心の求め方の定義名
-
中学マッチ棒
-
正八角形についてです。 3個の...
-
三角形の内接円が必ず存在する証明
-
ヘロンの公式って、3辺が整数で...
-
図形の性質 「平行な二直線を含...
-
三角形ABCと三角形DEFの重心は...
おすすめ情報