[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]