JP4713591B2 - 画素サンプリングによるアンチエイリアシングのための方法及びシステム - Google Patents

Description

背景
技術分野
本発明はグラフィック処理に関し、さらに詳しくは、発明を限定するもので無いが、アンチエイリアシング処理された高品質なグラフィック画像を、高フレームレートで、少ない計算コストで生成するための方法およびシステムに関する。

３次元グラフィックのリアルタイム描画は、ゲーム、マン‐マシンインタフェース、メッセージング、イー・コマースなどを含む移動端末において魅力的なアプリケーションである。通常、３次元描画は計算コストのかかる処理であり、許容できる性能を達成するために専用のハードウェアを構築しなければならないことが多い。従って、計算の複雑さを緩和し、ハードウエアアーキテクチャが使用する帯域を減らすための革新的な方法が、非常に重要となっている。Akenine-Moller、Tomas and Jacob Strom著の「Graphics for the Masses: A Hardware Architecture for Mobile Phones」、ACM Transactions on Graphics, vol. 22, no. 3, Proceedings of ACM SIGGRAPH 2003, pp. 801-808、２００３年６月発行、に記載されているように、目と画素の平均角度は、パーソナルコンピュータ（ＰＣ）よりも移動電話の方が２〜４大きい。従って、移動装置における画像の品質は、理想的にはＰＣよりも高い方がよい。しかしながら、移動装置のリソースは、通常、より数が少ないと共に計算パワーも低い。

コンピュータグラフィックスの初期から、静止画または動画をディスプレイに表示する際のエイリアシングが問題であった。エイリアシングの例として、階段状効果があるが、これは、線を角度を付けて描いたときに表示端末において目につくものである。これらの階段状アーチファクトは、一般的に「ジャギー」と呼ばれている。３次元描画の間に、ポリゴンのエッジはしばしば目に付くエイリアシングアーチファクトを生成する。アンチエイリアシング技術を用いて、これらのアーチファクトを減らすことが望ましい。

エイリアシングによる画像のアーチファクトを削減するためのアプローチの１つは、スーパーサンプリングとして知られるものを利用することである。スーパーサンプリングアプローチでは、表示する１画素につき１以上のポイントでシーンをサンプルし、最終画像をサンプルから計算する。スーパーサンプリングの特殊例として、同様に１画素につき１以上のポイントでサンプルするマルチサンプリング技術があるが、フラグメントシェーダー（fragment shader）計算の結果（例えば、テキスチャと色）は、１ピクセルのサンプル間で共有される。マルチサンプリングアルゴリズムは、一般的に、シングルパスで１画素ごとに１サンプル以上を用い、サンプル間でグリッドセルの計算を共有する。

アンチエイリアシングへのスーパーサンプリングアプローチでは、画像は、画面に表示される最終的な解像度よりも高い解像度で描画され、１画素あたり１サンプル以上となる。各画素のサンプルは、例えば、画素の色を形成するために平均される。これは、表示する各画素について複数のサブ画素サンプルを描画し、各画素値をサブ画素サンプル値の加重加算合計として計算することにより行われる。例えば表示された各画素は、画素内部にある４つのサブ画素サンプルからなるグループの、フィルタを通された加重加算合計から構成されていても良い。

スーパーサンプリングアプローチの結果、グラフィックハードウェアは、表示される各画素について、４倍のサンプルを処理しなければならない。このアンチエイリアシング方法は、しばしば総当たり（brute-force）スーパーサンプリングと呼ばれている。総当たり（brute-force）スーパーサンプリングは、画像の品質を大きく改善することができるが、メモリと描画時間という面において大きなペナルティを伴う。例えば、目的の画像の幅と高さをｗ×ｈとする。２ｗ×２ｈの解像度を総当たり（brute-force）スーパーサンプリングに用いたとすると、１画素あたり４つのサンプルが用いられ、４倍のメモリと４倍のラスタライズのための時間を必要とする。スーパーサンプリングは、高い画像品質を提供するが、計算負荷が大きいためにフレームレートが遅くなってしまう。

アンチエイリアシング処理された画素を生成するための計算負荷を減らすために、改良スーパーサンプリング手法は、１以上のサンプル位置の値が１以上の画素の最終値を計算するために用いられるように、サブ画素サンプル位置が配置されている状態で用いられる。この種のスーパーサンプリング手法は、しばしばサンプルシェアリング（sample sharing）手法と呼ばれる。サンプルを共有することにより、取得するサンプルを１画素につき４サンプルより少なくすることができる。マルチサンプリングは、計算の一部をある画素内のすべてのサンプルにより共有することができるため、必要帯域を更に削減するために用いられる。

米国サンタクララにあるNVIDIA CorporationのGeForce3（登録商標）グラフィックスプロセッシングユニットは、スーパーサンプリング及び画素間のサブサンプルの共有をサポートするハードウエアを供給している。このスーパーサンプリング手法は「Quincunx」と呼ばれ、サイコロの「５」の目の形状をしたサブ画素サンプルパターンを示している（つまり、５つのサブ画素サンプルが、最終画素の値を計算するために用いられる）。Quincunx手法では、そのサンプル位置のために、１画素につき２つのサンプルだけ計算すればよい。残りのサンプル値は周辺画素から得ることができる。中央のサブ画素サンプルは０．５の重みが付けられ、周辺のサブ画素サンプルはそれぞれ０．１２５の重みが付けられる。Quincunx手法に関する情報は、NVIDIA Corporationの「Technical Brief, HRAA: High-Resolution Antialiasing through Multixampling」に記載されている。

白黒スキームにおける黒と白の間にある中間調の数は、どれだけ多くの画素サンプルポイントを用いるかに応じて異なる。４つの画素サンプル位置を用いた場合、黒と白の間に、最大３つのグレーシェードができる。つまり、上述したQuincunx手法では、最大４つのグレーシェードを提供する。しかしながら、Quincunx手法のグレーシェードの有効数は、２まで下がることがある。Quincunx手法では、サンプルポイントは、垂直線、水平線、４５°の斜め線を形成し、いくつかの線が傾いているために別の手法よりも性能が落ちる。

発明の要約

本発明は、アンチエイリアシング処理された高品質な画像を生成するための方法及び装置を、低計算コストで提供することを目的とする。本発明の一実施形態は、エイリアシングを低減する為の方法を目的とする。当該方法は、対応する複数の画素サンプル値を生成するために、複数の画素サンプルポイントで画像の画素をサンプリングする工程を有し、前記複数の画素サンプルポイントの少なくとも１つは、前記画素のエッジ上において、予め決められた位置から所定の範囲内で変位された位置にあり、前記予め決められた位置からの変位量は、擬似無作為に決められる。更に、当該方法は表示された画素値を生成するために、前記複数の画素サンプル値を合成する工程とを有する。本発明の一実施形態において、前記変位量は、ルックアップテーブルを用いて決められる。

本発明の別の実施形態は、エイリアシングを低減する為のシステムを目的とし、画像を保持するためのサンプルバッファと、対応する複数の画素サンプル値を生成するために、複数の画素サンプルポイントで画素サンプリングを行うプロセッサとを有し、前記複数の画素サンプルポイントの少なくとも１つは、画素のエッジ上において、予め決められた位置から所定の範囲内で擬似無作為に決められた変位量、変位された位置にある。前記プロセッサは、少なくとも１つの表示された画素値を生成するために、複数の画素サンプル値を合成する。

本発明は、添付図面を参照して以下の例示的な詳細な説明を参照することにより、より完全に理解できるであろう。

発明の実施形態の詳細な説明

以下、図面を参照して、本発明の実施形態についてより詳しく説明する。しかしながら、本発明は異なる形態で実施することができ、ここで説明する実施形態に限定解釈されるべきものではない。本発明は、請求項及び請求項に同等な構成によってのみ限定されるべきである。

