画家のアルゴリズム 3Dアプリ開発支援 3D/受託/請負/常駐/人材/派遣/パートナー/協力会社

3Dアプリケーションは今後ますます普及していきます。 3Dアプリケーションの数自体はまだまだ少ないですが、キラーアプリケーションを含めた多くのアプリケーションにより、利用者が増える事は間違いはありません。

3Dアプリ特有の機能設計、プログラム面や運用面でのサポート迄、3Dアプリの上流から下流までお客様のビジネスに関するあらゆる面で、私達アクロビジョンは適切なご提案とソリューションを提供致します。

かつてない厳しい経営環境の中で、企業は顧客満足度の向上、コストダウン、生産性の向上など、自社のビジネス価値を向上するための手段を次々と講じていかなければなりません。弊社は、3Dアプリを活用してそうしたチャレンジを実践しようとするお客様のビジネスを強力にバックアップしてます。

　キーワード：画家のアルゴリズム

この記事の内容に関する文献や情報源が必要です。ご存じの方はご提示ください。出典を明記するためにご協力をお願いします。 画家のアルゴリズムまたはペインタアルゴリズム（英: painters algorithm）は、3次元コンピュータグラフィックスにおける隠面消去の最も単純な手法である。Zソート法（英: Z-sorting）、塗り重ね法（英: priority fill）とも。3次元のシーンを2次元平面に投影するとき、どのポリゴンが見え、どの面が見えないのかを決定する必要がある。 「画家のアルゴリズム」という名称は、画家が絵を描くとき遠景から順に描いていき、近いものを描く際に以前に描いた遠景の一部を塗りつぶすことに由来する。画家のアルゴリズムでは全ポリゴンを視点からの距離でソートし、遠い方から順に描いていく。視点から見えない部分は近景によって塗りつぶされるので隠面処理がなされるが、見えない遠景の部分まで描くというコストがかかる。 このアルゴリズムは、失敗する場合もある。例えば、ポリゴン同士が循環的に重なっている場合や、ポリゴンに穴がある場合である。右図のように循環的に重なっている場合、これらのポリゴンの上下（遠近）関係を決定することができない。この場合、問題のポリゴンを分割してソート可能にする必要がある。1972年、そのようなポリゴンの分割方法としてニューウェルのアルゴリズムが登場した。他にも計算幾何学の分野で様々な手法が提案されている。 穴のあるポリゴンの場合、別のポリゴンがその穴を貫通している状態が問題となる。これも循環的な重なりと同様、問題のポリゴンを分割することで解決できる。 基本的実装では、画家のアルゴリズムの効率は良くない。最終的に全く見えないポリゴンまでレンダリングしてしまうためである。したがって非常に複雑なシーンを描く場合、画家のアルゴリズムはあまりにも高いハードウェア性能を要求する。 画家のアルゴリズムの逆もある。これは、視点から見て近いオブジェクトを先に描画する方法である。その際に既に描画が行われた部分は後からは決して塗りつぶさない。これは、遠景の部分を描く際に描かない部分の色の計算（光源を考慮したり、テクスチャを張ったり）が不要となるため、コンピュータにとっては効率が良い。しかし、通常の画家のアルゴリズムの問題は逆の場合でもそのまま当てはまる。 このような問題があるため、Zバッファ技法が開発された。これは、ピクセル単位で重なりの判断を行うようなもので、奥行きを考慮した描画順序を決定する必要がない。そのようなシステムでも、画家のアルゴリズムのバリエーションを利用することがある。Zバッファは一般にハードウェア内の固定精度の奥行きバッファレジスタを使用するが、精度が有限であるために丸め誤差によって重なりの判断を誤ることがある。これはポリゴン間の隙間や重なりとなって現れる。これを防ぐため、グラフィックスエンジンの中には画家のアルゴリズムを使ってそのようなポリゴンのエッジ部分の描画を行うものもある。したがって一部のピクセルは2度描画することになるが、画像全体のごく一部であるため、性能への影響は無視できる。