(57)【要約】  スクリーン上に表示するための出力画像に頂点データをタイルごとに変換するグラフィックシステム。頂点データは、ポリゴンの組によりオブジェクトを表し、画像中の各頂点（ｑ１，ｑ２，．．．，ｑ１２）における３Ｄ空間座標を含む。ポリゴンは、少なくとも三つの頂点（ｑ１，ｑ２，．．．，ｑ１２）から構成される。システムは、画像を複数のタイル（ｔ２１，ｔ２２，ｔ２３）に分割するとともに、ポリゴンのシーケンスを含むポリゴンストリップ（ｑ１−ｑ１２）を決定するためのタイルプロセッサを備えている。また、タイルプロセッサは、各ポリゴンストリップ（ｑ１−ｑ１２）ごとにサブストリップ（ｑ３−ｑ１０）を決定するように機能する。各サブストリップ（ｑ３−ｑ１０）は、ポリゴンストリップ（ｑ１−ｑ１２）のうちのいくつかのポリゴンであってタイル（ｔ２１，ｔ２２，ｔ２３）のうちの一つのタイルに少なくとも部分的に重なるポリゴンを含む。タイル（ｔ２１，ｔ２２，ｔ２３）を処理するには、サブストリップ（ｑ３−ｑ１０）だけ、即ち、そのタイル（ｔ２１，ｔ２２，ｔ２３）を覆っているポリゴンだけを処理すれば足りる。
2008500625.tif 000002
【特許請求の範囲】
【請求項１】
スクリーン上に表示するための出力画像に頂点データをタイルごとに変換するグラフィックシステムであって、前記頂点データはポリゴンの組によりオブジェクトを表し、一つのポリゴンは少なくとも三つの頂点から構成されるグラフィックシステムにおいて、
前記頂点データを受け取るための入力部であって、前記頂点データは画像中の各頂点における３Ｄ空間座標を少なくとも含む、入力部と、
タイルプロセッサであって、
画像を複数のタイルに分割し、
ポリゴンストリップを決定し、各ポリゴンストリップは少なくとも一つのポリゴンのシーケンスを含み、ポリゴンストリップのそれぞれの後続するポリゴンはその先行するポリゴンと一つの辺を共有し、
各ポリゴンストリップごとにサブストリップを決定し、各サブストリップは、ポリゴンストリップのうちのいくつかのポリゴンであって前記タイルのうちの一つのタイルに少なくとも部分的に重なるポリゴンを含み、そのタイルを重なり合うサブストリップに関連付ける、
ためのタイルプロセッサと、
各タイルに関する表示リストを含むポリゴンタイルデータベースであって、前記表示リストは、前記タイルに関連付けられた前記サブストリップのそれぞれの各識別表示を含む、ポリゴンタイルデータベースと、
前記スクリーン上に表示するために画像のレンダリングを可能にする出力部と、
を備えていることを特徴とするグラフィックシステム。
【請求項２】
前記タイルに関連付けられた前記サブストリップのそれぞれの前記識別表示は、前記サブストリップの最初の頂点への参照を含むことを特徴とする請求項１に記載のグラフィックシステム。
【請求項３】
前記タイルに関連付けられた前記サブストリップのそれぞれの前記識別表示は、前記サブストリップの最後の頂点への参照を含むことを特徴とする請求項２に記載のグラフィックシステム。
【請求項４】
前記タイルに関連付けられた前記サブストリップのそれぞれの前記識別表示は、前記サブストリップ内の多くの頂点を含むことを特徴とする請求項２に記載のグラフィックシステム。
【請求項５】
タイルに関連付けられた前記サブストリップの前記頂点データをキャッシュするための頂点キャッシュを更に備えていることを特徴とする請求項１に記載のグラフィックシステム。
【請求項６】
前記頂点キャッシュは、その後のタイルのために使用されるべき頂点データを保存するように構成されていることを特徴とする請求項５に記載のグラフィックシステム。
【請求項７】
前記頂点キャッシュは、その後のタイルのために使用されるべき頂点データを先取りするように構成されていることを特徴とする請求項５に記載のグラフィックシステム。
【請求項８】
スクリーン上に表示するための出力画像に頂点データをタイルごとに変換する方法であって、前記頂点データはポリゴンの組によりオブジェクトを表し、一つのポリゴンは少なくとも三つの頂点から構成される方法において、
前記頂点データを受け取るステップであって、前記頂点データは画像中の各頂点における３Ｄ空間座標を少なくとも含む、ステップと、
画像を複数のタイルに分割するステップと、
ポリゴンストリップを決定するステップであって、各ポリゴンストリップは少なくとも一つのポリゴンのシーケンスを含み、前記ポリゴンストリップのそれぞれの後続するポリゴンはその先行するポリゴンと一つの辺を共有する、ステップと、
各ポリゴンストリップごとにサブストリップを決定するステップであって、各サブストリップは、前記ポリゴンストリップのうちのいくつかのポリゴンであって前記タイルのうちの一つのタイルに少なくとも部分的に重なるポリゴンを含み、そのタイルを重なり合うサブストリップに関連付ける、ステップと、
各タイルに関する表示リストを含むポリゴンタイルデータベースであって、各表示リストは、前記タイルに関連付けられた前記サブストリップのそれぞれの各識別表示を含む、ポリゴンタイルデータベースを充填するステップと、
前記スクリーン上に表示するために画像のレンダリングを可能にするステップと、
を含むことを特徴とする方法。
【請求項９】
請求項８に記載の方法をプロセッサに実行させるためのコンピュータプログラムプロダクト。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スクリーン上に表示するための出力画像に頂点データをタイルごとに変換するグラフィックシステムであって、頂点データがポリゴンの組（セット）によりオブジェクトを表し、一つのポリゴンが少なくとも三つの頂点から構成されるグラフィックシステムに関する。
【背景技術】
【０００２】
欧州特許第ＥＰ１１２７３３７号（特許文献１）は、フラットなポリゴンの組（セット）により画像中の各オブジェクトを表す、３次元コンピュータ生成画像をシェーディングするための装置について記載している。頂点座標（ｘ，ｙ，ｚ）は、三角形の各頂点ごとに与えられる。三角形は、三角形ストリップ（triangle strip）の一部として送られてもよく、そのように送られない場合には、頂点を相互に比較することにより、三角形をストリップに変換することができる。ストリップは、メモリの領域をあまり占有しない。これは、わずか（ｎ＋２）個の頂点を用いて、３ｎ個の三角形の代わりにｎ個の三角形を記憶するからである。また、ストリップ中の総てのオブジェクトを指し示すためには、一つのポインタだけが必要とされる。
【０００３】
欧州特許第ＥＰ１１２７３３７号（特許文献１）に記載された方法においては、一つのタイルにおけるグラフィックデータをレンダリングするために、そのタイルに重なる一つのストリップの総ての三角形が処理される。例えば、５０個のタイルに重なる一つの三角形ストリップの一部である一つの三角形は、それが一つのタイルだけに重なっている場合であっても、５０回処理される。
【特許文献１】欧州特許第ＥＰ１１２７３３７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の目的は、効率を向上させてスクリーン上に画像を表示するための最初の段落に記載されたグラフィックシステムを提供することである。本発明は、独立請求項によって規定される。従属請求項は、有利な実施の形態を規定する。
【課題を解決するための手段】
【０００５】
この目的は、前記頂点データを受け取るための入力部であって、前記頂点データは画像中の各頂点における３Ｄ空間座標を少なくとも含む、入力部と、タイルプロセッサであって、画像を複数のタイルに分割し、ポリゴンストリップを決定し、各ポリゴンストリップは少なくとも一つのポリゴンのシーケンスを含み、ポリゴンストリップのそれぞれの後続するポリゴンはその先行するポリゴンと一つの辺を共有し、各ポリゴンストリップごとにサブストリップを決定し、各サブストリップは、ポリゴンストリップのうちのいくつかのポリゴンであって前記タイルのうちの一つのタイルに少なくとも部分的に重なるポリゴンを含み、そのタイルを重なり合うサブストリップに関連付ける、ように機能するタイルプロセッサと、各タイルに関する表示リストを含むポリゴンタイルデータベースであって、前記タイルに関連付けられた前記サブストリップのそれぞれの各識別表示を含む、ポリゴンタイルデータベースと、前記スクリーン上に表示するために画像のレンダリングを可能にする出力部と、を備えているシステムにおいて実現される。
【０００６】
本発明に係るグラフィックシステムは、ポリゴンストリップが影響を及ぼしているタイルの数とは関係なく、どのタイルがポリゴンによって覆われているのかを決定するために１ポリゴン当たり一つのテストしか必要としない。このテストは、頂点データが入力部において受け取られた後、タイルプロセッサによって行われる。同じタイルに重なるポリゴンストリップのポリゴンは共に、そのタイルに関連付けられた一つのサブストリップを形成する。それぞれのタイルにおいて、重なり合うサブストリップのリストは、ポリゴン−タイル・データベースにおいて管理される。各タイルの更なる処理においては、そのタイルに重なるポリゴンだけが使用され、更なるテストは必要とされない。これに対し、サブストリップの代わりに各タイルごとにポリゴンストリップ全体が処理される場合、一つのポリゴンが一つのタイルに重なるかどうかを決定するためのテストは、タイルごとに必要であり、また、特定のタイルに重なるポリゴンストリップの一部である総てのポリゴンに関して必要となる。例えば、５０個のタイルに影響を及ぼす１００個のポリンゴンからなる一つのストリップに関し、既知の装置は５０００個のテストを必要とするが、本発明に係るシステムにおいては、わずか１００個のテストで済む。
【０００７】
３Ｄ空間座標は、座標をスクリーン空間に対してマッピングできるように、モデル空間座標、ワールド空間座標、アイ（eye）空間座標若しくはスクリーン空間座標であってよく、又は、他の空間からの座標であってもよい。
【０００８】
本発明の更なる態様において、タイルに関連するそれぞれのサブストリップにおける識別表示は、サブストリップの最初の頂点への参照、サブストリップの最後の頂点への参照、及び／又は、サブストリップ内の多くの頂点への参照を含んでいる。
【０００９】
サブストリップへのそのような参照が使用されると、サブストリップを別個のポリゴンサブストリップとして記憶する必要がなくなる。代わりに、ポリゴンストリップが全体として記憶されてもよい。その結果、メモリサイズ要件及び必要なメモリ帯域幅が低減される。
【００１０】
本発明のこれらの態様及び他の態様は、後述する実施の形態から明らかであり、当該実施の形態を参照しながら上記態様について説明する。
【発明を実施するための最良の形態】
【００１１】
図１は、本発明に係るグラフィックシステムの概略図を示している。システムは、頂点データ及びテクスチャデータを含むグラフィックデータを受け取るための入力部１０１を備えている。テクスチャデータは、テクスチャマップを含んでおり、テクスチャメモリ１０６内に記憶される。頂点データは、表示されるグラフィックシーンにおける総ての頂点の情報と、ポリゴンの構成を可能にするための接続性情報とを含んでいる。この情報は、例えば、スクリーン空間内の頂点位置を規定する（ｘ，ｙ，ｚ）スクリーン空間座標と、テクスチャ空間内の頂点位置を規定する（ｕ，ｖ）テクスチャ座標と、頂点カラー（赤、緑、青に関してＲ，Ｇ，Ｂ）及び透明度を規定するＲＧＢＡ値とを含んでいてもよい。入力部１０１におけるグラフィックデータは、コンピュータゲーム等のグラフィックプログラム１１２又はビデオクリップ再生プログラムによって供給され得る。グラフィックプログラムは、スクリーン空間座標、又は、他の３Ｄ空間座標、例えばモデル空間座標、ワールド空間座標若しくはアイ（eye）空間座標等を供給してもよい。グラフィックプログラムがスクリーン空間座標を供給しない場合には、他の３Ｄ空間座標をスクリーン空間に対してマッピングし且つスクリーン空間座標を入力部に供給するために、頂点変換・ライティングユニット（図示せず）が使用されてもよい。
【００１２】
頂点データは、タイルプロセッサ１０２に送られる。タイルプロセッサ１０２は、ポリゴンストリップとしてデータを受け取り、又は、頂点データをポリゴンストリップへ変換するとともに、前処理されたデータをポリゴンタイルデータベースと称されるデータ構造内に記憶する。通常、ポリゴンは三角形であるが、四角形又は五角形等の他のポリゴン形状が使用されてもよい。三角形を使用する場合には、ポリゴンタイルデータベースが三角形タイルデータベース（ＴＴＤＢ）１０３と称されることがある。以下において説明するほとんどの実施の形態は、三角形を使用する。しかしながら、当業者が容易に四角形、五角形又は他の多角形を代わりに使用できることに留意すべきである。頂点のポリゴンへの変換は、近くの頂点を比較して類似する頂点をグループ化することにより実現され得る。本発明に係るグラフィックシステムにおいて、隣接する類似のポリゴンはポリゴンストリップへ変換される。ポリゴンストリップは少なくとも一つのポリゴンのシーケンスを備えており、それぞれの後続するポリゴンは、その先行するポリゴンと一つの辺を共有する。三角形の代わりに三角形ストリップを使用すると、一つの新たな三角形を定めるために一つの頂点しか必要とせず、その結果、ストリップ内の総ての頂点を指し示すために一つのポインタしか必要としないため、システムのメモリサイズ及び帯域幅の要件が減少する。個々の三角形を使用すると、一つの新たな三角形を定めるために三つの頂点が必要とされる。タイルプロセッサ１０２は、各タイルごとに、ポリゴンストリップのどの部分がそのタイルに重なるのかを決定する。その後、一つのポリゴンストリップのポリゴンを備えるサブストリップが定められ、これらのポリゴンがタイルのうちの特定の一つを覆う。一つのポリゴンが一つのタイルに重なるかどうかを決定するための典型的なアルゴリズムについては、図５を参照して後述する。
【００１３】
サブストリップの幾何学データ（ジオメトリデータ）、及び、タイルに重なる総てのサブストリップの第１の頂点へのポインタは、ＴＴＤＢ１０３内に記憶される。ＴＴＤＢ１０３は、各タイルごとに、そのタイルに重なるサブストリップのうちのそれぞれの一つに対する一つのポインタを伴う表示リストを備えている。ＴＴＤＢ１０３の構造については、図４を参照して更に後述する。ラスタライザ１０５は、ＴＴＤＢ１０３及びテクスチャメモリ１０６からのデータをＲＧＢＡピクセル値へ変換する。ラスタライザ１０５により行われるプロセスの詳細な説明については、図５を参照して後述する。ラスタライザ１０５により計算される一つのタイルにおけるＲＧＢＡピクセル値は、ＲＧＢＡタイルバッファ１０８に書き込まれる。ＲＧＢＡピクセル値は、その（ｘ，ｙ）ピクセル座標に関するＺタイル１０７からのデプス（ｚ）値（深度（ｚ）値）の読み取りを伴うデプステストに依存している場合がある。一つのタイルにおける総てのＲＧＢＡピクセル値が生成されると、ＲＧＢＡタイルがＲＧＢＡフレームバッファ１１０へコピーされる。グラフィックシーンの総てのタイルにおける総てのピクセルに関するＲＧＢＡピクセル値がフレームバッファ内にある場合には、グラフィックシーンがディスプレイスクリーン１１１上に表示されてもよく、又は、グラフィックシーンがビーマへ送られてもよい。
【００１４】
タイルプロセッサ１０２及びラスタライザ１０５等のデータ処理ユニット、並びに、処理ユニットにより使用される情報を一時的に記憶するためのＲＧＢＡタイルバッファ１０８等の小型メモリバッファは、通常、グラフィック処理チップ１００の一部である。ＴＴＤＢ１０３、テクスチャメモリ１０６、ＲＧＢＡフレームバッファ１０９のような更に大きいメモリは、通常、オフチップとして実現される。３Ｄグラフィックは、オフチップテクスチャメモリとオンチップ処理ユニットとの間で多くのデータトラフィックを必要とする。効率的なグラフィック処理のためには、このデータトラフィックを低減しなければならない。ポリゴンストリップ全体の代わりにサブストリップを使用すると、データトラフィックが劇的に減少する。一つのタイルが処理される場合、処理は、そのタイルを覆うポリゴンのみが関与している。ポリゴンストリップ全体を使用する場合には、ストリップの各ポリゴンを処理しなければならないが、実際には、ストリップの一部だけが処理されるべきタイルを覆う。また、本発明に係る手法を使用すると、必要なコンピュータ資源が大幅に減少させられる。
【００１５】
図２は、図１に示される実施の形態に類似するが、頂点キャッシュ２０４を更に備えるグラフィックシステムの実施の一形態を示している。いくつかのポリゴンが複数のタイルを覆っている。結果として、これらのポリゴンは、複数のサブストリップの一部である。これらのポリゴンの頂点データは、いくつかのタイルの処理中に使用されなければならない。図２に示されるグラフィックシステムにおいて、頂点データは、オンチップ頂点キャッシュ２０４内に一時的に記憶される。オンチップ頂点キャッシュ２０４を使用することにより、オフチップメモリからのデータトラフィックが更に低減される。
【００１６】
グラフィックシステムの好ましい実施の形態において、頂点キャッシュ２０４は、厳選された頂点を保存するだけである。例えば、一つのタイルだけに重なるポリゴンの頂点は、１回だけ処理されるとともに、頂点キャッシュ２０４内に保存される必要はない。また、既に処理されたタイルだけに重なる頂点は、頂点キャッシュ２０４内に保存される必要はない。スマートキャッシュ管理は、タイル間処理方向とポリゴンストリップにおけるポリゴン間方向とを比較して、ポリゴンが再び使用されるべきかどうかを決定することを含んでいる。例えば、一つのポリゴンが第１のタイルとこの第１のタイルの上側に隣接する第２のタイルとに重なり且つタイル間横断方向が左から右及び上から下である場合、このポリゴンは、再び処理されず、頂点キャッシュ２０４内に保存される必要がない。これに対し、タイル間処理方向がポリゴン間方向に等しい場合、重なり合うポリゴンは、おそらく再び使用されるであろうことから、頂点キャッシュ２０４内に保存されることが好ましい。効率的なキャッシュ管理は、頂点キャッシュ２０４及びグラフィック処理チップ１００において必要なサイズを減少させることができる。効率的なキャッシュ管理のいくつかの例については、図７Ａ乃至図７Ｃを参照して更に後述する。
【００１７】
図３は、スクリーン上に表示されるポリゴンストリップ３０を示している。スクリーンは、１２個のタイルｔ１−ｔ１２に分割される。タイルサイズは、例えば、オンチップメモリのサイズ、処理能力、スクリーンサイズ、シーン複雑度に応じて選択され得る。３２０×２４０解像度を有する携帯電話スクリーンは、例えば、３２×１６ピクセルからなる１０×１５タイルに分割されるものとしてもよい。図３では、一つの三角形ストリップ３０がスクリーン上に表示されている。三角形ストリップ３０は、三つのタイルｔ５，ｔ６，ｔ７に重なっている。本発明に係るグラフィックシステムにおいて、タイルプロセッサ１０２は、サブストリップを定めるように機能する。この場合、各サブストリップは、一つのポリゴンストリップのうちのいくつかのポリゴンであって複数あるタイルのうちの一つのタイルに少なくとも部分的に重なるいくつかのポリゴンを備えている。図３においては、三つのサブストリップを定めることができる。一つのサブストリップは、頂点ｖ３から始まり頂点ｖ９で終わってタイルｔ５を覆っており、一つのサブストリップは、頂点ｖ６からｖ１４へと延びてタイルｔ６を覆っており、一つのサブストリップは、ｖ１１からｖ１４へと延びてタイルｔ７を覆っている。タイルｔ５の処理においては、頂点ｖ３−ｖ９がＴＴＤＢ１０３から引き出される。頂点ｖ６−ｖ９は、タイルｔ６の処理中の再使用のために頂点キャッシュ２０４内に記憶されてもよい。
【００１８】
図４は、可能なＴＴＤＢデータ構造を概略的に示している。ＴＴＤＢは、頂点データを有するシーンバッファを備えている。シーンバッファは、頂点アレイ（配列）４４と、テクスチャポインタアレイ（配列）４１とを備えている。頂点アレイ４４は、頂点に関する幾何学データを備えている。頂点は、ＸＹＺＵＶＲＧＢＡ属性：スクリーン空間又は他の３Ｄ空間内における頂点の位置に関しては（ｘ，ｙ，ｚ）座標、テクスチャ空間内における頂点の位置に関しては（ｕ，ｖ）座標、頂点のカラー及び透明度を定めることに関してはＲＧＢＡ明度を使用してコード化されるものとしてもよい。テクスチャポインタアレイ４１は、テクスチャメモリ１０６内に記憶されたポインタ−テクスチャマップを備えている。
【００１９】
また、ＴＴＤＢは、各タイルごとに表示リストを備えている。図４には、タイルｔ５（図３参照）に関する表示リスト４２と、タイルｔ６（図３参照）に関する表示リスト４３とが示されている。表示リストは、頂点アレイ４４内の頂点データを参照する４５，４７等の頂点へのインデックス又はポインタを含む場合がある少なくとも二つのタイプのエントリと、４６，４８等の状態変化エントリとを備えている。ｓエントリにより含まれる状態変化データは、テクスチャポインタアレイへのインデックスであってもよく、又は、特定の状態が変化すべきことを示すコードであってもよい。フォグ、ライティング及び他の有効／無効ＯｐｅｎＧＬ機能等の他の状態変化が直接にｓエントリへとエンコードされる。
【００２０】
各頂点ポインタは、一つのサブストリップの最初の頂点を指し示す。例えば、タイルｔ５に関する表示リスト４２は、図３に示されるサブストリップの最初の頂点ｖ３への頂点ポインタ４５を備えており、また、状態変化エントリ４６は、テクスチャポインタアレイ４１内のテクスチャポインタ４９へのインデックスを含んでいる。サブストリップの総ての頂点は、パイプラインの同じ状態を使用して処理される。サブストリップの最後の頂点が処理されたら、次の頂点ポインタにより指し示される次のサブストリップの処理が開始される。ストリップ中の総ての三角形は、新たなテクスチャ状態変化エントリに達するまで、同じテクスチャを使用して処理される。
【００２１】
サブストリップの最後は、各頂点ごとにその頂点がタイルに重なる三角形の一部であるかどうかをチェックすることにより決定され得る。グラフィックシステムの実施の一形態において、表示リストは、それぞれのサブストリップの長さ、又は、サブストリップの最後の頂点へのポインタを更に含んでいる。そのような実施の形態においては、タイルをレンダリングする場合に、各頂点ごとにその頂点が処理されるべきサブストリップの一部であるかどうかをチェックする必要がない。
【００２２】
図５は、タイルＣ，Ｄに重なるポリゴン５０を示している。どのタイルが三角形５０によって覆われるのかを決定するための典型的なアルゴリズムは、以下のステップを含んでいるものとするとよい。
−三角形を構成する頂点の最も小さいｘ座標値（ｘｍｉｎ）、最も大きいｘ座標値（ｘｍａｘ）、最も小さいｙ座標値（ｙｍｉｎ）、最も大きいｙ座標値（ｙｍａｘ）を決定することにより三角形の周りに境界ボックスを形成する。
−総てのタイルの完全セットで開始する。
−ｘｍｉｎよりも小さい最大ｘ値を有する総てのタイルを排除する。
−ｘｍａｘよりも大きい最小ｘ値を有する総てのタイルを排除する。
−ｙｍｉｎよりも小さい最大ｙ値を有する総てのタイルを排除する。
−ｙｍａｘよりも大きい最小ｙ値を有する総てのタイルを排除する。
【００２３】
タイルの残余のセット（組）における総てのタイルは、三角形により覆われる。
【００２４】
図１に示されるグラフィックシステムにおいて、このアルゴリズムは、タイルプロセッサ１０２により実行される。どの三角形がどのタイルを覆うのかを決定するために他のアルゴリズムが使用されてもよいことが認識される。ポリゴンが三角形ではなく四角形、五角形又は他のタイプの多角形である場合にも、同じアルゴリズムが使用され得る。
【００２５】
尚、前述したアルゴリズムを用いると、基本的に、タイルとポリゴンの境界ボックスとの重なり合いが検出される。ポリゴンが三つのタイル、例えば図３におけるタイルｔ２，ｔ３，ｔ７を覆うと、境界ボックスは、４番目のタイル、この場合にはｔ６を覆うことができるが、ポリゴン自体は実際には４番目のタイルを覆わない。そのようなケースにおいて、ポリゴンはタイルに重なるものとして定められるが、実際には、タイルに重なるのは境界ボックスであり、ポリゴンではない。結果として、サブストリップは、時として、実際に対応するタイルを覆わないポリゴンを備える場合がある。しかしながら、隣接するタイルと共に使用するため、必要とされないポリゴンの頂点が依然として頂点キャッシュ２０４内に記憶される可能性があり又は記憶される場合がある。更なるポリゴンは、メモリサイズ、計算能力、帯域幅のようなシステムの技術的要件を著しく増大させない。更に幾分複雑なアルゴリズムを用いると、どのタイルがどのポリゴンによって覆われるべきかを正確に知ることができる。
【００２６】
図６は、ラスタライザ１０５内でＲＧＢＡピクセル値を計算するプロセスのフローチャートを示している。最初のＲＥＴＲステップでは、一つのタイルの表示リスト中の最初のサブストリップの一つの三角形の頂点データがＴＴＤＢ１０３から引き出される。その後、ＣＡＬＣステップにおいて、ラスタライザは、三角形内の総てのピクセルをトラバースするとともに、カラー、z値、（ｕ，ｖ）テクスチャ座標を計算し、この座標におけるテクセルカラーを現在のテクスチャマップから取り出し、又は、各ピクセルごとに他の属性を取り出す。
【００２７】
任意的なデプス試験ステップＣＯＭＰにおいて、計算されたｚ値は、ｚタイルバッファ１０７内に記憶されたｚ値と比較される。試験の結果に応じて、記憶されたｚ値が計算されたｚ値に取って代えられるとともに、書き込みステップＷＲＴにおいてＲＧＢＡカラーがＲＧＢＡタイルバッファ１０８内に書き込まれる。次のステップＭＰにおいては、同じサブストリップの更に多くの三角形又は同じタイル上の更に多くのサブストリップが処理されるべきかどうかがチェックされる。処理されるべきである場合、次のサブストリップの次の三角形が最初のＲＥＴＲステップから開始されて処理される。処理されるべきでない場合には、完全なＲＧＢＡタイルバッファ１０８がフレームバッファ１１０にコピーされる。その後、次のステップＭＴにおいて、フレーム上の更に多くのタイルが処理されるべきかどうかがチェックされる。処理されるべきである場合には、次のタイルの最初のサブストリップの最初の三角形が、再び最初のＲＥＴＲステップを初めとして処理される。処理されるべきでない場合には、表示ステップＤＩＳＰにおいて、フレーム全体をスクリーン１１１上に表示することができ、又は、フレーム全体をビーマへ送ることができる。
【００２８】
図７Ａ乃至図７Ｃでは、効率的なキャッシュ管理のいくつかの例について説明する。図７Ａには、頂点ｑ１−ｑ１２から構成されるポリゴンストリップ７０が示されている。ポリゴンストリップ７０は、タイルｔ２１，ｔ２２，ｔ２３に重なっている。図７Ａでは、サブストリップ７１が強調して表示されている。タイルｔ２２をレンダリングする前、オフチップメモリに対する帯域幅要件を最小限に抑制することによりタイルの効率的なレンダリングを可能にするため、サブストリップ７１の頂点ｑ３−ｑ１０が頂点キャッシュ２０４に既に無かった場合には、これらの頂点が頂点キャッシュ２０４へとロードされる。頂点キャッシュ２０４は、画像をレンダリングするために依然として必要とされる総ての頂点を備えていることが好ましい。この目的は、一つの画像の総ての頂点データを備えることができる十分に大きい頂点キャッシュ２０４を設けることにより容易に得られる。しかしながら、そのような大きい頂点キャッシュ２０４は、製造コスト及びチップ面積の点から見ると非常に高価である。
【００２９】
頂点キャッシュ２０４の好ましい実施の形態においては、一つのタイルをレンダリングした後、他のタイルをレンダリングするために再び使用されるべきではない頂点が、他のタイルをレンダリングするために必要とされる頂点により上書きされる。例えば、図７Ｂの強調表示されたポリゴンを構成する頂点ｑ７−ｑ１０は、タイルｔ２３をレンダリングするために必要とされる。結果として、頂点ｑ７−ｑ１０は、タイルｔ２２のレンダリング後に頂点キャッシュ２０４内に保存されなければならない。サブストリップ７１の他の頂点ｑ３−ｑ６は、タイルｔ２３をレンダリングするために必要とされる他の頂点により上書きされてもよい。
【００３０】
更なる改良された実施の形態においては、一つのタイルをレンダリングする前に、他のタイルをレンダリングするために後に使用されるべき頂点が頂点キャッシュ２０４にロードされる。例えば、タイルｔ２２をレンダリングする前に、サブストリップ７１の頂点ｑ３−ｑ１０をキャッシュすることに加えて、タイルｔ２３をレンダリングするために必要とされる頂点ｑ１１及びｑ１２がキャッシュにロードされる。図７Ｃにおいて、この改良された実施の形態を使用すると、影付き領域は、タイルｔ２２をレンダリングする前にキャッシュされる頂点を含んでいる。この実施の形態を用いると、一つのタイルをレンダリングするために必要とされるデータを頂点キャッシュ２０４から直接に取り出すことができないという事態が最小限に抑制される。その結果、キャッシュの競合がほとんど生じない。
【００３１】
本発明がコンピュータプログラム、特に本発明を実現するようになっているキャリア上の又はキャリア内のコンピュータプログラムにも拡張されることが認識されるべきである。プログラムは、ソースコード、オブジェクトコード、コード中間ソース、部分的にコンパイルされた形式のようなオブジェクトコードの形態をなしていてもよく、又は、本発明に係る方法の実施における使用に適した任意の他の形態をなしていてもよい。キャリアは、プログラムを運ぶことができる任意のエンティティ又はデバイスであってよい。例えば、キャリアとしては、ＲＯＭ、例えばＣＤ−ＲＯＭや半導体ＲＯＭ等の記憶媒体、又は、フロッピーディスクやハードディスク等の磁気記録媒体を挙げることができる。また、キャリアは、電気ケーブル又は光ケーブルを介して又は無線若しくは他の手段により伝達され得る電気信号又は光信号等の送信可能なキャリアであってもよい。プログラムがそのような信号の状態で具現化される場合、キャリアは、そのようなケーブル又は他のデバイスや手段により構成されていてもよい。あるいは、キャリアは、内部にプログラムが組み込まれる集積回路であってもよく、この集積回路は、関連する方法を行うようになっている又は関連する方法の実行において使用されるようになっている。
【００３２】
尚、前述した実施の形態は、本発明の例示であって、本発明を限定するものではなく、当業者であれば、添付の請求項の範囲から逸脱することなく多くの他の実施の形態を設計することができる。請求項中、括弧内の任意の参照符号は、請求項を限定するものと解釈されるべきではない。動詞「備える、含む（comprise）」及びその活用形の使用は、請求項に記載されている要素又はステップ以外の要素又はステップの存在を排除するものではない。要素に先行する冠詞「一つの（ａ，ａｎ）」は、そのような要素が複数存在することを排除するものではない。本発明は、いくつかの別個の要素を備えるハードウェアにより、また、適切にプログラムされたコンピュータにより実施されてもよい。いくつかの手段を列挙するデバイス／システム請求項において、これらの手段のうちのいくつかは、ハードウェアの一つの同じアイテムにより具現化されていてもよい。特定の手段が互いに異なる従属請求項に記載されているという事実だけで、これらの手段の組み合わせを有利に使用することができないということを示すものではない。
【図面の簡単な説明】
【００３３】
【図１】本発明に係るグラフィックシステムの実施の一形態の概略図を示している。
【図２】頂点キャッシュを備えるグラフィックシステムの概略図を示している。
【図３】スクリーン上に表示されるポリゴンストリップを示している。
【図４】可能なＴＴＤＢデータ構造を概略的に示している。
【図５】二つのタイルに重なるポリゴンを示している。
【図６】ＲＧＢＡピクセル値を計算するプロセスのフローチャートを示している。
【図７Ａ】頂点キャッシュのいくつかの実施の形態の動作を示している。
【図７Ｂ】頂点キャッシュのいくつかの実施の形態の動作を示している。
【図７Ｃ】頂点キャッシュのいくつかの実施の形態の動作を示している。
【図１】
2008500625.tif 000003
【図２】
2008500625.tif 000004
【図３】
2008500625.tif 000005
【図４】
2008500625.tif 000006
【図５】
2008500625.tif 000007
【図６】
2008500625.tif 000008
【図７Ａ】
2008500625.tif 000009
【図７Ｂ】
2008500625.tif 000010
【図７Ｃ】
2008500625.tif 000011
【国際調査報告】
2008500625.tif 000012
2008500625.tif 000013
2008500625.tif 000014