本発明の様々な実施形態は、非周期的な画素サンプリングパターンを提供することにより、アンチエイリアシングアーチファクトを低減するものである。非周期的な画素サンプリングパターンは、エイリアシングアーチファクトを有しがちな特定角度のエッジを形成しない。本発明の様々な実施形態は、近隣画素の反射ルールを実行する必要性を排除し、画素のエッジを共有する近隣画素により共有される画素エッジ上のサンプルを必要とするのみである。従って、他の画素がそのサンプルに依存する必要がない。

図１Ａでは、８つの画素１０１ａ〜１０１ｈの画素サンプリングパターンを示している。図１Ａに示す画素サンプリングパターンは、画素１０１ａ〜１０１ｈのエッジ上に位置する、９つの画素サンプルポイント１０４〜１１２を示している。説明を明瞭にするために、画素の水平エッジ上に位置する画素サンプルは示していない。図１Ａの画素サンプリングパターンは、２画素毎に画素サンプリングパターンが繰り返されているため、周期性は２である。

図１Ｂは、本発明の実施形態における画素サンプリングパターンを示している。図１Ｂの画素サンプリングパターンは、画素１０１ａ’〜１０１ｈ’のエッジ上に位置する、９つの画素サンプルポイント１０４’〜１１２’を示している。説明を明瞭にするために、画素の水平エッジ上に位置する画素サンプルは示していない。図１Ｂでは、画素サンプルポイント１０５’は、画素１０１ａ’と１０１ｂ’が共有するエッジ上において、所定オフセット分、位置がずれており、他の画素サンプルポイント１０４’及び１０６’〜１１２’のいずれとも画素のエッジ上の垂直方向で同じ距離にならない。画素サンプルポイント１０５’の移動距離は、多くの方法またはアルゴリズムのいずれかにより決めることができる。１つの選択肢としては、画素サンプルポイント１０５’の移動距離をアンチエイリアシング手法を行う為の１以上の画素の為のテーブルからルックアップにより決めることができる。別の選択肢としては、オフセット量を擬似無作為に決めることができる。画素サンプルポイント１０５’が移動することにより、非周期的な画素サンプリングパターンが生成される。別の選択肢としては、画素のエッジを共有する隣接画素によって共有される画素のエッジ上にサンプルポイントがある場合、１以上の画素サンプルポイント１０４’〜１１２’を、画素のエッジ上で所定距離移動させても良い。

図２Ａは、８つの画素２０１ａ〜２０１ｈの画素サンプリングパターンを示す。図２Ａの画素サンプリングパターンは、画素２０１ａ〜２０１ｈのエッジ上に位置する９つの画素サンプルポイント２０４〜２１２を示している。説明を明瞭にするために、画素の水平エッジ上に位置する画素サンプルは示していない。図２Ａの画素サンプリングパターンは、３画素毎に画素サンプリングパターンが繰り返されているため、周期性は３である。

図２Ｂは、画素サンプリングパターンの全てのサンプルが、画素のエッジ上で所定量オフセットしているか、または、画素のエッジ上の所定範囲内に位置する場合を示している。図２Ｂは、８つの画素２０１ａ’〜２０１ｈ’の画素サンプリングパターンを示す。図２Ｂの画素サンプリングパターンは、画素２０１ａ’〜２０１ｄ’および２０２ａ’〜２０２ｄ’のエッジに位置する９つの画素サンプルポイント２０４’〜２１２’を示している。画素サンプルポイント２０４’〜２１２’それぞれは、画素のエッジの所定範囲内の所定位置に配置されている。１つの選択肢としては、画素サンプルポイント２０４’〜２１２’は、画素のエッジの所定範囲内に擬似無作為に位置される。別の選択肢としては、画素サンプルポイント２０４’〜２１２’は、画素サンプリングパターンが少なくとも２画素で反復しないように、ルックアップテーブルから読み出された所定オフセット位置に配置される。

図２Ｂは、画素サンプルポイント２０４’〜２１２’のそれぞれに関わる所定範囲を示しており、各所定範囲は、括弧により表されている。画素サンプルポイントを移動させることにより、ルックアップテーブルまたは移動量を生成するために用いられる擬似乱数発生器による制限内で、事実上、無限の周期の画素サンプリングパターンが生成されるため、ラインエッジ上の対象性をより崩し、アンチエイリアシング処理された画像の視覚的な品質を上げることができる。なお、画素サンプルポイント２０４’〜２１２’の所定範囲として画素のエッジ上の一部のみである場合について示しているが、ある特定の画素サンプルポイントが、画素のエッジ上のどの位置にあっても良いように、所定範囲を画素のエッジの全長としてもよい。また、画素サンプルポイントは厳密に画素のエッジ上にある必要は無く、画素のエッジの近辺、例えば、画素のエッジから、画素幅の１／３までの距離にあっても良い。また、追加的な画素サンプルポイントが各画素内にあっても良い。

図３Ａ及び図３Ｂは、画素サンプルポイント３０３〜３０６が、画素３０１のエッジに位置し、画素サンプルポイント３０７〜３１０が画素３０２のエッジに位置する場合の、スーパーサンプリング手法を示す図である。この例では、画素３０１と画素３０２が互いに隣接している場合に、表示メモリにおいて、画素３０１と画素３０２は画素サンプルを共有することができる。図３Ａ及び図３Ｂのスーパーサンプリング手法では、Quincunx手法と同様に、サンプルは画素３０１、３０２の角には無い。その代わりに、画素３０１、３０２の各エッジにつき１つの画素サンプルポイントが、回転された矩形構成で定義され、それぞれ０．２５の重みを与えられる。なお、各サンプル点に他の重みを用いても構わない。

正確な画素サンプル位置を決定するための式を、図３Ａ及び図３Ｂの下部にそれぞれ示している。図３Ａ及び図３Ｂの式において、ｘ０とｙ０は、それぞれ図３Ａ及び図３Ｂに示すようにｘ軸（“ｘ”）とｙ軸（“ｙ”）との原点を示す。

図示するような画素サンプルポイント３０３〜３１０の配置は、比較的少ない数の画素サンプルポイントが必要である場合のサンプリングパターンを提供する。更に、このサンプリングパターンでは、各サンプルポイントは、画素の行及び列に１つずつ配置され、２つの画素サンプルが特定画素の同じ列または行を共有することはない。このことは、図３Ａ及び図３Ｂにおいて、２つのポイントが同じ破線上に無いことで示している。また、このサンプリングパターンは画素サンプリングパターン構成の対称性を崩し、表示装置の非軸線のアンチエイリアシング効果を上げることができる。なお、非軸線とは、表示装置の水平軸または垂直軸のいずれとも平行にならない線のことである。アンチエイリアシング効果は、表示装置に対してほぼ垂直またはほぼ並行なラインについて、よりその効果が高い。例えば、表示装置上に描かれた、１以上の画素３０１、３０２を通過するポリゴンのほぼ水平に傾いたエッジを想定する。アンチエイリアシング処理された線を表すためにQuincunx手法を用いた場合、それぞれが画素の角である４つのサンプルポイントが用いられる。いくつかの画素については、ポリゴンのエッジは画素の上部のみを覆うが、２つの最上部の画素サンプル位置を覆うかも知れない。その結果、その画素の画素サンプル位置からの値を調べることにより、エッジにより画素の半分が覆われていても、決定されたその画素のアンチエイリアシング処理された値は０．２５となる。従って、画素の表現は悪くなる。

もし、略水平ラインに傾いたポリゴンのエッジが画素３０１、３０２の上部の微小な一部を覆う場合に、図３Ａ及び図３Ｂの方法を用いて同じ状況が起きるとすると、ポリゴンのエッジは画素サンプル位置を両方とも覆うことはないが、サンプル位置の場所によっては、画素３０１、３０２の上部水平エッジ上にあるサンプル位置のみを覆う。

