ブーリアン演算

1. デザイン

1.1 アイデア

単純で堅牢にするために、union (OR) と difference (DIFF) は intersection (AND) と否定 (NOT) の組み合わせで実装します。

obA AND* obB = and( obA, obB )
obA OR* obB = not( and( not( obA), not( obB ) ) )
obA DIFF* obB = and( obA, not( obB ) )

否定演算の本質は、法線の反転と、Meshのすべての面の頂点の順番の反転にあります。

1.2 方法論

ブーリアン演算のパイプラインは3段階に分かれています（図1）。入力Meshの形成：入力されたblenderオブジェクトを内部形式のMeshに変換します。このとき、ブーリアン演算の種類を考慮します。ブーリアン交差：2つのMeshに対する intersect (AND) ブーリアン演算の実装です。出力オブジェクトの形成：結果のMeshを最終的なblenderオブジェクトに変換します。

1.2.1 変換モジュール

ブーリアン演算を単純にするため、ここでは三角形面のMeshをモデルとして使います。そのために、blenderオブジェクトを内部形式のMeshに変換するモジュールが存在します。内部形式のMeshは、intersectionを適用するための全情報と演算を持ちます。このモジュールは上記パイプラインの最初と最後の段階で使います（図1）。

1.2.2 ブーリアン演算モジュール

ANDブーリアン演算の結果は三角形の集合になり、この集合を使って、2つのMeshが交差する境界線を判定します。この三角形は元々あった三角形とは異なる可能性があります。この新しい三角形を計算するために、このモジュールは、境界線上にあり交差する1組の三角形を探します。必要な三角形を得るための、この2つの三角形の分割の仕方は、交差 (intersection) によって決まります。

正しい結果を生成するために、このモジュールは2つのソリッドなMeshを受け取る必要があります。

このモジュールは3段階に分かれています。BSPツリーの構築：この段階では、2つのBSPツリーを構築します。1つは、結果の三角形を分類するために使い、もう1つは、交差を生成する三角形を判定するために使います。BSPは面(face)の平面を使って構築します。各Meshは自分のBSPツリーを持ちます。面と面：この段階は、2つのMeshの交差を判定し、両方の三角形に対応するテッセレーションを計算するために、一方のMeshに対してもう一方のMeshのすべての面をテストします。三角形の分類：目的は、Meshを2つの三角形集合、INとOUTに分けることです。三角形が両方の入力Meshに含まれるときはINに分類します。これを判定するために、最初の面が使われたときにBSPを作ります。三角形の後処理：目的は、きれいなMeshを手に入れることです。この段階で、可能なら三角形を結合します。結合の結果は三角形か四角形になります。

2. 実装

新しいファイル

新しい実装には、_boolop_という名前の新ディレクトリが与えられています。今までに追加された新ファイルは以下の通り。

_intern/boolop/extern/BOP_Interface.h_ : モジュール・インタフェイス。
_intern/boolop/intern/BOP_Interface.cpp_
_intern/boolop/intern/BOP_BSPTree.cpp/.h_ : 両方のMeshの面をINかOUTに分類するために使うBSPツリー。
_intern/boolop/intern/BOP_BSPNode.cpp/.h_ : BSP内部ノード。
_intern/boolop/intern/BOP_BBox.cpp/.h_ : バウンディング・ボックス
_intern/boolop/intern/BOP_Mesh.cpp/.h_ : boolopに役立つアクセス機能を備えたMeshデータ。
_intern/boolop/intern/BOP_Face.cpp/.h_ : Meshの面。
_intern/boolop/intern/BOP_Edge.cpp/.h_ : Meshの辺。
_intern/boolop/intern/BOP_Vertex.cpp/.h_ : Meshの頂点。
_intern/boolop/intern/BOP_Face2Face.cpp/.h_ : 中心となるコード。
_intern/boolop/intern/BOP_Merge.cpp/.h_ : 同じ面を親とする面の結合。
_intern/boolop/intern/BOP_Segment.cpp/.h_ : 2つの面の間の衝突領域。
_intern/boolop/intern/BOP_Splitter.cpp/.h_ : 面と辺を分割するための関数。
_intern/boolop/intern/BOP_Triangulator.cpp/.h_ : segmentsを用いて面を三角形化。
_intern/boolop/intern/BOP_Indexs.h_ : 便利なインデックス構造。
_intern/boolop/intern/BOP_Material.cpp/.h_ : 面のマテリアルのコンテナ。
_intern/boolop/intern/BOP_MaterialContainer.cpp/.h_ : Meshのマテリアルのコンテナ。元のMeshを再構築するために使います。
_intern/boolop/intern/BOP_MathUtils.cpp/.h_ : 数学の関数。
_intern/boolop/intern/BOP_Tag.cpp/.h_ : フラグ。値はIN、OUTなど。

修正したファイル

_intern/bsp/intern/CSG_BooleanOps.cpp_ : blenderのカーネルと新しいboolean opsを接続するために使います。実装が終わる頃には、blenderのカーネルと新しいboolean opsの接続は直接的になる予定です。
_intern/bsp/intern/BSP_CSGMesh_CFIterator.h_ : 四角形を可能に。
_source/blender/src/booleanops.c_ : 四角形を可能に。