JP4690312B2 - ３ｄリンダリングされたグラフィックスのためのタイリングシステムの改良 - Google Patents

Description

本発明は、３Ｄコンピュータグラフィックス画像の生成に関し、我々の英国特許2343603、及び先行関連特許GB2298111に開示されている技術の改良に関する。

これらのシステムにおいては、２Ｄ画像面が好ましくは画素の矩形領域に細分され、各領域毎にその領域に‘関心’のあるオブジェクトのリストがコンパイルされる。これらの領域をタイルと呼ぶ。特定のタイルのためのリストがこれらの全てのオブジェクトを含む場合には、そのタイルを完全にレンダリングすることができる。代替スキーム（我々の特許出願PCT / GB01 / 02536に開示されているように）によれば、部分的なレンダリングを可能にし、それによってリストは単に要求されたオブジェクトのサブセットを含むことができる。

どのプリミティブ（典型的には三角形及び線分である）を、どのタイル内に配置すべきかを決定する費用有効な手段を有することが重要である。１つの例が、図１に示されている。これは、画素２の集合からなる仮想画像面（例えば、フレームバッファー）１を示している。これらの画素は、タイル３によってグループ化されている。プリミティブ４の例として三角形が示されている。これは、少なくとも陰影付きタイル５のためのリストによって配置、または参照される必要があろう。このプリミティブを付加的なタイルリスト（例えば、タイル６のためのような）内に含むことは差し支えないが、陰影付きのどのタイルをも除外してしまうことは正しくないことに注目されたい。

どのプリミティブがどのタイル内にあるかを決定するプロセスを、‘ビンニング’または‘タイリング’と言う。

近代的な３Ｄコンピュータゲームは、極めて高い多角形カウントを、従って多数のプリミティブを有する傾向がある。シーンの生成中、多くのプリミティブがサンプルするには小さ過ぎるようになり、従って画像に影響しない。これはオブジェクトとして発生し、これらは後退を距離で描くために使用される。これらの極めて小さいプリミティブをタイルリスト内に格納することは、時間、メモリ、及び処理努力を不要に使用することになる。図７に、小さい三角形プリミティブ５３の簡単な例が、画像画素の格子５０内に示されている。典型的には、画素（例えば、５１）は１つの点（例えば、左上隅５２）においてサンプルされる。三角形５３はどのサンプル位置をも含んでおらず、従って画像に影響しない。この特定例においては、この事実は、プリミティブのバウンディングボックス５４を考慮することによって平凡に決定することができる。これはどのような‘整数’サンプリング位置をも含まないので、このプリミティブは冗長である。

図８及び９に、サンプリング点を全く含まない他の小さい三角形を示す。しかしながらこれらの場合には、バウンディングボックス拒絶テストはこれらのプリミティブの淘汰に失敗しよう。１つの素朴な費用節約方法は、プリミティブの面積を計算し、もしそれが小さければその表面を拒絶することである。不幸にも、オブジェクトを、例えば「小さい三角形へのモザイク化−全ての小さい三角形の拒絶」によってモデル化することは、全部のオブジェクトを容易に消滅させ得るので、常に上手く行くとは限らない。

３Ｄコンピュータグラフィックスにおいては、典型的には｛両方、時計方向、反時計方向｝の１つである関連付けられた‘ワインディング順序’を用いて三角形／凸多角形プリミティブを定義することが一般的である。ワインディング順序は、レンダリングの前に若干のプリミティブを排除するための性能最適化として使用される。この最適化は、もし、投影の後に、プリミティブがその指定されたワインディング順序とマッチしない頂点順序を有していれば、そのプリミティブを無視することができるように機能する。

IEEE 754標準においては、浮動小数点数は、符号ビット（符号）、指数値（ｅｘ）、及び‘Ｍ’ビット仮数値（ｍ）を使用して表される。ｍは、無視することができる若干の小さい特別な場合を除いて（−１）^sign・２^ex・｛１＋（ｍ／２^M）｝を表す。ここに、０≦ｍ＜２^Mである。32ビットのIEEE浮動小数点数の場合にはＭは23であるが、簡約化精密数学的処理ではより少ないビットを使用することができる。もしシステムが正規化されたIEEEフロート（ｘ）を、仮数のＭビットを使用するシステムに変換するのであれば、近似ｘ値

