ブーリアン演算のソースを表示

{{Otheruses|形状モデリングのブーリアン演算|[[ブール代数]]の演算|ブール論理}}
[[File:Boolean operations on shapes-en.svg|thumbnail|right|ブーリアン演算]]
'''ブーリアン演算'''（ブーリアンえんざん）または'''集合演算'''（しゅうごうえんざん）とは、[[3次元コンピュータグラフィックス]]や[[CAD]]等の形状モデリングにおいて、体積を持った形状（3次元の場合）を集合とみなし、複数の形状を[[合併 (集合論)|和]]、[[差集合|差]]、[[共通部分 (数学)|積]]といった[[集合の代数学|集合演算]]により組み合わせ、合成された形状を作る演算である。[[ソリッドモデリング]]の1手法である[[Constructive Solid Geometry|CSG表現]]においては根幹的な技術となる。[[サーフェスモデリング|サーフェスモデラ]]においても形状をソリッドモデルと仮定できる状況であれば使用できる場合がある。

== 例 ==
{| class="wikitable"
|+ ブーリアン演算の例（青い球が右[[被演算子|オペランド]]である）
! 和（<math>\cup</math>） !! 差（<math>-\!</math>） !! 積（<math>\cap</math>）
|-
| [[Image:Boolean_union.PNG|200px|和]] || [[Image:Boolean_difference.PNG|200px|差]] || [[Image:Boolean_intersect.PNG|200px|積]]
|-
| 他の形状と一体化するように働く。 || 他の形状を削るように働く。 || 他の形状と重なる部分を残すように働く。
|}

== 2次元 ==
2次元（平面）の[[多角形]]に対するブーリアン演算に関する話題。

=== アルゴリズム ===
* [[:en:Vatti clipping algorithm|Vattiクリッピング法]]
* [[:en:Sutherland–Hodgman algorithm|Sutherland–Hodgman法]] (特殊ケースのアルゴリズム)
* [[:en:Weiler–Atherton clipping algorithm|Weiler–Athertonクリッピング法]] (特殊ケースのアルゴリズム)

=== ソフトウェアでの利用 ===
初期の多角形に対するブーリアン演算は頂点を使うのではなくビットマップをそのまま使用していた。多角形を扱うのにビットマップをそのまま使用するのは欠点がたくさんある。欠点の一つは、多角形を表現する際のピクセル数に比例して必要な計算量・メモリ量が増える。

近年の多角形に対するブーリアン演算は頂点を使った走査アルゴリズム<ref>{{Cite book|和書
|author1 = T. コルメン
|author2 = R. リベスト
|author3 = C. シュタイン
|author4 = C. ライザーソン
|origdate  = 2009-7-31
|date      = 2013-12-17
|edition   = 第3版
|title     = アルゴリズムイントロダクション
|language  = 日本語
|publisher = 近代科学社
|isbn      = 476490408X
}}</ref>を使用する。凸多角形に対するブーリアン演算は線形時間で計算可能<ref>{{citation
 | last1 = Katz | first1 = Matthew J.
 | last2 = Overmars | first2 = Mark H.
 | last3 = Sharir | first3 = Micha
 | doi = 10.1016/0925-7721(92)90024-M
 | issue = 4
 | journal = Computational Geometry: Theory and Applications
 | pages = 223–234
 | title = Efficient hidden surface removal for objects with small union size
 | url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.7171
 | volume = 2
 | year = 1992}}</ref>である。

== 関連項目 ==
* [[Constructive Solid Geometry]]
* [[論理演算]]
* [[ベン図]]

== 参照 ==
{{reflist}}

{{Computer-stub}}

{{DEFAULTSORT:ふりあん}}
[[Category:3DCG]]
[[Category:CAD]]