(57)【特許請求の範囲】
【請求項１】
三次元コンピュータグラフィック画像をレンダリングするための方法において、
コンピュータが、
画像を複数の長方形タイルへと細分化する段階と、
複数レベルの次第に大きくなるタイルグループより成るマルチレベル構造に前記タイルを配列する段階と、
レンダリングされるべき画像データを、画像をレンダリングするのに必要な画像データを含む複数のプリミティブブロックへと分割する段階と、
各プリミティブブロックを、それが交差するタイルグループに基づいて前記マルチレベル構造内のタイルグループに指定して、各プリミティブブロックが前記マルチレベル構造内の１つのレベルのグループに指定されるようにする段階と、
画像をレンダリングするための制御ストリームデータリストを導出する段階であって、タイルの各グループに対する前記制御ストリームデータリストは、そのグループに指定されたプリミティブブロックに対応する前記マルチレベル構造の各レベル内のタイルのそのグループに対してプリミティブブロックへのリファレンスを含むものである段階と、
前記制御ストリームデータリストを使用して、プリミティブデータを表示のためにタイルグループ内のタイルへとレンダリングする段階と、
を実行することを備えた方法。
【請求項２】
前記制御ストリームデータは、タイルブロック制御ワードを含み、更に、前記コンピュータが、そのタイルブロック制御ワードの状態に対して各タイルブロックのレンダリングの際にプリミティブブロックを処理すべきかどうか決定する段階を更に備えた、請求項１に記載の方法。
【請求項３】
前記制御ストリームデータは、タイルブロック制御フォーマットワードを含み、これは、各プリミティブブロックをタイルブロックに対して処理すべきであると決定した後に、現在処理されているタイルに対してプリミティブブロックを処理すべきかどうか決定するのに使用される、請求項２に記載の方法。
【請求項４】
前記制御ストリームデータは、その制御ストリームデータにフルプリミティブマスクが存在するかどうか決定するためのフルプリミティブマスクフラグ存在ビットを含み、前記フルプリミティブマスクは、タイルブロック内の各タイルに対して、プリミティブブロック内の全てのプリミティブが各タイルにおいて見えるかどうか決定するビットを得るために使用される、請求項３に記載の方法。
【請求項５】
前記制御ストリームデータは、前記フルプリミティブマスクフラグ存在ビットがセットされないときにタイルブロック内のどのタイルがフルプリミティブマスクを有するか決定するのに使用されるプリミティブマスクフォーワードワードを含む、請求項４に記載の方法。
【請求項６】
三次元コンピュータグラフィック画像をレンダリングするための装置において、
画像を複数の長方形タイルへと細分化する手段と、
複数レベルの次第に大きくなるタイルグループより成るマルチレベル構造に前記タイルを配列する手段と、
レンダリングされるべき画像データを、画像をレンダリングするのに必要な画像データを含む複数のプリミティブブロックへと分割する手段と、
各プリミティブブロックを、それが交差するタイルグループに基づいて前記マルチレベル構造内のタイルグループに指定して、各プリミティブブロックが前記マルチレベル構造内の１つのレベルのグループに指定されるようにする手段と、
画像をレンダリングするための制御ストリームデータリストを導出する手段であって、各グループに対する前記制御ストリームデータリストは、そのグループに指定されたプリミティブブロックに対応する前記マルチレベル構造の各レベル内のタイルグループに対してプリミティブブロックへのリファレンスを含むものである手段と、
前記制御ストリームデータリストを使用して、プリミティブデータを表示のためにタイルグループ内のタイルへとレンダリングする手段と、
を備えた装置。
【請求項７】
前記制御ストリームデータは、タイルブロック制御ワードを含み、更に、前記装置は、そのタイルブロック制御ワードの状態から、各タイルブロックのレンダリングの際にプリミティブブロックを処理すべきかどうか決定する手段を更に備えた、請求項６に記載の装置。
【請求項８】
前記制御ストリームデータは、タイルブロック制御フォーマットワードを含み、このタイルブロック制御フォーマットワードを使用して、各プリミティブをタイルブロックに対して処理する必要があると決定し、タイルブロック内で現在処理されているタイルに対してプリミティブブロックを処理すべきかどうか決定するための手段を更に備えた、請求項７に記載の装置。
【請求項９】
前記制御ストリームデータは、フルプリミティブマスクフラグ存在ビットを含み、そしてそのフルプリミティブマスクフラグ存在ビットから、フルプリミティブマスクビットが制御ストリームデータに存在するかどうか決定するための手段と、タイルブロック内の各タイルに対して、フルプリミティブマスクビットをセットして、プリミティブブロック内のフルプリミティブが各タイルにおいて見えるかどうか決定する手段とを備えた、請求項８に記載の装置。
【請求項１０】
前記制御ストリームデータは、プリミティブマスクフォーワードワードを含み、更に、そのプリミティブマスクフォーワードワードから、前記フルプリミティブマスクフラグ存在ビットがセットされないときにタイルブロック内のどのタイルがフルプリミティブマスクを有するか決定する手段を備えた、請求項９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元コンピュータグラフィックシステムに係り、より特定すれば、タイルベースレンダリングを使用するシステムに係る。
【背景技術】
【０００２】
処理能力が高まるにつれて、三次元のコンピュータ作成画像の複雑さも増加した。頂点及び三角形メッシュを使用する人間の動きのような非常に複雑な３Ｄ物体のコンピュータモデルは、作成が容易になった。この種の３Ｄモデルを３Ｄコンピュータグラフィックシステムへ送り、３Ｄアニメ画像をコンピュータスクリーン上に作成することができる。コンピュータ作成の３Ｄアニメ画像は、３Ｄコンピュータゲーム、ナビゲーションツール、及びコンピュータ支援型エンジニアリングデザインツールで広く使用されている。
【０００３】
３Ｄコンピュータグラフィックシステムは、益々複雑なグラフィックや益々高速な表示の需要に対処しなければならない。表示モデルの細部が増加するにつれて、益々多くのプリミティブ及び頂点が使用される。又、テクスチャ及びシェーディング技術が進歩するにつれて、益々多くの情報がプリミティブ及び頂点データに添付される。近代的なゲームでは、レンダリングに百万を越えるプリミティブが存在する。それ故、メモリの帯域巾は、コンピュータグラフィックシステムの性能に影響する非常に大きな要因となる。
【０００４】
タイルベースのレンダリングシステムが良く知られている。これは、画像を複数の長方形ブロック又はタイルへと細分化する。英国特許第ＧＢ２３４３６０３号及び国際特許出願第ＷＯ２００４／０８６３０９号に開示されたように、これらのシステムは、レンダリング表面をｎｘｍのピクセルタイルのサブ表面へと分割し、三角形、線又は点のようなプリミティブのみが、プリミティブに重畳するタイルにおいて処理される。
【０００５】
タイルベースの３Ｄコンピュータグラフィックシステムにおいてタイル化のために遂行される主たるステップが図１に示されている。それらは、次の通りである。
【０００６】
１．図１の１０１において、プリミティブ及び頂点の入力データストリームが受け取られる。三角形ストリップ及び扇形のような、同様の位置におけるプリミティブが時間的に順次に到着する。
【０００７】
２．マクロタイルエンジン（ＭＴＥ）は、頂点をスクリーンスペースへと変換し、後方を向いているか又は良く知られた方法を使用してクリッピング平面によりクリップされるプリミティブを除去する。次いで、プリミティブは、固定の最大数の頂点及びプリミティブを伴うプリミティブブロックへとグループ化され、そして図１の１０２においてメモリへ書き込まれる。頂点及びプリミティブの数は、プリミティブブロックのメモリアドレス（プリミティブブロックポインタ）と共に、１０３において、タイルエンジンへ送られ、プリミティブによりカバーされるタイルの表示リストのための制御ストリームに追加される。
【０００８】
プリミティブ及び頂点データをフェッチするためのメモリ帯域巾の影響を最小にするために、プリミティブは、プリミティブブロックの境界ボックスに基づいてマクロタイルにおけるプリミティブブロックへとグループ化される。図２において、マクロタイル２０１は、固定数のタイル２０２を伴うスクリーン２００の長方形エリアである。例えば、マクロタイルは、スクリーンサイズの１／４又は１／１６である。この構造を使用して、プリミティブブロックを局所化し、メモリの帯域巾を減少させる。プリミティブブロックのプリミティブがマクロタイルに交差するときには、それらが、グローバルマクロタイルリストと称される特殊なマクロタイプリストに書き込まれる。このように、プリミティブブロックのパラメータデータは、一度しか書き込まれない。マクロタイルからのプリミティブは、マクロタイル内のタイルでなければアクセスできず、一方、グローバルマクロタイルリストからのプリミティブは、全てのタイルによってアクセスすることができる。
【０００９】
３．マクロタイルエンジンにより書き込まれた（１０２）プリミティブブロックからの各プリミティブは、プリミティブブロックの境界ボックス内の各タイルに対してチェックされる。プリミティブブロックのプリミティブによりカバーされるタイルについて表示リストにプリミティブブロックが追加される。タイルの表示リストに関連した制御ストリームに書き込まれた制御データは、プリミティブブロック内の頂点及びプリミティブの数に対するプリミティブブロックヘッダ、プリミティブブロックが書き込まれるメモリアドレスのプリミティブブロックポインタ、及びタイルにおいて見ることのできるプリミティブに対するプリミティブマスクを含む。
【００１０】
表示リスト内の制御ストリームデータに対して各タイルに個別のメモリスペースが割り当てられる。テールポインタと称されるメモリアドレスポインタが各タイルの制御ストリームデータにおける次の空きアドレスに対して使用される。
【００１１】
タイル内の制御ストリームに対するメモリアクセスを改善するために、小さなキャッシュ即ちテールポインタキャッシュをタイルエンジンに追加することができる（１０３）。タイル内の制御ストリームの終了のメモリ位置は、テールポインタキャッシュに記憶されてそこから読み取られ、これは、タイルエンジンからの主たるメモリアクセスを減少させる。
【００１２】
４．タイルベースの３Ｄコンピュータグラフィックシステムの３Ｄ画像処理が、図３の領域アレイ３００からのスクリーンのタイルごとに、１０４において遂行される。これは、図３の各タイル３０１の制御ストリームを通して進み、制御データ３０２においてプリミティブブロックポインタで指されたメモリアドレスから頂点及びプリミティブデータを読み取る。隠れた表面の除去、テクスチャ化及びシェーディングのような画像処理オペレーションがプリミティブブロックからタイルにおいて有効な全てのプリミティブに対して遂行される。
【００１３】
タイルベースのレンダリングの一例が図６に示されている。スクリーンの一部分であるマクロタイルＭＴ０  ６００は、１６枚のタイル６０１を内部に有する。２つの三角形ストリップ６０２、６０３及び大きな三角形６０４は、マクロタイルエンジンＭＴＥ６０５によって処理され、ＭＴ０のスクリーンの一部分へ投影される。３つのプリミティブブロックに関連した頂点及びプリミティブデータは、それら自身のメモリアドレスでメモリ６０７に書き込まれる。次いで、３つのプリミティブブロックのメモリアドレスポインタが、タイル処理のためにタイルエンジンＴＥ６０６へ通される。全てのタイルがタイルエンジンによって横断されて、プリミティブがタイルの内部にあるかどうか判断すると共に、タイル内に見えるプリミティブブロックに関連した制御ストリームデータがタイル表示リストのためにメモリに書き込まれる。この例では、Ｔ５における表示制御ストリームは、３つのプリミティブブロックのアドレスポインタに対する制御データと、３つのプリミティブブロック内の三角形の三角形可視マスクとを含む。例えば、プリミティブブロック６０２の左から最初の３つの三角形及びプリミティブブロック６０３の右から最初の三角形は、三角形６０４と一緒に、Ｔ５において見ることができる。タイルＴ９では、制御ストリームデータは、プリミティブブロック６０３及び６０４からの情報のみで構成される。そうする間に、プリミティブブロック６０２に関連した頂点データのアドレスポインタのような制御データは、タイルＴ５のための２つの制御ストリームに挿入され、一方、プリミティブブロック６０４に関連した制御データは、マクロタイルＭＴ０のタイルごとに制御ストリームへと挿入される。
【００１４】
３Ｄレンダリング処理６０８では、全てのタイルが図３の３００のような領域アレイの順序で１つづつ処理される。３Ｄ処理における各タイルに対して、制御ストリームからの制御データが、図３の３０１のように、最初にメモリから読み取られる。タイル制御データにおけるプリミティブブロックに関連した頂点及びプリミティブデータは、図３の３０２のようにメモリから読み取られ、それ故、タイルに対して見える全ての三角形が処理されてスクリーンにレンダリングされる。
【００１５】
タイルベースのコンピュータグラフィックシステムでは、レンダリングがタイルごとに遂行される。タイルベースレンダリングの大きな利点は、グラフィックシステムの大きな内部記憶及びメモリ帯域巾の必要性を著しく減少することである。
【発明の概要】
【発明が解決しようとする課題】
【００１６】
タイルベースレンダリングの欠点は、各タイルの表示リストに対して制御データの増加が必要とされることである。三角形がカバーする全てのタイルに対して表示制御データを書き込むことが必要である。多数のタイルをカバーする大きな三角形では、書き込まれる制御データの合計量が顕著なものとなる。
【００１７】
例えば、スクリーンサイズ１９２０ｘ１０８０のレンダリングは、１６ｘ１６ピクセルの８１６０個のタイルへと分割することができる。全スクリーンをカバーする大きな三角形を全てのタイルの表示リストに追加しなければならない。制御データとして３２ビットワードが２つ必要とされる場合には、合計制御ストリームデータは、単一のフルスクリーン三角形に対してほぼ６４ＫＢとなる。この場合に必要とされる制御データの量は、メモリスペース要求及びメモリ帯域巾に著しく影響し、それ故、タイルベースの３Ｄコンピュータグラフィックシステムのレンダリングの性能に影響を及ぼす。
【００１８】
英国特許出願第０７１７７８１．９号には、タイルエンジンの性能を改善するために２つのタイルを同時に処理するシステムが説明されている。２つの隣接タイルからの制御ストリームデータが単一の表示リストへと合成され、これは、合計制御ストリームデータを前記例において約３２ＫＢに減少する。制御ストリームデータのサイズは、この場合に約半分のサイズであるが、単一の三角形に対する制御データは、依然、顕著な量である。
【課題を解決するための手段】
【００１９】
本発明の好ましい実施形態は、タイルベースの３Ｄコンピュータグラフィックシステムにおいてマルチレベルの表示制御リストを可能にする方法及び装置を提供する。これは、特に、大きな三角形を伴うシーンに対して、書き込まれるタイルベースの制御ストリームデータの量を減少し、それにより、メモリ帯域巾を減少すると共に、タイルベースの３Ｄグラフィックシステムの性能を向上させる。
【００２０】
タイルベースのレンダリングシステムでは、複数のタイルをカバーする三角形は、制御ストリームデータにリファレンスを配さねばならない各タイルについてメモリ及び帯域巾を消費する。ここに提案する本発明は、多数のタイルに重畳する三角形が制御ストリームに対して少数のリファレンスを書き込むだけでよいように後続レベルが次第に大きなタイルグループを表すマルチレベルリスト構造を導入することにより、この問題を軽減する。ここに述べる実施形態では、マルチレベルリスト構造は、３つのレベル、即ちタイルレベル（１タイル）、ブロックレベル（ＮｘＭ個のタイル）、及びマクロタイルレベル（ＸｘＹ個のタイル）で具現化される。ここに提案する本発明は、複数のサブレベル表現を使用して、表示リストのための制御ストリームを更に効率良くできるように、容易に拡張することができる。
【００２１】
好ましい実施形態では、三次元コンピュータグラフィック画像をレンダリングするための方法において、
画像を複数の長方形タイルへと細分化し、
複数レベルの次第に大きくなるタイルグループより成るマルチレベル構造にタイルを配列し、
レンダリングされるべき画像データを、画像をレンダリングするのに必要な画像データを含む複数のプリミティブブロックへと分割し、
各プリミティブブロックを、それが交差するタイルグループに基づきマルチレベル構造内のタイルグループに指定して、各プリミティブブロックがマルチレベル構造内の１つのレベルのグループに指定されるようにし、
画像をレンダリングするための制御ストリームデータを導出し、その制御ストリームデータは、各グループに指定されたプリミティブブロックに対応するマルチレベル構造の各レベル内の各タイルグループに対してプリミティブブロックへのリファレンスを含み、
制御ストリームデータを使用して、プリミティブデータを表示のためにタイルグループ内のタイルへとレンダリングする、
ことを含む方法が提供される。
【図面の簡単な説明】
【００２２】
【図１】タイルベースの３Ｄコンピュータグラフィックシステムにおいてタイルを具現化するときに遂行される主たるステップの概略を示す。
【図２】タイルベースの３Ｄコンピュータグラフィックシステムに使用されるマクロタイル及びスクリーン上のタイルを示す。
【図３】タイル化に使用されるデータ構造の概略を示す。
【図４】本発明の一実施形態においてマクロタイルのマルチレベル表示制御リストに使用されるデータ構造の概略を示す。
【図５】本発明の一実施形態においてマルチレベル表示制御リストの制御ストリームデータに使用されるデータ構造の概略を示す。
【図６】タイルベースレンダリングの一例を示す。
【発明を実施するための形態】
【００２３】
上述したタイルベースの３Ｄコンピュータグラフィックシステムにおいて、タイルエンジンは、マクロタイルエンジンからプリミティブブロックを取り出し、そしてプリミティブをレンダリングするのに必要な最小タイル枚数を計算する。次いで、タイルの最小リストが処理され、そしてプリミティブブロックデータのアドレスに対するプリミティブブロックポインタが、タイルに存在するプリミティブを記述するプリミティブヘッダワードと共に、図３の３０１において、制御ストリームデータとして、動的に割り当てられたメモリに書き込まれる。
【００２４】
各タイルは、制御ストリームデータに対して使用されるそれ自身の固定サイズのメモリスペースを有する。このスペースのメモリブロックは、タイルベースの３Ｄコンピュータグラフィックシステムによりオンデマンドで割り当てられる。特定のタイルについて制御ストリームに追加されるべき新たなデータが、割り当てられた現在メモリブロックを越えると、新たなブロック割り当てが要求され、そして古い制御ストリームが、ストリームリンクを使用して新たなブロック割り当てにリンクされる。マクロタイルエンジンが終了信号を経てシーンの終わりを指示する場合には、全てのタイルが処理され、有効領域のタイルに対する制御ストリームが終了ワードで終了となる。
【００２５】
タイルベースの３Ｄコンピュータグラフィックシステムでは、プリミティブブロックに対する頂点及びインデックスデータは、プリミティブブロックが属するマクロタイルに、又はプリミティブブロックの境界ボックスがマクロタイルに交差するときにはグローバルなマクロタイルリストに、一度書き込まれるだけである。プリミティブブロックが大きなプリミティブを含むときには、制御ストリームデータは、プリミティブが重畳する全てのタイルに何回も書き込まれねばならない。フルスクリーン三角形という極端なケースでは、制御ストリームデータをタイルごとにスクリーンに書き込まねばならない。書き込まれる制御ストリームデータの複数の繰り返しは、メモリ帯域巾の著しい増加を引き起こす。
【００２６】
本発明の実施形態では、単一のタイルベースの表示制御リストに代わってマルチレベル表示制御リストが使用される。マルチレベル表示制御リストの制御ストリームデータは、個々のタイルではなくマクロタイル及びタイルブロックのようなタイルのグループに基づくが、選択されるサブレベルの数は、当業者にとって設計上の選択肢に過ぎない。制御リストは、各タイルグループに対する制御ストリームデータを含み、制御ストリームデータは、表示のために画像をレンダリングするのに使用するため、各タイルグループへとレンダリングされるプリミティブブロックへのリファレンスを含む。制御ストリームデータの規範的構造について以下に説明する。より高い及びより低い複雑さ程度を具現化することができる。
【００２７】
マルチレベル表示制御リスト
本発明の実施形態では、マクロタイルは、画像を１６のタイルブロック（ＴＢ）へ分割し、タイルブロックにおけるタイルの枚数は、マクロタイルサイズに基づいてレンダリングするために固定される。マクロタイルサイズが１６タイルｘ１６タイル（２５６タイル）であると仮定すれば、マクロタイル４００におけるタイルブロック４０１は、各々、図４に示すように、４タイルｘ４タイル（１６タイル）の同じサイズとなる。マクロタイルのタイルブロックごとに制御ストリームリストが形成される。４つのマクロタイルの場合には、１６ｘ４＝６４の制御ストリームリストがあり、一方、１６のマクロタイルの場合には、１６ｘ１６＝２５６の制御ストリームリストがある。
【００２８】
レンダリングは、依然、タイルごとに行われるが、タイルブロック内のタイルは、同じ制御ストリームリストを共有する。
【００２９】
タイルブロックベースのマルチレベル表示制御リストを使用する主たる利益は、特に、多数のタイルをカバーする大きなプリミティブの場合に、必要な制御データの量を減少し且つメモリ帯域巾を減少することである。他の利益として、次のことが含まれる。
【００３０】
タイルベースの制御ストリームリストは存在せず、それ故、各タイルに書き込むために制御ストリームデータの次の空きアドレスを記憶する必要はない。シーンが終了したときにタイルが空きタイルであるかどうか識別するために、１ビットのタイル使用フラグが各タイルに対して使用される。
【００３１】
又、マクロタイルベースの制御ストリームリストの数に限度があるために、各タイルに対する制御ストリームベースアドレスワードを領域アレイに書き出す必要はない。
【００３２】
制御ストリームデータ構造
マルチレベル表示制御ストリームリストシステムのデータ構造は、３つの主たる部分、即ち図４に示すタイルブロック制御リスト４０３、制御ポインタ４０４及びプリミティブ頂点マスク４０５で構成される。
【００３３】
タイルブロック制御リスト４０３は、タイルブロック（ＴＢ０、ＴＢ１、・・・ＴＢ１５）ベースで設けられる。図４の４０３のように、マクロタイル構造には１６個のタイルブロック制御リストがある。各タイルブロック制御リストは、マクロタイルの割り当てられたメモリスペースに、それ自身のメモリスペースが割り当てられている。
【００３４】
図４の制御ポインタ４０４及びプリミティブマスクデータ４０５は、マクロタイルごとに設けられる。これらは、マクロタイルの割り当てられたメモリに個別のメモリスペースを有する。
【００３５】
タイルブロック制御リスト
マルチレベル表示制御リストシステムでは、制御ストリームリストが、タイルブロック（ＴＢＯ、等）ベースで設けられる。図５の５００のようにマクロタイルのタイルブロックごとにタイルブロック制御リストがある。タイルブロック制御リストは、そのタイルブロックにより参照される各プリミティブブロックへのリファレンスを含む。
【００３６】
タイルブロック制御リストは、タイルブロックの全タイル間に共有されるので、制御リストにおいて参照されたプリミティブブロックだけが、タイルブロック内の幾つかのタイルに対して有効となる。本発明のこの実施形態に使用されるデータ構造は、画像をレンダリングするときにプリミティブブロックをできるだけ早く処理する必要のないタイルをスキップするために近道を使用するよう設計される。プリミティブブロックを処理する必要のないタイルについては、本発明の実施形態は、最小のデータ量でプリミティブブロックを処理するための全ての情報を得る。
【００３７】
タイルブロック制御ワード
プリミティブブロックの頂点データに対するアドレスポインタは、マクロタイルリスト４０４ごとに書き込まれるので、それらは、マクロタイル内の全タイルブロックによって共有される。特定のタイルブロックでは、マクロタイルの全てのプリミティブブロックがタイルブロックにおいて参照されるのではない。タイルブロックに必要とされないプリミティブブロックをスキップできるのが効率的である。
【００３８】
図５のタイルブロック制御ワード５０３は、マルチレベル表示制御リストストリームのトップレベル制御ワードである。これは、テーブル１に示す２ビットエンコーディングを有し、そして主として、そのタイルブロックに対してプリミティブブロックを処理すべきかどうか決定するのに使用される。
0005579193.tif 000002
テーブル１：タイルブロック制御ワード
【００３９】
それ故、テーブル１に示すように、２ビットのタイルブロック制御ワードにより定義された４つの考えられるオペレーションがある。
【００４０】
１つのプリミティブブロックをスキップする
プリミティブブロックがタイルブロックにおいてタイルをカバーするためにプリミティブをもたないときには、プリミティブブロックは、処理されずにスキップされる。
【００４１】
有効なプリミティブブロック
プリミティブブロックのプリミティブがタイルブロックのタイルをカバーするときは、プリミティブブロックをスキップすることができない。タイルブロック内のタイルについてプリミティブブロックを処理するためにはマルチレベル表示制御リストに更なる情報が必要とされる。
【００４２】
スキップカウントでスキップ
これは、タイルブロックが多数のプリミティブブロックを連続的にスキップできるとき、即ちこれらのプリミティブブロックがタイルに対して処理される必要がないときに使用される近道である。
【００４３】
この実施形態では、５のスキップカウントオフセットがある。スキップカウントが５未満である場合には、「１つのプリミティブブロックをスキップする」エンコーディングが繰り返し使用される。スキップカウントが５以上であるときには、「スキップカウントでスキップ」が使用される。８ビットスキップカウントの場合、最大スキップカウントは、２５５＋５＝２６０である。スキップカウントが２６０より大きいときには、２つ以上のスキップエンコーディングが必要になる。
【００４４】
終了
終了は、タイルブロックに対してマルチレベル表示制御リストが終了されることを指示する。
【００４５】
タイルブロックフォーマットワード
タイルブロック制御リストにおける図５のタイルブロックフォーマットワード５０４は、タイルブロック制御ワードの各有効プリミティブブロックエンコーディング（テーブル１の値１）の後に使用される。これは、処理されているタイルに対してプリミティブブロックが有効であるかどうか識別するために使用される。タイルブロックフォーマットワードの２ビットエンコーディングは、次の通りである。
0005579193.tif 000003
テーブル２：タイルブロックフォーマットワード
【００４６】
テーブル２に示すように、タイルブロックフォーマットワードの２ビットにより定義された４つの考えられるオペレーションがある。
【００４７】
タイルマスク存在
プリミティブブロックがタイルブロック内の各タイルをカバーするためにプリミティブをもたないとき、即ちあるタイルがプリミティブブロックのプリミティブによって重畳されないとき、タイル有効タイルマスク当たり１ビットを使用して、プリミティブブロックが処理される必要のないタイルをスキップする。タイルマスクに対する合計ビット数は、タイルブロックにおけるタイル数に等しい。
【００４８】
全タイル有効
プリミティブブロックがマクロタイル又はタイルブロックにおいて各タイルをカバーするためのプリミティブを有するときには、タイルブロックの全タイルに対してプリミティブブロックが有効である。この場合には、タイルマスクが不要である。
【００４９】
１つのタイルのみ有効
プリミティブブロックがマクロタイルの１つのタイル又はタイルブロックの１つのタイルしかカバーしないときには、タイルブロックの有効タイルに対するタイルインデックスＸ及びＹを使用して、必要なデータ量を減少する。このケースでは、タイルマスクが不要である。
【００５０】
８ｘ８のタイルを伴うタイルブロックでは、各タイルが有効であるかどうか指示するのに６４ビットマスクが必要である。タイルブロック内の唯一の有効タイルのインデックスＸ及びＹに対して４ビットが使用される場合には、８ビットしか必要とされない。
【００５１】
全タイル無効
プリミティブブロックがマクロタイル又はタイルブロックのタイルをカバーするためのプリミティブをもたないときには、タイルブロックのタイルに対してプリミティブブロックが無効となる。このケースでは、タイルマスクが不要である。このケースは、サブレベルタイルブロックに対するタイルブロックフォーマットワードでのみ生じる。
【００５２】
タイルブロックフォーマットワードが処理された後に、現在プリミティブブロックを、図５の５０５において処理されたタイルに対して有効又は無効として識別することができる。
【００５３】
フルプリミティブマスクフラグ存在
図５のフルプリミティブマスクフラグ存在５０６は、プリミティブブロックにおいてフルプリミティブマスクフラグが存在するかどうか指示するために現在タイルに対して有効なプリミティブブロックのための１ビットフラグである。
【００５４】
プリミティブブロックの全プリミティブがタイルにおいて見えるときには、フルプリミティブマスクと称される。プリミティブブロックの各プリミティブ及び頂点に対して個々のビットマスクではなく、フルプリミティブマスクに対して１ビットフラグが必要とされるに過ぎない。
【００５５】
フルプリミティブマスクフラグ
図５のフルプリミティブマスクフラグ存在５０６の１ビットフラグがセットされた場合には、各タイルがフルプリミティブマスクを有するかどうか指示するためにタイルブロックの各タイルに対し図５のタイル当たり１ビットのフルプリミティブマスクフラグ５０７をセットさせる。フルプリミティブマスクフラグの合計ビット数は、タイルブロックにおけるタイル数に等しい。
【００５６】
フルプリミティブマスクがない場合には、頂点マスクがプリミティブマスクにより連結され、そしてバイト整列される。最大１６個の頂点及び３２個のプリミティブを伴うプリミティブブロックの場合に、頂点マスクは、最大２バイトであり、そしてプリミティブマスクは、４バイトである。プリミティブ及び頂点マスクのサイズは、タイルブロックに対して同じに保たれる。プリミティブ及び頂点マスクデータは、図５のようにマクロタイル当たりプリミティブマスクデータストリーム５０２に書き込まれる。
【００５７】
フルプリミティブマスクフラグを伴うタイルを有するタイルブロックでは、フルプリミティブマスクフラグを使用すると、プリミティブブロックにおいて有効プリミティブ及び頂点に対する情報を得るための時間及びメモリスペースを節約する。処理されたタイルに対してプリミティブブロックが無効である場合には、これらのフラグをスキップすることができる。
【００５８】
プリミティブマスクフォーマットワード
タイルブロック制御リストにおける図５の２ビットのプリミティブマスクフォーマットワード５０８は、図５のフルプリミティブマスクフラグ存在５０６の１ビットフラグがセットされないとき、即ちフルプリミティブマスクフラグがないときに、存在する。
0005579193.tif 000004
テーブル３：プリミティブマスクフォーマットワード
【００５９】
テーブル３と同様に、プリミティブマスクフォーマットワードは、タイルブロックのプリミティブマスクフォーマットに対して４つの特殊なケースを含む。
【００６０】
プリミティブマスクが存在するタイルブロック内の全てのタイル
これは、プリミティブマスクが存在するプリミティブブロックによりカバーされたタイルブロック内の全てのタイルを指示する。即ち、フルプリミティブマスクを有するタイルはなく、プリミティブマスクは、タイルブロック内で同じではない。このケースでは、プリミティブ及び頂点マスクは、図５のプリミティブマスクデータストリームから読み取られる。
【００６１】
フルプリミティブマスクを伴うタイルブロック内の全てのタイル
これは、プリミティブブロックによりカバーされたタイルブロック内の全てのタイルがフルプリミティブマスクを有することを指示する。図５のタイル当たり１ビットのフルプリミティブマスクフラグ５０７は必要とされない。
【００６２】
マクロタイル内の同じプリミティブマスク
これは、プリミティブブロックによりカバーされるマクロタイル内の全てのタイルが同じプリミティブマスクを有し、そして共通のプリミティブマスク及び頂点マスクの合計ビットが２４ビット以下であることを指示する。
【００６３】
プリミティブ及び頂点マスクデータは、個別の４ＫＢメモリページ内の各マクロタイルについて図５のデータストリーム５０２に書き込まれる。プリミティブ及び頂点マスクデータストリームのスタートアドレスは、図５の制御ポインタ５０１にプリミティブマスクポインタワードとして記憶される。アドレスポインタワード「プリミティブマスクポインタワード」には４ＫＢ整列アドレスのために３バイトの空きビットがある。
【００６４】
このケースでは、マクロタイルに対する共通のプリミティブマスク及び頂点マスクは、２４ビット以下であり、それらは、現在制御ポインタにおけるプリミティブマスクポインタワードのＬＳＢ３バイトに書き込むことができる。
【００６５】
タイルブロック内の同じプリミティブマスク
これは、プリミティブブロックによりカバーされたタイルブロック内の全てのタイルが同じプリミティブマスクを有するか、又はその同じプリミティブマスクをマクロタイル内に有するが、共通のプリミティブマスク及び頂点マスクの合計ビットが２４ビットを越えることを指示する。
【００６６】
このケースでは、共通の頂点マスクは、プリミティブマスクによって連結され、そしてその両方が、プリミティブ及び頂点マスクのバイト数に対する先導する３ビットと共に、タイルブロック制御リストに書き込まれる。
【００６７】
処理されているタイル内のプリミティブマスクの形式は、図５のフルプリミティブマスクフラグ５０７又はプリミティブマスクフォーマットワード５０８のようなプロセスの後に定義することができる。
【００６８】
処理されたタイルは、フルプリミティブマスクフラグ５０７が処理されたがタイルがフルプリミティブマスクにないとき、又はプリミティブマスクフォーマットワード５０８が０（プリミティブブロックマスクが存在するタイルブロック内の全てのタイル）にセットされたときは、プリミティブ及び頂点マスク存在を有する。これら２つのケースでは、タイルに対するプリミティブ及び頂点マスクを、図５のプリミティブマスクデータストリーム５０２から読み取る必要がある。
【００６９】
他の全てのケースでは、プリミティブ及び頂点マスクは、マクロタイル／タイルブロックにおけるフルマスク又は同じマスクのいずれかであるから、既知である。
【００７０】
タイルブロックプリミティブマスクオフセット存在
マクロタイル内の各タイルのプリミティブ及び頂点マスクは、図５のプリミティブマスクデータストリーム５０２に書き込まれる。マクロタイルのプリミティブ及び頂点マスクデータのスタートアドレスは、図５の制御ポインタ５０１によりプリミティブマスクポインタワードとして定義される。
【００７１】
プリミティブ及び頂点データは、タイルごとにバイト整列され、そしてタイルブロックごとに３２ビット整列される。プリミティブ及び頂点マスクデータがプリミティブマスクデータストリームのスタートに書き込まれないタイルブロックについては、データストリームからタイルブロックに対するプリミティブ及び頂点マスクデータのスタートへプリミティブマスクオフセットを得ることが必要である。プリミティブ及び頂点マスクデータはタイルブロック内のタイルごとに同じサイズであるから、タイルブロックのプリミティブマスクオフセットに関連してタイルインデックスを使用して、タイルに対するマスクデータを読み戻すことができる。
【００７２】
タイルブロックのプリミティブマスクデータがマクロタイルのプリミティブマスクデータストリームのスタートにないときにはタイルブロックのプリミティブマスクオフセットが存在することを指示するために１ビットフラグが使用される。この１ビットフラグは、タイルに対するプリミティブ及び頂点マスクをプリミティブマスクデータストリームから読み取る必要がある２つのケースにおいて必要とされるだけである。
【００７３】
タイルブロックプリミティブマスクオフセット
図５のタイルブロックプリミティブマスクオフセット５０９は、マクロタイル内のプリミティブブロックのプリミティブマスクデータのスタートアドレスからタイルブロック内のプリミティブマスクデータのスタートアドレスに対する１３ビットワードオフセットである。このフィールドは、タイルブロックプリミティブマスクオフセット存在ビットがセットされたときしか存在しない。
【００７４】
プロセスの終わりに、プリミティブブロックに対する図５のタイルブロック制御リスト５００から、現在タイルにおいてプリミティブブロックを処理する必要があるかどうか分かる。プリミティブブロックを処理する必要がある場合には、プリミティブ及び頂点マスクは、現在タイルについても分かる。
【００７５】
マクロタイル制御ポインタ
マクロタイルにおいて有効なプリミティブブロックごとに図５のマクロタイル制御ポインタ５０１には２つの３２ビット制御ポインタワードがある。プリミティブブロックが、５０５において、タイルに対して有効であると決定された場合に、マクロタイル制御ポインタ５０１を使用して、ブロックからプリミティブデータにアクセスする。
【００７６】
プリミティブブロックポインタワード
プリミティブブロックポインタワードは、主として、プリミティブブロックに対する頂点データストリームのスタートアドレスを記憶するのに使用される。３２ビットのプリミティブブロックポインタワードの構造は、テーブル４において明らかである。
0005579193.tif 000005
テーブル４：プリミティブブロックポインタワード
【００７７】
プリミティブマスクポインタワード
プリミティブマスクポインタワードは、主として、プリミティブブロックのマクロタイルにおけるプリミティブ及び頂点マスクデータストリームのスタートアドレスを記憶するのに使用される。３２ビットのプリミティブマスクポインタワードの構造は、テーブル５において明らかである。
0005579193.tif 000006
テーブル５：プリミティブマスクポインタワード
【００７８】
フィールド２  ＨＴ＿ＳＡＭＥ＿ＰＲＩＭ＿ＭＡＳＫ＿ＩＮ＿ＭＴは、テーブル３のようにプリミティブマスクフォーマットワードが２にセットされたときだけ有効であり、これは、マクロタイルに対する共通のプリミティブマスクがあることを意味する。
【００７９】
制御ポインタは、２つの３２ビット／プリミティブブロックに固定されるので、制御ポインタは、タイルブロックにおいて有効でないプリミティブブロックに対してスキップすることができる。
【００８０】
マクロタイルプリミティブマスクデータ
タイル内のプリミティブマスクがマクロタイル又はタイルブロックにおいてフルマスクでも同じマスクでもないときには、プリミティブ及び頂点マスクデータは、図５のマクロタイルプリミティブマスクデータストリーム５０２へ書き込まれる。
【００８１】
プリミティブマスクデータストリームにおいて、頂点マスクは、タイルのためのプリミティブマスクと連結される。ビット数は、頂点の数と、そのときバイトまで丸められたプリミティブブロックにおけるプリミティブの数との和である。プリミティブ及び頂点マスクデータのサイズは、タイルブロック内で同じに保たれる。
【００８２】
マクロタイルプリミティブマスクデータストリームは、メモリページへ連続的に書き込まれた各タイルブロックからのマクロタイルベースのプリミティブ及び頂点マスクデータである。
【００８３】
タイルブロック内のプリミティブブロックに対するプリミティブ及び頂点マスクデータのスタートアドレスは、３２ビット整列される。スタートアドレスは、プリミティブブロックに対する図５の制御ポインタ５０１によりプリミティブマスクポインタワードとして記憶される。
【００８４】
マクロタイル内のプリミティブブロックのスタートアドレスからのタイルブロックに対するスタートアドレスの３２ビットオフセットは、タイルブロックプリミティブマスクオフセット存在ビットがセットされたときに図５の１３ビットタイルブロックプリミティブマスクオフセット５０９としてタイルブロック制御リスト５００に記憶される。タイルブロックプリミティブマスクオフセット存在ビットがセットされない場合には、タイルブロック内のプリミティブマスクデータのオフセットが０であることを意味する。プリミティブ及び頂点マスクデータは、タイルブロック内の各タイルに対して同じサイズであるから、タイルインデックスをタイルブロックプリミティブマスクオフセットに関連して使用して、タイルに対するプリミティブ及び頂点マスクデータを読み戻すことができる。
【００８５】
タイルブロック制御リストにおけるタイルブロックサブレベルマスク
マクロタイルは、１６個のタイルブロックに分割されるので、タイルブロックにおいて見えないプリミティブブロックは、スキップすることができる。タイルブロック内では、有効なタイルマスクを使用して、プリミティブブロックが処理する必要のないタイルをスキップする。３Ｄ処理で読み取られる制御データの量は、更に別のサブレベルブロックが各タイルブロックに導入されたときに減少される。
【００８６】
ここに述べるタイルブロック制御リストは、マルチレベル表示制御リスト構造へと容易に拡張することができる。
【００８７】
タイルブロック制御リストの有効なプリミティブブロックに対して、図５のタイルブロックフォーマットワード５０４は、１つのタイルブロックフォーマットワードではなく、４つのサブレベルタイルブロックフォーマットワードへ拡張することができる。各サブレベルタイルブロックは、タイルブロックからのタイルの１／４を有する。タイルブロックフォーマットワード５０４の１から３のように全タイルが有効、全タイルが無効及び１つのタイルだけが有効という特殊なケースに遭遇する確率は、サブレベルタイルブロックに対して高くなる。更に、サブレベルタイルブロックが図５のプリミティブマスクフォーマットワード５０８に全部フルプリミティブマスク及び同じプリミティブマスクを有する機会も高くなる。それ故、必要とされる制御データの量は、１つのタイルブロックフォーマットワードに比して減少される。
【００８８】
マルチサブレベルを使用して、タイルブロックフォーマットワードに更に含まれるタイルの数を減少することができる。これは、マクロタイルにより多くのタイルを伴う大きなレンダリングサイズについて、特に言えることである。
【００８９】
マルチサンプルアンチエイリアシング（ＭＳＡＡ）をイネーブルして６４０ｘ４８０ピクセルをレンダリングする場合に、タイルブロックには６ｘ４＝２４枚のタイルがある。タイルブロックに１つのサブレベルブロックを追加することにより、サブレベルブロックサイズは、３ｘ２＝６枚のタイルとなる。このケースでは、個々のタイルを早期にスキップしてもよく、プリミティブマスクデータの特殊なケースにタイルが得られる機会は、２４タイルのタイルブロックではなく、６タイルのサブレベルにおいて高くなる。
0005579193.tif 000007
テーブル９：マルチレベル表示制御リストタイルブロックサイズ
【００９０】
テーブル９は、ある共通使用のレンダリングサイズに対するタイルブロック内のタイルの数を示す。又、タイルブロック内のサブレベルブロックにおけるタイルの数も示す。
【００９１】
タイルブロック内のタイルの数がＸ及び／又はＹ方向に偶数でないケースでは、サブレベルブロックの幾つかが有効なフルタイルマスクをもたないことがある。レンダリングサイズ１０２４ｘ７６８、非ＭＳＡＡのケースでは、タイルブロックサイズが４ｘ３であり、サブレベルサイズが２ｘ２タイルである。タイルブロック内では、下部の２つのサブレベルブロックが２ｘ１のタイルを有し、一方、上部の２つのサブレベルブロックが２ｘ２のタイルを有する。
【００９２】
小さなレンダリングサイズについては、レンダリングサイズ６４０ｘ４８０、非ＭＳＡＡのケースと同様に、サブレベルブロックが不要になることがある。ＭＳＡＡがイネーブルされる非常に大きなレンダリングサイズでは、テーブル９に示すように、マルチサブレベルブロックが必要になることがある。
【００９３】
ここに提案する本発明の実施形態におけるマルチレベル表示制御リストは、制御ストリームデータの量を著しく、あるケースでは９０％も、減少させる。これは、プリミティブブロックが制御ストリームデータに書き込まれるタイルの数が、複数のタイルをカバーするブロックについて減少されるように、次第に大きなタイルグループのマルチレベル構造内で異なるタイルグループについて制御ストリームデータにプリミティブブロックを割り当てることにより達成される。
【符号の説明】
【００９４】
４０３：タイルブロック制御リスト
４０４：制御ポインタ
４０５：プリミティブ頂点マスク
５００：タイルブロック制御リスト
５０１：制御ポインタ
５０２：プリミティブマスクデータストリーム
５０３：タイルブロック制御ワード
５０４：タイルブロックフォーマットワード
５０６：フルプリミティブマスクフラグ存在
５０７：フルプリミティブマスクフラグ
５０８：プリミティブマスクフォーマットワード
５０９：タイルブロックプリミティブマスクオフセット存在
【図１】
0005579193.tif 000008
【図２】
0005579193.tif 000009
【図３】
0005579193.tif 000010
【図４】
0005579193.tif 000011
【図５】
0005579193.tif 000012
【図６】
0005579193.tif 000013