(57)【特許請求の範囲】
【請求項１】
３次元コンピュータグラフィック画像をマクロタイルエンジン及びタイルエンジンを使用してレンダリングする方法において、
前記マクロタイルエンジンが、レンダリングされるべき画像を複数の長方形エリアへと細分化する段階と、
前記マクロタイルエンジンが、前記画像に見ることのできるプリミティブを、複数のプリミティブブロックの各１つに指定する段階と、
前記マクロタイルエンジンが、どのプリミティブブロックが、各長方形エリアに交差するプリミティブを含むか決定する段階と、
前記マクロタイルエンジンが、前記長方形エリアを複数の固定サイズグループへとグループ化する段階と、
前記マクロタイルエンジンが、前記固定サイズグループの各々に対する制御ストリームデータから成る制御ストリームリストを導出する段階であって、前記制御ストリームデータは、どのプリミティブブロックが、各固定サイズグループの各長方形エリアをレンダリングするよう要求されたか決定するものである段階と、
前記タイルエンジンが、前記固定サイズグループの各々に対して前記制御ストリームリスト内の前記制御ストリームデータを使用して、各グループの長方形エリアを順次にレンダリングすることにより前記画像を表示のためにレンダリングする段階と、
前記タイルエンジンが、前記プリミティブブロックのプリミティブマスクを使用して、前記固定サイズグループをレンダリングするためにどのプリミティブが使用されるかを決定する段階と、
を備えた方法。
【請求項２】
長方形エリアの固定サイズグループの各々に対し領域ヘッダを指示する領域アレイと、各固定サイズグループによって参照される制御ストリームデータのための開始位置を指す制御ベースアドレスとが前記タイルエンジンによって与えられる、請求項１に記載の方法。
【請求項３】
前記制御ストリームデータは、長方形エリアの固定サイズグループをレンダリングするのに必要な各プリミティブブロックを含む、請求項１又は２に記載の方法。
【請求項４】
前記プリミティブマスクは、プリミティブ当たり１ビットである、請求項３に記載の方法。
【請求項５】
前記プリミティブブロックは、プリミティブブロックにおける頂点の数を表すプリミティブブロックヘッダを含む、請求項４に記載の方法。
【請求項６】
前記制御ストリームデータは、メモリの制御ブロックグループに書き込まれ、各制御ブロックは、現在制御ブロックからのデータにリンクされるべき制御ストリームデータを含む制御ブロックのための開始アドレスに対するデータを記憶する制御ポインタアレイを含む、請求項１から５のいずれかに記載の方法。
【請求項７】
長方形エリアの各固定サイズグループに対して、タイルのための前記制御データブロックの空きアドレスポインタの情報を含む２つのテールポインタワードが前記タイルエンジンによって記憶される、請求項６に記載の方法。
【請求項８】
３次元コンピュータグラフィック画像をレンダリングする装置において、
レンダリングされるべき画像を複数の長方形エリアへと細分化する手段と、
前記画像に見ることのできるプリミティブを、複数のプリミティブブロックの各１つに指定する手段と、
どのプリミティブブロックが、各長方形エリアに交差するプリミティブを含むか決定する手段と、
前記長方形エリアを複数の固定サイズグループへとグループ化する手段と、
前記固定サイズグループの各々に対し制御ストリームデータを導出する手段であって、その制御ストリームデータは、どのプリミティブブロックが、各固定サイズグループの長方形エリアをレンダリングするよう要求されたか決定するものである手段と、
前記固定サイズグループの各々に対して前記制御ストリームデータを使用して、各グループの長方形エリアを順次にレンダリングすることにより前記画像を表示のためにレンダリングする手段と、
前記プリミティブブロックのプリミティブマスクを使用して、前記固定サイズグループをレンダリングするためにどのプリミティブが使用されるかを決定する手段と、
を備えた装置。
【請求項９】
長方形エリアの固定サイズグループの各々に対する領域アレイと、長方形エリアの各固定サイズグループに対する制御ストリームデータのための開始位置を指す制御ベースアドレスとが与えられる、請求項８に記載の装置。
【請求項１０】
前記制御ストリームデータは、長方形エリアの固定サイズグループをレンダリングするのに必要な各プリミティブブロックを含む、請求項８又は９に記載の装置。
【請求項１１】
前記プリミティブマスクは、プリミティブ当たり１ビットである、請求項１０に記載の装置。
【請求項１２】
前記プリミティブブロックは、プリミティブブロックにおける頂点の数を表すプリミティブブロックヘッダを含む、請求項１１に記載の装置。
【請求項１３】
前記制御ストリームデータは、メモリの制御ブロックグループに書き込まれ、各制御ブロックグループは、現在制御ブロックからのデータにリンクされるべき制御ストリームデータを含む制御ブロックのための開始アドレスに対するデータを記憶する制御ポインタアレイを含む、請求項１２に記載の装置。
【請求項１４】
長方形エリアの各固定サイズグループに対して、タイルのための前記制御データブロックの空きアドレスポインタの情報を含む２つのテールポインタワードが記憶される、請求項１３に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元コンピュータグラフィックシステム、特に、タイルベースシステムに係り、タイルベースレンダリングの性能を向上させるものである。
【背景技術】
【０００２】
技術が急速に発展するにつれて、三次元のコンピュータ作成画像の複雑さも増加した。頂点及び三角形メッシュを使用して人間の動きのような非常に複雑な３Ｄ物体のコンピュータモデルを容易に構築することができる。この種の３Ｄモデルを３Ｄコンピュータグラフィックシステムへ送り、３Ｄアニメ画像をコンピュータスクリーン上に作成することができる。コンピュータ作成の３Ｄアニメ画像は、３Ｄコンピュータゲーム、ナビゲーションツール、及びコンピュータ支援型エンジニアリングデザインツールに広く使用されている。
【０００３】
３Ｄコンピュータグラフィックシステムは、益々複雑なグラフィックや益々高速な表示の需要に対処しなければならない。表示モデルの細部が増加するにつれて、益々多くのプリミティブ及び頂点が使用される。又、テクスチャ及びシェーディング技術が進歩するにつれて、益々多くの情報がプリミティブ及び頂点データと一緒にされる。近代的なゲームでは、レンダリングに百万を越えるプリミティブが存在する。従って、メモリ帯域巾は、コンピュータグラフィックシステムの性能に対して非常に大きな要因となる。
【０００４】
タイルベースのレンダリングシステムが良く知られている。これは、画像を複数の長方形ブロック又はタイルへと細分化する。英国特許第ＧＢ２３４３６０３号及び国際特許出願第ＷＯ２００４／０８６３０９号では、レンダリング表面がｎｘｍのピクセルタイルのサブ表面へと分割される。三角形、線又は点のようなプリミティブのみが、プリミティブに重畳するタイルにおいて処理される。
【０００５】
タイルベースの３Ｄコンピュータグラフィックシステムにおいてタイル化のために遂行される主たるステップが図１に示されている。
【０００６】
１．図１の１０１のようなプリミティブ及び頂点の入力データストリーム。三角形ストリップ及び扇形のように、同様の位置におけるプリミティブが時間的に順次に到着する。
【０００７】
２．マクロタイルエンジン（ＭＴＥ）は、頂点をスクリーンスペースへと変換し、後方を向いているか又は良く知られた方法を使用してクリッピング平面によりクリップされるプリミティブを除去する。次いで、プリミティブは、固定の最大数の頂点及びプリミティブを伴うプリミティブブロックへとグループ化され、そして図１の１０２のようにメモリへ書き込まれる。頂点及びプリミティブの数は、プリミティブブロックのメモリアドレス（プリミティブブロックポインタ）と共に、タイルエンジンへ送られて、プリミティブによりカバーされるタイルに対する表示リストの制御ストリームに追加される。
【０００８】
プリミティブ及び頂点データをフェッチするときにメモリ帯域巾の影響を最小にするために、プリミティブは、プリミティブブロックへ又はプリミティブブロックの境界ボックスに基づいてマクロタイルへグループ化される。図２において、マクロタイル２０１は、固定数のタイル２０２を伴うスクリーン２００の長方形エリアである。マクロタイルは、スクリーンサイズの１／４又は１／１６であり、これを使用して、プリミティブブロックを局所化し、メモリ帯域巾を減少させる。プリミティブブロックのプリミティブがマクロタイルに交差するときには、それらが、グローバルマクロタイルリストと称される特殊なマクロタイルに書き込まれる。このように、プリミティブブロック内のパラメータデータは、一度しか書き込まれない。マクロタイルからのプリミティブは、マクロタイル内のタイルでなければアクセスできず、一方、グローバルマクロタイルからのプリミティブは、全てのタイルによってアクセスすることができる。
【０００９】
３．図１の１０３のようなタイルエンジン（ＴＥ）。マクロタイルエンジンに書き込まれた（１０２）プリミティブブロックからの各プリミティブは、プリミティブブロックの境界ボックス内の各タイルに対してチェックされる。プリミティブブロックのプリミティブによりカバーされるタイルの表示リストにプリミティブブロックが追加される。タイルの表示リストに関連した制御ストリームに書き込まれた制御データは、プリミティブブロック内の頂点及びプリミティブの数に対するプリミティブブロックヘッダ、プリミティブブロックが書き込まれるメモリアドレスのプリミティブブロックポインタ、及びタイルにおいて見ることのできるプリミティブに対するプリミティブマスクを含む。
【００１０】
表示リスト内の制御ストリームデータに対して各タイルに個別のメモリスペースが割り当てられる。テールポインタと称されるメモリアドレスポインタが各タイルの制御ストリームデータにおける次の空きアドレスに対して使用される。
【００１１】
タイル内の制御ストリームに対するメモリアクセスを改善するために、小さなキャッシュ即ちテールポインタキャッシュをタイルエンジンに追加することができる。タイル内の制御ストリームの終了のメモリ位置は、テールポインタキャッシュに記憶されてそこから読み取られ、これは、タイルエンジンからの主たるメモリアクセスを減少させる。
【００１２】
４．３Ｄ画像処理。タイルベースの３Ｄコンピュータグラフィックシステムの３Ｄ画像処理が、図３の領域アレイ３００からのスクリーンのタイルごとに遂行される。これは、図３の各タイル３０１の制御ストリームを通して進み、図３の制御データ３０２においてプリミティブブロックポインタで指されたメモリアドレスから頂点及びプリミティブデータを読み取る。隠れた表面の除去、テクスチャ化及びシェーディングのような画像処理オペレーションは、プリミティブブロックからのタイルにおいて有効な全てのプリミティブに対して遂行される。
【００１３】
タイルベースのレンダリングの一例が図８に示されている。スクリーンの一部分であるマクロタイルＭＴ０  ８００は、１６枚のタイル８０１を内部に有する。２つの三角形ストリップ８０２、８０３及び大きな三角形８０４は、マクロタイルエンジンＭＴＥ８０５によって処理され、ＭＴ０のスクリーンの一部分へ投影される。３つのプリミティブブロックに関連した頂点及びプリミティブデータは、それら自身のメモリアドレスでメモリ８０７に書き込まれる。次いで、３つのプリミティブブロックのメモリアドレスポインタがタイル処理のためにタイルエンジンＴＥ８０６へ通される。全てのタイルがタイルエンジンによって横断されて、プリミティブがタイルの内部にあるかどうか判断すると共に、タイル内に見えるプリミティブブロックに関連した制御ストリームデータがタイル表示リストのためにメモリに書き込まれる。この例では、Ｔ４における表示制御ストリームは、３つのプリミティブブロックのアドレスポインタに対する制御データと、プリミティブブロック８０２、８０４内の三角形の三角形可視マスクとを含む。例えば、プリミティブブロック８０２の左から最初の３つの三角形及びプリミティブブロック８０４からの大きな三角形は、Ｔ４において見ることができる。タイルＴ１０では、制御ストリームデータは、プリミティブブロック８０３及び８０４からの情報のみで構成される。そうする間に、プリミティブブロック８０３に関連した頂点データのアドレスポインタのような制御データは、タイルＴ１０、Ｔ１１、Ｔ１４及びＴ１５のための制御ストリームに挿入され、一方、プリミティブブロック８０４に関連した制御データは、マクロタイルＭＴ０のタイルごとに制御ストリームへ挿入される。
【００１４】
３Ｄレンダリング処理８０８では、全てのタイルが図３の３００のような領域アレイの順序で１つづつ処理される。３Ｄ処理における各タイルに対して、タイル制御ストリームからの制御データが、図３の３０１のように、最初にメモリから読み取られる。タイル制御データにおけるプリミティブブロックに関連した頂点及びプリミティブデータは、図３の３０２のようにメモリから読み取られ、それ故、タイルに対して見える全ての三角形が処理されてスクリーンにレンダリングされる。
【００１５】
タイルベースのコンピュータグラフィックシステムでは、レンダリングがタイルごとに遂行される。タイルベースレンダリングの大きな利点は、グラフィックシステムの内部記憶及びメモリ帯域巾の必要性を著しく減少することである。
【発明の概要】
【発明が解決しようとする課題】
【００１６】
タイルベースレンダリングの欠点は、各タイルの表示リストに対して制御データの増加が必要とされることである。三角形がカバーする全てのタイルに対して表示制御データを書き込むことが必要である。多数のタイルをカバーする大きな三角形では、書き込まれる制御データの合計量が顕著なものとなる。
【００１７】
例えば、スクリーンサイズ１９２０ｘ１０８０のレンダリングは、１６ｘ１６ピクセルの８１６０個のタイルへと分割することができる。全スクリーンをカバーする大きな三角形を全てのタイルの表示リストに追加しなければならない。制御データとして３２ビットワードが２つ必要とされる場合には、合計制御ストリームデータは、単一のフルスクリーン三角形に対してほぼ６４ＫＢとなる。この場合に必要となる多量の制御データは、タイルベースの３Ｄコンピュータグラフィックシステムのレンダリングの性能に大きな影響を及ぼす。
【００１８】
英国特許出願第０７１７７８１．９号に開示されたシステムは、タイルエンジンの性能を改善するために２つのタイルを同時に処理する。２つの隣接タイルからの制御ストリームデータが単一の表示リストへと合成され、これは、前記例からほぼ３２ＫＢの合計制御ストリームデータを与える。制御ストリームデータのサイズは、この場合に約半分のサイズであるが、三角形に対する制御データは、依然、顕著な量である。
【課題を解決するための手段】
【００１９】
本発明の好ましい実施形態は、タイルベースの３Ｄコンピュータグラフィックシステムにおいて表示リスト制御ストリームをグループ化する方法及び装置を提供する。
【００２０】
タイルベースのレンダリングシステムでは、複数のタイルをカバーする三角形は、リファレンスを配さねばならないタイルごとにメモリ及び帯域巾を消費する。本発明の実施形態の表示リスト制御ストリームグループ化方法は、タイルベース表示リストをタイルグループへと編成して、制御ストリームデータが個々のタイルではなくグループに適用されるような単一表示リスト制御ストリームを形成する。タイルにおいてブロック内の制御ストリームデータが参照されない場合には、タイルにおいて全制御データブロックをスキップすることができる。必要とされる制御ストリームデータの量は、タイルグループベースの表示リスト制御ストリームによって減少される。又、この実施形態は、制御ストリームデータの処理効率を高めるために制御ポインタアレイを導入する。表示リスト制御ストリームを最適化することにより、この方法は、内部パラメータメモリ帯域幅を減少し、それ故、タイルベースの３Ｄグラフィックシステムの性能を改善する。
【図面の簡単な説明】
【００２１】
【図１】タイルベースの３Ｄコンピュータグラフィックシステムにおいてタイル化を遂行するための主たるステップの概略を示す。
【図２】タイルベースの３Ｄコンピュータグラフィックシステムに使用されるスクリーン上のマクロタイルを示す。
【図３】タイルベースレンダリングにおける表示リスト制御ストリームグループ化の概略を示す。
【図４】マクロタイルにおける表示リスト制御ストリームグループ化のためのデータ構造の概略を示す。
【図５】表示リスト制御ストリームグループ化における制御データブロックグループのデータ構造を示す。
【図６】表示リスト制御ストリームグループ化において制御データブロックにわたって書き込まれた制御ストリームデータを示す。
【図７】表示リスト制御ストリームグループ化における制御ストリームデータのためのデータ構造の概略を示す。
【図８】タイルベースレンダリングプロセスの一例を示す。
【発明を実施するための形態】
【００２２】
上述したタイルベースの３Ｄコンピュータグラフィックシステムにおいて、タイルエンジンは、マクロタイルエンジンからプリミティブブロックを取り出し、そしてプリミティブをレンダリングするのに必要な最小タイル枚数を計算する。次いで、タイルの最小リストが処理され、そしてプリミティブブロックデータのアドレスに対するプリミティブブロックポインタが、タイルに存在するプリミティブを記述するプリミティブヘッダワードと共に、図３に示す３０１において、制御ストリームデータとして、動的に割り当てられたメモリに書き込まれる。
【００２３】
各タイルは、制御ストリームデータに対して使用されるそれ自身の固定サイズのメモリスペースを有する。メモリブロックは、タイルベースの３Ｄコンピュータグラフィックシステムによりオンデマンドで割り当てられる。特定のタイルについて制御ストリームに追加されるべき新たなデータが、割り当てられた現在メモリブロックを越えると、新たな割り当てが要求され、そして古い制御ストリームが、ストリームリンクを使用して新たな割り当てにリンクされる。マクロタイルエンジンが終了信号を経てシーンの終わりを指示する場合には、全てのタイルが処理され、有効領域のタイルに対する制御ストリームが終了ワードで終了となる。
【００２４】
タイルベースの３Ｄコンピュータグラフィックシステムでは、プリミティブブロックに対する頂点及びインデックスデータは、プリミティブブロックが属するマクロタイルに、又はプリミティブブロックの境界ボックスがマクロタイルに交差するときはグローバルなマクロタイルリストに、一度書き込まれるだけである。しかし、大きなプリミティブを含むプリミティブブロックの場合には、制御ストリームデータが、プリミティブが重畳する全てのタイルに何回も書き込まれねばならない。フルスクリーン三角形という極端な場合には、制御ストリームデータをスクリーン上の各タイルに書き込まねばならない。制御ストリームデータの書き込みを繰り返すと、メモリ帯域巾の増加を引き起こす。
【００２５】
本発明の好ましい実施形態では、タイルベースの表示リストからの制御ストリームは、タイル表示リスト当たり１つの制御ストリームではなく、タイルのグループに対して制御ストリームへと最適化される。
【００２６】
制御ストリームグループ化における制御ストリーム
制御ストリームグループ化の実施形態では、マクロタイル４００におけるタイルが、例えば、図４の４０１の２ｘ２タイルのような固定数のタイルを伴うタイルグループへと分割される。図３の３００の領域アレイ、並びに図３の３０１及び図４の４０２の制御ストリームは、全て、タイルではなく、タイルグループをベースとする。レンダリングは、依然、タイルごとに行われるが、タイルグループ内のタイルは、同じ領域ヘッダワード及び制御ストリームリストを共有する。
【００２７】
パラメータストリーム構造をベースとする制御ストリームグループ化の利益は、次の通りである。
【００２８】
制御ストリームリストは、タイルグループをベースとするものであるから、制御ストリームリストの数は、例えば、必要なタイルベース制御ストリームリストの数の約１／４に減少される。テールポインタの数についても、同じ減少が達成される。
【００２９】
タイルグループの制御ストリームに対してメモリに割り当てられた各制御データブロックの出発アドレスは、図７の７０１において制御ポインタアレイに記憶され、リンクポインタは要求されない。制御データは、制御データブロックを交差するように書き込むことが許される。
【００３０】
制御データブロックの制御データがタイルにおいて参照されないときには、図１の３Ｄ処理１０４において全制御データブロックをスキップすることができる。
【００３１】
領域ヘッダワードは、タイル当たり２つの３２ビットではなく、タイルグループ当たり２つの３２ビットへ減少される。即ち、２ｘ２タイルのグループ化について領域アレイメモリスペースの７５％減少である。
【００３２】
マイクロタイルパラメータストリームデータの３つのエンティティ、即ち領域アレイ、制御ストリーム、及び頂点／インデックスブロックのうち、領域アレイ及び制御ストリームのデータ構造は、ここに提案する制御ストリームグループ化方法において異なる。しかしながら、頂点／インデックスブロックデータは、制御ストリームグループ化において変化がない。
【００３３】
本発明の一実施形態により制御ストリームデータを変更する仕方を、一例として以下に説明する。
【００３４】
領域アレイ
領域アレイは、各タイルの制御ストリームのスタートを記録する。このアレイは、領域ヘッダワード及びそれに続く制御ベースアドレスワードより各々成る領域定義の隣接セットである。
【００３５】
ここに提案する制御ストリームグループ化方法の領域アレイは、個々のタイルではなくて、例えば、２ｘ２タイルのタイルグループをベースとしている。これは、次のデータを記憶する。
0005579741.tif 000002
【００３６】
領域ヘッダ
領域ヘッダワードは、各々８ビットのタイルグループ内の全タイルに対する情報を有する。レンダリングを終了すると、図１のタイルエンジン１０３は、スクリーン上の全てのタイルを通過して、各タイルに対する８ビット領域ヘッダワードをセットアップし、次いで、タイルグループ内の領域ヘッダワードをタイルグループに対する領域ヘッダワードへと合成する。ビットの機能の説明は、２ｘ２タイルを伴うタイルグループについて以下に示す。ビット３１、２３、１５及び７は、未使用である。
【００３７】
領域ヘッダワード
0005579741.tif 000003
【００３８】
レンダリング開始領域位置
タイルグループに対して領域ヘッダワードに与えられるタイル位置Ｘ、Ｙはない。レンダリングのための開始タイル位置及び開始マクロタイルは、個別のレジスタに定義される。通常、この位置は、レンダリングされるべき画像の隅である。図１の３Ｄ処理１０４は、レジスタに定義されたタイル位置から３Ｄレンダリングを開始する。３Ｄ領域ベースアドレスから上述した２つの領域ヘッダワードを読み取り、次いで、タイルグループ内の各タイルをレンダリングする。
【００３９】
次の領域位置
図１の３Ｄ処理ステップ１０４は、所定のタイル順序を使用して、タイルのレンダリングを終了した後に、次のタイル位置Ｘ及びＹを自動的に計算する。
【００４０】
タイルグループを使用する本発明の実施形態では、グループ内の２ｘ２個のタイルは、各々、同じ制御ストリームベースアドレスを共有する。各タイルは、領域ヘッダワードからのそれ自身の８ビット領域情報を有する。マクロタイルのサイズは、タイルグループのサイズに整列されるので、タイルグループのタイルは、常に、スキャン順序でレンダリングされる。次のタイルが同じタイルグループ内にある場合には、次のタイル位置は、２ｘ２タイルグループに対して、Ｘ又はＹのいずれかの方向或いは両方向に、タイルグループ開始タイル位置＋１である。
【００４１】
タイルグループ内の全てのタイルについてレンダリングを終了した後、次の２つの３２ビットが、次のタイルグループに対する領域ヘッダワード及び制御ベースアドレスワードとして領域アレイから読み取られる。
【００４２】
次のタイルグループの位置は、レジスタに予め定義することのできるマクロタイルサイズ及びマクロタイルモードを使用して計算される。タイルグループにおけるタイルの数は固定であり、例えば、２ｘ２個のタイルである。タイルグループは、マクロタイル内のスキャン順序でレンダリングされる。マクロタイルは、垂直線の順序でレンダリングされるのが好ましい。それ故、次のタイルグループの位置は、３Ｄ処理において自動的に計算することができる。
【００４３】
制御ベースアドレス
これは、領域アレイに記憶される他のデータであり、タイルグループにより参照される制御ストリームの開始を指すポインタである。制御ストリームのベースアドレスは、常に、図１の１０３及び図１の３Ｄ処理１０４においてタイルエンジンＴＥにより発生されたときに整列される１２８ビットである。制御ベースワードは、タイルグループ内の最初のタイルについて読み取られ、タイルグループの全タイルにより共有される。
【００４４】
タイルグループに対する制御ストリームデータは、そのタイルグループに割り当てられた固定サイズのメモリブロック、例えば、図示された１６個の３２ビット制御データブロック３０２へ書き込まれる。
【００４５】
制御ベースアドレスワードに含まれた４ビットフィールドCONTROL_BLOCK_TILE_VALIDがあり、これは、制御データブロックからの制御ストリームデータがタイルグループ内のタイルにより参照されるかどうか指示する。ビット２８は、タイルグループのタイル（０、０）に対するものであり、ビット２９は、タイル（１、０）に対するものであり、ビット３０は、タイル（０、１）に対するものであり、そしてビット３１は、タイル（１、１）に対するものである。フィールドCONTROL_BLOCK_TILE_VALIDのビットがタイルに対してセットされない場合には、タイルの３Ｄ処理において制御データブロックをスキップすることができる。しかし、CONTROL_BLOCK_LASTがセットされた最後の制御データブロックであるか、又は制御データブロックが制御ポインタアレイを含む場合には、制御データブロックをスキップすることができない。
【００４６】
制御データブロックのスキップの後、図１の３Ｄ処理１０４は、次の有効な制御データブロックからのタイルを処理し続ける。３２ビットオフセットPRIME_BLOCK_OFFSETは、スキップ後に、制御データブロックから最初のプリミティブブロックヘッダワードを検索するのに使用される。制御ベースアドレスワードの構造は、２ｘ２個のタイルを伴うタイルグループについて以下に示す。
【００４７】
制御ベースアドレスワード
0005579741.tif 000004
【００４８】
制御ストリーム
３Ｄ表示リスト制御ストリームは、図３の３０２及び図４の４０２に示すように、オブジェクトに依存する量のデータが各々後に続く一連のブロックヘッダより成る。制御ストリームの種々の要素について以下に述べる。
【００４９】
ブロックヘッダ
各プリミティブブロックヘッダにおける上位２ビットであるビット３１及び３０は、プリミティブブロックヘッダ形式のために予約され、プリミティブブロックに対して０１であり、そして制御ストリーム終了に対して１１である。図４の制御ストリームデータ４０２がタイルグループにおいて処理されるときに、各ブロックヘッダワードの２つのビット３１及び３０は、そのブロックヘッダワードがプリミティブブロックヘッダワードであるか制御ストリーム終了ワードであるか判断するために最初に分析される。プリミティブブロックヘッダワードである場合には、プリミティブブロックポインタワード及びプリミティブマスクワードのような余分なヘッダワードがプリミティブブロックヘッダワードの後に存在してもよい。
【００５０】
プリミティブブロック
プリミティブブロックは、図３の３０３においてタイルグループに対するプリミティブデータのブロックを定義する。データは、インデックス／頂点データと、ブロックのプリミティブに関連した潜在的な状態とを含む。各プリミティブブロックの制御ストリーム、及びタイルグループリファレンスに、ヘッダワードがある。ヘッダワードは、プリミティブブロックヘッダワード、プリミティブブロックポインタワード及びプリミティブマスクワードを含む。
【００５１】
プリミティブブロックが設けられたプリミティブマスクワードは、タイルグループの各タイル内で現在ブロックのどのプリミティブ及び頂点が参照されるか定義するのに使用される。例えば、プリミティブブロックに３２までのプリミティブがある場合には、プリミティブ当たりのビットで、３２ビットプリミティブマスクが要求される。しかしながら、プリミティブブロックは、１６までの頂点しか含まず、それらの全てが特定のタイルに使用されるのではない。それ故、ブロック内のプリミティブにより参照される頂点を定義するために、頂点当たりのビットで、１６ビット頂点マスクが要求される。
【００５２】
プリミティブマスクワードは、任意であり、プリミティブブロックの全プリミティブをタイルグループの全タイルにおいて参照すべき場合には存在しない。この場合に、プリミティブマスク及び頂点マスクは、完全にセットされると仮定され、即ち、タイルグループ内の各タイルは、このブロック内の全てのプリミティブを参照し、そしてそれらプリミティブは、プリミティブブロック内の全ての頂点を参照する。
【００５３】
プリミティブマスクワードの合計数は、タイルグループ内のタイルのプリミティブマスクフォーマットに基づいてプリミティブブロック間で変化する。その一例を以下に示す。
0005579741.tif 000005
【００５４】
プリミティブブロックヘッダ
プリミティブブロックヘッダワードは、プリミティブブロック内の頂点数に関する情報を表す３２ビットを含む。又、２ｘ２タイルの各々に対するプリミティブマスクフォーマットも含む。この構造は、各ビットにより表される種々の制御機能から次の通りである。
0005579741.tif 000006
0005579741.tif 000007
0005579741.tif 000008
【００５５】
プリミティブブロックポインタ
これは、プリミティブブロックヘッダ後の別の３２ビットワードである。
0005579741.tif 000009
【００５６】
制御ポインタアレイ
タイルグループの表示リスト制御ストリームにおけるデータは、内部に割り当てられた固定サイズのメモリブロック、例えば、１６個の３２ビットメモリブロックに書き込まれる。これらの制御データブロックは、隣接メモリアドレスにないので、次の制御データブロック３０２における制御ストリームデータを処理するために、次の制御データブロックの開始アドレスを何らかの方法で得なければならない。通常、リンクされた制御データブロックのためのアドレスポインタを現在制御データブロックの終わりに挿入することができる。このように、３Ｄ処理は、次の制御データブロックの開始アドレスを得るために全制御データブロックが処理されるまで待機しなければならない。タイルグループのタイルについて、制御データブロックにおける制御ストリームデータをスキップできるときに、次の制御データブロックに対するリンクアドレスを得るだけのために制御データブロックを処理するのはあまり効率的でない。
【００５７】
ここに提案する表示リスト制御ストリームのグループ化方法では、制御ポインタアレイは、３Ｄ処理で連続的に処理されるタイルグループに対して制御ストリームを発生できるように制御データブロックに使用される。
【００５８】
制御ストリームのグループ化では、図５に示す５００において、制御データブロックが８個の制御ブロックのグループに編成される。グループの最初の制御ブロックは、図５の５０１において、制御ポインタアレイに対して予約された最初の８個の３２ビットを有する。制御ポインタの各々は、領域ヘッダにおける制御ベースアドレスワードと同じフォーマットを有し、図５の５０２において、８のグループにおける制御データブロックの開始アドレスを指す。
【００５９】
最初の制御ブロックグループ内の最初の制御データブロックの開始アドレスは、領域ヘッダワード「制御ベースアドレスワード」からである。制御ポインタアレイにおける８番目の制御ポインタは、次の制御ブロックグループの開始アドレスを指す。
【００６０】
全ての制御データブロックの開始アドレスは、制御ブロックにおける制御ポインタアレイに保持されるので、リンクポインタの必要はない。３Ｄ処理では、最初の制御ブロックからの制御ポインタが最初に読み取られ、それら制御ポインタを使用して、制御データブロックグループにおける制御データブロックの開始アドレスを得る。３Ｄ処理は、次の制御データブロックのアドレスを得るために制御データブロックの終わりまで待機する必要がない。これは、制御ブロックグループの制御ブロックを処理し続ける。このスキームは、制御ストリームのグループ化方法において３Ｄ処理の性能を高める。
【００６１】
あるプリミティブブロックでは、タイルグループ内の全てのタイルがプリミティブブロック内のプリミティブによってカバーされるのではない。プリミティブブロックでカバーされないタイルについては、タイルグループ制御ストリームの制御データを３Ｄ処理によりスキップしなければならない。
【００６２】
制御ポインタアレイを使用する別の利点は、CONTROL_BLOCK_TILE_VALIDのビットがタイルに対してセットされない場合に制御データブロックをスキップできることである。これは、制御データブロックの制御データがタイルによって参照されないことを意味する。３Ｄ処理は、タイルグループ内のタイルに対して全制御データブロックがスキップされたときでも、制御ブロックグループの制御データブロックを処理し続ける。タイルにおいて参照されない制御データブロックをスキップできることから、連続的にスキップされるプリミティブブロックの数が制限される。
【００６３】
制御データブロックは、それがCONTROL_BLOCK_LASTがセットされた最後の制御データブロックであるか又はそれが制御ポインタアレイを含む場合には、スキップすることができない。
【００６４】
制御データブロックが割り当てられると、制御データブロックの開始アドレスがタイルグループに対して記憶される。最初のプリミティブブロックヘッダの３２ビットオフセットPRIM_BLOCK_OFFSETも記憶される。CONTROL_BLOCK_TILE_VALID及びCONTROL_BLOCK_LASTのフィールドを埋めるために、制御データブロックが終了したときに制御ポインタワードを書き込まねばならない。即ち、新たな制御データブロックが割り当てられたときに手前の制御ポインタワードを書き込む。最後の制御ポインタワードは、CONTROL_BLOCK_LASTビットがセットされてレンダリングを終了する際に書き込まれる。
【００６５】
制御ストリームデータブロック
プリミティブブロックのデータサイズは、任意のプリミティブマスクワードにより変化する。制御ストリームメモリ使用の効率を改善するために、プリミティブブロックに対する制御ストリームデータは、１６個の３２ビット制御データブロック２つにわたって書きこむことが許される。
【００６６】
図６は、３つの制御ストリームワード、即ちプリミティブブロックヘッダ、プリミティブブロックポインタ、及び１つのプリミティブマスクワードを有するプリミティブブロックの一例を示す。図６の現在データブロック６０１には２つの３２ビット空きスペースがあり、従って、プリミティブマスクワードは、図６の６０２として、次の制御データブロックの開始に書き込まれる。
【００６７】
プリミティブマスク及び頂点マスク
プリミティブブロックは、固定数のプリミティブ及び頂点を含み、例えば、３２個までのプリミティブ及び１６個の頂点を含む。タイルグループのタイルにおいて全てのプリミティブが見えるのではないから、タイルグループの各タイルにおいて参照されたプリミティブ及び頂点を指示するためにプリミティブマスク及び頂点マスクが使用される。
【００６８】
ここに提案する制御ストリームグループ化方法では、タイルグループにおける２ｘ２個のタイルの各々がプリミティブブロックヘッダワードにそれ自身のプリミティブマスクフォーマットを有する。２ビットのプリミティブマスクフォーマットワードのフォーマットは、次の通りである。
【００６９】
・タイル無効
これは、タイルにおいて参照されるプリミティブブロックからのプリミティブがなく、タイルに対するプリミティブ及び頂点マスクもないことを意味する。この場合、３Ｄ処理がタイルグループのタイルにおけるプリミティブブロックをスキップする。
【００７０】
・フルマスク
これは、タイルグループのタイルにおいて全てのプリミティブが参照されることを意味する。この場合に、制御ストリームに必要とされるプリミティブ及び頂点マスクデータはない。３Ｄ処理は、プリミティブ及び頂点のフルマスクを自動的にセットする。
【００７１】
・パックされたマスクデータ
タイルグループのタイルに対してプリミティブマスク及び頂点マスクの両方に１つの非０バイトしかないときには、プリミティブブロックが最大３２個のプリミティブ及び１６個の頂点を含むときの６バイトマスクではなく、制御ストリームのタイルに対する２バイトマスクワードに２つの非０バイトをパックすることができる。マスクデータの開始に非０バイトがない場合には、頂点マスクのための１ビットバイトオフセット及びプリミティブマスクのための２ビットバイトオフセットがタイルグループの各タイルに対してプリミティブブロックヘッダワードに使用される。
【００７２】
例えば、プリミティブマスク００００００００  ００００００００  １０１００１００００００００００（０ｘ００００Ａ４００）及び頂点マスク０１１０１１００  ００００００００（０ｘ６Ｃ００）を伴うプリミティブブロックでは、マスクデータを、０ｘ００００Ａ４００及び０ｘ６Ｃ００ではなく、０ｘＡ４６Ｃへとパックして制御ストリームへ書き込むことができる。プリミティブブロックヘッダでは、プリミティブマスクフォーマットPF_PRIM_MASK_FMTが、タイルに対するパックされたマスクデータとして１０にセットされる。バイトオフセットPF_VERT_MASK_STARTが１にセットされ、そしてPF_PRIM_MASK_STARTがタイルに対して０１にセットされる。３Ｄ処理では、頂点マスクデータが０ｘ６Ｃから０ｘ６Ｃ００へ再構成され、そしてプリミティブマスクがプリミティブマスクフォーマット及びバイト開始ビットを使用して０ｘＡ４から０ｘ００００Ａ４００へ再構成される。
【００７３】
・アンパックされたマスクデータ
プリミティブマスク及び頂点マスクは、タイルに対してパックされない。
【００７４】
同じプリミティブマスク
プリミティブブロックヘッダワードのフラグPF_SAME_MASKがセットされると、それは、タイルグループ内の全タイルが同じプリミティブマスクを有することを指示する。このケースでは、１つのプリミティブマスク及び１つの頂点マスクのみがタイルグループに対する制御ストリームに書き込まれる。
【００７５】
プリミティブマスクワードの数
タイルグループの各タイルにおけるプリミティブ及び頂点マスクは、バイト整列データとして制御ストリームに書き込まれる。プリミティブマスクデータは、最後に３２ビットに丸められる。プリミティブブロックにおけるプリミティブマスクワードの合計数は、タイルグループのタイルのプリミティブマスクフォーマットから計算することができる。
【００７６】
統計学的には、平均で、２ｘ２個のタイルを伴うタイルグループに対して各プリミティブブロックに使用されるプリミティブマスクワードが２未満であることが示される。
【００７７】
テールポインタ
テールポインタワードは、タイルのための制御データブロックの空きアドレスポインタの情報と、他のタイル関連情報とを含むように、図１のタイルエンジン（ＴＥ）１０３にタイルごとに記憶される。ここに提案する制御ストリームグループ化方法では、タイル当たりではなく、タイルグループ当たり１つのテールポインタがある。
【００７８】
タイルグループ当たり２つのテールポインタワードがある。テールポインタワード１の４ビットフィールドTP_TILE_VALIDが、タイルグループのタイルにおいてテールポインタ有効として使用され、タイルがプリミティブブロックによりカバーされる場合にはビットがセットされる。レンダリングの終了時に、テールポインタのフィールドTP_TILE_VALIDのビットが非０である場合に、終了ワードが制御ストリームリストの終わりに書き込まれる。TP_TILE_VALIDのビットが０である場合には、レンダリング終了時にその関連タイルが空きタイルにセットされる。
【００７９】
制御ポインタワードにおけるCONTROL_BLOCK_TILE_VALID及びCONTROL_BLOCK_LASTのフィールドを埋めるために、タイルエンジンＴＥは、制御データブロックが終了したときに、制御ポインタを書き込まねばならない。即ち、新たな制御データブロックが割り当てられたときに手前の制御ポインタワードを書き込む。テールポインタワード１のビットTP_REGION_OUTPUTは、制御ベースアドレスワードが領域ヘッダに書き込まれたかどうか指示するためのフラグである。最初の制御ポインタワードは、TP_REGION_OUTPUTがセットされない場合には制御ベースアドレスワードとして領域ヘッダに書き込まれ、さもなければ、制御ブロックグループの最初の制御データブロックにおける制御ポインタアレイに書き込まれる。
【００８０】
テールポインタワード１
テールポインタワードの構造は、次の通りである。
0005579741.tif 000010
【００８１】
タイルグループの制御ストリームリストにおける最初の制御データブロックの後に、その後の制御ポインタワードが、制御ポインタアレイにおいて、８制御データブロックのグループ内の最初の制御データブロックの上半分に書き込まれる。次の制御ポインタワードのアドレスは、テールポインタワード２にTP_CTRL_POINTER_ADDRとして記憶される。３２ビットオフセットTP_CTRL_POINTER_OFFSETと結合されて、制御データブロックのグループの最初の制御データブロックにおける制御ポインタアレイに８個までの制御ポインタワードを書き込むことができる。
【００８２】
タイルグループのタイルにおいて制御ブロックが有効であるかどうか指示するために４ビットフィールドTP_CTRL_BLOCK_TILE_VALIDが使用される。制御ブロックの制御ストリームデータがタイルによって参照されない場合には、TP_CTRL_BLOCK_TILE_VALIDの当該ビットが０となる。この場合には、制御ブロックがスキップされ、次の制御ブロックが処理される。プリミティブブロックに対する制御ストリームデータが制御データブロックに書き込まれるたびに、フィールドTP_CTRL_BLOCK_TILE_VALIDがプリミティブブロックからのタイル有効フラグで更新される。制御ブロックが制御ストリームデータで完全に埋められた後に、フィールドTP_CTRL_BLOCK_TILE_VALIDがCTRL_BLOCK_TILE_VALIDとして制御ポインタワードに書き込まれる。
【００８３】
フィールドTP_PRIM_BLOCK_OFFSETは、制御ブロックにおける最初のプリミティブブロックヘッダワードの３２ビットオフセットである。これは、スキップ制御ブロックの後に最初のプリミティブブロックヘッダを得るために３Ｄ処理により使用される。制御ブロックにおける最初のプリミティブブロックヘッダワードのオフセットは、テールポインタワード２に記憶され、そして制御ポインタワードのフィールドPRIM_BLOCK_OFFSETに書き込まれねばならない。
【００８４】
テールポインタワード２
0005579741.tif 000011
【００８５】
３Ｄ処理における制御ストリームデータ構文解析
図７は、３Ｄ処理における制御ストリームデータ構文解析を示す。プリミティブブロックヘッダワード、プリミティブブロックポインタワード及びプリミティブマスクワードを含むプリミティブブロックヘッダワードが、図７の７００のように、タイルグループのための制御ストリームデータからフェッチされる。プリミティブブロックごとに、プリミティブブロックヘッダワード７０１が検査されて、プリミティブマスクワードがあれば、その数７０２を得る。プリミティブブロックヘッダワードから、プリミティブブロックに対してタイルが有効であるかどうか知ることができる。タイルが有効であって、タイルをカバーするプリミティブブロックからのプリミティブがある場合には、プリミティブブロックポインタワードが、７０３において、３Ｄ処理のためにプリミティブマスクワードと共にフェッチされる。プリミティブブロックヘッダワードに定義されたように、７０４において、プリミティブブロックに対してタイルが有効でない場合には、プリミティブヘッダワードがスキップされる。
【００８６】
プリミティブブロックヘッダワードは、レンダリングに対するタイルグループの制御ストリームの終わりである制御ストリームの終了ワードまで、タイルグループの制御ストリームデータから連続的に処理される。
【００８７】
制御ストリームデータのシステムレベルキャッシュ
グループ内の最初の制御データブロックの始めに書き込まれた制御ブロックグループの制御ポインタアレイには８つの制御ポインタがある。制御ポインタ及び制御ストリームデータの書き込みアドレスは、おそらく異なる制御データブロックからのものである。制御データブロックは、動的に割り当てられ、それ故、異なるメモリページに存在する。これは、制御ポインタ書き込みと制御ストリームデータ書き込みとの間にメモリページが破壊される機会を増加する。
【００８８】
メモリページの破壊を減少し、制御ストリームデータ書き込み性能を改善するために、制御ストリームデータ書き込み専用のシステムレベルキャッシュを、ここに提案する制御ストリームグループ化方法に使用することができる。
【００８９】
制御ストリームデータキャッシュは、１６方の連想擬似ＬＲＵキャッシュアルゴリズムをシステムレベルキャッシュとして使用する。又、制御ストリームデータキャッシュは、マスク型書き込みも使用し、それ故、キャッシュラインがフラッシュされた後にメモリからデータをロードするためのメモリ読み取りの必要がない。
【００９０】
制御ストリームデータキャッシュのキャッシュラインは、レンダリングの終了時に、フラッシュして無効化する必要がある。マルチコンテクストの場合には、制御ストリームデータキャッシュの各キャッシュ線にコンテクストＩＤを記憶することができる。レンダリング終了時に、現在レンダリングのコンテクストＩＤと同じコンテクストＩＤをもつキャッシュ線だけがフラッシュされ無効化されて、キャッシュ性能を向上させる。
【００９１】
平均的に、制御ストリームデータ書き込みは、６４ＫＢ制御ストリームデータキャッシュで１５％減少されることが実験で示される。
【符号の説明】
【００９２】
１０１：入力データストリーム
１０３：タイルエンジン（ＴＥ）
２００：スクリーン
２０１：マクロタイル
２０２：タイル
３００：領域アレイ
３０１：制御ストリーム
３０２：制御データブロック
４０２：制御ストリーム
６０１：現在データブロック
６０２：次の制御データブロック
８００：ＭＴ０
８０１：タイル
８０２、８０３：三角形ストリップ
８０４：大きな三角形
８０５：マクロタイルエンジンＭＴＥ
８０６：タイルエンジンＴＥ
８０７：メモリ
８０８：３Ｄレンダリングプロセス
【図１】
0005579741.tif 000012
【図２】
0005579741.tif 000013
【図３】
0005579741.tif 000014
【図４】
0005579741.tif 000015
【図５】
0005579741.tif 000016
【図６】
0005579741.tif 000017
【図７】
0005579741.tif 000018
【図８】
0005579741.tif 000019