図４は、Quincunx手法の場合と同様に、画素４０１の画素サンプルポイント４０３〜４０６が画素の角に置かれていない場合の画素サンプリングパターンを示す。画素サンプルポイント４０３〜４０６により表される画素サンプル構成を、「Quad A」と呼ぶ。同様に、画素サンプルポイント４０６〜４０９により表される画素サンプル構成を示す画素４０２を「Quad B」と呼ぶ。

Quad AとQuad Bが隣り合わせに並んだ構成を調べると、Quad Bの鏡像の画素サンプルポイント４０６〜４０９は、Quad Aの右垂直エッジ４１０（つまり、Quad Bの左垂直エッジ）で反射した時にQuad Aが対応する画素サンプルポイン４０３〜４０６であることは明らかである。画素サンプルポイント４０３〜４０６と４０６〜４０９の鏡像を取ることにより、２画素間の画素サンプルポイント４０６を共有することが可能になると共に、画素サンプリング構成の対称性を崩すことができ、よりよいアンチエイリアシング結果を達成することができる。１行につき１サンプル、１列につき１サンプルだけが存在する。例えばQuincunx手法では、最上行に２サンプル存在する。

図５は、左上の画素５０１が、Quad A構成の４つの画素サンプルポイント５１０〜５１３を含む場合のアンチエイリアシング手法を示す。画素５０１の右にある画素５０２も、Quad B構成の４つの画素サンプルポイント５１３〜５１６を含み、左端の画素５０１の右エッジについて反射している。さらに、第３画素５０３も、Quad A構成の４つの画素サンプルポイント５１６〜５１９を含む。図５から分かるように、画素５０１〜５０３は、各画素ペア５０１と５０２、５０２と５０３の間で、１つの画素サンプルポイント５１３及び５１６を共有している。画素５０４〜５０６を含む下の行の画素は、画素サンプルポイント５１１、５２０〜５２２からなるQuad B構成の画素５０４から始まる。画素サンプルポイント５１１は、画素５０４と上の画素の行にある画素５０１により共有されている。隣り合わせのQuad A（つまり、上の画素５０１）とQuad B（つまり、下の画素５０４）の構成を調べると、Quad Bの画素サンプルポイント５１１、５２０〜５２２は、Quad Aの対応するポイント５１０〜５１３が画素５０１の下の水平エッジ５３０（つまり、画素５０４の上の水平エッジ）で反射した鏡像を形成している。

画素５０５は、Quad A構成の４つの画素サンプルポイント５１５、５２２〜５２４を含む。画素５０５は画素５０２と１つの画素サンプルポイント５１５を共有し、画素５０４と１つの画素サンプルポイント５２２を共有する。右端の画素５０６についても同様であり、隣の画素５０３、５０５と、２つの画素サンプルポイント５１７、５２４を共有する。

鏡映手法を用いれば、画素５０１〜５０６の最終値を決定する際に、一番上の行及び左端の画素５０１〜５０４を除く全ての画素について、２つの新しい画素サンプル位置の値だけを計算すればよい。画素の計算が左から右へ、また、上から下の順番で行われる場合、画素５０１については、画素サンプルポイント５１０〜５１３の値を算出する。画素５０２については、画素サンプルポイント５１４〜５１６の値を算出すれば良く、画素サンプルポイント５１３の値は、画素５０１の時にすでに算出されているため、改めて算出する必要はない。画素５０３については、画素サンプルポイント５１７〜５１９の値を算出すれば良く、画素サンプルポイント５１６の値は、画素５０２の時にすでに算出されているため、改めて算出する必要はない。画素５０４については、画素サンプルポイント５２０〜５２２の値を算出すれば良く、画素サンプルポイント５１１の値は、画素５０１の時にすでに算出されているため、改めて算出する必要はない。画素５０５については、画素サンプルポイント５２３〜５２４の値を算出すれば良く、画素サンプルポイント５１５及び５２２の値は、それぞれ画素５０２及び５０４の時にすでに算出されているため、改めて算出する必要はない。同様に、画素５０６については、画素サンプルポイント５２５〜５２６の値を算出すれば良く、画素サンプルポイント５１７及び５２４の値は、それぞれ画素５０３及び５０５の時にすでに算出されているため、改めて算出する必要はない。画素が右から左、下から上へ走査される別の選択肢では、右端の列及び一番下の行を除き、全ての画素について２つのサンプルのみを必要とする。別の例では、メモリをより効率的に使用するために、１行おきに走査方向を変える。このように、走査手法により幾何プリミティブ内にある全ての画素が走査されるのであれば、どのように幾何プリミティブの画素を走査しても構わないことは、当業者には明らかであろう。

図６Ａ及び図６Ｂは、スーパーサンプリング手法を示す図であり、画素サンプルポイント３０３’〜３０６’が画素３０１’のエッジに配され、画素サンプルポイント３０７’〜３１０’が画素３０２’のエッジに配されている。これにより、画素３０１’と画素３０２’とが隣り合わせに配置された場合に、表示メモリにおいて、画素３０１’と画素３０２’が画素サンプルを共有することができる。図６Ａ及び図６Ｂに示すスーパーサンプリング手法では、１以上の画素サンプルポイント３０３’〜３０６’を画素３０１’と画素３０２’のエッジ上の範囲内の所定位置に配置することができる。図６Ａ及び図６Ｂは、画素サンプルポイント３０３’〜３１０’のそれぞれの所定範囲を括弧で示している。各括弧は画素エッジの一部の上にあるように表されているた、画素サンプルポイントは画素エッジのどの部分に配置されても良いことは理解されるであろう。図６Ａ及び図６Ｂに示す実施形態では、１つの画素サンプル位置は、画素３０１、３０２の各エッジについて定義され、それぞれ０．２５の重み付けをされている。図６Ａに示す正確な画素サンプル位置を決定するための式の例は以下の通りである：
303’=(x0+2/3+offset(x0, y0, 0), y0+1)
304’=(x0+y0+2/3+offset(x0, y0, 1))
305’=(x0+1/3+offset(x0, y0, 2), y0)
306’=(x0+1, y0+1/3+offset(x0, y0, 3))

また、図６Ｂの式の例は以下の通りである：
307’=(x0+1/3+offset(x0, y0, 0), y0+1)
308’=(x0+y0+１/3+offset(x0, y0, 1))
309’=(x0+2/3+offset(x0, y0, 2), y0)
310’=(x0+1, y0+2/3+offset(x0, y0, 3))

ただし、offset( )関数は、所定範囲における移動値を生成するための関数を示し、ｘ０及びｙ０は、図６Ａ及び図６Ｂに示されるように、ｘ軸（“ｘ”）及びｙ軸（“ｙ”）の原点をそれぞれ示す。別の実施形態では、画素サンプル位置を決定するための式において定数を追加する必要はなく、この情報はルックアップテーブル内または擬似乱数関数において、予め符号化することができる。例えば、画素サンプル位置３０３’の式は、
303’=(x0+offset(x0, y0, 0), y0+1)

のようであっても良い。
１以上の画素サンプルポイント３０３’〜３１０’の位置が移動された（オフセットされた）ことにより、特に２７°近辺での直線エッジ上のアンチエイリアシング効果を高めるために、サンプリングパターンの周期性を崩すことができる。画素サンプルポイントの移動が行われなかったサンプルパターンでは、２７°のエッジは、画素サンプルポイントが２７°回転した正方形を示すために、好ましくない結果をもたらす可能性がある。本発明の様々な実施形態における移動を行うことで、この対象性を崩すことができるため、より良い結果をもたらすことができる。

別の選択肢において、画素サンプルポイント３０３’〜３１０’それぞれを、画素サンプリングパターンが少なくとも全ての画素について繰り返されないように、ルックアップテーブルから読み出された所定オフセット位置に配置しても良い。別の選択肢では、画素サンプルポイント３０３’〜３１０’それぞれを、擬似乱数発生器を用いて配置しても良い。更に別の選択肢では、サンプリングパターンは、画素のエッジ上または近くに配置された画素サンプルポイントに加えて、画素内に配置された１以上の画素サンプルポイントを含むようにしても良い。

