３次元コンピュータ画像を生成する方法及びシステム
３次元コンピュータ画像を生成する方法及び装置を提供する。画像は、いくつかのオブジェクトを含み、かつ個別区域に分割される。第１の態様では、各オブジェクトに対してメモリに記憶されたオブジェクトデータにリンクする制御データが、一度に２つのオブジェクトに対して導出される。それによって処理及びメモリ使用量が改善される。第２の態様では、一度に２つの個別区域に対する制御データを導出することにより、２つ又はそれよりも多くの個別区域を並行して処理することができる。それによって処理時間が改善される。実際には一方の区域にのみ適用可能である両方の区域に対するデータをフェッチすることを回避するために、制御データ内で符号化が用いられる。第３の態様では、オブジェクトデータは、１つメモリページ上又は２つのメモリページにわたって記憶することができ、制御データは、前者の場合は１つのメモリページアドレスを含み、後者の場合は２つのメモリページアドレスを含む。それによってメモリ使用量が改善される。第４の態様では、各オブジェクトのオブジェクトデータに対して割り当てられた連続部分を有するルックアップテーブルを用いることにより、オブジェクトデータは、２つの不連続メモリページにわたって記憶することができる。それによってもメモリ使用量が改善される。第５の態様では、部分レンダリングが用いられ、かつ部分深度データが記憶されてその後更新される時には、データ記憶域の最後又は次のメモリページへのポイントのいずれかを示すメモリページのリンク部分を用いることにより、深度データは、２つのメモリページにわたって記憶することができる。それによってもメモリ使用量が改善される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元コンピュータ画像を生成する方法及び装置に関する。
【背景技術】
【０００２】
本出願人の英国特許第２２８１６８２号では、３Ｄシーン内の各プリミティブオブジェクトが無限の面の集合で定義されるような光景として見られる多角形に対する３Ｄレンダリングシステムが説明されている。画像が表示されることになる画面の各基本区域（例えば、ピクセル）は、それを通して光線を視点から３Ｄシーン内へ投影させる。次に、投影光線と各面の交点の位置が判断される。これらの交点から、いずれかの交差面がこの基本区域で可視であるか否かを次に判断することが可能である。この基本区域は、次に、判断の結果に応じて表示に向けてシェーディングされる。
【０００３】
このシステムは、各々が面との交点計算を実行することができるいくつかのセルを含むパイプライン型プロセッサに実施することができる。従って、多数の面交点を同時に計算することができる。各セルには、交点検査を実施する面を定義する１組の係数がロードされる。
この構成に対する改善が、本出願人の英国特許第２２９８１１１号に説明されている。この文献では、画像は、部分領域又はタイルに分割され、タイルは、逐次処理することができる。可変タイルサイズを用い、完全なプリミティブオブジェクトの周囲に境界ボックスを投影し、それによって境界ボックス内に収まるタイルのみが処理を必要とすることが提案されている。これは、適切なタイルサイズを選択するために可視画面上のプリミティブオブジェクトの配分を判断することによって行われる。タイル内の各オブジェクトは、面及び頂点を有するいくつかの三角形として記憶される。他の形状も可能である。次に、様々なプリミティブオブジェクトを定義する面が、表示リストとして公知のリストに記憶され、それによって各タイルに対して同一の面を記憶する必要性が回避されるが、これは、多くの面から成る１つのオブジェクトがいくつかのタイルに出現することができると考えられるからである。表示リスト内のプリミティブオブジェクトを識別するオブジェクトポインタも同様に記憶される。タイル毎に１つのオブジェクトポインタリストが存在する。次に、タイルは、各タイル内の全てのプリミティブオブジェクトが処理されるまで、上述の光線投射技術を用いて逐次レンダリングすることができる。これは、特定のタイル内で可視でないことが既知であるオブジェクトをレンダリングする必要がないので有用な方法である。
【０００４】
このシステムに対する更なる改善は、本出願人の国際特許出願番号ＰＣＴ／ＧＢ９９／０３７０７（公開番号ＷＯ２０００／０２８４８３）及びＰＣＴ／ＧＢ２００４／００１０７６（公開番号ＷＯ２００４／０８６３０９）、並びに本出願人の英国特許第２３４３６０３号に提案されており、特定のプリミティブオブジェクトを表示する必要のない境界ボックス内のあらゆるタイルが、レンダリングの前に廃棄される。
【０００５】
図１は、上述の既存のシステムに用いられる種類のプロセッサ１０１を示している。基本的に、３つの構成要素が存在する。タイルアクセラレータユニット（ＴＡ）１０３は、タイル分割作動を実施し、すなわち、適切なタイルサイズを選択して可視画面をタイルに分割し、タイル情報、すなわち、各タイルに関する３Ｄオブジェクトデータを表示リストメモリ１０５へと供給する。画像合成プロセッサ（ＩＳＰ）１０７は、表示リストメモリ内の３Ｄオブジェクトデータを用いて、上述の光線／面交点検査を実施する。この検査により、可視画面の各基本区域に関する深度データが生成される。この後、ＩＳＰ１０７から導出された画像データは、可視であると判断された面にテクスチャリング及びシェーディングデータを適用して画像及びシェーディングデータをフレームバッファメモリ１１１に出力するテクスチャリング及びシェーディングプロセッサ（ＴＳＰ）１０９に供給される。すなわち、ディスプレイの各基本区域の外観が、３Ｄ画像を表すように判断される。
【０００６】
上述のシステムでは、レンダリングされるシーンの複雑さが増大する時に問題が発生する場合がある。複雑なシーンは、各タイルに対してより多くの３Ｄオブジェクトデータを表示リストメモリに記憶することを必要とし、これは、記憶要件が増大することを意味する。表示リストメモリが空間を使い切ってしまった場合、単純に、シーンの一部は、レンダリングされない場合があり、この種類の画像破損は、益々容認できなくなっている。
【０００７】
この問題を解決するために、本出願人の国際特許出願ＰＣＴ／ＧＢ０１／０２５３６（公開番号ＷＯ２００１／０９５２５７）は、部分レンダリングの考えを提案している。タイルのレンダリングが完了する前に、システム（ＩＳＰ及びＴＳＰ）の状態がメモリに記憶され、この状態は、レンダリングを完了するために後の時点で再ロードされる。この処理を「ｚ／フレームバッファロード及び記憶」と呼ぶ。
【０００８】
画面は、各タイルが画面の矩形領域から成るマクロタイルと呼ぶいくつかの領域に分割される。次に、表示リスト内のメモリが、ブロックに分割され、これらは、空き記憶領域リストに列挙される。空き記憶領域からのブロックは、次に、必要に応じてマクロタイルに割り当てられる。タイル分割作動は、各マクロタイルに関連付けられたデータを各ブロックに記憶する。（ＴＡによって実施されるタイル分割作動は、表示リストメモリを埋め、従って、時によっては「メモリ割り当て」と呼ばれる。）表示リストメモリが埋め尽くされるか又は何らかの所定の閾値に達すると、システムは、マクロタイルを選択し、ｚ／フレームバッファロードを実行し、マクロタイルの内容をそれをｚ／フレームバッファ記憶作動を用いて保存する前にレンダリングする。すなわち、マクロタイルに関する深度データが、それまでに表示リスト内にロードされたデータに従って記憶される。そのようなレンダリングの完了時に、システムは、このマクロタイルに関連付けられたあらゆるメモリブロックを空にして、それによって更に別の記憶に向けてこれらのメモリブロックを利用可能にする。（レンダリング処理は、表示リストメモリ空間を解放するので、それは、「メモリ割り当て解除」として公知である。）従って、各タイルに対するシーンは、いくつかのタイル分割作動とそれに続く部分レンダリングによって構成される。各部分レンダリングは、記憶された深度データを更新する。これは、メモリ消費に対して上限が課せられ、システムによって消費されるメモリ帯域幅も最小にされることを意味する。
【０００９】
部分レンダリングシステムに用いられる種類のプロセッサの一例を図２に示す。このプロセッサは、図１の改訂バージョンであることが分る。ｚバッファメモリ２０９は、ｚ圧縮／解凍ユニット２１１を通じてＩＳＰ２０７にリンクされる。これは、システムが複雑なシーンをレンダリングし、かつ表示リストメモリ２０５が、特定のタイルに対して処理する必要がある全ての面を収容するほど十分大きくない時に作動を始める。表示リストには、それが実質的に一杯になるまで（又は、所定の閾値に達するまで）全てのタイルに対してＴＡ２０３によってデータがロードされることになる。しかし、これは、初期データの一部分を表すのみであろう。画像は、ＩＳＰ２０７によって一度に１つのタイルでレンダリングされる。各タイルに関する出力データは、テクスチャデータを用いてタイルをテクスチャリングするＴＳＰ２１３に供給される。それと同時に、画像データは、未完成であるから、ＩＳＰ２０７からの結果（すなわち、深度データ）は、一時的な記憶に向けて圧縮／解凍ユニット２１１を通じてバッファメモリ２０９に記憶される。残りのタイルのレンダリングは、次に、未完了の画像データを用いて、全てのタイルがレンダリングされてフレームバッファメモリ２１５及びｚバッファメモリ２０９に記憶されるまで継続される。
【００１０】
次に、表示リストの最初の部分が廃棄され、更に別の画像データがその中に読み込まれる。ＩＳＰ２０７によって各タイルに対して処理が順次実行される時に、ｚバッファメモリ２０９からのデータの関連の部分は、それを表示リストメモリ２０５からの新しい画像データと組み合わせることができるように、ｚ圧縮／解凍ユニット２１１を通じてロードされる。次に、各タイルに関する新しい深度データがＴＳＰ２１３に供給され、それは、データをフレームバッファ２１５へ供給する前にデータをテクスチャデータと組み合わせる。
【００１１】
この処理は、全ての画像データがレンダリングされ終わるまで、シーン内の全てのタイルに対して継続される。すなわち、ｚバッファメモリは、一時的記憶領域を埋めて、それによって特に複雑なシーンをレンダリングするのに必要になると考えられるものよりも小さい表示リストメモリを用いることを可能にすることが分る。圧縮／解凍ユニット２１１は、任意的であるが、それは、より小さいｚバッファメモリを用いることを可能にする。更に、繰延ピクセル処理が有効にされて、あらゆる冗長なピクセル作動を排除する。
【００１２】
従って、国際特許出願番号ＰＣＴ／ＧＢ０１／０２５３６に解説されているように、表示リストメモリが埋め尽くされるか又はある一定の閾値に達した状態で、システムは、一部の表示リストメモリを解放するために、レンダリングするマクロタイルを選択する。この出願では、レンダリングするマクロタイルの選択は、いくつかの要因に依存し、例えば、最も多くのメモリを空き記憶領域へと解放して戻すことになるマクロタイルを選択することができる。
【００１３】
このシステムに対する更なる改善が、本出願人の英国特許出願第０６１９３２７．０号に示されている。この構成に用いられるプロセッサの概略的な例を図３に示す。システム３０１は、図２のものと同様であり、ＴＡ３０３，ＩＳＰ３１１，ＴＳＰ３１３、及び「フレームバッファ」３１５を含むことが分る。しかし、この場合、「表示リストメモリ」３０５及び「Ｚバッファメモリ」３０７は、両方共に「パラメータメモリ」３０９と呼ぶメモリの単一ヒープの一部である。パラメータメモリ内での「表示リスト」と「Ｚバッファ」の間の割り当ては、必要に応じてのものであり、それによってメモリ使用がより効率的になる。図３は、図２におけるようなｚ圧縮／解凍ユニットを示していないが、そのようなユニットを含めることができると考えられる。
【００１４】
更に、本出願人の英国特許出願第０６１９３２７．０号では、表示リストメモリは、ブロックを必要とする各マクロタイルのためのブロック、及び同じく全体リストを含む。オブジェクトデータは、１つよりも多くのマクロタイルを横断することが可能である。この場合、オブジェクトデータは、１つよりも多くのマクロタイルに存在するオブジェクトデータのみを収容する全体リストに割り当てられる。従って、表示リストは、マクロタイルに全体リストを加えたものへとグループ分けされる。マクロタイル内の全てのオブジェクト及び制御ストリームデータは、所定のマクロタイル内に属するタイルによってのみアドレス指定されることになり、１つよりも多くのマクロタイルに属するあらゆるオブジェクトデータは、全体リストに存在し、これらのデータは、あらゆる制御ストリームからアドレス指定することができる。これは、同じくより効率的なメモリ使用及びアクセスに役立つ。
【００１５】
図４は、英国特許第０６１９３２７．０号に説明されているシステムの特定の例を示している。この構成は、「動的パラメータマネージャ」ＤＰＭ４１１，ＩＳＰ４０７、「マクロタイル分割エンジン」４０３、「タイル分割エンジン」ＴＥ４０５、及びメモリ４０９を含む。一般的には、ＭＴＥ４０３は、各マクロタイルに対してプリミティブオブジェクトデータを生成し、これらのデータをメモリ４０９の適切な部分に入力する。ＴＥ４０５は、ＭＴＥ４０３からのプリミティブオブジェクトデータを用いて各タイルに関する制御ストリームデータを生成し、これらのデータをメモリ４０９に入力する。従って、ＭＴＥとＴＥは、各マクロタイル内の各タイルに対する記憶域が適切なオブジェクトデータ記憶域を指すように、一緒にタイルアクセラレータとして作用する。ＩＳＰ４０７は、オブジェクトデータを用いて深度データを導出し、これらのデータをメモリ４０９のｚバッファ部分に記憶する。
【００１６】
次に、図４の作動のより詳細な説明を図５への参照も行いながら提供することにする。図５は、表示されるいくつかの三角形状を示している。各三角形状は、プリミティブ又は単純に形状として公知である。画面は、３０個のタイルに分割される。プリミティブは、２つのプリミティブオブジェクトに分割される。第１のプリミティブオブジェクトは、頂点５０１，５０３，５０５，５０７，及び５０９を有する。第２のプリミティブオブジェクトは、頂点５１１，５１３，５１５，５１７，及び５１９を有する。すなわち、各プリミティブオブジェクトは、いくつかのプリミティブを含む。
【００１７】
第１段階では、頂点及びプリミティブのデータが入力される（４０１において）。図５における三角形は、頂点５０１から５０９及び頂点５１１から５１９を有する２つのプリミティブオブジェクトへとグループ分けされる。プリミティブオブジェクトの各々は、ＭＴＥ４０３により、メモリ空間を適切に割り当てるＤＰＭ４１１を用いてメモリ内に書き込まれ、メモリアドレスは、次のタイル分割段階へと渡される。
【００１８】
第２段階では、ＭＴＥは、頂点５０１から５０９及び頂点５１１から５１９を画面空間内へと不可視であるあらゆる頂点（この事例では存在しない）を画面外として除去しながら処理する。既に解説したように、プリミティブ及び頂点データをフェッチする上でメモリ帯域幅の影響を最小にするために、プリミティブは、マクロタイル内のプリミティブオブジェクトへとグループ分けされる。一般的に、各マクロタイルは、画面サイズの４分の１又は１６分の１である。プリミティブオブジェクトがマクロタイルと交差する場合には、これらのプリミティブオブジェクトのデータは、全体リストに一度だけ書き込むことができる。従って、４０３では、プリミティブオブジェクト（最大数の頂点を有する）は、マクロタイルに関連付けられたメモリ４０９の一部に書き込まれる。各マクロタイルに関連付けられたメモリページは、要求に応じてＤＰＭ４１１によって割り当てられる。頂点及びプリミティブの数は、プリミティブオブジェクトのメモリアドレス（これらは、頂点ポインタとして公知である）と共にＴＥ４０５に送られて、プリミティブオブジェクトが可視であるタイルの制御ストリームに適用される。
【００１９】
第３段階では、ＴＥ４０５は、制御データを各タイルに書き込む。ＭＴＥ４０３において書き込まれるプリミティブオブジェクトからの各プリミティブは、プリミティブオブジェクトの境界ボックスの内側にある各タイルと照合される。タイル内でいずれか可視のプリミティブが存在する場合には、制御データは、そのタイルに関連付けられた制御ストリームに書き込まれる。従って、図５における頂点５０１から５０９を有する第１のプリミティブでは、このプリミティブオブジェクトに関連付けられた制御データは、Ｃ１及びＣ６のようなタイルではなく、Ｃ２，Ｃ３，Ｃ４，及びＣ５（陰付き灰色の）のようなタイルのうちの一部にのみ書き込まれる。同様に、図５における頂点５１１から５１９を有する第２のプリミティブオブジェクトでは、制御データは、Ｂ４及びＢ５のようなタイルのうちの一部に対して書き込まれ、Ｂ６のような他のものには書き込まれない。この段階で書き込まれる制御データは、プリミティブオブジェクト内の頂点及びプリミティブの数に関するプリミティブオブジェクトヘッダ、及び書き込まれるプリミティブオブジェクトのメモリアドレスへの頂点ポインタを含む。ＤＰＭ４１１による制御ストリームでは、別々のメモリ空間が、各タイルに割り当てられる。
【００２０】
最終的に、第４段階では、ＩＳＰ４０７によって３Ｄ画像処理が実施される。３Ｄ処理は、画面内の各タイルに対して実施される。タイル分割のためのデータ構造の概要を示している図６を参照すると、３Ｄ処理は、領域アレイ６０１からの各タイルに対して実施される。各タイルに対する制御データは、図６におけるいくつかの制御ストリーム０からＭを含む。各制御ストリームは、プリミティブオブジェクトヘッダ及び頂点ポインタを含み、各タイルに対する制御データ内の制御ストリーム数は、各タイル内に収まるプリミティブオブジェクトの数に依存する。ＩＳＰは、各タイル６０３の制御ストリームを通して全探索を行い、制御データ６０５内の頂点ポインタによってメモリアドレスから頂点及びプリミティブのデータを読み取る。従って、図５を再度参照すると、タイルの一部は、いかなるプリミティブも含まず、Ｂ２のような一部のタイルは、１つのプリミティブオブジェクトだけからのプリミティブを含み、Ｃ２及びＣ３のような他のタイルは、両方のプリミティブオブジェクトからのプリミティブを含む。隠れ面除去、テクスチャリング、及びシェーディングのような画像処理作動は、タイル内で有効なプリミティブオブジェクトからの全てのプリミティブに対して実施される。
【００２１】
上述の公知の構成は、多くの利点を有するが、一部の欠点を確かに有する。タイル分割システムは、制御データに関するメモリ書込みが１つの制御ストリームから別のものへとジャンプするように、各タイル内のプリミティブオブジェクトを処理する。これは、メモリバーストサイズを突破し、メモリアクセスの効率を低下させる。
また、大きいプリミティブ形状が画面上のタイルの多くを覆う時には、制御データは、多数回繰り返される。特定のメモリブロック内の頂点及びプリミティブのデータは、３Ｄ画像処理中に多くのタイルに対して多数回読み取られる可能性がある。この繰返しによってメモリ帯域幅が拡大する。一方、所定のタイル内で、プリミティブオブジェクトからの頂点及びプリミティブのうちの一部だけしか可視ではなかった場合には、プリミティブオブジェクトデータ全体をフェッチするのは効率的ではない。
【００２２】
マクロタイルに対して頂点及びプリミティブのデータに向けて用いられるメモリページは、要求に応じて割り当てられ、従って、必ずしも連続したページであるわけではない。特定のプリミティブオブジェクトからのデータがページ境界と交差するのを防ぐために、現在のページ上にプリミティブオブジェクト全体に対する十分な空間が存在しない場合には、空き記憶領域からの新しいページが割り当てられる必要がある。この割り当てによって浪費が生じる。また、パイプラインシステムでは、プリミティブオブジェクトの正確なサイズは、オブジェクト全体が実際に書き込まれるまでは既知ではなく、従って、開始時点で最大サイズを仮定する必要がある。この仮定によって更に別の浪費が生じる。
【００２３】
図２を参照して冒頭で解説した部分レンダリングでは、圧縮／解凍ユニット２１１が、ｚデータを圧縮してそれをメモリ２０９内に書込み始める時に、タイルに関する圧縮ｚデータのサイズが既知ではない点で類似の問題が存在する。タイルに関する圧縮データがメモリページと交差するのを回避するために、圧縮／解凍ユニット２１１は、タイルの開始時点に現在のメモリページ内に十分な空間が存在するか否かを検査する必要がある。この検査は、圧縮ｚデータに対して最大サイズを仮定する必要があり、それによって浪費が生じる。
【先行技術文献】
【特許文献】
【００２４】
【特許文献１】英国特許第２２８１６８２号
【特許文献２】英国特許第２２９８１１１号
【特許文献３】ＰＣＴ／ＧＢ９９／０３７０７（ＷＯ２０００／０２８４８３）
【特許文献４】ＰＣＴ／ＧＢ２００４／００１０７６（ＷＯ２００４／０８６３０９）
【特許文献５】英国特許第２３４３６０３号
【特許文献６】ＰＣＴ／ＧＢ０１／０２５３６（ＷＯ２００１／０９５２５７）
【特許文献７】英国特許出願第０６１９３２７．０号
【特許文献８】ＧＢ０６０６１９３２７．０
【発明の概要】
【発明が解決しようとする課題】
【００２５】
本発明者は、上述の公知のシステムに様々な改善を加えることができると考えられることを見出した。
【課題を解決するための手段】
【００２６】
本発明の第１の態様により、生成される画像が少なくとも１つの形状を各々含む複数のオブジェクトを含む３次元コンピュータ画像を生成する方法を提供し、本方法は、ａ）画像を複数の矩形区域に細分割し、各矩形区域を複数の小区域に細分割する段階と、ｂ）画像内のオブジェクトの少なくとも一部に対して、オブジェクト内の各形状に関する面データ及び頂点データと、面データと頂点データの間のポインタとを含むオブジェクトデータをメモリに記憶する段階と、ｃ）画像内の各小区域に対して、ｉ）段階ｂ）で記憶されたオブジェクトデータから、２つ又はそれよりも多くのオブジェクトに関するオブジェクトデータを抽出する段階、ｉｉ）画像内の小区域のうちのどれが、段階ｉ）でオブジェクトデータが抽出されたオブジェクトのうちの１つ又は全てを含むかを計算する段階、ｉｉｉ）段階ｉｉ）で計算された小区域の各々に対して、小区域内に含まれるオブジェクト又はその各々に関するオブジェクトデータにリンクする制御データセットを導出する段階、及びｉｖ）ｂ）における全てのオブジェクトに対して制御データが導出されるまで段階ｉ）からｉｉｉ）を繰り返す段階によって小区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データを導出する段階と、ｄ）制御データ及びオブジェクトデータから各矩形区域に関する深度データを導出する段階と、ｅ）表示に向けて深度データから画像データ及びシェーディングデータを導出する段階とを含む。
【００２７】
制御データは、２つ又はそれよりも多くのオブジェクトから一度に導出されるので、メモリアクセスが改善される。段階ｉｉｉ）で導出される各制御データセットは、段階ｉ）でオブジェクトデータが抽出された小区域内に含まれる全てのオブジェクトのオブジェクトデータへのリンクを含む。
好ましくは、段階ｉｉｉ）で導出された各制御データセットにおける最終メモリ位置に、小区域に関する次の制御データセットへのポインタが設けられ、最終メモリ位置は、キャッシュに記憶される。すなわち、制御データは、段階ｉ）でオブジェクトデータが抽出された小区域内に含まれる全てのオブジェクトのオブジェクトデータへのリンクを含むことになるので、この小区域内に収まる１つよりも多くのオブジェクトが存在したとしても、キャッシュは、一度アクセスするだけでよい。
【００２８】
一実施形態では、段階ｂ）は、画像の全てのオブジェクトに対してオブジェクトデータをメモリに記憶する段階を含む。これは、記憶される全てのオブジェクトデータに対して十分なメモリ空間が存在する場合のことである。
【００２９】
代替実施形態では、段階ｂ）は、画像内の所定数のオブジェクトに対してオブジェクトデータをメモリに記憶する段階を含み、本方法は、画像内の全てのオブジェクトに対してオブジェクトデータを記憶し終わるまで、段階ｅ）の前に段階ｂ）、段階ｃ）、及び段階ｄ）を繰り返す段階を更に含む。所定数は、利用可能メモリサイズによって判断することができる。
１つの好ましい実施形態では、段階ｉ）は、段階ｂ）で記憶されたオブジェクトデータから２つのオブジェクトに関するオブジェクトデータを抽出する段階を含む。
【００３０】
本発明の第１の態様により、生成される画像が少なくとも１つの形状を各々含む複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置も提供し、装置は、ａ）画像を複数の矩形区域に細分割し、各矩形区域を複数の小区域に細分割するための手段と、ｂ）画像内のオブジェクトの少なくとも一部に対して、オブジェクト内の各形状に関する面データ及び頂点データと、面データと頂点データの間のポインタとを含むオブジェクトデータをメモリに記憶するための手段と、ｃ）画像内の各小区域に対して、小区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データを導出するために、ｉ）記憶するための手段によって記憶されたオブジェクトデータから、２つ又はそれよりも多くのオブジェクトに関するオブジェクトデータを抽出し、ｉｉ）画像内の小区域のうちのどれが、オブジェクトデータが抽出されたオブジェクトのうちの１つ又は全てを含むかを計算し、ｉｉｉ）ｉｉ）で計算された小区域の各々に対して、小区域内に含まれるオブジェクト又はその各々に関するオブジェクトデータにリンクする制御データセットを導出し、かつｉｖ）ｂ）における全てのオブジェクトに対して制御データが導出されるまでｉ）からｉｉｉ）を繰り返すように構成された導出手段と、ｄ）制御データ及びオブジェクトデータから各矩形区域に関する深度データを導出するための手段と、ｅ）表示に向けて深度データから画像データ及びシェーディングデータを導出するための手段とを含む。
【００３１】
本発明の第２の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法を提供し、本方法は、ａ）画像を複数の個別区域に細分割する段階と、ｂ）画像内のオブジェクトの少なくとも一部に対して、オブジェクトデータをメモリに記憶する段階と、ｃ）一度に２つの個別区域に対して、２つの個別区域内のオブジェクトデータにリンクする制御データを導出する段階と、ｄ）ｉ）制御データ及びオブジェクトデータから第１の個別区域に関する深度データを導出し、更に、表示に向けて深度データから第１の個別区域に関する画像データ及びシェーディングデータを導出し、かつｉｉ）制御データ及びオブジェクトデータから第２の個別区域に関する深度データを導出し、更に、表示に向けて深度データから第２の個別区域に関する画像データ及びシェーディングデータを導出することを並行して行うことにより、２つの個別区域内に３次元コンピュータ画像を生成する段階と、ｅ）全ての個別区域に対して画像が生成されるまで段階ｃ）及び段階ｄ）を繰り返す段階とを含む。
【００３２】
ｄ）において２つの個別区域が並行して処理されるので、処理は、より迅速に達成される。
各個別区域は、好ましくは、矩形である。２つの個別区域は、好ましくは、１つが左に、１つが右に隣接する矩形の個別区域である。
１つの好ましい実施形態では、各オブジェクトは、複数の頂点を有する複数の形状を含み、段階ｃ）で導出された制御データは、各オブジェクトに対して、オブジェクトのどの形状が個別区域のうちのどれに収まるかに関する指示、及びオブジェクトのどの頂点が個別区域のうちのどれに収まるかに関する指示を含む。
形状及び頂点が何処に収まるかというこの指示は、深度データが導出される時に、処理されている個別区域内に実際に収まらない形状又は頂点に関するデータを取得するいかなる不要なデータフェッチも存在しないことを意味する。
【００３３】
一実施形態では、制御データは、ヘッダ部分及びペイロード部分を含む。好ましくは、ヘッダ部分は、オブジェクトのどの頂点が個別区域のうちのどれに収まるかに関する指示を含む。
好ましくは、オブジェクトの形状のうちの一部が、個別区域の各々に収まるか、又はオブジェクトの形状のうちの全てが、個別区域のうちの１つのみに収まる場合には、ペイロードは、オブジェクトのどの形状が個別区域のうちのどれに収まるかに関する指示を含む。
【００３４】
本発明の第２の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置も提供し、装置は、ａ）画像を複数の個別区域に細分割するための手段と、ｂ）画像内のオブジェクトの少なくとも一部に対して、オブジェクトデータをメモリに記憶するための手段と、ｃ）一度に２つの個別区域に対して、２つの個別区域内のオブジェクトデータにリンクする制御データを導出するための導出手段と、ｄ）２つの個別区域内に３次元コンピュータ画像を生成するための第１の画像発生器を第２の画像発生器と並列に備える画像発生器とを含み、第１の画像発生器は、第１の個別区域に対して、制御データ及びオブジェクトデータから深度データを導出し、更に、表示に向けて深度データから第１の個別区域に関する画像データ及びシェーディングデータを導出するように構成され、第２の画像発生器は、第２の個別区域に対して、制御データ及びオブジェクトデータから深度データを導出し、更に、表示に向けて深度データから第２の個別区域に関する画像データ及びシェーディングデータを導出するように構成される。
【００３５】
本発明の第３の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法を提供し、本方法は、ａ）画像を複数の個別区域に細分割する段階と、ｂ）画像内のオブジェクトの少なくとも一部に対して、第１のエンジンが、メモリページに分割されているメモリにオブジェクトデータを記憶する段階と、ｃ）ｂ）でオブジェクトデータが記憶された各オブジェクトに対して、オブジェクトデータが１つのメモリページ上に記憶された場合に、第１のエンジンが、このメモリページアドレスを第２のエンジンに送る段階、又はオブジェクトデータが２つのメモリページ上に記憶された場合に、第１のエンジンが、これらのメモリページアドレスを第２のエンジンに送る段階と、ｄ）画像内の各個別区域に対して、第２のエンジンが、ｂ）で記憶されたオブジェクトデータが１つのメモリページ上に記憶された場合に１つのメモリページアドレスを含み、ｂ）で記憶されたオブジェクトデータが２つのメモリページ上に記憶された場合に２つのメモリページアドレスを含む、小区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データを導出する段階と、ｅ）各個別区域に対して、制御データ及びオブジェクトデータから深度データを導出する段階と、ｆ）表示に向けて深度データから画像データ及びシェーディングデータを導出する段階とを含む。
【００３６】
オブジェクトが２つのメモリページに記憶されることは、データが２つのページにわたって延びる（データが複写されるのではなく）ことを意味する。ｂ）において記憶されるオブジェクトデータは、単一のメモリページ上、又は２つのメモリページにわたって記憶することができるのでメモリ浪費が低減する。２つのメモリページアドレスが制御データ内に含まれるので、画像が処理される時に正しいメモリページを得ることができる。
【００３７】
本方法は、メモリマネージャが、メモリのページを画像内のオブジェクトに割り当てる段階を更に含む。この場合、メモリマネージャは、２つのメモリページを各オブジェクトに自動的に割り当てることができる。実際に、オブジェクトデータが１つのメモリページしか必要としない場合には、第２のメモリページは、単純に次のオブジェクトデータセットに向けて用いられる。
好ましくは、深度データを導出する段階ｅ）は、個別区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データが１つ又は２つのいずれのメモリページアドレスを含むか否かを判断する段階を含む。
【００３８】
本発明の第３の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置も提供し、装置は、ａ）画像を複数の個別区域に細分割するための手段と、ｂ）画像内のオブジェクトの少なくとも一部に対して、オブジェクトデータをメモリに記憶するための第１のエンジンと、ｃ）小区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データを導出するための第２のエンジンと、ｄ）各個別区域に対して、制御データ及びオブジェクトデータから深度データを導出するための手段と、ｆ）表示に向けて深度データから画像データ及びシェーディングデータを導出するための手段とを含み、メモリは、メモリページに分割され、第１のエンジンは、オブジェクトデータが記憶された各オブジェクトに対して、ｉ）オブジェクトデータが１つのメモリページ上に記憶された場合に、このメモリページアドレスを第２のエンジンに送り、かつｉｉ）オブジェクトデータが２つのメモリページ上に記憶された場合に、これらのメモリページアドレスを第２のエンジンに送り、制御データは、第１のエンジンによって記憶されたオブジェクトデータが１つのメモリページ上に記憶された場合に、１つのメモリページアドレスを含み、第１のエンジンによって記憶されたオブジェクトデータが２つのメモリページ上に記憶された場合に、２つのメモリページアドレスを含む。
【００３９】
装置は、メモリのページを画像内のオブジェクトに割り当てるためのメモリマネージャを更に含むことができる。メモリマネージャは、２つのメモリページを各オブジェクトに自動的に割り当てるように構成することができる。
好ましくは、深度データを導出するための手段は、個別区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データが１つ又は２つのいずれのメモリページアドレスを含むか否かを判断するように構成される。
【００４０】
本発明の第３の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法も提供し、本方法は、ａ）画像を複数の個別区域に細分割する段階と、ｂ）メモリページに分割され、かつルックアップテーブルを含むメモリを準備する段階と、ｃ）メモリマネージャが、ルックアップテーブル内の２つ又はそれよりも多くの連続部分を各個別区域に割り当て、ルックアップテーブル内の各割り当てられた部分が、その個別区域に関するオブジェクトデータを記憶するために利用可能なメモリページを指し示す段階と、ｄ）画像内のオブジェクトの少なくとも一部に対して、第１のエンジンが、各個別区域に関するオブジェクトデータを段階ｃ）でその個別区域に割り当てられたメモリページに記憶する段階と、ｅ）各個別区域に対して、第１のエンジンが、ルックアップテーブル内の２つ又はそれよりも多くの割り当て部分のメモリアドレスを第２のエンジンに送る段階と、ｆ）画像内の各個別区域に対して、第２のエンジンが、第１のエンジンから送られたメモリアドレスを用いて、小区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データを導出する段階と、ｇ）画像内の各個別区域に対して、第１のエンジンから送られたメモリアドレスを用いて、制御データ及びオブジェクトデータから深度データを導出する段階と、ｈ）表示に向けて深度データから画像データ及びシェーディングデータを導出する段階とを含む。
【００４１】
各個別区域に割り当てられた連続部分を有するルックアップテーブルを用いることにより、この個別区域に関するオブジェクトデータが記憶される実際のメモリページは、連続のものである必要はない。これは、メモリページが必ずしも連続するわけではない場合であっても、オブジェクトデータが２つのメモリページに及ぶことができることを意味する。それによってメモリ使用量が改善され、浪費が低減する。本明細書では、順序又は一連における次のものを意味するのに「連続」という用語を用いており、すなわち、ルックアップテーブル内の２つ又はそれよりも多い連続部分は、ルックアップテーブル内で一方が他方に続く隣接部分である。
【００４２】
本発明の第３の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置も提供し、装置は、ａ）画像を複数の個別区域に細分割するための手段と、ｂ）メモリページに分割され、かつルックアップテーブルを含むメモリと、ｃ）ルックアップテーブル内の各割り当てられた部分が、その個別区域に関するオブジェクトデータを記憶するのに利用可能なメモリページを指し示し、ルックアップテーブル内の２つ又はそれよりも多くの連続部分を各個別区域に割り当てるためのメモリマネージャと、ｄ）各個別区域に対して、画像内のオブジェクトの少なくとも一部に関するオブジェクトデータをメモリマネージャによってその個別区域に割り当てされたメモリページに記憶するように構成された第１のエンジンと、ｅ）各個別区域に対して、ルックアップテーブル内の２つ又はそれよりも多くの割り当てられた部分のメモリアドレスを第１のエンジンから受け取るように構成され、更に、メモリアドレスを用いて、その個別区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データを導出するように構成された第２のエンジンと、ｇ）メモリアドレスを用いて、画像内の各個別区域に関する制御データ及びオブジェクトデータから深度データを導出するための手段と、ｈ）表示に向けて深度データから画像データ及びシェーディングデータを導出するための手段とを含む。
【００４３】
本発明の第４の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法を提供し、本方法は、ａ）画像を複数の個別区域に細分割する段階と、ｂ）画像内のオブジェクトの少なくとも一部に対して、オブジェクトデータを第１のメモリに記憶する段階と、ｃ）オブジェクトデータから各個別区域に関する深度データを導出する段階と、ｄ）各々がリンク部分として割り当てられた部分を含む複数のメモリページを含む、深度データを記憶するための第２のメモリを準備する段階と、ｅ）個別区域に関する深度データが１つのメモリページ上に記憶された場合に、そうであることをこのメモリページのリンク部分内に示し、個別区域に関する深度データが１つよりも多くのメモリページ上に記憶された場合に、この個別区域に対する各メモリページのリンク部分を用いて、この個別区域に対する次のメモリページを指し示す、各個別区域に関する深度データを第２のメモリに記憶する段階と、ｆ）更に別のオブジェクトデータを第１のメモリ内にロードして、既存の内容のうちの少なくとも一部を置換する段階と、ｇ）各個別区域に対して、この個別区域に対する上述の又は各メモリページのリンク部分を読み取ることにより、記憶された深度データを取り出す段階と、ｈ）新しいオブジェクトデータ及び記憶された深度データから最新の深度データを導出し、最新の深度データを記憶して過去に記憶された深度データを置換する段階と、ｉ）メモリ内にロードされる更なるオブジェクトデータがなくなるまで段階ｅ）、段階ｆ）、段階ｇ）、及び段階ｈ）を繰り返す段階と、ｊ）表示に向けて深度データから画像データ及びシェーディングデータを導出する段階とを含む。
【００４４】
本発明の第４の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置も提供し、装置は、ａ）画像を複数の個別区域に細分割するための手段と、ｂ）画像内のオブジェクトの少なくとも一部に関するオブジェクトデータを記憶するための第１のメモリと、ｃ）オブジェクトデータから各個別区域に関する深度データを導出するための手段と、ｄ）各々がリンク部分として割り当てられた部分を含む複数のメモリページを含む、深度データを記憶するための第２のメモリと、ｅ）個別区域に関する深度データが１つのメモリページ上に記憶された場合に、そうであることをこのメモリページのリンク部分内に示し、個別区域に関する深度データが１つよりも多くのメモリページ上に記憶された場合に、この個別区域に対する各メモリページのリンク部分を用いて、この個別区域に対する次のメモリページを指し示す、各個別区域に関する深度データを第２のメモリに記憶するための手段と、ｆ）更に別のオブジェクトデータを第１のメモリ内にロードして、既存の内容のうちの少なくとも一部を置換するための手段と、ｇ）各個別区域に対して、この個別区域に対する上述の又は各メモリページのリンク部分を読み取ることにより、記憶された深度データを取り出すための手段と、ｈ）新しいオブジェクトデータ及び記憶された深度データから最新の深度データを導出し、最新の深度データを記憶して過去に記憶された深度データを置換するための手段と、ｉ）表示に向けて深度データから画像データ及びシェーディングデータを導出するための手段とを含む。
本発明の一態様に関連して説明した態様は、本発明の別の態様にも適用可能である。
既存のシステムは、図１から６を参照して既に説明した。
本発明の例示的な実施形態は、図７から図１１を参照して以下に説明する。
【図面の簡単な説明】
【００４５】
【図１】第１の公知のレンダリング及びテクスチャリングシステムの概略図である。
【図２】図１のシステムに対して改善をもたらす第２の公知のレンダリング及びテクスチャリングシステムの概略図である。
【図３】図２のシステムに対して改善をもたらす第３の公知のレンダリング及びテクスチャリングシステムの概略図である。
【図４】図３のレンダリング及びテクスチャリングシステムの詳細図である。
【図５】タイル、プリミティブ、及びプリミティブオブジェクトを示すシーンの概略図である。
【図６】タイル分割のためのデータ構造の外観図である。
【図７】本発明の第１の態様の実施形態の方法の流れ図である。
【図８】本発明の第２の態様の実施形態による２つの半タイルを用いたタイル分割のためのデータ構造の外観図である。
【図８ａ】本発明の第２の態様の実施形態におけるプリミティブオブジェクトヘッダ構造の図である。
【図８ｂ】本発明の第２の態様の実施形態における２つの１６ビットプリミティブ半マスクが存在する場合のプリミティブワードマスク構造の図である。
【図８ｃ】本発明の第２の態様の実施形態における１つの３２ビットプリミティブマスクが存在する場合のプリミティブワードマスク構造の図である。
【図８ｄ】本発明の第２の態様の実施形態における１つの３２ビットプリミティブマスクが存在する場合の別のプリミティブワードマスク構造の図である。
【図８ｅ】本発明の第２の態様の実施形態における２つの３２ビットプリミティブマスクが存在する場合のプリミティブワードマスク構造の図である。
【図９】プリミティブオブジェクトに割り当てられた２つの頂点ポインタを示す本発明の第３の態様の実施形態の概略図である。
【図１０】メモリページ割り当てを連続的にするルックアップテーブルの使用を示す本発明の第３の態様の代替実施形態の概略図である。
【図１１】本発明の第４の態様の実施形態による圧縮ｚバッファにおけるページリンクの概略図である。
【発明を実施するための形態】
【００４６】
上述のように、本発明の第１の態様によると、制御ストリームデータを導出する方法によってメモリ使用量を改善することができる手法が達成される。ここで、第１の態様の実施形態を以下に説明する。
図４、図５、及び図６を参照して上述したように、標準的な構成では、ＴＥ４０５は、ＭＴＥ４０３からプリミティブオブジェクト（各々がいくつかのプリミティブを含む）を取得し、このプリミティブオブジェクトをレンダリングするのに必要な最少タイル数を計算する。例えば、図５の第１のプリミティブオブジェクトをレンダリングするのに必要なタイルはＣ２，Ｃ３，Ｃ４，Ｃ５，Ｂ３，Ｂ４，Ｂ５，及びＡ４である。次に、この最少タイルリストは処理されて、プリミティブオブジェクトのアドレスへの頂点ポインタが、タイルに存在するプリミティブを表すプリミティブオブジェクトヘッダと共に動的割り当てメモリに制御ストリームとして書き込まれる。これを図６に示す。
【００４７】
各タイルは、制御ストリームデータに向けて用いられる独自のメモリブロックを有し、これらのメモリブロックは、要求に応じてＤＰＭ４１１によって割り当てられる。特定のタイルに対する制御ストリームに追加される新しいデータが、ＤＰＭ４１１によって割り当てられた現在のメモリブロックを超えることになる場合には、新しい割り当てが要求され、古い制御ストリームは、ストリームリンクを用いて新しい割り当てにリンクされる。ＭＴＥ４０３が終了信号によってシーンの終了を示すと、全てのタイルが処理されて、有効領域内のタイルに対する制御システムが終了ワードで終了される。
【００４８】
大きいプリミティブを含むプリミティブオブジェクトでは、プリミティブオブジェクトが１つよりも多くのマクロタイルを覆う時に、全体リストを用いることができるが、制御ストリームデータは、プリミティブが収まる全てのタイルに対して数回書き込まれることを必要とする可能性がある。極端な場合には、制御ストリームデータを画面上の全てのタイルに対して書き込まなければならない場合がある。制御ストリームデータのそのような繰返しは、効率的なメモリ使用をもたらさない。
【００４９】
ＧＢ０６０６１９３２７．０から、ＴＥに追加された小さいキャッシュである「テールポインタキャッシュ（ＴＰＣ）」を用いてメモリアクセスを改善することができることは公知である。タイル内の制御ストリームの最後のメモリ位置が記憶され、次に、メモリをアクセスする必要がある時に、「テールポインタキャッシュ」から読み取られる。それによってＴＥからの主メモリアクセスが低減する。ＴＰＣの付設により、必要な主メモリアクセスの回数は低減するが、１つのタイルから次のものへの制御ストリーム間の頻繁なアドレス変更は改善されない。制御ストリームの書込みは配分されるので、ＴＰＣの付設は、幅広のバスを有するメモリインタフェースに対してはそれ程有効ではない。例えば、メモリインタフェースが１２８ビット幅であった場合には、２つの３ビットワード制御データを各タイル内に書き込む段階は、メモリ書込みの殆どを最大バーストのものにしないことになる（３２ビット×２は１２８ビットを大きく下回る）。この場合、１２８ビットのバースト書込みで有効な６４ビットのみを更新するために、バースト書込みの一部をマスクする必要がある（すなわち、未使用６４ビットを）。メモリモジュールにおけるこの種のマスクされたバースト書込みには、性能低下が生じる可能性がある。
【００５０】
本発明のこの実施形態では、ＴＥは、ＭＴＥから一度に２つのプリミティブオブジェクト（１つではなく）を取得する。ＴＥは、特定のタイルに対して２つのプリミティブオブジェクトを同時に処理する。従って、各プリミティブオブジェクトを取得して、このプリミティブオブジェクトが収まるタイルの全てを通じて作業し、次に、別のプリミティブオブジェクトを取得し、以降同様に続ける代わりに、ＴＥは、２つのプリミティブオブジェクトを一度に取得し、それによってメモリ使用量及びアクセスが改善される。
【００５１】
図５を参照すると、ＴＥは、ＭＴＥから両方のプリミティブオブジェクトを取得する。ＴＥは、片方又は両方のプリミティブオブジェクトが収まる各タイル（この事例では陰付きタイル）に関する制御ストリームデータを順次書き込む。片方のプリミティブオブジェクトだけが収まるタイル（例えば、タイルＢ５）に対しては、ＴＥは、このプリミティブオブジェクトに関する制御ストリームデータを書き込む。制御ストリームの最後では、メモリ位置が、テールポインタキャッシュ（ＴＰＣ）に記憶される。両方のプリミティブオブジェクトが収まるタイル（例えば、タイルＣ３）に対しては、ＴＥは、第１のプリミティブオブジェクトに関する制御ストリームデータを生成する。次に、ＴＥは、第２のプリミティブオブジェクトに関する制御ストリームデータを生成する。このタイルにおける両方のプリミティブオブジェクトに対する制御ストリームデータは、メモリに一緒に書き込まれる。別のタイルに対して処理を続ける前に、このタイルの処理にわたる全ての処理の最後において、制御ストリームの最終メモリアドレスがＴＰＣに記憶される。
【００５２】
この実施形態の一般的な方法を図７の流れ図に示す。タイル分割が２つのプリミティブオブジェクトに対して行われ、各プリミティブオブジェクトは、３２個までの形状（プリミティブとも呼ぶ）を収容することができる。
すなわち、２つのプリミティブオブジェクトが収まるタイルでは、このタイルに関する制御ストリームの最後におけるアドレスは、従来のシステムでの２度ではなく、一度だけ読み取られる必要がある。これらのタイルに対しては、制御ストリームデータ書込みは、１２８ビットよりも小さい２回のマスクされた書込みではなく、１２８ビットの最大バースト書込みになる。ＴＰＣアクセスは、これらのタイルでは半分になる。本発明者は、一部の事例において制御ストリームデータに関する１２８ビットの最大バースト書込みを０％から２５％に増大させることができ、一部の事例においてＴＰＣキャッシュミスの百分率を１２％から０．０４％に低減することができることを見出した。
【００５３】
上述の実施形態をＴＥがＭＴＥから２つのプリミティブオブジェクトを一度に取得する場合で説明した。明らかに、本方法は、ＴＥが一度に２つよりも多くのオブジェクトをＭＴＥから取得するように拡張することができる。毎回得られるプリミティブオブジェクトの数は、レンダリングされるシーンの複雑さ、プリミティブオブジェクト自体の複雑さ（すなわち、これらのプリミティブオブジェクトがいくつの面及び頂点を含むか）、及びＴＥの処理機能に依存することになる。
【００５４】
上述のように、本発明の第２の態様によると、２つの等しい３Ｄ画像処理パイプが２つのタイルに対して同時に機能することを可能にすることによって３Ｄ画像発生器の性能を改善する手法が達成される。これを図８に示す。
図８は、図４の簡略化したものであり、ＴＥ、ＩＳＰ、及びメモリのみを示している。ＴＥ８０１は、制御データをメモリ８０９に書き込む。３Ｄパラメータフェッチ８０３は、頂点及びプリミティブのデータを読み取って画像処理を実施する。この実施形態では、この処理は、２つのサブＩＳＰ／ＴＳＰ８０５及び８０７によって並行して実施される。この構成では、３Ｄ画像処理の性能は、二倍になると予想される。
図８のシステムを有効に作動させるために、ＴＥ８０１は、タイルのうちの２つに対して互いに制御データを書き込む。この書込みを８１１に略示している。本方法は、タイル分割制御ストリームデータにおける重複を大幅に低減し、従って、良好なメモリ帯域幅の改善を与える。
【００５５】
各タイルサイズが１６×１６ピクセルであった場合には、ＴＥ８０１は、全てのプリミティブオブジェクトを元の１６×１６タイルにタイル分割する。しかし、ＴＥは、制御ストリームデータ（８１１に示している）を３２×１６ピクセルのタイル、すなわち、２つの隣接する１６×１６タイルで書き込む。すなわち、各制御ストリームにおいて２つの１６×１６タイルが参照される。この２つのタイルの利点は、両方のタイル内に収まるオブジェクトを一度書き込むだけでよいので、書き込まれる制御ストリームデータの合計量が大きく低減することになる点である。一方、欠点も存在する。制御ストリームデータは、プリミティブオブジェクトの境界ボックスが、両方の１６×１６タイルと重なるという仮定に基づいている。プリミティブオブジェクト内には、例えば、３２個までのプリミティブ及び１６個までの頂点が存在する可能性があるが、これらのプリミティブ及び頂点の全てが特定の１６×１６タイルに収まることにはならない。プリミティブ及び頂点のうちの一部が、２つの１６×１６タイルのうちの片方にしか収まらない場合には、これらの無効なプリミティブ及び頂点によってパラメータデータ参照情報をフェッチして処理することは浪費になる。別の言い方をすると、２つのタイルを一度に取得することにより、最初に小さいタイルを有するという利点が幾分減少する。
【００５６】
この実施形態では、この問題は、制御ストリーム内で頂点マスク及びプリミティブマスクを用いて解決される。制御ストリームデータは、各プリミティブオブジェクトに対して、プリミティブオブジェクトヘッダ、及びそのプリミティブオブジェクトに関するオブジェクトデータ（プリミティブ及び頂点のデータを含む）のメモリアドレスを指し示す頂点ポインタを含む。この実施形態に用いられるマスクは、各１６×１６タイルに対して有効な頂点及びプリミティブ、すなわち、実際にそのタイル内に収まる頂点及びプリミティブを示している。頂点マスクは、頂点数及びプリミティブ数のような他の情報と共にプリミティブオブジェクトヘッダ内に含めることができる１６ビットのマスクである。頂点マスクは、各３２×１６タイルに対して有効な頂点を定義する。通常は、１６×１６タイルの各々に対して１つづつの２つの３２ビットプリミティブマスクが必要である。プリミティブマスクは、各１６×１６タイルに対して有効なプリミティブを定義する。プリミティブマスクは、ヘッダ内に含めることができ、又は制御ストリームに追加ワードとして加えることを必要とする場合がある。この実施形態では、両方の１６×１６タイルに対して１つの頂点マスクだけしか必要とされず、それに対して各１６×１６タイルに対して１つのプリミティブマスクを必要とすることに注意されたい。これは、頂点データがバーストで読み取られ、レンダリング処理がプリミティブに基づいており、従って、少数の不要頂点を読み取るのにそれ程コストが掛からないことによる。従って、空間を節約するために、３２×１６タイルに対して単一の頂点マスクを用いることができる。一方、不要なプリミティブを処理するには、より多くのコストが掛かり、従って、これを回避するために、より大きな空間を必要とはするが、各１６×１６タイルに対してプリミティブマスクが用いられる。
プリミティブが多くのタイルに重なる時にメモリ帯域幅に対する大きな影響を回避するために、制御ストリーム内のマスクのデータサイズを最小に保つ必要がある。この実施形態は、頂点マスク及びプリミティブマスクが含まれる時に制御ストリームのサイズを縮小する符号化手法を用いる。
【００５７】
既に解説したように、頂点マスク（及び場合によってはプリミティブマスク）は、プリミティブオブジェクトヘッダに含まれる。３２ビットプリミティブオブジェクトヘッダにおける符号化手法の詳細を表１に示す。
【００５８】
（表１）
【００５９】
表１に示しているプリミティブオブジェクトヘッダの構造を図８ａに例示している。
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ：
プリミティブマスク制御フラグ「ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ」に対して２ビット（２０：１９）が用いられる。このフラグは、制御ストリーム内の何処に頂点マスク及びプリミティブマスクが含まれるかを判断する。この符号化では、制御ストリーム内の追加プリミティブマスクワードは任意的である。
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝０１＝ＰＦ＿ＭＡＳＫ＿ＣＴＲＬ＿ＰＲＩＭ＿ＭＡＳＫ＿ＰＲＥＳである場合には、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬは、プリミティブマスクワードが制御ストリームに含まれることを意味する。一方、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１である場合には、プリミティブワードは、制御ストリームに含まれず、ヘッダに含まれる。
【００６０】
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝０１である前者の場合には、１つ又は２つのあらゆる追加プリミティブマスクワードを必要とすることができる。１つ又は２つのいずれの３２ビットワードが存在するかは、ＰＦ＿ＰＲＭ＿ＳＴＡＲＴに示されている。１つの追加プリミティブマスクワードしか持たない条件は、両方のプリミティブマスクが、下位１６ビット又は上位１６ビットセットのいずれかしか持たないということである。これは、両方のプリミティブオブジェクトが、左手１６×１６タイル又は右手１６×１６タイルのいずれかのみで有効であり、両方において有効ではないことを意味する。この場合、２つのプリミティブマスクワードが存在する場合は、片方は単純に０になり、従って、プリミティブワードマスクを完全に省略することができる。代替的に、両方のプリミティブオブジェクト内のプリミティブは、１６×１６タイルのうちの左又は右のいずれか片方においてのみ有効である。そうでなければ、２つの付加的なプリミティブマスクワードが必要とされ、これらは、２つの１６×１６タイル内で参照されるプリミティブに関する制御ストリームに追加される。
【００６１】
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１である後者の場合を有する条件、すなわち、いずれのプリミティブワードも制御ストリームに含まれない条件は、プリミティブオブジェクト内の全てのプリミティブが現在の３２×１６タイル内で参照されるか（すなわち、プリミティブオブジェクト内の全てのプリミティブが両方の１６×１６タイル内に収まり、従って、プリミティブマスクワードの必要がない）、又はプリミティブ及び頂点の両方のマスクに対して１バイト分の非０ビットのみが存在するということである。この第２の条件は、頂点マスクワードが、１バイト分の非０ビットを有し、非０頂点マスクバイトが、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１内にあることを意味する。すなわち、頂点１から８が３２×１６タイル内で参照されないか、又は頂点９から１６が３２×１６タイル内で参照されないかのいずれかである。（後に解説することになるが、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴが１の場合には、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１が頂点マスクの上位８ビットを含み、すなわち、頂点１から８が３２×１６タイル内で参照されないことを示している。ＰＦ＿ＶＴＭ＿ＳＴＡＲＴが０である場合には、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１が頂点マスクの下位８ビットを含み、すなわち、頂点９から１６は、３２×１６タイル内で参照されないことを示している。）ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１である場合には、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０内には、１バイトのプリミティブマスクしか存在せず、従って、３２ビットプリミティブマスクのうちの片方が０である必要がある。すなわち、プリミティブは、１６×１６タイルのうちの左又は右のいずれか片方においてのみ有効である。ＰＦ＿ＰＲＭ＿ＳＴＡＲＴにおける値は、プリミティブマスク内でのＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０のバイトオフセットを示している。例えば、ＰＦ＿ＰＲＭ＿ＳＴＡＲＴ＝１である場合には、３２ビットプリミティブマスクは、０ｘ００００Ｆ７００のように見えることになり、バイト１０×Ｆ７が、ヘッダにＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０として挿入される。
【００６２】
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１である後者の場合には、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１である時に、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０内に詰め込まれた１バイトプリミティブマスクに対して２つの可能性が存在する。
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝００（ＰＦ＿ＭＡＳＫ＿ＣＴＲＬ＿ＰＡＣＫＥＤ＿ＬＥＦＴ）である場合には、プリミティブマスク及び頂点マスクは、両方共にヘッダに含まれ、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０内に詰め込まれた１バイトプリミティブマスクは、３２×１６タイルの左半分に付属する。
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝１１（ＰＦ＿ＭＡＳＫ＿ＣＴＲＬ＿ＰＡＣＫＥＤ＿ＲＩＧＨＴ）である場合には、プリミティブマスク及び頂点マスクは、両方共にヘッダに含まれ、プリミティブマスクは、３２×１６タイルの右半分に付属する。
すなわち、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬのこれらの２ビットが、００，１１，又は１０である場合には、制御ストリームにいかなる追加プリミティブマスクも存在しない。
【００６３】
ＰＦ＿ＰＲＭ＿ＳＴＡＲＴ：
プリミティブマスク開始点「ＰＦ＿ＰＲＭ＿ＳＴＡＲＴ」に対して２ビット（１８：１７）が用いられる。ＰＦ＿ＰＲＭ＿ＳＴＡＲＴは、プリミティブマスクがヘッダに含まれるか（ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１）、又は制御ストリームに追加マスクとして含まれるか（ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝０１）のいずれであるかに依存して別々に用いられる。
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１である場合には、この２ビットは、プリミティブマスクがヘッダに含まれる時のプリミティブマスク内でのＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０のバイトオフセットを示している。
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝０１である場合には、この２ビットは、以下の通りに制御ストリームにどの追加マスクが含まれるかを示す上で用いられる。
【００６４】
これらの２ビット、すなわち、ＰＦ＿ＰＲＭ＿ＳＴＡＲＴが００である場合には、制御ストリームに２つの１６ビットプリミティブマスクが含まれ、すなわち、左右の１６×１６タイルに対する３２ビットプリミティブマスクの両方が、下位１６ビットを０として又は上位１６ビットを０として、そのいずれかで有する。ＰＦ＿ＶＴＭ＿ＳＴＡＲＴ＝０である場合には、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、２つの１６ビットプリミティブマスクがビット０から１５におけるものであり、かつ両方の１６×１６タイルに対してプリミティブ１から１６のみが参照されることを示している。ＰＦ＿ＶＴＭ＿ＳＴＡＲＴ＝１である場合には、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、２つの１６ビットプリミティブマスクがビット１６から３１におけるものであり、かつ両方の１６×１６タイルに対してプリミティブ１７から３２のみが参照されることを示している。
これらの２つの１６ビットプリミティブマスクは、３２ビットプリミティブマスクワードへと組み合わされる。これを下記の表２に示す。
【００６５】
（表２）
【００６６】
この場合のプリミティブマスクワードの構造を図８ｂに示す。ビット０から１５は、左手１６×１６タイルに対する１６ビットプリミティブ半マスクのために用いられる。ビット１６から３１は、右手１６×１６タイルに対する１６ビットプリミティブ半マスクのために用いられる。
２つのビット、すなわち、ＰＦ＿ＰＲＭ＿ＳＴＡＲＴが０１である場合には、左手１６×１６タイルに対して１つの３２ビットプリミティブマスクが制御ストリームに含まれる。これを下記の表３に示す。
【００６７】
（表３）
【００６８】
この場合のプリミティブマスクワードの構造を図８ｃに示す。
２つのビット、すなわち、ＰＦ＿ＰＲＭ＿ＳＴＡＲＴが１０である場合には、右手１６×１６タイルに対して１つの３２ビットプリミティブマスクが制御ストリームに含まれる。これを下記の表４に示す。
【００６９】
（表４）
【００７０】
この場合のプリミティブマスクワードの構造を図８ｄに示す。
最後に、２つのビット、すなわち、ＰＦ＿ＰＲＭ＿ＳＴＡＲＴが１１である場合には、各１６×１６タイルに対して１つの２つの３２ビットプリミティブマスクが制御ストリームに含まれる。これを下記の表５ａ及び５ｂに示す。
【００７１】
（表５ａ）
【００７２】
（表５ｂ）
【００７３】
この場合のプリミティブマスクワードの構造を図８ｅに示す。
【００７４】
ＰＦ＿ＶＴＭ＿ＳＴＡＲＴ：
表１を再度参照すると、頂点マスク開始点「ＰＦ＿ＶＴＭ＿ＳＴＡＲＴ」に対して１ビット（１６）が用いられる。ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、プリミティブマスクがヘッダに含まれるか（ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１）、又は制御ストリーム内の追加マスクとして含まれるか（ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝０１）のいずれであるかに依存して別々に用いられる。
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１であり、すなわち、プリミティブマスクがヘッダに含まれる場合には、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴのビットが設定され、すなわち、＝１である場合に、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１（下記に解説することになる）が、１６ビット頂点マスクの上位８ビットであるバイト１を反映することを示している。このビットが消去され、すなわち、＝０である場合には、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１が、１６ビット頂点マスクの下位８ビットであるバイト０を含むことを示している。
【００７５】
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝０１であり、すなわち、プリミティブマスクが制御ストリームに追加され、かつＰＦ＿ＰＲＭ＿ＳＴＡＲＴ＝００である場合には、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴが１である場合に、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、１６ビットプリミティブ半マスクの両方が、プリミティブ３１：１６に適用されることを示している。上記以外の場合は、これらは、１５：０に適用される。
【００７６】
ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１：
「ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１」に対して８ビットが用いられる。ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１は、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ及びＰＦ＿ＶＴＭ＿ＳＴＡＲＴのステータスに依存する。ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１、すなわち、プリミティブマスクが、ヘッダ内のＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０内に含まれ、かつＰＦ＿ＶＴＭ＿ＳＴＡＲＴが１に等しい場合には、これらの８ビットは、１６ビット頂点マスクの上位８ビットである。一方、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１であり、かつＰＦ＿ＶＴＭ＿ＳＴＡＲＴが０に等しい場合には、これらの８ビットは、１６ビット頂点マスクの下位８ビットである。
【００７７】
ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０：
「ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０」に対して８ビットが用いられる。ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０は、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ及びＰＦ＿ＰＲＭ＿ＳＴＡＲＴのステータスに依存する。ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝０１、すなわち、プリミティブマスクが、ヘッダではなく制御ストリームに含まれる場合には、１６ビット頂点マスクは、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０及びＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１内にあり、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０は、頂点マスクの下位８ビットである。一方、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１である場合には、プリミティブマスクからの１つの非０バイトが、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０内にある。この場合、この非０バイトプリミティブマスクのバイトオフセットは、ＰＦ＿ＰＲＭ＿ＳＴＡＲＴからのものである。
【００７８】
ＴＥが、３２×１６タイル内のプリミティブオブジェクトからのプリミティブ及び頂点データを処理する場合には、ＴＥは、オブジェクト内の全ての頂点を検査して、タイル内の有効頂点に対する頂点マスクを作成する。次に、ＴＥは、１６×１６タイルの各々に収まるオブジェクト内の有効プリミティブに対するプリミティブマスクを生成する。上述の符号化手法は、次に、頂点マスク及びプリミティブマスクを制御ストリームデータ内に可能な限り小さいサイズで書き込む上で用いられる。
【００７９】
制御ストリームの最後のテールポインタアドレスは、「テールポインタキャッシュ（ＴＰＣ）」を通じて３２×１６タイルへのタイル分割の開始時点で読み戻される。テールポインタアドレスは、タイルの全ての処理が完了した後に初めて書き戻される。３２×１６タイルの両方の１６×１６タイルが、両方のプリミティブオブジェクト含む場合は（図５に戻り、例えば、タイルＣ３及びＣ４を参照されたい）、２つのプリミティブオブジェクトは、２つの１６×１６タイル内で処理されることになり、ＴＰＣが制御ストリームの最後に対するテールポインタで更新される前に、制御ストリームに書き込まれた適切な制御データを有する。それによって制御ストリームデータ書込みからのメモリアクセスが改善され、ＴＰＣの性能が改善される。
【００８０】
本発明のこの実施形態では、各３２×１６タイルの制御ストリームが一度に処理される。３２×１６タイルでは、タイル内で参照される頂点は、頂点マスクを用いてメモリからフェッチされる。このフェッチは、図８のパラメータフェッチ８０３によって実施される。従って、タイル内で参照されないフェッチ頂点に対していかなるメモリ帯域幅も追加されず、従って、上記に解説した問題は解決される。同様に、１６×１６タイルの各々に対するプリミティブマスクは、プリミティブデータをフェッチするのに用いられる。このフェッチも、図８の８０３によって実施される。上述の場合のように、タイル内で参照されないフェッチプリミティブに対していかなるメモリ帯域幅も追加されない。次に、左手の１６×１６タイルに対して適切なプリミティブ及び頂点が、サブＩＳＰ／ＴＳＰ８０５に送られ、右手の１６×１６タイルに対して適切なプリミティブ及び頂点が、サブＩＳＰ／ＴＳＰ８０７に送られる。
【００８１】
本発明者は、３２×１６ピクセルタイルに基づくタイル分割であるこの実施形態の方法が、１６×１６ピクセルタイルに基づくタイル分割と比較して、付加的なプリミティブマスクワードを用いた場合でさえも平均で３５％の制御ストリームデータ書込みの低減をもたらすことを見出した。３Ｄパラメータフェッチにおける合計のデータ読取りに対しても同等のレベルの低減を達成した。
上述のように、本発明の第３の態様によると、メモリ空間を用いるより効率的な手法が達成される。次に、第３の態様の実施形態を以下に説明する。
【００８２】
既に解説したように、既存のシステムでは、頂点及びプリミティブデータに対するマクロタイルに用いられるメモリページは、要求に応じて割り当てられ、従って、必ずしも連続するページであるわけではない。特定のプリミティブオブジェクトからのデータがページ境界を超えるのを防ぐために、プリミティブオブジェクト全体に対して現在のページ上に不十分な空間しか存在しない場合には、空き記憶領域から新しいページを割り当てる必要がある。
【００８３】
特定のプリミティブオブジェクトに含まれる頂点及びプリミティブの最大数には制限が存在する（例えば、１６個の頂点及び３２個のプリミティブ）。上述のように、ＭＴＥは、プリミティブオブジェクトがメモリのページ境界に架からないことを確実にすべきである。これは、メモリページが、連続する順序で割り当てられることが保証されないからである。頂点をプリミティブオブジェクトに割り当てるパイプラインのフロントエンドは、このプリミティブオブジェクトに残されたいかなる空間量も既知ではないので、上述のことは困難である。一方、メモリを割り当て、実際にプリミティブオブジェクトデータをメモリに入力するパイプラインのバックエンドは、オブジェクト内の頂点数に対していかなる制御も持たない。現在のメモリページにプリミティブオブジェクト内の最大頂点数を保持するのに十分なメモリ空間が存在するか否かの検査が、十分な空間が存在しないことを明らかにした場合には、バックエンドにおいて新しいメモリページの割り当てが実施される。頂点データのサイズは既知であり（Ｘ、Ｙ、Ｚ座標に加えて、基本色、オフセット色、テクスチャ座標、テクスチャ座標がいくつあるか等に関する更に別のデータがある場合がある）、プリミティブオブジェクトに必要な最大メモリ空間は、容易に計算することができる。従って、例えば、プリミティブオブジェクト内の最大頂点数が１６である場合には、バックエンドは、頂点数が１６であることを常に仮定し、フロントエンドは、１つのプリミティブオブジェクト内に実際に１６個までの頂点を含むことができることを常に仮定する。一方では、メモリ帯域幅に関して優れた効率を生じる頂点間の最大共有量を得ることができるので、上述のことは有利である。しかし、他方では、例えば、このメモリページ内に１５個の頂点に対する空間だけしか残っていない場合には、新しいページをバックエンドで開始する必要があるが、それにも関わらず、フロントエンドで割り当てられる頂点の数は実際には１４である可能性がある。しかし、バックエンドは、これを知る由もなく、これに対していかなる制御も持たない。それによって明らかにメモリ浪費が生じる。このメモリ浪費によるコストは、頂点サイズ、すなわち、特定の頂点に関連付けられた追加データ（基本色、オフセット色、テクスチャ座標などのような）と共に変化する。
【００８４】
本発明の第３の態様のこの構成は、この問題を解決するための２つの実施形態を提供する。提案する第１の実施形態は、ＭＴＥによってプリミティブオブジェクトに対して２つのメモリページを割り当てることを可能にする。すなわち、特定のプリミティブオブジェクトは、２つのメモリページにわたることができる。従って、開始時点で、ＭＴＥによってプリミティブオブジェクトがメモリ内に書き込まれる時に、メモリマネージャは、２つのメモリページをそのマクロタイルに割り当てる。（１ページしか実際には必要ではないことになった場合には、第２のページは、単純に次の書込みに用いられる。）全てのプリミティブオブジェクトに対して、頂点及びプリミティブの数が、プリミティブオブジェクトのメモリアドレス（頂点ポインタ）と共にＴＥに送られて、プリミティブオブジェクトが可視であるタイルの制御ストリームに追加される。ＭＴＥがプリミティブオブジェクトデータをメモリ内に連続的に書き込む時には、ＭＴＥは、メモリ書込みがページ境界に架かるか否かを検査する。書込みが、１つのメモリページ範囲に収容されることになる場合には、このメモリページに対する頂点ポインタのみがＴＥに渡されることになる。一方、書込みがページ境界を超え、プリミティブオブジェクトデータが２つのメモリページ上に存在することになる場合には、第１のページ及び第２のページに対する両方の頂点ポインタがＴＥに送られる。
【００８５】
ＭＴＥによってＴＥに送られるデータが、２つの頂点ポインタを含む場合には（ＭＴＥ書込みが、上述のようにページ境界を超えたために）、ＴＥは、このタイルに対する制御ストリーム内のリンクページのアドレスへの追加頂点ポインタを書き込むことになる。これを図９に略示している。
図９では、制御ストリームは、第１のプリミティブオブジェクトに対してプリミティブオブジェクトヘッダを含み、次に、このプリミティブオブジェクトに対する頂点ポインタを含む。従って、このプリミティブオブジェクトに関するオブジェクトデータは、第１のメモリページ上にのみ記憶される。しかし、第２のプリミティブオブジェクトでは、制御ストリームは、プリミティブオブジェクトヘッダ、頂点ポインタ、及び頂点リンクポインタを含む。この頂点リンクポインタは、第２のメモリページへの頂点ポインタであり、頂点ポインタが第１のメモリページを指し示すのに対して、頂点リンクポインタは、第２のメモリページを指し示すことが分る。従って、このプリミティブオブジェクトに関するオブジェクトデータは、第１のメモリページ及び第２のメモリページという２つのメモリページにわたっている。
【００８６】
このタイルに対して画像処理が実施されている時に、制御ストリームは構文解析され、ＩＳＰは、特定のプリミティブオブジェクトに対して２つの頂点ポインタが存在することを把握する。これらの頂点リンクページポインタは、パイプラインの下流へと渡される。メモリアドレスがページ境界を超えた場合には、メモリからプリミティブ及び頂点データをフェッチする上で第２の頂点ポインタからのリンクページアドレスが用いられる。プリミティブオブジェクトサイズの上限、及びメモリページが割り当てられる手法により、ＭＴＥ書込みは、最大２ページしか必要としないことになる、すなわち、１つ又は２つの頂点ポインタしか存在しないことに注意されたい。
【００８７】
提案する第２の実施形態は、ページが連続することを保証する追加論理、及び付加的な小さいキャッシュを用いる「動的パラメータ管理（ＤＰＭ）」を提供する。ページが連続することが保証される場合には、所定のマクロタイルに関する書込みが２ページにわたることを容認することができる。
ページを各マクロタイルに割り当てられたままに保つために、ＭＴＥが連続書込みを行う時に、ＤＰＭは、一部分が各マクロタイルに割り当てられた１つ又は複数のルックアップテーブルページを維持する。ＭＴＥに割り当てられたページは、連続メモリページアドレスではなく、ルックアップテーブル内の連続インデックスである。各マクロタイルに対して、ルックアップテーブル内には、データが書き込まれる実際のメモリページへのポインタを与える部分が存在する。ルックアップテーブル内のこれらの部分は連続し、この連続性は、これらの部分が開始時点にＤＰＭによって割り当てられることから得ることができる。
【００８８】
各マクロタイル（及び用いられている場合は全体リスト）に対して、ＭＴＥへのページ割り当てのために、ＤＰＭ内でカウンタが維持される。ＭＴＥによって書き込まれるデータに対して第１のページがマクロタイルに割り当てられる時に、同様に一部分が、そのマクロタイルに関するルックアップテーブル内に割り当てられる。マクロタイルに割り当てられた第１のページのアドレスは、このマクロタイルに関するルックアップテーブルページ内のこの部分の位置０に書き込まれる。このマクロタイルに対するその後の割り当ては、このマクロタイルに関するルックアップテーブルページ内のこの部分の位置１，２等に書き込まれることになる。従って、実際の割り当てページが連続でない可能性があったとしても、ルックアップテーブルのこれらの部分は連続であり、従って、マクロタイルに関する書込みデータは、１つよりも多くのページにわたることができる。上述のルックアップテーブル部分が一杯になった状態で、新しい部分がルックアップテーブル内に割り当てられ、この位置は、更に別のページアドレス割り当てで埋められる。全てのマクロタイルは、この手法で取り扱われる。最大画面レンダリングが実施された状態で、全てのメモリページ及びルックアップテーブルページは解放される。
【００８９】
従って、ＭＴＥは、一方がデータの書き込まれる実際のアドレス、他方がこのマクロタイルに関するルックアップテーブルページの上述の部分のアドレス（基本アドレス）という２つのアドレスをＤＰＭから受け取る。マクロタイルに関する連続アドレスであるルックアップテーブル内のアドレスは、ＴＥに渡される頂点ポインタ（すなわち、オブジェクトデータに対するメモリアドレス）として用いられ、データが記憶される実際のアドレスは、データをメモリ内に書き込む上で用いられる。
【００９０】
ルックアップテーブルメモリページの基本アドレスは、レジスタ内に保持することができる。３Ｄ画像処理モジュール（ＩＳＰ）は、各タイル内のプリミティブオブジェクトを処理する前にこの基本アドレスを読み取る。各タイル内のプリミティブオブジェクトの処理中に、ルックアップテーブルページの上述の部分のアドレスは、このルックアップテーブルが属するマクロタイルのディレクトリエントリからフェッチされる。制御ストリームから読み戻された頂点ポインタは、実際のデータが書き込まれたメモリアドレスを得るのに用いられる。従って、連続ルックアップテーブルアドレスは、不連続メモリアドレスへと変換される。連続ルックアップテーブルアドレスと不連続メモリアドレスの間のこの変換をより効率的にするために、これらのアドレスにアクセスを行う上でキャッシュを用いることができる。
【００９１】
図１０は、この実施形態を略示している。第１のルックアップテーブルを１００１に示している。ルックアップテーブルに対する基本アドレスが存在する。この基本アドレスは、各マクロタイルＭＴ０，ＭＴ１．．．に対して、各々が２バイトの３２個までのエントリ、すなわち、合計６４バイトを含むルックアップテーブル１００１を指し示す。（図１０では、簡略化のためにＭＴ７に関するエントリのみ示しているが、これは、全てのマクロタイルに当て嵌まる。）この実施形態では、１６個のマクロタイルに加えて全体リスト（１つよりも多くのマクロタイルを横断するオブジェクトデータの記憶のための）が存在し、従って、１７×６４バイト＝１０８８バイトが生じる。この実施形態における各メモリページは、４０９６バイトであり、従って、全てのマクロタイルに全体リストを加えたものに対するエントリは、ページ内に容易に収まる。
【００９２】
各３２個の２バイト部分は、各々のサイズが４０９６バイトであり、すなわち、メモリページを占有する別のルックアップテーブル１００３を指し示す。これを矢印Ａで示している。上述のルックアップテーブル部分は開始時点に割り当てられるのに対して、これらの追加ページは、より効率的なメモリ使用に向けて要求に応じて割り当てられる。各４０９６バイトのテーブル１００３は、２０４８個の２バイト変換情報を含む。これは、仮想ドメイン１（ルックアップテーブル１００３）から仮想ドメイン２（メモリページ１００５）に変換することができることを意味する。各２バイト部分は、４０９６バイトのページ１００５を参照する。これを矢印Ｂで示している。従って、２０４８×４０９６バイト＝約８ＭＢが存在する。３２個のこれらが、各マクロタイルに対して存在し、すなわち、３２×８ＭＢ＝２５６ＭＢである。従って、各マクロタイルは、２５６ＭＢの仮想アドレス空間を保持することができる。
【００９３】
ここで、この実施形態では、メモリの合計量は、２５６ＭＢであり、従って、全てのデータが１つのマクロタイルに存在したとしても、全体の空間は、連続的にアドレス指定することができる。入って来る仮想アドレスは、１６ビットから成る。マクロタイル番号及び上位５ビットは、第１のテーブル（ディレクトリと呼ぶ）をアドレス指定し、３２個の他のテーブルのうちのどれをアクセスするかを示す上で用いられる。下位１１ビットは、２０４８個の変換値のうちのどれを実際に用いるべきかを示している。従って、連続するアドレスと仮想アドレスとの間で変換を行うための段階は、１）適切なマクロタイルを選択する段階、２）上位５ビットを用いて正しい第２のルックアップテーブルを選択する段階、及び３）１１個の下位ビットを用いて２０４８個のメモリページのうちのどれが実際の仮想アドレスであるかを選択する段階である。
【００９４】
この実施形態では、連続アドレス及び仮想アドレスは、ＤＰＭによってＴＡに供給される。データが書き込まれるアドレスが仮想アドレスであり、制御ストリームに組み込まれるアドレスは連続のものである。ルックアップテーブルは、連続アドレスを仮想アドレスへと変換するのにＩＳＰ及びＴＳＰパラメータフェッチによって用いられる。この第２の変換を効率的にするために、このルックアップテーブルはキャッシュに入れられ、このキャッシュは、性能を維持するのに必要である。
【００９５】
本発明者は、これらの実施形態を適用した後に、ＮＴＥによって用いられるメモリ空間の平均で１５％の低減を達成したことを見出した。２つの解決法の間の差は、第１の解決法（２つの頂点ポインタを用いた）は、２つの新しいキャッシュを追加する必要がないことから実装が小さくなることである。しかし、この解決法は、パラメータフォーマットを変更し、複雑さを増すことを要求する。第２の解決法（ルックアップテーブルを用いた）は、２つのページにわたって書込みを行うことを可能にし、システムの残りの部分に影響を及ぼすことなく実施することができる。また、第２のポインタという負荷の増大も存在しない。
【００９６】
上述の本発明の第３の態様の実施形態では、オブジェクトデータに対するメモリ割り当ての問題に対処した。特定のプリミティブオブジェクトからのデータがページ境界線を超えるのを防ぐために、プリミティブオブジェクト全体に対して現在のページ上に不十分な空間しか存在しなかった場合には、空き記憶領域から新しいページを割り当てる必要がある。ｚバッファメモリに記憶される深度データにおいて類似の問題が発生する可能性があり（図２を参照されたい）、ここで、これに対して更に説明を行うことにする。
【００９７】
図２は、部分レンダリングが採用された場合のプロセッサの例を示している。部分レンダリングは、オブジェクトデータのうちの一部を記憶するだけでよく、更に、部分レンダリングは、表示リストメモリ２０５を解放するように実施することができることから複雑なシーンに対して有効である。得られる深度データは、ｚバッファメモリ２０９に記憶され、後のオブジェクトデータと組み合わされ、最終的に全体画像が生成される。図２に示しているように、圧縮／解凍ユニット２１１を用いることができる。
【００９８】
画像が最終的に正しく生成されることを保証するために、メモリ２０９内の深度データを部分レンダリングが実施されたマクロタイル内のタイル上に記憶する必要がある。深度データを記憶するのに用いられるｚバッファメモリ２０９内の空間は、要求に応じてメモリマネージャ（例えば、ＤＰＭ）によって割り当てられ、特定のタイルに対するメモリアドレスが保存される。次に、更に別のオブジェクトデータが表示リストメモリ内にロードされ、次に、更に別の部分レンダリングが実施される。この段階では、更に別の深度データは、タイルに関連付けられたメモリアドレス内に置かれる。最終画像は、全ての部分レンダリングの後に正しくレンダリングされることになり、ｚバッファメモリのメモリページを解放することができる。
【００９９】
圧縮／解凍ユニット２１１が用いられる場合には、ユニット２１１内にはタイルに関する圧縮深度データを保持するいかなるバッファも存在せず、従って、ユニットは、圧縮しながらデータをメモリ内に書込み、解凍しながらメモリからデータを読み取る。タイル内の圧縮ｚデータがメモリページを超えることを回避するために、タイルの開始時点に、圧縮／解凍ユニットは、現在のメモリページ内に十分な空き空間が存在するか否かを検査する必要がある。圧縮／解凍ユニットは、ｚデータを圧縮し、それをｚバッファメモリ内に書込み始める時には、タイルに関する圧縮ｚデータのサイズを把握していない。従って、圧縮／解凍ユニットが、書込みの開始時点に空き空間を検査する時には、タイル内の深度データの最大サイズを仮定する必要がある。深度データのサイズは、常に最大サイズとは限らないので、メモリページの最後には浪費メモリ空間が存在する。
【０１００】
本発明のこの実施形態は、ページの最後のリンクページアドレスに対して特別に定められたトークンを与えることによってこの問題を解決することを試み、これを図１１に示す。図１１に示しているように、ＤＰＭによって圧縮ｚデータに割り当てられた各メモリページ１１０１において、最後の４バイトワード１１０３が、ページアドレスリンクに向けて保証される。圧縮／解凍ユニットが、書込みがメモリページを超えるのを検出した場合には、このユニットは、ＤＰＭから新しいページを要求することになる。現在のページ内の最後のワードは、図１１にあるリンクページヘッダ０ｘ８０００００００−１１０３と共に新しいページのためのページアドレスリンクで埋められることになる。リンクページヘッダは、ビット３１が１であるか、又は４バイトが右から左に８０，００，００，００である３２ビット１６進値である。この後、圧縮／解凍ユニットは、新しいページに向けてページアドレスリンクによって示された新しいページ内に圧縮深度データを書込み続ける。ページの最後では、いかなるメモリ空間も浪費されない。圧縮深度データを単一ページ内に収容することができる場合には、いかなるページアドレスリンクも必要とされない（最終の４バイトを除き）。この場合、現在のページ内の最後のワードは、００００．．．で埋められることになる。
読取段階中に、圧縮／解凍ユニットは、メモリから読み取られたデータを解凍する。ページ内の最後のワードは、深度データ自体ではなく、常に、新しいページアドレスへのトークンであるページ内の最後のワードのヘッダ（０ｘ８０００００００）を解析することにより、圧縮／解凍ユニットは、最後のワードが新しいページにリンクするためのアドレスであるのか、又は空白ワード（００００．．．）であるのかを判断する。最後のワードからのアドレスは、リンクページヘッダが設定されている場合に、リンクされたページから圧縮データをフェッチし続けるのに用いられる。
【０１０１】
この実施形態の利点は、新しいページの追加アドレスをタイルの領域ヘッダに含める必要がない点である。ページリンクは、圧縮及び解凍処理内で自然に発生する。この実施は、単純で分り易いものである。
本発明者は、この実施形態を適用した後に、圧縮ｚバッファによって用いられるメモリ空間の平均で３５％の低減を達成することができることを見出した。
【符号の説明】
【０１０２】
５０１，５０３，５０５，５０７，５０９ 第１のプリミティブオブジェクトの頂点
５１１，５１３，５１５，５１７，５１９ 第２のプリミティブオブジェクトの頂点
Ｃ１，Ｃ２，Ｃ３ タイル
【技術分野】
【０００１】
本発明は、３次元コンピュータ画像を生成する方法及び装置に関する。
【背景技術】
【０００２】
本出願人の英国特許第２２８１６８２号では、３Ｄシーン内の各プリミティブオブジェクトが無限の面の集合で定義されるような光景として見られる多角形に対する３Ｄレンダリングシステムが説明されている。画像が表示されることになる画面の各基本区域（例えば、ピクセル）は、それを通して光線を視点から３Ｄシーン内へ投影させる。次に、投影光線と各面の交点の位置が判断される。これらの交点から、いずれかの交差面がこの基本区域で可視であるか否かを次に判断することが可能である。この基本区域は、次に、判断の結果に応じて表示に向けてシェーディングされる。
【０００３】
このシステムは、各々が面との交点計算を実行することができるいくつかのセルを含むパイプライン型プロセッサに実施することができる。従って、多数の面交点を同時に計算することができる。各セルには、交点検査を実施する面を定義する１組の係数がロードされる。
この構成に対する改善が、本出願人の英国特許第２２９８１１１号に説明されている。この文献では、画像は、部分領域又はタイルに分割され、タイルは、逐次処理することができる。可変タイルサイズを用い、完全なプリミティブオブジェクトの周囲に境界ボックスを投影し、それによって境界ボックス内に収まるタイルのみが処理を必要とすることが提案されている。これは、適切なタイルサイズを選択するために可視画面上のプリミティブオブジェクトの配分を判断することによって行われる。タイル内の各オブジェクトは、面及び頂点を有するいくつかの三角形として記憶される。他の形状も可能である。次に、様々なプリミティブオブジェクトを定義する面が、表示リストとして公知のリストに記憶され、それによって各タイルに対して同一の面を記憶する必要性が回避されるが、これは、多くの面から成る１つのオブジェクトがいくつかのタイルに出現することができると考えられるからである。表示リスト内のプリミティブオブジェクトを識別するオブジェクトポインタも同様に記憶される。タイル毎に１つのオブジェクトポインタリストが存在する。次に、タイルは、各タイル内の全てのプリミティブオブジェクトが処理されるまで、上述の光線投射技術を用いて逐次レンダリングすることができる。これは、特定のタイル内で可視でないことが既知であるオブジェクトをレンダリングする必要がないので有用な方法である。
【０００４】
このシステムに対する更なる改善は、本出願人の国際特許出願番号ＰＣＴ／ＧＢ９９／０３７０７（公開番号ＷＯ２０００／０２８４８３）及びＰＣＴ／ＧＢ２００４／００１０７６（公開番号ＷＯ２００４／０８６３０９）、並びに本出願人の英国特許第２３４３６０３号に提案されており、特定のプリミティブオブジェクトを表示する必要のない境界ボックス内のあらゆるタイルが、レンダリングの前に廃棄される。
【０００５】
図１は、上述の既存のシステムに用いられる種類のプロセッサ１０１を示している。基本的に、３つの構成要素が存在する。タイルアクセラレータユニット（ＴＡ）１０３は、タイル分割作動を実施し、すなわち、適切なタイルサイズを選択して可視画面をタイルに分割し、タイル情報、すなわち、各タイルに関する３Ｄオブジェクトデータを表示リストメモリ１０５へと供給する。画像合成プロセッサ（ＩＳＰ）１０７は、表示リストメモリ内の３Ｄオブジェクトデータを用いて、上述の光線／面交点検査を実施する。この検査により、可視画面の各基本区域に関する深度データが生成される。この後、ＩＳＰ１０７から導出された画像データは、可視であると判断された面にテクスチャリング及びシェーディングデータを適用して画像及びシェーディングデータをフレームバッファメモリ１１１に出力するテクスチャリング及びシェーディングプロセッサ（ＴＳＰ）１０９に供給される。すなわち、ディスプレイの各基本区域の外観が、３Ｄ画像を表すように判断される。
【０００６】
上述のシステムでは、レンダリングされるシーンの複雑さが増大する時に問題が発生する場合がある。複雑なシーンは、各タイルに対してより多くの３Ｄオブジェクトデータを表示リストメモリに記憶することを必要とし、これは、記憶要件が増大することを意味する。表示リストメモリが空間を使い切ってしまった場合、単純に、シーンの一部は、レンダリングされない場合があり、この種類の画像破損は、益々容認できなくなっている。
【０００７】
この問題を解決するために、本出願人の国際特許出願ＰＣＴ／ＧＢ０１／０２５３６（公開番号ＷＯ２００１／０９５２５７）は、部分レンダリングの考えを提案している。タイルのレンダリングが完了する前に、システム（ＩＳＰ及びＴＳＰ）の状態がメモリに記憶され、この状態は、レンダリングを完了するために後の時点で再ロードされる。この処理を「ｚ／フレームバッファロード及び記憶」と呼ぶ。
【０００８】
画面は、各タイルが画面の矩形領域から成るマクロタイルと呼ぶいくつかの領域に分割される。次に、表示リスト内のメモリが、ブロックに分割され、これらは、空き記憶領域リストに列挙される。空き記憶領域からのブロックは、次に、必要に応じてマクロタイルに割り当てられる。タイル分割作動は、各マクロタイルに関連付けられたデータを各ブロックに記憶する。（ＴＡによって実施されるタイル分割作動は、表示リストメモリを埋め、従って、時によっては「メモリ割り当て」と呼ばれる。）表示リストメモリが埋め尽くされるか又は何らかの所定の閾値に達すると、システムは、マクロタイルを選択し、ｚ／フレームバッファロードを実行し、マクロタイルの内容をそれをｚ／フレームバッファ記憶作動を用いて保存する前にレンダリングする。すなわち、マクロタイルに関する深度データが、それまでに表示リスト内にロードされたデータに従って記憶される。そのようなレンダリングの完了時に、システムは、このマクロタイルに関連付けられたあらゆるメモリブロックを空にして、それによって更に別の記憶に向けてこれらのメモリブロックを利用可能にする。（レンダリング処理は、表示リストメモリ空間を解放するので、それは、「メモリ割り当て解除」として公知である。）従って、各タイルに対するシーンは、いくつかのタイル分割作動とそれに続く部分レンダリングによって構成される。各部分レンダリングは、記憶された深度データを更新する。これは、メモリ消費に対して上限が課せられ、システムによって消費されるメモリ帯域幅も最小にされることを意味する。
【０００９】
部分レンダリングシステムに用いられる種類のプロセッサの一例を図２に示す。このプロセッサは、図１の改訂バージョンであることが分る。ｚバッファメモリ２０９は、ｚ圧縮／解凍ユニット２１１を通じてＩＳＰ２０７にリンクされる。これは、システムが複雑なシーンをレンダリングし、かつ表示リストメモリ２０５が、特定のタイルに対して処理する必要がある全ての面を収容するほど十分大きくない時に作動を始める。表示リストには、それが実質的に一杯になるまで（又は、所定の閾値に達するまで）全てのタイルに対してＴＡ２０３によってデータがロードされることになる。しかし、これは、初期データの一部分を表すのみであろう。画像は、ＩＳＰ２０７によって一度に１つのタイルでレンダリングされる。各タイルに関する出力データは、テクスチャデータを用いてタイルをテクスチャリングするＴＳＰ２１３に供給される。それと同時に、画像データは、未完成であるから、ＩＳＰ２０７からの結果（すなわち、深度データ）は、一時的な記憶に向けて圧縮／解凍ユニット２１１を通じてバッファメモリ２０９に記憶される。残りのタイルのレンダリングは、次に、未完了の画像データを用いて、全てのタイルがレンダリングされてフレームバッファメモリ２１５及びｚバッファメモリ２０９に記憶されるまで継続される。
【００１０】
次に、表示リストの最初の部分が廃棄され、更に別の画像データがその中に読み込まれる。ＩＳＰ２０７によって各タイルに対して処理が順次実行される時に、ｚバッファメモリ２０９からのデータの関連の部分は、それを表示リストメモリ２０５からの新しい画像データと組み合わせることができるように、ｚ圧縮／解凍ユニット２１１を通じてロードされる。次に、各タイルに関する新しい深度データがＴＳＰ２１３に供給され、それは、データをフレームバッファ２１５へ供給する前にデータをテクスチャデータと組み合わせる。
【００１１】
この処理は、全ての画像データがレンダリングされ終わるまで、シーン内の全てのタイルに対して継続される。すなわち、ｚバッファメモリは、一時的記憶領域を埋めて、それによって特に複雑なシーンをレンダリングするのに必要になると考えられるものよりも小さい表示リストメモリを用いることを可能にすることが分る。圧縮／解凍ユニット２１１は、任意的であるが、それは、より小さいｚバッファメモリを用いることを可能にする。更に、繰延ピクセル処理が有効にされて、あらゆる冗長なピクセル作動を排除する。
【００１２】
従って、国際特許出願番号ＰＣＴ／ＧＢ０１／０２５３６に解説されているように、表示リストメモリが埋め尽くされるか又はある一定の閾値に達した状態で、システムは、一部の表示リストメモリを解放するために、レンダリングするマクロタイルを選択する。この出願では、レンダリングするマクロタイルの選択は、いくつかの要因に依存し、例えば、最も多くのメモリを空き記憶領域へと解放して戻すことになるマクロタイルを選択することができる。
【００１３】
このシステムに対する更なる改善が、本出願人の英国特許出願第０６１９３２７．０号に示されている。この構成に用いられるプロセッサの概略的な例を図３に示す。システム３０１は、図２のものと同様であり、ＴＡ３０３，ＩＳＰ３１１，ＴＳＰ３１３、及び「フレームバッファ」３１５を含むことが分る。しかし、この場合、「表示リストメモリ」３０５及び「Ｚバッファメモリ」３０７は、両方共に「パラメータメモリ」３０９と呼ぶメモリの単一ヒープの一部である。パラメータメモリ内での「表示リスト」と「Ｚバッファ」の間の割り当ては、必要に応じてのものであり、それによってメモリ使用がより効率的になる。図３は、図２におけるようなｚ圧縮／解凍ユニットを示していないが、そのようなユニットを含めることができると考えられる。
【００１４】
更に、本出願人の英国特許出願第０６１９３２７．０号では、表示リストメモリは、ブロックを必要とする各マクロタイルのためのブロック、及び同じく全体リストを含む。オブジェクトデータは、１つよりも多くのマクロタイルを横断することが可能である。この場合、オブジェクトデータは、１つよりも多くのマクロタイルに存在するオブジェクトデータのみを収容する全体リストに割り当てられる。従って、表示リストは、マクロタイルに全体リストを加えたものへとグループ分けされる。マクロタイル内の全てのオブジェクト及び制御ストリームデータは、所定のマクロタイル内に属するタイルによってのみアドレス指定されることになり、１つよりも多くのマクロタイルに属するあらゆるオブジェクトデータは、全体リストに存在し、これらのデータは、あらゆる制御ストリームからアドレス指定することができる。これは、同じくより効率的なメモリ使用及びアクセスに役立つ。
【００１５】
図４は、英国特許第０６１９３２７．０号に説明されているシステムの特定の例を示している。この構成は、「動的パラメータマネージャ」ＤＰＭ４１１，ＩＳＰ４０７、「マクロタイル分割エンジン」４０３、「タイル分割エンジン」ＴＥ４０５、及びメモリ４０９を含む。一般的には、ＭＴＥ４０３は、各マクロタイルに対してプリミティブオブジェクトデータを生成し、これらのデータをメモリ４０９の適切な部分に入力する。ＴＥ４０５は、ＭＴＥ４０３からのプリミティブオブジェクトデータを用いて各タイルに関する制御ストリームデータを生成し、これらのデータをメモリ４０９に入力する。従って、ＭＴＥとＴＥは、各マクロタイル内の各タイルに対する記憶域が適切なオブジェクトデータ記憶域を指すように、一緒にタイルアクセラレータとして作用する。ＩＳＰ４０７は、オブジェクトデータを用いて深度データを導出し、これらのデータをメモリ４０９のｚバッファ部分に記憶する。
【００１６】
次に、図４の作動のより詳細な説明を図５への参照も行いながら提供することにする。図５は、表示されるいくつかの三角形状を示している。各三角形状は、プリミティブ又は単純に形状として公知である。画面は、３０個のタイルに分割される。プリミティブは、２つのプリミティブオブジェクトに分割される。第１のプリミティブオブジェクトは、頂点５０１，５０３，５０５，５０７，及び５０９を有する。第２のプリミティブオブジェクトは、頂点５１１，５１３，５１５，５１７，及び５１９を有する。すなわち、各プリミティブオブジェクトは、いくつかのプリミティブを含む。
【００１７】
第１段階では、頂点及びプリミティブのデータが入力される（４０１において）。図５における三角形は、頂点５０１から５０９及び頂点５１１から５１９を有する２つのプリミティブオブジェクトへとグループ分けされる。プリミティブオブジェクトの各々は、ＭＴＥ４０３により、メモリ空間を適切に割り当てるＤＰＭ４１１を用いてメモリ内に書き込まれ、メモリアドレスは、次のタイル分割段階へと渡される。
【００１８】
第２段階では、ＭＴＥは、頂点５０１から５０９及び頂点５１１から５１９を画面空間内へと不可視であるあらゆる頂点（この事例では存在しない）を画面外として除去しながら処理する。既に解説したように、プリミティブ及び頂点データをフェッチする上でメモリ帯域幅の影響を最小にするために、プリミティブは、マクロタイル内のプリミティブオブジェクトへとグループ分けされる。一般的に、各マクロタイルは、画面サイズの４分の１又は１６分の１である。プリミティブオブジェクトがマクロタイルと交差する場合には、これらのプリミティブオブジェクトのデータは、全体リストに一度だけ書き込むことができる。従って、４０３では、プリミティブオブジェクト（最大数の頂点を有する）は、マクロタイルに関連付けられたメモリ４０９の一部に書き込まれる。各マクロタイルに関連付けられたメモリページは、要求に応じてＤＰＭ４１１によって割り当てられる。頂点及びプリミティブの数は、プリミティブオブジェクトのメモリアドレス（これらは、頂点ポインタとして公知である）と共にＴＥ４０５に送られて、プリミティブオブジェクトが可視であるタイルの制御ストリームに適用される。
【００１９】
第３段階では、ＴＥ４０５は、制御データを各タイルに書き込む。ＭＴＥ４０３において書き込まれるプリミティブオブジェクトからの各プリミティブは、プリミティブオブジェクトの境界ボックスの内側にある各タイルと照合される。タイル内でいずれか可視のプリミティブが存在する場合には、制御データは、そのタイルに関連付けられた制御ストリームに書き込まれる。従って、図５における頂点５０１から５０９を有する第１のプリミティブでは、このプリミティブオブジェクトに関連付けられた制御データは、Ｃ１及びＣ６のようなタイルではなく、Ｃ２，Ｃ３，Ｃ４，及びＣ５（陰付き灰色の）のようなタイルのうちの一部にのみ書き込まれる。同様に、図５における頂点５１１から５１９を有する第２のプリミティブオブジェクトでは、制御データは、Ｂ４及びＢ５のようなタイルのうちの一部に対して書き込まれ、Ｂ６のような他のものには書き込まれない。この段階で書き込まれる制御データは、プリミティブオブジェクト内の頂点及びプリミティブの数に関するプリミティブオブジェクトヘッダ、及び書き込まれるプリミティブオブジェクトのメモリアドレスへの頂点ポインタを含む。ＤＰＭ４１１による制御ストリームでは、別々のメモリ空間が、各タイルに割り当てられる。
【００２０】
最終的に、第４段階では、ＩＳＰ４０７によって３Ｄ画像処理が実施される。３Ｄ処理は、画面内の各タイルに対して実施される。タイル分割のためのデータ構造の概要を示している図６を参照すると、３Ｄ処理は、領域アレイ６０１からの各タイルに対して実施される。各タイルに対する制御データは、図６におけるいくつかの制御ストリーム０からＭを含む。各制御ストリームは、プリミティブオブジェクトヘッダ及び頂点ポインタを含み、各タイルに対する制御データ内の制御ストリーム数は、各タイル内に収まるプリミティブオブジェクトの数に依存する。ＩＳＰは、各タイル６０３の制御ストリームを通して全探索を行い、制御データ６０５内の頂点ポインタによってメモリアドレスから頂点及びプリミティブのデータを読み取る。従って、図５を再度参照すると、タイルの一部は、いかなるプリミティブも含まず、Ｂ２のような一部のタイルは、１つのプリミティブオブジェクトだけからのプリミティブを含み、Ｃ２及びＣ３のような他のタイルは、両方のプリミティブオブジェクトからのプリミティブを含む。隠れ面除去、テクスチャリング、及びシェーディングのような画像処理作動は、タイル内で有効なプリミティブオブジェクトからの全てのプリミティブに対して実施される。
【００２１】
上述の公知の構成は、多くの利点を有するが、一部の欠点を確かに有する。タイル分割システムは、制御データに関するメモリ書込みが１つの制御ストリームから別のものへとジャンプするように、各タイル内のプリミティブオブジェクトを処理する。これは、メモリバーストサイズを突破し、メモリアクセスの効率を低下させる。
また、大きいプリミティブ形状が画面上のタイルの多くを覆う時には、制御データは、多数回繰り返される。特定のメモリブロック内の頂点及びプリミティブのデータは、３Ｄ画像処理中に多くのタイルに対して多数回読み取られる可能性がある。この繰返しによってメモリ帯域幅が拡大する。一方、所定のタイル内で、プリミティブオブジェクトからの頂点及びプリミティブのうちの一部だけしか可視ではなかった場合には、プリミティブオブジェクトデータ全体をフェッチするのは効率的ではない。
【００２２】
マクロタイルに対して頂点及びプリミティブのデータに向けて用いられるメモリページは、要求に応じて割り当てられ、従って、必ずしも連続したページであるわけではない。特定のプリミティブオブジェクトからのデータがページ境界と交差するのを防ぐために、現在のページ上にプリミティブオブジェクト全体に対する十分な空間が存在しない場合には、空き記憶領域からの新しいページが割り当てられる必要がある。この割り当てによって浪費が生じる。また、パイプラインシステムでは、プリミティブオブジェクトの正確なサイズは、オブジェクト全体が実際に書き込まれるまでは既知ではなく、従って、開始時点で最大サイズを仮定する必要がある。この仮定によって更に別の浪費が生じる。
【００２３】
図２を参照して冒頭で解説した部分レンダリングでは、圧縮／解凍ユニット２１１が、ｚデータを圧縮してそれをメモリ２０９内に書込み始める時に、タイルに関する圧縮ｚデータのサイズが既知ではない点で類似の問題が存在する。タイルに関する圧縮データがメモリページと交差するのを回避するために、圧縮／解凍ユニット２１１は、タイルの開始時点に現在のメモリページ内に十分な空間が存在するか否かを検査する必要がある。この検査は、圧縮ｚデータに対して最大サイズを仮定する必要があり、それによって浪費が生じる。
【先行技術文献】
【特許文献】
【００２４】
【特許文献１】英国特許第２２８１６８２号
【特許文献２】英国特許第２２９８１１１号
【特許文献３】ＰＣＴ／ＧＢ９９／０３７０７（ＷＯ２０００／０２８４８３）
【特許文献４】ＰＣＴ／ＧＢ２００４／００１０７６（ＷＯ２００４／０８６３０９）
【特許文献５】英国特許第２３４３６０３号
【特許文献６】ＰＣＴ／ＧＢ０１／０２５３６（ＷＯ２００１／０９５２５７）
【特許文献７】英国特許出願第０６１９３２７．０号
【特許文献８】ＧＢ０６０６１９３２７．０
【発明の概要】
【発明が解決しようとする課題】
【００２５】
本発明者は、上述の公知のシステムに様々な改善を加えることができると考えられることを見出した。
【課題を解決するための手段】
【００２６】
本発明の第１の態様により、生成される画像が少なくとも１つの形状を各々含む複数のオブジェクトを含む３次元コンピュータ画像を生成する方法を提供し、本方法は、ａ）画像を複数の矩形区域に細分割し、各矩形区域を複数の小区域に細分割する段階と、ｂ）画像内のオブジェクトの少なくとも一部に対して、オブジェクト内の各形状に関する面データ及び頂点データと、面データと頂点データの間のポインタとを含むオブジェクトデータをメモリに記憶する段階と、ｃ）画像内の各小区域に対して、ｉ）段階ｂ）で記憶されたオブジェクトデータから、２つ又はそれよりも多くのオブジェクトに関するオブジェクトデータを抽出する段階、ｉｉ）画像内の小区域のうちのどれが、段階ｉ）でオブジェクトデータが抽出されたオブジェクトのうちの１つ又は全てを含むかを計算する段階、ｉｉｉ）段階ｉｉ）で計算された小区域の各々に対して、小区域内に含まれるオブジェクト又はその各々に関するオブジェクトデータにリンクする制御データセットを導出する段階、及びｉｖ）ｂ）における全てのオブジェクトに対して制御データが導出されるまで段階ｉ）からｉｉｉ）を繰り返す段階によって小区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データを導出する段階と、ｄ）制御データ及びオブジェクトデータから各矩形区域に関する深度データを導出する段階と、ｅ）表示に向けて深度データから画像データ及びシェーディングデータを導出する段階とを含む。
【００２７】
制御データは、２つ又はそれよりも多くのオブジェクトから一度に導出されるので、メモリアクセスが改善される。段階ｉｉｉ）で導出される各制御データセットは、段階ｉ）でオブジェクトデータが抽出された小区域内に含まれる全てのオブジェクトのオブジェクトデータへのリンクを含む。
好ましくは、段階ｉｉｉ）で導出された各制御データセットにおける最終メモリ位置に、小区域に関する次の制御データセットへのポインタが設けられ、最終メモリ位置は、キャッシュに記憶される。すなわち、制御データは、段階ｉ）でオブジェクトデータが抽出された小区域内に含まれる全てのオブジェクトのオブジェクトデータへのリンクを含むことになるので、この小区域内に収まる１つよりも多くのオブジェクトが存在したとしても、キャッシュは、一度アクセスするだけでよい。
【００２８】
一実施形態では、段階ｂ）は、画像の全てのオブジェクトに対してオブジェクトデータをメモリに記憶する段階を含む。これは、記憶される全てのオブジェクトデータに対して十分なメモリ空間が存在する場合のことである。
【００２９】
代替実施形態では、段階ｂ）は、画像内の所定数のオブジェクトに対してオブジェクトデータをメモリに記憶する段階を含み、本方法は、画像内の全てのオブジェクトに対してオブジェクトデータを記憶し終わるまで、段階ｅ）の前に段階ｂ）、段階ｃ）、及び段階ｄ）を繰り返す段階を更に含む。所定数は、利用可能メモリサイズによって判断することができる。
１つの好ましい実施形態では、段階ｉ）は、段階ｂ）で記憶されたオブジェクトデータから２つのオブジェクトに関するオブジェクトデータを抽出する段階を含む。
【００３０】
本発明の第１の態様により、生成される画像が少なくとも１つの形状を各々含む複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置も提供し、装置は、ａ）画像を複数の矩形区域に細分割し、各矩形区域を複数の小区域に細分割するための手段と、ｂ）画像内のオブジェクトの少なくとも一部に対して、オブジェクト内の各形状に関する面データ及び頂点データと、面データと頂点データの間のポインタとを含むオブジェクトデータをメモリに記憶するための手段と、ｃ）画像内の各小区域に対して、小区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データを導出するために、ｉ）記憶するための手段によって記憶されたオブジェクトデータから、２つ又はそれよりも多くのオブジェクトに関するオブジェクトデータを抽出し、ｉｉ）画像内の小区域のうちのどれが、オブジェクトデータが抽出されたオブジェクトのうちの１つ又は全てを含むかを計算し、ｉｉｉ）ｉｉ）で計算された小区域の各々に対して、小区域内に含まれるオブジェクト又はその各々に関するオブジェクトデータにリンクする制御データセットを導出し、かつｉｖ）ｂ）における全てのオブジェクトに対して制御データが導出されるまでｉ）からｉｉｉ）を繰り返すように構成された導出手段と、ｄ）制御データ及びオブジェクトデータから各矩形区域に関する深度データを導出するための手段と、ｅ）表示に向けて深度データから画像データ及びシェーディングデータを導出するための手段とを含む。
【００３１】
本発明の第２の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法を提供し、本方法は、ａ）画像を複数の個別区域に細分割する段階と、ｂ）画像内のオブジェクトの少なくとも一部に対して、オブジェクトデータをメモリに記憶する段階と、ｃ）一度に２つの個別区域に対して、２つの個別区域内のオブジェクトデータにリンクする制御データを導出する段階と、ｄ）ｉ）制御データ及びオブジェクトデータから第１の個別区域に関する深度データを導出し、更に、表示に向けて深度データから第１の個別区域に関する画像データ及びシェーディングデータを導出し、かつｉｉ）制御データ及びオブジェクトデータから第２の個別区域に関する深度データを導出し、更に、表示に向けて深度データから第２の個別区域に関する画像データ及びシェーディングデータを導出することを並行して行うことにより、２つの個別区域内に３次元コンピュータ画像を生成する段階と、ｅ）全ての個別区域に対して画像が生成されるまで段階ｃ）及び段階ｄ）を繰り返す段階とを含む。
【００３２】
ｄ）において２つの個別区域が並行して処理されるので、処理は、より迅速に達成される。
各個別区域は、好ましくは、矩形である。２つの個別区域は、好ましくは、１つが左に、１つが右に隣接する矩形の個別区域である。
１つの好ましい実施形態では、各オブジェクトは、複数の頂点を有する複数の形状を含み、段階ｃ）で導出された制御データは、各オブジェクトに対して、オブジェクトのどの形状が個別区域のうちのどれに収まるかに関する指示、及びオブジェクトのどの頂点が個別区域のうちのどれに収まるかに関する指示を含む。
形状及び頂点が何処に収まるかというこの指示は、深度データが導出される時に、処理されている個別区域内に実際に収まらない形状又は頂点に関するデータを取得するいかなる不要なデータフェッチも存在しないことを意味する。
【００３３】
一実施形態では、制御データは、ヘッダ部分及びペイロード部分を含む。好ましくは、ヘッダ部分は、オブジェクトのどの頂点が個別区域のうちのどれに収まるかに関する指示を含む。
好ましくは、オブジェクトの形状のうちの一部が、個別区域の各々に収まるか、又はオブジェクトの形状のうちの全てが、個別区域のうちの１つのみに収まる場合には、ペイロードは、オブジェクトのどの形状が個別区域のうちのどれに収まるかに関する指示を含む。
【００３４】
本発明の第２の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置も提供し、装置は、ａ）画像を複数の個別区域に細分割するための手段と、ｂ）画像内のオブジェクトの少なくとも一部に対して、オブジェクトデータをメモリに記憶するための手段と、ｃ）一度に２つの個別区域に対して、２つの個別区域内のオブジェクトデータにリンクする制御データを導出するための導出手段と、ｄ）２つの個別区域内に３次元コンピュータ画像を生成するための第１の画像発生器を第２の画像発生器と並列に備える画像発生器とを含み、第１の画像発生器は、第１の個別区域に対して、制御データ及びオブジェクトデータから深度データを導出し、更に、表示に向けて深度データから第１の個別区域に関する画像データ及びシェーディングデータを導出するように構成され、第２の画像発生器は、第２の個別区域に対して、制御データ及びオブジェクトデータから深度データを導出し、更に、表示に向けて深度データから第２の個別区域に関する画像データ及びシェーディングデータを導出するように構成される。
【００３５】
本発明の第３の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法を提供し、本方法は、ａ）画像を複数の個別区域に細分割する段階と、ｂ）画像内のオブジェクトの少なくとも一部に対して、第１のエンジンが、メモリページに分割されているメモリにオブジェクトデータを記憶する段階と、ｃ）ｂ）でオブジェクトデータが記憶された各オブジェクトに対して、オブジェクトデータが１つのメモリページ上に記憶された場合に、第１のエンジンが、このメモリページアドレスを第２のエンジンに送る段階、又はオブジェクトデータが２つのメモリページ上に記憶された場合に、第１のエンジンが、これらのメモリページアドレスを第２のエンジンに送る段階と、ｄ）画像内の各個別区域に対して、第２のエンジンが、ｂ）で記憶されたオブジェクトデータが１つのメモリページ上に記憶された場合に１つのメモリページアドレスを含み、ｂ）で記憶されたオブジェクトデータが２つのメモリページ上に記憶された場合に２つのメモリページアドレスを含む、小区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データを導出する段階と、ｅ）各個別区域に対して、制御データ及びオブジェクトデータから深度データを導出する段階と、ｆ）表示に向けて深度データから画像データ及びシェーディングデータを導出する段階とを含む。
【００３６】
オブジェクトが２つのメモリページに記憶されることは、データが２つのページにわたって延びる（データが複写されるのではなく）ことを意味する。ｂ）において記憶されるオブジェクトデータは、単一のメモリページ上、又は２つのメモリページにわたって記憶することができるのでメモリ浪費が低減する。２つのメモリページアドレスが制御データ内に含まれるので、画像が処理される時に正しいメモリページを得ることができる。
【００３７】
本方法は、メモリマネージャが、メモリのページを画像内のオブジェクトに割り当てる段階を更に含む。この場合、メモリマネージャは、２つのメモリページを各オブジェクトに自動的に割り当てることができる。実際に、オブジェクトデータが１つのメモリページしか必要としない場合には、第２のメモリページは、単純に次のオブジェクトデータセットに向けて用いられる。
好ましくは、深度データを導出する段階ｅ）は、個別区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データが１つ又は２つのいずれのメモリページアドレスを含むか否かを判断する段階を含む。
【００３８】
本発明の第３の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置も提供し、装置は、ａ）画像を複数の個別区域に細分割するための手段と、ｂ）画像内のオブジェクトの少なくとも一部に対して、オブジェクトデータをメモリに記憶するための第１のエンジンと、ｃ）小区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データを導出するための第２のエンジンと、ｄ）各個別区域に対して、制御データ及びオブジェクトデータから深度データを導出するための手段と、ｆ）表示に向けて深度データから画像データ及びシェーディングデータを導出するための手段とを含み、メモリは、メモリページに分割され、第１のエンジンは、オブジェクトデータが記憶された各オブジェクトに対して、ｉ）オブジェクトデータが１つのメモリページ上に記憶された場合に、このメモリページアドレスを第２のエンジンに送り、かつｉｉ）オブジェクトデータが２つのメモリページ上に記憶された場合に、これらのメモリページアドレスを第２のエンジンに送り、制御データは、第１のエンジンによって記憶されたオブジェクトデータが１つのメモリページ上に記憶された場合に、１つのメモリページアドレスを含み、第１のエンジンによって記憶されたオブジェクトデータが２つのメモリページ上に記憶された場合に、２つのメモリページアドレスを含む。
【００３９】
装置は、メモリのページを画像内のオブジェクトに割り当てるためのメモリマネージャを更に含むことができる。メモリマネージャは、２つのメモリページを各オブジェクトに自動的に割り当てるように構成することができる。
好ましくは、深度データを導出するための手段は、個別区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データが１つ又は２つのいずれのメモリページアドレスを含むか否かを判断するように構成される。
【００４０】
本発明の第３の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法も提供し、本方法は、ａ）画像を複数の個別区域に細分割する段階と、ｂ）メモリページに分割され、かつルックアップテーブルを含むメモリを準備する段階と、ｃ）メモリマネージャが、ルックアップテーブル内の２つ又はそれよりも多くの連続部分を各個別区域に割り当て、ルックアップテーブル内の各割り当てられた部分が、その個別区域に関するオブジェクトデータを記憶するために利用可能なメモリページを指し示す段階と、ｄ）画像内のオブジェクトの少なくとも一部に対して、第１のエンジンが、各個別区域に関するオブジェクトデータを段階ｃ）でその個別区域に割り当てられたメモリページに記憶する段階と、ｅ）各個別区域に対して、第１のエンジンが、ルックアップテーブル内の２つ又はそれよりも多くの割り当て部分のメモリアドレスを第２のエンジンに送る段階と、ｆ）画像内の各個別区域に対して、第２のエンジンが、第１のエンジンから送られたメモリアドレスを用いて、小区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データを導出する段階と、ｇ）画像内の各個別区域に対して、第１のエンジンから送られたメモリアドレスを用いて、制御データ及びオブジェクトデータから深度データを導出する段階と、ｈ）表示に向けて深度データから画像データ及びシェーディングデータを導出する段階とを含む。
【００４１】
各個別区域に割り当てられた連続部分を有するルックアップテーブルを用いることにより、この個別区域に関するオブジェクトデータが記憶される実際のメモリページは、連続のものである必要はない。これは、メモリページが必ずしも連続するわけではない場合であっても、オブジェクトデータが２つのメモリページに及ぶことができることを意味する。それによってメモリ使用量が改善され、浪費が低減する。本明細書では、順序又は一連における次のものを意味するのに「連続」という用語を用いており、すなわち、ルックアップテーブル内の２つ又はそれよりも多い連続部分は、ルックアップテーブル内で一方が他方に続く隣接部分である。
【００４２】
本発明の第３の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置も提供し、装置は、ａ）画像を複数の個別区域に細分割するための手段と、ｂ）メモリページに分割され、かつルックアップテーブルを含むメモリと、ｃ）ルックアップテーブル内の各割り当てられた部分が、その個別区域に関するオブジェクトデータを記憶するのに利用可能なメモリページを指し示し、ルックアップテーブル内の２つ又はそれよりも多くの連続部分を各個別区域に割り当てるためのメモリマネージャと、ｄ）各個別区域に対して、画像内のオブジェクトの少なくとも一部に関するオブジェクトデータをメモリマネージャによってその個別区域に割り当てされたメモリページに記憶するように構成された第１のエンジンと、ｅ）各個別区域に対して、ルックアップテーブル内の２つ又はそれよりも多くの割り当てられた部分のメモリアドレスを第１のエンジンから受け取るように構成され、更に、メモリアドレスを用いて、その個別区域内の各オブジェクトに関するオブジェクトデータにリンクする制御データを導出するように構成された第２のエンジンと、ｇ）メモリアドレスを用いて、画像内の各個別区域に関する制御データ及びオブジェクトデータから深度データを導出するための手段と、ｈ）表示に向けて深度データから画像データ及びシェーディングデータを導出するための手段とを含む。
【００４３】
本発明の第４の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法を提供し、本方法は、ａ）画像を複数の個別区域に細分割する段階と、ｂ）画像内のオブジェクトの少なくとも一部に対して、オブジェクトデータを第１のメモリに記憶する段階と、ｃ）オブジェクトデータから各個別区域に関する深度データを導出する段階と、ｄ）各々がリンク部分として割り当てられた部分を含む複数のメモリページを含む、深度データを記憶するための第２のメモリを準備する段階と、ｅ）個別区域に関する深度データが１つのメモリページ上に記憶された場合に、そうであることをこのメモリページのリンク部分内に示し、個別区域に関する深度データが１つよりも多くのメモリページ上に記憶された場合に、この個別区域に対する各メモリページのリンク部分を用いて、この個別区域に対する次のメモリページを指し示す、各個別区域に関する深度データを第２のメモリに記憶する段階と、ｆ）更に別のオブジェクトデータを第１のメモリ内にロードして、既存の内容のうちの少なくとも一部を置換する段階と、ｇ）各個別区域に対して、この個別区域に対する上述の又は各メモリページのリンク部分を読み取ることにより、記憶された深度データを取り出す段階と、ｈ）新しいオブジェクトデータ及び記憶された深度データから最新の深度データを導出し、最新の深度データを記憶して過去に記憶された深度データを置換する段階と、ｉ）メモリ内にロードされる更なるオブジェクトデータがなくなるまで段階ｅ）、段階ｆ）、段階ｇ）、及び段階ｈ）を繰り返す段階と、ｊ）表示に向けて深度データから画像データ及びシェーディングデータを導出する段階とを含む。
【００４４】
本発明の第４の態様により、生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置も提供し、装置は、ａ）画像を複数の個別区域に細分割するための手段と、ｂ）画像内のオブジェクトの少なくとも一部に関するオブジェクトデータを記憶するための第１のメモリと、ｃ）オブジェクトデータから各個別区域に関する深度データを導出するための手段と、ｄ）各々がリンク部分として割り当てられた部分を含む複数のメモリページを含む、深度データを記憶するための第２のメモリと、ｅ）個別区域に関する深度データが１つのメモリページ上に記憶された場合に、そうであることをこのメモリページのリンク部分内に示し、個別区域に関する深度データが１つよりも多くのメモリページ上に記憶された場合に、この個別区域に対する各メモリページのリンク部分を用いて、この個別区域に対する次のメモリページを指し示す、各個別区域に関する深度データを第２のメモリに記憶するための手段と、ｆ）更に別のオブジェクトデータを第１のメモリ内にロードして、既存の内容のうちの少なくとも一部を置換するための手段と、ｇ）各個別区域に対して、この個別区域に対する上述の又は各メモリページのリンク部分を読み取ることにより、記憶された深度データを取り出すための手段と、ｈ）新しいオブジェクトデータ及び記憶された深度データから最新の深度データを導出し、最新の深度データを記憶して過去に記憶された深度データを置換するための手段と、ｉ）表示に向けて深度データから画像データ及びシェーディングデータを導出するための手段とを含む。
本発明の一態様に関連して説明した態様は、本発明の別の態様にも適用可能である。
既存のシステムは、図１から６を参照して既に説明した。
本発明の例示的な実施形態は、図７から図１１を参照して以下に説明する。
【図面の簡単な説明】
【００４５】
【図１】第１の公知のレンダリング及びテクスチャリングシステムの概略図である。
【図２】図１のシステムに対して改善をもたらす第２の公知のレンダリング及びテクスチャリングシステムの概略図である。
【図３】図２のシステムに対して改善をもたらす第３の公知のレンダリング及びテクスチャリングシステムの概略図である。
【図４】図３のレンダリング及びテクスチャリングシステムの詳細図である。
【図５】タイル、プリミティブ、及びプリミティブオブジェクトを示すシーンの概略図である。
【図６】タイル分割のためのデータ構造の外観図である。
【図７】本発明の第１の態様の実施形態の方法の流れ図である。
【図８】本発明の第２の態様の実施形態による２つの半タイルを用いたタイル分割のためのデータ構造の外観図である。
【図８ａ】本発明の第２の態様の実施形態におけるプリミティブオブジェクトヘッダ構造の図である。
【図８ｂ】本発明の第２の態様の実施形態における２つの１６ビットプリミティブ半マスクが存在する場合のプリミティブワードマスク構造の図である。
【図８ｃ】本発明の第２の態様の実施形態における１つの３２ビットプリミティブマスクが存在する場合のプリミティブワードマスク構造の図である。
【図８ｄ】本発明の第２の態様の実施形態における１つの３２ビットプリミティブマスクが存在する場合の別のプリミティブワードマスク構造の図である。
【図８ｅ】本発明の第２の態様の実施形態における２つの３２ビットプリミティブマスクが存在する場合のプリミティブワードマスク構造の図である。
【図９】プリミティブオブジェクトに割り当てられた２つの頂点ポインタを示す本発明の第３の態様の実施形態の概略図である。
【図１０】メモリページ割り当てを連続的にするルックアップテーブルの使用を示す本発明の第３の態様の代替実施形態の概略図である。
【図１１】本発明の第４の態様の実施形態による圧縮ｚバッファにおけるページリンクの概略図である。
【発明を実施するための形態】
【００４６】
上述のように、本発明の第１の態様によると、制御ストリームデータを導出する方法によってメモリ使用量を改善することができる手法が達成される。ここで、第１の態様の実施形態を以下に説明する。
図４、図５、及び図６を参照して上述したように、標準的な構成では、ＴＥ４０５は、ＭＴＥ４０３からプリミティブオブジェクト（各々がいくつかのプリミティブを含む）を取得し、このプリミティブオブジェクトをレンダリングするのに必要な最少タイル数を計算する。例えば、図５の第１のプリミティブオブジェクトをレンダリングするのに必要なタイルはＣ２，Ｃ３，Ｃ４，Ｃ５，Ｂ３，Ｂ４，Ｂ５，及びＡ４である。次に、この最少タイルリストは処理されて、プリミティブオブジェクトのアドレスへの頂点ポインタが、タイルに存在するプリミティブを表すプリミティブオブジェクトヘッダと共に動的割り当てメモリに制御ストリームとして書き込まれる。これを図６に示す。
【００４７】
各タイルは、制御ストリームデータに向けて用いられる独自のメモリブロックを有し、これらのメモリブロックは、要求に応じてＤＰＭ４１１によって割り当てられる。特定のタイルに対する制御ストリームに追加される新しいデータが、ＤＰＭ４１１によって割り当てられた現在のメモリブロックを超えることになる場合には、新しい割り当てが要求され、古い制御ストリームは、ストリームリンクを用いて新しい割り当てにリンクされる。ＭＴＥ４０３が終了信号によってシーンの終了を示すと、全てのタイルが処理されて、有効領域内のタイルに対する制御システムが終了ワードで終了される。
【００４８】
大きいプリミティブを含むプリミティブオブジェクトでは、プリミティブオブジェクトが１つよりも多くのマクロタイルを覆う時に、全体リストを用いることができるが、制御ストリームデータは、プリミティブが収まる全てのタイルに対して数回書き込まれることを必要とする可能性がある。極端な場合には、制御ストリームデータを画面上の全てのタイルに対して書き込まなければならない場合がある。制御ストリームデータのそのような繰返しは、効率的なメモリ使用をもたらさない。
【００４９】
ＧＢ０６０６１９３２７．０から、ＴＥに追加された小さいキャッシュである「テールポインタキャッシュ（ＴＰＣ）」を用いてメモリアクセスを改善することができることは公知である。タイル内の制御ストリームの最後のメモリ位置が記憶され、次に、メモリをアクセスする必要がある時に、「テールポインタキャッシュ」から読み取られる。それによってＴＥからの主メモリアクセスが低減する。ＴＰＣの付設により、必要な主メモリアクセスの回数は低減するが、１つのタイルから次のものへの制御ストリーム間の頻繁なアドレス変更は改善されない。制御ストリームの書込みは配分されるので、ＴＰＣの付設は、幅広のバスを有するメモリインタフェースに対してはそれ程有効ではない。例えば、メモリインタフェースが１２８ビット幅であった場合には、２つの３ビットワード制御データを各タイル内に書き込む段階は、メモリ書込みの殆どを最大バーストのものにしないことになる（３２ビット×２は１２８ビットを大きく下回る）。この場合、１２８ビットのバースト書込みで有効な６４ビットのみを更新するために、バースト書込みの一部をマスクする必要がある（すなわち、未使用６４ビットを）。メモリモジュールにおけるこの種のマスクされたバースト書込みには、性能低下が生じる可能性がある。
【００５０】
本発明のこの実施形態では、ＴＥは、ＭＴＥから一度に２つのプリミティブオブジェクト（１つではなく）を取得する。ＴＥは、特定のタイルに対して２つのプリミティブオブジェクトを同時に処理する。従って、各プリミティブオブジェクトを取得して、このプリミティブオブジェクトが収まるタイルの全てを通じて作業し、次に、別のプリミティブオブジェクトを取得し、以降同様に続ける代わりに、ＴＥは、２つのプリミティブオブジェクトを一度に取得し、それによってメモリ使用量及びアクセスが改善される。
【００５１】
図５を参照すると、ＴＥは、ＭＴＥから両方のプリミティブオブジェクトを取得する。ＴＥは、片方又は両方のプリミティブオブジェクトが収まる各タイル（この事例では陰付きタイル）に関する制御ストリームデータを順次書き込む。片方のプリミティブオブジェクトだけが収まるタイル（例えば、タイルＢ５）に対しては、ＴＥは、このプリミティブオブジェクトに関する制御ストリームデータを書き込む。制御ストリームの最後では、メモリ位置が、テールポインタキャッシュ（ＴＰＣ）に記憶される。両方のプリミティブオブジェクトが収まるタイル（例えば、タイルＣ３）に対しては、ＴＥは、第１のプリミティブオブジェクトに関する制御ストリームデータを生成する。次に、ＴＥは、第２のプリミティブオブジェクトに関する制御ストリームデータを生成する。このタイルにおける両方のプリミティブオブジェクトに対する制御ストリームデータは、メモリに一緒に書き込まれる。別のタイルに対して処理を続ける前に、このタイルの処理にわたる全ての処理の最後において、制御ストリームの最終メモリアドレスがＴＰＣに記憶される。
【００５２】
この実施形態の一般的な方法を図７の流れ図に示す。タイル分割が２つのプリミティブオブジェクトに対して行われ、各プリミティブオブジェクトは、３２個までの形状（プリミティブとも呼ぶ）を収容することができる。
すなわち、２つのプリミティブオブジェクトが収まるタイルでは、このタイルに関する制御ストリームの最後におけるアドレスは、従来のシステムでの２度ではなく、一度だけ読み取られる必要がある。これらのタイルに対しては、制御ストリームデータ書込みは、１２８ビットよりも小さい２回のマスクされた書込みではなく、１２８ビットの最大バースト書込みになる。ＴＰＣアクセスは、これらのタイルでは半分になる。本発明者は、一部の事例において制御ストリームデータに関する１２８ビットの最大バースト書込みを０％から２５％に増大させることができ、一部の事例においてＴＰＣキャッシュミスの百分率を１２％から０．０４％に低減することができることを見出した。
【００５３】
上述の実施形態をＴＥがＭＴＥから２つのプリミティブオブジェクトを一度に取得する場合で説明した。明らかに、本方法は、ＴＥが一度に２つよりも多くのオブジェクトをＭＴＥから取得するように拡張することができる。毎回得られるプリミティブオブジェクトの数は、レンダリングされるシーンの複雑さ、プリミティブオブジェクト自体の複雑さ（すなわち、これらのプリミティブオブジェクトがいくつの面及び頂点を含むか）、及びＴＥの処理機能に依存することになる。
【００５４】
上述のように、本発明の第２の態様によると、２つの等しい３Ｄ画像処理パイプが２つのタイルに対して同時に機能することを可能にすることによって３Ｄ画像発生器の性能を改善する手法が達成される。これを図８に示す。
図８は、図４の簡略化したものであり、ＴＥ、ＩＳＰ、及びメモリのみを示している。ＴＥ８０１は、制御データをメモリ８０９に書き込む。３Ｄパラメータフェッチ８０３は、頂点及びプリミティブのデータを読み取って画像処理を実施する。この実施形態では、この処理は、２つのサブＩＳＰ／ＴＳＰ８０５及び８０７によって並行して実施される。この構成では、３Ｄ画像処理の性能は、二倍になると予想される。
図８のシステムを有効に作動させるために、ＴＥ８０１は、タイルのうちの２つに対して互いに制御データを書き込む。この書込みを８１１に略示している。本方法は、タイル分割制御ストリームデータにおける重複を大幅に低減し、従って、良好なメモリ帯域幅の改善を与える。
【００５５】
各タイルサイズが１６×１６ピクセルであった場合には、ＴＥ８０１は、全てのプリミティブオブジェクトを元の１６×１６タイルにタイル分割する。しかし、ＴＥは、制御ストリームデータ（８１１に示している）を３２×１６ピクセルのタイル、すなわち、２つの隣接する１６×１６タイルで書き込む。すなわち、各制御ストリームにおいて２つの１６×１６タイルが参照される。この２つのタイルの利点は、両方のタイル内に収まるオブジェクトを一度書き込むだけでよいので、書き込まれる制御ストリームデータの合計量が大きく低減することになる点である。一方、欠点も存在する。制御ストリームデータは、プリミティブオブジェクトの境界ボックスが、両方の１６×１６タイルと重なるという仮定に基づいている。プリミティブオブジェクト内には、例えば、３２個までのプリミティブ及び１６個までの頂点が存在する可能性があるが、これらのプリミティブ及び頂点の全てが特定の１６×１６タイルに収まることにはならない。プリミティブ及び頂点のうちの一部が、２つの１６×１６タイルのうちの片方にしか収まらない場合には、これらの無効なプリミティブ及び頂点によってパラメータデータ参照情報をフェッチして処理することは浪費になる。別の言い方をすると、２つのタイルを一度に取得することにより、最初に小さいタイルを有するという利点が幾分減少する。
【００５６】
この実施形態では、この問題は、制御ストリーム内で頂点マスク及びプリミティブマスクを用いて解決される。制御ストリームデータは、各プリミティブオブジェクトに対して、プリミティブオブジェクトヘッダ、及びそのプリミティブオブジェクトに関するオブジェクトデータ（プリミティブ及び頂点のデータを含む）のメモリアドレスを指し示す頂点ポインタを含む。この実施形態に用いられるマスクは、各１６×１６タイルに対して有効な頂点及びプリミティブ、すなわち、実際にそのタイル内に収まる頂点及びプリミティブを示している。頂点マスクは、頂点数及びプリミティブ数のような他の情報と共にプリミティブオブジェクトヘッダ内に含めることができる１６ビットのマスクである。頂点マスクは、各３２×１６タイルに対して有効な頂点を定義する。通常は、１６×１６タイルの各々に対して１つづつの２つの３２ビットプリミティブマスクが必要である。プリミティブマスクは、各１６×１６タイルに対して有効なプリミティブを定義する。プリミティブマスクは、ヘッダ内に含めることができ、又は制御ストリームに追加ワードとして加えることを必要とする場合がある。この実施形態では、両方の１６×１６タイルに対して１つの頂点マスクだけしか必要とされず、それに対して各１６×１６タイルに対して１つのプリミティブマスクを必要とすることに注意されたい。これは、頂点データがバーストで読み取られ、レンダリング処理がプリミティブに基づいており、従って、少数の不要頂点を読み取るのにそれ程コストが掛からないことによる。従って、空間を節約するために、３２×１６タイルに対して単一の頂点マスクを用いることができる。一方、不要なプリミティブを処理するには、より多くのコストが掛かり、従って、これを回避するために、より大きな空間を必要とはするが、各１６×１６タイルに対してプリミティブマスクが用いられる。
プリミティブが多くのタイルに重なる時にメモリ帯域幅に対する大きな影響を回避するために、制御ストリーム内のマスクのデータサイズを最小に保つ必要がある。この実施形態は、頂点マスク及びプリミティブマスクが含まれる時に制御ストリームのサイズを縮小する符号化手法を用いる。
【００５７】
既に解説したように、頂点マスク（及び場合によってはプリミティブマスク）は、プリミティブオブジェクトヘッダに含まれる。３２ビットプリミティブオブジェクトヘッダにおける符号化手法の詳細を表１に示す。
【００５８】
（表１）
【００５９】
表１に示しているプリミティブオブジェクトヘッダの構造を図８ａに例示している。
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ：
プリミティブマスク制御フラグ「ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ」に対して２ビット（２０：１９）が用いられる。このフラグは、制御ストリーム内の何処に頂点マスク及びプリミティブマスクが含まれるかを判断する。この符号化では、制御ストリーム内の追加プリミティブマスクワードは任意的である。
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝０１＝ＰＦ＿ＭＡＳＫ＿ＣＴＲＬ＿ＰＲＩＭ＿ＭＡＳＫ＿ＰＲＥＳである場合には、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬは、プリミティブマスクワードが制御ストリームに含まれることを意味する。一方、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１である場合には、プリミティブワードは、制御ストリームに含まれず、ヘッダに含まれる。
【００６０】
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝０１である前者の場合には、１つ又は２つのあらゆる追加プリミティブマスクワードを必要とすることができる。１つ又は２つのいずれの３２ビットワードが存在するかは、ＰＦ＿ＰＲＭ＿ＳＴＡＲＴに示されている。１つの追加プリミティブマスクワードしか持たない条件は、両方のプリミティブマスクが、下位１６ビット又は上位１６ビットセットのいずれかしか持たないということである。これは、両方のプリミティブオブジェクトが、左手１６×１６タイル又は右手１６×１６タイルのいずれかのみで有効であり、両方において有効ではないことを意味する。この場合、２つのプリミティブマスクワードが存在する場合は、片方は単純に０になり、従って、プリミティブワードマスクを完全に省略することができる。代替的に、両方のプリミティブオブジェクト内のプリミティブは、１６×１６タイルのうちの左又は右のいずれか片方においてのみ有効である。そうでなければ、２つの付加的なプリミティブマスクワードが必要とされ、これらは、２つの１６×１６タイル内で参照されるプリミティブに関する制御ストリームに追加される。
【００６１】
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１である後者の場合を有する条件、すなわち、いずれのプリミティブワードも制御ストリームに含まれない条件は、プリミティブオブジェクト内の全てのプリミティブが現在の３２×１６タイル内で参照されるか（すなわち、プリミティブオブジェクト内の全てのプリミティブが両方の１６×１６タイル内に収まり、従って、プリミティブマスクワードの必要がない）、又はプリミティブ及び頂点の両方のマスクに対して１バイト分の非０ビットのみが存在するということである。この第２の条件は、頂点マスクワードが、１バイト分の非０ビットを有し、非０頂点マスクバイトが、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１内にあることを意味する。すなわち、頂点１から８が３２×１６タイル内で参照されないか、又は頂点９から１６が３２×１６タイル内で参照されないかのいずれかである。（後に解説することになるが、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴが１の場合には、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１が頂点マスクの上位８ビットを含み、すなわち、頂点１から８が３２×１６タイル内で参照されないことを示している。ＰＦ＿ＶＴＭ＿ＳＴＡＲＴが０である場合には、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１が頂点マスクの下位８ビットを含み、すなわち、頂点９から１６は、３２×１６タイル内で参照されないことを示している。）ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１である場合には、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０内には、１バイトのプリミティブマスクしか存在せず、従って、３２ビットプリミティブマスクのうちの片方が０である必要がある。すなわち、プリミティブは、１６×１６タイルのうちの左又は右のいずれか片方においてのみ有効である。ＰＦ＿ＰＲＭ＿ＳＴＡＲＴにおける値は、プリミティブマスク内でのＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０のバイトオフセットを示している。例えば、ＰＦ＿ＰＲＭ＿ＳＴＡＲＴ＝１である場合には、３２ビットプリミティブマスクは、０ｘ００００Ｆ７００のように見えることになり、バイト１０×Ｆ７が、ヘッダにＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０として挿入される。
【００６２】
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１である後者の場合には、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１である時に、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０内に詰め込まれた１バイトプリミティブマスクに対して２つの可能性が存在する。
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝００（ＰＦ＿ＭＡＳＫ＿ＣＴＲＬ＿ＰＡＣＫＥＤ＿ＬＥＦＴ）である場合には、プリミティブマスク及び頂点マスクは、両方共にヘッダに含まれ、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０内に詰め込まれた１バイトプリミティブマスクは、３２×１６タイルの左半分に付属する。
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝１１（ＰＦ＿ＭＡＳＫ＿ＣＴＲＬ＿ＰＡＣＫＥＤ＿ＲＩＧＨＴ）である場合には、プリミティブマスク及び頂点マスクは、両方共にヘッダに含まれ、プリミティブマスクは、３２×１６タイルの右半分に付属する。
すなわち、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬのこれらの２ビットが、００，１１，又は１０である場合には、制御ストリームにいかなる追加プリミティブマスクも存在しない。
【００６３】
ＰＦ＿ＰＲＭ＿ＳＴＡＲＴ：
プリミティブマスク開始点「ＰＦ＿ＰＲＭ＿ＳＴＡＲＴ」に対して２ビット（１８：１７）が用いられる。ＰＦ＿ＰＲＭ＿ＳＴＡＲＴは、プリミティブマスクがヘッダに含まれるか（ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１）、又は制御ストリームに追加マスクとして含まれるか（ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝０１）のいずれであるかに依存して別々に用いられる。
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１である場合には、この２ビットは、プリミティブマスクがヘッダに含まれる時のプリミティブマスク内でのＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０のバイトオフセットを示している。
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝０１である場合には、この２ビットは、以下の通りに制御ストリームにどの追加マスクが含まれるかを示す上で用いられる。
【００６４】
これらの２ビット、すなわち、ＰＦ＿ＰＲＭ＿ＳＴＡＲＴが００である場合には、制御ストリームに２つの１６ビットプリミティブマスクが含まれ、すなわち、左右の１６×１６タイルに対する３２ビットプリミティブマスクの両方が、下位１６ビットを０として又は上位１６ビットを０として、そのいずれかで有する。ＰＦ＿ＶＴＭ＿ＳＴＡＲＴ＝０である場合には、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、２つの１６ビットプリミティブマスクがビット０から１５におけるものであり、かつ両方の１６×１６タイルに対してプリミティブ１から１６のみが参照されることを示している。ＰＦ＿ＶＴＭ＿ＳＴＡＲＴ＝１である場合には、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、２つの１６ビットプリミティブマスクがビット１６から３１におけるものであり、かつ両方の１６×１６タイルに対してプリミティブ１７から３２のみが参照されることを示している。
これらの２つの１６ビットプリミティブマスクは、３２ビットプリミティブマスクワードへと組み合わされる。これを下記の表２に示す。
【００６５】
（表２）
【００６６】
この場合のプリミティブマスクワードの構造を図８ｂに示す。ビット０から１５は、左手１６×１６タイルに対する１６ビットプリミティブ半マスクのために用いられる。ビット１６から３１は、右手１６×１６タイルに対する１６ビットプリミティブ半マスクのために用いられる。
２つのビット、すなわち、ＰＦ＿ＰＲＭ＿ＳＴＡＲＴが０１である場合には、左手１６×１６タイルに対して１つの３２ビットプリミティブマスクが制御ストリームに含まれる。これを下記の表３に示す。
【００６７】
（表３）
【００６８】
この場合のプリミティブマスクワードの構造を図８ｃに示す。
２つのビット、すなわち、ＰＦ＿ＰＲＭ＿ＳＴＡＲＴが１０である場合には、右手１６×１６タイルに対して１つの３２ビットプリミティブマスクが制御ストリームに含まれる。これを下記の表４に示す。
【００６９】
（表４）
【００７０】
この場合のプリミティブマスクワードの構造を図８ｄに示す。
最後に、２つのビット、すなわち、ＰＦ＿ＰＲＭ＿ＳＴＡＲＴが１１である場合には、各１６×１６タイルに対して１つの２つの３２ビットプリミティブマスクが制御ストリームに含まれる。これを下記の表５ａ及び５ｂに示す。
【００７１】
（表５ａ）
【００７２】
（表５ｂ）
【００７３】
この場合のプリミティブマスクワードの構造を図８ｅに示す。
【００７４】
ＰＦ＿ＶＴＭ＿ＳＴＡＲＴ：
表１を再度参照すると、頂点マスク開始点「ＰＦ＿ＶＴＭ＿ＳＴＡＲＴ」に対して１ビット（１６）が用いられる。ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、プリミティブマスクがヘッダに含まれるか（ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１）、又は制御ストリーム内の追加マスクとして含まれるか（ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝０１）のいずれであるかに依存して別々に用いられる。
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１であり、すなわち、プリミティブマスクがヘッダに含まれる場合には、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴのビットが設定され、すなわち、＝１である場合に、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１（下記に解説することになる）が、１６ビット頂点マスクの上位８ビットであるバイト１を反映することを示している。このビットが消去され、すなわち、＝０である場合には、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１が、１６ビット頂点マスクの下位８ビットであるバイト０を含むことを示している。
【００７５】
ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝０１であり、すなわち、プリミティブマスクが制御ストリームに追加され、かつＰＦ＿ＰＲＭ＿ＳＴＡＲＴ＝００である場合には、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴが１である場合に、ＰＦ＿ＶＴＭ＿ＳＴＡＲＴは、１６ビットプリミティブ半マスクの両方が、プリミティブ３１：１６に適用されることを示している。上記以外の場合は、これらは、１５：０に適用される。
【００７６】
ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１：
「ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１」に対して８ビットが用いられる。ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１は、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ及びＰＦ＿ＶＴＭ＿ＳＴＡＲＴのステータスに依存する。ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１、すなわち、プリミティブマスクが、ヘッダ内のＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０内に含まれ、かつＰＦ＿ＶＴＭ＿ＳＴＡＲＴが１に等しい場合には、これらの８ビットは、１６ビット頂点マスクの上位８ビットである。一方、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１であり、かつＰＦ＿ＶＴＭ＿ＳＴＡＲＴが０に等しい場合には、これらの８ビットは、１６ビット頂点マスクの下位８ビットである。
【００７７】
ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０：
「ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０」に対して８ビットが用いられる。ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０は、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ及びＰＦ＿ＰＲＭ＿ＳＴＡＲＴのステータスに依存する。ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ＝０１、すなわち、プリミティブマスクが、ヘッダではなく制御ストリームに含まれる場合には、１６ビット頂点マスクは、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０及びＰＦ＿ＭＡＳＫ＿ＢＹＴＥ１内にあり、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０は、頂点マスクの下位８ビットである。一方、ＰＦ＿ＭＡＳＫ＿ＣＯＮＴＲＯＬ≠０１である場合には、プリミティブマスクからの１つの非０バイトが、ＰＦ＿ＭＡＳＫ＿ＢＹＴＥ０内にある。この場合、この非０バイトプリミティブマスクのバイトオフセットは、ＰＦ＿ＰＲＭ＿ＳＴＡＲＴからのものである。
【００７８】
ＴＥが、３２×１６タイル内のプリミティブオブジェクトからのプリミティブ及び頂点データを処理する場合には、ＴＥは、オブジェクト内の全ての頂点を検査して、タイル内の有効頂点に対する頂点マスクを作成する。次に、ＴＥは、１６×１６タイルの各々に収まるオブジェクト内の有効プリミティブに対するプリミティブマスクを生成する。上述の符号化手法は、次に、頂点マスク及びプリミティブマスクを制御ストリームデータ内に可能な限り小さいサイズで書き込む上で用いられる。
【００７９】
制御ストリームの最後のテールポインタアドレスは、「テールポインタキャッシュ（ＴＰＣ）」を通じて３２×１６タイルへのタイル分割の開始時点で読み戻される。テールポインタアドレスは、タイルの全ての処理が完了した後に初めて書き戻される。３２×１６タイルの両方の１６×１６タイルが、両方のプリミティブオブジェクト含む場合は（図５に戻り、例えば、タイルＣ３及びＣ４を参照されたい）、２つのプリミティブオブジェクトは、２つの１６×１６タイル内で処理されることになり、ＴＰＣが制御ストリームの最後に対するテールポインタで更新される前に、制御ストリームに書き込まれた適切な制御データを有する。それによって制御ストリームデータ書込みからのメモリアクセスが改善され、ＴＰＣの性能が改善される。
【００８０】
本発明のこの実施形態では、各３２×１６タイルの制御ストリームが一度に処理される。３２×１６タイルでは、タイル内で参照される頂点は、頂点マスクを用いてメモリからフェッチされる。このフェッチは、図８のパラメータフェッチ８０３によって実施される。従って、タイル内で参照されないフェッチ頂点に対していかなるメモリ帯域幅も追加されず、従って、上記に解説した問題は解決される。同様に、１６×１６タイルの各々に対するプリミティブマスクは、プリミティブデータをフェッチするのに用いられる。このフェッチも、図８の８０３によって実施される。上述の場合のように、タイル内で参照されないフェッチプリミティブに対していかなるメモリ帯域幅も追加されない。次に、左手の１６×１６タイルに対して適切なプリミティブ及び頂点が、サブＩＳＰ／ＴＳＰ８０５に送られ、右手の１６×１６タイルに対して適切なプリミティブ及び頂点が、サブＩＳＰ／ＴＳＰ８０７に送られる。
【００８１】
本発明者は、３２×１６ピクセルタイルに基づくタイル分割であるこの実施形態の方法が、１６×１６ピクセルタイルに基づくタイル分割と比較して、付加的なプリミティブマスクワードを用いた場合でさえも平均で３５％の制御ストリームデータ書込みの低減をもたらすことを見出した。３Ｄパラメータフェッチにおける合計のデータ読取りに対しても同等のレベルの低減を達成した。
上述のように、本発明の第３の態様によると、メモリ空間を用いるより効率的な手法が達成される。次に、第３の態様の実施形態を以下に説明する。
【００８２】
既に解説したように、既存のシステムでは、頂点及びプリミティブデータに対するマクロタイルに用いられるメモリページは、要求に応じて割り当てられ、従って、必ずしも連続するページであるわけではない。特定のプリミティブオブジェクトからのデータがページ境界を超えるのを防ぐために、プリミティブオブジェクト全体に対して現在のページ上に不十分な空間しか存在しない場合には、空き記憶領域から新しいページを割り当てる必要がある。
【００８３】
特定のプリミティブオブジェクトに含まれる頂点及びプリミティブの最大数には制限が存在する（例えば、１６個の頂点及び３２個のプリミティブ）。上述のように、ＭＴＥは、プリミティブオブジェクトがメモリのページ境界に架からないことを確実にすべきである。これは、メモリページが、連続する順序で割り当てられることが保証されないからである。頂点をプリミティブオブジェクトに割り当てるパイプラインのフロントエンドは、このプリミティブオブジェクトに残されたいかなる空間量も既知ではないので、上述のことは困難である。一方、メモリを割り当て、実際にプリミティブオブジェクトデータをメモリに入力するパイプラインのバックエンドは、オブジェクト内の頂点数に対していかなる制御も持たない。現在のメモリページにプリミティブオブジェクト内の最大頂点数を保持するのに十分なメモリ空間が存在するか否かの検査が、十分な空間が存在しないことを明らかにした場合には、バックエンドにおいて新しいメモリページの割り当てが実施される。頂点データのサイズは既知であり（Ｘ、Ｙ、Ｚ座標に加えて、基本色、オフセット色、テクスチャ座標、テクスチャ座標がいくつあるか等に関する更に別のデータがある場合がある）、プリミティブオブジェクトに必要な最大メモリ空間は、容易に計算することができる。従って、例えば、プリミティブオブジェクト内の最大頂点数が１６である場合には、バックエンドは、頂点数が１６であることを常に仮定し、フロントエンドは、１つのプリミティブオブジェクト内に実際に１６個までの頂点を含むことができることを常に仮定する。一方では、メモリ帯域幅に関して優れた効率を生じる頂点間の最大共有量を得ることができるので、上述のことは有利である。しかし、他方では、例えば、このメモリページ内に１５個の頂点に対する空間だけしか残っていない場合には、新しいページをバックエンドで開始する必要があるが、それにも関わらず、フロントエンドで割り当てられる頂点の数は実際には１４である可能性がある。しかし、バックエンドは、これを知る由もなく、これに対していかなる制御も持たない。それによって明らかにメモリ浪費が生じる。このメモリ浪費によるコストは、頂点サイズ、すなわち、特定の頂点に関連付けられた追加データ（基本色、オフセット色、テクスチャ座標などのような）と共に変化する。
【００８４】
本発明の第３の態様のこの構成は、この問題を解決するための２つの実施形態を提供する。提案する第１の実施形態は、ＭＴＥによってプリミティブオブジェクトに対して２つのメモリページを割り当てることを可能にする。すなわち、特定のプリミティブオブジェクトは、２つのメモリページにわたることができる。従って、開始時点で、ＭＴＥによってプリミティブオブジェクトがメモリ内に書き込まれる時に、メモリマネージャは、２つのメモリページをそのマクロタイルに割り当てる。（１ページしか実際には必要ではないことになった場合には、第２のページは、単純に次の書込みに用いられる。）全てのプリミティブオブジェクトに対して、頂点及びプリミティブの数が、プリミティブオブジェクトのメモリアドレス（頂点ポインタ）と共にＴＥに送られて、プリミティブオブジェクトが可視であるタイルの制御ストリームに追加される。ＭＴＥがプリミティブオブジェクトデータをメモリ内に連続的に書き込む時には、ＭＴＥは、メモリ書込みがページ境界に架かるか否かを検査する。書込みが、１つのメモリページ範囲に収容されることになる場合には、このメモリページに対する頂点ポインタのみがＴＥに渡されることになる。一方、書込みがページ境界を超え、プリミティブオブジェクトデータが２つのメモリページ上に存在することになる場合には、第１のページ及び第２のページに対する両方の頂点ポインタがＴＥに送られる。
【００８５】
ＭＴＥによってＴＥに送られるデータが、２つの頂点ポインタを含む場合には（ＭＴＥ書込みが、上述のようにページ境界を超えたために）、ＴＥは、このタイルに対する制御ストリーム内のリンクページのアドレスへの追加頂点ポインタを書き込むことになる。これを図９に略示している。
図９では、制御ストリームは、第１のプリミティブオブジェクトに対してプリミティブオブジェクトヘッダを含み、次に、このプリミティブオブジェクトに対する頂点ポインタを含む。従って、このプリミティブオブジェクトに関するオブジェクトデータは、第１のメモリページ上にのみ記憶される。しかし、第２のプリミティブオブジェクトでは、制御ストリームは、プリミティブオブジェクトヘッダ、頂点ポインタ、及び頂点リンクポインタを含む。この頂点リンクポインタは、第２のメモリページへの頂点ポインタであり、頂点ポインタが第１のメモリページを指し示すのに対して、頂点リンクポインタは、第２のメモリページを指し示すことが分る。従って、このプリミティブオブジェクトに関するオブジェクトデータは、第１のメモリページ及び第２のメモリページという２つのメモリページにわたっている。
【００８６】
このタイルに対して画像処理が実施されている時に、制御ストリームは構文解析され、ＩＳＰは、特定のプリミティブオブジェクトに対して２つの頂点ポインタが存在することを把握する。これらの頂点リンクページポインタは、パイプラインの下流へと渡される。メモリアドレスがページ境界を超えた場合には、メモリからプリミティブ及び頂点データをフェッチする上で第２の頂点ポインタからのリンクページアドレスが用いられる。プリミティブオブジェクトサイズの上限、及びメモリページが割り当てられる手法により、ＭＴＥ書込みは、最大２ページしか必要としないことになる、すなわち、１つ又は２つの頂点ポインタしか存在しないことに注意されたい。
【００８７】
提案する第２の実施形態は、ページが連続することを保証する追加論理、及び付加的な小さいキャッシュを用いる「動的パラメータ管理（ＤＰＭ）」を提供する。ページが連続することが保証される場合には、所定のマクロタイルに関する書込みが２ページにわたることを容認することができる。
ページを各マクロタイルに割り当てられたままに保つために、ＭＴＥが連続書込みを行う時に、ＤＰＭは、一部分が各マクロタイルに割り当てられた１つ又は複数のルックアップテーブルページを維持する。ＭＴＥに割り当てられたページは、連続メモリページアドレスではなく、ルックアップテーブル内の連続インデックスである。各マクロタイルに対して、ルックアップテーブル内には、データが書き込まれる実際のメモリページへのポインタを与える部分が存在する。ルックアップテーブル内のこれらの部分は連続し、この連続性は、これらの部分が開始時点にＤＰＭによって割り当てられることから得ることができる。
【００８８】
各マクロタイル（及び用いられている場合は全体リスト）に対して、ＭＴＥへのページ割り当てのために、ＤＰＭ内でカウンタが維持される。ＭＴＥによって書き込まれるデータに対して第１のページがマクロタイルに割り当てられる時に、同様に一部分が、そのマクロタイルに関するルックアップテーブル内に割り当てられる。マクロタイルに割り当てられた第１のページのアドレスは、このマクロタイルに関するルックアップテーブルページ内のこの部分の位置０に書き込まれる。このマクロタイルに対するその後の割り当ては、このマクロタイルに関するルックアップテーブルページ内のこの部分の位置１，２等に書き込まれることになる。従って、実際の割り当てページが連続でない可能性があったとしても、ルックアップテーブルのこれらの部分は連続であり、従って、マクロタイルに関する書込みデータは、１つよりも多くのページにわたることができる。上述のルックアップテーブル部分が一杯になった状態で、新しい部分がルックアップテーブル内に割り当てられ、この位置は、更に別のページアドレス割り当てで埋められる。全てのマクロタイルは、この手法で取り扱われる。最大画面レンダリングが実施された状態で、全てのメモリページ及びルックアップテーブルページは解放される。
【００８９】
従って、ＭＴＥは、一方がデータの書き込まれる実際のアドレス、他方がこのマクロタイルに関するルックアップテーブルページの上述の部分のアドレス（基本アドレス）という２つのアドレスをＤＰＭから受け取る。マクロタイルに関する連続アドレスであるルックアップテーブル内のアドレスは、ＴＥに渡される頂点ポインタ（すなわち、オブジェクトデータに対するメモリアドレス）として用いられ、データが記憶される実際のアドレスは、データをメモリ内に書き込む上で用いられる。
【００９０】
ルックアップテーブルメモリページの基本アドレスは、レジスタ内に保持することができる。３Ｄ画像処理モジュール（ＩＳＰ）は、各タイル内のプリミティブオブジェクトを処理する前にこの基本アドレスを読み取る。各タイル内のプリミティブオブジェクトの処理中に、ルックアップテーブルページの上述の部分のアドレスは、このルックアップテーブルが属するマクロタイルのディレクトリエントリからフェッチされる。制御ストリームから読み戻された頂点ポインタは、実際のデータが書き込まれたメモリアドレスを得るのに用いられる。従って、連続ルックアップテーブルアドレスは、不連続メモリアドレスへと変換される。連続ルックアップテーブルアドレスと不連続メモリアドレスの間のこの変換をより効率的にするために、これらのアドレスにアクセスを行う上でキャッシュを用いることができる。
【００９１】
図１０は、この実施形態を略示している。第１のルックアップテーブルを１００１に示している。ルックアップテーブルに対する基本アドレスが存在する。この基本アドレスは、各マクロタイルＭＴ０，ＭＴ１．．．に対して、各々が２バイトの３２個までのエントリ、すなわち、合計６４バイトを含むルックアップテーブル１００１を指し示す。（図１０では、簡略化のためにＭＴ７に関するエントリのみ示しているが、これは、全てのマクロタイルに当て嵌まる。）この実施形態では、１６個のマクロタイルに加えて全体リスト（１つよりも多くのマクロタイルを横断するオブジェクトデータの記憶のための）が存在し、従って、１７×６４バイト＝１０８８バイトが生じる。この実施形態における各メモリページは、４０９６バイトであり、従って、全てのマクロタイルに全体リストを加えたものに対するエントリは、ページ内に容易に収まる。
【００９２】
各３２個の２バイト部分は、各々のサイズが４０９６バイトであり、すなわち、メモリページを占有する別のルックアップテーブル１００３を指し示す。これを矢印Ａで示している。上述のルックアップテーブル部分は開始時点に割り当てられるのに対して、これらの追加ページは、より効率的なメモリ使用に向けて要求に応じて割り当てられる。各４０９６バイトのテーブル１００３は、２０４８個の２バイト変換情報を含む。これは、仮想ドメイン１（ルックアップテーブル１００３）から仮想ドメイン２（メモリページ１００５）に変換することができることを意味する。各２バイト部分は、４０９６バイトのページ１００５を参照する。これを矢印Ｂで示している。従って、２０４８×４０９６バイト＝約８ＭＢが存在する。３２個のこれらが、各マクロタイルに対して存在し、すなわち、３２×８ＭＢ＝２５６ＭＢである。従って、各マクロタイルは、２５６ＭＢの仮想アドレス空間を保持することができる。
【００９３】
ここで、この実施形態では、メモリの合計量は、２５６ＭＢであり、従って、全てのデータが１つのマクロタイルに存在したとしても、全体の空間は、連続的にアドレス指定することができる。入って来る仮想アドレスは、１６ビットから成る。マクロタイル番号及び上位５ビットは、第１のテーブル（ディレクトリと呼ぶ）をアドレス指定し、３２個の他のテーブルのうちのどれをアクセスするかを示す上で用いられる。下位１１ビットは、２０４８個の変換値のうちのどれを実際に用いるべきかを示している。従って、連続するアドレスと仮想アドレスとの間で変換を行うための段階は、１）適切なマクロタイルを選択する段階、２）上位５ビットを用いて正しい第２のルックアップテーブルを選択する段階、及び３）１１個の下位ビットを用いて２０４８個のメモリページのうちのどれが実際の仮想アドレスであるかを選択する段階である。
【００９４】
この実施形態では、連続アドレス及び仮想アドレスは、ＤＰＭによってＴＡに供給される。データが書き込まれるアドレスが仮想アドレスであり、制御ストリームに組み込まれるアドレスは連続のものである。ルックアップテーブルは、連続アドレスを仮想アドレスへと変換するのにＩＳＰ及びＴＳＰパラメータフェッチによって用いられる。この第２の変換を効率的にするために、このルックアップテーブルはキャッシュに入れられ、このキャッシュは、性能を維持するのに必要である。
【００９５】
本発明者は、これらの実施形態を適用した後に、ＮＴＥによって用いられるメモリ空間の平均で１５％の低減を達成したことを見出した。２つの解決法の間の差は、第１の解決法（２つの頂点ポインタを用いた）は、２つの新しいキャッシュを追加する必要がないことから実装が小さくなることである。しかし、この解決法は、パラメータフォーマットを変更し、複雑さを増すことを要求する。第２の解決法（ルックアップテーブルを用いた）は、２つのページにわたって書込みを行うことを可能にし、システムの残りの部分に影響を及ぼすことなく実施することができる。また、第２のポインタという負荷の増大も存在しない。
【００９６】
上述の本発明の第３の態様の実施形態では、オブジェクトデータに対するメモリ割り当ての問題に対処した。特定のプリミティブオブジェクトからのデータがページ境界線を超えるのを防ぐために、プリミティブオブジェクト全体に対して現在のページ上に不十分な空間しか存在しなかった場合には、空き記憶領域から新しいページを割り当てる必要がある。ｚバッファメモリに記憶される深度データにおいて類似の問題が発生する可能性があり（図２を参照されたい）、ここで、これに対して更に説明を行うことにする。
【００９７】
図２は、部分レンダリングが採用された場合のプロセッサの例を示している。部分レンダリングは、オブジェクトデータのうちの一部を記憶するだけでよく、更に、部分レンダリングは、表示リストメモリ２０５を解放するように実施することができることから複雑なシーンに対して有効である。得られる深度データは、ｚバッファメモリ２０９に記憶され、後のオブジェクトデータと組み合わされ、最終的に全体画像が生成される。図２に示しているように、圧縮／解凍ユニット２１１を用いることができる。
【００９８】
画像が最終的に正しく生成されることを保証するために、メモリ２０９内の深度データを部分レンダリングが実施されたマクロタイル内のタイル上に記憶する必要がある。深度データを記憶するのに用いられるｚバッファメモリ２０９内の空間は、要求に応じてメモリマネージャ（例えば、ＤＰＭ）によって割り当てられ、特定のタイルに対するメモリアドレスが保存される。次に、更に別のオブジェクトデータが表示リストメモリ内にロードされ、次に、更に別の部分レンダリングが実施される。この段階では、更に別の深度データは、タイルに関連付けられたメモリアドレス内に置かれる。最終画像は、全ての部分レンダリングの後に正しくレンダリングされることになり、ｚバッファメモリのメモリページを解放することができる。
【００９９】
圧縮／解凍ユニット２１１が用いられる場合には、ユニット２１１内にはタイルに関する圧縮深度データを保持するいかなるバッファも存在せず、従って、ユニットは、圧縮しながらデータをメモリ内に書込み、解凍しながらメモリからデータを読み取る。タイル内の圧縮ｚデータがメモリページを超えることを回避するために、タイルの開始時点に、圧縮／解凍ユニットは、現在のメモリページ内に十分な空き空間が存在するか否かを検査する必要がある。圧縮／解凍ユニットは、ｚデータを圧縮し、それをｚバッファメモリ内に書込み始める時には、タイルに関する圧縮ｚデータのサイズを把握していない。従って、圧縮／解凍ユニットが、書込みの開始時点に空き空間を検査する時には、タイル内の深度データの最大サイズを仮定する必要がある。深度データのサイズは、常に最大サイズとは限らないので、メモリページの最後には浪費メモリ空間が存在する。
【０１００】
本発明のこの実施形態は、ページの最後のリンクページアドレスに対して特別に定められたトークンを与えることによってこの問題を解決することを試み、これを図１１に示す。図１１に示しているように、ＤＰＭによって圧縮ｚデータに割り当てられた各メモリページ１１０１において、最後の４バイトワード１１０３が、ページアドレスリンクに向けて保証される。圧縮／解凍ユニットが、書込みがメモリページを超えるのを検出した場合には、このユニットは、ＤＰＭから新しいページを要求することになる。現在のページ内の最後のワードは、図１１にあるリンクページヘッダ０ｘ８０００００００−１１０３と共に新しいページのためのページアドレスリンクで埋められることになる。リンクページヘッダは、ビット３１が１であるか、又は４バイトが右から左に８０，００，００，００である３２ビット１６進値である。この後、圧縮／解凍ユニットは、新しいページに向けてページアドレスリンクによって示された新しいページ内に圧縮深度データを書込み続ける。ページの最後では、いかなるメモリ空間も浪費されない。圧縮深度データを単一ページ内に収容することができる場合には、いかなるページアドレスリンクも必要とされない（最終の４バイトを除き）。この場合、現在のページ内の最後のワードは、００００．．．で埋められることになる。
読取段階中に、圧縮／解凍ユニットは、メモリから読み取られたデータを解凍する。ページ内の最後のワードは、深度データ自体ではなく、常に、新しいページアドレスへのトークンであるページ内の最後のワードのヘッダ（０ｘ８０００００００）を解析することにより、圧縮／解凍ユニットは、最後のワードが新しいページにリンクするためのアドレスであるのか、又は空白ワード（００００．．．）であるのかを判断する。最後のワードからのアドレスは、リンクページヘッダが設定されている場合に、リンクされたページから圧縮データをフェッチし続けるのに用いられる。
【０１０１】
この実施形態の利点は、新しいページの追加アドレスをタイルの領域ヘッダに含める必要がない点である。ページリンクは、圧縮及び解凍処理内で自然に発生する。この実施は、単純で分り易いものである。
本発明者は、この実施形態を適用した後に、圧縮ｚバッファによって用いられるメモリ空間の平均で３５％の低減を達成することができることを見出した。
【符号の説明】
【０１０２】
５０１，５０３，５０５，５０７，５０９ 第１のプリミティブオブジェクトの頂点
５１１，５１３，５１５，５１７，５１９ 第２のプリミティブオブジェクトの頂点
Ｃ１，Ｃ２，Ｃ３ タイル
【特許請求の範囲】
【請求項１】
少なくとも１つの形状を各々が含む複数のオブジェクトを生成される画像が含む３次元コンピュータ画像を生成する方法であって、
ａ）画像を複数の矩形区域に細分割し、かつ各矩形区域を複数のより小さい区域に細分割する段階と、
ｂ）前記画像内のオブジェクトの少なくとも一部に対して、該オブジェクト内の各形状に関する面データ及び頂点データと、該面データと該頂点データの間のポインタとを含むオブジェクトデータをメモリに記憶する段階と、
ｃ）前記画像内の各小区域に対して、
ｉ）段階ｂ）で記憶された前記オブジェクトデータから２つ又はそれよりも多くのオブジェクトに関するオブジェクトデータを抽出する段階、
ｉｉ）前記画像内の前記小区域のうちのどれが、段階ｉ）でオブジェクトデータが抽出された前記オブジェクトのうちの１つ又は全てを含むかを計算する段階、
ｉｉｉ）段階ｉｉ）で計算された前記小区域の各々に対して、該小区域に含まれる前記オブジェクト又はその各々に関するオブジェクトデータにリンクする制御データセットを導出する段階、及び
ｉｖ）ｂ）での全てのオブジェクトに対する制御データが導出されるまで段階ｉ）からｉｉｉ）を繰り返す段階、
により、前記小区域内の各オブジェクトに関する前記オブジェクトデータにリンクする制御データを導出する段階と、
ｄ）前記制御データ及び前記オブジェクトデータから各矩形区域に関する深度データを導出する段階と、
ｅ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出する段階と、
を含むことを特徴とする方法。
【請求項２】
段階ｉｉｉ）で導出された各制御データセットに対する最終メモリ位置において、ポインタが、前記小区域に関する次の制御データセットに対して設けられ、該最終メモリ位置は、キャッシュに記憶されることを特徴とする請求項１に記載の方法。
【請求項３】
段階ｂ）は、オブジェクトデータを前記画像内の全てのオブジェクトに対してメモリに記憶する段階を含むことを特徴とする請求項１又は請求項２に記載の方法。
【請求項４】
段階ｂ）は、オブジェクトデータを前記画像内の所定数のオブジェクトに対してメモリに記憶する段階を含み、
方法が、段階ｅ）の前に、前記画像内の全ての前記オブジェクトに対してオブジェクトデータを記憶するまで段階ｂ）、段階ｃ）、及び段階ｄ）を繰り返す段階を更に含む、
ことを特徴とする請求項１又は請求項２に記載の方法。
【請求項５】
段階ｉ）は、段階ｂ）で記憶された前記オブジェクトデータから２つのオブジェクトに関するオブジェクトデータを抽出する段階を含むことを特徴とする請求項１から請求項４のいずれか１項に記載の方法。
【請求項６】
少なくとも１つの形状を各々が含む複数のオブジェクトを生成される画像が含む３次元コンピュータ画像を生成するための装置であって、
ａ）画像を複数の矩形区域に細分割し、かつ各矩形区域を複数のより小さい区域に細分割するための手段と、
ｂ）前記画像内のオブジェクトの少なくとも一部に対して、該オブジェクト内の各形状に関する面データ及び頂点データと、該面データと該頂点データの間のポインタとを含むオブジェクトデータをメモリに記憶するための手段と、
ｃ）前記画像内の各小区域に対して、
ｉ）前記記憶するための手段によって記憶された前記オブジェクトデータから２つ又はそれよりも多くのオブジェクトに関するオブジェクトデータを抽出し、
ｉｉ）前記画像内の前記小区域のうちのどれが、オブジェクトデータが抽出された前記オブジェクトのうちの１つ又は全てを含むかを計算し、
ｉｉｉ）ｉｉ）で計算された前記小区域の各々に対して、該小区域に含まれる前記オブジェクト又はその各々に関するオブジェクトデータにリンクする制御データセットを導出し、かつ
ｉｖ）ｂ）での全てのオブジェクトに対する制御データが導出されるまでｉ）からｉｉｉ）を繰り返す、
ように構成され、前記小区域内の各オブジェクトに関する前記オブジェクトデータにリンクする制御データを導出するための導出手段と、
ｄ）前記制御データ及び前記オブジェクトデータから各矩形区域に関する深度データを導出するための手段と、
ｅ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出するための手段と、
を含むことを特徴とする装置。
【請求項７】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法であって、
ａ）画像を複数の個別区域に細分割する段階と、
ｂ）前記画像内のオブジェクトの少なくとも一部に対して、オブジェクトデータをメモリに記憶する段階と、
ｃ）一度に２つの個別区域に対して、該２つの個別区域内の前記オブジェクトデータにリンクする制御データを導出する段階と、
ｄ）ｉ）前記制御データ及び前記オブジェクトデータから第１の個別区域に関する深度データを導出し、かつ表示に向けて該深度データから該第１の個別区域に関する画像データ及びシェーディングデータを導出し、かつ
ｉｉ）前記制御データ及び前記オブジェクトデータから第２の個別区域に関する深度データを導出し、かつ表示に向けて該深度データから該第２の個別区域に関する画像データ及びシェーディングデータを導出する、
ことを並行して行うことにより、前記２つの個別区域に３次元コンピュータ画像を生成する段階と、
ｅ）画像が全ての前記個別区域に対して生成されるまで段階ｃ）及び段階ｄ）を繰り返す段階と、
を含むことを特徴とする方法。
【請求項８】
各オブジェクトが、複数の頂点を有する複数の形状を含み、段階ｃ）で導出された前記制御データは、各オブジェクトに対して、該オブジェクトのどの形状が前記個別区域のどれに収まるかに関する指示、及び該オブジェクトのどの頂点が該個別区域のどれに収まるかに関する指示を含むことを特徴とする請求項７に記載の方法。
【請求項９】
前記制御データは、ヘッダ部分及びペイロード部分を含むことを特徴とする請求項８に記載の方法。
【請求項１０】
前記ヘッダ部分は、前記オブジェクトのどの頂点が前記個別区域のどれに収まるかに関する前記指示を含むことを特徴とする請求項９に記載の方法。
【請求項１１】
前記オブジェクトの前記形状の一部が前記個別区域の各々に収まるか、又は該オブジェクトの該形状の全てが該個別区域の１つのみに収まる場合には、前記ペイロードは、該オブジェクトのどの形状が該個別区域のどれに収まるかに関する前記指示を含むことを特徴とする請求項９又は請求項１０に記載の方法。
【請求項１２】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置であって、
ａ）画像を複数の個別区域に細分割するための手段と、
ｂ）前記画像内のオブジェクトの少なくとも一部に対して、オブジェクトデータをメモリに記憶するための手段と、
ｃ）一度に２つの個別区域に対して、該２つの個別区域内の前記オブジェクトデータにリンクする制御データを導出するための導出手段と、
ｄ）前記２つの個別区域に３次元コンピュータ画像を生成するための画像発生器と、
を含み、
前記画像発生器は、第１の画像発生器と、それと並列の第２の画像発生器とを含み、
前記第１の画像発生器は、前記制御データ及び前記オブジェクトデータから第１の個別区域に関する深度データを導出し、かつ表示に向けて該深度データから該第１の個別区域に関する画像データ及びシェーディングデータを導出するように構成され、
前記第２の画像発生器は、前記制御データ及び前記オブジェクトデータから第２の個別区域に関する深度データを導出し、かつ表示に向けて該深度データから該第２の個別区域に関する画像データ及びシェーディングデータを導出するように構成される、
ことを特徴とする装置。
【請求項１３】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法であって、
ａ）画像を複数の個別区域に細分割する段階と、
ｂ）前記画像内のオブジェクトの少なくとも一部に対して、第１のエンジンが、メモリページに分割されているメモリにオブジェクトデータを記憶する段階と、
ｃ）ｂ）でオブジェクトデータが記憶された各オブジェクトに対して、該オブジェクトデータが１つのメモリページ上に記憶された場合に、前記第１のエンジンが、このメモリページアドレスを第２のエンジンに送り、又は該オブジェクトデータが２つのメモリページ上に記憶された場合に、該第１のエンジンが、これらのメモリページアドレスを該第２のエンジンに送る段階と、
ｄ）前記画像内の各個別区域に対して、より小さな前記区域内の各オブジェクトに関する前記オブジェクトデータにリンクし、かつｂ）で記憶された該オブジェクトデータが１つのメモリページ上に記憶された場合に前記１つのメモリページアドレスを含み、ｂ）で記憶された該オブジェクトデータが２つのメモリページ上に記憶された場合に前記２つのメモリページアドレスを含む制御データを前記第２のエンジンが導出する段階と、
ｅ）前記制御データ及び前記オブジェクトデータから各個別区域に関する深度データを導出する段階と、
ｆ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出する段階と、
を含むことを特徴とする方法。
【請求項１４】
メモリマネージャが、前記メモリのページを前記画像内の前記オブジェクトに割り当てる段階を更に含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
前記メモリマネージャは、２ページのメモリを各オブジェクトに自動的に割り当てることを特徴とする請求項１４に記載の方法。
【請求項１６】
深度データを導出する段階ｅ）は、前記個別区域内の各オブジェクトに関するオブジェクトデータにリンクする前記制御データが、１つ又は２つのいずれのメモリページアドレスを含むか否かを判断する段階を含むことを特徴とする請求項１３から請求項１５のいずれか１項に記載の方法。
【請求項１７】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置であって、
ａ）画像を複数の個別区域に細分割するための手段と、
ｂ）前記画像内のオブジェクトの少なくとも一部に対してオブジェクトデータをメモリに記憶するための第１のエンジンと、
ｃ）前記個別区域内の各オブジェクトに関する前記オブジェクトデータにリンクする制御データを導出するための第２のエンジンと、
ｄ）前記制御データ及び前記オブジェクトデータから各個別区域に関する深度データを導出するための手段と、
ｆ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出するための手段と、
を含み、
前記メモリは、メモリページに分割され、
前記第１のエンジンは、オブジェクトデータが記憶された各オブジェクトに対して、ｉ）該オブジェクトデータが１つのメモリページ上に記憶された場合に、このメモリページアドレスを前記第２のエンジンに送り、ｉｉ）該オブジェクトデータが２つのメモリページ上に記憶された場合に、これらのメモリページアドレスを該第２のエンジンに送るように構成され、かつ
前記制御データは、前記第１のエンジンによって記憶された前記オブジェクトデータが１つのメモリページ上に記憶された場合に、前記１つのメモリページアドレスを含み、又は該第１のエンジンによって記憶された該オブジェクトデータが２つのメモリページ上に記憶された場合に、前記２つのメモリページアドレスを含む、
ことを特徴とする装置。
【請求項１８】
前記メモリのページを前記画像内の前記オブジェクトに割り当てるためのメモリマネージャを更に含むことを特徴とする請求項１７に記載の装置。
【請求項１９】
前記メモリマネージャは、２ページのメモリを各オブジェクトに自動的に割り当てるように構成されることを特徴とする請求項１７に記載の装置。
【請求項２０】
深度データを導出するための手段は、前記個別区域内の各オブジェクトに関するオブジェクトデータにリンクする前記制御データが、１つ又は２つのいずれのメモリページアドレスを含むか否かを判断するように構成されることを特徴とする請求項１７から請求項１９のいずれか１項に記載の装置。
【請求項２１】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法であって、
ａ）画像を複数の個別区域に細分割する段階と、
ｂ）メモリページに分割され、かつルックアップテーブルを含むメモリを準備する段階と、
ｃ）メモリマネージャが、前記ルックアップテーブル内の２つ又はそれよりも多くの連続部分を各個別区域に割り当て、該ルックアップテーブル内の各割り当てられた部分が、その個別区域に関するオブジェクトデータを記憶するのに利用可能なメモリページを指し示す段階と、
ｄ）前記画像内のオブジェクトの少なくとも一部に対して、第１のエンジンが、各個別区域に関して、オブジェクトデータを段階ｃ）でその個別区域に割り当てられた前記メモリページに記憶する段階と、
ｅ）各個別区域に対して、前記第１のエンジンが、前記ルックアップテーブル内の前記２つ又はそれよりも多くの割り当て部分のメモリアドレスを第２のエンジンに送る段階と、
ｆ）前記画像内の各個別区域に対して、前記第２のエンジンが、前記第１のエンジンから送られた前記メモリアドレスを用いて、より小さな前記区域内の各オブジェクトに関する前記オブジェクトデータにリンクする制御データを導出する段階と、
ｇ）前記画像内の各個別区域に対して、前記第１のエンジンから送られた前記メモリアドレスを用いて、前記制御データ及び前記オブジェクトデータから深度データを導出する段階と、
ｈ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出する段階と、
を含むことを特徴とする方法。
【請求項２２】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置であって、
ａ）画像を複数の個別区域に細分割するための手段と、
ｂ）メモリページに分割され、かつルックアップテーブルを含むメモリと、
ｃ）前記ルックアップテーブル内の２つ又はそれよりも多くの連続部分を各個別区域に割り当て、該ルックアップテーブル内の各割り当てられた部分が、その個別区域に関するオブジェクトデータを記憶するのに利用可能なメモリページを指し示すメモリマネージャと、
ｄ）前記画像内のオブジェクトの少なくとも一部に対して、かつ各個別区域に関して、オブジェクトデータを前記メモリマネージャによってその個別区域に割り当てされた前記メモリページに記憶するように構成された第１のエンジンと、
ｅ）前記ルックアップテーブル内の前記２つ又はそれよりも多くの割り当てられた部分の各個別区域に対するメモリアドレスを前記第１のエンジンから受け取るように構成され、かつ該メモリアドレスを用いて、その個別区域内の各オブジェクトに関する前記オブジェクトデータにリンクする制御データを導出するように構成された第２のエンジンと、
ｇ）前記メモリアドレスを用いて、前記画像内の各個別区域に関して前記制御データ及び前記オブジェクトデータから深度データを導出するための手段と、
ｈ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出するための手段と、
を含むことを特徴とする装置。
【請求項２３】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法であって、
ａ）画像を複数の個別区域に細分割する段階と、
ｂ）前記画像内のオブジェクトの少なくとも一部に対して、オブジェクトデータを第１のメモリに記憶する段階と、
ｃ）前記オブジェクトデータから各個別区域に関する深度データを導出する段階と、
ｄ）リンク部分として割り当てられた部分を各ページが含む複数のメモリページを含む、前記深度データを記憶するための第２のメモリを準備する段階と、
ｅ）各個別区域に関する前記深度データを前記第２のメモリに記憶し、個別区域に関する該深度データが１つのメモリページ上に記憶された場合に、そうであることをこのメモリページの前記リンク部分に示し、又は個別区域に関する該深度データが１つよりも多いメモリページ上に記憶された場合に、この個別区域に対する各メモリページの該リンク部分を用いて、この個別区域に対する次のメモリページを指し示す段階と、
ｆ）更に別のオブジェクトデータを前記第１のメモリ内にロードして、既存の内容の少なくとも一部を置換する段階と、
ｇ）各個別区域に関して前記記憶された深度データをこの個別区域に対する前記又は各メモリページの前記リンク部分を読み取ることによって取り出す段階と、
ｈ）前記新しいオブジェクトデータ及び前記記憶された深度データからの更新された深度データを導出し、該更新された深度データを記憶して以前に記憶された深度データを置換する段階と、
ｉ）前記メモリ内にロードされる更に別のオブジェクトデータがなくなるまで段階ｅ）、ｆ）、ｇ）、及びｈ）を繰り返す段階と、
ｊ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出する段階と、
を含むことを特徴とする方法。
【請求項２４】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置であって、
ａ）画像を複数の個別区域に細分割するための手段と、
ｂ）前記画像内のオブジェクトの少なくとも一部に関するオブジェクトデータを記憶するための第１のメモリと、
ｃ）前記オブジェクトデータから各個別区域に関する深度データを導出するための手段と、
ｄ）リンク部分として割り当てられた部分を各ページが含む複数のメモリページを含む、前記深度データを記憶するための第２のメモリと、
ｅ）各個別区域に関する前記深度データを前記第２のメモリに記憶し、個別区域に関する該深度データが１つのメモリページ上に記憶された場合に、そうであることをこのメモリページの前記リンク部分に示し、又は個別区域に関する該深度データが１つよりも多いメモリページ上に記憶された場合に、この個別区域に対する各メモリページの該リンク部分を用いて、この個別区域に対する次のメモリページを指し示すための手段と、
ｆ）更に別のオブジェクトデータを前記第１のメモリ内にロードして、既存の内容の少なくとも一部を置換するための手段と、
ｇ）各個別区域に関して前記記憶された深度データをこの個別区域に対する前記又は各メモリページの前記リンク部分を読み取ることによって取り出すための手段と、
ｈ）前記新しいオブジェクトデータ及び前記記憶された深度データからの更新された深度データを導出し、該更新された深度データを記憶して以前に記憶された深度データを置換するための手段と、
ｉ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出するための手段と、
を含むことを特徴とする装置。
【請求項１】
少なくとも１つの形状を各々が含む複数のオブジェクトを生成される画像が含む３次元コンピュータ画像を生成する方法であって、
ａ）画像を複数の矩形区域に細分割し、かつ各矩形区域を複数のより小さい区域に細分割する段階と、
ｂ）前記画像内のオブジェクトの少なくとも一部に対して、該オブジェクト内の各形状に関する面データ及び頂点データと、該面データと該頂点データの間のポインタとを含むオブジェクトデータをメモリに記憶する段階と、
ｃ）前記画像内の各小区域に対して、
ｉ）段階ｂ）で記憶された前記オブジェクトデータから２つ又はそれよりも多くのオブジェクトに関するオブジェクトデータを抽出する段階、
ｉｉ）前記画像内の前記小区域のうちのどれが、段階ｉ）でオブジェクトデータが抽出された前記オブジェクトのうちの１つ又は全てを含むかを計算する段階、
ｉｉｉ）段階ｉｉ）で計算された前記小区域の各々に対して、該小区域に含まれる前記オブジェクト又はその各々に関するオブジェクトデータにリンクする制御データセットを導出する段階、及び
ｉｖ）ｂ）での全てのオブジェクトに対する制御データが導出されるまで段階ｉ）からｉｉｉ）を繰り返す段階、
により、前記小区域内の各オブジェクトに関する前記オブジェクトデータにリンクする制御データを導出する段階と、
ｄ）前記制御データ及び前記オブジェクトデータから各矩形区域に関する深度データを導出する段階と、
ｅ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出する段階と、
を含むことを特徴とする方法。
【請求項２】
段階ｉｉｉ）で導出された各制御データセットに対する最終メモリ位置において、ポインタが、前記小区域に関する次の制御データセットに対して設けられ、該最終メモリ位置は、キャッシュに記憶されることを特徴とする請求項１に記載の方法。
【請求項３】
段階ｂ）は、オブジェクトデータを前記画像内の全てのオブジェクトに対してメモリに記憶する段階を含むことを特徴とする請求項１又は請求項２に記載の方法。
【請求項４】
段階ｂ）は、オブジェクトデータを前記画像内の所定数のオブジェクトに対してメモリに記憶する段階を含み、
方法が、段階ｅ）の前に、前記画像内の全ての前記オブジェクトに対してオブジェクトデータを記憶するまで段階ｂ）、段階ｃ）、及び段階ｄ）を繰り返す段階を更に含む、
ことを特徴とする請求項１又は請求項２に記載の方法。
【請求項５】
段階ｉ）は、段階ｂ）で記憶された前記オブジェクトデータから２つのオブジェクトに関するオブジェクトデータを抽出する段階を含むことを特徴とする請求項１から請求項４のいずれか１項に記載の方法。
【請求項６】
少なくとも１つの形状を各々が含む複数のオブジェクトを生成される画像が含む３次元コンピュータ画像を生成するための装置であって、
ａ）画像を複数の矩形区域に細分割し、かつ各矩形区域を複数のより小さい区域に細分割するための手段と、
ｂ）前記画像内のオブジェクトの少なくとも一部に対して、該オブジェクト内の各形状に関する面データ及び頂点データと、該面データと該頂点データの間のポインタとを含むオブジェクトデータをメモリに記憶するための手段と、
ｃ）前記画像内の各小区域に対して、
ｉ）前記記憶するための手段によって記憶された前記オブジェクトデータから２つ又はそれよりも多くのオブジェクトに関するオブジェクトデータを抽出し、
ｉｉ）前記画像内の前記小区域のうちのどれが、オブジェクトデータが抽出された前記オブジェクトのうちの１つ又は全てを含むかを計算し、
ｉｉｉ）ｉｉ）で計算された前記小区域の各々に対して、該小区域に含まれる前記オブジェクト又はその各々に関するオブジェクトデータにリンクする制御データセットを導出し、かつ
ｉｖ）ｂ）での全てのオブジェクトに対する制御データが導出されるまでｉ）からｉｉｉ）を繰り返す、
ように構成され、前記小区域内の各オブジェクトに関する前記オブジェクトデータにリンクする制御データを導出するための導出手段と、
ｄ）前記制御データ及び前記オブジェクトデータから各矩形区域に関する深度データを導出するための手段と、
ｅ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出するための手段と、
を含むことを特徴とする装置。
【請求項７】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法であって、
ａ）画像を複数の個別区域に細分割する段階と、
ｂ）前記画像内のオブジェクトの少なくとも一部に対して、オブジェクトデータをメモリに記憶する段階と、
ｃ）一度に２つの個別区域に対して、該２つの個別区域内の前記オブジェクトデータにリンクする制御データを導出する段階と、
ｄ）ｉ）前記制御データ及び前記オブジェクトデータから第１の個別区域に関する深度データを導出し、かつ表示に向けて該深度データから該第１の個別区域に関する画像データ及びシェーディングデータを導出し、かつ
ｉｉ）前記制御データ及び前記オブジェクトデータから第２の個別区域に関する深度データを導出し、かつ表示に向けて該深度データから該第２の個別区域に関する画像データ及びシェーディングデータを導出する、
ことを並行して行うことにより、前記２つの個別区域に３次元コンピュータ画像を生成する段階と、
ｅ）画像が全ての前記個別区域に対して生成されるまで段階ｃ）及び段階ｄ）を繰り返す段階と、
を含むことを特徴とする方法。
【請求項８】
各オブジェクトが、複数の頂点を有する複数の形状を含み、段階ｃ）で導出された前記制御データは、各オブジェクトに対して、該オブジェクトのどの形状が前記個別区域のどれに収まるかに関する指示、及び該オブジェクトのどの頂点が該個別区域のどれに収まるかに関する指示を含むことを特徴とする請求項７に記載の方法。
【請求項９】
前記制御データは、ヘッダ部分及びペイロード部分を含むことを特徴とする請求項８に記載の方法。
【請求項１０】
前記ヘッダ部分は、前記オブジェクトのどの頂点が前記個別区域のどれに収まるかに関する前記指示を含むことを特徴とする請求項９に記載の方法。
【請求項１１】
前記オブジェクトの前記形状の一部が前記個別区域の各々に収まるか、又は該オブジェクトの該形状の全てが該個別区域の１つのみに収まる場合には、前記ペイロードは、該オブジェクトのどの形状が該個別区域のどれに収まるかに関する前記指示を含むことを特徴とする請求項９又は請求項１０に記載の方法。
【請求項１２】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置であって、
ａ）画像を複数の個別区域に細分割するための手段と、
ｂ）前記画像内のオブジェクトの少なくとも一部に対して、オブジェクトデータをメモリに記憶するための手段と、
ｃ）一度に２つの個別区域に対して、該２つの個別区域内の前記オブジェクトデータにリンクする制御データを導出するための導出手段と、
ｄ）前記２つの個別区域に３次元コンピュータ画像を生成するための画像発生器と、
を含み、
前記画像発生器は、第１の画像発生器と、それと並列の第２の画像発生器とを含み、
前記第１の画像発生器は、前記制御データ及び前記オブジェクトデータから第１の個別区域に関する深度データを導出し、かつ表示に向けて該深度データから該第１の個別区域に関する画像データ及びシェーディングデータを導出するように構成され、
前記第２の画像発生器は、前記制御データ及び前記オブジェクトデータから第２の個別区域に関する深度データを導出し、かつ表示に向けて該深度データから該第２の個別区域に関する画像データ及びシェーディングデータを導出するように構成される、
ことを特徴とする装置。
【請求項１３】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法であって、
ａ）画像を複数の個別区域に細分割する段階と、
ｂ）前記画像内のオブジェクトの少なくとも一部に対して、第１のエンジンが、メモリページに分割されているメモリにオブジェクトデータを記憶する段階と、
ｃ）ｂ）でオブジェクトデータが記憶された各オブジェクトに対して、該オブジェクトデータが１つのメモリページ上に記憶された場合に、前記第１のエンジンが、このメモリページアドレスを第２のエンジンに送り、又は該オブジェクトデータが２つのメモリページ上に記憶された場合に、該第１のエンジンが、これらのメモリページアドレスを該第２のエンジンに送る段階と、
ｄ）前記画像内の各個別区域に対して、より小さな前記区域内の各オブジェクトに関する前記オブジェクトデータにリンクし、かつｂ）で記憶された該オブジェクトデータが１つのメモリページ上に記憶された場合に前記１つのメモリページアドレスを含み、ｂ）で記憶された該オブジェクトデータが２つのメモリページ上に記憶された場合に前記２つのメモリページアドレスを含む制御データを前記第２のエンジンが導出する段階と、
ｅ）前記制御データ及び前記オブジェクトデータから各個別区域に関する深度データを導出する段階と、
ｆ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出する段階と、
を含むことを特徴とする方法。
【請求項１４】
メモリマネージャが、前記メモリのページを前記画像内の前記オブジェクトに割り当てる段階を更に含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
前記メモリマネージャは、２ページのメモリを各オブジェクトに自動的に割り当てることを特徴とする請求項１４に記載の方法。
【請求項１６】
深度データを導出する段階ｅ）は、前記個別区域内の各オブジェクトに関するオブジェクトデータにリンクする前記制御データが、１つ又は２つのいずれのメモリページアドレスを含むか否かを判断する段階を含むことを特徴とする請求項１３から請求項１５のいずれか１項に記載の方法。
【請求項１７】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置であって、
ａ）画像を複数の個別区域に細分割するための手段と、
ｂ）前記画像内のオブジェクトの少なくとも一部に対してオブジェクトデータをメモリに記憶するための第１のエンジンと、
ｃ）前記個別区域内の各オブジェクトに関する前記オブジェクトデータにリンクする制御データを導出するための第２のエンジンと、
ｄ）前記制御データ及び前記オブジェクトデータから各個別区域に関する深度データを導出するための手段と、
ｆ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出するための手段と、
を含み、
前記メモリは、メモリページに分割され、
前記第１のエンジンは、オブジェクトデータが記憶された各オブジェクトに対して、ｉ）該オブジェクトデータが１つのメモリページ上に記憶された場合に、このメモリページアドレスを前記第２のエンジンに送り、ｉｉ）該オブジェクトデータが２つのメモリページ上に記憶された場合に、これらのメモリページアドレスを該第２のエンジンに送るように構成され、かつ
前記制御データは、前記第１のエンジンによって記憶された前記オブジェクトデータが１つのメモリページ上に記憶された場合に、前記１つのメモリページアドレスを含み、又は該第１のエンジンによって記憶された該オブジェクトデータが２つのメモリページ上に記憶された場合に、前記２つのメモリページアドレスを含む、
ことを特徴とする装置。
【請求項１８】
前記メモリのページを前記画像内の前記オブジェクトに割り当てるためのメモリマネージャを更に含むことを特徴とする請求項１７に記載の装置。
【請求項１９】
前記メモリマネージャは、２ページのメモリを各オブジェクトに自動的に割り当てるように構成されることを特徴とする請求項１７に記載の装置。
【請求項２０】
深度データを導出するための手段は、前記個別区域内の各オブジェクトに関するオブジェクトデータにリンクする前記制御データが、１つ又は２つのいずれのメモリページアドレスを含むか否かを判断するように構成されることを特徴とする請求項１７から請求項１９のいずれか１項に記載の装置。
【請求項２１】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法であって、
ａ）画像を複数の個別区域に細分割する段階と、
ｂ）メモリページに分割され、かつルックアップテーブルを含むメモリを準備する段階と、
ｃ）メモリマネージャが、前記ルックアップテーブル内の２つ又はそれよりも多くの連続部分を各個別区域に割り当て、該ルックアップテーブル内の各割り当てられた部分が、その個別区域に関するオブジェクトデータを記憶するのに利用可能なメモリページを指し示す段階と、
ｄ）前記画像内のオブジェクトの少なくとも一部に対して、第１のエンジンが、各個別区域に関して、オブジェクトデータを段階ｃ）でその個別区域に割り当てられた前記メモリページに記憶する段階と、
ｅ）各個別区域に対して、前記第１のエンジンが、前記ルックアップテーブル内の前記２つ又はそれよりも多くの割り当て部分のメモリアドレスを第２のエンジンに送る段階と、
ｆ）前記画像内の各個別区域に対して、前記第２のエンジンが、前記第１のエンジンから送られた前記メモリアドレスを用いて、より小さな前記区域内の各オブジェクトに関する前記オブジェクトデータにリンクする制御データを導出する段階と、
ｇ）前記画像内の各個別区域に対して、前記第１のエンジンから送られた前記メモリアドレスを用いて、前記制御データ及び前記オブジェクトデータから深度データを導出する段階と、
ｈ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出する段階と、
を含むことを特徴とする方法。
【請求項２２】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置であって、
ａ）画像を複数の個別区域に細分割するための手段と、
ｂ）メモリページに分割され、かつルックアップテーブルを含むメモリと、
ｃ）前記ルックアップテーブル内の２つ又はそれよりも多くの連続部分を各個別区域に割り当て、該ルックアップテーブル内の各割り当てられた部分が、その個別区域に関するオブジェクトデータを記憶するのに利用可能なメモリページを指し示すメモリマネージャと、
ｄ）前記画像内のオブジェクトの少なくとも一部に対して、かつ各個別区域に関して、オブジェクトデータを前記メモリマネージャによってその個別区域に割り当てされた前記メモリページに記憶するように構成された第１のエンジンと、
ｅ）前記ルックアップテーブル内の前記２つ又はそれよりも多くの割り当てられた部分の各個別区域に対するメモリアドレスを前記第１のエンジンから受け取るように構成され、かつ該メモリアドレスを用いて、その個別区域内の各オブジェクトに関する前記オブジェクトデータにリンクする制御データを導出するように構成された第２のエンジンと、
ｇ）前記メモリアドレスを用いて、前記画像内の各個別区域に関して前記制御データ及び前記オブジェクトデータから深度データを導出するための手段と、
ｈ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出するための手段と、
を含むことを特徴とする装置。
【請求項２３】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成する方法であって、
ａ）画像を複数の個別区域に細分割する段階と、
ｂ）前記画像内のオブジェクトの少なくとも一部に対して、オブジェクトデータを第１のメモリに記憶する段階と、
ｃ）前記オブジェクトデータから各個別区域に関する深度データを導出する段階と、
ｄ）リンク部分として割り当てられた部分を各ページが含む複数のメモリページを含む、前記深度データを記憶するための第２のメモリを準備する段階と、
ｅ）各個別区域に関する前記深度データを前記第２のメモリに記憶し、個別区域に関する該深度データが１つのメモリページ上に記憶された場合に、そうであることをこのメモリページの前記リンク部分に示し、又は個別区域に関する該深度データが１つよりも多いメモリページ上に記憶された場合に、この個別区域に対する各メモリページの該リンク部分を用いて、この個別区域に対する次のメモリページを指し示す段階と、
ｆ）更に別のオブジェクトデータを前記第１のメモリ内にロードして、既存の内容の少なくとも一部を置換する段階と、
ｇ）各個別区域に関して前記記憶された深度データをこの個別区域に対する前記又は各メモリページの前記リンク部分を読み取ることによって取り出す段階と、
ｈ）前記新しいオブジェクトデータ及び前記記憶された深度データからの更新された深度データを導出し、該更新された深度データを記憶して以前に記憶された深度データを置換する段階と、
ｉ）前記メモリ内にロードされる更に別のオブジェクトデータがなくなるまで段階ｅ）、ｆ）、ｇ）、及びｈ）を繰り返す段階と、
ｊ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出する段階と、
を含むことを特徴とする方法。
【請求項２４】
生成される画像が複数のオブジェクトを含む３次元コンピュータ画像を生成するための装置であって、
ａ）画像を複数の個別区域に細分割するための手段と、
ｂ）前記画像内のオブジェクトの少なくとも一部に関するオブジェクトデータを記憶するための第１のメモリと、
ｃ）前記オブジェクトデータから各個別区域に関する深度データを導出するための手段と、
ｄ）リンク部分として割り当てられた部分を各ページが含む複数のメモリページを含む、前記深度データを記憶するための第２のメモリと、
ｅ）各個別区域に関する前記深度データを前記第２のメモリに記憶し、個別区域に関する該深度データが１つのメモリページ上に記憶された場合に、そうであることをこのメモリページの前記リンク部分に示し、又は個別区域に関する該深度データが１つよりも多いメモリページ上に記憶された場合に、この個別区域に対する各メモリページの該リンク部分を用いて、この個別区域に対する次のメモリページを指し示すための手段と、
ｆ）更に別のオブジェクトデータを前記第１のメモリ内にロードして、既存の内容の少なくとも一部を置換するための手段と、
ｇ）各個別区域に関して前記記憶された深度データをこの個別区域に対する前記又は各メモリページの前記リンク部分を読み取ることによって取り出すための手段と、
ｈ）前記新しいオブジェクトデータ及び前記記憶された深度データからの更新された深度データを導出し、該更新された深度データを記憶して以前に記憶された深度データを置換するための手段と、
ｉ）表示に向けて前記深度データから画像データ及びシェーディングデータを導出するための手段と、
を含むことを特徴とする装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図８ａ】
【図８ｂ】
【図８ｃ】
【図８ｄ】
【図８ｅ】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図８ａ】
【図８ｂ】
【図８ｃ】
【図８ｄ】
【図８ｅ】
【図９】
【図１０】
【図１１】
【公表番号】特表２０１０−５３９５７９（Ｐ２０１０−５３９５７９Ａ）
【公表日】平成２２年１２月１６日（２０１０．１２．１６）
【国際特許分類】
【出願番号】特願２０１０−５２４５６０（Ｐ２０１０−５２４５６０）
【出願日】平成２０年９月１日（２００８．９．１）
【国際出願番号】ＰＣＴ／ＧＢ２００８／００２９３７
【国際公開番号】ＷＯ２００９／０３４２９４
【国際公開日】平成２１年３月１９日（２００９．３．１９）
【出願人】（５０１１７６０３７）イマジネイション テクノロジーズ リミテッド (59)
【Ｆターム（参考）】
【公表日】平成２２年１２月１６日（２０１０．１２．１６）
【国際特許分類】
【出願日】平成２０年９月１日（２００８．９．１）
【国際出願番号】ＰＣＴ／ＧＢ２００８／００２９３７
【国際公開番号】ＷＯ２００９／０３４２９４
【国際公開日】平成２１年３月１９日（２００９．３．１９）
【出願人】（５０１１７６０３７）イマジネイション テクノロジーズ リミテッド (59)
【Ｆターム（参考）】
[ Back to top ]