データ構造内のB-Repsをツリーに変換する

1B-repストリーム

いくつかの標準的なポリゴン形式で外部的に定義されたB-repをインポートするプロデューサープロセスを設定することが明確に述べられています。ウェーブフロントまたはjava3Dobjファイルのいずれかを、ジオメトリックパイプラインの入力ストリームに入れます。ポリゴンと法線によって提供される境界表現は、コヒーレントに方向付けられている必要があります。非平面ポリゴンやその他の幾何学的不正確さに対処するための入力ファイルのフィルタリングは、主にコンピュータグラフィックスで実装される一般的にアーカイブされた幾何学的モデルに必要な場合があります。コヒーレントに方向付けられた三角形の出力ストリームは、次に説明するアルゴリズムの手順によって、ツインプログレッシブBSP（Binary Search Partitioning）ツリーに変換されます。

2B-repからBSPアルゴリズムの概要

私たちの方法の基本的な手順は、各三角形の事前に計算された慣性の収縮による三角形サブセットの慣性の計算、および三角形サブセットの慣性の固有分解によるそれらの形状を最適かつ再帰的に制限することです。

d次元の場合、オイラー行列の固有ベクトルごとに2つの極値接線超平面を実装して形状の閉じ込めが得られます。対応する2Dハイパースペースの交差により、現在のセルに含まれる境界サブセットの最適な（ハイパー）平行六面体が作成されます。 3Dimensionには、6=2×3のそのような平面があります。

初期化

• 各入力三角形のアフィンに拡張されたオイラーテンソルが最初に計算されます（線形時間で）。
• 入力三角形のセット全体がBSPルートに結合されます。
• E3スペース全体（つまり凸型）がルートに結合されます。
• ルートラベルはFUZZYに設定されています。

再帰的なケース

• 現在のFUZZYセルは、現在の三角形サブセットのオイラーテンソルの行列表現の固有ベクトルに垂直な最大6つの直交超平面で分割されます。
• このような平面は、現在の三角形サブセットの頂点vで評価された線形関数w =a•vの最小値と最大値を介して計算されます。ここで、aは現在の固有ベクトルとして示されます。
• 各固有ベクトルの場合、最大3つの凸状セルが、{OUT、FUZZY、IN}または{OUT、FUZZY、OUT}のいずれかである2つのmax-min平行超平面によって生成されます。
• 各FUZZYセルは、最大固有ベクトルに関連付けられた主超平面によってさらに分割されます。
• 三角形の小さなサブセットは、頂点の包含テストを介して、分割された各セルに結合されます。
• 分割平面を横切る三角形が分割され、（サブ）三角形がノードサブツリーに結合されます。

基本的なケース

再帰的な慣性ベースの除算は、現在のセルが少数の境界三角形のみで構成されている場合に停止します。最終的な細胞分裂は、境界三角形の平面を実装して実行されます。