透過的レンダリングのためのシステムと方法
可視化ＡＰＩから来る未処理の多角形幾何学形状及び視野パラメータを受け入れ、奥から手前の順に該多角形をソートし、その後ソートした三角形をＯｐｅｎＧＬなどのグラフィックスＡＰＩに供給するシステム、方法及びコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にグラフィックス処理（ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ）に関するものである。
【発明の背景】
【０００２】
航空宇宙産業、自動車産業など数多くの産業において、製造業者は初期段階でデザインの問題を発見すべくインタラクティブに（ｉｎｔｅｒａｃｔｉｖｅｌｙ）製品のデザインを見て点検するために可視化技術に依存することが増えてきている。製品構造全体を見てそのサブシステムのそれぞれを点検し易くする能力は、如何なる可視化システム（ｖｉｓｕａｌｉｚａｔｉｏｎ ｓｙｓｔｅｍ）においても不可欠とされている。したがって、本来なら陰になって見えない（ｏｃｃｌｕｓｉｏｎ）デザインの詳細が見えるようにするため、一部の選択した部品を透過的にレンダリングする（ｒｅｎｄｅｒ ｔｒａｎｓｐａｒｅｎｔｌｙ）ことが望ましい。また、ガラスなど透過的な素材からできている部品もあり、それらを透過的にレンダリングすることはそのシーンをよりリアルに見せる。したがって、インタラクティブなフレームレート（ｉｎｔｅｒａｃｔｉｖｅ ｆｒａｍｅ ｒａｔｅ）でオブジェクト（ｏｂｊｅｃｔ）にリアルな透過性（ｔｒａｎｓｐａｒｅｎｃｙ）を持たせることは効果的な可視化（ｖｉｓｕａｌｉｚａｔｉｏｎ）のために重要なのである。
【０００３】
新しいグラフィックシステムの殆どにおいては、「アルファブレンディング」（ａｌｐｈａ ｂｌｅｎｄｉｎｇ）と呼ばれるプロセスにより透過的レンダリングが実現されている。透過性を正確にするには、一画素に寄与する全ての多角形の色を奥から手前の順に「ブレンド」しなければならない。フレームごとに正確にソーティングを行なう必要があるため、大きなモデルのインタラクティブな透過的レンダリングは困難な課題であった。
【０００４】
従来提案されてきた三角形ソーティングの方法（ｔｒｉａｎｇｌｅ ｓｏｒｔ ｍｅｔｈｏｄ）は、画像に基づいたものとオブジェクトに基づいたものの二種類に分類することができる。画像スペースに基づいた方法では、特殊なグラフィックハードウェアを利用する必要がある。この種の方法では、深さに沿って奥から手前の順に一層ずつ透過的な多角形をレンダリングする。各層のレンダリングには個別のレンダリングのパスが必要となり、そのシーンの最大深さの数だけレンダリングのパスが必要である。異なるパスからの各画素の色をブレンドするために追加のメモリバッファが必要となる。オブジェクトスペースに基づいたの方法では、その時の視野方向に対して全ての多角形をソートする。これらのソートされた多角形はその後、レンダリングのために奥から手前の順にグラフィックスのパイプラインに供給される。この種類の方法の殆どは、Ｚ−バッファというハードウェアが利用できるようになる以前に可視性の問題を解決するために提案されたものである。これらの各方法には深刻な限界があり、大きな透過的モデルのレンダリングに効果的に利用することはできなかった。例えば、深さソーティング法にはＯ（Ｎ２）の計算の複雑さがあり、ＢＳＰ（バイナリスペースパーティション）ソーティング法（ｂｉｎａｒｙ ｓｐａｃｅ ｐａｒｔｉｔｉｏｎ ｓｏｒｔ ｍｅｔｈｏｄ）には大きな木構造（ｔｒｅｅ ｓｔｒｕｃｔｕｒｅ）を構築しメモリに保存する手間がかかる。大きな透過的のモデルのレンダリングをインタラクティブなレートで行なうことを可能にするための新たなアプローチが望まれている。
【０００５】
ＢＳＰツリーの構築（ｔｒｅｅ ｃｏｎｓｔｒｕｃｔｉｏｎ）に関するこれまでの研究は、一つのファクター、すなわち最終的なＢＳＰツリー（ｔｒｅｅ）における三角形の数を最小限にすることに焦点をあてており、実用面では等しく重要であるその他のファクターは考慮されていなかった。これらその他のファクターには、ＢＳＰツリーの構築にかかる時間、ＢＳＰツリー内の三角形をソートするのにかかると予想される時間などが含まれる。様々なファクターによって課された様々な条件を満たしつつ効率的にＢＳＰツリーを構築することは困難ではあるが、このアプローチをより実用的なものにするにはきわめて重要である。
【０００６】
深さソーティングに関するこれまでの研究は、一対の三角形の陰になって見えない部分がある関係を正確に割り出すことのできないようなテスト用アルゴリズムを用いていた。その結果として、二つの三角形が既に正しい順序に並んでいたとしても視野に依存した三角形スプリットが起こることがあった。そのような不必要な三角形スプリットを避け、より良いソーティング結果を得るために、陰になって見えない部分があることをテストするための、より洗練されたアルゴリズムが必要とされている。
【０００７】
したがって本技術分野では、より良い透過的レンダリングのためのシステム、方法及びコンピュータプログラム製品が求められている。
【発明の概要】
【０００８】
好ましい実施例では、可視化ＡＰＩから来る未処理の多角形幾何学形状及び視野パラメータを受け入れ、奥から手前の順に多角形をソートし、その後ソートした三角形をＯｐｅｎＧＬなどのグラフィックスＡＰＩに供給するシステム、方法及びコンピュータプログラム製品を提供する。
【０００９】
上記は、後述する本発明の詳細な説明を当業者がより良く理解できるよう、本発明の特徴及び技術的な効果についてかなり広範に概要を述べたものである。本発明の更なる特徴と効果は本発明の請求項の主題となるものあり、以下において説明する。当業者は、開示されている概念及び特定の実施例を、本発明と同じ目的を果たすために他の構成を変更もしくはデザインするための基礎として容易に使用できることを理解するであろう。当業者はまた、これらの同等な構築は最も広義な形での本発明の精神及び範囲から逸脱するものではないことを認識するであろう。
【００１０】
下記の発明の詳細な説明に進む前に、本特許全体に亘って用いる特定の単語及び語句を定義することは有意義であろう。「含む」及び「から成る」という用語並びにそれらの派生語は、制限のない包含を意味する。「または」と言う用語は包括的で、その意味するところは及び／またはということである。「に関連する」及び「と関連する」という語句並びにそれらの派生語は、含む、含まれる、相互に関連する、包含する、包含される、〜を含む、〜内に含まれる、相互に接続する、〜を包含する、〜に包含される、〜に接続するもしくは〜と接続する、〜と連結するもしくは〜に連結する、〜と伝達できる、〜と提携する、インターリーブする、並列する、〜に隣接する、〜に境を接するもしくは〜と境を接する、〜を有する、〜の性質を有する、等を意味する。「コントローラ」という用語は、少なくとも１つの操作を制御するデバイス、システム、またはそれらの部品の全てを意味し、そのようなデバイスが、ハードウェア、ファームウェア、ソフトウエアまたは少なくとも２つの同様なものを組み合わせたものに実装されているかを問わない。特定のコントローラーに関連する機能性は集中型でも分散型でもよく、ローカルかまたは遠隔かは問わないことに留意されたい。本特許では特定の単語および語句の定義を提供するが、当業者は、そのような定義は、殆どではないにしても多くの場合、そのように定義された単語および語句の従来の使用および今後の使用に当てはまることが理解できるであろう。
【発明を実施するための最良の形態】
【００１１】
以下に考察する図１乃至図１１及び本特許に記載の本発明の原理を説明するのに用いた様々な実施例は例を示すためだけのものであり、如何なる場合でも本発明の範囲はこれらのみに限定して解釈されるべきではない。当業者は、本発明の原理は適宜に準備されたものであればどのようなデバイスを用いても実施できることを理解するであろう。本出願の多数の革新的な教示を、現時点で好ましいとする実施例を特に参照しながら説明する。
【００１２】
好ましい実施例では、可視化ＡＰＩから来る未処理の多角形幾何学形状及び視野パラメータを受け入れ、奥から手前の順に多角形をソートし、そしてソートした三角形をＯｐｅｎＧＬなどのグラフィックスＡＰＩに供給するシステム、方法及びコンピュータプログラム製品を提供する。
【００１３】
本願ではでは特に三角形について説明しているが、当業者は、開示した実施例は全ての平面形状、例えば凸面または凹面の多角形であってもよく、単純でも複雑でもよいと認識するであろう。また区分面（ｐａｒｔｉｔｉｏｎ ｐｌａｎｅ）で切ったときに二つ以上の形状にスプリットする方法がある限り、曲線状のまたはプロシージャで定義された形状（ｐｒｏｃｅｄｕｒａｌｌｙ−ｄｅｆｉｎｅｄ ｓｈａｐｅ）でもよい。
【００１４】
図１は好ましい実施例を実現できるデータ処理システムのブロック図である。図示したデータ処理システムは、プロセッサ１０２、２次キャッシュ／ブリッジ１０４及びローカルシステムバス１０６を含み、プロセッサ１０２は２次キャッシュ／ブリッジ１０４に、そして２次キャッシュ／ブリッジ１０４はローカルシステムバス１０６に接続されている。ローカルシステムバス１０６は、例えば、周辺構成要素相互接続（ＰＣＩ）アーキテクチャバスでもよい。図示した例ではローカルシステムバスにはまたメインメモリ１０８及びグラフィックスアダプタ１１０も接続されている。
【００１５】
ローカルエリアネットワーク（ＬＡＮ）／ワイドエリアネットワーク／ワイアレス(例えばＷｉＦｉ)アダプタ１１２などのその他の周辺構成要素もローカルシステムバス１０６に接続されるようにしてもよい。拡張バスインターフェース１１４によりローカルシステムバス１０６が入力／出力（Ｉ／Ｏ）バス１１６に接続される。Ｉ／Ｏバス１１６はキーボード／マウスアダプタ１１８、ディスクコントローラ１２０及びＩ／Ｏアダプタ１２２に接続されている。
【００１６】
図示した例のＩ／Ｏバス１１６にはまたオーディオアダプタ１２４も接続されており、オーディオアダプタ１２４には音声を再生するためのスピーカー(図示せず)を接続することもできる。キーボード／マウスアダプタ１１８はマウス、トラックボール、トラックポインターなどのポインティングデバイス(図示せず)を提供する。
【００１７】
当業者は、図１に示したハードウェアの詳細については様々であり得ると理解するであろう。例えば、図示したハードウェアに加えてまたはそれらの代わりに、光ディスクドライブ等のその他の周辺構成デバイスを用いることもできる。図示した例は説明のためだけのものであって、本発明に関する構造上の制限を示唆するものではない。
【００１８】
本発明の好ましい実施例によるデータ処理システムはグラフィカルなユーザーインターフェースを用いたオペレーティングシステムを含む。該オペレーティングシステムは該グラフィカルなユーザーインターフェースに複数のウィンドウを同時にレンダリングすることを可能にし、各レンダリングウィンドウは異なるアプリケーションとのまたは同じアプリケーションの異なるインスタンスとのインターフェースを提供する。ユーザーは該グラフィカルなユーザーインターフェースのカーソルを該ポインティングデバイスを介して操作できる。該カーソルの位置を変えること及び／またはマウスボタンをクリックするなどのイベントによって、望ましいレスポンスを得るように作動させる。
【００１９】
適宜に変更すれば、ワシントン州レドモンド市にあるマイクロソフト社の製品であるマイクロソフトウィンドウズＴＭの一バージョンなどの様々な市販のオペレーティングシステムの一つを用いることができる。説明したような本発明にしたがって該オペレーティングシステムを変更または作成してもよい。
【００２０】
好ましい実施例は透過的レンダリングが現在抱える問題に対処するものである。図２の概略アーキテクチャ図に示すように、開示したシステム、方法及びコンピュータプログラム製品は、可視化ＡＰＩとグラフィックスＡＰＩの間で機能する。
【００２１】
該システムは可視化ＡＰＩから来る未処理の多角形幾何学形状及び視野パラメータを受け入れ、好ましくは実質的に奥から手前の順に多角形をソートし、そしてソートした三角形をＯｐｅｎＧＬなどのグラフィックスＡＰＩに供給する。そうする際に、開示されたシステムは二つの従来型のソーティング方法を新規のやり方で統合して両方の利点を十分に引き出し、新規のキャッシュに格納するストラテジーを可能にすると共に、主要なアルゴリズムも大きく改良できるようにする。そして、処理時間、レンダリングの速度、レンダリングの質及びメモリ消費など様々なファクターに関する利点・不利点のトレードオフを実現できる顕著な柔軟性を提供することにより、システムを実用面で改善する。開示したシステムは、最大で数十万もの多角形までの大きなモデルを市販のグラフィックス用ハードウェアを用いてインタラクティブなフレームレートで、殆ど不自然な結果も無くレンダリングできることが証明されている。
【００２２】
ＢＳＰソーティング法の特徴は深さソーティング法の特徴を補完するものである。ＢＳＰソーティング法は、非常に大きなツリー構造をメモリに維持することによりＯ（Ｎ）次のコンプレクシティを実現する。深さソーティング法はメモリのオーバーヘッドが少なくて済むが、Ｏ（Ｎ２）次のコンプレクシティを持ち、これはまったく望ましくない。本願で開示されている三角形ソーティング用アルゴリズムはこれら二つの方法を統合して両方の利点を引き出すものである。具体的には、（従来のやり方ではＢＳＰツリーは三角形が一つのリーフノードで構築されていたのに対し）少なくとも幾つかの実施例においては、ＢＳＰツリーは三角形が複数あるリーフノードで構築される。そして該ＢＳＰツリーを走査し、走査中に各リーフノード上の三角形を深さソーティングすることにより三角形がソートされる。
【００２３】
一つのリーフノード上で許容できる三角形の最大数βを指定することにより、開示されたアルゴリズムの挙動を、これら二つの方法の間で容易に調整でき、レンダリングの速度とメモリ消費の望ましいトレードオフが実現できる。例えば、βが１であると指定されると、開示されたアルゴリズムは従来のＢＳＰソーティング用アルゴリズムへと戻り、βが三角形の合計数であるＮと指定されると、開示されたアルゴリズムは従来の深さソーティング用アルゴリズムへと戻る。βが２とＮ−１の間の数値であると指定されると、我々のアルゴリズムの挙動もまたこれら二つの従来法の中間のものとなり、βが大きくなるにつれソーティング速度は落ちるがメモリ内のツリーサイズは小さくなる。また、好ましい実施例では深さソーティング用アルゴリズムには、二つの異なるモードがあり、深さソーティング用アルゴリズムがレンダリングの速度とレンダリングの質に関して、更なる柔軟性が提供される。高次なモードでは正確なレンダリングの結果が保証され、基本モードでは不自然な結果があるかもしれないがレンダリングの速度が速くなる。
【００２４】
ＢＳＰ構築アルゴリズムを改良するために、様々な技術を開示する。幾つかの実施例においては、実用的なアプリケーションに重要な複数のファクターを考慮した区分面の候補の質を評価するために新しい判断基準を用い、良い区分面の迅速な選択を促進する形状知識情報を効率的に抽出するために新しい方法を用いる。実験結果では、開発されたＢＳＰ構築アルゴリズムにより１．２ＧＨｚプロセッサのＰＣでおよそ１秒で２万個の三角形の高品質のＢＳＰツリーを作成できることが示された。
【００２５】
本願では、一対の三角形間での陰になって見えない部分がある関係を正確に識別するための洗練されていながら計算に関しては効率的なテスト用アルゴリズムにより、周知の深さソーティング用アルゴリズムが改良されている。その様にして不必要な三角形スプリットをなくすことができる。
【００２６】
更に、ある有限数の視野方向一組に対してソートされた幾何学形状をキャッシュに格納して、視野をキャッシングするアルゴリズムが開示されている。これらのキャッシュに格納されたされた三角形の配列を用いると、その時の視野方向の現実の三角形の配列をキャッシュに格納されたレファレンス方向の中で最も近いものの三角形の配列で近似することにより、透過的レンダリングの速度を上げることができる。
【００２７】
第一フレームの遅れを最小化するために、事前処理ステップとしてのＢＳＰツリーの構築は出来る限り効率的なものでなくてはならない。ＢＳＰツリーは一度構築されればその後の全てのフレームのレンダリングに使用されるため、出来る限り最適化されたものでなくてはならない。この分野での従来の研究は単一の判断基準、つまり最終的なＢＳＰツリーにおける三角形の数を最小限にすることに焦点を当てていた。
【００２８】
好ましい実施例においては、区分面評価のための新しい判断基準と、最良の区分面を効率的に選択するための新しい知識主導アルゴリズムとから成るＢＳＰツリー構築用アルゴリズムが使用されている。新しい判断基準は、各フレームの三角形をソーティングするための予測所要時間とＢＳＰツリーの構築時間との両方を短縮するための必要条件を満たすために作られたものである。
【００２９】
同一のリーフノードにおける三角形のソーティングに使用される深さソーティング用アルゴリズムは、陰になって見えない部分があるかどうかのテストを異なるレベルで用い、二つの異なるモードで作動できる。基本ソーティングモードでは、視野座標システムにおける三角形の最大Ｚ座標に基づいて三角形をソートする。高度なソーティングモードでは、陰になって見えない部分がある環状の関係がない場合、更に洗練された形で陰になって見えない部分があるかどうかをテストし、三角形をスプリットせずに正確な結果を保証する。
【００３０】
図２は、開示された透過性レンダリング用ソフトウェアシステムの実施例の概略を示す。システムへのインプット情報は、その時の視野方向と可視化ＡＰＩから供給される透過的ノードである。出力情報は、レンダリングのためにグラフィックスのパイプラインに供給される奥から手前の順にソートされた三角形である。透過的ノードはレンダリングされる全ての透過的三角形を含むデータ構造で、シーンのグラフ中の単一もしくは複数の部分に対応していることもある。ＢＳＰツリーはそれが存在していない時点で、第一フレームの始めに先ず入力幾何学形状から形成される。ＢＳＰツリーは一度形成されると透過的ノードにおいてキャッシュに格納され、その後のフレームに用いられる。この時点でＢＳＰツリーの中に組み込まれた透過的三角形は、次に三角形ソーティング用モジュールによりその時の視野方向に対してソートされる。法線情報及び色情報も含め、ソートされた三角形は（ＯｐｅｎＧＬなどの）グラフィックスＡＰＩにレンダリングのために供給される。視野キャッシング用モジュールはオプションであり、これが作動可能とされている場合、ソートされた三角形は視野方向とともに透過的ノードのキャッシュに格納される。その後、近接した視野方向のレンダリングが要求された場合、三角形のソーティングは必要なく、このキャッシュに格納された三角形のデータをレンダリングのために直接呼び出すことができる。
【００３１】
バイナリスペースパーティション（ＢＳＰ）ツリー：繰り返し実行され、多数の入力オブジェクトを扱うプロセスに関してその効率改善のために重要な方法は、それらのオブジェクトの間に一貫した構造を構築しそれを維持することである。例えば、幾何学問題で頻繁に使用されるストラテジーでは、大規模問題を簡単で効率的に扱うことができる複数の小規模問題に分断する「分断攻略」アプローチの再帰的使用がある。ＢＳＰツリーはこの種の構造の一つであり、各ノードは三次元空間領域に置かれた一組のエレメントを表す。全てのエレメントを含むルートノードからスタートし、ユークリッド空間を重複しない二つの領域に分断するために区分面が使用される。区分面により切り分けられたエレメントは二つ以上のエレメントにスプリットする。各領域のエレメントに子ノードが作られ、これがＢＳＰツリーの新しいリーフノードとなる。各リーフノードのこの区分は、事前に設定された条件が満たされるまで再帰的に継続して行われる。
【００３２】
各ＢＳＰノードの二つの子ノード（ｃｈｉｌｄ）は線形の区分面で隔てられているため、視野ポイントから離れた子ノードの陰になって他の子ノードに見えない部分がある状態になることはない。従って、ＢＳＰ木構造（ｔｒｅｅ ｓｔｒｕｃｔｕｒｅ）は三角形をソーティングするために特に有用である。ＢＳＰツリー内に形成された潜在的な可視性の順序を利用することにより、その全てのノードの可視性ソーティング（ｖｉｓｉｂｉｌｉｔｙ ｓｏｒｔｉｎｇ）が単にツリーを走査することで達成できる。ＢＳＰツリーはシーンの幾何学形状を特徴づけ、視野方向には拠らないため、シーンの内容に変化がない限り異なる視野方向の正しい可視性の順序を入手するために同一のＢＳＰツリーを使用できる。このことは、静的な幾何学形状の可視化アプリケーションで特に有用である。
【００３３】
好ましい実施例のＢＳＰ構築アルゴリズム（ＢＳＰ ｃｏｎｓｔｒｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ）は、余計なツリー構築時間（ｔｒｅｅ ｃｏｎｓｔｒｕｃｔｉｏｎ ｔｉｍｅ）を掛けずに三角形のソーティングを可能にするＢＳＰツリーを作成する。ＢＳＰツリーの構築に影響を及ぼす唯一の重要変数は、スプリットされる各リーフノードにおける区分面の選択である。従って、区分面の候補の評価にどのような判断基準を用いるべきか、また最良の区分面を如何にして効率的に選択するかということが重要課題となる。本願においては、ツリーの構築時間や最終的なツリーの質など複数のファクターを考慮した判断基準を選択することで第一の課題に対応し、最良の候補を迅速に識別するために抽出された形状知識を利用することで第二の課題に対応している。下記の説明は特に三角形エレメントに関連しているが、開示されたプロセスは明らかに一般的な平面多角形に応用可能なものであると当業者は認識するであろう。
【００３４】
図３は開発されたＢＳＰツリーの構築アルゴリズムの概略を示す。このアルゴリズムは三つのステップから成る：事前処理、区分面の選択、ノードの構築である。事前処理ステップは一度しか呼び出されないが、その後の二つのステップはスプリットされる各ＢＳＰノードに対して繰り返し呼び出される。三角形の法線情報及び位置情報を分析することで、区分面の候補をより効率的に選択するために使用される形状知識が事前処理ステップで抽出される。このステップにおいてはまた、全ての入力三角形を含むルートノードが作成され、これを保持するＢＳＰノードリストが初期化される。ノードリストは、スプリットされる全てのリーフノードを保持した待ち行列タイプ構造のもので、このリストが空になった場合再帰的な構築プロセスは終了する。区分面選択のメカニズムは仮説と検証の方法に基づいており、つまり最高の結果を出し得る面を決定するために幾つかの候補面が選択され評価される。ノード構築ステップにおいては、各三角形は選択された区分面に関して分類され、区分面を横切るかどうかに基づいてスプリットされる。その後、その時のＢＳＰノードに対し単一もしくは複数の子ノードが作成される。事前に設定された判断基準に基づき更なる再分断が必要な場合には、新しく作成された子ノードの各々がノードリストに付け加えられる。
【００３５】
ＢＳＰ構築アルゴリズムの課題の一つは、一組の三角形を含む所定のＢＳＰノードに対する異なる区分面を比較するために、どの判断基準を用いるべきかということである。好ましい実施例においては、ツリー構築時間及び構築されるＢＳＰツリーの質に関する様々な目標を反映した、ｗとして表される判断基準で区分面は評価される。最短のツリー構築時間とより良いＢＳＰツリーを達成する可能性が、ｗの最大値を有する区分面において最も高くなるようにこの判断基準はデザインされている。
【００３６】
表１は区分面Ｐの候補を特徴づけるために使用されるパラメータを示す。
【００３７】
【表１】
【００３８】
一組の三角形と区切り面Ｐの候補を含むリーフノードＬがある場合、表１に示される四つのパラメータがＰの質を特徴づけるために用いられる。パラメータnCに関しては、三角形が複数の三角形にスプリットされ、そのそれぞれが区分面Ｐの正の側か負の側に位置するようになるので、パラメータnCは判断基準ｗに悪い影響を及ぼすことは明らかである。三角形をスプリットすることは、一般的に結果としてツリーサイズがより大きくなりツリー構築時間が長くなる。また、ＢＳＰツリーにおける三角形の数が増加すると、三角形のソーティングも時間がかかる。Ｐ上にある三角形は同一平面上にあり、またノードＬのフロント子ノード及びバック子ノードに対するこれら三角形全体の順序は容易に入手できるため、Ｐにおける三角形の順序は任意のものとすることができる。これら三角形のソーティングのコストはゼロであるため、パラメータnOは明らかに、判断基準ｗに対して良い影響を与える。
【００３９】
ｎF及びnBの判断基準ｗへの影響はそれ程明らかなものではない。ツリーバランス、つまりnF及びnB間の差の絶対値は、ＢＳＰツリーにおける全ての三角形をソートするという目的においては重要ではない。しかし、ツリーのバランスが崩れた場合構築パイプラインを通る三角形の数が増加するため、ツリーバランスはツリー構築時間に甚大な影響を与えるということが明らかになっている。図４Ａ及び図４Ｂに示される二つの極端なケースを分析しこれらを比較することで、このことは浮き彫りになる。図４Ａは非常に良くバランスの取れたツリー区分を示し、図４Ｂは極端にバランスの崩れたツリー区分を示している。
【００４０】
【００４１】
上記の分析に基づいて、好ましい実施例では区分面の評価に下記の判断基準が用いられる。
ｗ＝ｎＯ−ＫＣｎＣ−ａｂｓ（ｎＦ−ｎＢ）（１）
ここで、ＫＣは三角形をスプリットすることの重要性を示す定数であり、ａｂｓという記号は絶対値オペレーションを意味する。三角形をスプリットすることで、その時のノードをスプリットするオペレーションが遅くなるのみならず、扱う三角形の数が増えるため、最終的なツリーサイズが大きくなりツリー構築が更に遅くなるという事実を示すために、ＫＣの値は一般的に１より大きく設定される。
【００４２】
ＢＳＰツリー構築パイプラインから、正しい区分面の選択が構築時間及び最終的なＢＳＰツリーサイズの両方に影響する課題であることが分かる。方程式（１）が示す評価判断基準は、区分面上の三角形が多くなり、区分面が切り分ける三角形の数が少なくなり、区分面のそれぞれの側の三角形のバランスができるだけ取れるように区分面を選択するべきである、ということを示している。好ましい実施例においては、入力三角形は事前処理ステップで、それぞれが特定の特徴もしくは位置づけパターンの情報を伝達する一貫した階層グループに編成される。このように編成された三角形はその後、質の高い区分面の候補の迅速な識別のために用いられる。
【００４３】
図５は、３２ビットの整数としての面インデックスのレイアウトの一例を示す。図６は、抽出した階層グループ（ｈｉｅｒａｒｃｈｉｃａｌ ｇｒｏｕｐ）の一例を示す。
【００４４】
【００４５】
好ましい実施例においては、各三角形の補助面の法線ベクトルとスカラー距離は、我々が面インデックスと呼ぶ単一の正負符号付整数にエンコードされる。面インデックスは、八進インデックス及び六進インデックスのそれぞれを正確にエンコードする３ビットと、二つの角度値のそれぞれを量子化しエンコードするｎビットと、距離値を量子化しエンコードする２５−２＊ｎビットから成る。ここで、ｎは調整可能である。ｎ＝３である場合の面インデックスのレイアウトを図５に示す。ここで、最上位ビットが正負ビットとして確保され、次の６ビットが八進値及び六進値用であり、次の１９ビットが量子化された距離値用であり、最後の６ビットが二つの量子化された角度値用である。
【００４６】
領域、層及び面と呼ばれる三つのグループが抽出され、この３グループの間の階層関係（ｈｉｅｒａｒｃｈｉｃａｌ ｒｅｌａｔｉｏｎ）は図６に図示されている。抽出プロセスは全ての三角形をその面インデックスに対して（降順に、一般性は失わずに）シードリストＳにソートすることから始まる。領域グループは、そのそれぞれがＳ中の同一の八進値及び六進値を有する三角形の隣接リストを含んでおり、その後リストＳから抽出される。八進値及び六進値の定義から、最大で４８個の領域が存在し、同一の領域内の全ての三角形はほぼ同じ方向を向いている。図５から分かるように、各領域内で三角形はその距離によりソートされる。層から同一の距離にある三角形と、同一の領域内にある層はそれらの距離により降順にソートされる。各層内で、同一の量子化された角度値を有し、それ故にほぼ同じ方向を向いている三角形は一つの面へとグループ化される。各面は一つもしくは複数の三角形エレメントから成る。
【００４７】
区分面選択における基本ストラテジーは、選択された一組の面候補を比較し最高質の面を選ぶ「仮説と検証」である。好ましい実施例では、方程式（１）による評価で優れた区分面になる可能性が最も高い区分面の候補を迅速に選択するために、抽出された形状知識が利用される。
【００４８】
殆どのＣＡＤモデルには重要性のある平面の特徴があるため、区分面上の三角形は、モデル内で最も大きな重要性のある面の特徴をあるものを選択した場合、最大多数となる。透過的なオブジェクト内の全ての面の特徴は面グループとして抽出されているため、最も大きな重要性のある面の特徴から成る三角形リストは、単に線形検索で識別できる。その後、リスト内の一つの三角形の補助面が区分面の候補として選択される（この例においては第一の三角形が選択される）。面の特徴の重要性は面グループの面積として、つまりはグループ内の三角形の全面積として定義される。これは、三角形が区分面によって切り分けられる可能性はその面積の増加と共に上昇するからで、それ故、面積が大きい三角形を区分面上に持つ方が良い。
【００４９】
【００５０】
区分面の六つの候補のそれぞれに関して、三角形との関係が演算される。区分面と単一の三角形との関係は四つのタイプ、三角形の上、三角形を横切る、三角形の前および後ろ、の内の一つとして分類されるが、区分面と一組の三角形との関係は、表１に示すようにｎＯ、ｎＣ、ｎＦ及びｎＢの四つのパラメータで特徴づけられる。単一の三角形と面との関係のタイプは、三角形の三つの頂点とその面との関係から容易に推測でき、この関係は半平面テストによって容易に演算できる。
【００５１】
選択された六つの候補面のそれぞれは、入力三角形の補助面である。このことは、少なくとも一つの三角形は切り分けられず、三角形によって形成された形状が凸状に近くない場合に良い結果を出す筈である、という意味で有益である。しかし、この形状がほぼ凸状である場合、選択された区分面は極端にバランスが悪くなる可能性が高く、これは避けるべきである。
【００５２】
【００５３】
【００５４】
その時のＢＳＰノードに対し最良な区分面が選択された後、手前の子ノード、または奥の子ノードもしくはその両方が、必要とされる親子リンクを有するように作られる。区分面の正の側にある三角形は全て手前の子ノード上に置かれるが、負の側にある三角形は全て奥の子ノード上に置かれる。区分面上にある三角形はその時のノード上に留まり、区分面を横切る三角形は二つもしくは三つの三角形にスプリットされる。スプリットされた三角形のそれぞれが、手前の子ノードか奥の子ノードのどちらかに追加される。
【００５５】
同じ子ノード上の三角形の順序が変化しないように、その時のノード上の三角形が順序通りに処理されるような形でノード構築は行われる。例えば、その時のノードにおいて三角形Ａが三角形Ｂに先行し、ノード構築後これらの三角形が同じ子ノードに属する場合、その後も三角形Ａ（もしくはそのスプリットされた三角形）は三角形Ｂ（もしくはそのスプリットされた三角形）に先行する。従って子ノードの三角形リストは、更なるソーティングを行わずとも階層グループの抽出が可能な状態にある。
【００５６】
ＢＳＰツリーに編成された三角形の可視性の順序は、走査時の各リーフノードにおける目の位置と深さソーティング手順に対し、ＢＳＰツリーを奥から手前の順に走査することで演算される。ツリーを走査することでＢＳＰツリーの全てのノードがソートされるが、深さソーティング手順により単一のリーフノード内の三角形に関して、奥から手前への順番が設定される。三角形ソーティング用アルゴリズムの疑似コードの例を以下に示す。ここで、「ｉｎＮｏｄｅ」はソートされるその時の入力ＢＳＰツリーノードであり、「ｉｎＥｙｅ」は目の位置の入力位置であり、「ｏｕｔＴｒｉＬｉｓｔ」は演算されるソートされた三角形の出力リストである。非リーフノード上の三角形に関しては、深さソーティングは必要ないためリーフノード上の三角形に比べソーティングコストはかなり低い。表１に示される数値ｎＣが方程式（１）の評価式に良い影響を与えるのはこのためである。
【００５７】
PROC triangle-sort (inNode, inEye, outTriList)
{
if(inNode is leaf node){
tempList = depth-sort(inNode, inEye);
outTriList.add(tempList);
}
else if(inEye is in the front of inNode.partitionPlane){
triangle-sort(inNode.back, inEye, outTriList);
outTriList.add(inNode.onTriList);
triangle-sort(inNode.front, inEye, outTriList);
}
else if(inEye is at the back of inNode.partitionPlane){
triangle-sort(inNode.front, inEye, outTriList);
outTriList.add(inNode.onTriList);
triangle-sort(inNode.back, inEye, outTriList);
}
else{ // eye is on node.partitionPlane
triangle-sort(inNode.front, inEye, outTriList);
triangle-sort(inNode.back, inEye, outTriList);
}
}
【００５８】
開示された深さソーティング用アルゴリズムは、異なる二つのモードで作動する。基本モードではそれぞれの三角形はポイントとして単純化され、一対の三角形の陰になって見えない部分がある関係は、それらの三角形から目の位置までの距離を比較することで演算できる。このように単純化することで、予想時間Ｏ（ＮｌｏｇＮ）でのＱｕｉｃｋＳｏｒｔなどの効率的な実行が可能となるが、このテストは完全でなく、正確な結果は保証されていない。従って、ソートされた順序が誤りである可能性もあり、これは透過的レンダリングにおいて不自然な結果に繋がる。
【００５９】
高次なモードで作動している場合、次項で説明する陰になって見えない部分があるかどうかをテストする高次なアルゴリズムによって演算された一対の三角形の陰になって見えない部分がある実際の関係に基づいて、深さソーティング用アルゴリズムが最終的なソートリストを作成する。保証された正確な結果を導き出しつつ、陰になって見えない部分がある実際の関係に基づいてソートリストを作成することは、基本Ｚソーティングよりも複雑である。三角形Ａと三角形Ｂの陰になって見えない部分があるかどうかをこれらの三角形だけでテストしても、最終的な奥から手前にソートされたリストにおけるこれら三角形の順序が完全に決定されるわけではない、ということがこの複雑さの原因である。例えば、これら二つの三角形の陰になって見えない部分がある関係が、Ａ＜Ｂとして表される「ＢはＡの陰になって見えない部分があることはない」という関係であると判明した場合、Ａ＞Ｃ０＞Ｃ１．．．＞Ｃｎ＞Ｂとして表される陰になって見えない部分がある連鎖関係を有する単一もしくは複数の三角形Ｃ０，Ｃ１，．．．，Ｃｎが存在する可能性があり、このことにより、最終リストにおいてＡがＢに先行するべきであるということになる。
【００６０】
図７は、ｎ＝０であるケースに対応して描かれた、陰になって見えない部分がある連鎖関係を示す。この図においては、図の真上が「目の位置」となっている。この種のソーティング問題に「分断攻略」のパラダイムを直接応用するのは、可能であるとしても困難であり、一般的に演算複雑性Ｏ（Ｎ２）を有するアルゴリズムが予想される。深さソーティング用アルゴリズムはＢＳＰツリーのそれぞれのリーフノードのみに応用され、単一のリーフノード上の三角形の最大数はコントロール可能であるため、好ましい実施例においてはこの演算負荷は軽減される。
【００６１】
一般的に元のリストにおいてＡがＢより先であると仮定した場合、陰になって見えない部分があるかどうかのテストで求められる結果は、ＢがＡの陰になって見えない部分がある状態にあるかどうかである。我々は先ず、複雑性が徐々に増加する、下記の四つの基本テスト［４］を用いる。どれか一つのテストが成功すれば、「ＢはＡの陰になって見えない部分がある状態ではない」という結論が導き出される。
【００６２】
１．視野座標システムで、Ａの最小Ｚ値はＢの最大Ｚ値よりも大きいか？
２．画像スペース内の、これら二つの三角形の軸に沿った境界ボックスは重なり
合っているか？
３．三角形Ａは、三角形Ｂに対して目の位置と反対側に位置しているか？
４．三角形Ｂは、三角形Ａに対して目の位置と同じ側に位置しているか？
【００６３】
典型的なＣＡＤモデルにおいては、モデルデータは通常スペース的にかなりコンパクトであり、これらの基本テストのどれも成功しない場合が多々ある。このケースを扱うための公知のアプローチは、二つの多角形が既に正しく順序づけられている場合でも視野に依存したスプリットを行うことがあるので、理想的ではない。フレーム毎にキャッシュに格納されたＢＳＰツリーの頻繁なアップデートが必要となるこのようなスプリットを避けるために、好ましい実施例では陰になって見えない部分があるかどうかの高次のテストを適用する。
【００６４】
【００６５】
図８Ａ乃至８Ｃは三角形と、三角形の陰になって見えない領域を示す。図８Ａはもう一方の三角形がそれだけである場合の領域Ｒを示す。図８Ｂは頂点ｖが共有されている場合の領域Ｒｖを示す。図８Ｃは辺ｅが共有されている場合の領域Ｒｅを示す。それそれの図において、目の位置が表示されている。
【００６６】
図９は三角形ＡとＢ領域の境界線との交差部分を示している。
【００６７】
Ａ領域として表される三角形Ａの陰になって見えない領域が構築された後、三角形Ｂ上の陰になって見えないポイントの位置を迅速に探し出す方法は、三角形の共有されていない頂点のそれぞれを三角形Ａに対してテストすることである。陰になって見えないポイントが見つからず、二つの三角形が一つの辺を共有する場合、「ＢはＡの影になって見えない部分がある状態ではない」。そうでなければ、Ｂ領域が構築され、Ａ上の共有されていない頂点から陰になって見えないポイントを検索する。それでも陰になって見えないポイントが見つからず、二つの三角形が一つの頂点を共有する場合もまた、「ＢはＡの影になって見えない部分がある状態ではない」という結論が得られる。二つの三角形だけであり、どちらの三角形のどの頂点も陰になって見えないポイントとなる条件を満たさない場合、我々はＢ領域の錐形の境界とＡとを交差させて、陰になって見えないポイントを演算する。演算された交差ポイントは錐形の境界上に位置し、陰になって見えないポイントとなる条件を満たす。図９に示されるケースに関しては、四つの交差ポイントがある。交差部分ポイントが見つからない場合、三角形Ｂは三角形Ａの陰になって見えない部分がある状態ではない。陰になって見えない部分があるかどうかの高次なテストのアルゴリズムの疑似コードの例を以下に示す。
【００６８】
PROC occlusion-test (triA, triB)
{
regionA = construct-region(triA);
occlusionPt = find-occlusionPt(triB, regionA); if (occlusionPt is found) {
return halfPlaneTest(occlusionPt, triA);
}
else if (triA shares an edge with triB) {
return “triA does not occlude triB”; }
else {
regionB = construct-region(triB);
occlusionPt = find-occlusionPt(triA, regionB);
if (occlusionPt is found) {
return halfPlaneTest(occlusionPt, triB);
}
else if (triA shares a vertex with triB) {
return “triA does not occlude triB”; }
else{
occlusionPt = intersect(triA, regionB);
if (occlusionPt is found) {
return halfPlaneTest(occlusionPt, triB);
}
else{
return “triA does not occlude triB”;
}
}
}
}
【００６９】
【００７０】
開示された視野をキャッシュに格納するアルゴリズム用疑似コードの例を以下に示す。この実施例において選択された参考方向は、単位球面上に均等に分散している。その時の視野方向に関して、最も近い参考方向が識別される。この参考方向からはキャッシュに格納された三角形リストが入手できない場合、三角形をソーティングするオペレーションが実行され、作成された三角形の配列が参考方向に対してキャッシュに格納される。これ以外の場合には、キャッシュに格納されたリストがレンダリングのために直接呼び出される。
【００７１】
PROC view-caching (inNode, inViewDir, outSortedList)
{
if(refDirList is empty)
refDirList = constructReferenceDirList();
closestRefDir = findClosestRef(inViewDir, refDirList); if(cachedTriList is available for closestRefDir){
outSortedList = cachedTriList;
}
else{
triangle-sort(inNode, inViewDir, outSortedList);
cacheList(closestRefDir, outSortedList);
}
return;
}
【００７２】
視野をキャッシュに格納することで、三角形ソーティングの実行が必要となる頻度が減ることにより、レンダリングのスピードが改善される。幾何学データの代わりにグラフィックスデータをキャッシュに格納することで更なる最適化が実現できる。例えば、三角形リストの代わりにディスプレイリストを参考方向においてキャッシュに格納することもできる。この方法によれば、必要なレンダリングのオペレーションも減らすことができる。
【００７３】
図１０は、上述のプロセスの詳細な説明に対応した、好ましい実施例によるプロセスのフローチャートを図示している。先ず、システムは透過的ノードとその時の視野方向を説明する幾何学データを受け取る（ステップ１００５）。
【００７４】
次に、システムはバイナリスペースパーティションツリーを構築する。ここで、透過的三角形のそれぞれがＢＳＰツリーのリーフと関連づけられる（ステップ１０１０）。
【００７５】
次に、ＢＳＰツリーを走査し各リーフにおいて三角形をソートすることで、実質的に奥から手前の順になるよう三角形をソートする（ステップ１０１５）。
【００７６】
次に、ソートされた三角形をグラフィックスＡＰＩに出力する(ステップ１０２０)。
【００７７】
最後に、その時の視野に対してソートされたデータを、三角形の形でもしくは表示リストの形でキャッシュに格納する（ステップ１０２５）。
【００７８】
図１１は好ましい実施例によるもう一つのプロセスのフローチャートを図示している。このプロセスは、上述のＢＳＰツリーの構築を説明する。第一に事前処理の段階で、システムはそれぞれの三角形の法線情報及び位置情報を含め、それぞれの三角形の形状知識を分析する（ステップ１１０５）。次に、システムはルートノード及びノードリストを作成する(ステップ１１１０)。
【００７９】
その後、ツリーの各ノードに関して、システムは本願記載の区分面選択（ステップ１１１５）を実行する。その後、ノードのそれぞれの三角形は区分面に関して分類され（ステップ１１２０）、この分類に基づき、子ノードが作成される(ステップ１１２５)。
【００８０】
残りのノードがある場合（ステップ１１３０）、このプロセスを繰り返す（ステップ１１１５に戻る）。残りのノードがなければ、ここでプロセスは終了し（ステップ１１３５）、全体プロセスでの次のステップが実行できる。
【００８１】
グラフィックス処理及びレンダリングに関する更なる背景情報は、下記の文献に記載されており、これらの文献は全て参照することにより本願に含まれるものである。アブラハム・マーメン著、「バーチャルピクセルマップ技術とともに使用される透過的性及びアンチエイリアスアルゴリズム」、ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ＆ Ａｐｐｌｉｃａｔｉｏｎｓ、９（４）、１９８９年７月、４３−５５；キャス・エベリット著、「インタラクティブなオーダー非依存型透過的性」、白書、エヌビディア、２００１年；マイケル・ケリー、カーク・ゴールド、ブレント・ピース、ステファニー・ウィナー、アレックス・イェン著、「ハードウェアで加速されたＣＳＧレンダリング及び透過的性」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２１ｓｔ ａｎｎｕａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｃｏｍｐｕｔｅｒ ｇｒａｐｈｉｃｓ ａｎｄ ｉｎｔｅｒａｃｔｉｖｅ ｔｅｃｈｎｉｑｕｅｓ、１９９４年、１７７−１８４；ニューウェル、Ｍ・Ｅ、ニューウェル、Ｒ・Ｇ、及びサンチャ、Ｔ・Ｌ著、「隠れたサーフェス問題へのソリューション」、Ｐｒｏｃ． ＡＣＭ Ｎａｔｉｏｎａｌ Ｃｏｎｆ．、１９７２年；ヘンリー・ファッチ、ズビ・Ｍ・ケデム、ブルース・Ｆ・ネイラー著、「アプリオリなツリー構造による目に見えるサーフェスの生成について」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ７ｔｈ ａｎｎｕａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｃｏｍｐｕｔｅｒ ｇｒａｐｈｉｃｓ ａｎｄ ｉｎｔｅｒｎａｃｔｉｖｅ ｔｅｃｈｎｉｑｕｅｓ、１９８０年７月、１２４−１３３；ヘンリー・ファッチ、グレゴリー・Ｄ・アブラム、エリック・Ｄ・グラント著、「リジットオブジェクトのほぼリアルタイムでの陰影ディスプレイ」、Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ、Ｖｏｌ．１、Ｎｏ．３、１９８３年７月．［７］マイケル・ディアリング著、「形状圧縮」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２２ｎｄ ａｎｎｕａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｃｏｍｐｕｔｅｒ ｇｒａｐｈｉｃｓ ａｎｄ ｉｎｔｅｒａｃｔｉｖｅ ｔｅｃｈｎｉｑｕｅｓ、１９９５年９月．［８］フォレイ、Ｊ・Ｄ、バン・ダム、Ａ、フェイナー、Ｓ・Ｋ、ヒューズ、Ｊ・Ｆ著、「コンピュータグラフィックス：原理と実践」、第２刊、アディソン―ウェスリー、１９９７年。
【００８２】
説明を簡潔かつ明確にするために、本発明と共に使用するに適した全てのデータ処理システムに関し、その完全な構成とオペレーションが本願に図示もしくは記載されているわけではないことを当業者は認識するであろう。そうではなく、本発明に特有なデータ処理システム、もしくは本発明を理解するのに必要なデータ処理システムのみが図示及び記載されている。データ処理システムの構成とオペレーションで本願に記載されていないものは、当技術分野で公知の様々な現行の実施方法及び使用例に沿ったもので良い。
【００８３】
本発明は完全に機能的なシステムとして記載されているが、本発明のメカニズムの少なくとも一部は、機械で使用可能な様々な形態の媒体に収められた指示として頒布させることができることを当業者は理解するであろうことと、また本発明が、実際の頒布のために使用される指示もしくはシグナルを含む媒体の特定の種類に関わらず、同じ様に応用できることは、特記すべき事項である。機械で使用可能な媒体の例としては読み取り専用メモリ（ＲＯＭ）もしくは電気的消去、プログラム可能型読み取り専用メモリ（ＥＥＰＲＯＭ）などの不揮発性のハードコードされた媒体、フロッピーディスク、ハードディスクドライブ、及びコンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、もしくはデジタル多用途ディスク（ＤＶＤ）などのユーザーが記録できる媒体、及び、デジタルコミュニケーションリンク及びアナログコミュニケーションリンクなどの伝達型媒体が含まれる。
【００８４】
本発明の実施例はその詳細が記載されているが、本願が開示する発明は、その最も広範な精神及び範囲から逸脱することなく、様々な形で変更、置き換え、変形、及び改良できるということを当業者は理解するであろう。
【００８５】
本出願内の記載は如何なるものであれ、特定の構成要素、ステップ、もしくは機能が、特許請求の範囲に含まれなければならない不可欠な構成要素であると示唆するものではない。つまり、特許に含まれる内容の範囲は、請求項の範囲によってのみ定義されるものである。また、これらの請求項はどれも、「（ため）の手段」という言葉が分詞の後に続かない限り、合衆国法典第３５編第１２条の第６段落の発動を意図するものではない。
【００８６】
本発明及び本発明による効果をより完全に理解するために、付随する図面と併せながら下記に説明をする。なお、図内の同じ数字は同じものを示す。
【図面の簡単な説明】
【００８７】
【図１】様々な実施例を実現できるデータ処理システムのブロック図である。
【図２】本発明の一実施例による概略図である。
【図３】ＢＳＰ木構造アルゴリズムの概要を示している。
【図４】Ａ及びＢはそれぞれ、釣合いのとれたツリー（ｂａｌａｎｃｅｄ ｔｒｅｅ）と不釣合いなツリー（ｕｎｂａｌａｎｃｅｄ ｔｒｅｅ）を図示している。
【図５】３２ビットの整数としての面インデックスのレイアウトの一例である。
【図６】抽出した階層グループの一例を図示している。
【図７】陰になって見えない部分が連鎖している関係を示している。
【図８】Ａ乃至Ｃは、三角形の陰になって見えない部分がある領域の三つの異なる形を示している。
【図９】三角形と領域の境界線との交差部分を示している。
【図１０】好ましい実施例によるプロセスのフローチャートである。
【図１１】好ましい実施例による別のプロセスのフローチャートである。
【技術分野】
【０００１】
本発明は、一般にグラフィックス処理（ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ）に関するものである。
【発明の背景】
【０００２】
航空宇宙産業、自動車産業など数多くの産業において、製造業者は初期段階でデザインの問題を発見すべくインタラクティブに（ｉｎｔｅｒａｃｔｉｖｅｌｙ）製品のデザインを見て点検するために可視化技術に依存することが増えてきている。製品構造全体を見てそのサブシステムのそれぞれを点検し易くする能力は、如何なる可視化システム（ｖｉｓｕａｌｉｚａｔｉｏｎ ｓｙｓｔｅｍ）においても不可欠とされている。したがって、本来なら陰になって見えない（ｏｃｃｌｕｓｉｏｎ）デザインの詳細が見えるようにするため、一部の選択した部品を透過的にレンダリングする（ｒｅｎｄｅｒ ｔｒａｎｓｐａｒｅｎｔｌｙ）ことが望ましい。また、ガラスなど透過的な素材からできている部品もあり、それらを透過的にレンダリングすることはそのシーンをよりリアルに見せる。したがって、インタラクティブなフレームレート（ｉｎｔｅｒａｃｔｉｖｅ ｆｒａｍｅ ｒａｔｅ）でオブジェクト（ｏｂｊｅｃｔ）にリアルな透過性（ｔｒａｎｓｐａｒｅｎｃｙ）を持たせることは効果的な可視化（ｖｉｓｕａｌｉｚａｔｉｏｎ）のために重要なのである。
【０００３】
新しいグラフィックシステムの殆どにおいては、「アルファブレンディング」（ａｌｐｈａ ｂｌｅｎｄｉｎｇ）と呼ばれるプロセスにより透過的レンダリングが実現されている。透過性を正確にするには、一画素に寄与する全ての多角形の色を奥から手前の順に「ブレンド」しなければならない。フレームごとに正確にソーティングを行なう必要があるため、大きなモデルのインタラクティブな透過的レンダリングは困難な課題であった。
【０００４】
従来提案されてきた三角形ソーティングの方法（ｔｒｉａｎｇｌｅ ｓｏｒｔ ｍｅｔｈｏｄ）は、画像に基づいたものとオブジェクトに基づいたものの二種類に分類することができる。画像スペースに基づいた方法では、特殊なグラフィックハードウェアを利用する必要がある。この種の方法では、深さに沿って奥から手前の順に一層ずつ透過的な多角形をレンダリングする。各層のレンダリングには個別のレンダリングのパスが必要となり、そのシーンの最大深さの数だけレンダリングのパスが必要である。異なるパスからの各画素の色をブレンドするために追加のメモリバッファが必要となる。オブジェクトスペースに基づいたの方法では、その時の視野方向に対して全ての多角形をソートする。これらのソートされた多角形はその後、レンダリングのために奥から手前の順にグラフィックスのパイプラインに供給される。この種類の方法の殆どは、Ｚ−バッファというハードウェアが利用できるようになる以前に可視性の問題を解決するために提案されたものである。これらの各方法には深刻な限界があり、大きな透過的モデルのレンダリングに効果的に利用することはできなかった。例えば、深さソーティング法にはＯ（Ｎ２）の計算の複雑さがあり、ＢＳＰ（バイナリスペースパーティション）ソーティング法（ｂｉｎａｒｙ ｓｐａｃｅ ｐａｒｔｉｔｉｏｎ ｓｏｒｔ ｍｅｔｈｏｄ）には大きな木構造（ｔｒｅｅ ｓｔｒｕｃｔｕｒｅ）を構築しメモリに保存する手間がかかる。大きな透過的のモデルのレンダリングをインタラクティブなレートで行なうことを可能にするための新たなアプローチが望まれている。
【０００５】
ＢＳＰツリーの構築（ｔｒｅｅ ｃｏｎｓｔｒｕｃｔｉｏｎ）に関するこれまでの研究は、一つのファクター、すなわち最終的なＢＳＰツリー（ｔｒｅｅ）における三角形の数を最小限にすることに焦点をあてており、実用面では等しく重要であるその他のファクターは考慮されていなかった。これらその他のファクターには、ＢＳＰツリーの構築にかかる時間、ＢＳＰツリー内の三角形をソートするのにかかると予想される時間などが含まれる。様々なファクターによって課された様々な条件を満たしつつ効率的にＢＳＰツリーを構築することは困難ではあるが、このアプローチをより実用的なものにするにはきわめて重要である。
【０００６】
深さソーティングに関するこれまでの研究は、一対の三角形の陰になって見えない部分がある関係を正確に割り出すことのできないようなテスト用アルゴリズムを用いていた。その結果として、二つの三角形が既に正しい順序に並んでいたとしても視野に依存した三角形スプリットが起こることがあった。そのような不必要な三角形スプリットを避け、より良いソーティング結果を得るために、陰になって見えない部分があることをテストするための、より洗練されたアルゴリズムが必要とされている。
【０００７】
したがって本技術分野では、より良い透過的レンダリングのためのシステム、方法及びコンピュータプログラム製品が求められている。
【発明の概要】
【０００８】
好ましい実施例では、可視化ＡＰＩから来る未処理の多角形幾何学形状及び視野パラメータを受け入れ、奥から手前の順に多角形をソートし、その後ソートした三角形をＯｐｅｎＧＬなどのグラフィックスＡＰＩに供給するシステム、方法及びコンピュータプログラム製品を提供する。
【０００９】
上記は、後述する本発明の詳細な説明を当業者がより良く理解できるよう、本発明の特徴及び技術的な効果についてかなり広範に概要を述べたものである。本発明の更なる特徴と効果は本発明の請求項の主題となるものあり、以下において説明する。当業者は、開示されている概念及び特定の実施例を、本発明と同じ目的を果たすために他の構成を変更もしくはデザインするための基礎として容易に使用できることを理解するであろう。当業者はまた、これらの同等な構築は最も広義な形での本発明の精神及び範囲から逸脱するものではないことを認識するであろう。
【００１０】
下記の発明の詳細な説明に進む前に、本特許全体に亘って用いる特定の単語及び語句を定義することは有意義であろう。「含む」及び「から成る」という用語並びにそれらの派生語は、制限のない包含を意味する。「または」と言う用語は包括的で、その意味するところは及び／またはということである。「に関連する」及び「と関連する」という語句並びにそれらの派生語は、含む、含まれる、相互に関連する、包含する、包含される、〜を含む、〜内に含まれる、相互に接続する、〜を包含する、〜に包含される、〜に接続するもしくは〜と接続する、〜と連結するもしくは〜に連結する、〜と伝達できる、〜と提携する、インターリーブする、並列する、〜に隣接する、〜に境を接するもしくは〜と境を接する、〜を有する、〜の性質を有する、等を意味する。「コントローラ」という用語は、少なくとも１つの操作を制御するデバイス、システム、またはそれらの部品の全てを意味し、そのようなデバイスが、ハードウェア、ファームウェア、ソフトウエアまたは少なくとも２つの同様なものを組み合わせたものに実装されているかを問わない。特定のコントローラーに関連する機能性は集中型でも分散型でもよく、ローカルかまたは遠隔かは問わないことに留意されたい。本特許では特定の単語および語句の定義を提供するが、当業者は、そのような定義は、殆どではないにしても多くの場合、そのように定義された単語および語句の従来の使用および今後の使用に当てはまることが理解できるであろう。
【発明を実施するための最良の形態】
【００１１】
以下に考察する図１乃至図１１及び本特許に記載の本発明の原理を説明するのに用いた様々な実施例は例を示すためだけのものであり、如何なる場合でも本発明の範囲はこれらのみに限定して解釈されるべきではない。当業者は、本発明の原理は適宜に準備されたものであればどのようなデバイスを用いても実施できることを理解するであろう。本出願の多数の革新的な教示を、現時点で好ましいとする実施例を特に参照しながら説明する。
【００１２】
好ましい実施例では、可視化ＡＰＩから来る未処理の多角形幾何学形状及び視野パラメータを受け入れ、奥から手前の順に多角形をソートし、そしてソートした三角形をＯｐｅｎＧＬなどのグラフィックスＡＰＩに供給するシステム、方法及びコンピュータプログラム製品を提供する。
【００１３】
本願ではでは特に三角形について説明しているが、当業者は、開示した実施例は全ての平面形状、例えば凸面または凹面の多角形であってもよく、単純でも複雑でもよいと認識するであろう。また区分面（ｐａｒｔｉｔｉｏｎ ｐｌａｎｅ）で切ったときに二つ以上の形状にスプリットする方法がある限り、曲線状のまたはプロシージャで定義された形状（ｐｒｏｃｅｄｕｒａｌｌｙ−ｄｅｆｉｎｅｄ ｓｈａｐｅ）でもよい。
【００１４】
図１は好ましい実施例を実現できるデータ処理システムのブロック図である。図示したデータ処理システムは、プロセッサ１０２、２次キャッシュ／ブリッジ１０４及びローカルシステムバス１０６を含み、プロセッサ１０２は２次キャッシュ／ブリッジ１０４に、そして２次キャッシュ／ブリッジ１０４はローカルシステムバス１０６に接続されている。ローカルシステムバス１０６は、例えば、周辺構成要素相互接続（ＰＣＩ）アーキテクチャバスでもよい。図示した例ではローカルシステムバスにはまたメインメモリ１０８及びグラフィックスアダプタ１１０も接続されている。
【００１５】
ローカルエリアネットワーク（ＬＡＮ）／ワイドエリアネットワーク／ワイアレス(例えばＷｉＦｉ)アダプタ１１２などのその他の周辺構成要素もローカルシステムバス１０６に接続されるようにしてもよい。拡張バスインターフェース１１４によりローカルシステムバス１０６が入力／出力（Ｉ／Ｏ）バス１１６に接続される。Ｉ／Ｏバス１１６はキーボード／マウスアダプタ１１８、ディスクコントローラ１２０及びＩ／Ｏアダプタ１２２に接続されている。
【００１６】
図示した例のＩ／Ｏバス１１６にはまたオーディオアダプタ１２４も接続されており、オーディオアダプタ１２４には音声を再生するためのスピーカー(図示せず)を接続することもできる。キーボード／マウスアダプタ１１８はマウス、トラックボール、トラックポインターなどのポインティングデバイス(図示せず)を提供する。
【００１７】
当業者は、図１に示したハードウェアの詳細については様々であり得ると理解するであろう。例えば、図示したハードウェアに加えてまたはそれらの代わりに、光ディスクドライブ等のその他の周辺構成デバイスを用いることもできる。図示した例は説明のためだけのものであって、本発明に関する構造上の制限を示唆するものではない。
【００１８】
本発明の好ましい実施例によるデータ処理システムはグラフィカルなユーザーインターフェースを用いたオペレーティングシステムを含む。該オペレーティングシステムは該グラフィカルなユーザーインターフェースに複数のウィンドウを同時にレンダリングすることを可能にし、各レンダリングウィンドウは異なるアプリケーションとのまたは同じアプリケーションの異なるインスタンスとのインターフェースを提供する。ユーザーは該グラフィカルなユーザーインターフェースのカーソルを該ポインティングデバイスを介して操作できる。該カーソルの位置を変えること及び／またはマウスボタンをクリックするなどのイベントによって、望ましいレスポンスを得るように作動させる。
【００１９】
適宜に変更すれば、ワシントン州レドモンド市にあるマイクロソフト社の製品であるマイクロソフトウィンドウズＴＭの一バージョンなどの様々な市販のオペレーティングシステムの一つを用いることができる。説明したような本発明にしたがって該オペレーティングシステムを変更または作成してもよい。
【００２０】
好ましい実施例は透過的レンダリングが現在抱える問題に対処するものである。図２の概略アーキテクチャ図に示すように、開示したシステム、方法及びコンピュータプログラム製品は、可視化ＡＰＩとグラフィックスＡＰＩの間で機能する。
【００２１】
該システムは可視化ＡＰＩから来る未処理の多角形幾何学形状及び視野パラメータを受け入れ、好ましくは実質的に奥から手前の順に多角形をソートし、そしてソートした三角形をＯｐｅｎＧＬなどのグラフィックスＡＰＩに供給する。そうする際に、開示されたシステムは二つの従来型のソーティング方法を新規のやり方で統合して両方の利点を十分に引き出し、新規のキャッシュに格納するストラテジーを可能にすると共に、主要なアルゴリズムも大きく改良できるようにする。そして、処理時間、レンダリングの速度、レンダリングの質及びメモリ消費など様々なファクターに関する利点・不利点のトレードオフを実現できる顕著な柔軟性を提供することにより、システムを実用面で改善する。開示したシステムは、最大で数十万もの多角形までの大きなモデルを市販のグラフィックス用ハードウェアを用いてインタラクティブなフレームレートで、殆ど不自然な結果も無くレンダリングできることが証明されている。
【００２２】
ＢＳＰソーティング法の特徴は深さソーティング法の特徴を補完するものである。ＢＳＰソーティング法は、非常に大きなツリー構造をメモリに維持することによりＯ（Ｎ）次のコンプレクシティを実現する。深さソーティング法はメモリのオーバーヘッドが少なくて済むが、Ｏ（Ｎ２）次のコンプレクシティを持ち、これはまったく望ましくない。本願で開示されている三角形ソーティング用アルゴリズムはこれら二つの方法を統合して両方の利点を引き出すものである。具体的には、（従来のやり方ではＢＳＰツリーは三角形が一つのリーフノードで構築されていたのに対し）少なくとも幾つかの実施例においては、ＢＳＰツリーは三角形が複数あるリーフノードで構築される。そして該ＢＳＰツリーを走査し、走査中に各リーフノード上の三角形を深さソーティングすることにより三角形がソートされる。
【００２３】
一つのリーフノード上で許容できる三角形の最大数βを指定することにより、開示されたアルゴリズムの挙動を、これら二つの方法の間で容易に調整でき、レンダリングの速度とメモリ消費の望ましいトレードオフが実現できる。例えば、βが１であると指定されると、開示されたアルゴリズムは従来のＢＳＰソーティング用アルゴリズムへと戻り、βが三角形の合計数であるＮと指定されると、開示されたアルゴリズムは従来の深さソーティング用アルゴリズムへと戻る。βが２とＮ−１の間の数値であると指定されると、我々のアルゴリズムの挙動もまたこれら二つの従来法の中間のものとなり、βが大きくなるにつれソーティング速度は落ちるがメモリ内のツリーサイズは小さくなる。また、好ましい実施例では深さソーティング用アルゴリズムには、二つの異なるモードがあり、深さソーティング用アルゴリズムがレンダリングの速度とレンダリングの質に関して、更なる柔軟性が提供される。高次なモードでは正確なレンダリングの結果が保証され、基本モードでは不自然な結果があるかもしれないがレンダリングの速度が速くなる。
【００２４】
ＢＳＰ構築アルゴリズムを改良するために、様々な技術を開示する。幾つかの実施例においては、実用的なアプリケーションに重要な複数のファクターを考慮した区分面の候補の質を評価するために新しい判断基準を用い、良い区分面の迅速な選択を促進する形状知識情報を効率的に抽出するために新しい方法を用いる。実験結果では、開発されたＢＳＰ構築アルゴリズムにより１．２ＧＨｚプロセッサのＰＣでおよそ１秒で２万個の三角形の高品質のＢＳＰツリーを作成できることが示された。
【００２５】
本願では、一対の三角形間での陰になって見えない部分がある関係を正確に識別するための洗練されていながら計算に関しては効率的なテスト用アルゴリズムにより、周知の深さソーティング用アルゴリズムが改良されている。その様にして不必要な三角形スプリットをなくすことができる。
【００２６】
更に、ある有限数の視野方向一組に対してソートされた幾何学形状をキャッシュに格納して、視野をキャッシングするアルゴリズムが開示されている。これらのキャッシュに格納されたされた三角形の配列を用いると、その時の視野方向の現実の三角形の配列をキャッシュに格納されたレファレンス方向の中で最も近いものの三角形の配列で近似することにより、透過的レンダリングの速度を上げることができる。
【００２７】
第一フレームの遅れを最小化するために、事前処理ステップとしてのＢＳＰツリーの構築は出来る限り効率的なものでなくてはならない。ＢＳＰツリーは一度構築されればその後の全てのフレームのレンダリングに使用されるため、出来る限り最適化されたものでなくてはならない。この分野での従来の研究は単一の判断基準、つまり最終的なＢＳＰツリーにおける三角形の数を最小限にすることに焦点を当てていた。
【００２８】
好ましい実施例においては、区分面評価のための新しい判断基準と、最良の区分面を効率的に選択するための新しい知識主導アルゴリズムとから成るＢＳＰツリー構築用アルゴリズムが使用されている。新しい判断基準は、各フレームの三角形をソーティングするための予測所要時間とＢＳＰツリーの構築時間との両方を短縮するための必要条件を満たすために作られたものである。
【００２９】
同一のリーフノードにおける三角形のソーティングに使用される深さソーティング用アルゴリズムは、陰になって見えない部分があるかどうかのテストを異なるレベルで用い、二つの異なるモードで作動できる。基本ソーティングモードでは、視野座標システムにおける三角形の最大Ｚ座標に基づいて三角形をソートする。高度なソーティングモードでは、陰になって見えない部分がある環状の関係がない場合、更に洗練された形で陰になって見えない部分があるかどうかをテストし、三角形をスプリットせずに正確な結果を保証する。
【００３０】
図２は、開示された透過性レンダリング用ソフトウェアシステムの実施例の概略を示す。システムへのインプット情報は、その時の視野方向と可視化ＡＰＩから供給される透過的ノードである。出力情報は、レンダリングのためにグラフィックスのパイプラインに供給される奥から手前の順にソートされた三角形である。透過的ノードはレンダリングされる全ての透過的三角形を含むデータ構造で、シーンのグラフ中の単一もしくは複数の部分に対応していることもある。ＢＳＰツリーはそれが存在していない時点で、第一フレームの始めに先ず入力幾何学形状から形成される。ＢＳＰツリーは一度形成されると透過的ノードにおいてキャッシュに格納され、その後のフレームに用いられる。この時点でＢＳＰツリーの中に組み込まれた透過的三角形は、次に三角形ソーティング用モジュールによりその時の視野方向に対してソートされる。法線情報及び色情報も含め、ソートされた三角形は（ＯｐｅｎＧＬなどの）グラフィックスＡＰＩにレンダリングのために供給される。視野キャッシング用モジュールはオプションであり、これが作動可能とされている場合、ソートされた三角形は視野方向とともに透過的ノードのキャッシュに格納される。その後、近接した視野方向のレンダリングが要求された場合、三角形のソーティングは必要なく、このキャッシュに格納された三角形のデータをレンダリングのために直接呼び出すことができる。
【００３１】
バイナリスペースパーティション（ＢＳＰ）ツリー：繰り返し実行され、多数の入力オブジェクトを扱うプロセスに関してその効率改善のために重要な方法は、それらのオブジェクトの間に一貫した構造を構築しそれを維持することである。例えば、幾何学問題で頻繁に使用されるストラテジーでは、大規模問題を簡単で効率的に扱うことができる複数の小規模問題に分断する「分断攻略」アプローチの再帰的使用がある。ＢＳＰツリーはこの種の構造の一つであり、各ノードは三次元空間領域に置かれた一組のエレメントを表す。全てのエレメントを含むルートノードからスタートし、ユークリッド空間を重複しない二つの領域に分断するために区分面が使用される。区分面により切り分けられたエレメントは二つ以上のエレメントにスプリットする。各領域のエレメントに子ノードが作られ、これがＢＳＰツリーの新しいリーフノードとなる。各リーフノードのこの区分は、事前に設定された条件が満たされるまで再帰的に継続して行われる。
【００３２】
各ＢＳＰノードの二つの子ノード（ｃｈｉｌｄ）は線形の区分面で隔てられているため、視野ポイントから離れた子ノードの陰になって他の子ノードに見えない部分がある状態になることはない。従って、ＢＳＰ木構造（ｔｒｅｅ ｓｔｒｕｃｔｕｒｅ）は三角形をソーティングするために特に有用である。ＢＳＰツリー内に形成された潜在的な可視性の順序を利用することにより、その全てのノードの可視性ソーティング（ｖｉｓｉｂｉｌｉｔｙ ｓｏｒｔｉｎｇ）が単にツリーを走査することで達成できる。ＢＳＰツリーはシーンの幾何学形状を特徴づけ、視野方向には拠らないため、シーンの内容に変化がない限り異なる視野方向の正しい可視性の順序を入手するために同一のＢＳＰツリーを使用できる。このことは、静的な幾何学形状の可視化アプリケーションで特に有用である。
【００３３】
好ましい実施例のＢＳＰ構築アルゴリズム（ＢＳＰ ｃｏｎｓｔｒｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ）は、余計なツリー構築時間（ｔｒｅｅ ｃｏｎｓｔｒｕｃｔｉｏｎ ｔｉｍｅ）を掛けずに三角形のソーティングを可能にするＢＳＰツリーを作成する。ＢＳＰツリーの構築に影響を及ぼす唯一の重要変数は、スプリットされる各リーフノードにおける区分面の選択である。従って、区分面の候補の評価にどのような判断基準を用いるべきか、また最良の区分面を如何にして効率的に選択するかということが重要課題となる。本願においては、ツリーの構築時間や最終的なツリーの質など複数のファクターを考慮した判断基準を選択することで第一の課題に対応し、最良の候補を迅速に識別するために抽出された形状知識を利用することで第二の課題に対応している。下記の説明は特に三角形エレメントに関連しているが、開示されたプロセスは明らかに一般的な平面多角形に応用可能なものであると当業者は認識するであろう。
【００３４】
図３は開発されたＢＳＰツリーの構築アルゴリズムの概略を示す。このアルゴリズムは三つのステップから成る：事前処理、区分面の選択、ノードの構築である。事前処理ステップは一度しか呼び出されないが、その後の二つのステップはスプリットされる各ＢＳＰノードに対して繰り返し呼び出される。三角形の法線情報及び位置情報を分析することで、区分面の候補をより効率的に選択するために使用される形状知識が事前処理ステップで抽出される。このステップにおいてはまた、全ての入力三角形を含むルートノードが作成され、これを保持するＢＳＰノードリストが初期化される。ノードリストは、スプリットされる全てのリーフノードを保持した待ち行列タイプ構造のもので、このリストが空になった場合再帰的な構築プロセスは終了する。区分面選択のメカニズムは仮説と検証の方法に基づいており、つまり最高の結果を出し得る面を決定するために幾つかの候補面が選択され評価される。ノード構築ステップにおいては、各三角形は選択された区分面に関して分類され、区分面を横切るかどうかに基づいてスプリットされる。その後、その時のＢＳＰノードに対し単一もしくは複数の子ノードが作成される。事前に設定された判断基準に基づき更なる再分断が必要な場合には、新しく作成された子ノードの各々がノードリストに付け加えられる。
【００３５】
ＢＳＰ構築アルゴリズムの課題の一つは、一組の三角形を含む所定のＢＳＰノードに対する異なる区分面を比較するために、どの判断基準を用いるべきかということである。好ましい実施例においては、ツリー構築時間及び構築されるＢＳＰツリーの質に関する様々な目標を反映した、ｗとして表される判断基準で区分面は評価される。最短のツリー構築時間とより良いＢＳＰツリーを達成する可能性が、ｗの最大値を有する区分面において最も高くなるようにこの判断基準はデザインされている。
【００３６】
表１は区分面Ｐの候補を特徴づけるために使用されるパラメータを示す。
【００３７】
【表１】
【００３８】
一組の三角形と区切り面Ｐの候補を含むリーフノードＬがある場合、表１に示される四つのパラメータがＰの質を特徴づけるために用いられる。パラメータnCに関しては、三角形が複数の三角形にスプリットされ、そのそれぞれが区分面Ｐの正の側か負の側に位置するようになるので、パラメータnCは判断基準ｗに悪い影響を及ぼすことは明らかである。三角形をスプリットすることは、一般的に結果としてツリーサイズがより大きくなりツリー構築時間が長くなる。また、ＢＳＰツリーにおける三角形の数が増加すると、三角形のソーティングも時間がかかる。Ｐ上にある三角形は同一平面上にあり、またノードＬのフロント子ノード及びバック子ノードに対するこれら三角形全体の順序は容易に入手できるため、Ｐにおける三角形の順序は任意のものとすることができる。これら三角形のソーティングのコストはゼロであるため、パラメータnOは明らかに、判断基準ｗに対して良い影響を与える。
【００３９】
ｎF及びnBの判断基準ｗへの影響はそれ程明らかなものではない。ツリーバランス、つまりnF及びnB間の差の絶対値は、ＢＳＰツリーにおける全ての三角形をソートするという目的においては重要ではない。しかし、ツリーのバランスが崩れた場合構築パイプラインを通る三角形の数が増加するため、ツリーバランスはツリー構築時間に甚大な影響を与えるということが明らかになっている。図４Ａ及び図４Ｂに示される二つの極端なケースを分析しこれらを比較することで、このことは浮き彫りになる。図４Ａは非常に良くバランスの取れたツリー区分を示し、図４Ｂは極端にバランスの崩れたツリー区分を示している。
【００４０】
【００４１】
上記の分析に基づいて、好ましい実施例では区分面の評価に下記の判断基準が用いられる。
ｗ＝ｎＯ−ＫＣｎＣ−ａｂｓ（ｎＦ−ｎＢ）（１）
ここで、ＫＣは三角形をスプリットすることの重要性を示す定数であり、ａｂｓという記号は絶対値オペレーションを意味する。三角形をスプリットすることで、その時のノードをスプリットするオペレーションが遅くなるのみならず、扱う三角形の数が増えるため、最終的なツリーサイズが大きくなりツリー構築が更に遅くなるという事実を示すために、ＫＣの値は一般的に１より大きく設定される。
【００４２】
ＢＳＰツリー構築パイプラインから、正しい区分面の選択が構築時間及び最終的なＢＳＰツリーサイズの両方に影響する課題であることが分かる。方程式（１）が示す評価判断基準は、区分面上の三角形が多くなり、区分面が切り分ける三角形の数が少なくなり、区分面のそれぞれの側の三角形のバランスができるだけ取れるように区分面を選択するべきである、ということを示している。好ましい実施例においては、入力三角形は事前処理ステップで、それぞれが特定の特徴もしくは位置づけパターンの情報を伝達する一貫した階層グループに編成される。このように編成された三角形はその後、質の高い区分面の候補の迅速な識別のために用いられる。
【００４３】
図５は、３２ビットの整数としての面インデックスのレイアウトの一例を示す。図６は、抽出した階層グループ（ｈｉｅｒａｒｃｈｉｃａｌ ｇｒｏｕｐ）の一例を示す。
【００４４】
【００４５】
好ましい実施例においては、各三角形の補助面の法線ベクトルとスカラー距離は、我々が面インデックスと呼ぶ単一の正負符号付整数にエンコードされる。面インデックスは、八進インデックス及び六進インデックスのそれぞれを正確にエンコードする３ビットと、二つの角度値のそれぞれを量子化しエンコードするｎビットと、距離値を量子化しエンコードする２５−２＊ｎビットから成る。ここで、ｎは調整可能である。ｎ＝３である場合の面インデックスのレイアウトを図５に示す。ここで、最上位ビットが正負ビットとして確保され、次の６ビットが八進値及び六進値用であり、次の１９ビットが量子化された距離値用であり、最後の６ビットが二つの量子化された角度値用である。
【００４６】
領域、層及び面と呼ばれる三つのグループが抽出され、この３グループの間の階層関係（ｈｉｅｒａｒｃｈｉｃａｌ ｒｅｌａｔｉｏｎ）は図６に図示されている。抽出プロセスは全ての三角形をその面インデックスに対して（降順に、一般性は失わずに）シードリストＳにソートすることから始まる。領域グループは、そのそれぞれがＳ中の同一の八進値及び六進値を有する三角形の隣接リストを含んでおり、その後リストＳから抽出される。八進値及び六進値の定義から、最大で４８個の領域が存在し、同一の領域内の全ての三角形はほぼ同じ方向を向いている。図５から分かるように、各領域内で三角形はその距離によりソートされる。層から同一の距離にある三角形と、同一の領域内にある層はそれらの距離により降順にソートされる。各層内で、同一の量子化された角度値を有し、それ故にほぼ同じ方向を向いている三角形は一つの面へとグループ化される。各面は一つもしくは複数の三角形エレメントから成る。
【００４７】
区分面選択における基本ストラテジーは、選択された一組の面候補を比較し最高質の面を選ぶ「仮説と検証」である。好ましい実施例では、方程式（１）による評価で優れた区分面になる可能性が最も高い区分面の候補を迅速に選択するために、抽出された形状知識が利用される。
【００４８】
殆どのＣＡＤモデルには重要性のある平面の特徴があるため、区分面上の三角形は、モデル内で最も大きな重要性のある面の特徴をあるものを選択した場合、最大多数となる。透過的なオブジェクト内の全ての面の特徴は面グループとして抽出されているため、最も大きな重要性のある面の特徴から成る三角形リストは、単に線形検索で識別できる。その後、リスト内の一つの三角形の補助面が区分面の候補として選択される（この例においては第一の三角形が選択される）。面の特徴の重要性は面グループの面積として、つまりはグループ内の三角形の全面積として定義される。これは、三角形が区分面によって切り分けられる可能性はその面積の増加と共に上昇するからで、それ故、面積が大きい三角形を区分面上に持つ方が良い。
【００４９】
【００５０】
区分面の六つの候補のそれぞれに関して、三角形との関係が演算される。区分面と単一の三角形との関係は四つのタイプ、三角形の上、三角形を横切る、三角形の前および後ろ、の内の一つとして分類されるが、区分面と一組の三角形との関係は、表１に示すようにｎＯ、ｎＣ、ｎＦ及びｎＢの四つのパラメータで特徴づけられる。単一の三角形と面との関係のタイプは、三角形の三つの頂点とその面との関係から容易に推測でき、この関係は半平面テストによって容易に演算できる。
【００５１】
選択された六つの候補面のそれぞれは、入力三角形の補助面である。このことは、少なくとも一つの三角形は切り分けられず、三角形によって形成された形状が凸状に近くない場合に良い結果を出す筈である、という意味で有益である。しかし、この形状がほぼ凸状である場合、選択された区分面は極端にバランスが悪くなる可能性が高く、これは避けるべきである。
【００５２】
【００５３】
【００５４】
その時のＢＳＰノードに対し最良な区分面が選択された後、手前の子ノード、または奥の子ノードもしくはその両方が、必要とされる親子リンクを有するように作られる。区分面の正の側にある三角形は全て手前の子ノード上に置かれるが、負の側にある三角形は全て奥の子ノード上に置かれる。区分面上にある三角形はその時のノード上に留まり、区分面を横切る三角形は二つもしくは三つの三角形にスプリットされる。スプリットされた三角形のそれぞれが、手前の子ノードか奥の子ノードのどちらかに追加される。
【００５５】
同じ子ノード上の三角形の順序が変化しないように、その時のノード上の三角形が順序通りに処理されるような形でノード構築は行われる。例えば、その時のノードにおいて三角形Ａが三角形Ｂに先行し、ノード構築後これらの三角形が同じ子ノードに属する場合、その後も三角形Ａ（もしくはそのスプリットされた三角形）は三角形Ｂ（もしくはそのスプリットされた三角形）に先行する。従って子ノードの三角形リストは、更なるソーティングを行わずとも階層グループの抽出が可能な状態にある。
【００５６】
ＢＳＰツリーに編成された三角形の可視性の順序は、走査時の各リーフノードにおける目の位置と深さソーティング手順に対し、ＢＳＰツリーを奥から手前の順に走査することで演算される。ツリーを走査することでＢＳＰツリーの全てのノードがソートされるが、深さソーティング手順により単一のリーフノード内の三角形に関して、奥から手前への順番が設定される。三角形ソーティング用アルゴリズムの疑似コードの例を以下に示す。ここで、「ｉｎＮｏｄｅ」はソートされるその時の入力ＢＳＰツリーノードであり、「ｉｎＥｙｅ」は目の位置の入力位置であり、「ｏｕｔＴｒｉＬｉｓｔ」は演算されるソートされた三角形の出力リストである。非リーフノード上の三角形に関しては、深さソーティングは必要ないためリーフノード上の三角形に比べソーティングコストはかなり低い。表１に示される数値ｎＣが方程式（１）の評価式に良い影響を与えるのはこのためである。
【００５７】
PROC triangle-sort (inNode, inEye, outTriList)
{
if(inNode is leaf node){
tempList = depth-sort(inNode, inEye);
outTriList.add(tempList);
}
else if(inEye is in the front of inNode.partitionPlane){
triangle-sort(inNode.back, inEye, outTriList);
outTriList.add(inNode.onTriList);
triangle-sort(inNode.front, inEye, outTriList);
}
else if(inEye is at the back of inNode.partitionPlane){
triangle-sort(inNode.front, inEye, outTriList);
outTriList.add(inNode.onTriList);
triangle-sort(inNode.back, inEye, outTriList);
}
else{ // eye is on node.partitionPlane
triangle-sort(inNode.front, inEye, outTriList);
triangle-sort(inNode.back, inEye, outTriList);
}
}
【００５８】
開示された深さソーティング用アルゴリズムは、異なる二つのモードで作動する。基本モードではそれぞれの三角形はポイントとして単純化され、一対の三角形の陰になって見えない部分がある関係は、それらの三角形から目の位置までの距離を比較することで演算できる。このように単純化することで、予想時間Ｏ（ＮｌｏｇＮ）でのＱｕｉｃｋＳｏｒｔなどの効率的な実行が可能となるが、このテストは完全でなく、正確な結果は保証されていない。従って、ソートされた順序が誤りである可能性もあり、これは透過的レンダリングにおいて不自然な結果に繋がる。
【００５９】
高次なモードで作動している場合、次項で説明する陰になって見えない部分があるかどうかをテストする高次なアルゴリズムによって演算された一対の三角形の陰になって見えない部分がある実際の関係に基づいて、深さソーティング用アルゴリズムが最終的なソートリストを作成する。保証された正確な結果を導き出しつつ、陰になって見えない部分がある実際の関係に基づいてソートリストを作成することは、基本Ｚソーティングよりも複雑である。三角形Ａと三角形Ｂの陰になって見えない部分があるかどうかをこれらの三角形だけでテストしても、最終的な奥から手前にソートされたリストにおけるこれら三角形の順序が完全に決定されるわけではない、ということがこの複雑さの原因である。例えば、これら二つの三角形の陰になって見えない部分がある関係が、Ａ＜Ｂとして表される「ＢはＡの陰になって見えない部分があることはない」という関係であると判明した場合、Ａ＞Ｃ０＞Ｃ１．．．＞Ｃｎ＞Ｂとして表される陰になって見えない部分がある連鎖関係を有する単一もしくは複数の三角形Ｃ０，Ｃ１，．．．，Ｃｎが存在する可能性があり、このことにより、最終リストにおいてＡがＢに先行するべきであるということになる。
【００６０】
図７は、ｎ＝０であるケースに対応して描かれた、陰になって見えない部分がある連鎖関係を示す。この図においては、図の真上が「目の位置」となっている。この種のソーティング問題に「分断攻略」のパラダイムを直接応用するのは、可能であるとしても困難であり、一般的に演算複雑性Ｏ（Ｎ２）を有するアルゴリズムが予想される。深さソーティング用アルゴリズムはＢＳＰツリーのそれぞれのリーフノードのみに応用され、単一のリーフノード上の三角形の最大数はコントロール可能であるため、好ましい実施例においてはこの演算負荷は軽減される。
【００６１】
一般的に元のリストにおいてＡがＢより先であると仮定した場合、陰になって見えない部分があるかどうかのテストで求められる結果は、ＢがＡの陰になって見えない部分がある状態にあるかどうかである。我々は先ず、複雑性が徐々に増加する、下記の四つの基本テスト［４］を用いる。どれか一つのテストが成功すれば、「ＢはＡの陰になって見えない部分がある状態ではない」という結論が導き出される。
【００６２】
１．視野座標システムで、Ａの最小Ｚ値はＢの最大Ｚ値よりも大きいか？
２．画像スペース内の、これら二つの三角形の軸に沿った境界ボックスは重なり
合っているか？
３．三角形Ａは、三角形Ｂに対して目の位置と反対側に位置しているか？
４．三角形Ｂは、三角形Ａに対して目の位置と同じ側に位置しているか？
【００６３】
典型的なＣＡＤモデルにおいては、モデルデータは通常スペース的にかなりコンパクトであり、これらの基本テストのどれも成功しない場合が多々ある。このケースを扱うための公知のアプローチは、二つの多角形が既に正しく順序づけられている場合でも視野に依存したスプリットを行うことがあるので、理想的ではない。フレーム毎にキャッシュに格納されたＢＳＰツリーの頻繁なアップデートが必要となるこのようなスプリットを避けるために、好ましい実施例では陰になって見えない部分があるかどうかの高次のテストを適用する。
【００６４】
【００６５】
図８Ａ乃至８Ｃは三角形と、三角形の陰になって見えない領域を示す。図８Ａはもう一方の三角形がそれだけである場合の領域Ｒを示す。図８Ｂは頂点ｖが共有されている場合の領域Ｒｖを示す。図８Ｃは辺ｅが共有されている場合の領域Ｒｅを示す。それそれの図において、目の位置が表示されている。
【００６６】
図９は三角形ＡとＢ領域の境界線との交差部分を示している。
【００６７】
Ａ領域として表される三角形Ａの陰になって見えない領域が構築された後、三角形Ｂ上の陰になって見えないポイントの位置を迅速に探し出す方法は、三角形の共有されていない頂点のそれぞれを三角形Ａに対してテストすることである。陰になって見えないポイントが見つからず、二つの三角形が一つの辺を共有する場合、「ＢはＡの影になって見えない部分がある状態ではない」。そうでなければ、Ｂ領域が構築され、Ａ上の共有されていない頂点から陰になって見えないポイントを検索する。それでも陰になって見えないポイントが見つからず、二つの三角形が一つの頂点を共有する場合もまた、「ＢはＡの影になって見えない部分がある状態ではない」という結論が得られる。二つの三角形だけであり、どちらの三角形のどの頂点も陰になって見えないポイントとなる条件を満たさない場合、我々はＢ領域の錐形の境界とＡとを交差させて、陰になって見えないポイントを演算する。演算された交差ポイントは錐形の境界上に位置し、陰になって見えないポイントとなる条件を満たす。図９に示されるケースに関しては、四つの交差ポイントがある。交差部分ポイントが見つからない場合、三角形Ｂは三角形Ａの陰になって見えない部分がある状態ではない。陰になって見えない部分があるかどうかの高次なテストのアルゴリズムの疑似コードの例を以下に示す。
【００６８】
PROC occlusion-test (triA, triB)
{
regionA = construct-region(triA);
occlusionPt = find-occlusionPt(triB, regionA); if (occlusionPt is found) {
return halfPlaneTest(occlusionPt, triA);
}
else if (triA shares an edge with triB) {
return “triA does not occlude triB”; }
else {
regionB = construct-region(triB);
occlusionPt = find-occlusionPt(triA, regionB);
if (occlusionPt is found) {
return halfPlaneTest(occlusionPt, triB);
}
else if (triA shares a vertex with triB) {
return “triA does not occlude triB”; }
else{
occlusionPt = intersect(triA, regionB);
if (occlusionPt is found) {
return halfPlaneTest(occlusionPt, triB);
}
else{
return “triA does not occlude triB”;
}
}
}
}
【００６９】
【００７０】
開示された視野をキャッシュに格納するアルゴリズム用疑似コードの例を以下に示す。この実施例において選択された参考方向は、単位球面上に均等に分散している。その時の視野方向に関して、最も近い参考方向が識別される。この参考方向からはキャッシュに格納された三角形リストが入手できない場合、三角形をソーティングするオペレーションが実行され、作成された三角形の配列が参考方向に対してキャッシュに格納される。これ以外の場合には、キャッシュに格納されたリストがレンダリングのために直接呼び出される。
【００７１】
PROC view-caching (inNode, inViewDir, outSortedList)
{
if(refDirList is empty)
refDirList = constructReferenceDirList();
closestRefDir = findClosestRef(inViewDir, refDirList); if(cachedTriList is available for closestRefDir){
outSortedList = cachedTriList;
}
else{
triangle-sort(inNode, inViewDir, outSortedList);
cacheList(closestRefDir, outSortedList);
}
return;
}
【００７２】
視野をキャッシュに格納することで、三角形ソーティングの実行が必要となる頻度が減ることにより、レンダリングのスピードが改善される。幾何学データの代わりにグラフィックスデータをキャッシュに格納することで更なる最適化が実現できる。例えば、三角形リストの代わりにディスプレイリストを参考方向においてキャッシュに格納することもできる。この方法によれば、必要なレンダリングのオペレーションも減らすことができる。
【００７３】
図１０は、上述のプロセスの詳細な説明に対応した、好ましい実施例によるプロセスのフローチャートを図示している。先ず、システムは透過的ノードとその時の視野方向を説明する幾何学データを受け取る（ステップ１００５）。
【００７４】
次に、システムはバイナリスペースパーティションツリーを構築する。ここで、透過的三角形のそれぞれがＢＳＰツリーのリーフと関連づけられる（ステップ１０１０）。
【００７５】
次に、ＢＳＰツリーを走査し各リーフにおいて三角形をソートすることで、実質的に奥から手前の順になるよう三角形をソートする（ステップ１０１５）。
【００７６】
次に、ソートされた三角形をグラフィックスＡＰＩに出力する(ステップ１０２０)。
【００７７】
最後に、その時の視野に対してソートされたデータを、三角形の形でもしくは表示リストの形でキャッシュに格納する（ステップ１０２５）。
【００７８】
図１１は好ましい実施例によるもう一つのプロセスのフローチャートを図示している。このプロセスは、上述のＢＳＰツリーの構築を説明する。第一に事前処理の段階で、システムはそれぞれの三角形の法線情報及び位置情報を含め、それぞれの三角形の形状知識を分析する（ステップ１１０５）。次に、システムはルートノード及びノードリストを作成する(ステップ１１１０)。
【００７９】
その後、ツリーの各ノードに関して、システムは本願記載の区分面選択（ステップ１１１５）を実行する。その後、ノードのそれぞれの三角形は区分面に関して分類され（ステップ１１２０）、この分類に基づき、子ノードが作成される(ステップ１１２５)。
【００８０】
残りのノードがある場合（ステップ１１３０）、このプロセスを繰り返す（ステップ１１１５に戻る）。残りのノードがなければ、ここでプロセスは終了し（ステップ１１３５）、全体プロセスでの次のステップが実行できる。
【００８１】
グラフィックス処理及びレンダリングに関する更なる背景情報は、下記の文献に記載されており、これらの文献は全て参照することにより本願に含まれるものである。アブラハム・マーメン著、「バーチャルピクセルマップ技術とともに使用される透過的性及びアンチエイリアスアルゴリズム」、ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ＆ Ａｐｐｌｉｃａｔｉｏｎｓ、９（４）、１９８９年７月、４３−５５；キャス・エベリット著、「インタラクティブなオーダー非依存型透過的性」、白書、エヌビディア、２００１年；マイケル・ケリー、カーク・ゴールド、ブレント・ピース、ステファニー・ウィナー、アレックス・イェン著、「ハードウェアで加速されたＣＳＧレンダリング及び透過的性」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２１ｓｔ ａｎｎｕａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｃｏｍｐｕｔｅｒ ｇｒａｐｈｉｃｓ ａｎｄ ｉｎｔｅｒａｃｔｉｖｅ ｔｅｃｈｎｉｑｕｅｓ、１９９４年、１７７−１８４；ニューウェル、Ｍ・Ｅ、ニューウェル、Ｒ・Ｇ、及びサンチャ、Ｔ・Ｌ著、「隠れたサーフェス問題へのソリューション」、Ｐｒｏｃ． ＡＣＭ Ｎａｔｉｏｎａｌ Ｃｏｎｆ．、１９７２年；ヘンリー・ファッチ、ズビ・Ｍ・ケデム、ブルース・Ｆ・ネイラー著、「アプリオリなツリー構造による目に見えるサーフェスの生成について」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ７ｔｈ ａｎｎｕａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｃｏｍｐｕｔｅｒ ｇｒａｐｈｉｃｓ ａｎｄ ｉｎｔｅｒｎａｃｔｉｖｅ ｔｅｃｈｎｉｑｕｅｓ、１９８０年７月、１２４−１３３；ヘンリー・ファッチ、グレゴリー・Ｄ・アブラム、エリック・Ｄ・グラント著、「リジットオブジェクトのほぼリアルタイムでの陰影ディスプレイ」、Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ、Ｖｏｌ．１、Ｎｏ．３、１９８３年７月．［７］マイケル・ディアリング著、「形状圧縮」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２２ｎｄ ａｎｎｕａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｃｏｍｐｕｔｅｒ ｇｒａｐｈｉｃｓ ａｎｄ ｉｎｔｅｒａｃｔｉｖｅ ｔｅｃｈｎｉｑｕｅｓ、１９９５年９月．［８］フォレイ、Ｊ・Ｄ、バン・ダム、Ａ、フェイナー、Ｓ・Ｋ、ヒューズ、Ｊ・Ｆ著、「コンピュータグラフィックス：原理と実践」、第２刊、アディソン―ウェスリー、１９９７年。
【００８２】
説明を簡潔かつ明確にするために、本発明と共に使用するに適した全てのデータ処理システムに関し、その完全な構成とオペレーションが本願に図示もしくは記載されているわけではないことを当業者は認識するであろう。そうではなく、本発明に特有なデータ処理システム、もしくは本発明を理解するのに必要なデータ処理システムのみが図示及び記載されている。データ処理システムの構成とオペレーションで本願に記載されていないものは、当技術分野で公知の様々な現行の実施方法及び使用例に沿ったもので良い。
【００８３】
本発明は完全に機能的なシステムとして記載されているが、本発明のメカニズムの少なくとも一部は、機械で使用可能な様々な形態の媒体に収められた指示として頒布させることができることを当業者は理解するであろうことと、また本発明が、実際の頒布のために使用される指示もしくはシグナルを含む媒体の特定の種類に関わらず、同じ様に応用できることは、特記すべき事項である。機械で使用可能な媒体の例としては読み取り専用メモリ（ＲＯＭ）もしくは電気的消去、プログラム可能型読み取り専用メモリ（ＥＥＰＲＯＭ）などの不揮発性のハードコードされた媒体、フロッピーディスク、ハードディスクドライブ、及びコンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、もしくはデジタル多用途ディスク（ＤＶＤ）などのユーザーが記録できる媒体、及び、デジタルコミュニケーションリンク及びアナログコミュニケーションリンクなどの伝達型媒体が含まれる。
【００８４】
本発明の実施例はその詳細が記載されているが、本願が開示する発明は、その最も広範な精神及び範囲から逸脱することなく、様々な形で変更、置き換え、変形、及び改良できるということを当業者は理解するであろう。
【００８５】
本出願内の記載は如何なるものであれ、特定の構成要素、ステップ、もしくは機能が、特許請求の範囲に含まれなければならない不可欠な構成要素であると示唆するものではない。つまり、特許に含まれる内容の範囲は、請求項の範囲によってのみ定義されるものである。また、これらの請求項はどれも、「（ため）の手段」という言葉が分詞の後に続かない限り、合衆国法典第３５編第１２条の第６段落の発動を意図するものではない。
【００８６】
本発明及び本発明による効果をより完全に理解するために、付随する図面と併せながら下記に説明をする。なお、図内の同じ数字は同じものを示す。
【図面の簡単な説明】
【００８７】
【図１】様々な実施例を実現できるデータ処理システムのブロック図である。
【図２】本発明の一実施例による概略図である。
【図３】ＢＳＰ木構造アルゴリズムの概要を示している。
【図４】Ａ及びＢはそれぞれ、釣合いのとれたツリー（ｂａｌａｎｃｅｄ ｔｒｅｅ）と不釣合いなツリー（ｕｎｂａｌａｎｃｅｄ ｔｒｅｅ）を図示している。
【図５】３２ビットの整数としての面インデックスのレイアウトの一例である。
【図６】抽出した階層グループの一例を図示している。
【図７】陰になって見えない部分が連鎖している関係を示している。
【図８】Ａ乃至Ｃは、三角形の陰になって見えない部分がある領域の三つの異なる形を示している。
【図９】三角形と領域の境界線との交差部分を示している。
【図１０】好ましい実施例によるプロセスのフローチャートである。
【図１１】好ましい実施例による別のプロセスのフローチャートである。
【特許請求の範囲】
【請求項１】
グラフィックオブジェクトに対するノードと視野データを受け取ることと、
該グラフィックオブジェクトに対応するバイナリスペースパーティションツリーを構築することで、該バイナリスペースパーティションツリーが、それぞれのリーフに関連する少なくとも一つの形状を有する、ことと、
該バイナリスペースパーティションツリーのそれぞれのリーフで形状をソートすることと、
該ソートされた形状を出力することと、
から成るグラフィックス処理の方法。
【請求項２】
該形状が実質的に奥から手前の順にソートされることを特徴とする請求項１の方法。
【請求項３】
該形状データをキャッシュに格納することから更に成る請求項１の方法。
【請求項４】
該バイナリスペースパーティションツリーを走査することから更に成る請求項１の方法。
【請求項５】
該形状が三角形であることを特徴とする請求項１の方法。
【請求項６】
構成コンポーネントが使用され、該構成コンポーネントが該バイナリスペースパーティションツリーの解像度と各リーフにおけるソーティング形状とのバランスを取ることを特徴とする請求項１の方法。
【請求項７】
構成コンポーネントが使用され、該構成コンポーネントがリソースの使用とキャッシュへの格納の解像度の正確性とのバランスを取ることを特徴とする請求項３の方法。
【請求項８】
グラフィックオブジェクト内の形状を分析することと、
バイナリスペースパーティションツリーに対してルートノードと追加ノードのリストを作成することで、それぞれのノードが少なくとも一つの形状に関連づけられている、ことと、
追加ノードのそれぞれに対して、区分面の選択を実行することと、
該区分面の選択に基づいて、該追加ノードにおいて形状を分類することと、
該形状の分類に基づいて、子ノードを作成することと、
から成るグラフィックス処理の方法。
【請求項９】
それぞれのノードが、三次元空間領域に置かれた一組のエレメントを表すことを特徴とする請求項８の方法。
【請求項１０】
該形状が三角形であることを特徴とする請求項８の方法。
【請求項１１】
少なくともプロセッサとアクセス可能なメモリを有するデータ処理システムで、
グラフィックオブジェクトに対するノードと視野データを受け取るための手段と、
該グラフィックオブジェクトに対応するバイナリスペースパーティションツリーを構築するための手段で、該バイナリスペースパーティションツリーが、それぞれのリーフに関連する少なくとも一つの形状を有する、該手段と、
該バイナリスペースパーティションツリーのそれぞれのリーフで形状をソートするための手段と、
該ソートされた形状を出力するための手段と、
から成る該データ処理システム。
【請求項１２】
該形状が実質的に奥から手前の順にソートされることを特徴とする請求項１１のデータ処理システム。
【請求項１３】
該形状データをキャッシュに格納するための手段から更に成る請求項１１のデータ処理システム。
【請求項１４】
該バイナリスペースパーティションツリーを走査するための手段から更に成る請求項１１のデータ処理システム。
【請求項１５】
該形状が三角形であることを特徴とする請求項１１のデータ処理システム。
【請求項１６】
構成コンポーネントが使用され、該構成コンポーネントが該バイナリスペースパーティションツリーの解像度と各リーフにおけるソーティング形状とのバランスを取ることを特徴とする請求項１１のデータ処理システム。
【請求項１７】
構成コンポーネントが使用され、該構成コンポーネントがリソースの使用とキャッシュへの格納の解像度の正確性とのバランスを取ることを特徴とする請求項１３のデータ処理システム。
【請求項１８】
少なくともプロセッサとアクセス可能なメモリを有するデータ処理システムで、
グラフィックオブジェクト内の形状を分析するための手段と、
バイナリスペースパーティションツリーに対してルートノードと追加ノードのリストを作成するための手段で、それぞれのノードが少なくとも一つの形状に関連づけられている、該手段と、
追加ノードのそれぞれに対して、区分面の選択を実行するための手段と、
該区分面の選択に基づいて、該追加ノードにおいて形状を分類するための手段と、
該形状の分類に基づいて、子ノードを作成するための手段と、
から成る該データ処理システム。
【請求項１９】
それぞれのノードが、三次元空間領域に置かれた一組のエレメントを表すことを特徴とする請求項１８のデータ処理システム。
【請求項２０】
該形状が三角形であることを特徴とする請求項１８のデータ処理システム。
【請求項２１】
機械で読み取り可能な媒体に具現的に実施されたコンピュータプログラム製品で、
グラフィックオブジェクトに対するノードと視野データを受け取るための指示と、
該グラフィックオブジェクトに対応するバイナリスペースパーティションツリーを構築するための指示で、該バイナリスペースパーティションツリーが、それぞれのリーフに関連する少なくとも一つの形状を有する、該指示と、
該バイナリスペースパーティションツリーのそれぞれのリーフで形状をソートするための指示と、
該ソートされた形状を出力するための指示と、
から成る該コンピュータプログラム製品。
【請求項２２】
該形状が実質的に奥から手前の順にソートされることを特徴とする請求項２１のコンピュータプログラム製品。
【請求項２３】
該形状データをキャッシュに格納するための指示から更に成る請求項２１のコンピュータプログラム製品。
【請求項２４】
該バイナリスペースパーティションツリーを走査するための指示から更に成る請求項２１のコンピュータプログラム製品。
【請求項２５】
該形状が三角形であることを特徴とする請求項２１のコンピュータプログラム製品。
【請求項２６】
構成コンポーネントが使用され、該構成コンポーネントが該バイナリスペースパーティションツリーの解像度と各リーフにおけるソーティング形状とのバランスを取ることを特徴とする請求項２１のコンピュータプログラム製品。
【請求項２７】
構成コンポーネントが使用され、該構成コンポーネントがリソースの使用とキャッシュへの格納の解像度の正確性とのバランスを取ることを特徴とする請求項２３のコンピュータプログラム製品。
【請求項２８】
機械で読み取り可能な媒体に具現的に実施されたコンピュータプログラム製品で、
グラフィックオブジェクト内の形状を分析するための指示と、
バイナリスペースパーティションツリーに対してルートノードと追加ノードのリストを作成するための指示で、それぞれのノードが少なくとも一つの形状に関連づけられている、該指示と、
追加ノードのそれぞれに対して、区分面の選択を実行するための指示と、
該区分面の選択に基づいて、該追加ノードにおいて形状を分類するための指示と、
該形状の分類に基づいて、子ノードを作成するための指示と、
から成る該コンピュータプログラム製品。
【請求項２９】
それぞれのノードが、三次元空間領域に置かれた一組のエレメントを表すことを特徴とする請求項２８のコンピュータプログラム製品。
【請求項３０】
該形状が三角形であることを特徴とする請求項２８のコンピュータプログラム製品。
【請求項１】
グラフィックオブジェクトに対するノードと視野データを受け取ることと、
該グラフィックオブジェクトに対応するバイナリスペースパーティションツリーを構築することで、該バイナリスペースパーティションツリーが、それぞれのリーフに関連する少なくとも一つの形状を有する、ことと、
該バイナリスペースパーティションツリーのそれぞれのリーフで形状をソートすることと、
該ソートされた形状を出力することと、
から成るグラフィックス処理の方法。
【請求項２】
該形状が実質的に奥から手前の順にソートされることを特徴とする請求項１の方法。
【請求項３】
該形状データをキャッシュに格納することから更に成る請求項１の方法。
【請求項４】
該バイナリスペースパーティションツリーを走査することから更に成る請求項１の方法。
【請求項５】
該形状が三角形であることを特徴とする請求項１の方法。
【請求項６】
構成コンポーネントが使用され、該構成コンポーネントが該バイナリスペースパーティションツリーの解像度と各リーフにおけるソーティング形状とのバランスを取ることを特徴とする請求項１の方法。
【請求項７】
構成コンポーネントが使用され、該構成コンポーネントがリソースの使用とキャッシュへの格納の解像度の正確性とのバランスを取ることを特徴とする請求項３の方法。
【請求項８】
グラフィックオブジェクト内の形状を分析することと、
バイナリスペースパーティションツリーに対してルートノードと追加ノードのリストを作成することで、それぞれのノードが少なくとも一つの形状に関連づけられている、ことと、
追加ノードのそれぞれに対して、区分面の選択を実行することと、
該区分面の選択に基づいて、該追加ノードにおいて形状を分類することと、
該形状の分類に基づいて、子ノードを作成することと、
から成るグラフィックス処理の方法。
【請求項９】
それぞれのノードが、三次元空間領域に置かれた一組のエレメントを表すことを特徴とする請求項８の方法。
【請求項１０】
該形状が三角形であることを特徴とする請求項８の方法。
【請求項１１】
少なくともプロセッサとアクセス可能なメモリを有するデータ処理システムで、
グラフィックオブジェクトに対するノードと視野データを受け取るための手段と、
該グラフィックオブジェクトに対応するバイナリスペースパーティションツリーを構築するための手段で、該バイナリスペースパーティションツリーが、それぞれのリーフに関連する少なくとも一つの形状を有する、該手段と、
該バイナリスペースパーティションツリーのそれぞれのリーフで形状をソートするための手段と、
該ソートされた形状を出力するための手段と、
から成る該データ処理システム。
【請求項１２】
該形状が実質的に奥から手前の順にソートされることを特徴とする請求項１１のデータ処理システム。
【請求項１３】
該形状データをキャッシュに格納するための手段から更に成る請求項１１のデータ処理システム。
【請求項１４】
該バイナリスペースパーティションツリーを走査するための手段から更に成る請求項１１のデータ処理システム。
【請求項１５】
該形状が三角形であることを特徴とする請求項１１のデータ処理システム。
【請求項１６】
構成コンポーネントが使用され、該構成コンポーネントが該バイナリスペースパーティションツリーの解像度と各リーフにおけるソーティング形状とのバランスを取ることを特徴とする請求項１１のデータ処理システム。
【請求項１７】
構成コンポーネントが使用され、該構成コンポーネントがリソースの使用とキャッシュへの格納の解像度の正確性とのバランスを取ることを特徴とする請求項１３のデータ処理システム。
【請求項１８】
少なくともプロセッサとアクセス可能なメモリを有するデータ処理システムで、
グラフィックオブジェクト内の形状を分析するための手段と、
バイナリスペースパーティションツリーに対してルートノードと追加ノードのリストを作成するための手段で、それぞれのノードが少なくとも一つの形状に関連づけられている、該手段と、
追加ノードのそれぞれに対して、区分面の選択を実行するための手段と、
該区分面の選択に基づいて、該追加ノードにおいて形状を分類するための手段と、
該形状の分類に基づいて、子ノードを作成するための手段と、
から成る該データ処理システム。
【請求項１９】
それぞれのノードが、三次元空間領域に置かれた一組のエレメントを表すことを特徴とする請求項１８のデータ処理システム。
【請求項２０】
該形状が三角形であることを特徴とする請求項１８のデータ処理システム。
【請求項２１】
機械で読み取り可能な媒体に具現的に実施されたコンピュータプログラム製品で、
グラフィックオブジェクトに対するノードと視野データを受け取るための指示と、
該グラフィックオブジェクトに対応するバイナリスペースパーティションツリーを構築するための指示で、該バイナリスペースパーティションツリーが、それぞれのリーフに関連する少なくとも一つの形状を有する、該指示と、
該バイナリスペースパーティションツリーのそれぞれのリーフで形状をソートするための指示と、
該ソートされた形状を出力するための指示と、
から成る該コンピュータプログラム製品。
【請求項２２】
該形状が実質的に奥から手前の順にソートされることを特徴とする請求項２１のコンピュータプログラム製品。
【請求項２３】
該形状データをキャッシュに格納するための指示から更に成る請求項２１のコンピュータプログラム製品。
【請求項２４】
該バイナリスペースパーティションツリーを走査するための指示から更に成る請求項２１のコンピュータプログラム製品。
【請求項２５】
該形状が三角形であることを特徴とする請求項２１のコンピュータプログラム製品。
【請求項２６】
構成コンポーネントが使用され、該構成コンポーネントが該バイナリスペースパーティションツリーの解像度と各リーフにおけるソーティング形状とのバランスを取ることを特徴とする請求項２１のコンピュータプログラム製品。
【請求項２７】
構成コンポーネントが使用され、該構成コンポーネントがリソースの使用とキャッシュへの格納の解像度の正確性とのバランスを取ることを特徴とする請求項２３のコンピュータプログラム製品。
【請求項２８】
機械で読み取り可能な媒体に具現的に実施されたコンピュータプログラム製品で、
グラフィックオブジェクト内の形状を分析するための指示と、
バイナリスペースパーティションツリーに対してルートノードと追加ノードのリストを作成するための指示で、それぞれのノードが少なくとも一つの形状に関連づけられている、該指示と、
追加ノードのそれぞれに対して、区分面の選択を実行するための指示と、
該区分面の選択に基づいて、該追加ノードにおいて形状を分類するための指示と、
該形状の分類に基づいて、子ノードを作成するための指示と、
から成る該コンピュータプログラム製品。
【請求項２９】
それぞれのノードが、三次元空間領域に置かれた一組のエレメントを表すことを特徴とする請求項２８のコンピュータプログラム製品。
【請求項３０】
該形状が三角形であることを特徴とする請求項２８のコンピュータプログラム製品。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公表番号】特表２００７−５１４２４３（Ｐ２００７−５１４２４３Ａ）
【公表日】平成１９年５月３１日（２００７．５．３１）
【国際特許分類】
【出願番号】特願２００６−５４４０５０（Ｐ２００６−５４４０５０）
【出願日】平成１６年１２月９日（２００４．１２．９）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０４１５３２
【国際公開番号】ＷＯ２００５／０５７５０２
【国際公開日】平成１７年６月２３日（２００５．６．２３）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（５０４４３８２８８）ユージーエス、コープ (13)
【Ｆターム（参考）】
【公表日】平成１９年５月３１日（２００７．５．３１）
【国際特許分類】
【出願日】平成１６年１２月９日（２００４．１２．９）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０４１５３２
【国際公開番号】ＷＯ２００５／０５７５０２
【国際公開日】平成１７年６月２３日（２００５．６．２３）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（５０４４３８２８８）ユージーエス、コープ (13)
【Ｆターム（参考）】
[ Back to top ]