(57)【特許請求の範囲】
【請求項１】
コンピュータによる３次元シェーディング及びテクスチャリング・システムにおける半透明オブジェクトのデータを自動的にソートする方法であって、
ａ）シェーディング及びテクスチャリングされる半透明のオブジェクトのリストを記憶するステップと、
ｂ）リスト内のオブジェクトが画像平面からみて、現在最も深いオブジェクトよりもさらに遠いかどうかを、各オブジェクトについて各ピクセルにおいて順に決定するステップと、
ｃ）前記リスト内の当該ピクセルにおいて最も深いオブジェクトについてのデータを記憶するステップと、
ｄ）最も深いオブジェクトについてのデータをシェーディングし、テクスチャリングするステップと、
ｅ）前記リストから最も深いオブジェクトをディスカードし、次に深いオブジェクトのデータをリスト内の最も深いオブジェクトの位置へ移動するステップと、
ｆ）前記リスト内のすべてのオブジェクトがシェーディング及びテクスチャリングされるまで、ｂ）、ｃ）、ｄ）、ｅ）のステップを繰り返すステップと、
を含むことを特徴とする方法。
【請求項２】
シェーディング及びテクスチャリングされる前記画像を、まず複数の小領域に分割し、それぞれの小領域についてソートを行う、請求項１に記載の方法。
【請求項３】
前記ソートは、各小領域について順に行うものである、請求項２に記載の方法。
【請求項４】
コンピュータによる３次元シェーディング及びテクスチャリング・システムにおける半透明オブジェクトのデータを自動的にソートする装置であって、
ａ）シェーディング及びテクスチャリングされる半透明のオブジェクトのリストを記憶する手段と、
ｂ）リスト内のオブジェクトが画像平面からみて、現在最も深いオブジェクトよりもさらに遠いかどうかを、各オブジェクトについて各ピクセルにおいて順に決定する手段と、
ｃ）前記リスト内の当該ピクセルにおいて最も深いオブジェクトについてのデータを記憶する手段と、
ｄ）最も深いオブジェクトのピクセルデータをシェーディングし、テクスチャリングする手段と、
ｅ）前記リストから最も深いオブジェクトをディスカードし、次に深いオブジェクトのデータをリスト内の最も深いオブジェクトの位置へ移動する手段と、
ｆ）リスト内のすべてのオブジェクトがシェーディング及びテクスチャリングされるまで、前記ｂ）、ｃ）、ｄ）、ｅ）の各手段に動作を繰り返させる手段と、
を含むことを特徴とする装置。
【請求項５】
シェーディング及びテクスチャリングされる前記画像を、まず複数の小領域に分割し、それぞれの小領域についてソートを行う、請求項４に記載の装置。
【請求項６】
前記ソートは、各小領域について順に行うものである、請求項５に記載の装置。
【請求項７】
前記各小領域は複数のピクセルを含んでおり、前記手段ｂ）は、リスト内のオブジェクトが画像平面からみて現在最も深いオブジェクトよりもさらに遠いかどうかを決定する複数の手段を含んでおり、これにより複数のピクセルを並列して処理できるようにした、請求項４又は５に記載の装置。
【請求項８】
前記リスト内で次に深いオブジェクトについてのデータを記憶する手段と、前記リスト内で次に深いオブジェクトについてのデータをシェーディングし、テクスチャリングしそして記憶する手段を含んでいる、請求項５又は７に記載の装置。
【発明の詳細な説明】
【０００１】
本発明は、３次元コンピュータ・イメージング・システムに使用するための、オブジェクトのソートに関する。
【０００２】
Ｚバッファ・システムとして広く知られている最新の３次元シェーディング及びテクスチャリング・システムでは、Ｚバッファを用いたアプリケーション・ソフトは、画像が正しく見えるように、半透明のオブジェクトを、レンダリングする前に、後から前へという順番に前もってソートしておく必要がある。Ｍａｍｍｅｎ，Ａ．による「Ｔｒａｎｓｐａｒｅｎｃｙ  ａｎｄ  Ａｎｔｉａｌｉａｓｉｎｇ  Ａｌｇｏｒｉｔｈｍｓ  Ｉｍｐｌｅｍｅｎｔｅｄ  ｗｉｔｈ  ｔｈｅ  Ｖｉｒｔｕａｌ  Ｐｉｘｅｌ  Ｍａｐｓ  Ｔｅｃｈｎｉｑｕｅ」，ＣＧ＆Ａ，９（４），Ｊｕｌｙ  １９８９，Ｐ４３〜Ｐ５５に１つの方法が開示され、これは上記の制限条件を取り除くシステムについて説明しており、Ｚバッファ・システムにおいて使用できる。しかしながら、これは像サイズと同じサイズのバッファが必要であり、各ピクセルについてＺ値すなわち深度値、ＲＧＢ値、そして半透明値すなわちアルファ値を含むという点において、大きな欠点を有している。これは、従来のＺバッファ・システムに対して必要とされる記憶量を、倍増させてしまう。加えて、この提案された方法は、像から一度に一つの三角形をレンダリングするという概念に基づいているので、ソート性能を非常に低くしている。
【０００３】
我々の英国特許２２９８１１１号には、概ね長方形のより小さい領域もしくはタイルに像を分割するシステムについての説明がなされている。このタイル・ベースのシステムを用いることによって、半透明のオブジェクトを自動ソートする場合の性能が、従来技術のシステムに比べて大いに改善されることを認識した。タイル・ベースのシステムにおける記憶装置についての必要条件は、タイル化の手法を用いることで、従来技術よりも非常に良好である。
【０００４】
他のシステムと同様に、我々の英国特許２，２９８，１１１号において説明されているタイプの３−Ｄ・シェーディング・システムでは、半透明のオブジェクトを、レンダリングするよりも前に、アプリケーション・ソフトによって後ろから前へという順序で予めソートする必要がある。このことは、アプリケーション・ソフトの速度を落とし、システム全体の最高性能を低下させる。更なる問題として、半透明オブジェクトのソートには、ピクセル程度の正確さを必要とする。このことは、図１に示すように二つのオブジェクトが交差するときのソーティングを複雑にし、二つのオブジェクトの交点を計算する必要を生じさせ、そして二つのオブジェクトを分離しなければならず、そして残りの部分を後を前にソートしなければならない。
【０００５】
ここで説明するシステムは、本質的に、通常は三角形である多数のオブジェクトを同時に処理することができ、これによって高い性能を達成することができる。また、従来の方法とは異なり、ここで説明する方法は、ディスカード（破棄）技術を用いてソート動作の複雑さを軽減し、ソートの速度を向上させる。
【０００６】
本発明のこの好適な実施例では、オブジェクトをレンダリングに先だってソートするときに、半透明オブジェクトについて別々の表示リストを保持し、ソーティング深度について一又は二以上の余分のタイル深度バッファを設ける。これによってアプリケーション・ソフトウェアは、半透明オブジェクトを、任意の順番でレンダリング・ハードウェアに送ることができる。そしてレンダリング・ハードウェアは、半透明オブジェクトを、ピクセルごとに後から前へという順序にソートすることができる。
【０００７】
ここで、本発明を、添付図面を参照しながら、例示として詳細に説明する。
【０００８】
図２に示すダイアグラムには、ポリゴン・セットアップ・ユニット２０が含まれている。これは、頂点のデータを受け取って、これらから、ポリゴンが構成される平面を定義するポリゴンの平面方程式を生成する。これらは、キャッシュメモリ２１へ渡される。キャッシュメモリ２１は、ポリゴン・セットアップ・ユニットとプロセッサ・アレイとの間のバッファとしての役割を果たすとともに、特定のポリゴンについてのデータをプロセッサ・エレメント（Ｐ．Ｅ．）アレーに与えるよう、ディスカードロジック５８によって制御される。プロセッサ・アレーは、視点から画像平面を通ってレンダリングすべきシーンへ達するレイ（光線）について、一連のレイ−表面交差テスト（ray surface intersection test）を行う。各表面は、ピクセルごとにテストされ、その結果は、タイル深度記憶及び深度テストユニット２６へ送られる。このタイル深度記憶装置には、記憶装置と、タイル内のピクセルごとに行う深度テストロジックとが含まれ、また自動ソートロジックも含まれている。
【０００９】
深度テストロジックは、深度バッファに現在格納されているものと、各ピクセルごとに処理されている現在のオブジェクトの深度との間の大きさの比較を実行する。アプリケーション・ソフトウェアは、「ｎｅｖｅｒ（あり得ない）」、「ｌｅｓｓ（小さい）」、「ｅｑｕａｌ（等しい）」、「ｌｅｓｓ  ｏｒ  ｅｑｕａｌ（以下）」、「ｇｒｅａｔｅｒ（大きい）」、「ｎｏｔ  ｅｑｕａｌ（等しくない）」、「ｇｒｅａｔｅｒ  ｏｒ  ｅｑｕａｌ（以上）」、「ａｌｗａｙｓ（常に）」という比較モードの中から、必要とされる比較の種類に応じていずれかを与えることができる。
【００１０】
深度記憶及び深度テストユニット２６は、この深度テストの結果をディスカード・ロジック５８に与えることができる。これは、将来必要とされる表面のリストを格納するとともに、頂点リクエスタ６０からの正しい順序でそれらをリクエストする。これは、前から後へか後から前へかをユーザーが設定するソート方向の入力を有している。ソートされた表面のリストが一旦計算されれば、頂点リクエスタ６０を制御するのに自動ソートロジックが用いられ、頂点リクエスタ６０は、頂点データをポリゴン・セットアップ・ユニット２０に供給するようメモリにリクエストを送り、データはここから再びキャッシュ２１へ、そしてプロセッサ・エレメント・アレー２４へ供給される。このように、一旦ソートが実行されると、各表面に対する適当な属性がタイル深度記憶装置から引き出され、その出力は並列ランレングス・エンコーダへ送られ、これはこれらをレンダリング及びテクスチャリング回路（図示せず）へ送る。
【００１１】
図から分かるように、頂点リクエスタ６０は、これへの入力となっている別々の表示リストへもアクセスする。これは前述の半透明オブジェクトの表示リストである。頂点リクエスタを制御する自動ソートロジックよりも前には、これは画像内の半透明オブジェクトのためのオブジェクト・データのソースである。
【００１２】
動作中に、システムは、表面を正しい順序にソートするために、半透明表示リストに対して多数回のパスを行う。パスの回数は、半透明レイヤーの総数に依存する。半透明レイヤーが１０個あるとすれば、オブジェクトを完全にソートするのに１０回のパスが必要となる。
【００１３】
この構成は、タイル深度記憶装置２４に、二以上の深度バッファを設けることによって大幅に改良することができる。この実施例では、二つの追加の深度バッファを設けている。これによって１０層であれば５回のパスでソートでき、ソートに要する時間を半分に短縮できる。深度バッファをさらに追加すれば、システムはさらに改善される。３２×３２ピクセルの深度バッファを有するタイルを基礎とするシステムでは、半透明のオブジェクトをソートするのにく、さらに二つの３２×３２ピクセルの深度バッファを設けることが望ましい。この二つの深度バッファをワーキング深度１及びワーキング深度２と呼ぶ。タイル深度記憶装置２６の元々の深度バッファは、不透明深度バッファと呼ぶ。
【００１４】
後述するアルゴリズムは、タイル内のすべてのピクセルをソートするのに用いられる。ここで説明する特定の構成では、３２個の個別の深度比較プロセッサを設けてあるので、３２個のピクセルを一度に処理することができる。
【００１５】
深度プロセッサ、ワーキング深度、そして不透明深度バッファの間の関係を図３に示す。深度プロセッサ３０はそれぞれ３２個のプロセッサを含んでおり、その幅は各タイルの幅とされている。深度バッファは、ワーキング深度１  ３４、ワーキング深度２  ３６、不透明深度バッファ３８からなる。
【００１６】
不透明オブジェクトをソートする場合、ソータは、前から後へという順序でソートするように制御される。各パスにおいて、そのパスで最も近いオブジェクトはワーキング深度１に格納される。ワーキング深度１のオブジェクトは、常にワーキング深度２のオブジェクトよりも近い。したがって、ワーキング深度２の比較においてそのオブジェクトがワーキング深度１のオブジェクトよりも近いときは、そのオブジェクトがワーキング深度１のオブジェクトに置き換わり（そのピクセルについて）、元々ワーキング深度１にあったオブジェクトはディスカード（破棄）される。続いて次のオブジェクトがワーキング深度２に供給され、再びワーキング深度１との比較が行われる。ワーキング深度１における任意の不透明ピクセルは、不透明深度バッファ３８に供給される。これ以降のパスから現れるより近い不透明なオブジェクトがある場合には、これは特定のピクセルについて不透明深度バッファ内の深度と置き換わる。
【００１７】
半透明オブジェクトは、オブジェクトの後に処理される。半透明のオブジェクトを後から前へとうい順序でソートするには、データについて多数回のパスを行うことが必要である。各パス上で、最も深い深度及び二番目に深い深度が格納され、レンダリングされる。これは、すべてのオブジェクトが完全にレンダリングされるまで続けられる。半透明オブジェクトは、完全にレンダリングされると、半透明表示リストからディスカードされる。こうして、表示リストを通じてなされる次のパスはより速くなり、ソート時間が短縮される。
【００１８】
パスの中で最も深いオブジェクトは、ワーキング深度１に記憶され、ワーキング深度２には二番目に深い深度が記憶される。ワーキング深度１のオブジェクトは、常にワーキング深度２のオブジェクトよりも深く、したがってワーキング深度１が置き換えられたときは、古いオブジェクトはワーキング深度２へ移され、元々ワーキング深度２にあったオブジェクトはディスカードされる。オブジェクトがワーキング深度１よりも深くなければ、ワーキング深度２の値に照らしてテストされる。ワーキング深度１の値より深ければ、置き換えが行われる。
【００１９】
以上の動作を行う仮想的なプログラム・コードを以下に与える。
【００２０】
【数１】
0004678951.tif 000002
0004678951.tif 000003
【００２１】
上述した処理を行った後、以下のどれかの場合に当てはまるときは、パスをもう一度実行しなければないない。
１．オブジェクトがワーキング深度１からワーキング深度２へと移動された場合に、それによって以前そこに格納されていたオブジェクトが追い出された場合；
２．ワーキング深度２の記憶装置への書き込みが、そのパスのより前の時期に格納されていたオブジェクトを置き換えた場合；
３．オブジェクトが、ワーキング深度２のオブジェクトよりも近かったためにスキップされた場合。
【００２２】
オブジェクトが、タイル内のすべてのピクセルについてバック深度の後ろにある場合には、次のパスからディスカードされる。バック深度とは、シーン内において最い目に見える深度である。
【００２３】
冒頭において言及した従来のアルゴリズムは、
0004678951.tif 000004
という式で与えられるソート性能を有していた。ここでＮｐは、画像内の半透明ポリゴンの合計数である。
【００２４】
ここで説明した方法は、一つの深度バッファを追加した場合には、
0004678951.tif 000005
という式で与えられる時間を有する。ここで、Ｎ１は、半透明レイヤーの合計数である。レイヤーの数は、常にポリゴンの数と同じかこれよりも少ない。前述のように二つの追加の深度バッファを有する場合には、合計の時間は、
0004678951.tif 000006
となる。深度バッファの数をさらに増やせば、ソート性能はそれに比例して向上する。
【図面の簡単な説明】
【図１】  オブジェクトが交差する状態を示した図である。
【図２】  レンダリング・システムにおける自動ソートロジックのブロック図である。
【図３】  タイル深度記憶及び深度テスト装置を詳しく示したブロック図である。
【図１】
0004678951.tif 000007
【図２】
0004678951.tif 000008
【図３】
0004678951.tif 000009