内の誤差が、次の不等式に従うことを示すことができる。

加算及び乗算演算のための同じような式を導出することができる。

GB2343603特許には、どのプリミティブ（即ち、オブジェクトを表すために使用される基本的レンダリング要素）が特定のタイル内にあるかを決定する方法が記述されている。各プリミティブ毎に、先ず候補タイルのバウンディングボックスが決定され、次いでそのタイルの若干のコーナー点に対して各エッジ方程式をテストすることによって、候補タイルを排除することが試みられる。各エッジ毎に、各タイルの１つのコーナーだけをテストすればよい。もし候補が排除されなければ、そのプリミティブはタイルのリストに付加される。

上述した方法には幾つかの不都合な面が存在する。即ち、

（１）拒絶計算を遂行するために使用した数学的処理の精度は、あるプリミティブをカバーしているのはどの画素かを決定する時に、レンダリングシステムが使用するものと少なくとも同程度に正確であるか、または少なくともそれと同一の結果を与えなければならない。

潜在的問題の例を図２に示す。複数の画素８からなる画像のタイル７の２×２サブセットが、プリミティブの境界エッジ９と共に示されている。グレーで示されているこれらの画素は、レンダラーによってプリミティブの‘内側’にあると見られる画素を表している。明らかに、このような画素を含むどのタイルも、たとえこのような画素が１つだけしか（例えば、１０）存在しなくとも、そのリスト内に含まれるプリミティブをも有しているべきである。

これは平凡なことに見えるが、実際には、より複雑であり得る。例えば、種々の内側／外側テストを遂行するために浮動小数点算術を使用して特定のタイルをレンダリングする場合、画像の左上隅に画素原点を使用するのではなく、レンダリングが例えばタイルの左上にローカル原点を使用できるように座標系を再位置合わせすることができる。このようにすると、タイルの内側をレンダリングする場合に必要なハードウェアのコストが低下するが、‘タイリング’演算のために使用することができる精度と正確に同一の精度で‘グローバルテスト’を行うことが極めて困難であり、及び／またはより高価になる。もし精度に何等かの差が存在すれば、タイル１１がプリミティブを含まないように見え、従って画素１０は不正確にレンダリングされることになる。

たとえ数学的処理が、レンダラーの内側で使用されるものと正確に同一の結果を与えるとしても、ハードウェア解決法にはかなりな量のシリコンを必要としよう。

代替として、浮動小数点ではなく、固定小数点数学的処理を使用することができるが、任意多角形が有効支援された数学的処理範囲に‘クリップ’されてしまうという問題を招く。クリッピングは、回避することが好ましい高価な演算である。

（２）タイルの‘テストコーナー’は、特定のエッジの線／面方程式のパラメータに依存して変化する。これは、タイル毎に／エッジ毎に決定を必要とするので不便である。

（３）システムは三角形だけを支援しており、平行四辺形から構成された‘太線’のような他のプリミティブ型にも‘タイリング’プロセスを適用することが有用である。勿論、平行四辺形を１対の三角形に変換すること、または何等かの凸多角形を支援する方法を拡張することさえも平凡なことではあるが、線の場合にはより効率的な方法が望ましい。

（４）システムは、‘小さな’プリミティブ（例えば、ある画素のサイズの周囲のプリミティブのような）がタイリングエンジンに供給されるが、実際にレンダリングされないような場合に対処しようとはしない。図６乃至８に示されているような多くのこれらのプリミティブは、それらがレンダラー内に使用される‘サンプリング点’の間に入ってしまうので、単に最終画像の結果に影響しないだけである。従って、これらをタイルリストに付加することは無駄な努力である。

本発明の好ましい実施の形態は、図６に示す単純な場合だけではなく、図７及び８から生ずる場合をも処理する方法に関する。

我々は、各（凸多角形）プリミティブを最小セットのタイルリストに付加することが望ましいが、この最小セットの計算まで拡張することが可能であり、また図１に示した６のような余分な不要タイルを臨時に付加することが間違いなく安全であることも理解している。従って、たとえそれが誤りであっても、常に付加的なタイルを含ませるようにすることを条件として、低精度の、即ち安価に実現できる数学的処理を使用できることは明白であろう。詳述すれば、低精度の方法によって計算されるタイルのセットは、正確なタイルのセットのスーパーセットでなければならない。

本発明の第１の実施の形態として、低精度計算を安全に使用する方法及び装置が提供される。更に、システムは、冗長タイルが益々付加される可能性と、数学的処理の精度、即ち実現費用とをトレードオフさせるように調整することができる。システムは、全てのエッジ／タイルに対して一貫したテスト手順を使用する利点をも有している。

本発明の第２の実施の形態において、我々は、特別な特性を利用する線分プリミティブを直接タイリングする方法が望ましいことも理解している。提唱する方法は、プリミティブを１つまたは複数の同等多角形に変換するよりも安価である。

第３の実施の形態において、本発明は、画像に影響しないことが保証されている若干の‘小さい’プリミティブを拒絶する手段を提供する。

以下に、図３を参照して本発明の好ましい実施の形態を説明する。第１のステップとして、好ましくは三角形であるプリミティブを入力する（ステップ１４）。

この三角形は、IEEE、32ビット、浮動小数点座標を使用して指定されている頂点｛（ｘ₀，ｙ₀），（ｘ₁，ｙ₁），（ｘ₂，ｙ₂）｝を有している。GB2343603特許と同様に、このプリミティブのバウンディングボックスは、投影されたＸ及びＹの両座標値の最大値及び最小値を計算することによって識別される（ステップ１５）。即ち、
ｐ_{x min}＝min（ｘ₀，ｘ₁，ｘ₂）
ｐ_{x max}＝max（ｘ₀，ｘ₁，ｘ₂）
ｐ_{y min}＝min（ｙ₀，ｙ₁，ｙ₂）
ｐ_{y max}＝max（ｙ₀，ｙ₁，ｙ₂）

これらの最大値及び最小値は、これが比較的安価な演算であるので、完全精度で決定される。最適化として、頂点位置の等しさをテストし、頂点位置が反復される三角形を拒絶する（これらの面積が正確に０であり、画像には貢献しないであろうから）ことも可能である。この点において、本発明は単純に完全に‘オフ・スクリーン’であるプリミティブを拒絶することもできる。

計算されたバウンディングボックス及びプリミティブの座標を使用して、小プリミティブ淘汰テストが遂行される（ステップ１６：これの詳細に関しては後述する）。もしそのプリミティブが画像に影響しないと考えられれば、それは破棄され（ステップ１７）、そうでなければそれは‘タイル’される、即ち関連タイルリスト内に配置される（ステップ１８）。以下に、先ず三角形プリミティブのタイリングプロセス（ステップ１８）の詳細を、幅広線の処理への延長と共に説明する。その後に、小オブジェクト淘汰ステップ（ステップ１６）に関して説明する。

我々の英国特許第2343603号は、（凸多角形）プリミティブのエッジを、どのようにして形の線（または平面方程式）として表すことができるかを記述している。
Ａx＋Ｂy＋Ｃ＝０
但し、Ａ、Ｂ、及びＣは、特定のエッジの位置及び向きに依存する係数であり、ｘ及びｙは画像座標である。画像面内の点（ｘ，ｙ）は、全てのエッジｉについて
Ａ_ix＋Ｂ_iy＋Ｃ_i＞０
の時に‘時計方向’プリミティブの厳密に内側にあると定義される。若干の環境の下（例えば、コンピュータグラフィックス標準OpenGLに記載されているフィルルール）では、若干のエッジは、プリミティブの内側にあるとしても含まれる。タイリングの目的から、システムが保存性であることを提供できる場合には、全てのエッジをプリミティブの部分であると考えることができ、従って‘時計方向’プリミティブに対する内側テストは、
∀i，Ａ_ix＋Ｂ_iy＋Ｃ_i≧０
に緩和される。

‘反時計方向’プリミティブには、‘≦’テストを使用すべきである。簡単に言えば、本明細書においては、時計方向の場合だけを記述する。それは、当分野に精通していれば、他の場合への拡張は明白だからである。

投影された三角形について、GB 2343603特許はエッジテストのための係数を計算するための方程式をも与えている。即ち、もし（ｘ_i，ｙ_i）及び（ｘ_i+1，ｙ_i+1）があるエッジｉの端点であれば、
Ａ_i＝ｙ_i−ｙ_i+1
Ｂ_i＝ｘ_i+1−ｘ_i
Ｃ_i＝ｘ_iｙ_i+1−ｘ_i+1ｙ_i

これらの方程式は、三角形頂点の投影された座標を含む３×３行列の随伴から実際に導出される。若干の状況においては、頂点を投影することなく、即ち、斉次座標を使用して三角形の（投影された）エッジを計算することが好ましい。その状況においては、エッジ方程式は対応する随伴行列を使用して計算することもでき、また代替実施の形態においては、タイリング演算は斉次座標を使用して遂行することができる。簡易化のために、この代替実施の形態は説明しないが、当業者にはその適応は明白であろう。

以下に、図４を参照して、好ましい実施の形態のステップ１８内に含まれる処理ステップの概要を説明する。

画像面の大きさまでに制限されている候補タイルの最初の矩形領域が、プリミティブの先端から決定される（ステップ２２）。

好ましい実施の形態における最適化として、候補タイルのセットが単一のタイル高、及び／または単一のタイル幅である場合（ステップ２３）、全てのタイルが必要であろうからバウンディングボックスを直接使用することができる（ステップ２４）。

次のステップは、エッジ方程式のパラメータを計算することである（ステップ２５）。この処理ステップは、先行システムのそれとは異なっており、短く説明することにする。

プロセスは、タイルの候補セットを通して繰り返し（ステップ２６）、各候補を各エッジに対してテストする（ステップ２７）ことによって続行される。全てのエッジテストに‘合格’した場合だけ、プリミティブはそのタイルのリスト内に含まれる。本発明に使用されるエッジテストも、GB2343603特許に記述されているより簡単である。代替実施の形態においては、システムは、バイナリチョップのような候補タイルを処理するための代替順序を使用することができ、これはそれらの近傍の結果に基づいて若干のタイルを排除する。

ステップ２５において遂行されるエッジ方程式の計算を理解するために、図５を参照されたい。所与の候補タイル３０について、各プリミティブのエッジを考えなければならない。この例においては、エッジ３１がタイルを横切っている。陰影付きの領域３２は、プリミティブの内側の領域の部分を表している。GB2343603特許に記載されているように、この特定のエッジに対してコーナー３３において内側テストを遂行すると、この特定のエッジについて正しい結果が得られるが、エッジ毎にサンプル点を選択しなければならないのは不便である。その代わりとして、一貫したサンプリング位置を使用することが好ましい。好ましい実施の形態においては、これは左上隅３４に選択される。実際のエッジ方程式は、これを行うことを可能にするために、若干調整される。

各エッジは独立的に計算されるが、以下、これに関して説明する。我々は、オリジナルの完全浮動小数点精度でエッジｉの端点（定義の順番に）を、

であると定義する。但し、０≦ｉ≦２、及びｊ＝（ｉ＋１）mod３である。これらのデータ値の２つの比較

が遂行され、以下の擬似コード内に記載されているように使用される。当業者ならば、この擬似コードをハードウェアまたはソフトウェアの何れかで実現することができよう。

OrientationTypes={TopLeft, TopRight, BottomLeft, BottomRight};

OrientationTypes Mode;

BOOL XjGTE, YjGTE;

// Compare the coordinate values
XjGTE := (xj >= xi);
YjGTE := (yj >= Yi);

// Determine edge orientation
IF (XjGTE AND NOT YjGTE)

{
Mode : = TopLeft;
}
ELSE IF (XjGTE AND YjGTE)
{
Mode : = TopRight;
}
ELSE IF (NOT XjGTE AND YjGTE)
{
Mode : = BottomRight;
}
ELSE
{
Mode := BottomLeft;
}

エッジの向きは、エッジ方程式に対してなされる調整を決定する。これは、以下の擬似コード内に記載されている‘シフト’量の計算を含む。また、Ｔ_x及びＴ_y値は、それぞれｘ及びｙ方向におけるタイルの寸法を表している。

IF ((Mode == ToTopLeft) OR (Mode == ToBottomLeft))
{
x shift = Tx;
}
ELSE
{
x shift = 0;
}
IF ((Mode == ToTopLeft) OR (Mode == ToTopRight))
{
y shift = Ty;
}
ELSE
{
y shift = 0;
}

このシフト量の背後の論理は、エッジの関数としてテスト点を移動させるのではなく、同一のテストコーナーを全てのエッジに関して使用することができるように各エッジがシフトすることである。当業者ならば直ぐ後に理解されるように、サイズが、例えば32×16のような正確な２の冪であるタイル寸法を選択することが好ましい。これは、より低いコストで実現できるからである。

このシフト値は、方程式Ｃ_i’＝ｘ₁ｙ₂−ｘ₂ｙ₁＋ｘ_shift・Ａ_i＋ｙ_shift・Ｂ_iに基づいて、エッジのための新しい係数Ｃ_iを計算するために使用される。しかしながら、この方程式は、完全精度数学的処理が使用されない限り、直接使用することはできない。その代わりとして、我々は、より低い精度で行うことができる‘安全’計算を使用する。

浮動小数点数学的処理を、少数の仮数ビットＭと共に使用する。これは、典型的には、８乃至22ビットであり、好ましい実施の形態では16ビットを使用する。

前述した不等式１、２、及び３から、浮動小数点数における誤差はそれらの大きさによって境界が画される。これらの大きさを直接使用することは不便であり、従って、この実施の形態は、誤差の境界を更に緩和することによってテストを簡易化する。従って、‘安全’エッジ方程式を計算する第１のステップとして、以下の不等式が遵守されるように端点から以下の値xmag_i及びymag_iを計算する。
２^xmag≧max（｜ｘ_j｜，｜ｘ_i｜，Ｔ_x）＞２^xmag-1
２^ymag≧max（｜ｙ_j｜，｜ｙ_i｜，Ｔ_y）＞２^ymag-1

当業者ならば、浮動小数点数に適用する時には、これが簡単な演算であることが理解されよう。

これらの値、及び方程式１、２、及び３の適用から、‘安全マージン’値fslopが計算される。即ち、
fslop_i＝１３*２^{xmag+ymag-(M+1)}

これもまた、浮動小数点指数を導出するために‘定数’仮数値（ユニット１３から導出）と、若干の単純な整数数学的処理とを含む浮動小数点においては簡単な演算である。

低精度数学的処理を使用する場合、エッジ方程式係数は次のように計算される。

（注：反時計方向プリミティブの場合、fslop値を最後の方程式において差し引くべきである。）

これらの値が各エッジ毎に計算された後に、システムは候補タイルのセットを通して繰り返すことができる（ステップ２６）。

ステップ２７において遂行される各タイル内の各エッジ毎の不等性テストは、幾つかの方法で行うことができる。１つの可能性は、

ここに、X及びYは候補タイルの左上コーナーの座標であるが、好ましい実施の形態は以下のものを使用する。

それは、（１）浮動小数点の大きさ比較の方が加算より僅かに安価であるからであり、そして（２）この公式化によって、候補タイルの行を通して繰り返す間、左側を一定に保持することができるからである。

好ましい実施の形態においては浮動小数点数学的処理を使用しているが、整数計算を使用するように若干の調整も実行可能である。

ステップ２６は、代替実施の形態において、候補タイルを通して‘ステッッピング’または‘繰り返し’として述べたが、幾つかの候補タイルを同時にテストすることができる。

好ましい実施の形態の拡張においては、幅広線分のための支援も設けられており、他の三角形／凸プリミティブのタイリングのために設けられている多くの機能を再使用することになろう。これらの線分は図６に示す形状であることが好ましく、４０で示されているように主に垂直であるもの、及び４１のような主に水平であるものの２つのクラスに大別される。これらは、中心軸の端点、即ち４２（ｘ₀，ｙ₀）及び４３（ｘ₁，ｙ₁）を定義することによって指定される。線分は、もし｜Δ_x｜＜｜Δ_y｜ならば‘主に垂直’形状であり、それ以外は‘主に水平’であると選択される。‘垂直’線分は既知の幅ｗ_x４４の水平線によってキャップされ、一方‘水平’線は別の既知の幅ｗ_y４５の垂直区分によって閉じられている。

三角形プリミティブと同様に、最初のステップは、候補タイルのバウンディングボックスを計算することである。好ましい実施の形態は、費用節約の目的から完全精度数学的処理の使用を回避しているから、特定の線分がどのクラスに入るのかを100％の確実性をもって知ることはできない。この理由から、バウンディングボックス計算は、線分が水平または垂直の何れかの端を有し得ることを仮定する。前述したように、システムは端点の最小値及び最大値を安価に計算することができる。好ましい実施の形態の場合、線分上のバウンディングボックスは、

であるとセットされる。

次いで、これは候補タイルのセットを決定し、前述したようにステップ２２、２３、及び２４を適用する。

エッジのテストに関して、端キャップがバウンディングボックスの一部として効果的にテストされるので、本発明は中心軸に対して平行な２つのエッジを考えるだけでよい。これらをエッジ０及びエッジ１と呼ぶ。エッジ０のａ及びｂ値の計算は、前述したように行われる。

エッジ０のＣ係数

の計算は次のように進行する。前述したように、エッジの向きが決定され、次いで以下の方法を使用してシフト量が計算される。

IF ((Mode==ToTopLeft) OR (Mode==ToBottomLeft))
{
x shift = (Tx + w x/2);
}
ELSE
{
x shift = (− w x/2);
}
IF((Mode==ToTopLeft) OR (Mode==ToTopRight))
{
y shift = (Ty + w y/2);
}
ELSE
{
y shift = (− w y/2);
}

のための計算の残余は、前述したものと正確に同一である。即ち

但し、ｉ＝０、ｊ＝１である。

エッジ１については、その‘ａ’及び‘ｂ’値は単にエッジ０の値の負の値であるが、そのｃ係数は上述した手順を使用して計算される。

次に、好ましい実施の形態のユニット１６において遂行されるステップ、即ち小さいプリミティブ（これらはレンダラーによってサンプルされないので、タイリング中に拒絶され得る）のテストを説明する。これは三角形に関して説明するが、この面は線分プリミティブにも適用することができる。しかしながら、その適用は当業者には明白であろうから、簡易化のために詳細な説明は省略する。同様に、他の‘淘汰’する型を支援するための変更も明白であるので、以下 ‘時計方向’プリミティブだけに関してだけ説明する。実施の形態は、画素の左上コーナーに位置する画素サンプリング点を使用する。画素の中心を選択するような他の可能性も、プリミティブをオフセットさせることによって達成することができる。

図１０を参照して説明する。ステップ２１において計算されたプリミティブの最大値及び最小値を使用して、システムは４つの画素サンプリング点のセット、即ち｛Ｓ₀₀，Ｓ₀₁，Ｓ₁₀，Ｓ₁₁｝を以下のように決定する（ステップ８０）。

ここに、

は標準‘フロア’及び‘シーリング’演算子である。例えば、図７にはＳ₀₀及びＳ₁₀がそれぞれ５５及び５６で示されており、一方図９にはそれらはそれぞれ７３及び７１で示されている。バウンディングボックスの相対サイズ及び‘フロア’及び‘シーリング’の挙動の故に、これらの位置が交換されているように見えることに注目されたい。

ステップ８１において、プリミティブのバウンディングボックスが全てのサンプリング点をミスしているか否かを見る（即ち、平凡な場合のテスト）ためにテストされる。その例が図７に示されている。もし含んでいなければ、そのプリミティブは淘汰される（ステップ８２）。ステップ８１におけるテストは、次のように要約することができる。
IF (S_xmin＞S_xmax OR S_ymin＞S_ymax) THEN CULL
しかしながら、このテストは図８及び９に示す例を淘汰しない。

あるサイズより大きいプリミティブを考えることは費用有効ではないので、好ましい実施の形態は、それらの選択されたサンプリング位置が１×１画素領域より更に広がらないプリミティブに対するその小オブジェクト淘汰テストを制限する。ステップ８３は、この条件に関してテストし、もしそのプリミティブが大き過ぎると考えられれば、それは淘汰のためのテストを受けない（ステップ８４）。ステップ８３において遂行されるテストは、
IF ((S_xmax−S_xmin)＞1) OR (S_ymax−S_ymin)＞1) THEN KEEP
である。

次いで、本発明は、４つのサンプリング点の各々を、それらがプリミティブの内側にあるか否かを見るためにテストする。前述したように、エッジ係数が先に指定されたエッジ方程式を使用して計算される（ステップ８５）。しかしながら、この状況においては数の範囲が小さいので、計算は固定小数点数学的処理を使用して極めて安価に‘高精度’で行われる。

多くとも３つの可能な場合、即ち、１つの明確なサンプリング点、２つの明確なサンプリング点（図８に６１及び６２で示されているような）、または４つの明確なサンプリング点（図９に７１、７２、７３、及び７４で示されているような）が考えられることに注目されたい。

好ましい実施の形態においては、４つの明確なサンプリング位置を有する状況における１つのエッジのための４つのテスト不等式が

であることに注目することによって、各エッジに対して４つまでのサンプル位置を極めて安価にテストすることができる（ステップ８６）。

同一の基本的計算、即ちＡ_iＳ_xmin＋Ｂ_iＳ_ymin＋Ｃ_iが全てに使用され、次いでそれと｛０，−Ａ_i，−Ｂ_i，（−Ａ_i−Ｂ_i）｝とが比較されていることは明白である。最悪の場合には４つのサンプリング点が必要であり、またプリミティブの外側のサンプリングは害にはならないから、この実施の形態は、簡易化のために、真に関心のあるサンプリング点の数には無関係に上述した条件の全てをテストする。

もし何れかのエッジがそのテストに失敗すれば、そのサンプル点はプリミティブの外側にあると見做される。ステップ８７において、もし全てのサンプル位置がプリミティブの外側にあればそのプリミティブは淘汰され（ステップ８２）、それ以外の場合にはそのプリミティブは保持される（ステップ８４）。

代替実施の形態においては、２×２より大きいサンプリング格子を使用することができる。

画像面上に投影された三角形プリミティブ、及びそのプリミティブによって影響される最小タイルセットを示す図である。 １つのタイルがプリミティブによって影響された単一の画素だけを含むような、４つのタイルの領域及び１つのプリミティブエッジの‘クローズアップ’図である。 本発明を使用して１つのプリミティブを‘タイル’するか否かを決定する場合に遂行される、及びどのように‘タイル’するかを示すフロー図である。 タイリングを拒絶されなかったプリミティブをタイリングするために遂行されるステップを示すフロー図である。 GB2343603特許に記載されているエッジの‘安全な’テスト点を有するプリミティブによって部分的にカバーされているタイル、及び本発明の実施の形態における好ましいサンプリング位置を示す図である。 好ましい線分プリミティブの形状及び向きを示す図である。 もしレンダラーへ引渡されれば見ることはできないが、簡単なバウンディングボックステストを使用すれば拒絶、または淘汰することができる小さいプリミティブの例を示す図である。 これも見ることはできないが、単純にバウンディングボックスを使用しても淘汰することができない小さいプリミティブの例を示す図である。 これもまた見ることはできないが、単純にバウンディングボックスを使用しても淘汰することができない小さいプリミティブの例を示す図である。 小さい多角形を淘汰することができるか否かをテストするのに使用される諸ステップを示すフロー図である。

Claims (6)

