ブーリアン演算(ブーリアンえんざん)または集合演算(しゅうごうえんざん)とは、3次元コンピュータグラフィックスCAD等の形状モデリングにおいて、体積を持った形状(3次元の場合)を集合とみなし、複数の形状をといった集合演算により組み合わせ、合成された形状を作る演算である。ソリッドモデリングの1手法であるCSG表現においては根幹的な技術となる。サーフェスモデラにおいても形状をソリッドモデルと仮定できる状況であれば使用できる場合がある。

ブーリアン演算

編集

ブーリアン演算の例(青い球が右オペランドである)
和(  差(  積( 
     
他の形状と一体化するように働く。 他の形状を削るように働く。 他の形状と重なる部分を残すように働く。

2次元編集

2次元(平面)の多角形に対するブーリアン演算に関する話題。

アルゴリズム編集

ソフトウェアでの利用編集

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

近年の多角形に対するブーリアン演算は頂点を使った走査アルゴリズム[1]を使用する。凸多角形に対するブーリアン演算は線形時間で計算可能[2]である。

関連項目編集

参照編集

  1. ^ T. コルメン、R. リベスト、C. シュタイン、C. ライザーソン『アルゴリズムイントロダクション』近代科学社、2013年12月17日(原著2009年7月31日)、第3版(日本語)。ISBN 476490408X
  2. ^ 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, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.7171