結合判定メカニズムを用いて三次元グラフィックス画像をコンポジットするための方法およびシステム
各サブ画像における同一の空間位置に対応するピクセルの深さ値を検査し、そして最大の深さ値を有するピクセルの内容をコンポジットすることによって複数の三次元サブ画像をコンポジット処理するための方法およびシステムである。深さ値は、二つ以上のバイナリセグメントに分割され、そこでは、セグメントのビット長が、それらの有意性のレベルに従って決定される。第一のステップにおいては、同一レベルの有意性を有するセグメント群の絶対値が同時に比較され、そしてそれに従って、それらの最上位セグメントの絶対値が、同一レベルの有意性の他のセグメントの絶対値と比較して、最大である深さ値を示すグループが決定され、そしてそれらの絶対値サイズを示す最下位セグメントについてのグレードが評価される。第二のステップにおいては、当該グループに対応する深さ値のセグメントのグレードが比較され、そして、もしもそれらのグレードが、当該グループにおける他の深さ値に対応する最高グレードよりも小さいならば、深さ値指示が、グループから除去される。第二のステップは、セグメントの最終セットに達するまで、または単一の深さ値がグループによって指示されるまで、繰り返される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータグラフィックスレンダリングの分野に関する。より詳細には、本発明は、多重三次元／深さラスタ画像の二次元画像への再コンポジションのための方法および装置に関する。
【０００２】
［関連出願へのクロスリファレンス］
この出願は、その全開示が引用によりここに組み込まれる、２００３年１月２８日に出願された米国仮特許出願第６０／４４２，７５０号の恩恵を請求する。
【背景技術】
【０００３】
多くのタイプの情報処理インプリメンテーションと同様に、コンピュータグラフィックスレンダリングの性能を向上させるべく努力が続けられている。レンダリング性能を向上させる魅力的な試みの一つは、単一の場面を並列にレンダリングすべく一緒に利用される多重のグラフィック処理ユニット（ＧＰＵ）を用いることに基づいている。
【０００４】
多重ＧＰＵを用いてグラフィックデータをレンダリングするための三つの有力な方法がある。それらは、各ＧＰＵが次の後続フレームをレンダリングする時間領域コンポジションと、各ＧＰＵが各フレームのピクセルのサブセットをレンダリングする画面空間コンポジションと、各ＧＰＵがデータベースのサブセットをレンダリングする場面ベースコンポジションとを含んでいる。
【０００５】
時間領域コンポジションにおいては、各ＧＰＵは、次の後続フレームをレンダリングする。この方法の大きな不都合は、各ＧＰＵが全フレームをレンダリングすることを有することにある。それゆえ、各フレームがレンダリングされるスピードは、単一のＧＰＵのレンダリング速度に制限される。多重ＧＰＵは、より高いフレーム速度を可能とすると同時に、ユーザの入力に対するシステムの応答時間における時間領域コンポジションアプリケーションにおいて遅延が分与され得る（すなわち、待ち時間の縮減）。いかなる与えられた時間においてもレンダリングされたフレームを表示するのに、他の全てのＧＰＵが、連続する一連のフレームの一つをレンダリングするプロセス中にある間に、ただ一つのＧＰＵが従事させられるから、これらの遅延が典型的に生ずる。一定のフレーム速度を維持するために、システムは、ユーザの入力を最初に受信した特定のＧＰＵがシーケンスを通して周期動作するまでユーザの入力に作用するのを遅延させ、そしてそのレンダリングされたフレームを表示するのに、再び従事する。実際的なアプリケーションにおいて、この条件は、システムに使用されるＧＰＵの数を制限させる。
【０００６】
時間領域コンポジションアプリケーションに関連する他の困難性は、これらのアプリケーションにおいては、各ＧＰＵが、画像レンダリングのために使用される全データへのアクセスを得ることができなければならないから、各ＧＰＵがアクセスすることができなければならない大きなデータのセットに関連する。これは、例えば、単一のコピーをアクセスすることの多重の試みによって生ずる可能性がある衝突を防止するために大きなデータセットの多重コピーを維持することによって達成される。
【０００７】
画面空間コンポジションアプリケーションは、各ＧＰＵが、どのグラフィックエレメントが画面のその部分内に属するかを決定すべくデータベース全体を検査しなければならないから、大きなデータセットの処理における同様の問題を有する。この場合におけるシステム待ち時間は、単一のＧＰＵによって単一のフレームをレンダリングするために必要とされる時間に等しい。
【０００８】
本発明がそれに関連する、場面コンポジション法は、上述された待ち時間の問題、データセットの多重コピーを維持することの必要性、および各ＧＰＵによるデータベース全体を取り扱うことに関連する問題によるものを排除する。
【０００９】
場面コンポジション法は、莫大な量の幾何学的データのレンダリングを必要とするアプリケーションに良く適合する。典型的には、それらは、ＣＡＤアプリケーション、および空間におけるそれらの三次元的位置がユーザの対話的制御下にないようにデータが予め設計されていることを意味する、「ビューワ」として論じられる、類似の視覚的シミュレーションアプリケーションである。しかしながら、ユーザは、観察者の位置である、ビュー方向およびグラフィックデータの縮尺を対話的制御している。ユーザは、また、データのサブセットの選択およびそれがレンダリングされる方法を制御していても良い。このことは、基礎をなすデータの画像ライティング、彩色、透明性および他の視覚的特性の影響を操作することを含んでいる。
【００１０】
ＣＡＤアプリケーションにおいては、データが、通常は、ディスプレイリストまたは頂点アレイにおける膨大な量の幾何学的実体からなるので、非常に複雑になる傾向にある。それゆえ、単一フレームの構成時間は、非常に長く（例えば典型的には、２千万個の多角形群について０．５秒に）なる傾向にあり、結果として全体のシステム応答をスローダウンさせる。
【００１１】
場面コンポジション法（例えば、オブジェクトベースのデコンポジション法）は、多重ＧＰＵの間のデータサブセットの分布に基づいている。データサブセットは、ＧＰＵパイプラインにおいてレンダリングされ、そしてフラグメント（サブ画像ピクセル）のフレームバッファ（ＦＢ）に変換される。多重ＦＢのサブ画像は、表示されるべき最終画像を生成するためにマージされなければならない。図１に示されるように、最終画像のＸ／Ｙ平面における各ピクセルについて、ＦＢのサブ画像によって与えられる異なる画像深さに対応する種々のとり得る値が存在する。
【００１２】
各ＧＰＵは、各画面の（Ｘ／Ｙ）座標にて多くて一つのピクセル１２を生起する。この構成されたピクセル１２は、隠れた面の除去および影付けおよび透明性を実現するための混色の結果である。ＧＰＵによって生成されたピクセル１２の各々は、（観察者に最も近い）最高のＺについて解かれるべき、異なる深さ量（Ｚ−値）を保持する。ただ一つのピクセルのみが最終的に通ることが許可される。各ＦＢのサブ画像のマージは、ＦＢによって与えられる種々の可能性のあるピクセル値１２からどの値（１０）が、観察者の視点において視認可能な最近点をあらわすかの決定の結果である。しかしながら、一つの単一のラスタへの部分的場面データのマージングは、依然として先行技術における性能のボトルネックを引き起こしている。
【００１３】
先行技術における並列処理のレベルは、多重ラスタのコンポジション性能の不足によって制限されている。二つのラスタのコンポジションは、隠れ面除去を行うためのハードウェア技法であるＺ−バッファリングによって通常は行われる。先行技術の在来の方法においては、Ｚ−バッファリングは、一度に二つのラスタのみのマージングを許容する。
【００１４】
在来のハードウェアコンポジッティング技法は、図２Ａに例示されたように、典型的には、ラスタのペアの繰り返し照合プロセス（Ｓ．Ｍｏｌｎｅｒの「高速レンダリングのためのＺ−バッファエンジンの結合」（Ｃｏｍｂｉｎｉｎｇ Ｚ−ｂｕｆｆｅｒ Ｅｎｇｉｎｅｓ ｆｏｒ Ｈｉｇｈｅｒ−Ｓｐｅｅｄ Ｒｅｎｄｅｒｉｎｇ）、Ｅｕｒｏｇｒａｐｈｉｃｓ、１９８８年）、またはパイプライン技法（Ｊ．Ｅｙｅｓ他の「ピクセルフロー：現実化」（ＰｉｘｅｌＦｌｏｗ：Ｔｈｅ Ｒｅａｌｉｚａｔｉｏｎ）、ＡＣＭ Ｓｉｇｇｒａｐｈ、１９９７年）に基づいている。これらの技法のマージングは、Ｓステージの、ｌｏｇ２Ｒステップ以内で実行される。ここで、Ｒは、レンダリングＧＰＵの数である。照合のケースにおいては、各そのようなコンパレータ（ＭＸ）における二つの深さ寸法の間の比較を達成するために必要とされる時間は、ｌｏｇ２Ｚである。ここで、Ｚは、場面の深さ領域である。例えば、ピクセルあたり２４ビットを有する典型的な深さバッファについては、二つのＺ−バッファの間の比較は、典型的には、２４の時間クロック内に行われる。
【００１５】
先行技術の技法において、一度に、二つのＺ−バッファのみのマージングが許容され、多重ラスタのコンポジションは、階層的な形式でなされる。これらのコンポジション構造の複雑さは、Ｏ（ｌｏｇ２Ｒ）であり、グラフィックパイプラインの数、性能がＲによって高度に影響されるようにさせる。Ｒの値を増大させるために、コンポジッティング時間が、リアルタイムアニメーションのための割り当てられたタイムスロットを超える。実際的なアプリケーションにおいては、この条件は、システム内に使用されるＧＰＵの数に制限を与える。図２Ｂは、並列処理の増大による理論的な性能の改善を示している。コンポジション時間は、複雑さの因子、Ｏ（ｌｏｇ２Ｒ）によって増大する。統合された時間は、（例えば）１６個のパイプラインにおいて増大をスタートする。明らかに、この場合には、１６を超える並行処理のレベルの増大には、有意性がない。
【００１６】
ソフトウェア技法は、通常、Ｐ個の汎用プロセッサを用いることによってＲ個のＧＰＵの出力をコンポジットすることに基づいている（Ｅ．ＲｅｉｎｈａｒｄおよびＣ．Ｈａｎｓｅｎの「共有メモリ構成における並列コンポジッティング技法の比較」（Ａ Ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｐａｒａｌｌｅｌ Ｃｏｍｐｏｓｉｔｉｎｇ Ｔｅｃｈｎｉｑｕｅｓ ｏｎ Ｓｈａｒｅｄ Ｍｅｍｏｒｙ Ａｒｃｈｉｔｅｃｔｕｒｅｓ）、Ｐａｒａｌｌｅｌ Ｇｒａｐｈｉｃｓ ａｎｄ ＶｉｓｕａｌｉｓａｔｉｏｎのＥｕｒｏｇｒａｐｈｉｃｓ Ｗｏｒｋｓｈｏｐ、Ｇｉｒｏｎａ、２０００年）。しかしながら、これらの解決策は、典型的には、（ｉ）バイナリスワップ、（ｉｉ）並列パイプライン、および（ｉｉｉ）共有メモリコンポジッタの利用を必要とし、そしてそのことは、そのようなインプリメンテーションの複雑さおよびコストを有意に増大させる。
【００１７】
ソフトウェア技法の中で最も効果的なインプリメンテーションは、共有メモリコンポジッタ法（分散メモリ構成における「直接送出」としても知られている）である。この方法においては、サブ画像をレンダリングするための計算労力が、図３Ａのブロック図および図３Ｂに示される擬似コードに示されるように、付加的なＧＰＵ（レンダラ）を利用することによって、増大される。図３Ａに図解されたシステムにおいては、二つのコンポジッタ（ＣＰＵｐ０およびｐ１）が、三つのレンダラ（ＧＰＵＢ０、Ｂ１、およびＢ２）によって生成される、同一のサブ画像について同時に操作している。計算タスクは、ＣＰＵ間に分散され、各々同一画像の半分のコンポジションを実行する。いかなる与えられた数のＧＰＵのためにも、並列コンポジタの数を増大させることによってコンポジッティングをスピードアップすることができることは良く知られている。
【００１８】
しかしながら、増大された数のレンダラは、性能を著しくスローダウンさせる。この方法の複雑さは、Ｏ（Ｎ＊Ｒ／Ｐ）であり、ここで、Ｎは、ラスタ（画像）におけるピクセルの数、Ｒは、ＧＰＵの数、そしてＰは、コンポジッティングユニット（ＣＰＵｐｉ）の数である。この技法におけるコンポジッティングプロセスは、Ｒ−１回の繰り返し以内に完了される。ＳＧＩのＯｒｉｇｉｎ（オリジン）２０００スーパコンピュータ上でのこの技法のインプリメンテーションにおいては、計算は、ＣＰＵを用いて実行される。このシステムによって行われるコンポジッティングの結果は図４に示される。図４は、この方法のオーバヘッドを説明しており、このシステムに必要とされるコンポジッティング時間は、レンダリングのために必要とされる時間の６倍を超える。
【００１９】
上述された全ての方法は、多量のサブ画像データを一つの画像にコンポジットするための先行技術の方法の問題に対して、未だ、満足すべき解決策を提供していない。
【発明の開示】
【発明が解決しようとする課題】
【００２０】
本発明の目的は、ほとんどリアルタイム観察の範囲内で複数のサブ画像フレームを並列的にレンダリングするための方法およびシステムを提供することにある。
【００２１】
本発明の他の目的は、多量のサブ画像データを単一の画像に同時に構成するための方法およびシステムを提供することにある。
【００２２】
本発明のさらなる目的は、サブ画像データを単一の画像に構成するために必要とされる時間の量を実質的に低減する方法およびシステムを提供することにある。
【００２３】
本発明のまた他の目的は、半導体ベースのデバイスとして有効にインプリメントされ得る大量のサブ画像データを単一の画像に同時に構成するための方法および装置を提供することにある。
【００２４】
本発明のまたさらなる目的は、サブ画像データの多重供給源の間の競争を呈することに基づくサブ画像の構成のための方法および装置を提供することにある。
【００２５】
本発明の他の目的および利点は、説明が進むにつれて明白になるであろう。
【課題を解決するための手段】
【００２６】
一つの局面において、本発明は、複数の数Ｚ１，Ｚ２，…，ＺＲから最大の数を検出するための方法およびシステムに向けられたものである。数の各々は、二つ以上のバイナリセグメントＺｊ（Ｎ−１），Ｚｊ（Ｎ−２），…，Ｚｊ（０）に分割され、前記セグメントのビット長が、それらの有意性のレベルに従って決定され、そして前記セグメントのセットは、それらの有意性のレベルに従って配列され、セグメントの第一のセットＺｊ（Ｎ−１），Ｚｊ（Ｎ−１），…，Ｚｊ（Ｎ−１）は、前記数の最上位セグメントを含み且つセグメントの最終セットＺｊ（０），Ｚｊ（０），…，Ｚｊ（０）は、前記数の最下位セグメントを含む。第一のステップにおいては、同一レベルの有意性を有するセグメントＺ１（Ｋ），Ｚ２（Ｋ），…，ＺＲ（Ｋ）の絶対値が、それらの最上位セグメントの絶対値が最大である数を指定するグループを決定し、そして最下位セグメントについて、それらの絶対値サイズを指示するグレードを、同一レベルの有意性の他のセグメントの絶対値と比較して評価するために、同時に比較される。第二のステップにおいては、セグメントの第二のセットＺ１（Ｎ−２），Ｚ２（Ｎ−２），…，ＺＲ（Ｎ−１）からスタートして、前記グループに対応する数のセグメントのグレードが比較され、且つもしもそれらのグレードが、前記グループにおける他の数の指示に対応する最も高いグレードよりも低いならば、数の指示が前記グループから除去される。前記第二のステップは、最後のセットのセグメントＺ１（０），Ｚ２（０），…，ＺＲ（０）が到達されるまで、または、単一の数が前記グループによって指定されるまで、繰り返される。
【００２７】
オプション的に、前記数は、多重三次元ラスタ画像のピクセルの深さ値である。
【００２８】
最大数の検出は、さらに数をしきい値と比較することと、それらの値が前記しきい値の上または下である数についてのみ最大数の検出を実行することをさらに有していても良い。
【００２９】
同様の検出は、それらの最上位セグメントの絶対値が最も小さい数をグループによって指定することによって、そして、それらのグレードが、前記グループにおける他の数の指示に対応する最小のグレードよりも大きいときはいつも、前記グループから数の指定を除去することによって、最小数を決定するために行われても良い。
【００３０】
本発明の一つの望ましい実施の形態において、全てのセグメントは、同一のビット長からなっている。その代わりになるべきものとしては、一つ以上の最下位セグメントのビット長が、最上位セグメントのビット長よりも大きい。
【００３１】
他の局面において、本発明は、各サブ画像における同一の空間位置に対応するピクセルの深さ値Ｚ１，Ｚ２，…，ＺＲを検査し、そして最大の深さ値を有するピクセルの内容をコンポジットすることによって、複数の三次元サブ画像をコンポジット処理するための方法およびシステムに向けられている。前記深さ値は、二つ以上のバイナリセグメントＺｊ（Ｎ−１），Ｚｊ（Ｎ−２），…，Ｚｊ（０）に分割され、そこでは、前記セグメントのビット長が、それらの有意性のレベルに従って決定され、そして前記セグメントのセットは、それらの有意性のレベルに従って配列され、セグメントの第一のセットＺｊ（Ｎ−１），Ｚｊ（Ｎ−１），…，Ｚｊ（Ｎ−１）は、前記深さ値の最上位セグメントを含み且つセグメントの最終セットＺｊ（０），Ｚｊ（０），…，Ｚｊ（０）は、前記深さ値の最下位セグメントを含む。第一のステップにおいて、同一レベルの有意性を有するセグメントＺ１（Ｋ），Ｚ２（Ｋ），…，ＺＲ（Ｋ）の絶対値は、同時に比較され、そしてそれに応じて、それらの最上位セグメントの絶対値が最大である深さ値を指定するグループが決定され、そしてそれらの絶対値サイズを指示する最下位セグメントについて、同一レベルの有意性の他のセグメントの絶対値と比較して、グレードが評価される。第二のステップにおいて、セグメントの第二のセットＺ１（Ｎ−２），Ｚ２（Ｎ−２），…，ＺＲ（Ｎ−１）からスタートして、前記グループに対応する深さ値のセグメントのグレードが比較され、且つもしもそれらのグレードが、前記グループにおける他の深さ値に対応する最も高いグレードよりも低いならば、深さ値の指示が前記グループから除去される。前記第二のステップは、最後のセットのセグメントＺ１（０），Ｚ２（０），…，ＺＲ（０）に到達するまで、または、単一の深さ値が前記グループによって指定されるまで、繰り返される。
【００３２】
最大数の検出は、深さ値をしきい値と比較すること、およびそれらの値が前記しきい値の上または下である深さ値についてのみ最大数の検出を実行することをさらに有していても良い。
【００３３】
同様の検出が、最小数を決定するために、それらの最上位セグメントの絶対値が最も小さい深さ値をグループによって指定することによって行われても良く、そして深さ値の指定は、それらのグレードが、前記グループにおける他の数の指示に対応する最小のグレードよりも大きいときはいつも、前記グループから除去される。
【００３４】
本発明の他の望ましい実施の形態においては、全てのセグメントは、同一のビット長からなっている。その代わりになるべきものとしては、一つ以上の最下位セグメントのビット長が、最上位セグメントのビット長よりも大きい。
【００３５】
本発明は、単一の集積回路チップ上にインプリメントされていても良く、例えば、それは、ＶＬＳＩインプリメンテーションであっても良い。
【発明を実施するための最良の形態】
【００３６】
本発明は、結合様式での、多重三次元／深さラスタ画像の二次元画像への再コンポジションのための方法およびシステムに向けられている。本発明の望ましい実施の形態によれば、多重グラフィックパイプラインを経由して提供される、レンダリングされたグラフィックスデータ（サブ画像）が、各ラスタ座標にて、観察者に最も近いピクセルについて、解かれる。このタスクは、多重の結合ユニット（ＡＵ）を利用することによって、与えられたラスタ座標にて全てのピクセルについて同時に、各ピクセルにおける自律的結合判断プロセスを行うことによって達成される。コンポジション結果により得られる最終画像は、観察のために出力される。本発明は、概して観察のための画像の階層的組み合わせに基づいている先行技術方法の不適当なオーバヘッドを克服する。
【００３７】
原則として、本発明は、多重供給源の中で最も高い深さ値（Ｚ）についての競争を与える。最も高い深さ値は、多重ＡＵを利用することによって決定されるべきである。各ＡＵは、与えられた他の値に対する局所的な深さ値を連続的に検査し、そして他のＡＵに対する競争をやめるか、さらに競争させるかを自律的に判定する。シーケンシャルな種類からなる在来のソート処理方法と対照的に、本発明による分散処理は、並列的に実行され得て、実質的にコンポジション実行のスピードを上げる。本発明の付加的な優位性は：（ｉ）いかなる長さの数についても実行され得ること；および（ｉｉ）いかなる数の供給源にも、性能を減少することなしに適合することである。
【００３８】
図５は、本発明の構成メカニズムの一般的な図解を提供する。本発明のコンポジションシステム５１は、グラフィックスパイプライン（ＦＢｊ，ｊ＝１，２，３，…，Ｒ）によって提供されるサブ画像データが与えられる。コンポジションシステム５１において、サブ画像のデータ（Ｚｊ，Ｐｊ）は、ＡＵ（ＡＵｊ，ｊ＝１，２，３，…，Ｒ）に対応する一セットのＲに提供され、それらの各々は、画面の同一のＸ／Ｙ座標における画像ピクセルを取り扱うことができる。各競争するデータは、内容Ｐｊ（例えばカラー、透明、ここではＲＧＢ−値とも称される）およびピクセルの深さＺｊから構成される。
【００３９】
Ｚ−値は、ＡＵによって受信され、そして深さ競争バス（ＤＣＢ）上に導入される。ＤＣＢラインの論理状態は、ＡＵによって検知され、該ＡＵは、それに応じてキャリーインおよびストップマークベクトルを生起し、これらベクトルは、それらが最も高いＺ−値を保持しているかどうかを決定すべく、プロモーションマトリクス（ＰＭ）５３と共に使用される。競争するデータに関する判定は、結合メカニズムに基づき、且つＤＣＢ上の他のＡＵとの比較によって、各ＡＵにおいて局所的に実行される。最終的に、最も近いピクセル（すなわち、最も高いＺ−値）を保持しているＡＵは、ピクセルのカラーＰｊ（ＲＧＢ−値）を、最終画像５５を構成する最終ラスタ５０にわたすことが可能とされる。
【００４０】
深さ競争バス（ＤＣＢ）構造は、図７Ａおよび図７Ｂに示され且つ説明されるように、ワイアド−アンド論理をインテリジェントに配備する。ワイアド−アンド論理７０の機能性は、通常の論理アンド機能の機能性と同様である。しかしながら、ワイアド−アンド機能は、単一の電気的ポイントに多数の出力を導入し、その点で通常の論理アンドゲートはその信号を他のいかなる出力とも絶縁されている他のゲートに出力しなければならない。図７Ａに説明されているように、入力のいずれか１つにおける論理「０」状態は、出力ライン上を論理「０」状態とさせる。
【００４１】
ＤＣＢ上の比較プロセスは、ビット優位性連続方式にて実行される。図７Ｂに示されるように、グラフィックパイプライン（ＦＢｊ）を経由して提供される各Ｚ−値（Ｚ１，Ｚ２，Ｚ３，…，ＺＲ）は、それぞれのＡＵ（ＡＵｊ）内に供給される。ＤＣＢのラインは、それらの優位性のレベルに従って、Ｎ−バイナリのＺ−値（Ｚｊ（ｉ），ｉ＝０，１，２，…，Ｎ）の各セグメントのワイアド−アンド結果を出力するために用いられる。このようにして、ＤＣＢ（０）ラインは、Ｚ−値（Ｚｊ（０））の最下位セグメント（ＬＳＳ、非第一のセグメントとも称される）上で実行されるワイアド−アンド論理の出力として使用され、そして、ＤＣＢ（Ｎ−１）ラインは、Ｚ−値（Ｚｊ（Ｎ−１））の最上位セグメント（ＭＳＳ、第一のセグメントとも称される）上で実行されるワイアド−アンド論理の出力のために使用される。
【００４２】
比較プロセスは、Ｚ−値の最上位ビットからスタートする、順序付けられた様式で行われ、そしてそれは、Ｚ−値の最下位ビットで終了させられる。競争は、ＡＵが、ＤＣＢ（Ｎ−１）の最も上のライン上に最上位ビット（ＭＳＢ）を出力したときにスタートする。このプロセスの期間は、いつも、ｌｏｇ２｜Ｚ｜の一定時間を要し、ここで、｜Ｚ｜は、場面の深さ領域、すなわちＺ−値のビット長である。その結果として、先行技術の方法の多重ステージ構造は、本発明の方法に従った単一のステージによって置換される。先行技術の方法のＯ（ｌｏｇ２Ｚ＊ｌｏｇ２Ｎ）の実行の複雑さは、本発明の方法によってＯ（ｌｏｇ２Ｚ）に有意的に低減される。
【００４３】
ＭＳＳビットＺｊ（Ｎ−１）の比較において、ＤＣＢラインＤＣＢ（Ｎ−１）上に、単一の、またはそれらのいくつかの、論理「０」状態を、置くことは、前記ライン上を「０」論理状態に強制する。ＤＣＢライン上に「１」論理状態が置かれ、且つ前記ライン上で結果的に「０」論理状態が検知されるＡＵは、それらの現在のＺ−値についてのそれらの競争を終結させ、さもなければ、該ＡＵは、表１に例示されたように、次に続くビット（優位性が低い）に対するそれらの競争を続けることが許可される。
【００４４】
（表１）
ＭＳＳビットＺｊ（Ｎ−１）の比較
┌───────────┬───────────┬───────────┐
│ 強制値 │ＤＣＢラインの状態 │ 判 定 │
├───────────┼───────────┼───────────┤
│ 1 │ 0 │ ストップ │
├───────────┼───────────┼───────────┤
│ 1 │ 1 │ 継 続 │
├───────────┼───────────┼───────────┤
│ 0 │ 0 │ 継 続 │
├───────────┼───────────┼───────────┤
│ 0 │ 1 │ 継 続 │
└───────────┴───────────┴───────────┘
上の表１に示された最後のケースは、ＤＣＢライン上の論理「０」状態の強制は、このラインを論理「０」状態に強制しなければならないから、実際に可能でないことに留意されるべきである。
【００４５】
Ｚ−値が競争を継続すべきであるかどうかについての判定は、ＤＣＢラインの論理状態を検知することにより各ＡＵによって確立される。最後に残存しているＡＵが、競争に「勝つ」。ＡＵの比較論理がバス上により高いＺ−値を識別したとき、それ自体を競争から引き離す。さもなければ、バス上に残った値が最も高いＺ−値を有するものとなるまで競争を続ける。
【００４６】
図８は、ＡＵの動作を説明するブロック図である。第ＫのＺ−値（Ｚｋ（Ｎ−１），Ｚｋ（Ｎ−２），…，Ｚｋ（０））は、１セットのゲート（９０、図９に示されている）を経由してＤＣＢに結線されており、ピクセル値ＰＫは、ゲート８４を経由してマージされたＦＢ５０へ通るゲート制御がされる。結合論理８０は、ワイアド−アンド機能を有効とし、ユニットの競争を制御し、そしてＰＭ５３の一つから勝ちの通知８６（ＷＫ）を受けたときに、有効化指示８１を利用してＲＧＢ−値ＰＫがＦＢ５０へ通過することを許可する。
【００４７】
ＡＵは、Ｚ−値（Ｚｋ（ｉ），ｉ＝０，１，２，…，Ｎ−２）のＬＳＳについて結合ロジック８０によって生成され且つその後にＰＭ５３に供給されたストップマーク（ＳＭ）ベクトル８５ＳＭｋ＝（ＳＭｋ（０），ＳＭｋ（１），…，ＳＭｋ（Ｎ−２））を生成する。キャリーアウト指示（Ｃｋ（Ｎ−１））もＡＵｋによって生起され、Ｚ−値ＺｋのＭＳＳ（Ｚｋ（Ｎ−１））が競争の第一のステージを勝ったかどうかを指示する。
【００４８】
結合論理８０は、種々の方法でＡＵの競争機能性を拡張すべく設計されても良いことに留意されるべきである。例えば、到来するＺ−値の逆数が競争のために（全てのＡＵにおいて）使用されても良く、そしてそのようなケースにおいては、ＡＵ間の競争は、最小の深さ値を決定することに基づいて行われるであろう。その代わりとして、ＡＵのＺ−値入力上に、しきい値をむしろ配置し、そしてこのようにして、それら２つの値の、どちらが、しきい値より大きいか、またはしきい値より小さいか、という競争を可能とするようにしても良い。
【００４９】
局所ＡＵにおいて、各Ｚ−値Ｚｊは、ＮセグメントＺｊ（Ｎ−１），Ｚｊ（Ｎ−２），…，Ｚｊ（０）にセグメント化され、ここで、第（Ｎ−１）のセグメントＺｊ（Ｎ−１）は、ＭＳＢを保持し、そして第（０）のセグメントＺｊ（０）は、ＺｊのＬＳＢを保持している。例えば、３つのセグメント（すなわち。Ｎ＝３，Ｚｊ（２），Ｚｊ（１），およびＺｊ（０））に処理される３２ビットの長さのＺ−値数を仮定しよう、そこでは第一および第二のセグメント（Ｚｊ（２）およびＺｊ（１））は、各々８ビットの長さで且つ第三のセグメント（Ｚｊ（０））は、１６ビットの長さである。競争の第一のステージにおいて、Ｚ−値（Ｚｊ（２），ｊ＝１，２，…，Ｒ）のＭＳＳ（第一のセグメント）に従って一つ以上の予備的な勝者が決定され、且つストップマークグレーディング（ＳＭｊ（ｉ），ｉ＝０，１，２，…，Ｎ−２、例えばＮ＝３についてＳＭｊ（０）およびＳＭｊ（１））がＺ−値（Ｚｊ（ｉ），ｉ＝０，１，２，…，Ｎ−２、例えばＮ＝３についてＺｊ（２）およびＺｊ（１））の全ての他のセグメント（ＬＳＳ）の間の競争に従って確立される。競争の次のステップにおいて、第一のステージを勝利したＺ−値に対応する第二のセグメント（Ｚｊ（Ｎ−２）例えばＺｊ（１））について確立された、ストップマークグレーディングＳＭＫ（Ｎ−２）（例えば、ＳＭＫ（１））は、それらのＺ−値のいずれを競争させ続けるかを決定すべく検査される。次のセグメント（ＳＭｊ（ｉ），ｉ＝０，１，２，…，Ｎ−３、例えばＮ＝３についてＳＭｊ（０））について確立されたストップマークグレーディングによって、最後のセグメント（ＬＳＳ、Ｚｊ（０））の結果に従って最も高いＺ−値が決定されるまで、同一のプロセスが実行される。
【００５０】
各ＡＵは、全てのセグメント（Ｚｊ（ｉ），ｉ＝０，１，…，Ｎ−１）を並列に処理する。ＡＵは、ＭＳＢからＬＳＢまでに使用されたセグメンテーションに従って、全てのＺ−値の数を制御する。ＡＵ論理が、第一のセグメントＺｊ（Ｎ−１）を競争させ且つそのキャリーアウトＣ（Ｎ−１）をＰＭ（Ｎ−１）（図６）に提示すると同時に、第二のセグメントＺｊ（Ｎ−２）を競争させ且つそのストップマークＳＭ（Ｎ−２）をＰＭ（Ｎ−１）に提示する。同様に、Ｚ−値の第三のセグメントＺｊ（Ｎ−３）を競争させ且つストップマークグレーディングＳＭ（Ｎ−３）をＰＭ（Ｎ−２）に提示するなどする。
【００５１】
セグメント長は、競争性能を最適化すべく選定される。例えば、３２ビットの長さのＺ−値について、それぞれ、８、８、および１６ビットの、Ｚｊ（２）、Ｚｊ（１）、およびＺｊ（０）の、三つのセグメントで処理され、第二のセグメントについてのＳＭベクトルＳＭ（１）は、第一のセグメントＺｊ（２）が処理されている間に準備され得て、そして第三の（最長の）セグメントについてのＳＭベクトルＳＭ（０）は、二つの先行するセグメントＺｊ（２）およびＺｊ（１）のために必要とされる時間期間を利用して同時的に準備され得る。
【００５２】
このプロセスは、図６に説明されている。数字６１〜６４は、Ｚ−値のセグメンテーションに従ってＡＵによって生成される指示を概略的に指定している。Ｚ−値（Ｚｊ（ｉ），ｉ＝０，１，２，…，Ｎ−２）のＬＳＳを供するＮ−１個のＰＭ５３が存在する。ＰＭ５３は、対応する（第ｉの）セグメントにについてＡＵによって生成されるそれぞれストップマークベクトルＳＭ（ｉ）＝（ＳＭ１（ｉ），ＳＭ２（ｉ），…，ＳＭＲ（ｉ））に従って決定されるキャリーアウトベクトルＣ（ｉ）（Ｃ（Ｎ−２），Ｃ（Ｎ−３），…，Ｃ（１））、および従前のステージにおいてＰＭ（ｉ−１）によって生起されるキャリーアウトベクトルＣ（ｉ−１）を生成する。ＰＭによって生成される付加的な信号は、（ａ）競争の各ステージにおいて勝ったＺ−値を指定する勝者指示Ｗｊ、および（ｂ）一旦単一の勝者が決定されると生成され、後続のマトリクスが、それらの競争を継続するのを防止する「競争ストップ」信号である。
【００５３】
Ｚ−値の第一のセグメントＺｊ（Ｎ−１）＝（Ｚｊ，０（Ｎ−１），Ｚｊ，１（Ｎ−１），…，Ｚｊ，ｎ−１（Ｎ−１））についてのキャリー指示を生成するためのＡＵ論理が、図９に示されている。ワイアド−アンドの機能性を活用すべく、各ビットの反転状態が、論理ナンドゲート９０を経由してＤＣＢラインに導入される。各検査されたビットＺｊ，ｋ（Ｎ−１）について、それぞれのＤＣＢラインの論理状態および検査されたビットＺｊ，ｋ（Ｎ−１）の論理状態に従って、Ｚ−値が次のビットレベルＺｊ，ｋ＋１（Ｎ−１）において競争を継続するかどうかを決定するために、論理オアゲート９２が、使用される。各ビットステージＺｊ，ｋ（Ｎ−１）は、論理アンドゲート９２を経由して次のビットステージＺｊ，ｋ（Ｎ−１）を制御する。キャリーアウト指示Ｃｊ（Ｎ−１）は、全てのｎビットステージが競争を生き残った場合にのみ生成される。キャリーアウト指示は、図６に示されたＰＭ（Ｎ−１）プロモーションマトリクスに対して提供され、そしてこのようにして、次のセグメントにおけるＺ−値Ｚｊのさらなる競争を可能としている。
【００５４】
同時に、ＡＵが、Ｚ−値の第一のセグメントを検査している間に、ＬＳＳ（Ｚｊ（ｉ），ｉ＝０，１，２，…，Ｎ−２）の各々もワイアド−アンド論理によって検査される。しかしながら、ＬＳＳの検査において、第一のセグメントについて生成されたキャリーアウト指示Ｃｊ（Ｎ−１）の代わりに、ストップマークＳＭｊ（ｉ）（ｉ＝０，１，２，…，Ｎ−２）信号が生成される。各ストップマークＳＭｊ（ｉ）信号は、ストップマークベクトルＳＭ（ｉ）の一部としてのＰＭ（ｉ）プロモーションマトリクスにそれぞれ送られる。
【００５５】
ストップマークＳＭｊ（ｉ）は、競争から全Ｚ−値Ｚｊがもしかすると省かれるかもしれないそれぞれのセグメントＺｊ（ｉ）の「弱い」ビットを指示する。ＬＳＳについてのＳＭ信号（ＳＭｊ（ｉ），ｉ＝０，１，２，…，Ｎ−２）を生成するための論理は、図１０に示されている。主として、この論理は、キャリーアウトベクトルＣ（Ｎ−１）の生成のために使用された論理と類似している。しかしながら、各ビットステージが、インバータ９９を経由して、ストップマーク信号「ストップ１」−「ストップ（ｎ＋１）」を生成し得ることにおいて異なっている。各ＬＳＳセグメント（Ｚｊ（ｉ），ｉ＝０，１，２，…，Ｎ−２）について、ただ一つのストップマーク信号ＳＭｊ（ｉ）が生成される。最も高い可能性のストップマーク信号「ストップ（ｎ＋１）」は、検査されたセグメントは、いかなるそのワイアリング比較においても消滅しないことを示している。
【００５６】
結合マトリクスの論理は、ストップマークベクトルＳＭｊ（ｉ）および従前に生成されたキャリーアウトベクトルＣ（ｉ＋１）を取り扱い、そして新たなキャリーアウトベクトルＣ（ｉ）を生成する。この新たなキャリーアウトベクトルＣ（ｉ）において、これまで競争に生き残ったそれらのＡＵのみが参加している。もしもちょうど単一のＡＵが生き残ったならば、それが最終勝者になり、競争プロセスを停止する。そうでなければ、次のＰＭ（ＰＭ（ｉ−１））が、単一の勝者が残るまで同一のタスクを実行する。
【００５７】
図１１は、ＰＭ（縮小されたケース）の論理を説明している。平易化のために、図１１は、二つのＡＵ（Ｒ＝２）を供する第ｉのＰＭ（すなわちＰＭ（ｉ））を図解しており、そこでは第ｉのセグメントは４ビットの長さである（すなわち、５つのストップマーク、ＳＭｊ（ｉ）＝（ＳＭｊ，１（ｉ），ＳＭｊ，２（ｉ），…，ＳＭｊ，５（ｉ）））。ストップマークベクトルＳＭ１（ｉ）およびＳＭ２（ｉ）の各々は、ＦＦ１１０および１１１の一方に設定する。一つよりも多いＦＦ１１０および１１１が、並んで「オン」状態になることはできない。勝利指示Ｃｊ（ｉ＋１）が従前のＰＭ（ＰＭ（ｉ＋１））から受信されたストップマークベクトルは、より高い数を有し且つ従前のＰＭ（ＰＭ（ｉ＋１））において勝利が指示されたキャリーアウトを有する他のストップマークが存在しなければ、そして存在しない場合にのみ、キャリーアウトを生成するであろう。
【００５８】
ＰＭにおける従前の縦列の操作は、最も高いレベルを有するストップマーク指示がそこで受信され且つ対応するキャリーアウト指示が従前のＰＭからそのために受信される、縦列の論理オアゲート１１９を介して集められた論理アンドゲート１１７から対応する指示を受け取ると同時に、抑止機能１１３を介して抑止される。もしもＰＭによって受信されたストップマークが同一の優位性からなっている（例えば、ＳＭ１，４（ｉ）およびＳＭ２，４（ｉ））ならば、キャリーアウト指示Ｃ１（ｉ）およびＣ２（ｉ）がバッファ１１２を経由して次のＰＭ（ＰＭ（ｉ））に供給される。
【００５９】
ただ一つの勝利信号Ｗ（ｉ）のみが、ＰＭの一つによって生起され得る。検出部１１５が、単一の勝者が、現在のステージで決定されたことを指示するときはいつも、抑止機能１１３は、次のステージＰＭ（ｉ−１）のＰＭによってさらなる処理を抑止するであろうストップ指示Ｓｔｏｐ（ｉ）を生起する。ストップ信号が抑止機能（例えば、Ｓｔｏｐ（ｉ＋１））によって受信されたときはいつも、ゲート１１７を抑止することおよび次のＰＭの抑止機能へストップ指示（例えばＳｔｏｐ（ｉ））を発行することによって、現在およびそれに続くＰＭの機能を、抑止する。
【００６０】
例えば、ＡＵ１が、ストップマーク４、ＳＭ１，４（ｉ）、を設定し、ＡＵ２が、ストップマーク２、ＳＭ２，２（ｉ）、を設定すること、そして従前のＰＭから受信される両方のキャリー指示、Ｃ１（ｉ＋１）およびＣ２（ｉ＋１）、が、競争の従前のステージにおける勝利を指示することと仮定する。そのようなケースにおいては、ＡＵ１において競争するＺ−値が勝ち、抑止機能１１３を経由して縦列１〜３を抑止し、そしてキャリーアウトＣ１（ｉ）のみを生成する。単一のキャリーアウトの検出は、現在のステージにおける単一の勝者を指示し、結果は、ＡＵ１へのＷ１ライン上に設けられる単一キャリーアウト検出部１１５を経由して勝利通知信号Ｗ（ｉ）を生成することである。勝利ＡＵは、それからそのＲＧＢ値ＰＫをＦＢ５０へ供給することが可能とされる。
【００６１】
もしも、例えば、ＡＵ１およびＡＵ２が、両方ともストップマーク４、ＳＭｊ，４（ｉ）、をオンとし、キャリー指示Ｃ１（ｉ＋１）およびＣ２（ｉ＋１）が両Ｚ−値が従前のステージで勝ったことを指示すると、そのときは、次のＰＭ（ＰＭ（ｉ＋１））へ転送される二つのキャリーアウトＣ１（ｉ）およびＣ２（ｉ）が、現在のステージにおける勝ちをも指示するであろう。
【００６２】
図１２は、ＡＵａからｅに属するＲ＝５のＺ−値（Ｚ１，Ｚ２，Ｚ３，Ｚ４，およびＺ５）の競争プロセスを例示している。この例において、Ｚ−値の深さ寸法は、３２ビットからなり、そして深さ値は、各８ビットのＮ＝４セグメント（Ｚｊ（３），Ｚｊ（２），Ｚｊ（１），およびＺｊ（０））にセグメント化される。（プロモーションマトリクスを有さない）シーケンシャルなワイアド−アンドプロセスが、３２時間単位を要するのに、この例における合計処理時間は、１１時間単位である。
【００６３】
この例における第一のセグメントにおいて、ＭＳＳ，Ｚ２（３），Ｚ３（３），およびＺ５（３）は、全て等しく且つＺ１（３）およびＺ４（３）よりも大きく、そしてそれゆえ対応するＣ２（３），Ｃ３（３），およびＣ５（３）キャリーアウト信号のみが、Ｚ−値Ｚ２，Ｚ３，およびＺ５が第一のステージを勝ったことを指示すべく生起される。同時に、ＬＳＳのＳＭベクトルが、ＡＵによって生起される。
【００６４】
Ｚ−値の第二のセグメントについて、Ｚｊ（２）数の６つのＭＳＢは全て等しい。「ストップ７」ＳＭは、Ｚ１（２）について指示され、そして、セグメントにおける全ての他のＺ−値の第７ビットの状態が、「１」（Ｚ２，７（２）＝Ｚ３，７（２）＝Ｚ４，７（２）＝Ｚ５，７（２）＝１）であるのに、その第７ビットの状態は「０」（Ｚ１，７（２）＝０）であるからさらなる競争はしない。「ストップ８」ＳＭは、Ｚ３（２）について指示され、そして、それらの競争がこのビットステージにおいて続行する値の第８ビットの状態が、「１」（Ｚ２，８（２）＝Ｚ４，８（２）＝Ｚ５，８（２）＝１）であるのに、その第８ビットの状態は「０」（Ｚ３，８（２）＝０）であるから、また、さらなる競争を終了する。それゆえ、「ストップ９」ＳＭは、セグメントにおけるビットステージはどれもこれもそれらが勝つから、Ｚ２（２），Ｚ４（２），およびＺ５（２）についての指示が生起される。したがって、ＰＭ（２）におけるＳＭ（２）およびＣ（３）ベクトルの処理は、次のＰＭ、ＰＭ（１）、に対するキャリーアウト指示Ｃ２（２）およびＣ５（２）を生起するであろう。
【００６５】
Ｚ−値の第三のセグメントについて、「ストップ２」ＳＭは、Ｚ５（１）について指示され、Ｚ１，２（１）＝Ｚ２，２（１）＝Ｚ３，２（１）＝Ｚ４，２（１）＝１であるのに、Ｚ５，２（１）＝０およびＺｊ，１（１）＝０であるから、それはいかなるさらなる競争をもストップし、そして「ストップ９」ＳＭは、それらの６つのＭＳＢは同等であるから、Ｚ１（１），Ｚ２（１），Ｚ３（１），およびＺ４（１）について指示される。したがって、ＰＭ（１）におけるＳＭ（１）およびＣ（２）ベクトルの処理は、最後のＰＭ、ＰＭ（０）、に対する単一キャリーアウト指示Ｃ２（１）を生起するであろう。ＰＭ（１）、が単一の勝者を決定したから、その検出部１１５は、対応する指示Ｗ２を勝ったＡＵ、ＡＵ２、に対して生起し、そのＲＧＢ値Ｐ２をＦＢ５０において利用可能とする。それゆえに、ＰＭ（１）の抑止機能は、最後のＰＭ、ＰＭ（０）、におけるさらなる処理を抑止するストップ（０）指示を生成する。
【００６６】
第三のセグメントの処理は、実行されない。それにもかかわらず、ＡＵによってＳＭ（０）指示が生起される。Ｚ１，１（０）＝Ｚ２，１（０）＝Ｚ３，１（０）＝Ｚ４，１（０）＝１であるのに、Ｚ５，１（０）＝０であるから、「ストップ１」ＳＭは、Ｚ５（０）について指示される。ｒ＝２，３，４，５および６について、Ｚ１，ｒ（０）＝Ｚ２，ｒ（０）＝Ｚ３，ｒ（０）＝Ｚ４，ｒ（０）＝１、Ｚ３，７（０）＝Ｚ４，７（０）＝０、そしてＺ１，７（０）＝Ｚ２，７（０）＝１であるから、「ストップ７」ＳＭは、Ｚ３（０）およびＺ４（０）について指示される。それゆえに、Ｚ２，８（０）＝０およびＺ１，８（０）＝１であるから、「ストップ８」ＳＭは、Ｚ２（０）について指示され、そして「ストップ９」ＳＭは、Ｚ１（０）について指示される。
【００６７】
全てのセグメントは、長さについて一様に維持されるから、セグメントのＳＭ結果をマージングすることによって、競争時間は、さらに縮減され得る。そのような縮減は、従前のＰＭからのキャリーアウト指示の到着に先立って結果のクラスタリングを可能とする。このアプローチは、複雑さをＯ（ｌｏｇ２Ｚ）からＯ（（ｌｏｇ２Ｚ）／ｋ）（但しｋは折り畳み係数）に低減する。例えば、Ｚ＝２３２と仮定すると、シーケンシャルなワイアド−アンドプロセスは、Ｏ（３２）の複雑さを要する。しかしながら、各８ビットの４個のＰＭを用いれば、数の後半は、前半を処理するときに「折り畳まれる」。結果として、複雑さは、Ｏ（８＋１＋１）に低減される。このケースでは、折り畳み係数ｋは、３２／１０＝３．２である。より長い数、例えば６４ビットのケースにおいては、複雑さの程度は、顕著には変化されず：Ｏ（８＋１＋１＋１）である。この並列のアプローチの利点は、Ｚ−値数のいかなるビット長にも、高い効率を維持しつつ、ほとんど同様の短時間に処理され得ることにある。
【００６８】
図１３は、本発明の望ましい実施の形態のチップインプリメンテーション１４０（例えばＶＬＳＩ）を説明するブロック図である。この例は、６つの異なるＧＰＵから６つのＦＢをコンポジットするためのインプリメンテーションを図解している。このインプリメンテーションは、複数のサブ画像ユニット（ＳＩＵ）によって複数のサブ画像ピクセルを同時に構成するためのコンポジット処理ユニットを実現する。各ＳＩＵは、ＧＰＵの数に対応するＡＵのセット、ＤＣＢ、ＰＭ、および制御論理１４１を具備している。各ＳＩＵにおける制御論理１４１は、それぞれのサブ画像の座標と符合するピクセルのみを、ポート〜ポート６入力ポートを介して取り込まれるデータ入力ストリームと区別する。各ＳＩＵは、サブ画像の一つのＲＧＢデータを出力し、該データは、出力ポート１４２を介してＦＢ５０に出力される。
【００６９】
全コンポジットプロセスは、各ＦＢを１６個のサブ画像に分割することによってさらに並列化される。例えば、１０２４×１０２４ピクセルの分解能を有する画像について、各サブ画像ユニット（ＳＩＵ）は、６４×６４サブ画像（画像の１／１６）を処理する。もしも、例えば、ピクセルのカラーデータが２４ビットの長さであれば、ＳＩＵのスタックの出力は１２Ｋバイトの勝利したピクセルカラーデータを含んでいる。
【００７０】
先行技術に反して、本発明は、図５において説明されたように、いかなる数のＧＰＵ、Ｒ、についての単一のマージ処理ステップを実行することが可能である。先行技術方法の階層的構造は、本発明においては、特有の、平坦な、単一ステップ構造によって置き換えられている。この新規な構造の性能は、並列処理のレベル、すなわち参加するＧＰＵの数、に敏感ではない。コンポジション時間は、単一比較まで事実上低減され、そしてどんな任意数のＧＰＵも、全体の性能に対する犠牲なしに、許容される。
【００７１】
上述の例および記述は、もちろん、説明の目的のためにのみ提供されており、そしていかなる点においても発明を限定することを意図していない。当業者によって認められるであろうように、本発明は、非常に多種多様の方法において、上述されたものとは異なる技術を採用して、本発明の範囲を逸脱することのない全てを実施され得るものである。
【図面の簡単な説明】
【００７２】
【図１】複数のサブ画像データの単一の画像へのマージ処理を図解するブロック図である。
【図２Ａ】先行技術の階層的コンポジット処理方法を図解するブロック図である。
【図２Ｂ】階層的コンポジット処理性能の並行処理制限を図表的に図解している。
【図３Ａ】先行技術の共有メモリコンポジット処理方法を示すブロック図および擬似コードを示している。
【図３Ｂ】先行技術の共有メモリコンポジット処理方法を示すブロック図および擬似コードを示している。
【図４】先行技術の共有メモリコンポジション法の性能を図表的に図解している。
【図５】本発明の望ましい実施の形態を例示するブロック図である。
【図６】本発明に従ったプロモーションシステムを図解するブロック図である。
【図７Ａ】本発明のワイアド−アンド機能の原理を具体的に説明するブロック図である。
【図７Ｂ】Ｎ個のバイナリ数のワイアド−アンド競争の原理を図解するブロック図である。
【図８】結合ユニットの望ましい実施の形態を図解するブロック図である。
【図９】第一のセグメントの論理を概略的に図解するブロック図である。
【図１０】非第一のセグメントの論理を概略的に図解するブロック図である。
【図１１】低減されたプロモーションマトリクスを概略的に図解するブロック図である。
【図１２】５個の深さ値の競争プロセスを例示している。
【図１３】本発明の望ましい実施の形態のチップインプリメンテーションを図解するブロック図である。
【技術分野】
【０００１】
本発明は、コンピュータグラフィックスレンダリングの分野に関する。より詳細には、本発明は、多重三次元／深さラスタ画像の二次元画像への再コンポジションのための方法および装置に関する。
【０００２】
［関連出願へのクロスリファレンス］
この出願は、その全開示が引用によりここに組み込まれる、２００３年１月２８日に出願された米国仮特許出願第６０／４４２，７５０号の恩恵を請求する。
【背景技術】
【０００３】
多くのタイプの情報処理インプリメンテーションと同様に、コンピュータグラフィックスレンダリングの性能を向上させるべく努力が続けられている。レンダリング性能を向上させる魅力的な試みの一つは、単一の場面を並列にレンダリングすべく一緒に利用される多重のグラフィック処理ユニット（ＧＰＵ）を用いることに基づいている。
【０００４】
多重ＧＰＵを用いてグラフィックデータをレンダリングするための三つの有力な方法がある。それらは、各ＧＰＵが次の後続フレームをレンダリングする時間領域コンポジションと、各ＧＰＵが各フレームのピクセルのサブセットをレンダリングする画面空間コンポジションと、各ＧＰＵがデータベースのサブセットをレンダリングする場面ベースコンポジションとを含んでいる。
【０００５】
時間領域コンポジションにおいては、各ＧＰＵは、次の後続フレームをレンダリングする。この方法の大きな不都合は、各ＧＰＵが全フレームをレンダリングすることを有することにある。それゆえ、各フレームがレンダリングされるスピードは、単一のＧＰＵのレンダリング速度に制限される。多重ＧＰＵは、より高いフレーム速度を可能とすると同時に、ユーザの入力に対するシステムの応答時間における時間領域コンポジションアプリケーションにおいて遅延が分与され得る（すなわち、待ち時間の縮減）。いかなる与えられた時間においてもレンダリングされたフレームを表示するのに、他の全てのＧＰＵが、連続する一連のフレームの一つをレンダリングするプロセス中にある間に、ただ一つのＧＰＵが従事させられるから、これらの遅延が典型的に生ずる。一定のフレーム速度を維持するために、システムは、ユーザの入力を最初に受信した特定のＧＰＵがシーケンスを通して周期動作するまでユーザの入力に作用するのを遅延させ、そしてそのレンダリングされたフレームを表示するのに、再び従事する。実際的なアプリケーションにおいて、この条件は、システムに使用されるＧＰＵの数を制限させる。
【０００６】
時間領域コンポジションアプリケーションに関連する他の困難性は、これらのアプリケーションにおいては、各ＧＰＵが、画像レンダリングのために使用される全データへのアクセスを得ることができなければならないから、各ＧＰＵがアクセスすることができなければならない大きなデータのセットに関連する。これは、例えば、単一のコピーをアクセスすることの多重の試みによって生ずる可能性がある衝突を防止するために大きなデータセットの多重コピーを維持することによって達成される。
【０００７】
画面空間コンポジションアプリケーションは、各ＧＰＵが、どのグラフィックエレメントが画面のその部分内に属するかを決定すべくデータベース全体を検査しなければならないから、大きなデータセットの処理における同様の問題を有する。この場合におけるシステム待ち時間は、単一のＧＰＵによって単一のフレームをレンダリングするために必要とされる時間に等しい。
【０００８】
本発明がそれに関連する、場面コンポジション法は、上述された待ち時間の問題、データセットの多重コピーを維持することの必要性、および各ＧＰＵによるデータベース全体を取り扱うことに関連する問題によるものを排除する。
【０００９】
場面コンポジション法は、莫大な量の幾何学的データのレンダリングを必要とするアプリケーションに良く適合する。典型的には、それらは、ＣＡＤアプリケーション、および空間におけるそれらの三次元的位置がユーザの対話的制御下にないようにデータが予め設計されていることを意味する、「ビューワ」として論じられる、類似の視覚的シミュレーションアプリケーションである。しかしながら、ユーザは、観察者の位置である、ビュー方向およびグラフィックデータの縮尺を対話的制御している。ユーザは、また、データのサブセットの選択およびそれがレンダリングされる方法を制御していても良い。このことは、基礎をなすデータの画像ライティング、彩色、透明性および他の視覚的特性の影響を操作することを含んでいる。
【００１０】
ＣＡＤアプリケーションにおいては、データが、通常は、ディスプレイリストまたは頂点アレイにおける膨大な量の幾何学的実体からなるので、非常に複雑になる傾向にある。それゆえ、単一フレームの構成時間は、非常に長く（例えば典型的には、２千万個の多角形群について０．５秒に）なる傾向にあり、結果として全体のシステム応答をスローダウンさせる。
【００１１】
場面コンポジション法（例えば、オブジェクトベースのデコンポジション法）は、多重ＧＰＵの間のデータサブセットの分布に基づいている。データサブセットは、ＧＰＵパイプラインにおいてレンダリングされ、そしてフラグメント（サブ画像ピクセル）のフレームバッファ（ＦＢ）に変換される。多重ＦＢのサブ画像は、表示されるべき最終画像を生成するためにマージされなければならない。図１に示されるように、最終画像のＸ／Ｙ平面における各ピクセルについて、ＦＢのサブ画像によって与えられる異なる画像深さに対応する種々のとり得る値が存在する。
【００１２】
各ＧＰＵは、各画面の（Ｘ／Ｙ）座標にて多くて一つのピクセル１２を生起する。この構成されたピクセル１２は、隠れた面の除去および影付けおよび透明性を実現するための混色の結果である。ＧＰＵによって生成されたピクセル１２の各々は、（観察者に最も近い）最高のＺについて解かれるべき、異なる深さ量（Ｚ−値）を保持する。ただ一つのピクセルのみが最終的に通ることが許可される。各ＦＢのサブ画像のマージは、ＦＢによって与えられる種々の可能性のあるピクセル値１２からどの値（１０）が、観察者の視点において視認可能な最近点をあらわすかの決定の結果である。しかしながら、一つの単一のラスタへの部分的場面データのマージングは、依然として先行技術における性能のボトルネックを引き起こしている。
【００１３】
先行技術における並列処理のレベルは、多重ラスタのコンポジション性能の不足によって制限されている。二つのラスタのコンポジションは、隠れ面除去を行うためのハードウェア技法であるＺ−バッファリングによって通常は行われる。先行技術の在来の方法においては、Ｚ−バッファリングは、一度に二つのラスタのみのマージングを許容する。
【００１４】
在来のハードウェアコンポジッティング技法は、図２Ａに例示されたように、典型的には、ラスタのペアの繰り返し照合プロセス（Ｓ．Ｍｏｌｎｅｒの「高速レンダリングのためのＺ−バッファエンジンの結合」（Ｃｏｍｂｉｎｉｎｇ Ｚ−ｂｕｆｆｅｒ Ｅｎｇｉｎｅｓ ｆｏｒ Ｈｉｇｈｅｒ−Ｓｐｅｅｄ Ｒｅｎｄｅｒｉｎｇ）、Ｅｕｒｏｇｒａｐｈｉｃｓ、１９８８年）、またはパイプライン技法（Ｊ．Ｅｙｅｓ他の「ピクセルフロー：現実化」（ＰｉｘｅｌＦｌｏｗ：Ｔｈｅ Ｒｅａｌｉｚａｔｉｏｎ）、ＡＣＭ Ｓｉｇｇｒａｐｈ、１９９７年）に基づいている。これらの技法のマージングは、Ｓステージの、ｌｏｇ２Ｒステップ以内で実行される。ここで、Ｒは、レンダリングＧＰＵの数である。照合のケースにおいては、各そのようなコンパレータ（ＭＸ）における二つの深さ寸法の間の比較を達成するために必要とされる時間は、ｌｏｇ２Ｚである。ここで、Ｚは、場面の深さ領域である。例えば、ピクセルあたり２４ビットを有する典型的な深さバッファについては、二つのＺ−バッファの間の比較は、典型的には、２４の時間クロック内に行われる。
【００１５】
先行技術の技法において、一度に、二つのＺ−バッファのみのマージングが許容され、多重ラスタのコンポジションは、階層的な形式でなされる。これらのコンポジション構造の複雑さは、Ｏ（ｌｏｇ２Ｒ）であり、グラフィックパイプラインの数、性能がＲによって高度に影響されるようにさせる。Ｒの値を増大させるために、コンポジッティング時間が、リアルタイムアニメーションのための割り当てられたタイムスロットを超える。実際的なアプリケーションにおいては、この条件は、システム内に使用されるＧＰＵの数に制限を与える。図２Ｂは、並列処理の増大による理論的な性能の改善を示している。コンポジション時間は、複雑さの因子、Ｏ（ｌｏｇ２Ｒ）によって増大する。統合された時間は、（例えば）１６個のパイプラインにおいて増大をスタートする。明らかに、この場合には、１６を超える並行処理のレベルの増大には、有意性がない。
【００１６】
ソフトウェア技法は、通常、Ｐ個の汎用プロセッサを用いることによってＲ個のＧＰＵの出力をコンポジットすることに基づいている（Ｅ．ＲｅｉｎｈａｒｄおよびＣ．Ｈａｎｓｅｎの「共有メモリ構成における並列コンポジッティング技法の比較」（Ａ Ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｐａｒａｌｌｅｌ Ｃｏｍｐｏｓｉｔｉｎｇ Ｔｅｃｈｎｉｑｕｅｓ ｏｎ Ｓｈａｒｅｄ Ｍｅｍｏｒｙ Ａｒｃｈｉｔｅｃｔｕｒｅｓ）、Ｐａｒａｌｌｅｌ Ｇｒａｐｈｉｃｓ ａｎｄ ＶｉｓｕａｌｉｓａｔｉｏｎのＥｕｒｏｇｒａｐｈｉｃｓ Ｗｏｒｋｓｈｏｐ、Ｇｉｒｏｎａ、２０００年）。しかしながら、これらの解決策は、典型的には、（ｉ）バイナリスワップ、（ｉｉ）並列パイプライン、および（ｉｉｉ）共有メモリコンポジッタの利用を必要とし、そしてそのことは、そのようなインプリメンテーションの複雑さおよびコストを有意に増大させる。
【００１７】
ソフトウェア技法の中で最も効果的なインプリメンテーションは、共有メモリコンポジッタ法（分散メモリ構成における「直接送出」としても知られている）である。この方法においては、サブ画像をレンダリングするための計算労力が、図３Ａのブロック図および図３Ｂに示される擬似コードに示されるように、付加的なＧＰＵ（レンダラ）を利用することによって、増大される。図３Ａに図解されたシステムにおいては、二つのコンポジッタ（ＣＰＵｐ０およびｐ１）が、三つのレンダラ（ＧＰＵＢ０、Ｂ１、およびＢ２）によって生成される、同一のサブ画像について同時に操作している。計算タスクは、ＣＰＵ間に分散され、各々同一画像の半分のコンポジションを実行する。いかなる与えられた数のＧＰＵのためにも、並列コンポジタの数を増大させることによってコンポジッティングをスピードアップすることができることは良く知られている。
【００１８】
しかしながら、増大された数のレンダラは、性能を著しくスローダウンさせる。この方法の複雑さは、Ｏ（Ｎ＊Ｒ／Ｐ）であり、ここで、Ｎは、ラスタ（画像）におけるピクセルの数、Ｒは、ＧＰＵの数、そしてＰは、コンポジッティングユニット（ＣＰＵｐｉ）の数である。この技法におけるコンポジッティングプロセスは、Ｒ−１回の繰り返し以内に完了される。ＳＧＩのＯｒｉｇｉｎ（オリジン）２０００スーパコンピュータ上でのこの技法のインプリメンテーションにおいては、計算は、ＣＰＵを用いて実行される。このシステムによって行われるコンポジッティングの結果は図４に示される。図４は、この方法のオーバヘッドを説明しており、このシステムに必要とされるコンポジッティング時間は、レンダリングのために必要とされる時間の６倍を超える。
【００１９】
上述された全ての方法は、多量のサブ画像データを一つの画像にコンポジットするための先行技術の方法の問題に対して、未だ、満足すべき解決策を提供していない。
【発明の開示】
【発明が解決しようとする課題】
【００２０】
本発明の目的は、ほとんどリアルタイム観察の範囲内で複数のサブ画像フレームを並列的にレンダリングするための方法およびシステムを提供することにある。
【００２１】
本発明の他の目的は、多量のサブ画像データを単一の画像に同時に構成するための方法およびシステムを提供することにある。
【００２２】
本発明のさらなる目的は、サブ画像データを単一の画像に構成するために必要とされる時間の量を実質的に低減する方法およびシステムを提供することにある。
【００２３】
本発明のまた他の目的は、半導体ベースのデバイスとして有効にインプリメントされ得る大量のサブ画像データを単一の画像に同時に構成するための方法および装置を提供することにある。
【００２４】
本発明のまたさらなる目的は、サブ画像データの多重供給源の間の競争を呈することに基づくサブ画像の構成のための方法および装置を提供することにある。
【００２５】
本発明の他の目的および利点は、説明が進むにつれて明白になるであろう。
【課題を解決するための手段】
【００２６】
一つの局面において、本発明は、複数の数Ｚ１，Ｚ２，…，ＺＲから最大の数を検出するための方法およびシステムに向けられたものである。数の各々は、二つ以上のバイナリセグメントＺｊ（Ｎ−１），Ｚｊ（Ｎ−２），…，Ｚｊ（０）に分割され、前記セグメントのビット長が、それらの有意性のレベルに従って決定され、そして前記セグメントのセットは、それらの有意性のレベルに従って配列され、セグメントの第一のセットＺｊ（Ｎ−１），Ｚｊ（Ｎ−１），…，Ｚｊ（Ｎ−１）は、前記数の最上位セグメントを含み且つセグメントの最終セットＺｊ（０），Ｚｊ（０），…，Ｚｊ（０）は、前記数の最下位セグメントを含む。第一のステップにおいては、同一レベルの有意性を有するセグメントＺ１（Ｋ），Ｚ２（Ｋ），…，ＺＲ（Ｋ）の絶対値が、それらの最上位セグメントの絶対値が最大である数を指定するグループを決定し、そして最下位セグメントについて、それらの絶対値サイズを指示するグレードを、同一レベルの有意性の他のセグメントの絶対値と比較して評価するために、同時に比較される。第二のステップにおいては、セグメントの第二のセットＺ１（Ｎ−２），Ｚ２（Ｎ−２），…，ＺＲ（Ｎ−１）からスタートして、前記グループに対応する数のセグメントのグレードが比較され、且つもしもそれらのグレードが、前記グループにおける他の数の指示に対応する最も高いグレードよりも低いならば、数の指示が前記グループから除去される。前記第二のステップは、最後のセットのセグメントＺ１（０），Ｚ２（０），…，ＺＲ（０）が到達されるまで、または、単一の数が前記グループによって指定されるまで、繰り返される。
【００２７】
オプション的に、前記数は、多重三次元ラスタ画像のピクセルの深さ値である。
【００２８】
最大数の検出は、さらに数をしきい値と比較することと、それらの値が前記しきい値の上または下である数についてのみ最大数の検出を実行することをさらに有していても良い。
【００２９】
同様の検出は、それらの最上位セグメントの絶対値が最も小さい数をグループによって指定することによって、そして、それらのグレードが、前記グループにおける他の数の指示に対応する最小のグレードよりも大きいときはいつも、前記グループから数の指定を除去することによって、最小数を決定するために行われても良い。
【００３０】
本発明の一つの望ましい実施の形態において、全てのセグメントは、同一のビット長からなっている。その代わりになるべきものとしては、一つ以上の最下位セグメントのビット長が、最上位セグメントのビット長よりも大きい。
【００３１】
他の局面において、本発明は、各サブ画像における同一の空間位置に対応するピクセルの深さ値Ｚ１，Ｚ２，…，ＺＲを検査し、そして最大の深さ値を有するピクセルの内容をコンポジットすることによって、複数の三次元サブ画像をコンポジット処理するための方法およびシステムに向けられている。前記深さ値は、二つ以上のバイナリセグメントＺｊ（Ｎ−１），Ｚｊ（Ｎ−２），…，Ｚｊ（０）に分割され、そこでは、前記セグメントのビット長が、それらの有意性のレベルに従って決定され、そして前記セグメントのセットは、それらの有意性のレベルに従って配列され、セグメントの第一のセットＺｊ（Ｎ−１），Ｚｊ（Ｎ−１），…，Ｚｊ（Ｎ−１）は、前記深さ値の最上位セグメントを含み且つセグメントの最終セットＺｊ（０），Ｚｊ（０），…，Ｚｊ（０）は、前記深さ値の最下位セグメントを含む。第一のステップにおいて、同一レベルの有意性を有するセグメントＺ１（Ｋ），Ｚ２（Ｋ），…，ＺＲ（Ｋ）の絶対値は、同時に比較され、そしてそれに応じて、それらの最上位セグメントの絶対値が最大である深さ値を指定するグループが決定され、そしてそれらの絶対値サイズを指示する最下位セグメントについて、同一レベルの有意性の他のセグメントの絶対値と比較して、グレードが評価される。第二のステップにおいて、セグメントの第二のセットＺ１（Ｎ−２），Ｚ２（Ｎ−２），…，ＺＲ（Ｎ−１）からスタートして、前記グループに対応する深さ値のセグメントのグレードが比較され、且つもしもそれらのグレードが、前記グループにおける他の深さ値に対応する最も高いグレードよりも低いならば、深さ値の指示が前記グループから除去される。前記第二のステップは、最後のセットのセグメントＺ１（０），Ｚ２（０），…，ＺＲ（０）に到達するまで、または、単一の深さ値が前記グループによって指定されるまで、繰り返される。
【００３２】
最大数の検出は、深さ値をしきい値と比較すること、およびそれらの値が前記しきい値の上または下である深さ値についてのみ最大数の検出を実行することをさらに有していても良い。
【００３３】
同様の検出が、最小数を決定するために、それらの最上位セグメントの絶対値が最も小さい深さ値をグループによって指定することによって行われても良く、そして深さ値の指定は、それらのグレードが、前記グループにおける他の数の指示に対応する最小のグレードよりも大きいときはいつも、前記グループから除去される。
【００３４】
本発明の他の望ましい実施の形態においては、全てのセグメントは、同一のビット長からなっている。その代わりになるべきものとしては、一つ以上の最下位セグメントのビット長が、最上位セグメントのビット長よりも大きい。
【００３５】
本発明は、単一の集積回路チップ上にインプリメントされていても良く、例えば、それは、ＶＬＳＩインプリメンテーションであっても良い。
【発明を実施するための最良の形態】
【００３６】
本発明は、結合様式での、多重三次元／深さラスタ画像の二次元画像への再コンポジションのための方法およびシステムに向けられている。本発明の望ましい実施の形態によれば、多重グラフィックパイプラインを経由して提供される、レンダリングされたグラフィックスデータ（サブ画像）が、各ラスタ座標にて、観察者に最も近いピクセルについて、解かれる。このタスクは、多重の結合ユニット（ＡＵ）を利用することによって、与えられたラスタ座標にて全てのピクセルについて同時に、各ピクセルにおける自律的結合判断プロセスを行うことによって達成される。コンポジション結果により得られる最終画像は、観察のために出力される。本発明は、概して観察のための画像の階層的組み合わせに基づいている先行技術方法の不適当なオーバヘッドを克服する。
【００３７】
原則として、本発明は、多重供給源の中で最も高い深さ値（Ｚ）についての競争を与える。最も高い深さ値は、多重ＡＵを利用することによって決定されるべきである。各ＡＵは、与えられた他の値に対する局所的な深さ値を連続的に検査し、そして他のＡＵに対する競争をやめるか、さらに競争させるかを自律的に判定する。シーケンシャルな種類からなる在来のソート処理方法と対照的に、本発明による分散処理は、並列的に実行され得て、実質的にコンポジション実行のスピードを上げる。本発明の付加的な優位性は：（ｉ）いかなる長さの数についても実行され得ること；および（ｉｉ）いかなる数の供給源にも、性能を減少することなしに適合することである。
【００３８】
図５は、本発明の構成メカニズムの一般的な図解を提供する。本発明のコンポジションシステム５１は、グラフィックスパイプライン（ＦＢｊ，ｊ＝１，２，３，…，Ｒ）によって提供されるサブ画像データが与えられる。コンポジションシステム５１において、サブ画像のデータ（Ｚｊ，Ｐｊ）は、ＡＵ（ＡＵｊ，ｊ＝１，２，３，…，Ｒ）に対応する一セットのＲに提供され、それらの各々は、画面の同一のＸ／Ｙ座標における画像ピクセルを取り扱うことができる。各競争するデータは、内容Ｐｊ（例えばカラー、透明、ここではＲＧＢ−値とも称される）およびピクセルの深さＺｊから構成される。
【００３９】
Ｚ−値は、ＡＵによって受信され、そして深さ競争バス（ＤＣＢ）上に導入される。ＤＣＢラインの論理状態は、ＡＵによって検知され、該ＡＵは、それに応じてキャリーインおよびストップマークベクトルを生起し、これらベクトルは、それらが最も高いＺ−値を保持しているかどうかを決定すべく、プロモーションマトリクス（ＰＭ）５３と共に使用される。競争するデータに関する判定は、結合メカニズムに基づき、且つＤＣＢ上の他のＡＵとの比較によって、各ＡＵにおいて局所的に実行される。最終的に、最も近いピクセル（すなわち、最も高いＺ−値）を保持しているＡＵは、ピクセルのカラーＰｊ（ＲＧＢ−値）を、最終画像５５を構成する最終ラスタ５０にわたすことが可能とされる。
【００４０】
深さ競争バス（ＤＣＢ）構造は、図７Ａおよび図７Ｂに示され且つ説明されるように、ワイアド−アンド論理をインテリジェントに配備する。ワイアド−アンド論理７０の機能性は、通常の論理アンド機能の機能性と同様である。しかしながら、ワイアド−アンド機能は、単一の電気的ポイントに多数の出力を導入し、その点で通常の論理アンドゲートはその信号を他のいかなる出力とも絶縁されている他のゲートに出力しなければならない。図７Ａに説明されているように、入力のいずれか１つにおける論理「０」状態は、出力ライン上を論理「０」状態とさせる。
【００４１】
ＤＣＢ上の比較プロセスは、ビット優位性連続方式にて実行される。図７Ｂに示されるように、グラフィックパイプライン（ＦＢｊ）を経由して提供される各Ｚ−値（Ｚ１，Ｚ２，Ｚ３，…，ＺＲ）は、それぞれのＡＵ（ＡＵｊ）内に供給される。ＤＣＢのラインは、それらの優位性のレベルに従って、Ｎ−バイナリのＺ−値（Ｚｊ（ｉ），ｉ＝０，１，２，…，Ｎ）の各セグメントのワイアド−アンド結果を出力するために用いられる。このようにして、ＤＣＢ（０）ラインは、Ｚ−値（Ｚｊ（０））の最下位セグメント（ＬＳＳ、非第一のセグメントとも称される）上で実行されるワイアド−アンド論理の出力として使用され、そして、ＤＣＢ（Ｎ−１）ラインは、Ｚ−値（Ｚｊ（Ｎ−１））の最上位セグメント（ＭＳＳ、第一のセグメントとも称される）上で実行されるワイアド−アンド論理の出力のために使用される。
【００４２】
比較プロセスは、Ｚ−値の最上位ビットからスタートする、順序付けられた様式で行われ、そしてそれは、Ｚ−値の最下位ビットで終了させられる。競争は、ＡＵが、ＤＣＢ（Ｎ−１）の最も上のライン上に最上位ビット（ＭＳＢ）を出力したときにスタートする。このプロセスの期間は、いつも、ｌｏｇ２｜Ｚ｜の一定時間を要し、ここで、｜Ｚ｜は、場面の深さ領域、すなわちＺ−値のビット長である。その結果として、先行技術の方法の多重ステージ構造は、本発明の方法に従った単一のステージによって置換される。先行技術の方法のＯ（ｌｏｇ２Ｚ＊ｌｏｇ２Ｎ）の実行の複雑さは、本発明の方法によってＯ（ｌｏｇ２Ｚ）に有意的に低減される。
【００４３】
ＭＳＳビットＺｊ（Ｎ−１）の比較において、ＤＣＢラインＤＣＢ（Ｎ−１）上に、単一の、またはそれらのいくつかの、論理「０」状態を、置くことは、前記ライン上を「０」論理状態に強制する。ＤＣＢライン上に「１」論理状態が置かれ、且つ前記ライン上で結果的に「０」論理状態が検知されるＡＵは、それらの現在のＺ−値についてのそれらの競争を終結させ、さもなければ、該ＡＵは、表１に例示されたように、次に続くビット（優位性が低い）に対するそれらの競争を続けることが許可される。
【００４４】
（表１）
ＭＳＳビットＺｊ（Ｎ−１）の比較
┌───────────┬───────────┬───────────┐
│ 強制値 │ＤＣＢラインの状態 │ 判 定 │
├───────────┼───────────┼───────────┤
│ 1 │ 0 │ ストップ │
├───────────┼───────────┼───────────┤
│ 1 │ 1 │ 継 続 │
├───────────┼───────────┼───────────┤
│ 0 │ 0 │ 継 続 │
├───────────┼───────────┼───────────┤
│ 0 │ 1 │ 継 続 │
└───────────┴───────────┴───────────┘
上の表１に示された最後のケースは、ＤＣＢライン上の論理「０」状態の強制は、このラインを論理「０」状態に強制しなければならないから、実際に可能でないことに留意されるべきである。
【００４５】
Ｚ−値が競争を継続すべきであるかどうかについての判定は、ＤＣＢラインの論理状態を検知することにより各ＡＵによって確立される。最後に残存しているＡＵが、競争に「勝つ」。ＡＵの比較論理がバス上により高いＺ−値を識別したとき、それ自体を競争から引き離す。さもなければ、バス上に残った値が最も高いＺ−値を有するものとなるまで競争を続ける。
【００４６】
図８は、ＡＵの動作を説明するブロック図である。第ＫのＺ−値（Ｚｋ（Ｎ−１），Ｚｋ（Ｎ−２），…，Ｚｋ（０））は、１セットのゲート（９０、図９に示されている）を経由してＤＣＢに結線されており、ピクセル値ＰＫは、ゲート８４を経由してマージされたＦＢ５０へ通るゲート制御がされる。結合論理８０は、ワイアド−アンド機能を有効とし、ユニットの競争を制御し、そしてＰＭ５３の一つから勝ちの通知８６（ＷＫ）を受けたときに、有効化指示８１を利用してＲＧＢ−値ＰＫがＦＢ５０へ通過することを許可する。
【００４７】
ＡＵは、Ｚ−値（Ｚｋ（ｉ），ｉ＝０，１，２，…，Ｎ−２）のＬＳＳについて結合ロジック８０によって生成され且つその後にＰＭ５３に供給されたストップマーク（ＳＭ）ベクトル８５ＳＭｋ＝（ＳＭｋ（０），ＳＭｋ（１），…，ＳＭｋ（Ｎ−２））を生成する。キャリーアウト指示（Ｃｋ（Ｎ−１））もＡＵｋによって生起され、Ｚ−値ＺｋのＭＳＳ（Ｚｋ（Ｎ−１））が競争の第一のステージを勝ったかどうかを指示する。
【００４８】
結合論理８０は、種々の方法でＡＵの競争機能性を拡張すべく設計されても良いことに留意されるべきである。例えば、到来するＺ−値の逆数が競争のために（全てのＡＵにおいて）使用されても良く、そしてそのようなケースにおいては、ＡＵ間の競争は、最小の深さ値を決定することに基づいて行われるであろう。その代わりとして、ＡＵのＺ−値入力上に、しきい値をむしろ配置し、そしてこのようにして、それら２つの値の、どちらが、しきい値より大きいか、またはしきい値より小さいか、という競争を可能とするようにしても良い。
【００４９】
局所ＡＵにおいて、各Ｚ−値Ｚｊは、ＮセグメントＺｊ（Ｎ−１），Ｚｊ（Ｎ−２），…，Ｚｊ（０）にセグメント化され、ここで、第（Ｎ−１）のセグメントＺｊ（Ｎ−１）は、ＭＳＢを保持し、そして第（０）のセグメントＺｊ（０）は、ＺｊのＬＳＢを保持している。例えば、３つのセグメント（すなわち。Ｎ＝３，Ｚｊ（２），Ｚｊ（１），およびＺｊ（０））に処理される３２ビットの長さのＺ−値数を仮定しよう、そこでは第一および第二のセグメント（Ｚｊ（２）およびＺｊ（１））は、各々８ビットの長さで且つ第三のセグメント（Ｚｊ（０））は、１６ビットの長さである。競争の第一のステージにおいて、Ｚ−値（Ｚｊ（２），ｊ＝１，２，…，Ｒ）のＭＳＳ（第一のセグメント）に従って一つ以上の予備的な勝者が決定され、且つストップマークグレーディング（ＳＭｊ（ｉ），ｉ＝０，１，２，…，Ｎ−２、例えばＮ＝３についてＳＭｊ（０）およびＳＭｊ（１））がＺ−値（Ｚｊ（ｉ），ｉ＝０，１，２，…，Ｎ−２、例えばＮ＝３についてＺｊ（２）およびＺｊ（１））の全ての他のセグメント（ＬＳＳ）の間の競争に従って確立される。競争の次のステップにおいて、第一のステージを勝利したＺ−値に対応する第二のセグメント（Ｚｊ（Ｎ−２）例えばＺｊ（１））について確立された、ストップマークグレーディングＳＭＫ（Ｎ−２）（例えば、ＳＭＫ（１））は、それらのＺ−値のいずれを競争させ続けるかを決定すべく検査される。次のセグメント（ＳＭｊ（ｉ），ｉ＝０，１，２，…，Ｎ−３、例えばＮ＝３についてＳＭｊ（０））について確立されたストップマークグレーディングによって、最後のセグメント（ＬＳＳ、Ｚｊ（０））の結果に従って最も高いＺ−値が決定されるまで、同一のプロセスが実行される。
【００５０】
各ＡＵは、全てのセグメント（Ｚｊ（ｉ），ｉ＝０，１，…，Ｎ−１）を並列に処理する。ＡＵは、ＭＳＢからＬＳＢまでに使用されたセグメンテーションに従って、全てのＺ−値の数を制御する。ＡＵ論理が、第一のセグメントＺｊ（Ｎ−１）を競争させ且つそのキャリーアウトＣ（Ｎ−１）をＰＭ（Ｎ−１）（図６）に提示すると同時に、第二のセグメントＺｊ（Ｎ−２）を競争させ且つそのストップマークＳＭ（Ｎ−２）をＰＭ（Ｎ−１）に提示する。同様に、Ｚ−値の第三のセグメントＺｊ（Ｎ−３）を競争させ且つストップマークグレーディングＳＭ（Ｎ−３）をＰＭ（Ｎ−２）に提示するなどする。
【００５１】
セグメント長は、競争性能を最適化すべく選定される。例えば、３２ビットの長さのＺ−値について、それぞれ、８、８、および１６ビットの、Ｚｊ（２）、Ｚｊ（１）、およびＺｊ（０）の、三つのセグメントで処理され、第二のセグメントについてのＳＭベクトルＳＭ（１）は、第一のセグメントＺｊ（２）が処理されている間に準備され得て、そして第三の（最長の）セグメントについてのＳＭベクトルＳＭ（０）は、二つの先行するセグメントＺｊ（２）およびＺｊ（１）のために必要とされる時間期間を利用して同時的に準備され得る。
【００５２】
このプロセスは、図６に説明されている。数字６１〜６４は、Ｚ−値のセグメンテーションに従ってＡＵによって生成される指示を概略的に指定している。Ｚ−値（Ｚｊ（ｉ），ｉ＝０，１，２，…，Ｎ−２）のＬＳＳを供するＮ−１個のＰＭ５３が存在する。ＰＭ５３は、対応する（第ｉの）セグメントにについてＡＵによって生成されるそれぞれストップマークベクトルＳＭ（ｉ）＝（ＳＭ１（ｉ），ＳＭ２（ｉ），…，ＳＭＲ（ｉ））に従って決定されるキャリーアウトベクトルＣ（ｉ）（Ｃ（Ｎ−２），Ｃ（Ｎ−３），…，Ｃ（１））、および従前のステージにおいてＰＭ（ｉ−１）によって生起されるキャリーアウトベクトルＣ（ｉ−１）を生成する。ＰＭによって生成される付加的な信号は、（ａ）競争の各ステージにおいて勝ったＺ−値を指定する勝者指示Ｗｊ、および（ｂ）一旦単一の勝者が決定されると生成され、後続のマトリクスが、それらの競争を継続するのを防止する「競争ストップ」信号である。
【００５３】
Ｚ−値の第一のセグメントＺｊ（Ｎ−１）＝（Ｚｊ，０（Ｎ−１），Ｚｊ，１（Ｎ−１），…，Ｚｊ，ｎ−１（Ｎ−１））についてのキャリー指示を生成するためのＡＵ論理が、図９に示されている。ワイアド−アンドの機能性を活用すべく、各ビットの反転状態が、論理ナンドゲート９０を経由してＤＣＢラインに導入される。各検査されたビットＺｊ，ｋ（Ｎ−１）について、それぞれのＤＣＢラインの論理状態および検査されたビットＺｊ，ｋ（Ｎ−１）の論理状態に従って、Ｚ−値が次のビットレベルＺｊ，ｋ＋１（Ｎ−１）において競争を継続するかどうかを決定するために、論理オアゲート９２が、使用される。各ビットステージＺｊ，ｋ（Ｎ−１）は、論理アンドゲート９２を経由して次のビットステージＺｊ，ｋ（Ｎ−１）を制御する。キャリーアウト指示Ｃｊ（Ｎ−１）は、全てのｎビットステージが競争を生き残った場合にのみ生成される。キャリーアウト指示は、図６に示されたＰＭ（Ｎ−１）プロモーションマトリクスに対して提供され、そしてこのようにして、次のセグメントにおけるＺ−値Ｚｊのさらなる競争を可能としている。
【００５４】
同時に、ＡＵが、Ｚ−値の第一のセグメントを検査している間に、ＬＳＳ（Ｚｊ（ｉ），ｉ＝０，１，２，…，Ｎ−２）の各々もワイアド−アンド論理によって検査される。しかしながら、ＬＳＳの検査において、第一のセグメントについて生成されたキャリーアウト指示Ｃｊ（Ｎ−１）の代わりに、ストップマークＳＭｊ（ｉ）（ｉ＝０，１，２，…，Ｎ−２）信号が生成される。各ストップマークＳＭｊ（ｉ）信号は、ストップマークベクトルＳＭ（ｉ）の一部としてのＰＭ（ｉ）プロモーションマトリクスにそれぞれ送られる。
【００５５】
ストップマークＳＭｊ（ｉ）は、競争から全Ｚ−値Ｚｊがもしかすると省かれるかもしれないそれぞれのセグメントＺｊ（ｉ）の「弱い」ビットを指示する。ＬＳＳについてのＳＭ信号（ＳＭｊ（ｉ），ｉ＝０，１，２，…，Ｎ−２）を生成するための論理は、図１０に示されている。主として、この論理は、キャリーアウトベクトルＣ（Ｎ−１）の生成のために使用された論理と類似している。しかしながら、各ビットステージが、インバータ９９を経由して、ストップマーク信号「ストップ１」−「ストップ（ｎ＋１）」を生成し得ることにおいて異なっている。各ＬＳＳセグメント（Ｚｊ（ｉ），ｉ＝０，１，２，…，Ｎ−２）について、ただ一つのストップマーク信号ＳＭｊ（ｉ）が生成される。最も高い可能性のストップマーク信号「ストップ（ｎ＋１）」は、検査されたセグメントは、いかなるそのワイアリング比較においても消滅しないことを示している。
【００５６】
結合マトリクスの論理は、ストップマークベクトルＳＭｊ（ｉ）および従前に生成されたキャリーアウトベクトルＣ（ｉ＋１）を取り扱い、そして新たなキャリーアウトベクトルＣ（ｉ）を生成する。この新たなキャリーアウトベクトルＣ（ｉ）において、これまで競争に生き残ったそれらのＡＵのみが参加している。もしもちょうど単一のＡＵが生き残ったならば、それが最終勝者になり、競争プロセスを停止する。そうでなければ、次のＰＭ（ＰＭ（ｉ−１））が、単一の勝者が残るまで同一のタスクを実行する。
【００５７】
図１１は、ＰＭ（縮小されたケース）の論理を説明している。平易化のために、図１１は、二つのＡＵ（Ｒ＝２）を供する第ｉのＰＭ（すなわちＰＭ（ｉ））を図解しており、そこでは第ｉのセグメントは４ビットの長さである（すなわち、５つのストップマーク、ＳＭｊ（ｉ）＝（ＳＭｊ，１（ｉ），ＳＭｊ，２（ｉ），…，ＳＭｊ，５（ｉ）））。ストップマークベクトルＳＭ１（ｉ）およびＳＭ２（ｉ）の各々は、ＦＦ１１０および１１１の一方に設定する。一つよりも多いＦＦ１１０および１１１が、並んで「オン」状態になることはできない。勝利指示Ｃｊ（ｉ＋１）が従前のＰＭ（ＰＭ（ｉ＋１））から受信されたストップマークベクトルは、より高い数を有し且つ従前のＰＭ（ＰＭ（ｉ＋１））において勝利が指示されたキャリーアウトを有する他のストップマークが存在しなければ、そして存在しない場合にのみ、キャリーアウトを生成するであろう。
【００５８】
ＰＭにおける従前の縦列の操作は、最も高いレベルを有するストップマーク指示がそこで受信され且つ対応するキャリーアウト指示が従前のＰＭからそのために受信される、縦列の論理オアゲート１１９を介して集められた論理アンドゲート１１７から対応する指示を受け取ると同時に、抑止機能１１３を介して抑止される。もしもＰＭによって受信されたストップマークが同一の優位性からなっている（例えば、ＳＭ１，４（ｉ）およびＳＭ２，４（ｉ））ならば、キャリーアウト指示Ｃ１（ｉ）およびＣ２（ｉ）がバッファ１１２を経由して次のＰＭ（ＰＭ（ｉ））に供給される。
【００５９】
ただ一つの勝利信号Ｗ（ｉ）のみが、ＰＭの一つによって生起され得る。検出部１１５が、単一の勝者が、現在のステージで決定されたことを指示するときはいつも、抑止機能１１３は、次のステージＰＭ（ｉ−１）のＰＭによってさらなる処理を抑止するであろうストップ指示Ｓｔｏｐ（ｉ）を生起する。ストップ信号が抑止機能（例えば、Ｓｔｏｐ（ｉ＋１））によって受信されたときはいつも、ゲート１１７を抑止することおよび次のＰＭの抑止機能へストップ指示（例えばＳｔｏｐ（ｉ））を発行することによって、現在およびそれに続くＰＭの機能を、抑止する。
【００６０】
例えば、ＡＵ１が、ストップマーク４、ＳＭ１，４（ｉ）、を設定し、ＡＵ２が、ストップマーク２、ＳＭ２，２（ｉ）、を設定すること、そして従前のＰＭから受信される両方のキャリー指示、Ｃ１（ｉ＋１）およびＣ２（ｉ＋１）、が、競争の従前のステージにおける勝利を指示することと仮定する。そのようなケースにおいては、ＡＵ１において競争するＺ−値が勝ち、抑止機能１１３を経由して縦列１〜３を抑止し、そしてキャリーアウトＣ１（ｉ）のみを生成する。単一のキャリーアウトの検出は、現在のステージにおける単一の勝者を指示し、結果は、ＡＵ１へのＷ１ライン上に設けられる単一キャリーアウト検出部１１５を経由して勝利通知信号Ｗ（ｉ）を生成することである。勝利ＡＵは、それからそのＲＧＢ値ＰＫをＦＢ５０へ供給することが可能とされる。
【００６１】
もしも、例えば、ＡＵ１およびＡＵ２が、両方ともストップマーク４、ＳＭｊ，４（ｉ）、をオンとし、キャリー指示Ｃ１（ｉ＋１）およびＣ２（ｉ＋１）が両Ｚ−値が従前のステージで勝ったことを指示すると、そのときは、次のＰＭ（ＰＭ（ｉ＋１））へ転送される二つのキャリーアウトＣ１（ｉ）およびＣ２（ｉ）が、現在のステージにおける勝ちをも指示するであろう。
【００６２】
図１２は、ＡＵａからｅに属するＲ＝５のＺ−値（Ｚ１，Ｚ２，Ｚ３，Ｚ４，およびＺ５）の競争プロセスを例示している。この例において、Ｚ−値の深さ寸法は、３２ビットからなり、そして深さ値は、各８ビットのＮ＝４セグメント（Ｚｊ（３），Ｚｊ（２），Ｚｊ（１），およびＺｊ（０））にセグメント化される。（プロモーションマトリクスを有さない）シーケンシャルなワイアド−アンドプロセスが、３２時間単位を要するのに、この例における合計処理時間は、１１時間単位である。
【００６３】
この例における第一のセグメントにおいて、ＭＳＳ，Ｚ２（３），Ｚ３（３），およびＺ５（３）は、全て等しく且つＺ１（３）およびＺ４（３）よりも大きく、そしてそれゆえ対応するＣ２（３），Ｃ３（３），およびＣ５（３）キャリーアウト信号のみが、Ｚ−値Ｚ２，Ｚ３，およびＺ５が第一のステージを勝ったことを指示すべく生起される。同時に、ＬＳＳのＳＭベクトルが、ＡＵによって生起される。
【００６４】
Ｚ−値の第二のセグメントについて、Ｚｊ（２）数の６つのＭＳＢは全て等しい。「ストップ７」ＳＭは、Ｚ１（２）について指示され、そして、セグメントにおける全ての他のＺ−値の第７ビットの状態が、「１」（Ｚ２，７（２）＝Ｚ３，７（２）＝Ｚ４，７（２）＝Ｚ５，７（２）＝１）であるのに、その第７ビットの状態は「０」（Ｚ１，７（２）＝０）であるからさらなる競争はしない。「ストップ８」ＳＭは、Ｚ３（２）について指示され、そして、それらの競争がこのビットステージにおいて続行する値の第８ビットの状態が、「１」（Ｚ２，８（２）＝Ｚ４，８（２）＝Ｚ５，８（２）＝１）であるのに、その第８ビットの状態は「０」（Ｚ３，８（２）＝０）であるから、また、さらなる競争を終了する。それゆえ、「ストップ９」ＳＭは、セグメントにおけるビットステージはどれもこれもそれらが勝つから、Ｚ２（２），Ｚ４（２），およびＺ５（２）についての指示が生起される。したがって、ＰＭ（２）におけるＳＭ（２）およびＣ（３）ベクトルの処理は、次のＰＭ、ＰＭ（１）、に対するキャリーアウト指示Ｃ２（２）およびＣ５（２）を生起するであろう。
【００６５】
Ｚ−値の第三のセグメントについて、「ストップ２」ＳＭは、Ｚ５（１）について指示され、Ｚ１，２（１）＝Ｚ２，２（１）＝Ｚ３，２（１）＝Ｚ４，２（１）＝１であるのに、Ｚ５，２（１）＝０およびＺｊ，１（１）＝０であるから、それはいかなるさらなる競争をもストップし、そして「ストップ９」ＳＭは、それらの６つのＭＳＢは同等であるから、Ｚ１（１），Ｚ２（１），Ｚ３（１），およびＺ４（１）について指示される。したがって、ＰＭ（１）におけるＳＭ（１）およびＣ（２）ベクトルの処理は、最後のＰＭ、ＰＭ（０）、に対する単一キャリーアウト指示Ｃ２（１）を生起するであろう。ＰＭ（１）、が単一の勝者を決定したから、その検出部１１５は、対応する指示Ｗ２を勝ったＡＵ、ＡＵ２、に対して生起し、そのＲＧＢ値Ｐ２をＦＢ５０において利用可能とする。それゆえに、ＰＭ（１）の抑止機能は、最後のＰＭ、ＰＭ（０）、におけるさらなる処理を抑止するストップ（０）指示を生成する。
【００６６】
第三のセグメントの処理は、実行されない。それにもかかわらず、ＡＵによってＳＭ（０）指示が生起される。Ｚ１，１（０）＝Ｚ２，１（０）＝Ｚ３，１（０）＝Ｚ４，１（０）＝１であるのに、Ｚ５，１（０）＝０であるから、「ストップ１」ＳＭは、Ｚ５（０）について指示される。ｒ＝２，３，４，５および６について、Ｚ１，ｒ（０）＝Ｚ２，ｒ（０）＝Ｚ３，ｒ（０）＝Ｚ４，ｒ（０）＝１、Ｚ３，７（０）＝Ｚ４，７（０）＝０、そしてＺ１，７（０）＝Ｚ２，７（０）＝１であるから、「ストップ７」ＳＭは、Ｚ３（０）およびＺ４（０）について指示される。それゆえに、Ｚ２，８（０）＝０およびＺ１，８（０）＝１であるから、「ストップ８」ＳＭは、Ｚ２（０）について指示され、そして「ストップ９」ＳＭは、Ｚ１（０）について指示される。
【００６７】
全てのセグメントは、長さについて一様に維持されるから、セグメントのＳＭ結果をマージングすることによって、競争時間は、さらに縮減され得る。そのような縮減は、従前のＰＭからのキャリーアウト指示の到着に先立って結果のクラスタリングを可能とする。このアプローチは、複雑さをＯ（ｌｏｇ２Ｚ）からＯ（（ｌｏｇ２Ｚ）／ｋ）（但しｋは折り畳み係数）に低減する。例えば、Ｚ＝２３２と仮定すると、シーケンシャルなワイアド−アンドプロセスは、Ｏ（３２）の複雑さを要する。しかしながら、各８ビットの４個のＰＭを用いれば、数の後半は、前半を処理するときに「折り畳まれる」。結果として、複雑さは、Ｏ（８＋１＋１）に低減される。このケースでは、折り畳み係数ｋは、３２／１０＝３．２である。より長い数、例えば６４ビットのケースにおいては、複雑さの程度は、顕著には変化されず：Ｏ（８＋１＋１＋１）である。この並列のアプローチの利点は、Ｚ−値数のいかなるビット長にも、高い効率を維持しつつ、ほとんど同様の短時間に処理され得ることにある。
【００６８】
図１３は、本発明の望ましい実施の形態のチップインプリメンテーション１４０（例えばＶＬＳＩ）を説明するブロック図である。この例は、６つの異なるＧＰＵから６つのＦＢをコンポジットするためのインプリメンテーションを図解している。このインプリメンテーションは、複数のサブ画像ユニット（ＳＩＵ）によって複数のサブ画像ピクセルを同時に構成するためのコンポジット処理ユニットを実現する。各ＳＩＵは、ＧＰＵの数に対応するＡＵのセット、ＤＣＢ、ＰＭ、および制御論理１４１を具備している。各ＳＩＵにおける制御論理１４１は、それぞれのサブ画像の座標と符合するピクセルのみを、ポート〜ポート６入力ポートを介して取り込まれるデータ入力ストリームと区別する。各ＳＩＵは、サブ画像の一つのＲＧＢデータを出力し、該データは、出力ポート１４２を介してＦＢ５０に出力される。
【００６９】
全コンポジットプロセスは、各ＦＢを１６個のサブ画像に分割することによってさらに並列化される。例えば、１０２４×１０２４ピクセルの分解能を有する画像について、各サブ画像ユニット（ＳＩＵ）は、６４×６４サブ画像（画像の１／１６）を処理する。もしも、例えば、ピクセルのカラーデータが２４ビットの長さであれば、ＳＩＵのスタックの出力は１２Ｋバイトの勝利したピクセルカラーデータを含んでいる。
【００７０】
先行技術に反して、本発明は、図５において説明されたように、いかなる数のＧＰＵ、Ｒ、についての単一のマージ処理ステップを実行することが可能である。先行技術方法の階層的構造は、本発明においては、特有の、平坦な、単一ステップ構造によって置き換えられている。この新規な構造の性能は、並列処理のレベル、すなわち参加するＧＰＵの数、に敏感ではない。コンポジション時間は、単一比較まで事実上低減され、そしてどんな任意数のＧＰＵも、全体の性能に対する犠牲なしに、許容される。
【００７１】
上述の例および記述は、もちろん、説明の目的のためにのみ提供されており、そしていかなる点においても発明を限定することを意図していない。当業者によって認められるであろうように、本発明は、非常に多種多様の方法において、上述されたものとは異なる技術を採用して、本発明の範囲を逸脱することのない全てを実施され得るものである。
【図面の簡単な説明】
【００７２】
【図１】複数のサブ画像データの単一の画像へのマージ処理を図解するブロック図である。
【図２Ａ】先行技術の階層的コンポジット処理方法を図解するブロック図である。
【図２Ｂ】階層的コンポジット処理性能の並行処理制限を図表的に図解している。
【図３Ａ】先行技術の共有メモリコンポジット処理方法を示すブロック図および擬似コードを示している。
【図３Ｂ】先行技術の共有メモリコンポジット処理方法を示すブロック図および擬似コードを示している。
【図４】先行技術の共有メモリコンポジション法の性能を図表的に図解している。
【図５】本発明の望ましい実施の形態を例示するブロック図である。
【図６】本発明に従ったプロモーションシステムを図解するブロック図である。
【図７Ａ】本発明のワイアド−アンド機能の原理を具体的に説明するブロック図である。
【図７Ｂ】Ｎ個のバイナリ数のワイアド−アンド競争の原理を図解するブロック図である。
【図８】結合ユニットの望ましい実施の形態を図解するブロック図である。
【図９】第一のセグメントの論理を概略的に図解するブロック図である。
【図１０】非第一のセグメントの論理を概略的に図解するブロック図である。
【図１１】低減されたプロモーションマトリクスを概略的に図解するブロック図である。
【図１２】５個の深さ値の競争プロセスを例示している。
【図１３】本発明の望ましい実施の形態のチップインプリメンテーションを図解するブロック図である。
【特許請求の範囲】
【請求項１】
複数の数Ｚ１，Ｚ２，…，ＺＲから最大の数を検出するための方法であって：
ａ）前記数の各々を二つ以上のバイナリセグメントＺｊ（Ｎ−１），Ｚｊ（Ｎ−２），…，Ｚｊ（０）に分割するステップであって、前記セグメントのビット長が、それらの有意性のレベルに従って決定され、そして前記セグメントのセットは、それらの有意性のレベルに従って配列され、セグメントの第一のセットＺｊ（Ｎ−１），Ｚｊ（Ｎ−１），…，Ｚｊ（Ｎ−１）は、前記数の最上位セグメントを含み且つセグメントの最終セットＺｊ（０），Ｚｊ（０），…，Ｚｊ（０）は、前記数の最下位セグメントを含むステップと；
ｂ）同一レベルの有意性を有するセグメントＺ１（Ｋ），Ｚ２（Ｋ），…，ＺＲ（Ｋ）の絶対値を同時に比較し、それらの最上位セグメントの絶対値が最大である数を指定するグループを決定し、そして最下位セグメントについて、それらの絶対値サイズを指示するグレードを、同一レベルの有意性の他のセグメントの絶対値と比較して評価するステップと；
ｃ）セグメントの第二のセットＺ１（Ｎ−２），Ｚ２（Ｎ−２），…，ＺＲ（Ｎ−１）からスタートして、前記グループに対応する数のセグメントのグレードを比較し、且つ前記グループにおける他の数の指示に対応する最も高いグレードよりも低いグレードを有するいかなる数の指示をも前記グループから除去するステップと；
ｄ）最後のセットのセグメントＺ１（０），Ｚ２（０），…，ＺＲ（０）に到達するまで、または、単一の数が前記グループによって指定されるまで、ステップｃ）を繰り返すステップと；
を有する方法。
【請求項２】
数は、多重三次元ラスタ画像のピクセルの深さ値である請求項１に記載の方法。
【請求項３】
数をしきい値と比較し、且つそれらの値が前記しきい値の上または下である数についてのみ最大数の検出を実行するステップをさらに有する請求項１に記載の方法。
【請求項４】
最小数を決定するために、グループが、それらの最上位セグメントの絶対値が最も小さい数を指定すべく決定され、且つ数の指定は、それらのグレードが、前記グループにおける他の数の指示に対応する最小のグレードよりも大きいときはいつも前記グループから除去される請求項１に記載の方法。
【請求項５】
全てのセグメントは、同一のビット長からなる請求項１に記載の方法。
【請求項６】
一つ以上の最下位セグメントのビット長は、最上位セグメントのビット長よりも大きい請求項１に記載の方法。
【請求項７】
各サブ画像における同一の空間位置に対応するピクセルの深さ値Ｚ１，Ｚ２，…，ＺＲを検査し、そして最大の深さ値を有するピクセルの内容をコンポジットすることによって複数の三次元サブ画像をコンポジット処理するための方法であって：
ａ）前記深さ値の各々を二つ以上のバイナリセグメントＺｊ（Ｎ−１），Ｚｊ（Ｎ−２），…，Ｚｊ（０）に分割するステップであって、前記セグメントのビット長が、それらの有意性のレベルに従って決定され、そして前記セグメントのセットは、それらの有意性のレベルに従って配列され、セグメントの第一のセットＺｊ（Ｎ−１），Ｚｊ（Ｎ−１），…，Ｚｊ（Ｎ−１）は、前記深さ値の最上位セグメントを含み且つセグメントの最終セットＺｊ（０），Ｚｊ（０），…，Ｚｊ（０）は、前記深さ値の最下位セグメントを含むステップと；
ｂ）同一レベルの有意性を有するセグメントＺ１（Ｋ），Ｚ２（Ｋ），…，ＺＲ（Ｋ）の絶対値を同時に比較し、それらの最上位セグメントの絶対値が最大である深さ値を指定するグループを決定し、そして最下位セグメントについて、それらの絶対値サイズを指示するグレードを、同一レベルの有意性の他のセグメントの絶対値と比較して評価するステップと；
ｃ）セグメントの第二のセットＺ１（Ｎ−２），Ｚ２（Ｎ−２），…，ＺＲ（Ｎ−１）からスタートして、前記グループに対応する深さ値のセグメントのグレードを比較し、且つ前記グループにおける他の深さ値に対応する最も高いグレードよりも低いグレードを有するいかなる深さ値の指示をも前記グループから除去するステップと；
ｄ）最後のセットのセグメントＺ１（０），Ｚ２（０），…，ＺＲ（０）に到達するまで、または、単一の深さ値が前記グループによって指定されるまで、ステップｃ）を繰り返すステップと；
を有する方法。
【請求項８】
深さ値をしきい値と比較し、且つそれらの値が前記しきい値の上または下である深さ値についてのみ最大数の検出を実行するステップをさらに有する請求項７に記載の方法。
【請求項９】
最小数を決定するために、グループが、それらの最上位セグメントの絶対値が最も小さい深さ値を指定すべく決定され、且つ深さ値の指定は、それらのグレードが、前記グループにおける他の数の指示に対応する最小のグレードよりも大きいときはいつも前記グループから除去される請求項７に記載の方法。
【請求項１０】
全てのセグメントは、同一のビット長からなる請求項７に記載の方法。
【請求項１１】
一つ以上の最下位セグメントのビット長は、最上位セグメントのビット長よりも大きい請求項７に記載の方法。
【請求項１２】
複数の三次元サブ画像をコンポジットするためのシステムであって：
ａ）複数のピクセルの深さ値のビット群を同時に導入するためのバスライン群であり、各バスライン上に同一レベルの有意性を有するビット群が導入され、前記ビット群の全ての論理状態が「１」であるときはいつも、前記ライン群の論理状態が「１」にセットされ、そしてもしも前記ビット群の少なくとも一つの論理状態が「０」であれば、その論理状態が「０」にセットされるバスラインと；
ｂ）前記サブ画像における同一の空間位置に対応するピクセル群のデータを同時に読み取り、各読み取りピクセルの深さ値を二つ以上のセグメントに分割し、前記セグメントを前記バスのそれぞれのライン上に導入し、前記ライン群の論理状態を検知し、そしてそれに応じて最大の絶対値を有する深さ値を指定する前記値の最上位セグメントについての、および同一レベルの有意性の他のセグメントの絶対値と比較してそれらの絶対値サイズを指示する最下位セグメントストップマークグレーディングについての中間比較結果を同時に生起するための結合ユニットと；
ｃ）対応するストップマークグレーディングが、前記中間比較結果の一つに関連する最大のストップマークグレーディングよりも小さいものについての先に生起された中間比較結果深さ値指定を除去することによって、最上位セグメントのセットに続くセグメントのセットからスタートする、有意性の順における各後続のセグメントのセットについての中間比較結果を連続的に生起するためのプロモーションマトリクスと；
を具備し、
前記プロモーションマトリクスは、ピクセルデータがそれぞれの結合ユニットからコンポジット処理のために回復され得るように、現在生起された中間比較結果が単一指定を含むことを指示することができるシステム。
【請求項１３】
現在生起された中間比較結果が単一の指定を含むことがプロモーションマトリクスによって指示されたときはいつでも、後続のプロモーションマトリクスの動作を抑止するための抑止手段をさらに備える請求項１２に記載のシステム。
【請求項１４】
当該システムが単一の集積回路チップ上にインプリメントされた請求項１２に記載のシステム。
【請求項１５】
チップは、ＶＬＳＩインプリメンテーションである請求項１２に記載のシステム。
【請求項１６】
ワイアド−アンドバスのライン上にピクセルの深さ値のセグメントのビット群を導入し、キャリーアウトおよびストップマーク指示を発行し、そして対応する外部の有効化指示に従って前記ピクセルのデータを有効化するための結合ユニットであって：
ａ）前記バスのそれぞれのライン上への前記深さ値の最上位セグメントのビット群の導入を有効化し、前記ラインの論理状態を、最上位ラインからスタートして検知し、そしてもしも検知されたラインおよび対応するビットの論理状態が、「０」ならば、それに続くバスラインの検知を抑止し、さもなければ前記セグメントの最後まで進めるべく検知を有効化し、そしてキャリーアウト指示を発行するための第一のセグメント論理回路要素と；
ｂ）前記バスのそれぞれのライン上への前記深さ値の最下位セグメントのビット群の導入を有効化し、前記ラインの論理状態を、最上位ラインからスタートして検知し、そしてもしも検知されたラインおよび対応するビットの論理状態が、「０」ならば、それに続くバスラインの検知を抑止し且つそのセグメントにおける前記ビットの有意性のレベルに対応するストップマーク指示を発行し、さもなければ前記セグメントの最後まで進めるべく検知を有効化し、そして前記セグメントにおける最上位ビットよりも高い一つのレベルである有意性のレベルを有するストップマーク指示を発行するための一つ以上の非第一のセグメント論理回路要素と；
ｃ）前記有効化指示が受信されたときはいつでも前記データの出力を有効化するためのゲートと；
を具備し、
それに導入されたビット群の全ての論理状態が「１」であるときはいつでも前記バスの各ラインの論理状態が、「１」にセットされ、且つもしも前記ビット群の少なくとも一つの論理状態が「０」であれば、それは「０」にセットされ、そして前記有効化指示は、前記キャリーアウトおよびストップマーク指示に従って外部的に決定される結合ユニット。
【請求項１７】
深さ値の値が、しきい値よりも大きいときはいつでも、第一のおよび非第一のセグメント論理回路要素の動作を有効化するための手段をさらに備える請求項１６に記載の結合ユニット。
【請求項１８】
該手段は、深さ値の値が、しきい値よりも小さいときはいつでも、第一のおよび非第一のセグメント論理回路要素の動作を有効化する請求項１７に記載の結合ユニット。
【請求項１９】
検知されたラインおよび対応するビットの論理状態が「１」であるときはいつでも、それに続くバスラインの検知は抑止される請求項１６に記載の結合ユニット。
【請求項１】
複数の数Ｚ１，Ｚ２，…，ＺＲから最大の数を検出するための方法であって：
ａ）前記数の各々を二つ以上のバイナリセグメントＺｊ（Ｎ−１），Ｚｊ（Ｎ−２），…，Ｚｊ（０）に分割するステップであって、前記セグメントのビット長が、それらの有意性のレベルに従って決定され、そして前記セグメントのセットは、それらの有意性のレベルに従って配列され、セグメントの第一のセットＺｊ（Ｎ−１），Ｚｊ（Ｎ−１），…，Ｚｊ（Ｎ−１）は、前記数の最上位セグメントを含み且つセグメントの最終セットＺｊ（０），Ｚｊ（０），…，Ｚｊ（０）は、前記数の最下位セグメントを含むステップと；
ｂ）同一レベルの有意性を有するセグメントＺ１（Ｋ），Ｚ２（Ｋ），…，ＺＲ（Ｋ）の絶対値を同時に比較し、それらの最上位セグメントの絶対値が最大である数を指定するグループを決定し、そして最下位セグメントについて、それらの絶対値サイズを指示するグレードを、同一レベルの有意性の他のセグメントの絶対値と比較して評価するステップと；
ｃ）セグメントの第二のセットＺ１（Ｎ−２），Ｚ２（Ｎ−２），…，ＺＲ（Ｎ−１）からスタートして、前記グループに対応する数のセグメントのグレードを比較し、且つ前記グループにおける他の数の指示に対応する最も高いグレードよりも低いグレードを有するいかなる数の指示をも前記グループから除去するステップと；
ｄ）最後のセットのセグメントＺ１（０），Ｚ２（０），…，ＺＲ（０）に到達するまで、または、単一の数が前記グループによって指定されるまで、ステップｃ）を繰り返すステップと；
を有する方法。
【請求項２】
数は、多重三次元ラスタ画像のピクセルの深さ値である請求項１に記載の方法。
【請求項３】
数をしきい値と比較し、且つそれらの値が前記しきい値の上または下である数についてのみ最大数の検出を実行するステップをさらに有する請求項１に記載の方法。
【請求項４】
最小数を決定するために、グループが、それらの最上位セグメントの絶対値が最も小さい数を指定すべく決定され、且つ数の指定は、それらのグレードが、前記グループにおける他の数の指示に対応する最小のグレードよりも大きいときはいつも前記グループから除去される請求項１に記載の方法。
【請求項５】
全てのセグメントは、同一のビット長からなる請求項１に記載の方法。
【請求項６】
一つ以上の最下位セグメントのビット長は、最上位セグメントのビット長よりも大きい請求項１に記載の方法。
【請求項７】
各サブ画像における同一の空間位置に対応するピクセルの深さ値Ｚ１，Ｚ２，…，ＺＲを検査し、そして最大の深さ値を有するピクセルの内容をコンポジットすることによって複数の三次元サブ画像をコンポジット処理するための方法であって：
ａ）前記深さ値の各々を二つ以上のバイナリセグメントＺｊ（Ｎ−１），Ｚｊ（Ｎ−２），…，Ｚｊ（０）に分割するステップであって、前記セグメントのビット長が、それらの有意性のレベルに従って決定され、そして前記セグメントのセットは、それらの有意性のレベルに従って配列され、セグメントの第一のセットＺｊ（Ｎ−１），Ｚｊ（Ｎ−１），…，Ｚｊ（Ｎ−１）は、前記深さ値の最上位セグメントを含み且つセグメントの最終セットＺｊ（０），Ｚｊ（０），…，Ｚｊ（０）は、前記深さ値の最下位セグメントを含むステップと；
ｂ）同一レベルの有意性を有するセグメントＺ１（Ｋ），Ｚ２（Ｋ），…，ＺＲ（Ｋ）の絶対値を同時に比較し、それらの最上位セグメントの絶対値が最大である深さ値を指定するグループを決定し、そして最下位セグメントについて、それらの絶対値サイズを指示するグレードを、同一レベルの有意性の他のセグメントの絶対値と比較して評価するステップと；
ｃ）セグメントの第二のセットＺ１（Ｎ−２），Ｚ２（Ｎ−２），…，ＺＲ（Ｎ−１）からスタートして、前記グループに対応する深さ値のセグメントのグレードを比較し、且つ前記グループにおける他の深さ値に対応する最も高いグレードよりも低いグレードを有するいかなる深さ値の指示をも前記グループから除去するステップと；
ｄ）最後のセットのセグメントＺ１（０），Ｚ２（０），…，ＺＲ（０）に到達するまで、または、単一の深さ値が前記グループによって指定されるまで、ステップｃ）を繰り返すステップと；
を有する方法。
【請求項８】
深さ値をしきい値と比較し、且つそれらの値が前記しきい値の上または下である深さ値についてのみ最大数の検出を実行するステップをさらに有する請求項７に記載の方法。
【請求項９】
最小数を決定するために、グループが、それらの最上位セグメントの絶対値が最も小さい深さ値を指定すべく決定され、且つ深さ値の指定は、それらのグレードが、前記グループにおける他の数の指示に対応する最小のグレードよりも大きいときはいつも前記グループから除去される請求項７に記載の方法。
【請求項１０】
全てのセグメントは、同一のビット長からなる請求項７に記載の方法。
【請求項１１】
一つ以上の最下位セグメントのビット長は、最上位セグメントのビット長よりも大きい請求項７に記載の方法。
【請求項１２】
複数の三次元サブ画像をコンポジットするためのシステムであって：
ａ）複数のピクセルの深さ値のビット群を同時に導入するためのバスライン群であり、各バスライン上に同一レベルの有意性を有するビット群が導入され、前記ビット群の全ての論理状態が「１」であるときはいつも、前記ライン群の論理状態が「１」にセットされ、そしてもしも前記ビット群の少なくとも一つの論理状態が「０」であれば、その論理状態が「０」にセットされるバスラインと；
ｂ）前記サブ画像における同一の空間位置に対応するピクセル群のデータを同時に読み取り、各読み取りピクセルの深さ値を二つ以上のセグメントに分割し、前記セグメントを前記バスのそれぞれのライン上に導入し、前記ライン群の論理状態を検知し、そしてそれに応じて最大の絶対値を有する深さ値を指定する前記値の最上位セグメントについての、および同一レベルの有意性の他のセグメントの絶対値と比較してそれらの絶対値サイズを指示する最下位セグメントストップマークグレーディングについての中間比較結果を同時に生起するための結合ユニットと；
ｃ）対応するストップマークグレーディングが、前記中間比較結果の一つに関連する最大のストップマークグレーディングよりも小さいものについての先に生起された中間比較結果深さ値指定を除去することによって、最上位セグメントのセットに続くセグメントのセットからスタートする、有意性の順における各後続のセグメントのセットについての中間比較結果を連続的に生起するためのプロモーションマトリクスと；
を具備し、
前記プロモーションマトリクスは、ピクセルデータがそれぞれの結合ユニットからコンポジット処理のために回復され得るように、現在生起された中間比較結果が単一指定を含むことを指示することができるシステム。
【請求項１３】
現在生起された中間比較結果が単一の指定を含むことがプロモーションマトリクスによって指示されたときはいつでも、後続のプロモーションマトリクスの動作を抑止するための抑止手段をさらに備える請求項１２に記載のシステム。
【請求項１４】
当該システムが単一の集積回路チップ上にインプリメントされた請求項１２に記載のシステム。
【請求項１５】
チップは、ＶＬＳＩインプリメンテーションである請求項１２に記載のシステム。
【請求項１６】
ワイアド−アンドバスのライン上にピクセルの深さ値のセグメントのビット群を導入し、キャリーアウトおよびストップマーク指示を発行し、そして対応する外部の有効化指示に従って前記ピクセルのデータを有効化するための結合ユニットであって：
ａ）前記バスのそれぞれのライン上への前記深さ値の最上位セグメントのビット群の導入を有効化し、前記ラインの論理状態を、最上位ラインからスタートして検知し、そしてもしも検知されたラインおよび対応するビットの論理状態が、「０」ならば、それに続くバスラインの検知を抑止し、さもなければ前記セグメントの最後まで進めるべく検知を有効化し、そしてキャリーアウト指示を発行するための第一のセグメント論理回路要素と；
ｂ）前記バスのそれぞれのライン上への前記深さ値の最下位セグメントのビット群の導入を有効化し、前記ラインの論理状態を、最上位ラインからスタートして検知し、そしてもしも検知されたラインおよび対応するビットの論理状態が、「０」ならば、それに続くバスラインの検知を抑止し且つそのセグメントにおける前記ビットの有意性のレベルに対応するストップマーク指示を発行し、さもなければ前記セグメントの最後まで進めるべく検知を有効化し、そして前記セグメントにおける最上位ビットよりも高い一つのレベルである有意性のレベルを有するストップマーク指示を発行するための一つ以上の非第一のセグメント論理回路要素と；
ｃ）前記有効化指示が受信されたときはいつでも前記データの出力を有効化するためのゲートと；
を具備し、
それに導入されたビット群の全ての論理状態が「１」であるときはいつでも前記バスの各ラインの論理状態が、「１」にセットされ、且つもしも前記ビット群の少なくとも一つの論理状態が「０」であれば、それは「０」にセットされ、そして前記有効化指示は、前記キャリーアウトおよびストップマーク指示に従って外部的に決定される結合ユニット。
【請求項１７】
深さ値の値が、しきい値よりも大きいときはいつでも、第一のおよび非第一のセグメント論理回路要素の動作を有効化するための手段をさらに備える請求項１６に記載の結合ユニット。
【請求項１８】
該手段は、深さ値の値が、しきい値よりも小さいときはいつでも、第一のおよび非第一のセグメント論理回路要素の動作を有効化する請求項１７に記載の結合ユニット。
【請求項１９】
検知されたラインおよび対応するビットの論理状態が「１」であるときはいつでも、それに続くバスラインの検知は抑止される請求項１６に記載の結合ユニット。
【図１】
【図４】
【図５】
【図６】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図４】
【図５】
【図６】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公表番号】特表２００７−５２８０３３（Ｐ２００７−５２８０３３Ａ）
【公表日】平成１９年１０月４日（２００７．１０．４）
【国際特許分類】
【出願番号】特願２００６−５０２６２３（Ｐ２００６−５０２６２３）
【出願日】平成１６年１月２８日（２００４．１．２８）
【国際出願番号】ＰＣＴ／ＩＬ２００４／００００７９
【国際公開番号】ＷＯ２００４／０７０６５２
【国際公開日】平成１６年８月１９日（２００４．８．１９）
【出願人】（５０５２７１７６９）ルシッド インフォメーション テクノロジー リミテッド (2)
【Ｆターム（参考）】
【公表日】平成１９年１０月４日（２００７．１０．４）
【国際特許分類】
【出願日】平成１６年１月２８日（２００４．１．２８）
【国際出願番号】ＰＣＴ／ＩＬ２００４／００００７９
【国際公開番号】ＷＯ２００４／０７０６５２
【国際公開日】平成１６年８月１９日（２００４．８．１９）
【出願人】（５０５２７１７６９）ルシッド インフォメーション テクノロジー リミテッド (2)
【Ｆターム（参考）】
[ Back to top ]