図７は、左端の画素４０１’の画素サンプルポイント４０３’〜４０６’が、画素４０１’のエッジ上の所定位置に配置された画素サンプリングパターンを示す。画素サンプルポイント４０７’〜４０９’は、画素４０２’のエッジ上に配置されている。画素サンプルポイント４０３’〜４０９’の少なくとも１つの位置を、画素４０１’と４０２’のそれぞれのエッジ上の所定範囲内の所定位置に配置するようにしても良い。図７は、画素サンプルポイント４０３’〜４０９’それぞれの所定範囲を示しており、各所定範囲は括弧で示している。なお、括弧は、画素のエッジ上の一部にあるように示されているが、画素サンプルポイントは画素のエッジ上のどの部分に配置しても構わない。

図８は、左上画素５０１’が４つの画素サンプルポイント５１０’〜５１３’を含む場合のアンチエイリアシング手法を示す。画素５０１’の右側にある画素５０２’も４つの画素サンプルポイント５１３’〜５１６’を含む。更に、第３の画素５０３’も４つの画素サンプルポイント５１６’〜５１９’を含む。図８から分かるように、画素５０１’〜５０３’は、画素のペア５０１’と５０２’、５０２’と５０３’の間でそれぞれ１つの画素サンプルポイント５１３’５１６’を共有している。画素の下の行は画素５０４’から始まり、画素サンプルポイント５１１’、５２０’〜５２２’の構成を有する。画素サンプルポイント５１１’は、画素５０４’と、その上の行の画素５０１’により共有されている。

画素５０５’は、４つの画素サンプルポイント５１５’、５２２’〜５２４’を含む。画素５０５’は、１つの画素サンプルポイント５１５’をその上の行の画素５０２’と共有し、１つの画素サンプルポイント５２２’を画素５０４’と共有している。右端の画素５０６’についても同様であり、２つの画素サンプルポイント５１７’及び５２４’を近隣の画素５０３’及び５０５’とそれぞれ共有している。画素サンプルポイント５１０’〜５２５’の少なくとも１つは、画素５０１’〜５０６’の少なくとも１つのそれぞれのエッジ上の所定範囲内の所定位置に配置される。別の選択肢では、画素サンプルポイントはルックアップテーブルから読み出された所定オフセット位置に配置される。別の選択肢では、画素サンプルポイントは、画素エッジの所定範囲内で擬似無作為に配置される。

画素５０１’〜５０６’の最終値を決定する際に、最上部及び左端の画素５０１’〜５０４’を除く全ての画素について、新しい画素サンプル値を２つだけ計算すればよい。別の選択肢では、右端の列及び最下行を除く全ての画素について、新しい２つのサンプル値だけが必要である。画像の画素におけるサンプル位置は、左から右へ行を走査することにより得られる。別の選択肢では、メモリをより効率的に使用するために、１行おきに走査方向を変える。なお、スーパーサンプリング手法と共に、どのような走査手法を用いても構わない。

図９Ａは、高品質アンチエイリアシング処理された画像を生成するための方法を示すフローチャートであり、画像を生成するために１以上の幾何プリミティブがサンプルされる。アプリケーション段階では（ステップ６１０）、プロセッサ（例えば、中央処理装置（ＣＰＵ））がアプリケーションプログラム（例えば、コンピューターゲーム）を実行し、ディスプレイ上で２Ｄ表示に変換される幾何プリミティブ（例えば、三角形のポリゴン）を生成する。

次に、幾何段階において（ステップ６２０）、プロセッサまたはグラフィカル処理装置（ＧＰＵ）は、照明、切り抜き、変形、投影など、ディスプレイ上のオブジェクトの見かけに影響を与える異なる視覚効果を計算する。典型的な幾何プリミティブは、コンピュータグラフィックスの３Ｄオブジェクトを生成する時に使用されるため、典型的には幾何プリミティブの頂点の画素座標が計算される。

ラスタライザ段階では（ステップ６３０）、三角形がサンプルバッファに書き込まれる。１以上の幾何プリミティブへのテクスチャ座標の遠近的に正しい挿入は、確実に正しい投影がなされるように用いられる。ラスタライザ段階は、プロセッサ及び／またはＧＰＵにより行われる。加えて、プロセッサまたはＧＰＵは、例えば、１以上の色や、別のテクスチャ座標セット、フォグなどを書き加えることができる。プロセッサまたはＧＰＵは、また、Ｚ−バッファテストを行い、最終画素が正しい色を得たことを確かめるようにしても良い。フィルタリング段階では（ステップ６４０）、サンプルバッファは、カラーバッファに保持された画素の色を生成するためにフィルタリングされる。この後、カラーバッファの内容は画面に表示される。

図９Ｂは、図９Ａのステップ６３０をより詳しく表すフローチャートである。ステップ６３１において、第１の幾何プリミティブの為の幾何プリミティブセットアップが行われ、本発明の様々な実施形態に基づく画素サンプルパターンの第１のサンプルポイントを幾何プリミティブにおいて探し、ステップ６３２に進む。ステップ６３２において、幾何プリミティブの境界内においてサンプルポイントが見つかったかどうかを判断する。幾何プリミティブ内でサンプルポイントが見つからなかった場合、ステップ６３３に進み、他に描画する幾何プリミティブが存在するかを判断する。他に描画する幾何プリミティブが存在する場合、ステップ６３４に進む。ステップ６３４において、次の幾何プリミティブを取り出してステップ６３１に戻り、幾何プリミティブのセットアップを行う。ステップ６３３で他に描画する幾何プリミティブが存在しないと判断されると、ステップ６３０の処理を終えてステップ６４０に進み、フィルターを生成するためにサンプルのフィルタリングを実行する。

ステップ６３２において、幾何プリミティブ内にサンプルポイントがあると判断された場合にはステップ６３５に進み、幾何プリミティブにおいてサンプルを見ることができるかに関する可視チェックを行う。ステップ６３６では、サンプルを見ることができるかどうかを判断する。サンプルを見ることができなければ、ステップ６３７に進み、幾何プリミティブ内で次のサンプルポイントを探すために幾何プリミティブを走査し、ステップ６３２に進む。

ステップ６３６において、サンプルポイントを見ることができると判断した場合には、ステップ６３８でサンプルの色の計算を行い、ステップ６３９でサンプルの色と奥行きを、例えばサンプルバッファなどの１以上のバッファに格納する。そして処理はステップ６３７に戻り、幾何プリミティブ内で、次のサンプルポイントを見つけるために幾何プリミティブを走査する。

図１０Ａ〜図１０Ｄは、画素８０１、８０２、８１１、８１２のそれぞれについて、３つの画素サンプルポイントを含むマルチサンプリング手法の変形例を示す。画素サンプルポイント８０３〜８０８、８１３〜８１８は、画素８０１、８０２、８１１、８１２の境界に配置されている。画素の境界は、サンプル共有の為の鏡映面としての役割を持ち、これにより表示メモリにおいて異なる画素８０１、８０２、８１１、８１２間でサンプルを共有することができる。

画素サンプルポイント８０３〜８０８、８１３〜８１８の少なくとも１つは、各画素８０１、８０２、８１１、８１２の角に配置されている。「角に」は、サンプルが画素の交差する２つの境界のほぼ角に有ることを意味し、例えば、角から、角で終焉している短い画素エッジの長さの１／３以下の距離にあることを意味している。しかしながら、角サンプルは、角サンプルが最大４つの画素値の計算に用いられるのであれば、実際の角からわずかにずれていても良い。

