画家のアルゴリズム
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。（2009年6月） |
画家のアルゴリズム（がかのアルゴリズム）またはペインタアルゴリズム（英: painter's algorithm）は、3次元コンピュータグラフィックスにおける隠面消去の最も単純な手法である。Zソート法（英: Z-sorting）、塗り重ね法、priority fill とも。3次元のシーンを2次元平面に投影するとき、どのポリゴンが見え、どの面が見えないのかを決定する必要がある。
「画家のアルゴリズム」という名称は、画家が絵を描くとき遠景から順に描いていき、近いものを描く際に以前に描いた遠景の一部を塗りつぶすことに由来する。画家のアルゴリズムでは全ポリゴンを視点からの距離でソートし、遠い方から順に描いていく。視点から見えない部分は近景によって塗りつぶされるので隠面処理がなされるが、見えない遠景の部分まで描くというコストがかかる。
このアルゴリズムは、失敗する場合もある。例えば、ポリゴン同士が循環的に重なっている場合や、ポリゴンに穴がある場合である。右図のように循環的に重なっている場合、これらのポリゴンの上下（遠近）関係を決定することができない。この場合、問題のポリゴンを分割してソート可能にする必要がある。1972年、そのようなポリゴンの分割方法としてニューウェルのアルゴリズムが登場した。他にも計算幾何学の分野で様々な手法が提案されている。
穴のあるポリゴンの場合、別のポリゴンがその穴を貫通している状態が問題となる。これも循環的な重なりと同様、問題のポリゴンを分割することで解決できる。
基本的実装では、画家のアルゴリズムの効率は良くない。最終的に全く見えないポリゴンまでレンダリングしてしまうためである。したがって非常に複雑なシーンを描く場合、画家のアルゴリズムはあまりにも高いハードウェア性能を要求する。
画家のアルゴリズムの逆もある。これは、視点から見て近いオブジェクトを先に描画する方法である。その際に既に描画が行われた部分は後からは決して塗りつぶさない。これは、遠景の部分を描く際に描かない部分の色の計算（光源を考慮したり、テクスチャを張ったり）が不要となるため、コンピュータにとっては効率が良い。しかし、通常の画家のアルゴリズムの問題は逆の場合でもそのまま当てはまる。
このような問題があるため、Zバッファ技法が開発された。これは、ピクセル単位で重なりの判断を行うようなもので、奥行きを考慮した描画順序を決定する必要がない。そのようなシステムでも、画家のアルゴリズムのバリエーションを利用することがある。Zバッファは一般にハードウェア内の固定精度の奥行きバッファレジスタを使用するが、精度が有限であるために丸め誤差によって重なりの判断を誤ることがある。これはポリゴン間の隙間や重なりとなって現れる。これを防ぐため、グラフィックスエンジンの中には画家のアルゴリズムを使ってそのようなポリゴンのエッジ部分の描画を行うものもある。したがって一部のピクセルは2度描画することになるが、画像全体のごく一部であるため、性能への影響は無視できる。
外部リンク
- 陰面処理、陰線処理について[リンク切れ] 愛媛大学鵜飼研究室
- 画家のアルゴリズムによる隠面消去を用いた全方向視差計算機合成ホログラム 大島勇樹（他）、関西大学工学部、2007年
Zソート法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/30 16:19 UTC 版)
「3次元コンピュータグラフィックス」の記事における「Zソート法」の解説
詳細は「画家のアルゴリズム」および「Zオーダー」を参照 隠面消去方法のひとつ。ポリゴンの座標（大抵は中心点）を基準に、画面の奥（視線からもっとも遠いポリゴン）から、全てのポリゴンを順番に描画する。後述のZバッファ法のような特殊な処理をせず、基本的に多角形を描画すればよいだけなので、実装が簡単であり、消費メモリが少なく非常に処理が高速にできる利点がある。Zバッファ法が普及するまでは古くは3DCG全般で利用され、また、最近[いつ?]まで家庭用ゲーム機におけるリアルタイム3DCGでは一般的に利用されていた。しかし、ポリゴン数が増えた場合は、ポリゴンをソートするコストがかかる、またフィルレートが膨大になるため、Zバッファ法と比較して速度的なメリットがなくなる。 ポリゴンが交差した場合に正しく表示することができないという欠点があるが、この解決策として、ポリゴンが互いに交差しないように静的、あるいは動的に細分化する方法がとられることがある。 Zバッファ法と異なり、半透明ポリゴンの描画に関しては、ポリゴンが交差する場合を除いて、概ね正しく扱うことができる。
※この「Zソート法」の解説は、「3次元コンピュータグラフィックス」の解説の一部です。
「Zソート法」を含む「3次元コンピュータグラフィックス」の記事については、「3次元コンピュータグラフィックス」の概要を参照ください。
- Zソート法のページへのリンク
