(57)【特許請求の範囲】
【請求項１】
複数のピクセル行を含むグラフィック表示フィールド中に複数のタイル行を定義する工程を含み、各タイルは、少なくとも２つのピクセル行からのピクセルを含む、グラフィック処理方法であって、
タイル行のタイルに関する各代表奥行値が、遮蔽基準を満たしているか否かの判断を基準として、表示要素のためのタイル行の各タイルに関する遮蔽フラグを設定する工程と、
遮蔽フラグに応じて、行ごとに、表示要素に関するタイル行に対応するピクセル行のピクセルを処理する工程とを備え、
遮蔽フラグが、タイル行の各タイルに関する各遮蔽フラグと、前記タイル行の各タイルに関する各遮蔽既定奥行値とを格納するように構成される、タイル遮蔽情報キャッシュに格納され、
遮蔽フラグを設定する工程が、
タイルの表示要素に関する最大奥行値を決定する工程と、
最大奥行値を、タイル遮蔽情報キャッシュ内のタイルに関するキャッシュされた遮蔽既定奥行値と比較する工程と、
前記比較に応じてタイルに関する遮蔽フラグを設定する工程とを含むことを特徴とする、グラフィック処理方法。
【請求項２】
ピクセルを処理する工程が、
遮蔽フラグに応じて、タイル行の第１のタイル中のピクセルの一部を処理する工程と、
適切な場合に、遮蔽フラグに応じて、第１のタイルの未処理のピクセルを処理する前に、遮蔽フラグに応じて、タイル行の第２のタイル中のピクセルを処理する工程とを含む、請求項１に記載の方法。
【請求項３】
ピクセルを処理する工程が、ジグザグトラバーサルアルゴリズムを利用して、タイル行中のピクセル行を処理する工程を含む、請求項２に記載の方法。
【請求項４】
グラフィック表示フィールドの各ピクセルに関し各遮蔽既定奥行値を格納するように構成される奥行バッファを設定する工程を更に含み、
遮蔽フラグを設定する工程が、遮蔽が無いことを示すタイルに関する遮蔽フラグを設定する工程を含み、
ピクセルを処理する工程が、
タイルが、遮蔽が無いことを示す遮蔽フラグを有するかを検知する工程と、
それに応じて、奥行バッファからのピクセルに関する遮蔽既定奥行値を読み取ること無しに、タイル内の表示要素に関するピクセルを処理する工程とを含む、請求項１に記載の方法。
【請求項５】
グラフィック表示フィールドのピクセルの夫々に関する各カラー値を格納するように構成されるカラーバッファを設定する工程を更に含み、
それに応じて、奥行バッファからのピクセルに関する遮蔽既定奥行値を読み取ること無しに、タイトル中の表示要素に関するピクセルを処理することが、それに応じて、夫々のカラーバッファと奥行バッファ中のピクセル用の表示要素に関するカラー値と奥行値を格納することを含む、請求項４に記載の方法。
【請求項６】
遮蔽フラグが、タイル行の各タイルに関する各遮蔽フラグ、タイル行の各タイルに関する各遮蔽既定奥行値を格納するように構成される遮蔽情報キャッシュに格納され、
ピクセルの表示要素に関する奥行値を決定することと、
ピクセルの表示要素に関して決定した奥行値と、タイル遮蔽情報キャッシュ中のタイルに関する遮蔽既定奥行値とを比較することと、
前記比較に応じて、タイル遮蔽情報既定キャッシュ中のタイルに関する遮蔽既定奥行値を、ピクセルの表示要素に関する前記決定した奥行値にアップデートすることとを更に含む、請求項５に記載の方法。
【請求項７】
遮蔽フラグを設定する工程が、遮蔽が無いことを示すタイルに関する遮蔽フラグを設定する工程を含み、
ピクセルを処理する工程に先行して、
全タイル行に関して各遮蔽既定奥行値を格納するように構成される集合タイル遮蔽情報メモリを設定する工程と、
タイル遮蔽情報キャッシュに集合遮蔽情報メモリからの遮蔽既定奥行値をロードする工程と、を含み、
タイル遮蔽情報既定キャッシュ内のタイルに関する遮蔽既定奥行値をアップデートする工程の後に続いて、タイル遮蔽情報キャッシュから集合タイル遮蔽情報メモリ内の既定遮蔽奥行値をアップデートする工程とを行う、請求項６に記載の方法。
【請求項８】
グラフィック表示フィールドの各ピクセルに関し各遮蔽既定奥行値を格納するように構成される奥行バッファを設定する工程を更に含み、
遮蔽フラグを設定する工程が、遮蔽の可能性があることを示すタイルに関する遮蔽フラグを設定する工程を含み、
ピクセルを処理する工程が、
タイルが遮蔽の可能性を示す遮蔽フラグを有するかを検知する工程と、
タイルが遮蔽の可能性があることを示す遮蔽フラグを有するかを検知するのに応じて、タイル中のピクセルの表示要素に関する奥行値と奥行バッファ中のピクセルに関する遮蔽既定奥行値とを比較する工程と、
前記比較に応じてピクセルを処理する工程と、
ピクセルの書込まれた奥行値に応じて、タイル遮蔽情報キャッシュ中のタイルに関する遮蔽既定奥行値をアップデートする工程とを含む、請求項１に記載の方法。
【請求項９】
グラフィック表示フィールドのピクセルの夫々に関する各カラー値を格納するように構成されるカラーバッファを設定する工程を更に含み、
ピクセルを処理する工程が、
タイル中のピクセルの表示要素に関する奥行値と奥行バッファ中のピクセルに関する遮蔽既定奥行値との比較が、遮蔽が無いことを示した場合、カラーバッファと奥行バッファにカラー値と奥行値を格納する工程と、
ピクセルの書き込まれた奥行値に応じて、タイル遮蔽情報キャッシュ中のタイルに関する遮蔽奥行値をアップデートする工程とを含む、
請求項８に記載の方法。
【請求項１０】
遮蔽フラグが、タイル行の各タイルに関する各遮蔽フラグと、タイル行の各タイルに関する各遮蔽既定奥行値と、タイル行の各タイルに関する各ステイタスフラグとを格納するように構成されるタイル遮蔽情報キャッシュ中に格納され、
タイル遮蔽情報キャッシュに応じて、第１のピクセル行を処理する工程であって、少なくとも１つのタイルの遮蔽ステイタスが決定されたことを示すために、第１のタイル行中の少なくとも１タイルに関して遮蔽とステイタスのフラグとを設定する工程を含む、第１のピクセル行を処理する工程と、
第２のピクセル行が、第１のタイル行中にあるかを決定する工程と、
第２のピクセル行が第１のタイル行にある場合、第１のピクセル行から得たタイル遮蔽キャッシュ中の情報を用いて第２のピクセル行を処理する工程と、を更に含む、請求項１に記載の方法。
【請求項１１】
第１のピクセル行を処理する工程に先行して、
全タイル行中の全タイルに関する各遮蔽既定奥行値を格納するように構成される集積タイル遮蔽情報メモリを設定する工程と、
タイル遮蔽情報キャッシュ中の遮蔽とステイタスのフラグとを既定値に設定する工程と、
集積タイル遮蔽情報メモリから第１のタイル行に関する遮蔽既定奥行値をタイル遮蔽情報キャッシュに格納する工程とを行う、請求項１０に記載の方法。
【請求項１２】
遮蔽フラグが、タイル行の各タイルに関する各遮蔽フラグと、タイル行の各タイルに関する各遮蔽既定奥行値と、タイル行のタイルに関する各ステイタスフラグとを格納するように構成されるタイル遮蔽情報キャッシュに格納され、
タイル行の全タイルに関する各遮蔽既定奥行値を格納するように構成される集積タイル遮蔽情報メモリを設定する工程と、
タイル遮蔽情報キャッシュに応じて第１のピクセル行を処理する工程であって、第１行の少なくとも１つのタイルの少なくとも１つの遮蔽ステイタスが決定されたことを示すために、第１のピクセル行中のピクセルを有する第１のタイル行に関して遮蔽フラグとステイタスフラグを設定する工程を含む、第１のピクセル行を処理する工程と、
第２のピクセル行が、第１のタイル行であるか、該第１のタイル行と異なる第２のタイル行であるかを決定する工程と、
第２のピクセル行が第２のタイル行であるという決定に応じて、タイル遮蔽情報キャッシュから、タイル遮蔽情報キャッシュ中の集積タイル遮蔽情報に、遮蔽既定奥行値を書き戻し、遮蔽既定奥行値を、集積タイル遮蔽情報メモリからの第２のタイル行に関する対応する遮蔽既定奥行値で、タイル遮蔽情報キャッシュに遮蔽既定奥行値をロードし、アップデートしたタイル遮蔽キャッシュを利用して第２のピクセル行を処理する工程と、を更に含む、請求項１に記載の方法。
【請求項１３】
第２のピクセル行が第１のタイル行にあるか否かを決定する工程の後に続いて、第２のピクセル行が第２のタイル行にあることを決定するのに応じて、タイル遮蔽キャッシュからの遮蔽既定奥行値で、集積タイル遮蔽情報メモリ中の第１のタイル行に関する遮蔽既定奥行値をアップデートする工程を行う、請求項１２に記載の方法。
【請求項１４】
ディスプレイと、ディスプレイに連結され、ディスプレイのグラフィック表示フィールド中の複数のタイル行を定義し、各タイルがピクセルの少なくとも２行からのピクセルを含むグラフィック処理装置と、タイル遮蔽情報キャッシュとを備えた装置であって、
前記グラフィック処理装置が、タイル行のタイルに関する各代表奥行値が遮蔽の基準を満たすか否かを基本とした表示要素に関するタイル行の各タイルに関する遮蔽フラグを設定し、表示要素に関するタイル行に対応するピクセル行中のピクセルを行ごとに遮蔽フラグに応じて処理するための作動が可能であり、
遮蔽フラグが、タイル行の各タイルに関する各遮蔽フラグと、前記タイル行の各タイルに関する各遮蔽既定奥行値とを格納するように構成される、前記タイル遮蔽情報キャッシュに格納され、
前記グラフィック処理装置が、タイルの表示要素に関する最大奥行値を決定し、最大奥行値を、タイル遮蔽情報キャッシュ内のタイルに関するキャッシュされた遮蔽既定奥行値と比較し、前記比較に応じてタイルに関する遮蔽フラグを設定することを特徴とする、装置。
【請求項１５】
グラフィック処理装置が、遮蔽フラグに応じて、タイル行の第１のタイル中のピクセルの一部を処理し、次に、遮蔽フラグに応じて第１のタイル中の未処理のピクセルを処理する前に、遮蔽フラグに応じてタイル行の第２のタイル中のピクセルを処理するように作動する、請求項１４に記載の装置。
【請求項１６】
グラフィック処理装置は、ジグザグトラバーサルアルゴリズムを利用してタイル行中のピクセル行を処理するように作動する、請求項１４に記載の装置。
【請求項１７】
ディスプレイとグラフィック処理装置が携帯電子機器に内蔵される、請求項１４に記載の装置。
【請求項１８】
コンピュータ読取可能媒体に組み込まれたプログラムコードを含み、前記プログラムコードは、ディスプレイのグラフィック表示フィールド中の複数タイル行を定義するように構成されるプログラムコードを含み、各タイルが少なくとも２つのピクセル行からのピクセルを含む、コンピュータプログラム製品であって、
前記プログラムコードが、タイル行のタイルに関する各代表奥行値が遮蔽の基準を満たすか否かを基準として、表示要素に関するタイル行の各タイルに関する遮蔽フラグを設定し、遮蔽フラグに応じて、行ごとに、表示要素に関するタイル行に対応するピクセル行中のピクセルを処理するように更に構成され、
前記プログラムコードが、遮蔽フラグが、タイル行の各タイルに関する各遮蔽フラグと、前記タイル行の各タイルに関する各遮蔽既定奥行値とを格納するように構成される、タイル遮蔽情報キャッシュに格納されるように構成され、
遮蔽フラグを設定するプログラムコードが、タイルの表示要素に関する最大奥行値を決定し、最大奥行値を、タイル遮蔽情報キャッシュ内のタイルに関するキャッシュされた遮蔽既定奥行値と比較し、前記比較に応じてタイルに関する遮蔽フラグを設定することを特徴とする、コンピュータプログラム製品。
【請求項１９】
前記プログラムコードが、遮蔽フラグに応じてタイル行の第１のタイル中のピクセルの一部を処理し、次に、遮蔽フラグに応じて第１のタイル中の未処理のピクセルを処理する前に、遮蔽フラグに応じてタイル行の第２のタイル中のピクセルを処理するように更に構成される、請求項１８に記載のコンピュータプログラム製品。
【請求項２０】
前記プログラムコードが、ジグザグトラバーサルアルゴリズムを利用して、タイル行中のピクセル行を処理するように更に構成される、請求項１９に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願）
本出願は、「ジグザグＺ−Ｍｉｎカリング」と題した、アクニンモラーの２００２年１２月２０日提出の米国仮出願第６０／４３４９００号からの優先権を主張し、その全体を参照として本明細書に組み込む。
本発明は、コンピュータグラフィックに関し、特にグラフィック処理方法、グラフィック処理装置、そしてコンピュータプログラム製品に関する。
【背景技術】
【０００２】
携帯電話は、世界中で利用されている。携帯電話には一般的にディスプレイがあるので、ディスプレイ上にイメージを表示することも可能である。このことはまた、今日携帯電話が、表示基盤として最も広まった理由でもある。しかし、この種の表示は、たいてい非常に単純な２次元グラフィックに限定されており、このような状況で最近ようやく３次元グラフィックが脚光を浴びるようになった。携帯表示（mobile graphics）に対する関心の高まりは、ジャバ仕様要求１８４（例えばｗｗｗ．ｊｃｐ．ｏｒｇ）や組込システム用のＯｐｅｎＧＬ  ＥＳ（例えばｗｗｗ．ｋｈｒｏｎｏｓ．ｏｒｇを参照）等の来るべき仕様の動向に見られる。３次元グラフィックを利用する傾向にあるアプリケーションには、マンマシンインターフェイス（ＭＭＩｓ）、スクリーンセイバー、地図、動画メッセージ、そして当然ゲームを含む。
【０００３】
携帯電話は、例えばグラフィックカードを搭載したＰＣシステムとは抜本的に異なる元来２つの特質を示す。第１に非常に小さなディスプレイを有し、第２に表示について非常に少量のリソースを有することである。これらの特質を次に簡単に説明する。
【０００４】
現存するカラー表示装置付携帯電話は、たいてい（１７６〜３２０）×（１４４〜２４０）の解像度であり、即ちディスプレイが非常に小さい。ＱＣＩＦ仕様は、解像度１７６×１４４を定義し、ＱＶＧＡ仕様は３２０×２４０を利用する。例えば１０２４×７６８より高い解像度が携帯電話に表示可能である一方、それは非常にハイエンドな携帯電話にのみ利用される可能性が高く、殆どの人々に利用可能なものではない。しかも、このような高解像度は、より多くのエネルギーを消費し、バッテリの寿命を短くする可能性がある。したがって、ＱＣＩＦやＱＶＧＡのような、低解像度が優勢となることが予想される。
【０００５】
ディスプレイのカラーの数から考えると、２５６〜６５５３６カラーが一般的である。低解像度に加え、多くの場合ユーザは目に近い位置にディスプレイを維持するので、ＰＣシステムのディスプレイに比べて、平均的な目からのピクセル角度が大きくなる。その結果、これらのディスプレイ環境は、携帯電話ディスプレイの各ピクセルが、最終的にＰＣシステムよりも高品質で表示されるべきであることを意味する。このことは、よく「表示品質と画面サイズの逆法則」と呼ばれている。
【０００６】
携帯電話が低解像度を利用する幾つかの理由がある。一般的に携帯電話は、再充電可能なバッテリを電源としているので、どのような表示であっても極力小さなエネルギーを使用することが好ましい。更に、バッテリ技術は通常ムーアの法則の速度で改良されていない。しかも、コンピュータシステムにおいて、外部メモリアクセスが最もエネルギーを使用する作用である場合が最も多い。これは、帯域幅のリソースが注意して利用されるべきで、まずピークの帯域幅が非常に限定されていることを意味する。
【０００７】
携帯電話は、装置一台当たりのコストを低く保つために、通常非常に小さなメモリが搭載され、グラフィック作動用には小さなチップ領域が与えられる。小さな利用可能帯域幅と、小さなチップ領域と、少量のメモリとが、全て装置ごとの価格を低く保つのに役立つが、もっと重要なことは、これらの要因がまた、殆どの場合、多くのリソースを有するシステムよりも少ないエネルギーを使用するのに貢献することである。リアル携帯電話データの典型例は、（１）クロック周期ごとに１またはハーフ３２ビットメモリアクセス、（２）１０〜２００ＭＨｚのＣＰＵ、そして（３）適当な速さのメモリ１〜１６ＭＢである。
【０００８】
３次元グラフィックのリアルタイム表示は、ゲーム、マンマシンインターフェイス、メッセージング、Ｍコマースを含む、幾つかの魅力的な携帯端末への応用が可能である。３次元表示は、通常コンピュータ利用上高価な作業であるため、充分なパフォーマンスを発揮するために、多くの場合専用ハードウエアが搭載される必要性がある。したがって、このハードウエアアーキテクチャの複雑性と帯域幅の利用を軽減する革新的な方法が、非常に重要なこととなる。
【０００９】
多くの場合、Ｚバッファ（奥行バッファ）が、可視性の解決に用いられる。これは、通常三角形がどのような順番でも描くことが可能なので、一般的に行われている。したがって、Ｚバッファは、目から三角形までの換算距離を格納し、もし次の三角形がＺバッファのコンテントよりも遠い場合、カラーとＺバッファが上書きされない。
【００１０】
いぜんとして、ピクセルは幾度か上書き可能なので、この方法もまた、グラフィックシステムが賢いものではないことを意味している。そして、ピクセルが幾度か上書きされたとしても、結局１つの形状要素（三角形）のみが可視状態である。アナログでカンバスの上に絵を描くようなもので、最下層のレイヤーは、最上層のレイヤーによって覆われてしまう。グラフィックシステムに関しても、ペイントがどのような順番でも描くことが可能なことを除けば、同じことである。
【００１１】
また携帯プラットフォームに関し、メモリアクセスが一般的に限られたエネルギーのかなりの部分を使用するので、通常メインメモリに利用する帯域幅が減少すればするだけ望ましいことに気付くことが重要である。
【００１２】
今日、遮蔽カリングの形式を使う、例えばＮＶＩＤＩＡのＧｅｆｏｒｃｅ３以上とＡＴＩラディオンといった幾つかのグラフィックカードがある。画面は、例えば８×８領域（タイル）に別れ、各タイルに関し、そのタイルのＺバッファ中のＺ値の最大、ＺＭＡＸが、（速く、エネルギーを多く使用しない（not energy-expensive））キャッシュメモリに格納される。三角形が表示される時、次のタイルに変わる前に、全ピクセルがタイルで参照され、新タイルに移行すると、そのタイル内の三角形上の最小Ｚ値、ＺＭＩＮが計算される（そうでなければ、安価で正確性が低い手段を利用して、最小Ｚ値を過大評価してしまう）。ＺＭＩＮがタイルのＺＭＡＸより大きい場合、現在表示する三角形が遮蔽され（さえぎられ）、それ以上この三角形に関する前記タイルを処理する必要がない。タイルが遮蔽されない場合、タイル内部のピクセルが通常通り処理され、即ち三角形内の含有物に関してピクセルをテストし、Ｚテストが行われ、テクスチャ化される。
【００１３】
（アクニン―モラートーマス、エリックハインズ、「リアルタイム表示」第２版、２００２年６月の６９４〜６９７頁に説明された）モレーンの米国特許第６４２１７６４号、「メモリの有効なクリア方法および装置」は、メモリの効果的なクリア方法を説明している。（例えば）Ｚバッファをクリアする代わりに、各タイル（例えば８×８領域）にフラグを設定する。その後、タイルが最初にアクセスされた時、そのブロックのピクセルの読み込みを回避でき、代わりに、フラグが設定されているので、「クリアバリュー」が高速のチップ搭載メモリから読み込まれる。タイルが最初に書き込まれると、フラッグの設定が解除される。これにより、クリア中には、メモリの一部にしかアクセスしないので、エネルギーと帯域幅の節約になる。
【００１４】
一般的に、より良いパフォーマンスと（バッテリの）パワーの節約との両方を成就するためには、メインメモリへの帯域幅は出来る限り小さくすることが望ましい。三角形上でテクスチュア（イメージ）データ、Ｚ座標等を補間するために、幾つかのパラメータを格納する必要がある場合があり、特定のピクセルに関するパラメータのセットが、コンテキストと呼ばれる。他のピクセルに移動する時、このコンテキストのアップデートが可能である。利用されるコンテキストの数が増えれば、ハードウエア中のゲートに関する解決手段がより高価なものとなり得る。
【００１５】
一般的に費用対効果を考え、ゲート数を出来るだけ抑えることが望ましい。次のタイルに移動する前に、タイルの全ピクセルを参照するための現在既知の方法は、４または５の全コンテキストが必要である（マコーミック、ジョエル、ロバートマクナムラの「ハーフプレーンエッジ機能を利用したタイルポリゴントラバーサル」、グラフィックハードウエアのワークショップ、２０００年８月、１５〜２２頁、そしてケルハー、ブライアンの「ピクセルビジョンアーキテクチャ」、デジタルシステムリサーチセンタ、１９９８−０１３、１９９８年１０月を参照のこと）。これは携帯プラットフォームには高価過ぎる。またＺ−ＭＡＸ技術を利用することが可能であるが、タイル全体の全Ｚ値はＺ−ＭＡＸがアップデートされる前に読み込まれる必要性があるので、三角形が表示された後に、Ｚ−ＭＡＸをアップデートするのは高価なもとなり得るといった潜在的な問題があることに注意すべきである。Ｚ−ＭＡＸを利用した現在の解決策は、Ｚ値の全ブロックを読み込んで解決する。それは、一般的に携帯プラットフォームよりもメインメモリへの帯域幅が大きいために可能なことであり、このような解決策を講じることができる。
【００１６】
一般的に、全システムを説明した低コストのアーキテクチャに関する公開はあまり存在しない。２つの著名な例外としては、ネオン（マコーミック、ジョエルとロバートマクナムラに説明された「ハーフプレーンエッジ機能を利用したタイルポリゴントラバーサル」、グラフィックハードウエアのワークショップ、２０００年８月、１５〜２２頁、そしてピクセルビジョンアーキテクチャ（ケルハー、ブライアンの「ピクセルビジョンアーキテクチャ」、デジタルシステムリサーチセンタ、１９９８−０１３、１９９８年１０月に説明された）がある。イマジネーションテクノロジは、ＭＢＸと呼ばれるシステムを有し、このアーキテクチャはタイルベースであるので、Ｚバッファ、バックバッファ、ステンシルバッファのみを、例えば３２×１６ピクセルのタイルのサイズとする必要がある。このメモリはよく高速オンチップメモリに実装される。最初に、全ジオメトリをタイルにソートするために１つのパスが必要であり、メモリとメモリ帯域幅も必要となる。このソート化が終了すると、各タイルのジオメトリが、ラスタライズされる。ラスタライゼーション中、可視性が決定され、可視のフラグメントにだけテクスチャリングとシェーディングが実行される。これを遅延シェーディングという。タイルソーティングと平行して行われるタイルのラスタライゼーションを保持するために、各タイルに２つのバッファが必要となる。ＭＢＸアーキテクチャに関しては十分な情報がないので、バッファ用のメモリの節約を除いて、どのような利点があるか明確ではない。このアーキテクチャがエネルギーの節約を提供することは極めて明白である。しかし、どれだけ節約になるかの記述は存在しない。
【００１７】
サブピクセルの精度のポリゴンのラスタライゼーションに関し、ラスロップ、Ｏ．カーク、Ｄ．とブーチズの「サブピクセルアドレシングによる正確な表示」、ＩＥＥＥコンピュータグラフィックとアプリケーション１０，５（１９９０年９月）４５〜５３頁に説明された、改良ブレセンハムアルゴリズムを利用可能である。よく利用される代替策としては、三角形の内側の領域を、三角形の輪郭の陽の半スペースの論理交差（the logical intersection of the positivehalf-spaces of the triangle edges）（ロジカルインターセクション）として説明した、ピネダ、Ｊ．の「ポリゴンラスタライゼーションのための並列アルゴリズム」シーグラフ会報１９９８、ＡＣＭ，１７〜２０頁（１９８８年）に説明されているような、輪郭機能を利用する。そして、三角形内のピクセルを探すために異なった策が利用可能である。これがトラバーサルといわれるものだ。この策がどれだけ効果的かによって、トラバーサル中、異なった数の（補間パラメータ等の）コンテキストが要求される。各コンテキストは、ゲートに関しては、通常非常にコストがかかるものだ。
【発明の開示】
【発明が解決しようとする課題】
【００１８】
図１は、ピネダのジグザグトラバーサルスキームによる三角形のトラバーサルを示す。薄いグレーまたは暗いグレーでマークされたピクセルは、トラバーサルスキームで触れられるピクセルである。暗いグレーでマークされたピクセルは、トラバーサルアルゴリズムが三角形内に見つけるピクセルである。ジグザグトラバーサルアルゴリズムのパスは、矢印のパスとして図示されている。基本的に、三角形は、三角形の外に出るまで、第１スキャンライン上を右から左へとトラバースされる。そして、１ステップ上がる。そして、三角形の中であれば、三角形の外に出るまで同じ方向に進行する必要がある。これは、バックトラッキングと呼ばれる。三角形の外になった場合、トラバーサルの方向が逆になり、今度は左から右に、現在のスキャンラインをラスタライズし始める。三角形の外の場合、更に上がり、継続される。
【００１９】
図１には一例が示されている。最も下のスキャンライン上で、１ピクセルが設定されるが、１つ左隣のピクセルは三角形の外である。これは、１つ上に上がるべきという意味である。このステップの後、三角形内に位置し、バックトラック、即ち三角形の外に出るまで左に継続して進む必要がある。１つのピクセルの後は、三角形の外であり、トラバーサル方向を反対に（右から左、左から右に）することが可能であり、第２スキャンラインをラスタライズし始める。三角形内に位置すべき２つのピクセルを発見し、この後、三角形外に位置し、１つ上がる必要がある。今度は、既に三角形の外に位置し、バックトラックする必要がない。したがって、トラバーサル方向を逆にし、第３スキャンラインをラスタライズし始め、これを継続することが可能である。
【００２０】
三角形内に見つけられたピクセルに出会うたびに、描画するか否か判断する必要がある。したがって、そのポイントでの三角形のＺ値を計算する。ここではｚ−ｔｒｉ（ｘ，ｙ）と呼び、（ｘ，ｙ）がこのポイントの座標である。そして、そのピクセルに関するＺバッファからのＺ値を取得し、これをｚ−ｂｕｆ（ｘ，ｙ）と呼ぶ。ｚ―ｔｒｉ（ｘ，ｙ）＞＝ｚ―ｂｕｆ（ｘ，ｙ）であれば何も起こらない。しかし、もしｚ―ｔｒｉ（ｘ，ｙ）＜ｚ―ｂｕｆ（ｘ，ｙ）であれば、ピクセルを描画すべきであり、またＺバッファをｚ―ｔｒｉ（ｘ，ｙ）でアップデートすべきである。スードコード（pseudo code）で、次のように表現される：
【００２１】
ｃａｌｃｕｌａｔｅ  ｚ―ｔｒｉ（ｘ，ｙ）
【００２２】
ｆｅｔｃｈ  ｚ−ｂｕｆ（ｘ，ｙ）ｆｒｏｍ  ｚ−ｂｕｆｆｅｒ
【００２３】
ｉｆ（ｚ―ｔｒｉ（ｘ，ｙ）＜ｚ―ｂｕｆ（ｘ，ｙ））
【００２４】
｛
【００２５】
ｗｒｉｔｅ  ｚ−ｔｒｉ（ｘ，ｙ）  ｔｏ  ｚ−ｂｕｆｆｅｒ
【００２６】
ｗｒｉｔｅ  ｃｏｌｏｒ  ｉｎ  ｃｏｌｏｒ−ｂｕｆｆｅｒ
【００２７】
｝
【００２８】
ステートメントは、任意の奥行きテスト、ｉｆ（ｄｅｐｔｈｔｅｓｔ（ｚ−ｔｒｉ（ｘ，ｙ），ｚ−ｂｕｆ（ｘ，ｙ））と書くことが可能であることに注意されたい。コヒーレンスの利用レベルを増加するために、そして単純な遮蔽カリングアルゴリズムのために、多くの場合、グラフィックハードウエアは、三角形がタイル状態でカバーするピクセルをトラバースする（ケルハー、ブライアンの「ピクセルビジョンアーキテクチャ」、デジタルシステムリサーチセンタ、１９９８−０１３、１９９８年１０月、マコーミック、ジョエルとロバートマクナマラの「ハーフプレーンエッジ機能を利用したタイルポリゴントラバーサル」、グラフィックハードウエアのワークショップ、２０００年８月、１５〜２２頁、そしてモレーンの米国特許第６４２１７６４号を参照のこと）。これは、タイル（例えば８×８領域）内の全ピクセルが、他のタイル上に移動する前に参照されるという意味である。これには異なったトラバーサル策が必要とされ、格納される必要があるコンテキストの数を考えると費用がかかる。例えば、マコーミックとマクナムラは、対応する非タイルトラバーサルよりも１つコンテキストを多く要求するタイルトラバーサルアルゴリズムについて説明している。全体で、タイルバージョンには４つのコンテキストが必要である。
【００２９】
断層的Ｚバッファアルゴリズムは、Ｚピラミッドを利用し、ピラミッド中の各レベルの各ピクセルが、（グリーン  Ｎ．カスとミラー  Ｇ．の「断層化Ｚバッファ可視性」シーグラフ会報１９９３、ＡＣＭ，２３１〜２３８頁（１９９３年）、米国特許第５６００７６３号、米国特許第５５７９４５５号に説明されているように、（下のレベルの）最大で４つの子のＺ値を格納する。したがって、ピラミッドの先端には、全スクリーン上の全Ｚ値の最大が格納される。このピラミッドが遮蔽カリングを行うのに利用される。ジオメトリのグループを表示する時、そのグループのバウンディングボリュームが、スキャン変換されて、そのグループが可視か否かを判定するために、Ｚバッファ中の適切なレベルでテストされる。このアルゴリズムは、ソフトウエアで実行する場合に非常に有効ではあるが、しかし、まだハードウエア完全実装は存在しない。しかし、たいていグラフィックハードウエア製品は、簡単な遮蔽カリングの形式を有している。モーレン  Ｓ．の「ＡＴＩラディオンのハイパーＺテクノロジ」グラフィックハードウエアのワークショップ、Ｈｏｔ３会報、ＡＣＭシーグラフ、ユーログラフィックス  モーレン（２０００）は、各タイルが、タイル内のＺ値の最大、Ｚｍａｘを格納し、例えば８×８ピクセルとなり得る技術を説明している。三角形の走査中、新たなタイルに移行した時、三角形の「最小」Ｚ値が、対応するタイルのＺｍａｘよりも大きいか否かを判断するテストが行われる。もし大きいのであれば、そのタイルを飛ばし、そうでなければ、タイルが通常通りレンダーされる。Ｚｍａｘをアップデートするには、タイルの全Ｚ値が読み込まれる必要があり、高価なものとなり得ることに注意されたい。他のタイル又はブロックベースのカリング技術は、米国特許第６０３７９４６号のＴＡＫＥＤＡ、欧州特許出願ＥＰ１１０７１７７号に記載されている。
【課題を解決するための手段】
【００３０】
本発明の実施形態によれば、複数のピクセル行（rows of pixels）を含むグラフィック表示フィールドにおいて、複数のタイル行（rows of tiles）が定義され、各タイルは少なくとも２つのピクセル行のピクセルを有する。表示要素（graphics primitive）のタイル行の夫々のタイルに関する（例えば、遮蔽無し、遮蔽有り、他の遮蔽状態を示す）遮蔽フラグが、タイル行のタイルに関する各代表奥行値が遮蔽の基準を満たすか否かをベースに設定される。タイル行に対応するピクセル行のピクセルは、遮蔽フラグに応じて、行ごとに（in a row-by-row manner）、表示要素に関して処理される。この処理は、遮蔽フラグに応じてタイル行の第の１タイル中のピクセルの一部を処理し、次に、遮蔽フラグに応じて第１のタイル中の追加ピクセルを処理する前に、遮蔽フラグに応じてタイル行の第２のタイル中のピクセルを処理する工程を含むことが可能である。この処理は、ジグザグトラバーサルアルゴリズムを利用してタイル行中のピクセルの行を処理する工程を含むことが可能である。
【００３１】
本発明の更なる実施形態では、遮蔽フラグが、タイル行の各タイルに関する各遮蔽フラグ、タイル行の各タイルに関する各遮蔽既定奥行値（occlusion threshold depth values）を格納するように構成されるタイル遮蔽情報キャッシュに格納される。遮蔽フラグを設定する工程は、タイルの表示要素のための最大奥行値を決定し、そのタイルの最大奥行値をタイル遮蔽情報キャッシュ中のそのタイルのキャッシュされた遮蔽既定奥行値と比較し、その比較に対応する遮蔽フラグを設定する工程を含む。
【００３２】
次の実施形態によれば、奥行バッファは、グラフィック表示フィールドの各ピクセルの各遮蔽既定奥行値を格納するよう構成される。遮蔽フラグを設定する工程は、遮蔽が無いことを示すためのタイルの遮蔽フラグを設定する工程を含み、ピクセルを処理する工程は、タイルが、遮蔽が無いことを示す遮蔽フラグを有することを検知する工程と、それに応答して奥行バッファよりのピクセルの遮蔽既定奥行値を読み取ること無くタイルの表示要素のためにピクセルを処理する工程とを有する。
【００３３】
この方法は更に、ピクセルの表示要素に関する奥行値を決定する工程と、ピクセルの表示要素に関する前記決定した奥行値と、タイル遮蔽情報キャッシュ中のそのタイルに関する遮蔽既定奥行値とを比較する工程と、比較に対応してピクセルの表示要素に関する奥行値を決定するためにタイル遮蔽情報既定キャッシュ中のそのタイルに関する遮蔽規定奥行値をアップデートする工程とを有することが可能である。
【００３４】
追加の実施形態では、遮蔽フラグを設定する工程は、遮蔽が無いことを示すためにタイルの遮蔽フラグを設定する工程と、ピクセルの処理に先行して、全タイル行の各遮蔽既定奥行値を格納するように構成される集積タイル遮蔽情報メモリ（aggregate tile occlusion information memory）を設定する工程と、集積時間遮蔽情報メモリからの遮蔽既定奥行値でタイル遮蔽情報キャッシュをロードする工程とを含む。タイル遮蔽情報既定キャッシュ中のタイルの遮蔽既定奥行値をアップデートして、次にタイル遮蔽情報キャッシュから集積タイル遮蔽情報キャッシュ中の既定遮蔽奥行値をアップデートする。
【００３５】
更なる本発明の実施形態では、遮蔽フラグが、タイル行の各タイルの各遮蔽フラグと、タイル行の各タイルの各遮蔽既定奥行値と、タイル行の各タイルの各ステイタスフラグとを格納するように構成されるタイル遮蔽情報キャッシュ中に格納される。タイル行のどこかに位置する第１のピクセル行が、タイル遮蔽情報キャッシュに応じて処理され、第１のピクセル行の処理が、少なくとも１つのタイルの遮蔽ステータスが決定されたことを示すために、第１のタイル行中の少なくとも１つのタイルに関する遮蔽とステイタスフラグを設定する工程を有する。そして、次のピクセル行が、第１のタイル行中にあるかを決定する。もし第１のタイル行中にあるのであれば、次のピクセル行が、第１のピクセル行から得たタイル遮蔽キャッシュ中の情報を利用して処理される。もしそうでなければ、タイル遮蔽情報キャッシュ中の遮蔽とステイタスフラグ情報がクリアされ、タイル遮蔽情報キャッシュ中の遮蔽既定奥行値が、タイル遮蔽情報キャッシュから集積タイル遮蔽情報メモリへの対応する遮蔽既定値の書き込みによってアップデートされ、そして遮蔽既定値を集積タイル遮蔽情報メモリから次のタイル行に応じたタイル遮蔽情報キャッシュに読み込む。そして、次のピクセル行が、更新されたタイル遮蔽キャッシュを利用して処理される。
【００３６】
本発明の追加的な態様によれば、複数のタイル行は、グラフィック表示フィールドに定義され、各タイルが、複数のピクセルを含む。タイルの遮蔽フラグが、タイルの表示要素に関する遮蔽が無いことを示すように設定される。遮蔽が無いことを示す遮蔽フラグを有するタイルを検知したことに対して、タイル中の表示要素に関してピクセルが処理される。ピクセルは、奥行バッファからのピクセルの遮蔽既定奥行値を読み取ること無く処理が可能であり、これによって奥行バッファから読み取る頻度を減少させることが可能である。
【００３７】
本発明は、方法、装置そしてコンピュータプログラム製品として具体化が可能である。例えば、本発明は、携帯無線端末、パーソナルデジタルアシスタント（ＰＤＡ）等のポータブルな電子機器に有効利用可能である。
【発明を実施するための最良の形態】
【００３８】
以下に、本発明を説明する実施形態が図示された添付図面を参照しながら、本発明を充分に説明する。これらの実施形態は、本発明を詳細に完全に説明する目的で提供される。全体を通して同じ符号は、同じ要素を示している。
【００３９】
図２〜６を参照して以下に説明された本発明の実施形態は、３つの新しい方法で、ピネダのジグザグトラバーサル法を拡大することが可能である。
【００４０】
（１）  Ｚバッファは、例えば８×８ピクセルの重ならないタイルに分けることが可能である。
【００４１】
（２）  システム中にタイル情報（「集積タイル遮蔽情報メモリ」と上述した）と呼ばれるメモリを有することができ、タイルに関する情報が格納される。各タイルに関し、タイル中の全Ｚ値の最小値を保持するｚ−ｍｉｎ変数を格納することができる。例えば、スクリーンの解像度が、１７６×１４４で、タイルのサイズが８×８である場合、タイル数が、１７６／８×１４４／８＝２２×１８＝３９６である。したがって、もし各ｚ−ｍｉｎ値が２バイトである場合、タイル情報は、３９６のｚ−ｍｉｎ値、すなわち３９６×２＝７９２バイトを保持可能である。特定タイルのｚ−ｍｉｎに関するアドレスを得るために、ピクセルのｘとｙ座標が利用可能である。例えば、１７６×１４４ピクセルと８×８タイルの上記の例において、アドレスは、（ｙ／８）＊２２＋ｘ／８（「／」は整数除算）のように計算できる。
【００４２】
（３）  タイル行に関する情報を格納できる、行タイル情報（「タイル遮蔽情報キャッシュ」と上述した）と呼ばれるキャッシュメモリを有することが可能である。３つの情報が、行中の各タイルに関して格納可能である。３つの情報の１つ目は、タイル情報中に存在するｚ−ｍｉｎのキャッシュバージョンである「ｚ−ｍｉｎキャッシュ」である。通常のキャッシュと同様、ｚ−ｍｉｎキャッシュの値が、タイル情報のアップデート無しで、アップデートが可能である。タイルの全行の処理後、ｚ−ｍｉｎキャッシュが、タイル情報中のｚ−ｍｉｎに書き戻される必要がある。２つ目は、１ビットステイタスフラグの「参照（visited）」で、３つ目もまた１ビットフラッグの「可視（visible）」（「遮蔽無しフラグ」と上述）である。
【００４３】
キャッシュメモリは、完全なタイル行に関する情報を格納するために充分に大きくすることが可能である。例えば、解像度が１７６×１４４で、タイルのサイズが８×８であった場合、１つのタイル行は１７６／８＝２２タイルと等しく、行タイル情報は、２２タイルに関して「ｚ−ｍｉｎキャッシュ」、「参照」、「可視」を格納可能である必要がある。もしｚ−ｍｉｎキャッシュが、１６ビットだとしたら、全ての行タイル情報は、２２×（１６＋１＋１）ビット３９６ビット＝４９．５バイトを利用して形成することが可能である。したがって、行タイル情報は、タイル情報よりもずっと小さく、それはハードウエアオンチップが可能で（can be implemented in hardware on-chip）、速く、エネルギー効率がよいと言うことを意味する。また、行タイル情報は、常にタイルの現在の行に関する情報を保持していることに注意されたい。したがって、最終スキャンラインのあるタイル行から第１スキャンラインの次タイル行に移動する時、行タイル情報とタイル情報がアップデートされる。行タイル情報中のデータに関するアドレスを計算するためには、ピクセルに関するｘ座標だけが必要である。ｙ座標を考える必要が無い理由は、行タイル情報がタイルの１行のみを扱うからである。例えば、もし全ｚ−ｍｉｎキャッシュが、お互いに格納されると、ｘ／８（「／」は整数除算）によってアドレスを計算することが可能である。
【００４４】
（４）  ４つ目に追加としては、ジグザグトラバーサルスキーム、タイル構造、タイル情報メモリ、行タイル情報を利用するｚ−ｍｉｎベースのカリングアルゴリズムがあり、これによってメモリアクセスを少なくすることができる。このアルゴリズムがどのように作動するかについて以下に詳細に説明する。
【００４５】
アルゴリズムを幾つかのステップで説明し、各ステップを前述の説明よりもより詳細に説明する。第１ステップは、三角形がどのようにラタライズされるかを説明し、第２ステップは、スキャンラインがどのようにラタライズされるか説明し、第３ステップと最終ステップは、どのようにピクセルがラタライズされるか（フレームバッファに書かれるか）を説明する。しかし、まずバッファがどのようにクリアされるかについて説明から始める。クリアが、一般的に三角形のラタライゼーション以前に、フレーム毎に少なくとも１度行われるからである。
【００４６】
＜クリアリング＞
全てを描画する前に、Ｚバッファメモリーは、すべての値を予め規定してある値にセットすることによって、クリアされる。たいていこの規定値は、遠点までの距離、ｚ＿ｆａｒである。このシステムでは、ｚ＿ｆａｒを全てのｚ−ｍｉｎ変数に代入することによってタイル情報をもクリアする。また、行タイル情報メモリもクリアする。これは、行タイル情報の全タイルに関し、「参照」フラグを「偽（false）」に設定することで行われる。Ｚバッファとタイル情報を各三角形間ではなくフレーム毎に一度、クリアすることが好ましい点に、注意する。しかし、行タイル情報は、新たなタイル行に行くたびにクリアされ、このことは図２を参照しながら以下により詳しく取り扱う。
【００４７】
＜三角形のラスタライゼーション＞
本発明の実施形態によれば、ラスタライゼーションが、図２の「三角形処理」にしたがって実施可能である。第１に、「参照」フラグは、行タイル情報の全タイル中において偽に設定される（１０１）。そして、１スキャンラインを処理する（１０２）。どのように行われるかは、より詳細に図３を参照にしながら下に説明される。スキャンラインの処理の後、次行が、現在の行と異なったタイルにあるかを確かめる。このことは、例えば
（ｙ＋１）  ｍｏｄ  ｔｉｌｅｓｉｚｅ＝＝０
であるか確かめることによって可能であり、ｙは現在のスキャンライン行であり、ｍｏｄはモジューロ演算子であり、ｔｉｌｅｓｉｚｅはｙ方向におけるタイルサイズである（１０３）。次行が異なったタイル上にある場合、行タイル情報中の情報を行タイル情報に書き戻す必要がある（１０４）。全ての「参照」フラグも偽に設定する（１０５）。このことは、以下のスードコードを利用して実行することができる：
【００４８】
ｆｏｒ  ａｌｌ  ｔｉｌｅｓ  ｉｎ  ｒｏｗｔｉｌｅｉｎｆｏ
｛
ｉｆ  ｖｉｓｉｔｅｄ＝＝ｔｒｕｅ
｛
ｗｒｉｔｅ  ｂａｃｋ  ｚ−ｍｉｎ−ｃａｃｈｅｄ  ｔｏ  ｃｏｒｒｅｓｐｏｎｄｉｎｇ  ｚ−ｍｉｎ  ｉｎ  ｔｉｌｅｉｎｆｏ
｝
ｖｉｓｉｔｅｄ＝ｆａｌｓｅ
｝
【００４９】
上述の方法で行タイル情報とタイル情報をアップデートした後に、ｙ方向に１ピクセルすすめる（１０６）。ｘ方向の移動方向も反転させる（１０７）。三角形の終わりに到着したか否かをテストする（１０８）。もし到着したのであれば、停止し、そうでなければ戻って、次のスキャンラインを処理する（１０２）。
【００５０】
＜スキャンラインの処理＞
図３には、新しいスキャンラインに来た時にどうすべきかが示されている。第１に、三角形の輪郭の外側に出るまで「ｄｉｒ」の逆方向にすすむ（２０１）（既に外であれば本ステップは全く必要が無い）。そして、反対側の三角形の外に完全に到達するまで（２０３）「ｄｉｒ」の方向に１ステップずつすすむ（２０２）。例えば右にすすむ場合、三角形全体が、テストする現在位置の左に位置するまで、右にすすむ必要がある。新しいスキャンラインに到達したばかりなので、一度のステップでは十分でない可能性があり、数ピクセルは三角形の外側に位置しているかもしれない。各ステップに関し、三角形の内側かをテストする（２０４）。内側でなければ、「ｄｉｒ」の方向に、次のステップをすすめる（２０２）。内側であれば、行タイル情報中の対応するタイルに関して参照フラグをチェックする（２０５）。もし参照フラグが偽であれば、そのタイルを参照していない（not yet visited）し、そのタイルに関する行タイル情報中の情報を初期化する必要がある（２０６）。これをどのように行うかは、図４を参照にしながら以下に詳しく説明する。もし参照フラグが真であった場合、行タイル情報の情報が既に最新のものであり、利用可能である。したがって、可視フラグが真か否かをテストする（２０７）。もし可視フラグが真であれば、Ｚバッファを読み込む必要が無く、ピクセルを書き込む高速の方法を利用できる。ここで、この状態を「ライトビジブル」と呼び（２０９）、図５を参照しながら以下により詳細に説明する。参照フラグが偽であった場合、ピクセルをラタライズする通常の方法が利用される。ここで、この状態を「ライトノーマル」と呼び（２０８）、図６を参照しながら以下により詳しく説明される。この後、戻って次のピクセルのすすむ（２０２）。
【００５１】
＜タイルに関する行タイル情報の初期化＞
図４は、どのようにタイルに関する行タイル情報を初期化するかを示している。タイル情報から行タイル情報のｚ−ｍｉｎキャッシュ値にｚ−ｍｉｎ値を読み込むことによって始める（３０１）。その後、三角形が現在のタイル中に仮定できる全ての可能なＺ値よりも大きいか、等しいｚ−ｔｒｉ−ｍａｘと呼ばれる値を計算する（３０２）。ｚ−ｔｒｉ−ｍａｘの１つの計算方法は、ｚ−ｔｒｉ−ｍａｘを三角形の頂点のＺ値の最大とすることである。もし三角形の頂点に関する座標が、（ｘ＿Ａ，ｙ＿Ａ，ｚ＿Ａ），（ｘ＿Ｂ，ｙ＿Ｂ，ｚ＿Ｂ）、（ｘ＿Ｃ，ｙ＿Ｃ，ｚ＿Ｃ）であると、ｚ−ｔｒｉ−ｍａｘは、
ｚ−ｔｒｉ−ｍａｘ＝ｍａｘ（ｚ＿Ａ，ｍａｘ（ｚ＿Ｂ，ｚ＿Ｃ））
で計算可能である。
【００５２】
他の方法としては、ｚ−ｔｒｉ−ｍａｘを、三角形平面がタイル中に仮定できる最大Ｚ値とする。ｚ−ｔｒｉ−ｍａｘを計算した後、ｚ−ｔｒｉ−ｍａｘ＜ｚ−ｍｉｎ−ｃａｃｈｅｄであるかをチェックする（３０３）。成立すれば、タイル内の三角形の全ピクセルが可視（先に描画した要素によって遮蔽されていない（non-occluded））であることは確かであり、したがって、「可視」フラグが真に設定される（３０４）。成立しなければ、「可視」が偽に設定される（３０５）。最後に、行タイリング情報中の対応タイルの「参照」フラグが「真」に設定される（３０６）。
【００５３】
＜「ライトビジブル」−可視であることが知られているピクセルの書き込み＞
図５は、ピクセルに対応する行タイル情報中のタイルに関して「可視」、「参照」のフラグの両方が真である場合に、どのようにピクセルを書き込むかを示す。
【００５４】
「可視」フラグが真である場合、Ｚバッファを読み込むこと無くピクセルを書き込むことが可能である。ピクセルは確実に可視である。しかし、新しいピクセルを描写する場合、現在のｚ−ｍｉｎキャッシュよりも小さなＺ値を有するピクセルを描写することが可能である。したがって、このようにｚ−ｍｉｎキャッシュをアップデートすべきである。まず、ｚ−ｔｒｉ（ｘ，ｙ）を計算して（４０１）、ｚ−ｔｒｉ（ｘ，ｙ）をＺバッファ（奥行バッファ）に書き込み、カラーをカラーバッファに書き込む（４０２）。ここで、（ｘ，ｙ）は、処理したピクセルの座標となる。次に、ｚ−ｔｒｉ（ｘ，ｙ）＜ｚ−ｍｉｎキャッシュであるかをチェックする（４０３）。成立すれば、ｚ−ｍｉｎキャッシュをアップデートする（４０４）。
【００５５】
＜ライトノーマル―「参照」が偽の場合＞
「参照」フラグが真であるが、「可視」フラグが偽である場合、Ｚバッファを読み込み、カラーを設定すべきか否かについて知るべきである。また、ｚ−ｍｉｎキャッシュより小さなＺ値をＺバッファに書き込む場合には、ｚ−ｍｉｎキャッシュをアップデートすべきである。このことは、図６に示されている。第１に、Ｚバッファよりｚ−ｂｕｆを読む（５０１）。そして、ｚ−ｔｒｉ（ｘ，ｙ）を計算する（５０２）。次に、ｚ−ｔｒｉ（ｘ，ｙ）＜ｚ−ｂｕｆ（ｘ，ｙ）であるかをチェックする（５０３）。成立しなければ、ピクセルが可視でないので停止する。成立すれば、ｚ−ｔｒｉ（ｘ，ｙ）をＺバッファに書き込み、カラーをカラーバッファに書き込む。また、ｚ−ｔｒｉ（ｘ，ｙ）＜ｚ−ｍｉｎキャッシュか否かをチェックする（５０５）。成立すれば、ｚ−ｔｒｉ（ｘ，ｙ）で、ｚ−ｍｉｎキャッシュをアップデートすべきである（５０６）。成立しなければ終了し、停止することができる。
【００５６】
＜実施形態の追加説明＞
本発明の更なる側面に基づく一般化された典型的なグラフィック処理工程は、図７で説明されている。タイル行は、グラフィック表示フィールド中に定義され、タイルが複数のピクセル行を含む（７１０）。タイル行中のタイルに関する遮蔽フラグが、代表奥行値が遮蔽基準を満たすか否かを基準として、表示要素に関して設定される、すなわち、上述のように、遮蔽無しまたは遮蔽の可能性があるか否かを示す値が与えられる（７２０）。例えば、遮蔽フラグは、上述のように行タイル情報キャッシュの「ビジビリティ」フラグとなり得る。該フラグは、例えば上述のように、要素（例えば三角形）のｚ−ｍａｘ値と、キャッシュされた遮蔽既定Ｚ値との比較に基づき、設定が可能である。タイル行のピクセルは、遮蔽フラグに応じて、例えば上述のようにジグザグトラバーサルアルゴリズムを用いて、１行ずつ処理される（７３０）。該行の１つ以上のピクセルが処理された後に、遮蔽フラグおよび／または奥行値が、ブロック７２０からブロック７３０へのループバックによって示されるように、更新されるのは良くあるケースであるので、該行の１つのピクセルが処理（例えば、表示）される前に、タイル行に関する全ての遮蔽フラグおよび／または奥行値が設定される必要がある訳ではないことを理解すべきである。上述のように、行ごとの処理は、スキャンラインの処理時に幾つかのタイルを一部参照する結果となり得、通常、要素のジオメトリによるが、他のスキャンラインの次の処理時に幾つかのタイルまたは全タイルを再び参照する結果となり得る。
【００５７】
図８は、本発明の追加の側面に基づく、更に一般化した典型的な工程を説明する図である。グラフィック表示フィールドに複数タイルが定義される（８１０）。遮蔽フラグ（例えば行タイル情報中の「ビジビリティ」フラグ）が、表示要素がタイル中で遮蔽されていないことを示すように、設定される（８２０）。続いて、例えばスキャンライントラバーサルにおけるピクセルの処理中に、ピクセルが置かれるタイルが、遮蔽を行わない旨を示す遮蔽フラグを持っていることを検知する（８３０）。そしてピクセルは、フラグ状況の検知に応じて、処理される（８４０）。例えば、上記の実施形態で議論したように、遮蔽フラグが遮蔽を行わないことを示す場合、ピクセルに関するＺバッファ値を読み取ること無く、ピクセルに関するカラー値とＺ値が、単純にカラーバッファ、Ｚバッファに書き込まれる。上に説明したように、このことが、フレーム処理を行うにあたって、（遅めのオフチップメモリに格納されるであろう）Ｚバッファからの帯域幅の消費を伴う読み出しを縮減する結果となり得る。
【００５８】
図９は、本発明の更なる実施形態による典型的な装置９１０を示し、これによって、図２〜８を参照してここに説明した工程のようなグラフィック処理が実施可能である。ここでは携帯電子機器９００（例えば、携帯無線端末、ＰＤＡまたは類似の装置）に実装された装置９１０は、ディスプレイ９１２と、図２〜８を参照して説明された１つまたは全てのグラフィック処理工程を実装するように構成されるグラフィックプロセッサ９１４とを含む。グラフィックプロセッサ９１４は、例えば、マイクロプロセッサチップ、マイクロコントローラーチップ、デジタルシグナルプロセッサ（ＤＳＰ）チップ、ビデオプロセッサチップ、特定用途向け集積回路（ＡＳＩＣ）に実装された特定用途向けプロセッサ、それらの組み合わせを含むことができる。グラフィックプロセッサ９１４は、更に、グラフィックプロセッサ９１４で実行されると、ここで説明されたグラフィック処理工程を行うように構成される、コンピュータコードを格納するメモリを含む。メモリは、例えば、タイル遮蔽情報キャッシュ（例えば、上述の行タイル情報）を実装するのに利用可能な、マイクロプロセッサ、ＤＳＰ，ビデオプロセッサチップ、またはこれらに類似の演算装置中に内蔵されたオンチップメモリ（例えばキャッシュメモリ）と、このような演算装置と相互作用可能で、表示フィールド中の全データに係わるｚバッファやカラーバッファのような大容量のデータを格納するために利用が可能な独立したメモリ（例えばＤＲＡＭ，ＳＲＡＭ，フラッシュメモリなど）とを含むことが可能である。
【００５９】
本出願において、図２〜９は、本発明の実施形態に基づく典型的な装置と工程を説明する図である。これらの図に示された工程やその組み合わせは、例えば、無線電話やＰＤＡのような携帯電子装置のグラフィック処理回路中の１つ以上の電子回路を利用して実行することが可能であると理解される。一般的に、図に示された工程とその組み合わせは、１つ以上の独立した電子部品、１つ以上の集積回路（ＩＣ）、１つ以上の特定用途向け集積回路（ＡＳＩＣ）、特定用途向け回路モジュールといった１つ以上の電子回路に実装され、マイクロプロセッサ若しくはデジタルシグナルプロセッサ（ＤＳＰ）のようなコンピュータまたは他のデータ処理装置によって実行可能なコンピュータプログラム命令によって実行され、コンピュータまたは他のプログラム可能なデータ処理装置上で実行する命令が、電子回路または特定の工程を実装する他の手段をもたらすような機会を提供する。コンピュータプログラム命令はまた１つ以上のコンピュータまたは他のデータ処理装置上で実行可能であり、コンピュータや他のプログラム可能な装置によって一連の作動を行い、特定工程を含むコンピュータ実装プロセスを提供する。
【００６０】
コンピュータプログラム命令はまた、コンピュータ読取可能な記憶媒体中のコンピュータプログラム製品の形で、即ち命令実行システムによって又は接触して使用される媒体中に含まれたコンピュータ読取可能プログラムコードとして、具体化可能である。コンピュータ読取可能記録媒体には、磁気または光学ディスクまたは集積回路記憶装置等の電子、電磁、光学、または他の記録媒体が含まれるが、これらに限定されない。例えば、コンピュータプログラム命令は、コンピュータのような装置に含まれるメモリに格納される。したがって、図２〜９の図のブロックは、特定工程を実行する電子回路及び他の装置、特定工程を実行する行為、そして特定工程を実行するように構成されたコンピュータプログラム製品を裏付けるものである。
【００６１】
図面と明細書において、本発明の典型的な実施形態が開示された。特定の用語が採用されたが、汎用で、記述的な意味で用いられ、限定をするために用いられたものではない。
【図面の簡単な説明】
【００６２】
【図１】従来のジグザグトラバーサル技術を示す図である。
【図２】本発明の実施形態に基づくグラフィック処理工程と装置の説明図である。
【図３】本発明の実施形態に基づくグラフィック処理工程と装置の説明図である。
【図４】本発明の実施形態に基づくグラフィック処理工程と装置の説明図である。
【図５】本発明の実施形態に基づくグラフィック処理工程と装置の説明図である。
【図６】本発明の実施形態に基づくグラフィック処理工程と装置の説明図である。
【図７】本発明の実施形態に基づくグラフィック処理工程と装置の説明図である。
【図８】本発明の実施形態に基づくグラフィック処理工程と装置の説明図である。
【図９】本発明の更なる実施形態に基づくグラフィック装置を含む典型的な携帯電子機器の説明図である。
【図１】
0004515917.tif 000002
【図２】
0004515917.tif 000003
【図３】
0004515917.tif 000004
【図４】
0004515917.tif 000005
【図５】
0004515917.tif 000006
【図６】
0004515917.tif 000007
【図７】
0004515917.tif 000008
【図８】
0004515917.tif 000009
【図９】
0004515917.tif 000010