３次元画像のレンダリングにおける早期Ｚテスト方法およびシステム
【課題】タイルごとの３次元レンダリングにおいて、ユーザからは見えない３次元モデルの部分に対するラスタライズをタイル単位で省略可能にすることで、レンダリングに必要な演算を簡単化できる早期Ｚテスト方法およびシステムを提供する。
【解決手段】まず、画面を複数のタイルに分割する。次に、レンダリング対象の３次元モデルを構成する複数の三角形の中から一つを選択し、選択された三角形の最小Ｚ値よりタイルＺ値が小さい第１タイルを複数のタイルの中から選別する。続いて、第１タイルを除く残りのタイルにおいて、選択された三角形のレンダリングを行う。各三角形の最小Ｚ値は好ましくは、その三角形の３つの頂点のＺ値の中で最も小さい値に等しい。各タイルのタイルＺ値は好ましくは、そのタイルを完全に含む三角形それぞれの最大Ｚ値の中で最も小さい値に等しい。
【解決手段】まず、画面を複数のタイルに分割する。次に、レンダリング対象の３次元モデルを構成する複数の三角形の中から一つを選択し、選択された三角形の最小Ｚ値よりタイルＺ値が小さい第１タイルを複数のタイルの中から選別する。続いて、第１タイルを除く残りのタイルにおいて、選択された三角形のレンダリングを行う。各三角形の最小Ｚ値は好ましくは、その三角形の３つの頂点のＺ値の中で最も小さい値に等しい。各タイルのタイルＺ値は好ましくは、そのタイルを完全に含む三角形それぞれの最大Ｚ値の中で最も小さい値に等しい。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は３次元画像のレンダリングに関し、特に、隠面消去に利用される早期Ｚテスト方法およびシステムに関する。
【背景技術】
【０００２】
近年、携帯電話、ＰＤＡ、またはナビゲーションシステムなどのモバイル機器の高性能化に伴い、それらの機器の出力に３次元グラフィックが用いられる場合が増えている。３次元グラフィックは２次元グラフィックより表現力が高いので、例えば、操作画面のデザインの更なる多様化や、３次元画像のリアリティを利用した情報伝達力の更なる強化に適している。
【０００３】
３次元グラフィックでは、まず、表現対象の３次元画像が、（モバイル機器等の）画面に表現されるべき仮想的な３次元空間の中にモデル化される（モデリング）。次に、各３次元モデルが、ユーザの視点からの位置に基づき、仮想的な３次元空間から２次元画面に投影され、得られた２次元画像が画面に再現される（レンダリング）。ここで、３次元モデルは一般にベクトルデータで表されている。従って、３次元モデルを２次元画面に投影する過程では、ベクトルデータが画面の各ピクセルの輝度データとＺ値（そのピクセルに投影された３次元モデルの一点の、視点からの仮想的な距離）とに変換される（この変換処理をラスタライズと称する）。各ピクセルの輝度データとＺ値とはフレームバッファに格納される。ここで、フレームバッファのうち、輝度データの格納部分をカラーバッファと称し、Ｚ値の格納部分をＺバッファと称する。
【０００４】
３次元モデルが複数の三角形で表現されている場合、従来のレンダリングでは、まず、ラスタライズがそれらの三角形の全てについて行われ、その後、画面への描画が開始される。従って、カラーバッファとＺバッファとのそれぞれのサイズが画面の解像度と同じでなければならない。そのように大きなサイズのフレームバッファを３次元グラフィックの処理回路と同じチップの内部に埋め込むことは決して容易ではない。それ故、従来のグラフィックシステムでは一般に、フレームバッファが外部メモリに設定されている。その場合、一つのピクセルについて輝度データとＺ値とが決定されるごとに外部メモリがアクセスされる。ここで、外部メモリへのアクセスはチップ内部のメモリへのアクセスに比べて約10倍の電力を消耗する。特にモバイル機器では更なる省電力化が強く望まれているので、モバイル機器における３次元グラフィックシステムの利用では、外部メモリへのアクセスの効率化が大きな課題となっている。
【０００５】
外部メモリへのアクセスを効率良く行うための技術としては、タイルごとの３次元画像のレンダリング方法が開発されている。その方法では、まず、画面が複数のタイルに分割される。次に、３次元モデルを表す三角形のいずれかと一部でも重なっているタイルが選択される。続いて、選択されたタイルごとにラスタライズが行われる。このとき、各ピクセルの輝度データとＺ値とは一旦、３次元グラフィックシステムの処理回路が実装されたチップの内部に埋め込まれているメモリに保持される。ここで、そのメモリのサイズはタイル一枚当たりの解像度と等しければ良い。一枚のタイルに対するラスタライズが完了するごとに、そのメモリに保持されているデータがバーストモードで外部のフレームバッファに一挙に送信される。このように、外部メモリへのアクセス（書き込み）をタイル単位で行うことで、３次元グラフィックシステムの消費電力を更に低減できる。
【０００６】
ラスタライズによって画面の同じ位置（ピクセル）に複数の輝度データが設定された場合、ユーザから見て画面のその位置で複数の三角形が重なっている。その場合、それらの三角形を画面に表示するとき、ユーザの視点に最も近い三角形の部分だけを画面に表示し、その部分に重なっている他の三角形の部分を隠さねばならない（隠面消去）。例えば図1に示されているように、仮想的な３次元空間に、ユーザの視点110から近い順に４つの三角形131〜134が存在しているときを想定する。第１三角形131はユーザの視点110に最も近いので、その全体が視点110から見える。第２三角形132の上の部分は第１三角形131によって隠されているので、第２三角形132の下の部分だけが視点110から見える。第３三角形133は第１三角形131および第２三角形132によって完全に隠されているので、第３三角形133は視点110からは見えない。第４三角形134は、他の三角形131〜133によって隠されていない上の部分だけが視点110から見える。
【０００７】
このような隠面消去には、次のようなＺテスト方法が利用される。まず、仮想的な３次元空間内での各三角形131〜134の視点110からの距離（深さ）をＺ値として表わす。ここで、仮想的な３次元空間には一般に、画面に平行な方向にＸ軸とＹ軸とが設定され、画面と直交する方向にＺ軸が設定される。その場合、Ｚ値はＺ軸方向の座標値を表す。図1にはＺ軸が破線120で示されている。図1では、第１三角形131から第４三角形134の順にＺ値が大きくなっている。次に、それらの三角形131〜134が重なっている画面の領域に含まれている各ピクセルのＺ値を、そのピクセルに投影された各三角形131〜134のＺ値のうち、最小のものに設定する。更に、各ピクセルの輝度データを、そのピクセルのＺ値の示す三角形に基づいて決定する。こうして、各ピクセルの輝度データが、視点110から最も近い三角形に基づいて決定される。それにより、ユーザから見えるべきではない三角形の部分が画面には表示されない。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
レンダリング対象の３次元モデルを表すベクトルデータが全て２次元画面（又は、その中の一枚のタイル）の各ピクセルの輝度データに変換された後に、すなわち、レンダリング対象の３次元モデル全てのラスタライズが終わった後に、従来のＺテスト方法は行われる。しかし、その場合、最終的には他の３次元モデル（三角形）に隠されて見えない３次元モデル（三角形）の部分に対してもラスタライズが行われる。それにより、グラフィック処理全体の演算量の更なる削減、及びそれによるグラフィック処理の更なる高速化が困難である。
【０００９】
本発明は、複数の三角形で表現される３次元モデルをタイルごとにレンダリングする方法において、他の三角形によって隠されてユーザからは見えない三角形の部分に対するラスタライズをタイル単位で省略可能にすることで、レンダリングに必要な演算を更に簡単化し、それによる更なる省電力化及び更なる高速化を共に実現できる早期Ｚテスト方法およびシステムの提供を目的とする。
【課題を解決するための手段】
【００１０】
本発明による早期Ｚテスト方法は、複数の三角形で表現される３次元画像のレンダリングを行うための方法であり、以下の段階を順に有する：画面を複数のタイルに分割する段階；複数の三角形の中から一つを選択し、選択された三角形の最小Ｚ値よりタイルＺ値が小さい第１タイルを複数のタイルの中から選別する段階；及び、第１タイルを除く残りのタイルにおいて、上記の選択された三角形のレンダリングを行う段階。ここで、各三角形の最小Ｚ値は好ましくは、その三角形の３つの頂点のＺ値の中で最も小さい値に等しい。一方、各タイルのタイルＺ値は、そのタイルに含まれている各ピクセルに共通に与えられたＺ値であり、好ましくは、そのタイルを完全に含む三角形それぞれの最大Ｚ値の中で最も小さい値に等しい。
【００１１】
本発明によるこの早期Ｚテスト方法は好ましくは、次のような早期Ｚテストシステムによって実行される。そのシステムは、画面を複数のタイルに分割するタイル分割部；複数の三角形の中から一つを選択し、選択された三角形の最小Ｚ値よりタイルＺ値が小さい第１タイルを選別するタイル選別部；及び、第１タイルを除く残りのタイルにおいて上記の選択された三角形のレンダリングを行うレンダリング実行部；を有する。このシステムは更に好ましくは、次のようなタイルＺ値更新部を更に有する。タイルＺ値更新部は、タイル選別部によって選択された三角形に完全に含まれる第２タイルを複数のタイルの中から選別し、第２タイルのタイルＺ値より上記の選択された三角形の最大Ｚ値が小さい場合、その第２タイルのタイルＺ値を上記の選択された三角形の最大Ｚ値に更新する。
【発明の効果】
【００１２】
本発明による早期Ｚテスト方法では、各三角形のレンダリング（特にラスタライズ）の前に第１タイルが選別され、第１タイルについてはその三角形のレンダリングが省略される。それにより、レンダリングに必要な演算量が低減するので、レンダリングに伴う消費電力が削減され、かつレンダリングが高速化される。従って、本発明による早期Ｚテスト方法は特に、モバイル機器での利用や３次元グラフィックによる動画処理に適している。
【発明を実施するための最良の形態】
【００１３】
以下、添付の図面に基づき、本発明の好適な実施の形態を詳細に説明する。
本発明の一実施形態による早期Ｚテスト方法は、複数の三角形で表現される３次元モデルをタイルごとにレンダリングを行う場合に、ユーザの視点からは他の三角形に隠されて見えない三角形の部分をタイル単位でレンダリングの対象から除くことを可能にする。例えば図2の(a)に示されているように、画面上で、第２三角形212と重なっているタイル213が第１三角形211に完全に含まれている場合、第２三角形212が第１三角形211の後ろに位置するときは、タイル213においては第２三角形212のレンダリングが省略される。タイル213に重なっている第２三角形212の部分は、それよりも前に存在する第１三角形211に隠されてユーザの視点からは見えないので、タイル213において第２三角形212のレンダリングが省略されても、画面に実際に表示される画像は影響を受けない。このように、実際には画面に表示されない三角形の部分をレンダリングの対象から予め排除することにより、レンダリングの作業効率を高めることができる。
【００１４】
一方、図2の(b)に示されている画面では、第１三角形221にタイル223の一部のみが重なっている。すなわち、図2の(a)に示されているタイル213とは異なり、タイル223の全体が第１三角形221に含まれてはいない。その場合、第２三角形222が第１三角形221の後ろに位置するときでも、「タイル223に重なっている第２三角形222の部分がユーザの視点からは第１三角形221に隠されて見えない」という保証はない。実際、図2の(b)では、タイル223と重なっている第２三角形222の一部には、第１三角形221に隠されている部分と第１三角形221に隠されていない部分とがいずれも存在する。従って、画面に投影されたある三角形の内部に全体が含まれているタイルに限り、そのタイルに重なっている、その三角形より後に位置する他の三角形のレンダリングを省略することができる。
【００１５】
図3に、本発明の一実施形態による早期Ｚテスト方法のフローチャートを示す。図3に示されているように、第１段階S301では、画面を複数のタイルに分割する。各タイルは好ましくは所定のサイズ及び所定の形状（更に好ましくは矩形）に統一されている。３次元モデルのレンダリングはタイルごとに行う。例えば、解像度640×480の画面を解像度32×32のタイルに分割する場合、20×15＝300枚のタイルのそれぞれでレンダリングを行う。特にレンダリングの対象のサイズが画面より小さい場合、その対象が重なっているタイルについてのみ、その対象のレンダリングが行われれば十分である。その結果、画面全体でレンダリングを行う場合より、レンダリングに必要な演算量を大幅に節減できる。
【００１６】
第２段階S302においては、まず、複数の三角形の中から一つを選択する。次に、複数のタイルの中から、選択された三角形の最小Ｚ値よりタイルＺ値が小さいタイル（以下、第１タイルという）を選別する。
ここで、三角形の最小Ｚ値は、その三角形の３つの頂点のＺ値のうち、最も小さなＺ値に等しい。すなわち、三角形の３つの頂点のうち、ユーザの視点に最も近い頂点のＺ値がその三角形の最小Ｚ値として採用される。三角形は平面であり、その各辺はいずれも直線である。従って、三角形に含まれている各点のＺ値は必ず、その三角形の最小Ｚ値以上である。
【００１７】
各タイルのタイルＺ値は好ましくは、そのタイルを完全に含む三角形それぞれの最大Ｚ値の中で最も小さい値に等しい。ここで、三角形の最大Ｚ値は、その三角形の各頂点のＺ値のうち最も大きい値に等しい。すなわち、ユーザの視点から最も遠い頂点のＺ値がその三角形の最大Ｚ値として採用される。三角形に含まれている各点のＺ値は必ず、その三角形の最大Ｚ値以下である。従って、各タイルのタイルＺ値は、そのタイルを完全に含む各三角形に含まれているユーザの視点から最も遠い点の中で、ユーザの視点に最も近い点のＺ値に等しい。あるタイルが、画面に投影されたある三角形に完全に含まれている場合、そのタイル内においては、その三角形の最大Ｚ値より大きいＺ値の点が、ユーザの視点からはその三角形に隠されて見えない。一方、画面上でそのタイルを完全に含む三角形が複数個存在する場合、そのタイル内では、最大Ｚ値の最も小さい三角形の部分がユーザの視点に最も近い。従って、ユーザの視点からは他の三角形の部分がその三角形の部分に隠されて見えない。第１タイルでは、選択された三角形の最小Ｚ値（すなわち、その三角形に含まれている点の中で、ユーザの視点に最も近い点のＺ値）よりタイルＺ値が小さい。それ故、第１タイルを完全に含む三角形の中に、選択された三角形を第１タイルの内部では隠す三角形が存在する。
【００１８】
第２段階S302では好ましくは、各タイルのタイルＺ値を次のように更新する。まず、選択された三角形（より正確には、それから画面に投影された三角形。以下、同様。）に完全に含まれているタイル（以下、第２タイルという）を選別する。その三角形に完全に含まれていないタイルでは、「その三角形が、その三角形の最大Ｚ値より最大Ｚ値が大きい他の三角形を隠している」という保証はないからである。次に、各第２タイルのタイルＺ値を選択された三角形の最大Ｚ値と比較する。そのタイルＺ値がその最大Ｚ値より大きい場合、そのタイルＺ値をその最大Ｚ値に更新する。
【００１９】
第２タイルの選別では好ましくは、まず、ハーフプレーンエッジ関数を用い、各タイルのタイルノードの判別値を決定する。ここで、各タイルのタイルノードは好ましくは、そのタイルの頂点である。タイルノードの判別値は、画面に投影された三角形に対するそのタイルノードの位置を表す。好ましくは、各タイルノードの判別値は、第１判別値、第２判別値、および第３判別値を含む。第１判別値、第２判別値、および第３判別値はそれぞれ、三角形の第１辺、第２辺、および第３辺のそれぞれに対するハーフプレーンエッジ関数値の符号に基づいて決められる。好ましくは、ハーフプレーンエッジ関数値が正数である場合には各判別値が1に決められ、負数または0である場合には0に決められる。尚、この場合分けとは異なる場合分けが行われても良い。
【００２０】
ハーフプレーンエッジ関数は、２次元画面上での直線と点との間の位置関係を表わす関数である。好ましくは、対象の直線の始点と終点との各座標を（x0、y0）、（x1、y1）とし、対象の点の座標を（x、y）とすると、ハーフプレーンエッジ関数値E(x、y)は次式によって定義される。
【００２１】
E(x、y)＝(x−x0)×Δy−(y−y0)×Δx。ここで、Δx＝x1−x0、Δy＝y1−y0。
【００２２】
ハーフプレーンエッジ関数値E(x、y)は、点が直線の左側にある場合には負であり、直線の右側にある場合には正である。第２タイルの選別においては、２次元画面に投影された三角形の各辺が上記の直線として設定され、タイルノードが上記の点として設定される。ここで、ユーザの視点から見て、その三角形の周に沿って時計回りに回転する方向をその三角形の各辺の方向とし、その方向に基づいて各辺の始点と終点とを決める。尚、各辺の方向はその他にも変更可能である。しかし、三角形の内部に存在するタイルノードの第１判別値、第２判別値、および第３判別値に同じ値を持たせるには、三角形の各辺の方向が循環するように決められねばならない。
【００２３】
第２タイルの選別では次に、各タイルのタイルノードの判別値を以下のように用い、「そのタイルが選択された三角形の内部に完全に含まれているかどうか」を確認する。図6に示されているように、その三角形の各辺の方向が時計回りに設定されている場合、各辺に対するハーフプレーンエッジ関数値は、三角形の内部610に含まれている点ではいずれも正である。一方、三角形の外部620、630、および640に含まれている点では、少なくともいずれか一つの辺に対するハーフプレーンエッジ関数値が負である。従って、あるタイルノードの第１判別値、第２判別値、および第３判別値がいずれも1である場合、対応するハーフプレーンエッジ関数値の符号がいずれも正であるので、「そのタイルノードは三角形の内部に含まれている」と判別される。更に、タイルノードが矩形状のタイルの４つの頂点である場合、全てのタイルノードが三角形の内部に含まれていれば、「そのタイルの全体がその三角形の内部に含まれている」と判別できる。
【００２４】
尚、各タイルのタイルノードのハーフプレーンエッジ関数値を用いると、画面に投影されたある三角形と一部でも重なっているタイルを識別できる（タイルビニング（tile binning））。従って、第２タイルの選別段階で計算されたハーフプレーンエッジ関数値をタイルビニングにも利用することで、レンダリング全体での計算量を低減し、かつレンダリングの処理時間を短縮できる。
【００２５】
第３段階S303においては、第２段階S302で選択された三角形のレンダリングを、第１タイルを除く残りのタイルでのみ行う。第１タイルではその三角形が他の三角形に隠されて見えないので、第１タイルではその三角形のレンダリングが行われなくても、画面に実際に表示される画像には影響がない。こうして、第１タイルでのレンダリングを省略することにより、選択された三角形のレンダリングをより効率よく行うことができる。
【００２６】
尚、第１タイルとは異なるタイルでも、第２段階S302で選択された三角形の部分が他の三角形に隠されて見えないことがある。従って、従来のレンダリング方法と同様に、選択された三角形のレンダリングの終了時にＺテストを行う必要がある。しかし、従来のレンダリング方法とは異なり、確実に除去可能なタイルが第１タイルとして予め除去されている。それ故、レンダリングの終了時のＺテストに必要な演算量は従来のレンダリング方法での演算量より顕著に少ない。
【００２７】
例えば、仮想的な３次元空間内に、図4に示されている、第１三角形410、第２三角形430、および第３三角形440しか存在しない場合、上記の方法では、それらのレンダリングを以下のように行う。
【００２８】
まず、第１三角形410に対してタイルごとのレンダリングを、第２段階S302、第３段階S303の順で行う。第２段階S302では、第１三角形410と重なっているタイルをすべて選別し、選別された各タイルのタイルＺ値を第１三角形410の最小Ｚ値と比較する。ここで、レンダリング済みの三角形がまだないので、第３段階S303では、第２段階S302で選別されたすべてのタイルにおいて第１三角形410のレンダリングを行うべきである。従って、好ましくは、各タイルのタイルＺ値の初期値がＺ値の上限（すなわち、仮想的な３次元空間内でユーザの視点から最も遠い点のＺ値）に設定されている。その他に、「まだ一度も更新されたことがない」という旨を示す特定の値が初期値として設定されていても良い。それにより、第２段階S302で選別されたすべてのタイルでタイルＺ値が第１三角形410の最小Ｚ値以上である。従って、第１三角形410については第１タイルが一枚も選別されない。それ故、第３段階S303では、第２段階S302で選別されたすべてのタイルで第１三角形410のレンダリングが行われる。
第２段階S302では更に、第１三角形410に完全に含まれている第２タイル群420が選別され、それらの各タイルＺ値が第１三角形410の最大Ｚ値に更新される。
【００２９】
次に、第２三角形430に対してタイルごとのレンダリングを、第２段階S302、第３段階S303の順で行う。第２段階S302では、第２三角形430と重なっているタイルを選別し、それらのタイルＺ値を第２三角形430の最小Ｚ値と比較する。ここで、図4に示されているように、画面上では第２三角形430が第１三角形410の内部に完全に含まれている。従って、第２三角形430の最小Ｚ値が第１三角形410の最大Ｚ値より大きい場合、ユーザの視点からは第２三角形430は第１三角形410に隠されて見えない。実際、この場合、第３段階S303では第２三角形430のレンダリングが次のように省略される。第２段階S302で選別される、第２三角形430と重なっているタイルはいずれも、第１三角形410に対する第２タイル群420に含まれている。従って、それらのタイルのタイルＺ値はいずれも第１三角形410の最大Ｚ値と等しいので、第２三角形430の最小Ｚ値より小さい。その結果、それらのタイルはいずれも第１タイルとして選別されるので、第３段階S303ではそれらのタイルにおける第２三角形430のレンダリングが省略される。
【００３０】
最後に、第３三角形440に対してタイルごとのレンダリングを、第２段階S302、第３段階S303の順で行う。第２段階S302では、第３三角形440と重なっている7枚のタイルA〜Gを選別し、それらのタイルＺ値を第３三角形440の最小Ｚ値と比較する。ここで、図4に示されているように、画面上では第３三角形430の一部が第１三角形410に重なり、更に第１三角形410に対する第２タイル群420に含まれている３つのタイルA、B、Cに重なっている。それらのタイルA〜CではタイルＺ値が更新されているが、残りのタイルD〜GではタイルＺ値が初期値のままである。従って、第３三角形430の最小Ｚ値が第１三角形410の最大Ｚ値より大きい場合、第３三角形440の最小Ｚ値よりタイルＺ値が、前者のタイルA〜Cでは小さく、後者のタイルD〜Gでは大きい。その結果、第３段階S303では第３三角形430のレンダリングが、第２タイル群420に含まれているタイルA〜Cについては省略され、その他のタイルD〜Gについてのみ行われる。
【００３１】
例えば図5に示されているように、4×4のタイルのマトリックスについて三角形510のレンダリングを行う場合は以下の通りである。ここで、図5では、マトリックスの縦横にタイルの行番号1〜4と列符号a〜dとが付記され、各タイルの中に各タイルのタイルＺ値が示されている。更に、三角形510の最小Ｚ値を5とする。
【００３２】
第２段階S302では、まず、三角形510と重なっているタイルを選別する。これにより、2−c、2−d、3−b、3−c、3−d、4−b、4−c、4−dの8枚のタイルが選別される。次に、選別された各タイルのタイルＺ値を三角形510の最小Ｚ値と比較し、タイルＺ値が三角形510の最小Ｚ値より小さいタイルを第１タイルとして選別する。これにより、3枚のタイル3−b、3−c、4−bが第１タイルとして選別される。第１タイルでは、タイルＺ値が三角形510の最小Ｚ値より小さいので、三角形510が別の三角形に隠されて画面には表示されない。第３段階S303では、3枚の第１タイル3−b、3−c、4−bを除く残り5枚のタイル2−c、2−d、3−d、4−c、4−dに対してのみ三角形510のレンダリングを行う。こうして、ユーザの視点からは見えない部分を除いて効率よくレンダリングを行うことができる。
尚、「5枚のタイル2−c、2−d、3−d、4−c、4−dに重なっている三角形510の部分のいずれもが必ず画面に表示される」とは限らないので、レンダリングの終了時には、ピクセル単位のＺテストを別に行うことが好ましい。
【００３３】
以上のように、本発明の上記の実施形態による早期Ｚテスト方法では、ある三角形に完全に含まれているタイルでその三角形に隠されている別の三角形の部分のレンダリングがそのタイルについては省略される。それにより、レンダリングを効率よく行うことができる。
【００３４】
本発明の上記の実施形態による早期Ｚテスト方法は好ましくは、図7に示されているシステムによって行われる。図7に示されているように、本発明の一実施形態による早期Ｚテストシステム701は、タイル分割部710、タイル選別部720、レンダリング実行部730、およびタイルＺ値更新部740を備えている。ここで、各構成要素は、ソフトウェア、ハードウェア、または、それらの組み合わせのいずれによっても実現可能である。
【００３５】
タイル分割部710は、上記の第１段階S301で画面を複数のタイルに分割する。
タイル選別部720は、上記の第２段階S302で、複数のタイルの中から、特定の三角形の最小Ｚ値よりタイルＺ値が小さいタイル（すなわち、第１タイル）を選別する。
レンダリング実行部730は、上記の第３段階S303で、タイル選別部720によって選別された第１タイルを除く残りのタイルにおいて、特定の三角形に対するレンダリングを行う。
タイルＺ値更新部740は、上記の第２段階S302で、まず、複数のタイルの中から特定の三角形に完全に含まれているタイル（すなわち、第２タイル）を選別する。次に、各第２タイルのタイルＺ値を選択された三角形の最大Ｚ値と比較する。そのタイルＺ値がその三角形の最大Ｚ値より大きい場合、そのタイルＺ値をその三角形の最大Ｚ値に更新する。
【００３６】
本発明の上記の実施形態による早期Ｚテスト方法は好ましくは、コンピュータにより所定のプログラムに従って実行される。更に好ましくは、コンピュータがそのプログラムに従い、図7に示されている各構成要素として機能する。そのプログラムは好ましくは、コンピュータ読み取り可能な記録媒体に保管されている。ここで、その記録媒体は、プログラム命令、データファイル、データ構造などを含む。更に、そのプログラムは、その全体が特別に設計されたものでも良く、当業者にとって公知なモジュール等の組み合わせから構成されたものであっても良い。コンピュータ読み取り可能な記録媒体の例としては、ハードディスク、フロッピーディスク（登録商標）、および磁気テープのような磁気媒体、ＣＤ−ＲＯＭやＤＶＤのような光記録媒体、フロプティカルディスク（登録商標）のような光磁気記録媒体、並びに、ＲＯＭ、ＲＡＭ、フラッシュメモリなどのような半導体メモリが含まれる。プログラム命令の例としては、コンパイラによって生成される機械語コードだけでなく、インタプリタなどを用いてコンピュータによって実行される高級言語コードを含む。
【００３７】
以上、本発明の好ましい実施形態を説明した。しかし、当業者にとっては、特許請求の範囲に記載された本発明の思想および領域から逸脱しない範囲内で、本発明の上記の実施形態を多様に修正し、又は変更可能であろう。従って、本発明の技術的範囲は上記の実施形態にのみ制限されるべきではなく、特許請求の範囲に基づき、上記の修正や変更を受けた実施形態をも含むように定められるべきである。
【図面の簡単な説明】
【００３８】
【図１】仮想的な３次元空間内に配置された４つの三角形のＺ軸方向での配置を示す模式図
【図２】レンダリング対象の２つの三角形とタイルとの間の、画面上での位置関係を例示する模式図
【図３】本発明の一実施形態による早期Ｚテスト方法のフローチャート
【図４】本発明の一実施形態による早期Ｚテスト方法において、画面に投射されたレンダリング対象の３つの三角形と、その画面にマトリックス状に配置されたタイルとの間の位置関係を示す模式図
【図５】本発明の一実施形態による早期Ｚテスト方法において、画面に投射されたレンダリング対象の別の三角形と、その画面にマトリックス状に配置されたタイルとの間の位置関係を示す模式図
【図６】本発明の一実施形態による早期Ｚテスト方法において、画面に投射された三角形の内外の領域別に、その三角形の各辺に対するハーフプレーンエッジ関数値の符号を示す模式図
【図７】本発明の一実施形態による早期Ｚテストシステムのブロック図
【符号の説明】
【００３９】
701 早期Ｚテストシステム
710 タイル分割部
720 タイル選別部
730 レンダリング実行部
740 タイルＺ値更新部
【技術分野】
【０００１】
本発明は３次元画像のレンダリングに関し、特に、隠面消去に利用される早期Ｚテスト方法およびシステムに関する。
【背景技術】
【０００２】
近年、携帯電話、ＰＤＡ、またはナビゲーションシステムなどのモバイル機器の高性能化に伴い、それらの機器の出力に３次元グラフィックが用いられる場合が増えている。３次元グラフィックは２次元グラフィックより表現力が高いので、例えば、操作画面のデザインの更なる多様化や、３次元画像のリアリティを利用した情報伝達力の更なる強化に適している。
【０００３】
３次元グラフィックでは、まず、表現対象の３次元画像が、（モバイル機器等の）画面に表現されるべき仮想的な３次元空間の中にモデル化される（モデリング）。次に、各３次元モデルが、ユーザの視点からの位置に基づき、仮想的な３次元空間から２次元画面に投影され、得られた２次元画像が画面に再現される（レンダリング）。ここで、３次元モデルは一般にベクトルデータで表されている。従って、３次元モデルを２次元画面に投影する過程では、ベクトルデータが画面の各ピクセルの輝度データとＺ値（そのピクセルに投影された３次元モデルの一点の、視点からの仮想的な距離）とに変換される（この変換処理をラスタライズと称する）。各ピクセルの輝度データとＺ値とはフレームバッファに格納される。ここで、フレームバッファのうち、輝度データの格納部分をカラーバッファと称し、Ｚ値の格納部分をＺバッファと称する。
【０００４】
３次元モデルが複数の三角形で表現されている場合、従来のレンダリングでは、まず、ラスタライズがそれらの三角形の全てについて行われ、その後、画面への描画が開始される。従って、カラーバッファとＺバッファとのそれぞれのサイズが画面の解像度と同じでなければならない。そのように大きなサイズのフレームバッファを３次元グラフィックの処理回路と同じチップの内部に埋め込むことは決して容易ではない。それ故、従来のグラフィックシステムでは一般に、フレームバッファが外部メモリに設定されている。その場合、一つのピクセルについて輝度データとＺ値とが決定されるごとに外部メモリがアクセスされる。ここで、外部メモリへのアクセスはチップ内部のメモリへのアクセスに比べて約10倍の電力を消耗する。特にモバイル機器では更なる省電力化が強く望まれているので、モバイル機器における３次元グラフィックシステムの利用では、外部メモリへのアクセスの効率化が大きな課題となっている。
【０００５】
外部メモリへのアクセスを効率良く行うための技術としては、タイルごとの３次元画像のレンダリング方法が開発されている。その方法では、まず、画面が複数のタイルに分割される。次に、３次元モデルを表す三角形のいずれかと一部でも重なっているタイルが選択される。続いて、選択されたタイルごとにラスタライズが行われる。このとき、各ピクセルの輝度データとＺ値とは一旦、３次元グラフィックシステムの処理回路が実装されたチップの内部に埋め込まれているメモリに保持される。ここで、そのメモリのサイズはタイル一枚当たりの解像度と等しければ良い。一枚のタイルに対するラスタライズが完了するごとに、そのメモリに保持されているデータがバーストモードで外部のフレームバッファに一挙に送信される。このように、外部メモリへのアクセス（書き込み）をタイル単位で行うことで、３次元グラフィックシステムの消費電力を更に低減できる。
【０００６】
ラスタライズによって画面の同じ位置（ピクセル）に複数の輝度データが設定された場合、ユーザから見て画面のその位置で複数の三角形が重なっている。その場合、それらの三角形を画面に表示するとき、ユーザの視点に最も近い三角形の部分だけを画面に表示し、その部分に重なっている他の三角形の部分を隠さねばならない（隠面消去）。例えば図1に示されているように、仮想的な３次元空間に、ユーザの視点110から近い順に４つの三角形131〜134が存在しているときを想定する。第１三角形131はユーザの視点110に最も近いので、その全体が視点110から見える。第２三角形132の上の部分は第１三角形131によって隠されているので、第２三角形132の下の部分だけが視点110から見える。第３三角形133は第１三角形131および第２三角形132によって完全に隠されているので、第３三角形133は視点110からは見えない。第４三角形134は、他の三角形131〜133によって隠されていない上の部分だけが視点110から見える。
【０００７】
このような隠面消去には、次のようなＺテスト方法が利用される。まず、仮想的な３次元空間内での各三角形131〜134の視点110からの距離（深さ）をＺ値として表わす。ここで、仮想的な３次元空間には一般に、画面に平行な方向にＸ軸とＹ軸とが設定され、画面と直交する方向にＺ軸が設定される。その場合、Ｚ値はＺ軸方向の座標値を表す。図1にはＺ軸が破線120で示されている。図1では、第１三角形131から第４三角形134の順にＺ値が大きくなっている。次に、それらの三角形131〜134が重なっている画面の領域に含まれている各ピクセルのＺ値を、そのピクセルに投影された各三角形131〜134のＺ値のうち、最小のものに設定する。更に、各ピクセルの輝度データを、そのピクセルのＺ値の示す三角形に基づいて決定する。こうして、各ピクセルの輝度データが、視点110から最も近い三角形に基づいて決定される。それにより、ユーザから見えるべきではない三角形の部分が画面には表示されない。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
レンダリング対象の３次元モデルを表すベクトルデータが全て２次元画面（又は、その中の一枚のタイル）の各ピクセルの輝度データに変換された後に、すなわち、レンダリング対象の３次元モデル全てのラスタライズが終わった後に、従来のＺテスト方法は行われる。しかし、その場合、最終的には他の３次元モデル（三角形）に隠されて見えない３次元モデル（三角形）の部分に対してもラスタライズが行われる。それにより、グラフィック処理全体の演算量の更なる削減、及びそれによるグラフィック処理の更なる高速化が困難である。
【０００９】
本発明は、複数の三角形で表現される３次元モデルをタイルごとにレンダリングする方法において、他の三角形によって隠されてユーザからは見えない三角形の部分に対するラスタライズをタイル単位で省略可能にすることで、レンダリングに必要な演算を更に簡単化し、それによる更なる省電力化及び更なる高速化を共に実現できる早期Ｚテスト方法およびシステムの提供を目的とする。
【課題を解決するための手段】
【００１０】
本発明による早期Ｚテスト方法は、複数の三角形で表現される３次元画像のレンダリングを行うための方法であり、以下の段階を順に有する：画面を複数のタイルに分割する段階；複数の三角形の中から一つを選択し、選択された三角形の最小Ｚ値よりタイルＺ値が小さい第１タイルを複数のタイルの中から選別する段階；及び、第１タイルを除く残りのタイルにおいて、上記の選択された三角形のレンダリングを行う段階。ここで、各三角形の最小Ｚ値は好ましくは、その三角形の３つの頂点のＺ値の中で最も小さい値に等しい。一方、各タイルのタイルＺ値は、そのタイルに含まれている各ピクセルに共通に与えられたＺ値であり、好ましくは、そのタイルを完全に含む三角形それぞれの最大Ｚ値の中で最も小さい値に等しい。
【００１１】
本発明によるこの早期Ｚテスト方法は好ましくは、次のような早期Ｚテストシステムによって実行される。そのシステムは、画面を複数のタイルに分割するタイル分割部；複数の三角形の中から一つを選択し、選択された三角形の最小Ｚ値よりタイルＺ値が小さい第１タイルを選別するタイル選別部；及び、第１タイルを除く残りのタイルにおいて上記の選択された三角形のレンダリングを行うレンダリング実行部；を有する。このシステムは更に好ましくは、次のようなタイルＺ値更新部を更に有する。タイルＺ値更新部は、タイル選別部によって選択された三角形に完全に含まれる第２タイルを複数のタイルの中から選別し、第２タイルのタイルＺ値より上記の選択された三角形の最大Ｚ値が小さい場合、その第２タイルのタイルＺ値を上記の選択された三角形の最大Ｚ値に更新する。
【発明の効果】
【００１２】
本発明による早期Ｚテスト方法では、各三角形のレンダリング（特にラスタライズ）の前に第１タイルが選別され、第１タイルについてはその三角形のレンダリングが省略される。それにより、レンダリングに必要な演算量が低減するので、レンダリングに伴う消費電力が削減され、かつレンダリングが高速化される。従って、本発明による早期Ｚテスト方法は特に、モバイル機器での利用や３次元グラフィックによる動画処理に適している。
【発明を実施するための最良の形態】
【００１３】
以下、添付の図面に基づき、本発明の好適な実施の形態を詳細に説明する。
本発明の一実施形態による早期Ｚテスト方法は、複数の三角形で表現される３次元モデルをタイルごとにレンダリングを行う場合に、ユーザの視点からは他の三角形に隠されて見えない三角形の部分をタイル単位でレンダリングの対象から除くことを可能にする。例えば図2の(a)に示されているように、画面上で、第２三角形212と重なっているタイル213が第１三角形211に完全に含まれている場合、第２三角形212が第１三角形211の後ろに位置するときは、タイル213においては第２三角形212のレンダリングが省略される。タイル213に重なっている第２三角形212の部分は、それよりも前に存在する第１三角形211に隠されてユーザの視点からは見えないので、タイル213において第２三角形212のレンダリングが省略されても、画面に実際に表示される画像は影響を受けない。このように、実際には画面に表示されない三角形の部分をレンダリングの対象から予め排除することにより、レンダリングの作業効率を高めることができる。
【００１４】
一方、図2の(b)に示されている画面では、第１三角形221にタイル223の一部のみが重なっている。すなわち、図2の(a)に示されているタイル213とは異なり、タイル223の全体が第１三角形221に含まれてはいない。その場合、第２三角形222が第１三角形221の後ろに位置するときでも、「タイル223に重なっている第２三角形222の部分がユーザの視点からは第１三角形221に隠されて見えない」という保証はない。実際、図2の(b)では、タイル223と重なっている第２三角形222の一部には、第１三角形221に隠されている部分と第１三角形221に隠されていない部分とがいずれも存在する。従って、画面に投影されたある三角形の内部に全体が含まれているタイルに限り、そのタイルに重なっている、その三角形より後に位置する他の三角形のレンダリングを省略することができる。
【００１５】
図3に、本発明の一実施形態による早期Ｚテスト方法のフローチャートを示す。図3に示されているように、第１段階S301では、画面を複数のタイルに分割する。各タイルは好ましくは所定のサイズ及び所定の形状（更に好ましくは矩形）に統一されている。３次元モデルのレンダリングはタイルごとに行う。例えば、解像度640×480の画面を解像度32×32のタイルに分割する場合、20×15＝300枚のタイルのそれぞれでレンダリングを行う。特にレンダリングの対象のサイズが画面より小さい場合、その対象が重なっているタイルについてのみ、その対象のレンダリングが行われれば十分である。その結果、画面全体でレンダリングを行う場合より、レンダリングに必要な演算量を大幅に節減できる。
【００１６】
第２段階S302においては、まず、複数の三角形の中から一つを選択する。次に、複数のタイルの中から、選択された三角形の最小Ｚ値よりタイルＺ値が小さいタイル（以下、第１タイルという）を選別する。
ここで、三角形の最小Ｚ値は、その三角形の３つの頂点のＺ値のうち、最も小さなＺ値に等しい。すなわち、三角形の３つの頂点のうち、ユーザの視点に最も近い頂点のＺ値がその三角形の最小Ｚ値として採用される。三角形は平面であり、その各辺はいずれも直線である。従って、三角形に含まれている各点のＺ値は必ず、その三角形の最小Ｚ値以上である。
【００１７】
各タイルのタイルＺ値は好ましくは、そのタイルを完全に含む三角形それぞれの最大Ｚ値の中で最も小さい値に等しい。ここで、三角形の最大Ｚ値は、その三角形の各頂点のＺ値のうち最も大きい値に等しい。すなわち、ユーザの視点から最も遠い頂点のＺ値がその三角形の最大Ｚ値として採用される。三角形に含まれている各点のＺ値は必ず、その三角形の最大Ｚ値以下である。従って、各タイルのタイルＺ値は、そのタイルを完全に含む各三角形に含まれているユーザの視点から最も遠い点の中で、ユーザの視点に最も近い点のＺ値に等しい。あるタイルが、画面に投影されたある三角形に完全に含まれている場合、そのタイル内においては、その三角形の最大Ｚ値より大きいＺ値の点が、ユーザの視点からはその三角形に隠されて見えない。一方、画面上でそのタイルを完全に含む三角形が複数個存在する場合、そのタイル内では、最大Ｚ値の最も小さい三角形の部分がユーザの視点に最も近い。従って、ユーザの視点からは他の三角形の部分がその三角形の部分に隠されて見えない。第１タイルでは、選択された三角形の最小Ｚ値（すなわち、その三角形に含まれている点の中で、ユーザの視点に最も近い点のＺ値）よりタイルＺ値が小さい。それ故、第１タイルを完全に含む三角形の中に、選択された三角形を第１タイルの内部では隠す三角形が存在する。
【００１８】
第２段階S302では好ましくは、各タイルのタイルＺ値を次のように更新する。まず、選択された三角形（より正確には、それから画面に投影された三角形。以下、同様。）に完全に含まれているタイル（以下、第２タイルという）を選別する。その三角形に完全に含まれていないタイルでは、「その三角形が、その三角形の最大Ｚ値より最大Ｚ値が大きい他の三角形を隠している」という保証はないからである。次に、各第２タイルのタイルＺ値を選択された三角形の最大Ｚ値と比較する。そのタイルＺ値がその最大Ｚ値より大きい場合、そのタイルＺ値をその最大Ｚ値に更新する。
【００１９】
第２タイルの選別では好ましくは、まず、ハーフプレーンエッジ関数を用い、各タイルのタイルノードの判別値を決定する。ここで、各タイルのタイルノードは好ましくは、そのタイルの頂点である。タイルノードの判別値は、画面に投影された三角形に対するそのタイルノードの位置を表す。好ましくは、各タイルノードの判別値は、第１判別値、第２判別値、および第３判別値を含む。第１判別値、第２判別値、および第３判別値はそれぞれ、三角形の第１辺、第２辺、および第３辺のそれぞれに対するハーフプレーンエッジ関数値の符号に基づいて決められる。好ましくは、ハーフプレーンエッジ関数値が正数である場合には各判別値が1に決められ、負数または0である場合には0に決められる。尚、この場合分けとは異なる場合分けが行われても良い。
【００２０】
ハーフプレーンエッジ関数は、２次元画面上での直線と点との間の位置関係を表わす関数である。好ましくは、対象の直線の始点と終点との各座標を（x0、y0）、（x1、y1）とし、対象の点の座標を（x、y）とすると、ハーフプレーンエッジ関数値E(x、y)は次式によって定義される。
【００２１】
E(x、y)＝(x−x0)×Δy−(y−y0)×Δx。ここで、Δx＝x1−x0、Δy＝y1−y0。
【００２２】
ハーフプレーンエッジ関数値E(x、y)は、点が直線の左側にある場合には負であり、直線の右側にある場合には正である。第２タイルの選別においては、２次元画面に投影された三角形の各辺が上記の直線として設定され、タイルノードが上記の点として設定される。ここで、ユーザの視点から見て、その三角形の周に沿って時計回りに回転する方向をその三角形の各辺の方向とし、その方向に基づいて各辺の始点と終点とを決める。尚、各辺の方向はその他にも変更可能である。しかし、三角形の内部に存在するタイルノードの第１判別値、第２判別値、および第３判別値に同じ値を持たせるには、三角形の各辺の方向が循環するように決められねばならない。
【００２３】
第２タイルの選別では次に、各タイルのタイルノードの判別値を以下のように用い、「そのタイルが選択された三角形の内部に完全に含まれているかどうか」を確認する。図6に示されているように、その三角形の各辺の方向が時計回りに設定されている場合、各辺に対するハーフプレーンエッジ関数値は、三角形の内部610に含まれている点ではいずれも正である。一方、三角形の外部620、630、および640に含まれている点では、少なくともいずれか一つの辺に対するハーフプレーンエッジ関数値が負である。従って、あるタイルノードの第１判別値、第２判別値、および第３判別値がいずれも1である場合、対応するハーフプレーンエッジ関数値の符号がいずれも正であるので、「そのタイルノードは三角形の内部に含まれている」と判別される。更に、タイルノードが矩形状のタイルの４つの頂点である場合、全てのタイルノードが三角形の内部に含まれていれば、「そのタイルの全体がその三角形の内部に含まれている」と判別できる。
【００２４】
尚、各タイルのタイルノードのハーフプレーンエッジ関数値を用いると、画面に投影されたある三角形と一部でも重なっているタイルを識別できる（タイルビニング（tile binning））。従って、第２タイルの選別段階で計算されたハーフプレーンエッジ関数値をタイルビニングにも利用することで、レンダリング全体での計算量を低減し、かつレンダリングの処理時間を短縮できる。
【００２５】
第３段階S303においては、第２段階S302で選択された三角形のレンダリングを、第１タイルを除く残りのタイルでのみ行う。第１タイルではその三角形が他の三角形に隠されて見えないので、第１タイルではその三角形のレンダリングが行われなくても、画面に実際に表示される画像には影響がない。こうして、第１タイルでのレンダリングを省略することにより、選択された三角形のレンダリングをより効率よく行うことができる。
【００２６】
尚、第１タイルとは異なるタイルでも、第２段階S302で選択された三角形の部分が他の三角形に隠されて見えないことがある。従って、従来のレンダリング方法と同様に、選択された三角形のレンダリングの終了時にＺテストを行う必要がある。しかし、従来のレンダリング方法とは異なり、確実に除去可能なタイルが第１タイルとして予め除去されている。それ故、レンダリングの終了時のＺテストに必要な演算量は従来のレンダリング方法での演算量より顕著に少ない。
【００２７】
例えば、仮想的な３次元空間内に、図4に示されている、第１三角形410、第２三角形430、および第３三角形440しか存在しない場合、上記の方法では、それらのレンダリングを以下のように行う。
【００２８】
まず、第１三角形410に対してタイルごとのレンダリングを、第２段階S302、第３段階S303の順で行う。第２段階S302では、第１三角形410と重なっているタイルをすべて選別し、選別された各タイルのタイルＺ値を第１三角形410の最小Ｚ値と比較する。ここで、レンダリング済みの三角形がまだないので、第３段階S303では、第２段階S302で選別されたすべてのタイルにおいて第１三角形410のレンダリングを行うべきである。従って、好ましくは、各タイルのタイルＺ値の初期値がＺ値の上限（すなわち、仮想的な３次元空間内でユーザの視点から最も遠い点のＺ値）に設定されている。その他に、「まだ一度も更新されたことがない」という旨を示す特定の値が初期値として設定されていても良い。それにより、第２段階S302で選別されたすべてのタイルでタイルＺ値が第１三角形410の最小Ｚ値以上である。従って、第１三角形410については第１タイルが一枚も選別されない。それ故、第３段階S303では、第２段階S302で選別されたすべてのタイルで第１三角形410のレンダリングが行われる。
第２段階S302では更に、第１三角形410に完全に含まれている第２タイル群420が選別され、それらの各タイルＺ値が第１三角形410の最大Ｚ値に更新される。
【００２９】
次に、第２三角形430に対してタイルごとのレンダリングを、第２段階S302、第３段階S303の順で行う。第２段階S302では、第２三角形430と重なっているタイルを選別し、それらのタイルＺ値を第２三角形430の最小Ｚ値と比較する。ここで、図4に示されているように、画面上では第２三角形430が第１三角形410の内部に完全に含まれている。従って、第２三角形430の最小Ｚ値が第１三角形410の最大Ｚ値より大きい場合、ユーザの視点からは第２三角形430は第１三角形410に隠されて見えない。実際、この場合、第３段階S303では第２三角形430のレンダリングが次のように省略される。第２段階S302で選別される、第２三角形430と重なっているタイルはいずれも、第１三角形410に対する第２タイル群420に含まれている。従って、それらのタイルのタイルＺ値はいずれも第１三角形410の最大Ｚ値と等しいので、第２三角形430の最小Ｚ値より小さい。その結果、それらのタイルはいずれも第１タイルとして選別されるので、第３段階S303ではそれらのタイルにおける第２三角形430のレンダリングが省略される。
【００３０】
最後に、第３三角形440に対してタイルごとのレンダリングを、第２段階S302、第３段階S303の順で行う。第２段階S302では、第３三角形440と重なっている7枚のタイルA〜Gを選別し、それらのタイルＺ値を第３三角形440の最小Ｚ値と比較する。ここで、図4に示されているように、画面上では第３三角形430の一部が第１三角形410に重なり、更に第１三角形410に対する第２タイル群420に含まれている３つのタイルA、B、Cに重なっている。それらのタイルA〜CではタイルＺ値が更新されているが、残りのタイルD〜GではタイルＺ値が初期値のままである。従って、第３三角形430の最小Ｚ値が第１三角形410の最大Ｚ値より大きい場合、第３三角形440の最小Ｚ値よりタイルＺ値が、前者のタイルA〜Cでは小さく、後者のタイルD〜Gでは大きい。その結果、第３段階S303では第３三角形430のレンダリングが、第２タイル群420に含まれているタイルA〜Cについては省略され、その他のタイルD〜Gについてのみ行われる。
【００３１】
例えば図5に示されているように、4×4のタイルのマトリックスについて三角形510のレンダリングを行う場合は以下の通りである。ここで、図5では、マトリックスの縦横にタイルの行番号1〜4と列符号a〜dとが付記され、各タイルの中に各タイルのタイルＺ値が示されている。更に、三角形510の最小Ｚ値を5とする。
【００３２】
第２段階S302では、まず、三角形510と重なっているタイルを選別する。これにより、2−c、2−d、3−b、3−c、3−d、4−b、4−c、4−dの8枚のタイルが選別される。次に、選別された各タイルのタイルＺ値を三角形510の最小Ｚ値と比較し、タイルＺ値が三角形510の最小Ｚ値より小さいタイルを第１タイルとして選別する。これにより、3枚のタイル3−b、3−c、4−bが第１タイルとして選別される。第１タイルでは、タイルＺ値が三角形510の最小Ｚ値より小さいので、三角形510が別の三角形に隠されて画面には表示されない。第３段階S303では、3枚の第１タイル3−b、3−c、4−bを除く残り5枚のタイル2−c、2−d、3−d、4−c、4−dに対してのみ三角形510のレンダリングを行う。こうして、ユーザの視点からは見えない部分を除いて効率よくレンダリングを行うことができる。
尚、「5枚のタイル2−c、2−d、3−d、4−c、4−dに重なっている三角形510の部分のいずれもが必ず画面に表示される」とは限らないので、レンダリングの終了時には、ピクセル単位のＺテストを別に行うことが好ましい。
【００３３】
以上のように、本発明の上記の実施形態による早期Ｚテスト方法では、ある三角形に完全に含まれているタイルでその三角形に隠されている別の三角形の部分のレンダリングがそのタイルについては省略される。それにより、レンダリングを効率よく行うことができる。
【００３４】
本発明の上記の実施形態による早期Ｚテスト方法は好ましくは、図7に示されているシステムによって行われる。図7に示されているように、本発明の一実施形態による早期Ｚテストシステム701は、タイル分割部710、タイル選別部720、レンダリング実行部730、およびタイルＺ値更新部740を備えている。ここで、各構成要素は、ソフトウェア、ハードウェア、または、それらの組み合わせのいずれによっても実現可能である。
【００３５】
タイル分割部710は、上記の第１段階S301で画面を複数のタイルに分割する。
タイル選別部720は、上記の第２段階S302で、複数のタイルの中から、特定の三角形の最小Ｚ値よりタイルＺ値が小さいタイル（すなわち、第１タイル）を選別する。
レンダリング実行部730は、上記の第３段階S303で、タイル選別部720によって選別された第１タイルを除く残りのタイルにおいて、特定の三角形に対するレンダリングを行う。
タイルＺ値更新部740は、上記の第２段階S302で、まず、複数のタイルの中から特定の三角形に完全に含まれているタイル（すなわち、第２タイル）を選別する。次に、各第２タイルのタイルＺ値を選択された三角形の最大Ｚ値と比較する。そのタイルＺ値がその三角形の最大Ｚ値より大きい場合、そのタイルＺ値をその三角形の最大Ｚ値に更新する。
【００３６】
本発明の上記の実施形態による早期Ｚテスト方法は好ましくは、コンピュータにより所定のプログラムに従って実行される。更に好ましくは、コンピュータがそのプログラムに従い、図7に示されている各構成要素として機能する。そのプログラムは好ましくは、コンピュータ読み取り可能な記録媒体に保管されている。ここで、その記録媒体は、プログラム命令、データファイル、データ構造などを含む。更に、そのプログラムは、その全体が特別に設計されたものでも良く、当業者にとって公知なモジュール等の組み合わせから構成されたものであっても良い。コンピュータ読み取り可能な記録媒体の例としては、ハードディスク、フロッピーディスク（登録商標）、および磁気テープのような磁気媒体、ＣＤ−ＲＯＭやＤＶＤのような光記録媒体、フロプティカルディスク（登録商標）のような光磁気記録媒体、並びに、ＲＯＭ、ＲＡＭ、フラッシュメモリなどのような半導体メモリが含まれる。プログラム命令の例としては、コンパイラによって生成される機械語コードだけでなく、インタプリタなどを用いてコンピュータによって実行される高級言語コードを含む。
【００３７】
以上、本発明の好ましい実施形態を説明した。しかし、当業者にとっては、特許請求の範囲に記載された本発明の思想および領域から逸脱しない範囲内で、本発明の上記の実施形態を多様に修正し、又は変更可能であろう。従って、本発明の技術的範囲は上記の実施形態にのみ制限されるべきではなく、特許請求の範囲に基づき、上記の修正や変更を受けた実施形態をも含むように定められるべきである。
【図面の簡単な説明】
【００３８】
【図１】仮想的な３次元空間内に配置された４つの三角形のＺ軸方向での配置を示す模式図
【図２】レンダリング対象の２つの三角形とタイルとの間の、画面上での位置関係を例示する模式図
【図３】本発明の一実施形態による早期Ｚテスト方法のフローチャート
【図４】本発明の一実施形態による早期Ｚテスト方法において、画面に投射されたレンダリング対象の３つの三角形と、その画面にマトリックス状に配置されたタイルとの間の位置関係を示す模式図
【図５】本発明の一実施形態による早期Ｚテスト方法において、画面に投射されたレンダリング対象の別の三角形と、その画面にマトリックス状に配置されたタイルとの間の位置関係を示す模式図
【図６】本発明の一実施形態による早期Ｚテスト方法において、画面に投射された三角形の内外の領域別に、その三角形の各辺に対するハーフプレーンエッジ関数値の符号を示す模式図
【図７】本発明の一実施形態による早期Ｚテストシステムのブロック図
【符号の説明】
【００３９】
701 早期Ｚテストシステム
710 タイル分割部
720 タイル選別部
730 レンダリング実行部
740 タイルＺ値更新部
【特許請求の範囲】
【請求項１】
複数の三角形で表現される３次元画像のレンダリングを行うための方法であり、
画面を複数のタイルに分割する段階、
前記複数の三角形の中から一つを選択し、選択された三角形の最小Ｚ値よりタイルＺ値が小さい第１タイルを前記複数のタイルの中から選別する段階、及び、
前記第１タイルを除く残りのタイルにおいて前記選択された三角形のレンダリングを行う段階、
を有する早期Ｚテスト方法。
【請求項２】
各三角形の最小Ｚ値が、その三角形の３つの頂点のＺ値の中で最も小さい値に等しい、請求項１に記載の早期Ｚテスト方法。
【請求項３】
各タイルのタイルＺ値が、そのタイルを完全に含む三角形それぞれの最大Ｚ値の中で最も小さい値に等しい、請求項１に記載の早期Ｚテスト方法。
【請求項４】
各三角形の最大Ｚ値が、その三角形の３つの頂点のＺ値の中で最も大きい値に等しい、請求項３に記載の早期Ｚテスト方法。
【請求項５】
前記第１タイルを選別する段階が、
前記選択された三角形に完全に含まれる第２タイルを前記複数のタイルの中から選別する段階、及び、
前記第２タイルのタイルＺ値より前記選択された三角形の最大Ｚ値が小さい場合、前記第２タイルのタイルＺ値を前記選択された三角形の最大Ｚ値に更新する段階、
を含む、請求項３に記載の早期Ｚテスト方法。
【請求項６】
前記第２タイルを選別する段階が、
前記複数のタイルのそれぞれのタイルノードについて判別値を決定する段階、及び、
前記判別値に基づいて前記第２タイルを選別する段階、
を含む、請求項５に記載の早期Ｚテスト方法。
【請求項７】
前記判別値を決定する段階が、
各タイルのタイルノードごとに、前記選択された三角形の第１辺、第２辺、及び第３辺のそれぞれに対するハーフプレーンエッジ関数値の符号に基づいて、第１判別値、第２判別値、及び第３判別値を決める段階、
を含む、請求項６に記載の早期Ｚテスト方法。
【請求項８】
前記判別値に基づいて前記第２タイルを選別する段階が、
一つのタイルに含まれるタイルノードの全てで、第１判別値、第２判別値、及び第３判別値がいずれも、対応するハーフプレーンエッジ関数値の符号が正であることを示す場合、そのタイルを前記第２タイルとして選別する段階、
を含む、請求項７に記載の早期Ｚテスト方法。
【請求項９】
請求項１から請求項８までのいずれか一項に記載の早期Ｚテスト方法をコンピュータに実行させるためのプログラム。
【請求項１０】
請求項１から請求項８までのいずれか一項に記載の早期Ｚテスト方法をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１１】
複数の三角形で表現される３次元画像のレンダリングを行うためのシステムであり、
画面を複数のタイルに分割するタイル分割部、
前記複数の三角形の中から一つを選択し、選択された三角形の最小Ｚ値よりタイルＺ値が小さい第１タイルを前記複数のタイルの中から選別するタイル選別部、及び、
前記第１タイルを除く残りのタイルにおいて前記選択された三角形のレンダリングを行うレンダリング実行部、
を有する早期Ｚテストシステム。
【請求項１２】
前記選択された三角形に完全に含まれる第２タイルを前記複数のタイルの中から選別し、前記第２タイルのタイルＺ値より前記選択された三角形の最大Ｚ値が小さい場合、前記第２タイルのタイルＺ値を前記選択された三角形の最大Ｚ値に更新するタイルＺ値更新部、
をさらに有する、請求項１１に記載の早期Ｚテストシステム。
【請求項１】
複数の三角形で表現される３次元画像のレンダリングを行うための方法であり、
画面を複数のタイルに分割する段階、
前記複数の三角形の中から一つを選択し、選択された三角形の最小Ｚ値よりタイルＺ値が小さい第１タイルを前記複数のタイルの中から選別する段階、及び、
前記第１タイルを除く残りのタイルにおいて前記選択された三角形のレンダリングを行う段階、
を有する早期Ｚテスト方法。
【請求項２】
各三角形の最小Ｚ値が、その三角形の３つの頂点のＺ値の中で最も小さい値に等しい、請求項１に記載の早期Ｚテスト方法。
【請求項３】
各タイルのタイルＺ値が、そのタイルを完全に含む三角形それぞれの最大Ｚ値の中で最も小さい値に等しい、請求項１に記載の早期Ｚテスト方法。
【請求項４】
各三角形の最大Ｚ値が、その三角形の３つの頂点のＺ値の中で最も大きい値に等しい、請求項３に記載の早期Ｚテスト方法。
【請求項５】
前記第１タイルを選別する段階が、
前記選択された三角形に完全に含まれる第２タイルを前記複数のタイルの中から選別する段階、及び、
前記第２タイルのタイルＺ値より前記選択された三角形の最大Ｚ値が小さい場合、前記第２タイルのタイルＺ値を前記選択された三角形の最大Ｚ値に更新する段階、
を含む、請求項３に記載の早期Ｚテスト方法。
【請求項６】
前記第２タイルを選別する段階が、
前記複数のタイルのそれぞれのタイルノードについて判別値を決定する段階、及び、
前記判別値に基づいて前記第２タイルを選別する段階、
を含む、請求項５に記載の早期Ｚテスト方法。
【請求項７】
前記判別値を決定する段階が、
各タイルのタイルノードごとに、前記選択された三角形の第１辺、第２辺、及び第３辺のそれぞれに対するハーフプレーンエッジ関数値の符号に基づいて、第１判別値、第２判別値、及び第３判別値を決める段階、
を含む、請求項６に記載の早期Ｚテスト方法。
【請求項８】
前記判別値に基づいて前記第２タイルを選別する段階が、
一つのタイルに含まれるタイルノードの全てで、第１判別値、第２判別値、及び第３判別値がいずれも、対応するハーフプレーンエッジ関数値の符号が正であることを示す場合、そのタイルを前記第２タイルとして選別する段階、
を含む、請求項７に記載の早期Ｚテスト方法。
【請求項９】
請求項１から請求項８までのいずれか一項に記載の早期Ｚテスト方法をコンピュータに実行させるためのプログラム。
【請求項１０】
請求項１から請求項８までのいずれか一項に記載の早期Ｚテスト方法をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１１】
複数の三角形で表現される３次元画像のレンダリングを行うためのシステムであり、
画面を複数のタイルに分割するタイル分割部、
前記複数の三角形の中から一つを選択し、選択された三角形の最小Ｚ値よりタイルＺ値が小さい第１タイルを前記複数のタイルの中から選別するタイル選別部、及び、
前記第１タイルを除く残りのタイルにおいて前記選択された三角形のレンダリングを行うレンダリング実行部、
を有する早期Ｚテストシステム。
【請求項１２】
前記選択された三角形に完全に含まれる第２タイルを前記複数のタイルの中から選別し、前記第２タイルのタイルＺ値より前記選択された三角形の最大Ｚ値が小さい場合、前記第２タイルのタイルＺ値を前記選択された三角形の最大Ｚ値に更新するタイルＺ値更新部、
をさらに有する、請求項１１に記載の早期Ｚテストシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００８−７７６２７（Ｐ２００８−７７６２７Ａ）
【公開日】平成２０年４月３日（２００８．４．３）
【国際特許分類】
【出願番号】特願２００７−９３７６６（Ｐ２００７−９３７６６）
【出願日】平成１９年３月３０日（２００７．３．３０）
【出願人】（３９００１９８３９）三星電子株式会社 (8,520)
【氏名又は名称原語表記】ＳＡＭＳＵＮＧ ＥＬＥＣＴＲＯＮＩＣＳ ＣＯ．，ＬＴＤ．
【住所又は居所原語表記】４１６，Ｍａｅｔａｎ−ｄｏｎｇ，Ｙｅｏｎｇｔｏｎｇ−ｇｕ，Ｓｕｗｏｎ−ｓｉ，Ｇｙｅｏｎｇｇｉ−ｄｏ ４４２−７４２（ＫＲ）
【Ｆターム（参考）】
【公開日】平成２０年４月３日（２００８．４．３）
【国際特許分類】
【出願日】平成１９年３月３０日（２００７．３．３０）
【出願人】（３９００１９８３９）三星電子株式会社 (8,520)
【氏名又は名称原語表記】ＳＡＭＳＵＮＧ ＥＬＥＣＴＲＯＮＩＣＳ ＣＯ．，ＬＴＤ．
【住所又は居所原語表記】４１６，Ｍａｅｔａｎ−ｄｏｎｇ，Ｙｅｏｎｇｔｏｎｇ−ｇｕ，Ｓｕｗｏｎ−ｓｉ，Ｇｙｅｏｎｇｇｉ−ｄｏ ４４２−７４２（ＫＲ）
【Ｆターム（参考）】
[ Back to top ]