(57)【要約】      （修正有）【課題】階層だてられているタイル状構造に基づくラスタライゼーションの方法を開示する。【解決手段】ラスタライゼーションのアルゴリズムは、階層だてられた矩形もしくは区画におけるピクセルをラスタライズする。その方法は、複数のピクセルのタイルを追跡し、各タイルが有効であるどうかを判定するステップと、各有効なタイルを複数のサブタイルに分け、各サブタイルが有効であるどうかを判定するステップと、各有効なサブタイルを複数の四分の１のタイル（クワッド）に分け、各クワッドが有効であるどうかを判定するステップと、各有効なクワッドのピクセルを描画するステップと、を含む。これらの階層レベルの区画の有効性評価を並列で行う。【選択図】図１
2008117384.tif 000002
【特許請求の範囲】
【請求項１】
階層だてられた三角形のラスタライゼーション法において、
（ａ）複数のピクセルのタイルを追跡し、前記各タイルが有効であるかどうかを判定するステップと、
（ｂ）前記各有効なタイルを複数のサブタイルに分割し、前記各サブタイルが有効であるかどうかを判定するステップと、
（ｃ）前記各有効なサブタイルを複数のクワッドに分割し、前記各クワッドが有効であるかどうかを判定するステップと、
（ｄ）前記各有効なクワッドに対応するピクセルを描画するステップ、
とを含み、
ここでの前記ステップ（ａ）からステップ（ｄ）までを並列して行う、
ことを特徴とするラスタライゼーション法。
【請求項２】
前記分割ステップ（ｂ）が、
（ｂ１）前記各有効なタイルを前記複数のサブタイルに分割するステップと、
（ｂ２）前記複数のサブタイルを追跡するステップと、
（ｂ３）前記各サブタイルが有効であるかどうかを判定するステップと、
を含むことを特徴とする請求項１記載の方法。
【請求項３】
前記複数のサブタイルを追跡するステップが、前記複数のタイルを追跡する手段と同じ手法で行われる、
ことを特徴とする請求項２記載の方法。
【請求項４】
前記分割ステップ（ｃ）が、
（ｃ１）前記各有効なサブタイルを前記複数のクワッドに分割するステップと、
（ｃ２）前記複数のクワッドを追跡するステップと、
（ｃ３）前記各クワッドが有効であるかどうかを判定するステップと、
を含むことを特徴とする請求項１記載の方法。
【請求項５】
前記複数のクワッドを追跡する前記ステップが、前記複数のタイルを追跡する手法および前記複数のサブタイルを追跡する手法と同じ手法で行われる、
ことを特徴とする請求項４記載の方法。    
【請求項６】
タイルおよびサブタイルおよびクワッドを含む区画の有効性評価として、
エッジ方程式を用いることで、前記区画内のピクセルが、三角形の線の左右に存在するか、あるいは、線上にあるかどうかを確認するステップと、
三角形の３つの辺に接しているかどうかを前記区画の４つの頂点すべてについて確認し、組み合わせた結果を返すステップと、
前記組み合わせた結果に基づいて、前記区画が、前記三角形の内部にピクセルを含んでいるかどうかを判定するステップと、
前記区画が、前記三角形内部に少なくとも一つのピクセルを含んでいる場合に、前記区画を有効であると判定するステップと、
を含むことを特徴とする請求項１記載の方法。
【請求項７】
前記区画が、前記三角形内部に一つも有効なピクセルを含んでいない場合に、前記区画を放棄するステップ、
をさらに含むことを特徴とする請求項６記載の方法。
【請求項８】
階層だてられたラスタライゼーション法であって、
（ａ）多角形に対して開始点を入力するステップと、
（ｂ）前記多角形が線であるかもしくは三角形であるかを判定するステップと、
（ｃ）前記多角形が三角形ならば、
（ｃ１）複数のピクセルのタイルを追跡し、前記各タイルが有効であるかどうかを判定するステップと、
（ｃ２）前記各有効なタイルを複数のサブタイルに分割し、前記各サブタイルが有効であるかどうかを判定するステップと、
（ｃ３）前記各有効なサブタイルを複数のクワッドに分割し、前記各クワッドが有効であるかどうかを判定するステップと、
（ｃ４）前記各有効なクワッドに対応するピクセルを描画するステップと、
を含み、ここでの前記ステップ（ｃ１）からステップ（ｃ４）までを並列して行う、階層的手法で前記三角形をラスタライズするステップと、
を含むことを特徴とするラスタライゼーション法。
【請求項９】
前記分割ステップ（ｃ２）が、
（ｃ２i）前記各有効なタイルを前記複数のサブタイルに分割するステップと、
（ｃ２ii）前記複数のサブタイルを追跡するステップと、
（ｃ２iii）前記各サブタイルが有効であるかどうかを判定するステップと、
を含むことを特徴とする請求項８記載の方法。
【請求項１０】
前記複数のサブタイルを追跡するステップが、前記複数のピクセルのタイルを追跡する手法と同じ手法で行われる、
ことを特徴とする請求項９記載の方法。
【請求項１１】
前記分割ステップ（ｃ３）が、
（ｃ３i）前記各有効なサブタイルを前記複数のクワッドに分割するステップと、
（ｃ３ii）前記複数のクワッドを追跡するステップと、
（ｃ３iii）前記各クワッドが有効であるかどうかを判定するステップと、
を含むことを特徴とする請求項８記載の方法。
【請求項１２】
前記複数のクワッドを追跡するステップが、前記複数のタイルを追跡する手法および前記複数のサブタイルを追跡する手法と同じ手法で行われる、
ことを特徴とする請求項１１記載の方法。
【請求項１３】
タイルおよびサブタイルおよびクワッドを含む区画の有効性評価として、
エッジ方程式を用いることで、前記区画のピクセルが三角形の線の左右に存在するか、あるいは、線上にあるかどうかを確認するステップと、
三角形の３つの辺に接しているかどうかを前記区画の４つの頂点のすべてについて確認し、組み合わせた結果を返すステップと、
前記組み合わせた結果に基づいて、前記区画が前記三角形内部にピクセルを含んでいるかどうかを判定するステップと、
前記区画が、前記三角形内部に少なくとも一つの有効なピクセルを含んでいる場合に、前記区画を有効であると判定するステップと、
を含むことを特徴とする請求項８記載の方法。
【請求項１４】
前記区画が、前記三角形内部に一つも有効なピクセルを含んでいない場合に、前記区画を放棄するステップ、
をさらに含むことを特徴とする請求項１３記載の方法。
【請求項１５】
（ｄ）前記多角形が線であるならば、前記線のピクセルの各クワッドに対応するピクセ
ルを処理するステップと、
（ｅ）前記各有効なクワッドのピクセルを描画するステップと、
をさらに含むことを特徴とする請求項８記載の方法。
【請求項１６】
階層だてられた三角形のラスタライゼーション法における区画のピクセルの有効性評価のための方法として、
（ａ）エッジ方程式を用いることで、前記区画のピクセルが三角形の線の左右に存在するか、あるいは、線上にあるかどうかを確認するステップと、
（ｂ）三角形の３つの辺に接しているかどうかを前記区画の４つの頂点のすべてについて確認し、組み合わせた結果を返すステップと、
（ｃ）前記組み合わせた結果に基づいて、前記区画が前記三角形内部にピクセルを含んでいるかどうかを判定するステップと、
（ｄ）前記区画が、前記三角形内部に少なくとも一つのピクセルを含んでいる場合に、前記区画を有効であると判定するステップと、
を含むことを特徴とする方法。
【請求項１７】
（ｅ）前記区画が、前記三角形内部に一つもピクセルを含んでいない場合に、前記区画を放棄するステップ、
をさらに含むことを特徴とする請求項１６記載の方法。
【請求項１８】
前記ステップ（a）からステップ（ｄ）までを、複数のピクセルのタイル、複数のサブ
タイル、および複数のクワッドを有効とするために行い、
有効なタイルを前記複数のサブタイルに分割し、
有効なサブタイルを前記複数のクワッドに分割し、
前記複数のタイル、前記複数のサブタイル、前記複数のクワッドの前記有効性評価を並行して行う、
ことを特徴とする請求項１６記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ラスタライゼーションのアルゴリズムに関し、特に階層的タイル状構造に基づくラスタライゼーションのアルゴリズムに関する。
【背景技術】
【０００２】
ラスタライゼーションのアルゴリズムに基づく方程式は、公知な技術である。その一つとして、３次元のＺバッファ法を用いた画像を実現するための多角形のラスタライゼーションに関する並列アルゴリズム(parallel algorithm)がある。このアルゴリズムでは、輪郭の一方の側においてはゼロよりも大きな値を有し、なおかつ、輪郭の反対側においてはゼロよりも小さい値を有する線形エッジ関数を使って、多角形の各辺を表現している。色およびＺピクセル値を補間するために必要とされるハードウェアと同様のハードウェアを用いて、その関数の値を補間することができる。さらに、隣接するピクセルのエッジ関数を並列処理することもできる。しかしながら、このアルゴリズムには、最適化および好適なハードウェアの実装が不足しているという欠点がある。また、線をラスタライズすることができないという欠点もある。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上記を鑑みて、ラスタライゼーションのアルゴリズムに基づく方程式を改良する必要がある。本発明は、このような要求に応えるものである。
【課題を解決するための手段】
【０００４】
本発明に準ずるアルゴリズムは、性能および局所性をともに最適にする階層的タイル状構造に基づくアルゴリズムである。また、線のラスタライゼーションもできる。
【０００５】
階層だてられているタイル状構造に基づくラスタライゼーションの方法を開示する。本発明のラスタライゼーションアルゴリズムは、階層だてられた矩形もしくは区画内のピクセルをラスタライズする。その方法は、複数のピクセルのタイルを追跡し、各タイルが有効であるどうかを判定するステップと、各有効なタイルを複数のサブタイルに分け、各サブタイルが有効であるどうかを判定するステップと、各有効なサブタイルを複数の４分の１のタイル（クワッド）に分け、各クワッドが有効であるどうかを判定するステップと、各有効なクワッドのピクセルを描画するステップと、を含む。これらの階層レベルの区画の有効性評価を並列で行う。本発明のラスタライゼーションのアルゴリズムは、さらにハードウェア内に実装して、高性能が得られるようにする。
【発明を実施するための最良の形態】
【０００６】
本発明のラスタライゼーションのアルゴリズムは、階層だてられた多角形もしくは区画内のピクセルをラスタライズする。その階層の各区画が有効とされたときは、有効性に対応する次のレベルへパイプを介して（階層を下げるように）送り、最小のレベルに達するまで繰り返す。最小のレベルの区画が有効である場合は、そのピクセルを描画する。それらの階層レベルの区画の有効性判定は、並列して行われる。本発明のラスタライゼーションのアルゴリズムは、さらにハードウェア内に実装して、高性能が得られるようにする。
【０００７】
また、本発明のラスタライゼーションのアルゴリズムは、メモリ内で局在化されており、パイプの後段でピクセルをシェーディングするときに、良好なメモリ特性を有することになり、高頻度でキャッシュヒットができる。このアルゴリズムは、全体的なピクセル処理量を高めることができ、これによって、従来の輪郭追跡アルゴリズムやメモリ内に局在
化されていないアルゴリズムよりも速く多角形を描画できる。
【０００８】
図１は、本発明に準ずるラスタライゼーションのアルゴリズムの実施態様を示している。まず、多角形の開始点を設定エンジンでラスタライザーに入力する（ステップ１０１）。その開始点は、三角形の内部もしくは線上にとる。そのラスタライザーは、その多角形が線であるか三角形であるかどうかを判定する（ステップ１０２）。線の場合、そのラスタライザーは、その線に対しての各最小レベルの区画におけるピクセルを処理する（ステップ１０３）。三角形の場合、そのラスタライザーは、最小レベルの区画に到達するまでの階層段階における各レベルの区画を「追跡する（walks）」（ステップ１０４）。さらに下記で、区画の追跡について記載する。最小レベルの区画が決定されると、補間を行うために、この最小レベルの区画を出力区画へと送信する（ステップ１０５）。その後、本ラスタライゼーションのアルゴリズムを次の多角形に対して繰り返す。
【０００９】
一つの実施の形態として、本ラスタライゼーションのアルゴリズムに３レベルの階層を用いる。図２に示しているように、最高階層の区画もしくは「タイル」２０１は、８×８ピクセルの矩形である。そして、第二位の階層の区画内で、有効であるならばタイル２０１を、４つの４×４ピクセルの「サブタイル」２０２へと分割する。さらに、第三位の階層の区画内で、有効であるならば各サブタイル２０２を、４つの２×２ピクセルの「クワッド」２０３に分割する。それから、各有効なクワッドを描画する。当業者は、本発明の内容および範囲を超えることなく、任意の階層レベルの数や型を用いることができることを理解できる。
【００１０】
ラスタライザーがタイルを追跡するときには、ラスタライザーは同様の方式にのっとりタイルの各水平線を追跡する。図３は、三角形とタイルの例を示している。一つの実施形態として、まず、ラスタライザーは、三角形の外縁もしくは範囲指定枠（clipping window）に到達するまで一方向に追跡をする。それから、ラスタライザーは、開始点から他の
方向へ、三角形の外縁もしくは範囲指定枠に到達するまで追跡する。その後、ラスタライザーは開始点の位置によって定まる上方向もしくは下方向のどちらかへと、タイルの次の線にむけて、ラスタライザーが中断した箇所から進む。
【００１１】
もし開始点が三角形のほぼ中央にあるならば、まず、三角形の外縁もしくは範囲指定枠に到達するまで上方向に進む。それから、ラスタライザーは、その開始点から下方向に進む。
【００１２】
図４は、発明に準ずるラスタライゼーションのアルゴリズムとともに用いられる有効性評価アルゴリズムの実施態様を示している。その有効性評価アルゴリズムは、区画（タイル、サブタイル、もしくはクワッド）が、三角形内部にピクセルが含まれているかどうかを判定する。まず、そのラスタライザーは、エッジ方程式を用いることで、ピクセルが三角形の線の左右に存在するか、または線上にあるかどうかを確認する（ステップ４０１）。
【００１３】
E(x,y)=(x-Xinit)*dY-(y-Yinit)*dX
【００１４】
三角形の３つの辺に接しているかどうかを区画の４つの頂点すべてについて確認し、４つの頂点すべてについて確認した結果を組み合わせる（ステップ４０２）。それから、区画が三角形内部のいくつかのピクセルを含んでいるかどうかを判定する。もしそうであれば、すなわち、その区画が有効ならば、さらに進んだ描画をするために区画の階層を下げ
る（ステップ４０４）。もしそうでなければ、すなわち、その区画が有効でなければ、その区画を放棄する（ステップ４０５）。
【００１５】
一つの実施形態として、区画の各辺において３つのエッジ方程式を用いる。多重送信手段を用いることで、各サイクルにおいて、その三角形に対して確認された区画全体の状態を処理する。すぐにこの処理された情報を用いて、ラスタライザーは、現在の区画の左右にまだ有効な区画があるかどうかも判定する。これは、ラスタライザーがどの方向にむけて（追跡を）続ければよいかを判定する援けとなる。
【００１６】
図５は、本発明に準ずる階層だてられた三角形のラスタライゼーションのアルゴリズムの実施態様を示している。まず、ラスタライザーは、上述のようにタイルを追跡する（ステップ５０１）。そのラスタライザーは、図４で説明した有効性評価アルゴリズムを用いてタイルが有効かどうかを判定する。もしタイルが有効でなければ、それを放棄する。もし、タイルが有効であれば、それを階層の次のレベルに下げ、タイルをサブタイルに分割する（ステップ５０２）。それから、ラスタライザーは、そのサブタイルを追跡し（ステップ５０３）、図４で説明した有効性評価アルゴリズムを用いて（サブタイルが）有効かどうかを判定する。有効でないサブタイルは、放棄される。有効なサブタイルは、階層の次のレベルに下げられ、サブタイルがクワッドに分割される（ステップ５０４）。その後、ラスタライザーは、そのクワッドを追跡し（ステップ５０５）、図４で説明した有効性評価アルゴリズムを用いて（クワッドが）有効かどうかを判定する。有効でないクワッドは、放棄される。有効なクワッドは、描画される（ステップ５０６）。
【００１７】
上記の実施形態において、有効なタイルが次のレベルに下げられて、ステップ５０２〜５０３が行われる際に、ラスタライザーは、次のタイルを追跡し、そのタイルの処理に進む。有効なサブタイルが次のレベルに下げられて、ステップ５０４〜５０５が行われる際に、ラスタライザーは、次のサブタイルを追跡し、そのサブタイルの処理に進む。有効なクワッドが処理され、ステップ５０６で描画される際に、ラスタライザーは、次のクワッドを追跡し、クワッドの処理に進む。このように、階層のレベル内のタイル、サブタイル、クワッドのラスタライゼーションは、並列して行われる。一つのレベル内の各区画のラスタライゼーションも並列して行われる。したがって、本発明のラスタライゼーションアルゴリズムは最適化される。さらに、本アルゴリズムをさらに最適化するために、ラスタライザーはタイル、サブタイル、およびクワッドの追跡を同一の方法で行い、メモリコヒレンシーを維持するようにする。
【００１８】
一つの実施形態として、本ラスタライゼーションのアルゴリズムは、２つの隣接しあうピクセルの深さの値が一サイクルで処理される、特別な二重深さモード（double-depth mode）も支持する。これによって、２×２ピクセルのクワッドは、２サイクルの処理をす
るだけでよく、他方、このモードではない場合には、（各ピクセルに対して１サイクルの）４サイクルの処理が必要とされる。これにより、ビデオゲームなどのアプリケーションで、より速く深さバッファを描画することが可能となり、その結果、描画の第２段階において、有効である（すなわち、深さの値が深さバッファに一致する）ピクセルのみを、処理するピクセルとして階層を下げる。これはゲームの性能全般を向上させる。一般に、二重深さモード（double-depth mode）において、描画性能は、一般的な描画モードの２倍
から４倍になる。
【００１９】
図面と文面によって前述の本発明の実施態様を示している。それらは、記載どおりに本発明を限定することを意図するものではない。特に、本明細書中で記載した発明の機能的な実現は、ハードウェア、ソフトウェア、ファームウェア、および／もしくは他の使用可能な機能的な構成物あるいは設計してあるブロック、ならびに、有線ネットワーク、無線ネットワーク、もしくは有線および無線の組み合わせであるネットワーク内で同様に実現
されることを意図している。他の変形例や実施態様は、上述で開示している範囲内で可能であり、したがって、本発明の権利範囲は本明細書の詳細な記載によって限定されず、下記の請求項によって定められることを意図している。
【図面の簡単な説明】
【００２０】
【図１】図１は、本発明に準ずるラスタライゼーションのアルゴリズムの実施態様を示している。
【図２】図２は、本発明に準ずるラスタライゼーションのアルゴリズムに使用される３レベルの階層構造の実施態様を示している。
【図３】図３は、三角形とタイルの例を示している。
【図４】図４は、本発明に準ずるラスタライゼーションのアルゴリズムとともに用いられる有効性評価アルゴリズムの実施態様を示している。
【図５】図５は、本発明に準ずる階層だてられた三角形のラスタライゼーションのアルゴリズムの実施態様を示している。
【図１】
2008117384.tif 000003
【図２】
2008117384.tif 000004
【図３】
2008117384.tif 000005
【図４】
2008117384.tif 000006
【図５】
2008117384.tif 000007
【外国語明細書】
2008117384.tif 000008
2008117384.tif 000009
2008117384.tif 000010
2008117384.tif 000011
2008117384.tif 000012
2008117384.tif 000013
2008117384.tif 000014
2008117384.tif 000015
2008117384.tif 000016
2008117384.tif 000017
2008117384.tif 000018
2008117384.tif 000019
【図１】
2008117384.tif 000020
【図２】
2008117384.tif 000021
【図３】
2008117384.tif 000022
【図４】
2008117384.tif 000023
【図５】
2008117384.tif 000024