ブーリアン演算
ブーリアン演算（ブーリアンえんざん）または集合演算（しゅうごうえんざん）とは、3次元コンピュータグラフィックスやCAD等の形状モデリングにおいて、体積を持った形状（3次元の場合）を集合とみなし、複数の形状を和、差、積といった集合演算により組み合わせ、合成された形状を作る演算である。ソリッドモデリングの1手法であるCSG表現においては根幹的な技術となる。サーフェスモデラにおいても形状をソリッドモデルと仮定できる状況であれば使用できる場合がある。
例
[編集]| 和（） | 差（） | 積（） |
|---|---|---|
 |
 |
|
| 他の形状と一体化するように働く。 | 他の形状を削るように働く。 | 他の形状と重なる部分を残すように働く。 |
2次元
[編集]2次元（平面）の多角形に対するブーリアン演算に関する話題。
アルゴリズム
[編集]- Vattiクリッピング法
- Sutherland–Hodgman法 (特殊ケースのアルゴリズム)
- Weiler–Athertonクリッピング法 (特殊ケースのアルゴリズム)
ソフトウェアでの利用
[編集]初期の多角形に対するブーリアン演算は頂点を使うのではなくビットマップをそのまま使用していた。多角形を扱うのにビットマップをそのまま使用するのは欠点がたくさんある。欠点の一つは、多角形を表現する際のピクセル数に比例して必要な計算量・メモリ量が増える。
近年の多角形に対するブーリアン演算は頂点を使った走査アルゴリズム[1]を使用する。凸多角形に対するブーリアン演算は線形時間で計算可能[2]である。
関連項目
[編集]参照
[編集]- ^ T. コルメン、R. リベスト、C. シュタイン、C. ライザーソン『アルゴリズムイントロダクション』（第3版）近代科学社、2013年12月17日（原著2009-7-31）。ISBN 476490408X。
- ^ Katz, Matthew J.; Overmars, Mark H.; Sharir, Micha (1992), “Efficient hidden surface removal for objects with small union size”, Computational Geometry: Theory and Applications 2 (4): 223–234, doi:10.1016/0925-7721(92)90024-M
 | この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |