画家のアルゴリズム
画家のアルゴリズム(がかのアルゴリズム)またはペインタアルゴリズム(英: painter's algorithm)は、3次元コンピュータグラフィックスにおける隠面消去の最も単純な手法である。Zソート法(英: Z-sorting)、塗り重ね法、priority fill とも。3次元のシーンを2次元平面に投影するとき、どのポリゴンが見え、どの面が見えないのかを決定する必要がある。
「画家のアルゴリズム」という名称は、画家が絵を描くとき遠景から順に描いていき、近いものを描く際に以前に描いた遠景の一部を塗りつぶすことに由来する。画家のアルゴリズムでは全ポリゴンを視点からの距離でソートし、遠い方から順に描いていく。視点から見えない部分は近景によって塗りつぶされるので隠面処理がなされるが、見えない遠景の部分まで描くというコストがかかる。
このアルゴリズムは、失敗する場合もある。例えば、ポリゴン同士が循環的に重なっている場合や、ポリゴンに穴がある場合である。右図のように循環的に重なっている場合、これらのポリゴンの上下(遠近)関係を決定することができない。この場合、問題のポリゴンを分割してソート可能にする必要がある。1972年、そのようなポリゴンの分割方法としてニューウェルのアルゴリズム(英語版)が登場した。他にも計算幾何学の分野で様々な手法が提案されている。
穴のあるポリゴンの場合、別のポリゴンがその穴を貫通している状態が問題となる。これも循環的な重なりと同様、問題のポリゴンを分割することで解決できる。