Blender.jp - Blender2.4 ブーリアン演算

[wiki]
元記事：[[BlenderDev-BooleanDevelopment - BlenderWiki:http://mediawiki.blender.org/index.php/BlenderDev/BooleanDevelopment]]
----
*ブーリアン演算

**1. デザイン

***1.1 アイデア

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

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

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

***1.2 方法論

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

[wiki]

****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を手に入れることです。この段階で、可能なら三角形を結合します。結合の結果は三角形か四角形になります。
[/wiki]

[wiki]

**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_ : 四角形を可能に。

***従属物

-_intern/bsp_ : Mesh関数、export関数、主要なエントリー・ポイント。コードがbooleanops.cと直接的に接続すれば、この従属物はスキップできます。
-_intern/csg_ : 補間関数。UV座標の計算に使います。

**3. インタラクション

ブーリアン演算の内部実装しか変更していないので、ユーザーとシステムのインタラクション（相互作用、対話）は従来と同じです。

**4. 課題

テスト（進行中）
booleanops.cとの直接的な接続
入力Meshのnon-manifold（多様体でない） / non-closed（閉じていない）のチェック（現在はクラッシュします）

**5. スクリーンショット
[/wiki]

旧バージョン

2つの立方体のUnion。辺に重なる頂点がある。ソリッドなMeshでない。
新バージョン

2つの立方体のUnion。よく縫い合わされている。
Megabool スクリプト

2つの立方体のUnion。よく縫い合わされている。

ソリッドなMeshでない。　　

2つの球のIntersection。三角形が多すぎる。

2つの球のIntersection。元の四角形を維持している。

2つの球のIntersection。元の四角形を維持している。マテリアルがない。

piramide.blend (union 演算例)

誤った一致判定(coincidences detection)。

正しい一致判定。

誤ったunion演算。

cube_sphere.blend (union 演算例)

三角形が多すぎる。ソリッドなMeshでない。

きれいな結果。

きれいなMeshだが、いくつかの穴がある。

sphere_cube.blend (difference 演算例)

三角形が多すぎる。ソリッドなMeshでない。

正しいMesh。

驚異的な結果。結合の仕方が良い。

[wiki]

**6. サンプルファイル

[[Piramid:http://mediawiki.blender.org/uploads/2/27/Dev-piramide.blend]]: 面上の頂点。
[[Drill:http://mediawiki.blender.org/uploads/5/5e/Dev-drill.blend]]: 異なる構成で穴をあけた立方体。

**7. Megabool スクリプト

すばらしいスクリプト: [[Megabool:http://astro.scu.edu/~ted/oss/blender/boolean/megabool_r12.py]]

-- MarcFreixas - 22 Jul 2005

----
元記事：[[BlenderDev-BooleanDevelopment - BlenderWiki:http://mediawiki.blender.org/index.php/BlenderDev/BooleanDevelopment]]
This page was last modified 17:08, 22 December 2005.
[/wiki]