画家のアルゴリズム

画家のアルゴリズム︵がかのアルゴリズム︶またはペインタアルゴリズム︵英: painter's algorithm︶は、3次元コンピュータグラフィックスにおける隠面消去の最も単純な手法である。Zソート法︵英: Z-sorting︶、塗り重ね法、priority fill とも。3次元のシーンを2次元平面に投影するとき、どのポリゴンが見え、どの面が見えないのかを決定する必要がある。

﹁画家のアルゴリズム﹂という名称は、画家が絵を描くとき遠景から順に描いていき、近いものを描く際に以前に描いた遠景の一部を塗りつぶすことに由来する。画家のアルゴリズムでは全ポリゴンを視点からの距離でソートし、遠い方から順に描いていく。視点から見えない部分は近景によって塗りつぶされるので隠面処理がなされるが、見えない遠景の部分まで描くというコストがかかる。

遠くの山を最初に描き、その前の草地を次に描き、最後に最も近い木々を描く。

このように互いに循環的に重なり合った多角形は、このアルゴリズムでは描けない。

このアルゴリズムは、失敗する場合もある。例えば、ポリゴン同士が循環的に重なっている場合や、ポリゴンに穴がある場合である。右図のように循環的に重なっている場合、これらのポリゴンの上下︵遠近︶関係を決定することができない。この場合、問題のポリゴンを分割してソート可能にする必要がある。1972年、そのようなポリゴンの分割方法としてニューウェルのアルゴリズムが登場した。他にも計算幾何学の分野で様々な手法が提案されている。

穴のあるポリゴンの場合、別のポリゴンがその穴を貫通している状態が問題となる。これも循環的な重なりと同様、問題のポリゴンを分割することで解決できる。

基本的実装では、画家のアルゴリズムの効率は良くない。最終的に全く見えないポリゴンまでレンダリングしてしまうためである。したがって非常に複雑なシーンを描く場合、画家のアルゴリズムはあまりにも高いハードウェア性能を要求する。

画家のアルゴリズムの逆もある。これは、視点から見て近いオブジェクトを先に描画する方法である。その際に既に描画が行われた部分は後からは決して塗りつぶさない。これは、遠景の部分を描く際に描かない部分の色の計算︵光源を考慮したり、テクスチャを張ったり︶が不要となるため、コンピュータにとっては効率が良い。しかし、通常の画家のアルゴリズムの問題は逆の場合でもそのまま当てはまる。

このような問題があるため、Zバッファ技法が開発された。これは、ピクセル単位で重なりの判断を行うようなもので、奥行きを考慮した描画順序を決定する必要がない。そのようなシステムでも、画家のアルゴリズムのバリエーションを利用することがある。Zバッファは一般にハードウェア内の固定精度の奥行きバッファレジスタを使用するが、精度が有限であるために丸め誤差によって重なりの判断を誤ることがある。これはポリゴン間の隙間や重なりとなって現れる。これを防ぐため、グラフィックスエンジンの中には画家のアルゴリズムを使ってそのようなポリゴンのエッジ部分の描画を行うものもある。したがって一部のピクセルは2度描画することになるが、画像全体のごく一部であるため、性能への影響は無視できる。

外部リンク

• 陰面処理、陰線処理について 愛媛大学鵜飼研究室
• 画家のアルゴリズムによる隠面消去を用いた全方向視差計算機合成ホログラム 大島勇樹（他）、関西大学工学部、2007年