1. 三次元コンピュータグラフィックス画像をシェーディングするシステムにおいて小さいオブジェクトを淘汰する装置によって実行される方法であって、
   画像が見られるディスプレイを、複数の矩形領域に細分するステップと、
   各矩形領域毎に、前記矩形領域内において可視であることができる前記画像内のオブジェクトのリストを導出するステップと、
   前記オブジェクトのリストを使用して、ディスプレイのために前記矩形領域をどのようにシェーディングすべきかを決定するステップと、
   を含み、
   前記オブジェクトのリストを導出するステップが、
   各オブジェクト毎に、Ｘ及びＹ方向の最大値及び最小値を決定するステップと、
   前記画像内の各オブジェクト毎に、該オブジェクトのＸ座標及びＹ座標の最大値及び最小値からバウンディングボックスを決定するステップと、
   前記最大値及び最小値から、１組のピクセルサンプリング点を決定するステップと、
   前記オブジェクトを取り囲むバウンディングボックスが、前記ピクセルサンプリング点の何れかをカバーしているか否かを決定するステップと、
   前記バウンディングボックスが前記ピクセルサンプリング点をすべて欠いている場合に前記オブジェクトを淘汰するステップと、
   前記オブジェクトの各エッジに対して各サンプリング点をテストするステップと、
   実行された前記テストから前記オブジェクトが何れかのピクセルサンプリング点をカバーしているか否かを決定するステップと、
   前記決定の結果に依存して、前記オブジェクトを前記リストへ付加、または前記リストから拒絶するステップと、
   を含むことを特徴とする方法。
2. 前記サンプリング点が１×１ピクセルより大きく広がっているか否かを決定するステップと、
   前記サンプリング点がこの制限を超えている場合に淘汰に関して前記オブジェクトをテストしないステップと、
   を含む、請求項１に記載の方法。
3. 各オブジェクト毎に、前記オブジェクトを矩形領域のためのリストに付加すべきか否かを決定するときに、前記オブジェクトのバウンディングボックス内に少なくとも部分的に入る矩形領域だけを選択するステップ、
   を含む請求項１又は請求項２に記載の方法。
4. 三次元コンピュータグラフィックス画像をシェーディングするシステムにおいて小さいオブジェクトを淘汰する装置であって、
   画像が見られるディスプレイを、複数の矩形領域に細分する手段と、
   各矩形領域毎に、前記矩形領域内に可視であることができる前記画像内のオブジェクトのリストを導出する手段と、
   前記オブジェクトのリストを使用することによって、ディスプレイのために前記矩形領域をどのようにシェーディングすべきかを決定する手段と、
   を含み、
   前記オブジェクトのリストを導出する手段が、
   各オブジェクト毎に、Ｘ及びＹ方向の最大値及び最小値を決定する手段と、
   前記画像内の各オブジェクト毎に、前記Ｘ及びＹ方向の最大値及び最小値からバウンディングボックスを決定する手段と、
   前記最大値及び最小値から、１組のピクセルサンプリング点を決定する手段と、
   前記オブジェクトを取り囲むバウンディングボックスが、前記ピクセルサンプリング点の何れかをカバーしているか否かを決定する手段と、
   前記バウンディングボックスが前記ピクセルサンプリング点をすべて欠いている場合に前記オブジェクトを淘汰する手段と、
   前記オブジェクトの各エッジに対して各サンプリング点をテストする手段と、
   該テストする手段により実行されたテストから前記オブジェクトが何れかのサンプリング点をカバーしているか否かを決定する手段と、
   前記決定の結果に依存して、前記オブジェクトを前記リストへ付加、または前記リストから拒絶する手段と、
   を含むことを特徴とする装置。
5. 前記サンプリング点が前記Ｘ及びＹ方向における１×１ピクセルより大きく広がっているか否かを決定し、前記サンプリング点がこの制限を超えている場合に淘汰に関して前記オブジェクトをテストしない手段、を含む請求項４に記載の装置。
6. 各オブジェクト毎に、前記オブジェクトを矩形領域のためのリストに付加すべきか否かを決定するときに、前記バウンディングボックス内に少なくとも部分的に入る矩形領域だけを選択する手段、を含む請求項４又は請求項５に記載の装置。

Images