資料室 ページ指定表示
資料室 ページ指定表示
 ■Report Liblary..._____________
| HOME | | 最新3ページ | | 最新100リスト | | 10回毎一覧 | | ANDOR  | | 辞書 |

Close

Only
000033.ブーリアン計算の覚え書き 
  (2003年02月18日(火) 21:00)

Open
●ブーリアン計算の覚え書き
ブーリアンプラグインを作り出して、教えてもらったこと、学んだことなど、
忘れないうちに資料にしておきます。
2003/07/15現在最新版plugin>(boolean.lzh●三次元空間における、面と線の交点の求め方
公式を教えてくれたkaoru氏、kao氏には感謝。
La(x,y,z)からLb(x,y,z)への直線
P(x,y,z)を含む、法線N(x,y,z)の無限平面
交点S(x,y,z)

※上図で無限平面は、一部の矩形だけ描く
左記において、平面と線の交点S(x,y,z)は以下のように導き出す。

面について、
 S・N = d
 P・N = d
 ∴S・N = P・N

線について、
 S = t(Lb−La)+La   (式1)

交点Sは、
 (t(Lb−La)+La)・N = P・N
 t(Lb−La)・N+La・N = P・N
 t(Lb−La)・N = P・N−La・N
 t = (P−La)・N/(Lb−La)・N
 tについて求まるので、式1に代入する。
●交点による面の分割手順(Type.0) (boolean0.lzh) 「Metasequoiaプラグイン「ブーリアン」β版」を見て頂ければいろいろ書いてあります。 交点の求め方に無駄があるのはともかくとしても、全ての線で、全ての面を交差していないかを検索し、 交差していたら直ちに面を分割して検索しなおす、実に単純な方法のため、 分割線が多く、面が増え、精度も低く、処理速度も低速でした。 ●交点による面の分割手順(Type.1) (boolean1.lzh) Type.1から、まず、交点の求め方を変更。 そしてなるべく無駄な面が出来ないよう、以下の手順で面を分割していきます。 精度、速度が向上しましたが、それでもまだ速度はかなり遅いと言えます。



左図のように、面に面が刺さるときの処理は以下のようになる。

01.線ABに何か交わってないか検索→無い
02.線BCで検索→面DEFと交わっている
03.線BCと面DEFの交点をPとする
04.もう1点で交わっているはずなので、さらに検索
05.線CAで検索→面DEFと交わっている
06.面ABCの中から検索されたので、面ABCは面DEFに刺さっていると判断し、以下の処理
07.線CAと面DEFの交点をQとする
08.面DEFを点Pで分割→面PDE、面PEF、面PFDを生成
09.面DEFを削除
10.点Qが面PDE、面PEF、面PFDのどこにあるか検索→面PFD
11.面PFDを点Qで分割→面QPF、面QFD、面QDPを生成
12.面PFDを削除
13.点P、点Qと、面DEFと交差する線の共通点Cで、面PQCを生成
14.点P、点Qと、最初に検索された線BCから、面DEFと交差する線の共通でない点Bで、面PQBを生成
15.点Qと、面DEFと交差しない線ABで、面QABを生成
16.面ABCを削除



左図のように、面と面交差するときの処理は以下のようになる。

01.線ABに何か交わってないか検索→無い
02.線BCで検索→無い
03.線CAで検索→面DEFと交わっている
04.線CAと面DEFの交点をPとする
05.もう1点で交わっているはずなので、さらに検索
06.面ABC3つの線で検索完了→面ABCには無い
07.線DEで検索→無い
08.線EFで検索→面ABCと交わっている
09.面DEFの中から検索されたので、面ABCは面DEFと交差していると判断し、以下の処理
10.線EFと面ABCの交点をQとする
11.面DEFを線PQで分割
12.面ABCとの交線EFの各点と線PQで、面PQE、面PQFを生成
13.点Qと、残りの点Dと、交線EFの各点で、面QDE、面QDFを生成
14.面DEFを削除
15.面ABCを線PQで分割
16.面DEFとの交線CAの各点と線PQで、面PQC、面PQAを生成
17.点Pと、残りの点Bと、交線CAの各点で、面PBC、面PBAを生成
18.面ABCを削除
●交点による面の分割手順(Type.2) (boolean2.lzh) ※2003/05/11 追加 交点計算の処理だけは変わらないが、それ以外の計算を今までとは大幅に変更。 ブーリアン(+)では以下の処理を行なっている。  01.カレントとその次のオブジェクトのコピーを取り、カレントをコピーしたオブジェクトに合わせる  02.三角分割(ABCDで構成された面をABC、CDAに分解)  03.各面の交点を算出(まだ分割しない)  04.各面を一気に交点で分割  05.分割構成適正化  06.オブジェクトをマージして近い点を結合  07.形を維持して頂点を最適化 ●01.カレントとその次のオブジェクトのコピーを取り、カレントをコピーしたオブジェクトに合わせる 説明する必要は無いだろう。単純にコピーを取るだけ。これが処理結果となる。 ●02.三角分割(ABCDで構成された面をABC、CDAに分解) 一応程度説明しておくと、4頂点の面だと交点が特定出来ないため3頂点分割している。 以下の図を参考にして欲しい。 図1は普通の4頂点の面。4頂点が同一面にあるなら問題無いのだが、図2ではハンドルの付いた頂点だけY軸にずれている。 こういう面の場合交点は算出できない。図3、図4の分割パターンが考えられるからだ。 ●03.各面の交点を算出(まだ分割しない) ここの処理では各面毎に交点だけを計算してメモリに蓄えている。 面と面が交差するとき、必ず2点の交点が算出される。 交点を求めた順番(単にインデックス)も記憶しておく。(※05で重要) 今まではその場で分割して、結果として余計な計算が増えていたため遅かった。 ただし今回は多面のオブジェクトではかなりのメモリを消費する。 ●04.各面を一気に交点で分割 03で算出した交点で各面を分解する。 後から計算することにより余計な頂点は増えない。 ●05.分割構成適正化 04で分割したままだと、分割線が正しく切れないので補正する。
三角形ABCがあり、それに三角推が刺さってその交点が三角形DEFだとする。
これをDからFまで順番通りに分割すると、下のようになる。
順番通り分割した状態。
最初にABCをDで分割するためABD、BCD、CADが生成される。
次にEで分割。DBE、BCE、CDEが生成され、
最後にFで分割。ADF、DCF、CAFが生成される。
EF間とDC間で分割線がおかしな方向を向いている。
このままマージすると正しい図形にはならない。
分割線方向を正さなければならない。
理想形は左図のようになるが、見た目のように簡単には行かない。
普通、面を分割するときは、その線によって左右にわかれる面の比率が
50%:50%に近くなるように分割する。(流れが関わる時はこの限りではないが)
線が最短になるように分割する方法もあるようだが、いづれもNG。成り立たない。
03で交点を計算したとき、計算した順番も記憶してある。
1回の計算で交点は2点求まり、この2点を共有する面が存在しなければならない。
今回はEとFが同じインデックスを持っているのに、それらを使う面が存在しない。

そこで、点EF間に分割線が有るかどうかチェックし、その線を使う面を全て削除する。
このとき、削除した面の辺(エッジ)を記憶しておく。
更に各頂点の角度も記憶しておく。(※後の計算で重要)
まずDECが削除され、エッジDE、EC、CDが記憶される。
EF間にあるDCは計算対象外として記憶される。
DCFについても同じ処理を行い、エッジDE、EC、CF、FDが摘出され、
CDが対象外となり、問題のEFがエッジとして追加される。
まずEFと、EかFを使うエッジとで面を構成すると、EFDが生成され、
これに使われたエッジEF、FE、EDは使用済みとされる。
残るエッジで同様処理を行なうと、ECとCFでECFが生成される。
エッジが無くなるまでこの処理を続けて分割構成が適正化される。
さて、上記の通りで概ね分割線方向が適正化されるが、これだけではうまく出来ない場合がある。 以下のように、今度は四角DEFGで分割する。 ここではDEFGと記したが、点の構成なんて無限にあるし、計算の順番も保証されるものではないので、 以下のように分割されてしまうこともある。 DG間の分割線が正しくないので、先に書いた方法で、邪魔になる線を含んだ面を削除すると、 ADE、AEF、AFGが削除され、エッジAD、DE、ED、DG、GAとDGが摘出される。 そこで、計算される順番は保証される物ではないということで、以下の問題が出てくる。 ・問題点1 エッジDG、DEで面DEGを生成すると、点Fが中に入ってしまい、おかしな面になる。 DEGを構成するには、面削除時に計算された「各点の角度」の容量が、点E、Gに置いてオーバーしている。 この時点でDEGはありえない。 ・問題点2 エッジEF、FGで面を構成することになった場合、EFGになるが、見ての通りあり得ない。 しかも「各点の角度」の容量は超えていない。 上記の事から、面を構成する時には以下の例外処理も考慮する必要がある。 ・関係する点が重なっていないかチェックする。>問題点1を回避 ・共有する点の角度が180度をこえている場合は後回しにする。(っていうか処理しない)>問題点2回避 以上で下図のような正しい面が構成される。 ●06.オブジェクトをマージして近い点を結合 単純にマージ(合成)して、接近する頂点をくっつける処理をしている。 距離は「0.01」。 ●07.形を維持して頂点を最適化 Metasequoiaプラグイン「ブーリアン」β版の「5.形を維持して頂点を最適化」で説明している通り。 今後は、可能ならば三角形を四角形にする処理も含めたい。
ブーリアン(−)も(+)と似たような処理を行なっている。 違う部分のみ太文字で表示すると、02、07、08の処理が追加されている。  01.カレントとその次のオブジェクトのコピーを取り、カレントをコピーしたオブジェクトに合わせる  02.カレントの次のオブジェクトの面を全部反転する  03.三角分割(ABCDで構成された面をABC、CDAに分解)  04.各面の交点を算出(まだ分割しない)  05.各面を一気に交点で分割  06.分割構成適正化  07.カレントの次のオブジェクトの中にある面を削除する  08.裏を向いた不要な面を削除する  09.オブジェクトをマージして近い点を結合  10.形を維持して頂点を最適化 ●02.カレントの次のオブジェクトの面を全部反転する カレントのオブジェクトはその次のオブジェクトで削られ、その断面は削ったオブジェクトのマテリアルになる。 断面は表裏が逆になるので、予め反転しておく。 ●07.カレントの次のオブジェクトの中にある面を削除する 具体的に削り取る処理を行なう。 少々説明しにくいが、以下の図は青い箱から半透明の緑の箱を削るイメージである。 緑の箱は面が反転しているが、閉じたオブジェクトとして、その中に含まれる青い部分を削除している。 判断の方法としては、青面全てで法線方向に最初にぶつかる面が緑面かどうか、更に法線方向差が90度未満なら それは不要な面と判断し、削除している。 ●08.裏を向いた不要な面を削除する 全ての緑面に対して、法線と逆方向に青又は緑の面が存在するかどうか。 存在しなければそれは不要な面と判断し、削除している。
この他に以下のようなプラグインが含まれていたが、05/23、処理を一元化出来たため削除しました。
ブーリアン(交点分割)カレントのオブジェクトとその次のオブジェクトの交点でそれぞれを分割する
形を維持して最適化Metasequoiaプラグイン「ブーリアン」β版の「5.形を維持して頂点を最適化」の通り
ブーリアン(中抜き)カレントオブジェクトのが閉じたオブジェクトだとして、内部にある不要な面を削除する

適度に面倒な図形で処理してみました。
↓処理前.面倒臭そうな図形を処理してみます↓ブーリアン(+)処理後
↓ブーリアン(+)処理後、緑オブジェの後を削除して中を覗いた↓ブーリアン(−)処理後
関連リンク: 資料室 35ページ:デローニー三角分割 3D空間の表示、表現、演算方法について 2003/07/15現在最新版plugin>(boolean.lzh

| HOME | | 最新3ページ | | 最新100リスト | | 10回毎一覧 |
■0x112 ■0x227 ■0x55F ■0xDDF ■0xF36 ■0xF8B ■0xEBC ■0x114 ■0x33F ■0x77F ■0xAAF ■0xEEF
____________Report Library Ver2.00β 2003/08/27_bomber@xps.jp_http://bomber.xps.jp/_