図１０Ａ〜図１０Ｄに示すマルチサンプリング手法において、第１画素サンプルポイントは画素８０１、８０２、８１１、８１２の２つの境界の角に定義される。第２及び第３画素サンプルポイントは、第１画素サンプルがある画素の角と交差しない、画素８０１、８０２、８１１、８１２の別の境界に定義される。図１０Ａ〜図１０Ｄにおいて、各画素８０１、８０２、８１１、８１２の第２及び第３画素サンプルは、２つの角の間の境界の中心に配置される。画素８０１において、画素サンプルポイント８０４、８０５はそれぞれ２つの角の間の境界の中心の中心に配置される。画素８０２において、画素サンプルポイント８０６、８０７はそれぞれ２つの角の間の境界の中心の中心に配置される。画素８１１において、画素サンプルポイント８１３、８１５はそれぞれ２つの角の間の境界の中心の中心に配置される。画素８１２において、画素サンプルポイント８１６、８１７はそれぞれ２つの角の間の境界の中心の中心に配置される。画素サンプルポイント８０３、８０８、８１４、８１８は、画素８０１、８０２、８１１、８１２の角にそれぞれ配置される。しかしながら、第２及び第３画素サンプルポイントは、サンプルが２つの近隣画素の値の計算に用いられるのであれば、境界上のどの位置に配置しても構わない。また、図１０Ａ〜図１０Ｄにおいて、第２及び第３画素サンプルポイント８０４、８０５、８０６，８０７、８１３、８１５、８１６、８１７は、それぞれの画素８０１、８０２、８１１、８１２の境界上の角から同じ距離に配置されている。別の選択肢では、角からの距離は、各画素サンプルポイント８０４、８０５、８０６，８０７、８１３、８１５、８１６、８１７によって異なっていても良い。画素サンプルポイントは、各々１／３の重み（つまり、重みの合計が１となるように）を与えられている。使用できる他の重みの分配としては、第１画素サンプルに０．２、第２及び第３画素サンプルにそれぞれ０．４を与える。合計が１となるのであれば、他の重みを分配しても構わない。

図１０Ａから図１０Ｄでは、各画素８０１、８０２、８１１、８１２上にグリッドを重畳して表し、角に可能な画素サンプルポイントを定義し、グリッドは、角サンプルポイントが存在する、画素８０１、８０２、８１１、８１２の画素の角と交差しない境界と交差する。各画素８０１、８０２、８１１、８１２の正確なサンプルポイントパターンを決定するための式の例は、それぞれ図１０Ａ〜図１０Ｄに示している。図１０Ａ〜図１０Ｄに示すように、図１０Ａ〜図１０Ｄの式において、ｘ０及びｙ０はｘ軸（“ｘ”）とｙ軸（“ｙ”）との原点をそれぞれ表す。

図１１は、左端の画素９０１が、角にある１つの画素サンプルポイント９０３と、画素９０１の別の境界にある２つの画素サンプルポイント９０４〜９０５を含む場合の、マルチサンプリング手法を示す。以下の文において、この画素サンプル構成をパターンＡと呼ぶ。また、画素サンプルポイント９０５〜９０７を持つ画素サンプル構成を示す第２の画素９０２をパターンＢと呼ぶ。隣り合わせに配されたパターンＡとパターンＢの構成を調べると、パターンＢの画素サンプルポイント９０５〜９０７は、パターンＡの対応するポイント９０３〜９０５の鏡像であることが明らかである。パターンＡは画素９０１の右垂直境界９０８で反射し、画素９０２のパターンＢを構成する。従って、パターンＢはパターンＡの鏡像である。

パターンＡとパターンＢの画素サンプルポイントは、それぞれの下部水平境界９０９で反射してもよい。パターンＡが、画素９０１の下部水平境界で反射したときのパターンＡの鏡像である画素サンプル構成を示す第３画素９１１を、パターンＣと呼ぶ。パターンＣは画素サンプルポイント９０４、９２３〜９２４を有し、画素サンプルポイントの１つ（即ち、サンプルポイント９０４をパターンＡと共有する。パターンＢが、下部水平境界９０９で反射したときのパターンＢの鏡像である画素サンプル構成を示す第４画素９１２を、パターンＤと呼ぶ。パターンＤは画素サンプルポイント９０６、９２４〜９２５を有し、画素サンプルポイントの１つ（即ち、サンプルポイント９０６）をパターンＢと共有し、画素サンプルポイントの１つ（即ち、サンプルポイント９２４）をパターンＣと共有する。

画素サンプルポイント９０３〜９０５の位置を垂直境界９０８について反射することにより、画素サンプルポイント９０５を２つの画素９０１、９０２により共有することができると共に、構成の対称性を崩し、アンチエイリアシング処理結果を向上させることができる。図１１に示すマルチサンプリング手法では、画素の行及び画素の列毎に、１つのサンプルがある。これに対し、Quincunx手法では、一番上の行では２つのサンプルがある。

図１２は、３×３画素構成の９画素１００１〜１００９におけるアンチエイリアシング手法を示す図である。左上端画素１００１は、パターンＡ構成の３つの画素サンプルポイント１０１０〜１０１２を含む。第２画素１００２は、パターンＢ構成の３つの画素サンプルポイント１０１２〜１０１４を含み、左上端画素１００１の右側の境界で反射している。更に、画素１００３はパターンＡ構成の３つの画素サンプルポイント１０１４〜１０１６を含む。図１２から分かるように、上の行の画素１００１〜１００３は、画素ペア１００１と１００２、１００２と１００３がそれぞれ１つの画素サンプルポイント１０１２、１０１４を共有している。

画素の２行目は、画素サンプルポイント１０１１、１０１７〜１０１８のパターンＣ構成を示す画素１００４から始まる。画素サンプルポイント１０１１は画素１００４と画素１００１により共有される。２行目の画素１００５は、パターンＤ構成の３つの画素サンプルポイント１０１３、１０１８〜１０１９を含む。画素１００５は、１つの画素サンプルポイント１０１３を画素１００２と共有し、１つの画素サンプルポイント１０１８を画素１００４と共有する。２行目の画素１００６についても同様に３つの画素サンプルポイント１０１５、１０１９〜１０２０を有し、２つの画素サンプルポイント１０１５、１０１９を近隣画素１００３、１００５と共有する。

画素の３行目は、画素サンプルポイント１０１７、１０２１〜１０２２のパターンＡ構成を示す画素１００７から始まる。画素サンプルポイント１０１７は画素１００７と第４の１００４により共有される。画素１００８は、パターンＢ構成の３つの画素サンプルポイント１０１９、１０２２〜１０２３を含む。画素１００８は、１つの画素サンプルポイント１０１９を画素１００５と共有し、１つの画素サンプルポイント１０２２を左の画素１００７と共有する。３行目の画素１００９についても同様に３つの画素サンプルポイント１０１９、１０２４〜１０２５を有し、１つの画素サンプルポイント１０１９を近隣画素１００６と共有する。

図１２を調べることにより、最上行及び左端列を除いて、画素の角に配置された全ての画素サンプルポイントが４つの画素により共有されることは明らかである。従って、角の画素サンプルのほとんど（比較的大きな画素のグリッドについて）は、４画素に付き１回計算すればよく、画素当たりの計算コストが０．２５となる。２つの画素により共有される角の画素の境界と交差しない境界上に配置された画素サンプルポイント１０１１、１０１２、１０１３、１０１５、１０１８、１０２１、１０２２、１０２３、１０２４は、２つの近隣画素について１回計算をすればよい。従って、これらの境界画素の計算コストは、１画素当たり０．５である。

従って、鏡映手法を用いることにより、最上部及び左端画素１００１〜１００４、１００７を除く全ての画素は、画素１００１〜１００９の最終値を決定するために、平均で１．２５（０．２５＋０．５＋０．５＝１．２５）の新しい画素サンプルポイント値の計算を必要とする。別の選択肢では、右端列及び最下行の画素を除く全ての画素が、１．２５サンプルのみを必要とする。最も知られたマルチサンプリング構成では、画素の最終値を決定するために、少なくとも２つの画素サンプルを計算しなければならない。

