データ構造内のB-Repをツリーに変換する：プログレッシブBSPツリー構築アルゴリズム

1. B-Repストリームの構築

本手法ではまず、Wavefront OBJやJava3Dのobjファイルといった標準的なポリゴン形式で外部定義されたB-Rep(境界表現)を読み込み、幾何パイプラインの入力ストリームへ供給するプロデューサプロセスを構築します。ポリゴンと法線からなる境界表現は、面同士の向きが一貫している(整合的にオリエンテーションされている)必要があります。

コンピュータグラフィックス用途で作成・蓄積された幾何モデルには、非平面ポリゴンや幾何学的な誤差が含まれることが少なくありません。そのため、入力ファイルに対して非平面ポリゴンの修正などを目的としたフィルタリング処理が必要となる場合があります。こうして整備された、向きの揃った三角形からなる出力ストリームは、後述のアルゴリズム的手順を経て、ツイン・プログレッシブBSP(Binary Space Partitioning:二分空間分割)ツリーへと変換されます。

2. B-RepからBSPツリーへの変換アルゴリズム概要

本手法の基本となるのは、各三角形について事前計算しておいた慣性テンソルを縮約することで三角形部分集合の慣性を求め、その固有分解(固有値分解)を行うことで、形状を再帰的かつ最適な形で包含する境界を導出する手順です。

d次元の場合、オイラー行列のd個の固有ベクトルそれぞれに対して2枚の極値接超平面を設けることで形状の限定が得られます。対応する2d個の超空間の交わりにより、現在のセルに含まれる境界部分集合に対する最良適合の(超)平行六面体が構成されます。3次元の場合は、6=2×3枚の平面がこれに相当します。

初期化

• 入力される各三角形のアフィン拡張オイラーテンソルを最初に計算します(線形時間で処理可能)。
• 入力三角形全体の集合をBSPツリーの根(ルート)に結合します。
• 凸集合であるE³空間全体を根に結合します。
• 根のラベルをFUZZYに設定します。

再帰ケース

• 現在のFUZZYセルを、最大6枚の互いに直交する超平面で分割します。これらの超平面は、現在の三角形部分集合のオイラーテンソルの行列表現における固有ベクトルに垂直な方向を持ちます。
• 各平面の位置は、線形関数 w = a·v を現在の三角形部分集合の頂点 v 上で評価した際の最小値と最大値から決定されます。ここで a は現在着目している固有ベクトルです。
• 各固有ベクトルについて、max-min の2枚の平行超平面によって最大3つの凸セルが生成され、そのラベルは {OUT, FUZZY, IN} または {OUT, FUZZY, OUT} のいずれかになります。
• 残った各FUZZYセルは、最大固有ベクトルに対応する主超平面(principal hyper-plane)によってさらに分割されます。
• 頂点の包含判定(コンテインメントテスト)により、より小さな三角形部分集合を分割後の各セルに割り当てます。
• 分割平面と交差する三角形は分割され、生成された(部分)三角形は対応するノードの部分木に結合されます。

基本ケース(終了条件)

現在のセルが少数の境界三角形のみを含む状態になると、慣性に基づく再帰的分割を停止します。最後に、境界三角形自身の平面を用いて最終的なセル分割を実行し、処理を完了します。