BSP-Tree の生成方法

BSP-tree の生成方法について詳しく見てみよう． 配布資料 pp.70-73 も参考にしよう．

例として，Fig.1 の図形を対象としよう．

前面図 背面図

Fig.1.　図形の例

まず，親になるポリゴンを決めよう． これはどれでも良いのだが，ここではポリゴン 0 を選ぶことにしよう． そして，この親に対して前方（表側）に位置するポリゴン群を 左の枝に， 後方（裏側）に位置するポリゴン群を 右の枝に割り当てる． このとき，親ポリゴンの延長平面に交差するようなポリゴンは， 例えば，{10，11，12} や {13，14，15} のように， 前方部分と後方部分とに再分割しておく必要がある．

現実的には，できるだけ再分割しなくても済むように， 親の選び方を工夫すべきだ． 例えば，ポリゴン 0 ではなく， 外側のポリゴン 2，8，5，等を先に親にして行けば， ポリゴン 3-4 や 6-7 を再分割せず一体のまま処理を進めることができる．

また，物体の内部にダミーのポリゴンを追加し，それを親に選べば， 分割を回避できる場合もある．

この段階では，BSP-tree は Fig.2 のような状態になっている．

Fig.2.　BSP-tree 生成の第 1 段階

なお， 四角形ポリゴンを 2 個の三角形ポリゴンに分割した場合など， 同一平面内の面同士については，どちらが前方でも後方でも，どちらでもよい．

次に，各ポリゴン群において親を決め， 同様の処理を施そう． 例えば，ポリゴン 1 および 4 を親に選べば， BSP-tree は Fig.3 となる．

特に再分割などの不都合がなければ， 番号のもっとも若いものを選ぶのが自然な方法だと思われる．

Fig.3.　BSP-tree 生成の第 2 段階

さらに，各ポリゴン群に対して同じ処理を繰り返そう． Fig.4 となる．

Fig.4.　BSP-tree 生成の第 3 段階

最終的に，Fig.5 のような木が生成される．

Fig.5.　完成した BSP-tree

なお，親の選び方によって異なる木が生成されることになるが， レンダリング結果は必ず同じ画像になるので心配しなくてよい．

だが，データ入力の作業の手間を考えると， できるだけ単純な形状の木を作っておきたい． ポリゴンへの番号付けと親の選択の作業については， 場当たり的ではなく， 規則的に進めるとよい．
(c) 2015, KY