画素におけるサンプル位置は、左から右へラインを走査することにより得ることができる。他の選択肢では、メモリをより有効に利用するために、走査方向を１行おきに変える。なお、マルチサンプリング手法と共に、どのような走査手法を用いても構わない。

図１３Ａ〜図１３Ｄはマルチサンプリング手法を示す。図１３Ａ〜図１３Ｄに示すマルチサンプリング手法は、各画素８０１’、８０２’、８１１’、８１２’それぞれについて３つの画素サンプルを含むものとして示している。画素サンプルポイント８０３’〜８０８’、８１３’〜８１８’は、画素８０１’、８０２’、８１１’、８１２’の境界に配置されている。画素サンプルポイント８０１’、８０８’、８１４’、８１８’はそれぞれ画素８０１’、８０２’、８１１’、８１２’の角に配置されている。図１３Ａ〜図１３Ｄのマルチサンプリング手法によれば、１以上の画素サンプルポイント８０４’、８０５’、８０６’、８０７’、８１３’、８１５’、８１６’、８１７’が、画素８０１’、８０２’、８１１’、８１２’のエッジ上の範囲内の所定位置に配置されている。図１３Ａ〜図１３Ｄは、各画素サンプルポイント８０４’、８０５’、８０６’、８０７’、８１３’、８１５’、８１６’、８１７’の所定範囲を示し、各所定範囲を括弧で表している。「角に」は、サンプルが画素の交差する２つの境界のほぼ角に有ることを意味している。しかしながら、角サンプルは、角サンプルが最大４つの画素値の計算に用いられるのであれば、実際の角からずれていても良い。例えば、サンプルポイントが角の近くにあっても良く、そのようなサンプルポイントは、画素幅の１／３以下の距離に位置する。更に別の選択肢では、サンプリングパターンは、画素のエッジの近くまたは角に位置する画素サンプルポイントの他に、画素内にある１以上の画素サンプルポイントを含んでいても良い。

図１３Ａ〜図１３Ｄのマルチサンプリング手法において、第１画素サンプルポイント８０３’、８０８’、８１４’、８１８’はそれぞれ、画素８０１’、８０２’、８１１’、８１２’の２つの境界の角に定義される。第２及び第３画素サンプルポイント８０４’、８０５’、８０６’、８０７’、８１３’、８１５’、８１６’、８１７’は、角画素サンプルと交差しない、画素８０１’、８０２”、８１１’、８１２’の別の境界に定義される。図１３Ａ〜図１３Ｄにおいて、各画素８０１’、８０２”、８１１’、８１２’の第２及び第３画素サンプルポイント８０４’、８０５’、８０６’、８０７’、８１３’、８１５’、８１６’、８１７’は、２つの角の間の境界の中心に配置される。しかしながら、第２及び第３画素サンプルポイント８０４’、８０５’、８０６’、８０７’、８１３’、８１５’、８１６’、８１７’は、サンプルが２つの近隣画素の値の計算に用いられるのであれば、境界上のどの位置に配置しても構わない。画素サンプルは、各々１／３の重み（つまり、重みの合計が１となるように）を与えられている。従って、別の重みの分配例では、第１画素サンプルに０．２、第２及び第３画素サンプルにそれぞれ０．４を与える。

図１３Ａに示す各画素の正確な画素サンプルポイントパターンを決定するための式の例は以下の通りである：
803’=(x0, y0+1)
804’=(x0+0.5+offset(x0, y0, 0), y0)
805’=(x0+1, y0+0.5+offset(x0, y0, 1))

図１３Ｂについては以下の通りである：
806’=(x0, y0+0.5+offset(x0, y0, 0))
807’=(x0+0.5+offset(x0, y0, 1), y0)
808’=(x0+1, y0+1)

図１３Ｃについては以下の通りである：
813’=(x0+0.5+offset(x0, y0, 0), y0+1)
814’-(x0, y0)
815’=(x0+1, y0+0.5+offset(x0, y0, 1))

図１３Ｄについては以下の通りである：
816’=(x0, y0+0.5+offset(x0, y0, 0)
817’=(x0+0.5+offset(x0, y0, 1), y0+1)
818’=(x0+1, y0)

なお、offset( )関数は、所定範囲における移動値を生成するための関数を示し、ｘ０及びｙ０は、図１３Ａ〜図１３Ｄに示されるように、ｘ軸（“ｘ”）及びｙ軸（“ｙ”）の原点をそれぞれ示す。別の実施形態では、画素サンプル位置を決めるために定数０．５を式に含ませる必要は無く、これは、この情報をルックアップテーブルまたは擬似乱数関数に含ませることができるからである。例えば、画素サンプル位置８０４’の式を、
804’=(x0+offset(x0, y0, 0), y0)
としても良い。
移動（オフセット）した画素サンプルポイント８０３’〜８０８’、８１３’〜８１８’の位置は、構成の対称性を崩し、アンチエイリアシング効果を向上させることができる。ある選択肢においては、各画素サンプルポイント８０４’〜８０７’、８１３’、８１５’〜８１７’を、画素サンプリングパターンが少なくとも各画素において繰り返されないように、ルックアップテーブルから読み出した所定のオフセット位置に配置しても良い。別の選択肢では、画素サンプルポイント８０４’〜８０７’、８１３’、８１５’〜８１７’を、擬似乱数発生器を用いて配置しても良い。

図１４は、左端画素９０１’が角にある１つの画素サンプルポイント９０３’と、画素９０１’の境界上の範囲内の所定位置にある２つの画素サンプルポイント９０４’〜９０５’とを含む場合のマルチサンプリング手法を示す。第２画素９０２’は、角にある画素サンプルポイント９０７’と、画素９０２’の境界上の範囲内の所定位置にある２つの画素サンプルポイント９０５’と９０６’とを有する。第３画素９１１’は、角にある画素サンプルポイント９２３’と、画素９１１’の境界上の範囲内の所定位置にある２つの画素サンプルポイント９０４’と９２４’とを有する。第４画素９１２’は、角にある画素サンプルポイント’９２５と、画素９１２’の境界上の範囲内の所定位置にある２つの画素サンプルポイント９０６’と９２４’とを有する。図１４は、画素サンプルポイント９０４’、９０５’、９０６’、９２４’それぞれの所定範囲を示し、各所定範囲は括弧で表している。各括弧は画素エッジ上の一部にあるように表されているが、画素サンプルポイントは画素エッジ上のどの部分に配置されても良いことは理解されよう。図１４に示すように、画素サンプルポイント９０４’、９２３’〜９２４’は画素サンプルパターンを構成し、画素サンプルポイント９０４’は画素９０１’と９１１’により共有されている。画素サンプルポイント９０６’、９２４’〜９２５’は画素サンプルパターンを構成し、画素サンプルポイント９０６’は画素９０２’と９１２’により共有され、画素サンプルポイント９２４’は画素９１１’と９１２’により共有されている。各画素サンプルポイントの所定位置は、例えば、ルックアップテーブルを参照したり、擬似無作為に決定しても良い。

選択された画素サンプル位置の移動またはオフセット配置により、画素サンプリング構成の対称性を崩し、よりよいアンチエイリアシング効果を達成することができる。更に、画素の行及び画素の列毎に、１つのサンプルがあるだけである。これに対し、例えばQuincunxでは、一番上の行の画素では２つのサンプルがある。

図１５は、３×３画素構成の９画素１００１’〜１００９’におけるアンチエイリアシング手法を示す図である。画素１００１’は、３つの画素サンプルポイント１０１０’〜１０１２’を含む。画素１００１’の右にある画素１００２’は、３つの画素サンプルポイント１０１２’〜１０１４’を含む。更に、画素１００３’は３つの画素サンプルポイント１０１４’〜１０１６’を含む。図１５から分かるように、上の行の画素１００１’〜１００３’は、画素ペア１００１’と１００２’、１００２’と１００３’がそれぞれ１つの画素サンプルポイント１０１２’、１０１４’を共有している。

画素の２行目は、画素サンプルポイント１０１１’、１０１７’〜１０１８’の構成を示す画素１００４’から始まる。画素サンプルポイント１０１１’は画素１００４’と画素１００１’により共有される。２行目の画素１００５’は、３つの画素サンプルポイント１０１３’、１０１８’〜１０１９’を含む。画素１００５’は、１つの画素サンプルポイント１０１３’を画素１００２’と共有し、１つの画素サンプルポイント１０１８’を画素１００４’と共有する。２行目の画素１００６’についても同様に３つの画素サンプルポイント１０１５’、１０１９’〜１０２０’を有し、２つの画素サンプルポイント１０１５’、１０１９’を近隣画素１００３’、１００５’と共有する。

画素の３行目は、画素サンプルポイント１０１７’、１０２１’〜１０２２’の構成を示す画素１００７’から始まる。画素サンプルポイント１０１７’は画素１００７’と画素１００４’により共有される。画素１００８’は、３つの画素サンプルポイント１０１９’、１０２２’〜１０２３’を含む。画素１００８’は、１つの画素サンプルポイント１０１９’を画素１００５’と共有し、１つの画素サンプルポイント１０２２’を画素１００７’と共有する。３行目の画素１００９’についても同様に３つの画素サンプルポイント１０１９’、１０２４’〜１０２５’を有し、１つの画素サンプルポイント１０１９’を近隣画素１００６’と共有する。１以上の画素サンプルポイント１０１１’、１０１２’、１０１３’、１０１５’、１０１６’、１０１８’、１０２０’、１０２１’、１０２２’、１０２３’、１０２４’、１０２５’を、画素１００１’〜１００９’の境界上の範囲内の所定位置に配置しても良い。図１５は、画素サンプルポイント１０１１’、１０１２’、１０１３’、１０１５’、１０１６’、１０１８’、１０２０’、１０２１’、１０２２’、１０２３’、１０２４’、１０２５’それぞれの所定範囲を示し、各所定範囲は括弧で示している。各括弧は画素エッジ上の一部分にあるように表されているが、画素サンプルポイントは画素エッジ上のどの部分に配置されても良いことは理解されるであろう。各画素サンプルポイントの所定位置は、例えば、擬似無作為に、またはルックアップテーブルを参照して決定しても良い。

図１５を調べることにより、最上行及び左端列を除いて、画素の角に配置された全ての画素サンプルポイントが４つの画素により共有されることは明らかである。従って、角の画素サンプルのほとんど（比較的大きな画素のグリッドについて）は、４画素につき１回計算すればよく、画素当たりの計算コストは０．２５となる。２つの画素により共有される、角の画素の境界と交差しない境界上に配置された画素サンプルポイント１０１１’、１０１２’、１０１３’、１０１５’、１０１６’、１０１８’、１０２０’、１０２１’、１０２２’、１０２３’、１０２４’、１０２５’は、２つの近隣画素について１回計算をすればよい。従って、これらの境界画素の計算コストは、１画素当たり０．５である。

従って、最上部及び左端画素１００１’〜１００４’、１００７’を除く全ての画素は、画素１００１’〜１００９’の最終値を決定するために、平均で１．２５（０．２５＋０．５＋０．５＝１．２５）の新しい画素サンプルポイント値の計算を必要とする。別の選択肢では、右端列及び最下行の画素を除く全ての画素が、１．２５サンプルのみを必要とする。最も知られたマルチサンプリング構成では、画素の最終値を決定するために、少なくとも２つの画素サンプルを計算しなければならない。

画素におけるサンプルポイントは、左から右へラインを走査することにより得ることができる。他の選択肢では、メモリをより有効に利用するために、走査方向を１行おきに変える。本発明の原則から離れない限り、どのような走査手法を用いても構わないことは理解されるであろう。

図１５に示すマルチサンプリング手法を用いることにより、画素の最終値を計算するために最大３回、表示メモリにアクセスするだけでよい。しかしながら、画素値の１つまたはいくつか続く計算において必要とされるサンプルを一時的に保持する為の、オンチップキャッシュメモリなどの小型の高速メモリを追加することにより、表示メモリにアクセスする必要回数を、最小で１．２５に下げることができる。このアプローチをQuincunx手法に用いると、画素の最終値を計算するために、最小２回、メモリにアクセスする必要がある。更に、１つのサンプル（即ち、第１画素の値の計算と、次の画素の値の計算に用いられるサンプル）を保持するために、更に小さい追加メモリを用いることができる。

図１４を再び参照すると、表示メモリから画素サンプル９０３’〜９０５’を取得することにより、画素９０１’の最終値を計算することができる。そして、画素サンプル９０５’は、追加メモリに一時的に保持される。画素９０２’の最終値を計算するためには、表示メモリから画素サンプル９０６’〜９０７’を取得するだけで良く、画素サンプル９０５’は追加メモリから得ることができる。その結果、例えば、移動端末の１７６×１７６画素グリッドといった、大きなピクセルのグリッドの画素ほとんどを計算するために、表示メモリに２回アクセスするだけでよい。Quincunx手法を用いると、画素の最終値を計算するために、表示メモリに３回、追加メモリに２回アクセスする必要がある。

図１６は、画素サンプルパターンを有するスーパーサンプリング手法に基づいて、ポリゴンなどの１以上の幾何プリミティブを描画するためのシステムを示す図である。中央処理装置（ＣＰＵ）７０１は、データバス７０３を介してメモリ７０２に接続している。メモリ７０２はシステム上で実行されるアプリケーションプログラム（例えば、コンピュータゲームまたはコンピュータ支援設計（ＣＡＤ）プログラム）を保持する。ＣＰＵ７０１はメモリ７０２の指示を取り出して、所定タスクを行うためにその指示を実行する。ここでは、ＣＰＵ７０１のタスクは、ディスプレイ７０５上に描くオブジェクトに関する情報をグラフィックス処理装置（ＧＰＵ）７０４に提供することである。

ＧＰＵ７０４は、プロセッサの形態、例えば、デジタル信号プロセッサ（ＤＳＰ）や特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、ハードワイヤードロジック（hard-wired logic）などであっても良い。別の選択肢としては、ＣＰＵ７０１上で実行されても良い。ＧＰＵ７０４もまたバス７０３に接続されているが、ＣＰＵ７０１とＧＰＵ７０４間で大量の情報を転送する必要がある場合には、別の高速バス７０６を介してＣＰＵ７０１に接続してもよい。これにより、別の高速バス７０６によるデータ転送が、通常のバス７０３上のデータトラフィックを妨げることはない。

表示メモリ７０７もバス７０３に接続され、ディスプレイ７０５上に描く画像（つまり、フレーム）に関する、ＧＰＵ７０４から送られる情報を格納する。更に詳しくは、表示メモリはサンプルバッファ７０７ａとカラーバッファ７０７ｂとを含む。サンプルバッファ７０７ａは、最終カラーバッファ７０７ｂ内にある画素のほぼ２倍のサンプルを持つ。カラーバッファ７０７ｂは、画像の描画が完了した後、画面上に表示する画素の色を保持する。ＣＰＵ７０１とＧＰＵ７０４間の相互接続と同様に、表示メモリ７０７は、別の高速バスによりＧＰＵ７０４に直接接続しても良い。ＧＰＵ７０４と表示メモリ７０７は、通常、動画を生成するために用いられるため、これら２つのユニットのリンクは、通常、できるだけ速くすることが求められると共に、バス７０３の通常のトラフィックを妨げないことが求められる。

表示メモリ７０７は、共有バス７０３または別の高速バス７０９を介してビデオデジタル−アナログ変換器（ＶＤＡＣ）７０８に接続され、ＶＤＡＣ７０８は、カラーバッファ７０７ｂから情報を読み出して、アナログ信号（例えば、赤、緑、青（ＲＧＢ）の複合信号）に変換し、変換されたアナログ信号は、ディスプレイ７０５上に各画素を描くためにディスプレイ７０５に供給される。ＧＰＵ７０４は、カラーバッファ７０７ｂに保持された画素を生成するために、ここで説明した画素サンプリングパターンを用いてスーパーサンプリングまたはマルチサンプリング手順を実行する。

上述した詳細な説明は実施形態の例を示すもので、画素サンプルポイントの位置はテーブルルックアップまたは擬似無作為方法を用いて決定するものとしたが、本発明の原則に基づいて、画素サンプルポイントを配置する他の方法を用いても構わないことは理解されるであろう。

上述した詳細な説明は本発明の実施形態である。本発明の範囲は、この説明により制限されるべきものではない。例えば、本発明は、サンプルを画素のエッジに配置するどのサンプル手法とも共に用いることができることは理解されるであろう。また、本発明の種々の説明した実施形態におけるスーパーサンプリング手法は、コンピュータ及び移動端末を含む多くの装置において含むことができる。本発明の範囲は、代わりに、以下の請求項及び同等のものによって定義される。

図１Ａは、アンチエイリアシングのための画素サンプリングパターンの一例を示す図である。 図１Ｂは、アンチエイリアシングのための画素サンプリングパターンを示す図である。 図２Ａは、アンチエイリアシングのための画素サンプリングパターンの他の例を示す図である。 図２Ｂは、アンチエイリアシングのための画素サンプリングパターンを示す図である。 、 図３Ａ及び図３Ｂは、画素サンプルパターンにおける画素サンプル位置の計算を示す図である。 図４は、画素サンプルパターンの鏡映工程を示す図である。 図５は、別の画素サンプルパターンの別の鏡映工程を示す図である。 、 図６Ａ及図６Ｂは、画素サンプルパターンを示す図である。 図７は、画素サンプルパターンを示す図である。 図８は、画素サンプルパターンを示す図である。 、 図９Ａ及び図９Ｂは、アンチエイリアシング処理された画像を生成するための方法を示す図である。 、 、 、 図１０Ａから図１０Ｄは、各画素について３画素サンプルを含むマルチサンプリング手法の変形例を示す図である。 図１１は、他のマルチサンプリング手法を示す図である。 図１２は、３×３画素構成の９画素におけるアンチエイリアシング手法を示す図である。 、 、 、 図１３Ａから図１３Ｄは、マルチサンプリング手法を示す図である。 図１４は、マルチサンプリング手法を示す図である。 図１５は、３×３画素構成におけるアンチエイリアシング手法を示す図である。 図１６は、アンチエイリアシング処理された画像を生成するためのグラフィックシステムを示す概略ブロック図である。

Claims (28)

1. エイリアシングを低減する為の方法であって、
   対応する複数の画素サンプル値を生成するために、画素の１以上のエッジ上にある複数の画素サンプルポイントで画像の画素をサンプリングする工程と、
   表示された画素値を生成するために、前記複数の画素サンプル値を合成する工程とを有し、
   前記画素の第１のエッジ上にある前記複数の画素サンプルポイントの少なくとも１つは、前記画素の第１のエッジ上において、予め決められた位置から所定の範囲内で変位された位置にあり、前記予め決められた位置からの変位量は、擬似無作為に決められることを特徴とする方法。
2. 前記擬似無作為に決められた変位量は、擬似乱数発生器を用いて決められることを特徴とする請求項１に記載の方法。
3. 前記複数の画素サンプルポイントの少なくとも１つは、隣接画素の少なくとも１つの画素サンプルポイントと共有されることを特徴とする請求項１に記載の方法。
4. 前記複数の画素サンプル値を合成する工程は、前記複数の画素サンプル値の平均を決定することを特徴とする請求項１に記載の方法。
5. 前記複数の画素サンプル値は、複数の色値を有することを特徴とする請求項１に記載の方法。
6. 前記表示された画素値は、色値を含むことを特徴とする請求項１に記載の方法。
7. 前記変位量は、０を含むことを特徴とする請求項１に記載の方法。
8. 前記複数の画素サンプルポイントは、略非周期的なサンプルパターンであることを特徴とする請求項１に記載の方法。
9. 前記複数の画素サンプルポイントは、４つの画素サンプルポイントから成ることを特徴とする請求項１に記載の方法。
10. 前記複数の画素サンプルポイントは、３つの画素サンプルポイントから成ることを特徴とする請求項１に記載の方法。
11. 前記複数の画素サンプルポイントは、
    画素の角に位置する第１の画素サンプルポイントと、
    画素の第１のエッジ上に位置する第２の画素サンプルポイントと、
    画素の第２のエッジ上に位置する第３の画素サンプルポイントと
    を含むことを特徴とする請求項１に記載の方法。
12. 前記第３の画素サンプルポイントが、前記画素の第２のエッジ上において、予め決められた位置から所定の範囲内で擬似無作為に決められた変位量、変位した位置にあることを特徴とする請求項１１に記載の方法。
13. エイリアシングを低減する為のシステムであって、
    画像を保持するためのサンプルバッファと、
    対応する複数の画素サンプル値を生成するために、画素の１以上のエッジ上にある複数の画素サンプルポイントで画素サンプリングを行うプロセッサとを有し、
    前記画素の第１のエッジ上にある前記複数の画素サンプルポイントの少なくとも１つは、前記画素の第１のエッジ上において、予め決められた位置から所定の範囲内で擬似無作為に決められた変位量、変位された位置にあり、
    前記プロセッサは、少なくとも１つの表示された画素値を生成するために、複数の画素サンプル値を合成することを特徴とするシステム。
14. 前記少なくとも１つの表示された画素値を保持するためのカラーメモリを更に有することを特徴とする請求項１３に記載のシステム。
15. 前記プロセッサは、中央処理装置（ＣＰＵ）とグラフィック処理回路（ＧＰＵ）とから成るグループから選択されることを特徴とする請求項１３に記載のシステム。
16. 前記プロセッサは、前記複数の画素サンプル値の平均を決定することにより前記複数の画素サンプル値を合成することを特徴とする請求項１３に記載のシステム。
17. 前記複数の画素サンプル値は、複数の色値を有することを特徴とする請求項１３に記載のシステム。
18. 前記少なくとも１つの表示された画素値は、色値を含むことを特徴とする請求項１３に記載のシステム。
19. 前記変位量を決定するための擬似乱数発生器を更に有することを特徴とする請求項１３に記載のシステム。
20. 前記変位量は、０を含むことを特徴とする請求項１３に記載のシステム。
21. 前記複数の画素サンプルポイントの少なくとも１つは、前記画像の隣接した画素の少なくとも１つの画素サンプルポイントに対応することを特徴とする請求項１３に記載のシステム。
22. 前記複数の画素サンプルポイントは、略非周期的なサンプルパターンであることを特徴とする請求項１３に記載のシステム。
23. 前記複数の画素サンプルポイントは、４つの画素サンプルポイントから成ることを特徴とする請求項１３に記載のシステム。
24. 前記複数の画素サンプルポイントは、３つの画素サンプルポイントから成ることを特徴とする請求項１３に記載のシステム。
25. 前記複数の画素サンプルポイントは、
    画素の角に位置する第１の画素サンプルポイントと、
    画素の第１のエッジ上に位置する第２の画素サンプルポイントと、
    画素の第２のエッジ上に位置する第３の画素サンプルポイントと
    を含むことを特徴とする請求項１３に記載のシステム。
26. 前記第３の画素サンプルポイントが、前記画素の第２のエッジ上において、予め決められた位置から所定の範囲内で擬似無作為に決められた変位量、変位した位置にあることを特徴とする請求項２５に記載のシステム。
27. コンピュータに、請求項１乃至１２のいずれか１項に記載の方法の各工程を実行させるためのプログラム。
28. 請求項２７に記載のプログラムを格納したことを特徴とするコンピュータが読み取り可能な記憶媒体。

Images