(57)【要約】【課題】グラフィクスオブジェクトの３Ｄモデルをレンダリングする方法を提供する。【解決手段】モデルは離散的な０次元のポイントを含む。第１の不透明なポリゴンが各ポイントを中心として配置され、このポリゴンはｚバッファ内に奥行き像の奥行き値を得るためにレンダリングされる。第２のポリゴンが各ポイントを中心として配置される。第２のポリゴンは関連するオブジェクト空間ＥＷＡリサンプリングフィルタに適合され、適合された第２ポリゴンは、奥行き像における奥行き値に従って像としてレンダリングされる。【選択図】図１
2004164593.tif 000002
【特許請求の範囲】
【請求項１】
グラフィクスオブジェクトの、複数のポイントを含む３Ｄモデルをレンダリングする方法であって、
各ポイントを中心として第１ポリゴンを配置することと、
奥行き像における奥行き値として前記第１ポリゴンをレンダリングすることと、
各ポイントを中心として第２ポリゴンを配置することと、
それぞれの第２ポリゴンを関連するオブジェクト空間ＥＷＡリサンプリングフィルタに適合させることと、
前記奥行き像における前記奥行き値にしたがって、それぞれの適合した第２ポリゴンを像としてレンダリングすることとを備える方法。
【請求項２】
前記ポイントは離散的かつ非連結である、請求項１に記載の方法。
【請求項３】
前記ポイントはポリゴンメッシュにおける頂点である、請求項１に記載の方法。
【請求項４】
各ポイントは３Ｄ位置、サーフェス法線、および色を有する、請求項１に記載の方法。
【請求項５】
前記第１ポリゴンは、前記ポイントの法線に垂直であり、かつ不透明である、請求項４に記載の方法。
【請求項６】
前記第１ポリゴンを前記モデルのサーフェスから奥行きしきい値だけ視線に沿ってオフセットすることをさらに備える、請求項１に記載の方法。
【請求項７】
前記第１ポリゴンをレンダリングすることは、グラフィクス処理ユニット内のラスタ化手段を使用する、請求項１に記載の方法。
【請求項８】
前記適合させることは、
前記第２ポリゴンをスケーリングし伸張することと、
前記適合した第２ポリゴンをアルファ混合することと、
をさらに備える請求項１に記載の方法。
【請求項９】
前記像を正規化することをさらに備える請求項１に記載の方法。
【請求項１０】
それぞれのオブジェクト空間ＥＷＡリサンプリングフィルタを得るために像空間ＥＷＡリサンプリングフィルタをオブジェクト空間に写像することをさらに備える請求項１に記載の方法。
【請求項１１】
前記第２ポリゴンをレンダリングすることは、
前記第２ポリゴンを像空間に投影することと、
前記投影された第２ポリゴンをラスタ化することと、
をさらに備える請求項１に記載の方法。
【請求項１２】
前記第２ポリゴンをレンダリングすることは、グラフィクス処理ユニットの頂点シェーダを使用する、請求項１に記載の方法。
【請求項１３】
エイリアシング効果を避けるために、レンダリング中にビュー依存ポイント位置を動的に決定することをさらに備える請求項１に記載の方法。
【請求項１４】
前記第１ポリゴンは、前記ポイント間の最大距離の２倍の辺の長さを有する四辺形である、請求項１に記載の方法。
【請求項１５】
前記奥行きしきい値は、前記ポイント間の平均距離である、請求項６に記載の方法。
【請求項１６】
前記ポイントを階層化奥行きキューブに記憶することをさらに備える請求項１に記載の方法。
【請求項１７】
各ポイントに、離散的単位ガウシアン基底関数をアルファテクスチャとしてエンコードすることと、
前記関連するオブジェクト空間ＥＷＡリサンプリングフィルタに適合するように前記テクスチャを伸張しスケーリングすることと、
前記伸張されスケーリングされたテクスチャを前記第２ポリゴンに適用することと、
をさらに備える請求項１に記載の方法。
【請求項１８】
前記オブジェクト空間ＥＷＡリサンプリングフィルタを得るために、オブジェクト空間基底関数とワーピングされたプレフィルタとの畳み込みをとることをさらに備える請求項１に記載の方法。
【請求項１９】
グラフィクスオブジェクトの、複数のポイントを含む３Ｄモデルをレンダリングする装置であって、
各ポイントを中心として第１ポリゴンを配置する手段と、
前記第１ポリゴンをレンダリングすることにより得られる奥行き値を記憶するように構成された奥行きバッファと、
各ポイントを中心として第２ポリゴンを配置する手段と、
それぞれの第２ポリゴンを関連するオブジェクト空間ＥＷＡリサンプリングフィルタに適合させるように構成された頂点シェーダと、
前記奥行きバッファ内の前記奥行き値に従って、それぞれの適合した第２ポリゴンを像としてレンダリングするように構成されたピクセルシェーダとを備える装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、グラフィクスモデルをレンダリングすることに関し、より詳細には、グラフィクスハードウェアレンダリングエンジンにおいてサーフェススプラッティングによりポイントベースの３Ｄサーフェスモデルをレンダリングすることに関する。
【背景技術】
【０００２】
ポイントベースのサーフェスモデルは、３Ｄグラフィクスオブジェクトのサーフェスをサンプルポイントの集合により定義する。ポイントベースのレンダリングは、離散的なサンプリングされたサーフェスポイントの連続像を生成する。サーフェス上のポイントは、ピクチャエレメント(ピクセル)およびボリュームエレメント(ボクセル)のその類似性を示すために、一般にサーフェスエレメントまたは「サーフェル(surfel)」と呼ばれている。
【０００３】
ポイントベースの表現は、連結性情報が要求されないかもしくは利用可能でないレンダリングアプリケーションにおける複雑なトポロジーを有するグラフィクスモデルにとって、または複数の情報源からのデータの融合にとって、利点を有する。例えば、Levoy等著「The Use of Points as Display Primitives」Technical Report TR 85-022, The University of North Carolina at Chapel Hill, Department of Computer Science, 1985、Zwicker等著「Surface Splatting」SIGGRAPH 2001 Proceedings, pp.371-378, 2001、およびPfister等に２００２年５月２８日に交付された米国特許第６，３９６，４９６号「Method for modeling graphical objects represented as surface elements」（これらを参照により本明細書に援用する）を参照されたい。
【０００４】
ポイントベースのモデルは、３Ｄ走査技法を用いて直接に、またはテクスチャを有するポリゴンモデルからの変換により、獲得することができる。Levoy等著「The Digital Michelangelo Project: 3D Scanning of Large Statues」SIGGRAPH 2000 Proceedings, pp.131-144, 2000、およびPfister等著「Surfels: Surface Elements as Rendering Primitives」SIGGRAPH 2000 Proceedings, pp.335-342, 2000を参照されたい。
【０００５】
ほとんどの従来技術のポイントベースのレンダリング方法は、効率および速度に焦点を当てている。それらの方法のいくつかは、毎秒２〜５百万ポイントのインタラクティブレンダリング性能を達成するためにＯｐｅｎＧＬおよびハードウェア高速化を使用する。Rusinkiewicz等著「QSplat: A Multiresolution Point Rendering System for Large Meshes」SIGGRAPH 2000 Proceedings, pp.343-352, 2000、およびStamminger等著「Interactive Sampling and Rendering for Complex and Procedural Geometry」Proceedings of the 12th Eurographics Workshop on Rendering, pp.151-162, 2001を参照されたい。
【０００６】
しかし、それらの技法はいずれも、複雑なサーフェステクスチャを有するモデルに対するアンチエイリアス処理をサポートしていない。最近、Zwicker等は楕円加重平均（ＥＷＡ）サーフェススプラッティングを記述した。Zwicker等著「Surface Splatting」SIGGRAPH 2001 Proceedings, pp.371-378, 2001、およびZwicker等により２００１年４月２６日に出願された米国特許出願第０９／８４２，７３７号「Rendering Discrete Sample Points Projected to a Screen Space with a Continuous Resampling Filter」（これらを参照により本明細書に援用する）を参照されたい。
【０００７】
それらの方法は、異方性テクスチャフィルタリングと、不規則ポイントサンプルに適合したＥＷＡテクスチャフィルタの像空間定式化とを使用する。Greene等著「Creating Raster Omnimax Images from Multiple Perspective Views Using the Elliptical Weighted Average Filter」IEEE Computer Graphics & Applications, 6(6):21-27, 1986、およびHeckbert著「Fundamentals of Texture Mapping and Image Warping」Master's Thesis, University of California at Berkeley, Department of Electrical Engineering and Computer Science, 1989を参照されたい。
【０００８】
しかし、ＥＷＡサーフェススプラッティングのソフトウェアによる実施は、毎秒約２５０，０００ポイント以下のレンダリング性能しか達成していない。
【０００９】
ポリゴンおよびポイントプリミティブを組み合わせて、像空間投影基準に基づいていずれかを選択する効率的なレンダリングシステムにすることもできる。Chen等著「POP: A Hybrid Point and Polygon Rendering System for Large Data」Proceedings of IEEE Visualization, pp.45-52, 2001、およびCohen等著「Hybrid Simplification: Combining Multi-Resolution Polygon and Point Rendering」Proceedings of IEEE Visualization, pp.37-44, 2001を参照されたい。それらのシステムは両方とも、適度に複雑なモデルに対するリアルタイム性能を達成するためにグラフィクスハードウェアを利用する。しかし、いずれのシステムもサーフェステクスチャを処理しておらず、連結性情報の導入は、純粋にポイントサンプリングされたモデルのメリットをさらに減少させる。
【００１０】
像空間ＥＷＡスプラッティング
Zwicker 等により記述された像空間ＥＷＡスプラッティングフレームワークでは、隣接性または連結性情報を含むポリゴンまたは三角形モデルとは対照的に、オブジェクトは、連結性情報のない３次元オブジェクト空間内の不規則に離間したポイント｛Ｐｋ｝の集合により表現される。
【００１１】
それぞれの０次元のポイントは、位置、サーフェス法線、放射対称基底関数ｒｋ、ならびに赤、緑、および青の色成分の連続関数を表現するスカラー係数ｗｒｋ、ｗｇｋ、ｗｂｋに関連づけられる。基底関数ｒｋは、局所パラメータ表示されたドメインで定義される再構成フィルタである。したがって、これらの関数は、離散的なポイントにより表現されるモデルのサーフェス上の連続なテクスチャ関数を定義する。
【００１２】
図１は、３Ｄオブジェクト空間１０２から２Ｄ像空間１０３への局所パラメータ表示１０１を示す。局所座標ｕを有する任意のポイントＱ１０４の近傍の色は、基底関数ｒｋ１０５を累算することにより評価され、連続なテクスチャ関数ｆｃ（ｕ）が次の加重和として得られる。
【００１３】
【数１】
2004164593.tif 000003
【００１４】
ただしｕｋは各ポイントＰｋの局所座標である。
【００１５】
Heckbert等により記述された理想的なリサンプリングフレームワークでは、テクスチャ関数ｆｃ（ｕ）をレンダリングすることにより、出力ピクセルグリッドのナイキスト基準に従う、像空間における連続な出力関数ｇｃ（ｘ）が得られる。したがって、エイリアシングアーティファクトは避けられる。そのレンダリングプロセスは以下のステップを含む。
【００１６】
まず、テクスチャ関数ｆｃ（ｕ）は、各ポイントにおける透視投影の局所アフィン写像を用いて像空間にワーピングされる。次に、連続な像空間信号は、それとプレフィルタｈとの畳み込みをとることにより帯域制限されて、出力関数ｇｃ（ｘ）が得られる。ただしｘは像空間座標である。数式を書き直した後、出力関数は、像空間リサンプリングフィルタρｋ（ｘ）の加重和として次のように表すことができる。
【００１７】
【数２】
2004164593.tif 000004
【００１８】
ただし
【００１９】
【数３】
2004164593.tif 000005
【００２０】
ここで、リサンプリングフィルタρｋ（ｘ）は、ワーピングされた基底関数ｒ′ｋ（ｘ）＝ｒｋ（ｘ）（ｍ−１（ｘ））とプレフィルタｈ（ｘ）の畳み込みとして書かれている。
【００２１】
各ポイントｕｋにおけるρｋの評価を簡単化するため、局所サーフェスパラメータ表示から像空間への投影写像ｘ＝ｍ（ｕ）の局所アフィン近似ｘ＝ｍｋ（ｕ）が使用される。局所アフィン近似ｍｋは次式となる。
【００２２】
【数４】
2004164593.tif 000006
【００２３】
局所アフィン近似ｍｋは、線形項で打ち切ったｕｋにおけるｍのテイラー展開により与えられる。ただしｘｋ＝ｍ（ｕｋ）であり、ヤコビアンは次の通りである。
【００２４】
【数５】
2004164593.tif 000007
【００２５】
ＥＷＡフレームワークでは、楕円ガウシアンが、その特有の性質のため、基底関数ｒｋおよびプレフィルタｈとして選択される。ガウシアンは、アフィン写像および畳み込みの下で閉じている。したがって、リサンプリングフィルタρｋは、以下で説明するように、楕円ガウシアンとして表すことができる。分散行列Ｖ∈Ｒ２×２を有する２Ｄ楕円ガウシアンＧＶ（ｘ）は次のように定義される。
【００２６】
【数６】
2004164593.tif 000008
【００２７】
ただし｜Ｖ｜はＶの行列式である。基底関数ｒｋおよびローパスフィルタｈの分散行列はそれぞれＶｋｒ（＝Ｖ１）およびＶｈ（＝Ｖ２）で定義され、したがってｒｋ＝ＧＶ１およびｈ＝ＧＶ２である。
【００２８】
ローパスフィルタの分散の典型的な選択は単位行列Ｉであることに留意されたい。式（３）にガウシアンの基底関数およびプレフィルタを代入することにより、ガウシアンリサンプリングフィルタが得られる。
【００２９】
【数７】
2004164593.tif 000009
【００３０】
これは像空間ＥＷＡリサンプリングフィルタと呼ばれる。さらに詳細には、Zwicker等を参照されたい。
【００３１】
像空間フィルタは、ソフトウェアによる実施に適している。しかし、ハードウェアグラフィクスエンジンは、このようなフィルタを像空間で直接決定することができない。したがって、レンダリング性能は激しく（例えば上記のように１桁以上）劣化する。
【発明の開示】
【発明が解決しようとする課題】
【００３２】
本発明の目的は、できるだけ高品質で、任意のサーフェステクスチャを有する複雑なポイントベースのモデルをインタラクティブにレンダリングするレンダリングシステムを提供することである。レンダリングシステムは、ＰＣグラフィクスハードウェアにおける進歩、すなわち、グラフィック処理ユニット（ＧＰＵ）およびプログラマブルシェーディングのますます向上する性能を利用すべきである。システムはまた、異方性テクスチャフィルタリングも提供すべきである。
【課題を解決するための手段】
【００３３】
楕円加重平均（ＥＷＡ）サーフェススプラッティングは、ポイントサンプリングされた３Ｄオブジェクトの高品質レンダリングのための技法である。ＥＷＡサーフェススプラッティングは、複雑なポイントモデルのウォータータイトなサーフェスを高品質の異方性テクスチャフィルタリングによりレンダリングする。本発明は、最新のＰＣグラフィクスハードウェアを用いるＥＷＡサーフェススプラッティングの方法を提供する。
【００３４】
本発明は、従来の三角形ベースのグラフィクスレンダリングハードウェアによる高速化レンダリングに適合したＥＷＡフィルタのオブジェクト空間定式化を提供する。オブジェクト空間ＥＷＡフィルタは、プログラマブルな頂点およびピクセルシェーダを用いて、今日のグラフィクス処理ユニット（ＧＰＵ）の能力を十分に活用してレンダリングされる。本発明による方法は、現在のＰＣグラフィクスハードウェア上で毎秒数百万ポイントをレンダリングする。これは、従来技術のＥＷＡサーフェススプラッティングの純粋なソフトウェアによる実施よりも１桁大きい。
【発明の効果】
【００３５】
ポイントごとの正規化を有するオブジェクト空間ＥＷＡサーフェススプラッティングは、高品質でインタラクティブなポイントレンダリングのための望ましいレンダリング方法である。それは、オブジェクトレベルのカリング（選抜除去）が可能なときには毎秒数百万ポイントを処理することができる。レンダリング品質をさらに改善するために、ポイントごとの正規化およびピクセルごとの正規化をプログレッシブレンダリング中に組み合わせることができる。ポイントモデルは、ユーザインタラクション中にポイントごとの正規化によりレンダリングされ、その後ピクセルごとの正規化によりリファインされる。
【００３６】
発明者は、オブジェクト空間ＥＷＡサーフェススプラッティングの性能と、像空間ＥＷＡサーフェススプラッティングのソフトウェア実施態様との比較も行っている。出力解像度が５１２の場合、本発明の方法は毎秒約１．５百万のアンチエイリアス処理されたスプラットをレンダリングすることができる。同じＰＣ上で、像空間ＥＷＡサーフェススプラッティングのソフトウェアのみによる実施は、毎秒２００，０００スプラット以下しかレンダリングしない。また、ソフトウェアレンダラの方が出力像解像度に影響されやすい。像の解像度が高くなると、ソフトウェア方法の性能は直線的に減少する。これに対して、ハードウェア高速化されたオブジェクト空間ＥＷＡサーフェススプラッティングは、出力解像度に影響されにくい。
【００３７】
本発明は、不規則なポイントサンプルに対するＥＷＡサーフェススプラッティングのオブジェクト空間定式化を提供する。第２に、本発明は、最新のＰＣグラフィクスハードウェアの頂点およびピクセルシェーダを用いて効率的にその方法を実施するマルチパス手法を提供する。本発明はまた、ＥＷＡスプラットの適切な正規化のための前処理方法を提供する。
【００３８】
性能の向上に加えて、ポイントベースのレンダリングのためにＧＰＵを使用することには他の利点もある。ＣＰＵは２年ごとに速度が倍加しているのに対して、ＧＰＵは最近９か月間でその性能が１１倍向上した。疑いなく、ＧＰＵ性能は近い将来においてもＣＰＵ速度より速く向上し続けるであろう。ＧＰＵは、その固定機能の処理のため、より多くの並列化の余地がある。
【００３９】
各ポイントが独立に処理されるため、本発明の方法の性能は直線的に向上するであろう。さらに、ＥＷＡサーフェススプラッティングのソフトウェア実施態様の性能は出力解像度の増大とともに低下するが、本発明のハードウェアベースの実施にとって重大な影響はほとんどない。最後に、ＧＰＵを使用することは、ＣＰＵを、協調的オーディオ処理のような他のタスクのために解放する。
【発明を実施するための最良の形態】
【００４０】
システムアーキテクチャ
図１０は、本発明によるハードウェア高速化レンダリングシステムおよび方法１００を示す。この方法は、オブジェクト空間楕円加重平均（ＥＷＡ）サーフェススプラッティングを用いて３Ｄポイントベースグラフィクスモデルを像８としてレンダリングする。３Ｄモデルは、離散的な０次元サーフェスポイント（サーフェル）ｐｋ１から構成され得る。各ポイント１は、３Ｄ位置、サーフェス法線、および色を有する。これらの値は、サンプリングにより得ることが可能であり、また、手続き的に生成することも可能である。別法として、ポイントはポリゴンベースのモデルの頂点であることも可能である。以下でさらに詳細に説明するように、各ポイントはまた、関連するオブジェクト空間ＥＷＡリサンプリングフィルタを有する。モデル１からの像８のレンダリングは１つ以上のパスで行われる。
【００４１】
第１パスの間に、第１のポリゴン２が、例えば四辺形(quad)の形態で、各ポイントｐｋ１（またはポリゴンメッシュの三角形の各頂点）を中心として配置される（１０）。四辺形２の平面は、そのポイントのサーフェス法線に垂直である。次に、四辺形２は、オクルージョンを避けるため、奥行きしきい値ｚｔ３だけ視線４に沿ってオフセットされ（２０）平行移動される（３０）。次に、奥行きオフセットされ平行移動された四辺形は、従来のグラフィック処理ユニット（ＧＰＵ）のハードウェアラスタ化を用いてレンダリングされる（４０）。レンダリングは、不透明四辺形の奥行き値をｚバッファに奥行き像５として累算する（５０）。累算は、視点に最も近いピクセルに対する奥行き値のみを保持し、他のすべての（オクルージョン状態の）奥行き値を捨てる。奥行き像５は後で３Ｄモデル１の可視部分を表現するピクセルをレンダリングするためにのみ使用される。
【００４２】
第２パスの間に、第２のポリゴン６が、例えば平行四辺形の形態で、各ポイントｐｋ１を中心として配置される（６０）。平行四辺形６は、ポリゴンをオブジェクト空間ＥＷＡリサンプリングフィルタ７に適合させるために伸張されスケーリングされる（７０）。次に、適合したポリゴンは、奥行き像５の奥行き値に従ってラスタ化およびアルファ混合され（８０）、最終出力像８を形成する。
【００４３】
２つの奥行きバッファが使用され、一方が実際の奥行き値を記憶し、他方がオフセット奥行き値を記憶するときには、レンダリングは単一パスで行うことができることが留意されるべきである。また、もう１つのパスで正規化が実行可能であることも留意されるべきである。また、各ポイントの第１のポリゴンと、対応する第２のポリゴンとは同一とすることが可能であることも留意されるべきである。
【００４４】
本方法およびシステムについて以下でさらに詳細に説明する。
【００４５】
オブジェクト空間ＥＷＡスプラッティング
上記の式（３）において、リサンプリングフィルタは像すなわちスクリーン空間座標ｘの関数として表されており、これはソフトウェアによる実施に適している。しかし、ハードウェアグラフィクスエンジンはこのようなフィルタを像空間で直接計算することができない。本発明により所望されているように、ＥＷＡスプラッティングをグラフィクスハードウェアによる高速化になじみやすくするため、リサンプリングフィルタをオブジェクト空間においてパラメータ表示されたサーフェス上の関数として定式化する。そうすれば、モデルのサーフェスを像空間に投影するためにグラフィクスハードウェアを活用することができ、式（３）のような像空間におけるリサンプリングフィルタが得られる。
【００４６】
これを行うため、局所アフィン近似ｍｋを用いて式（３）を次のように書き直す。
【００４７】
【数８】
2004164593.tif 000010
【００４８】
これは、局所サーフェスパラメータ表示の座標ｕで定義されたオブジェクト空間リサンプリングフィルタρ′ｋを与える。像空間リサンプリングフィルタとは異なり、本発明によるオブジェクト空間リサンプリングフィルタは、もとの基底関数ｒｋ（ｕ）と、ワーピングされた（ローパス）プレフィルタｈ′ｋ（ｕ）＝｜Ｊｋ｜ｈ（Ｊｋ（ｕ））との畳み込みを含む。
【００４９】
図２Ａに示すように、ρ′ｋ２０１とρｋ（ｘ）２０２の間の変換（ｍおよびｍ−１）は、オブジェクト空間から像への写像、およびオブジェクト空間から像空間への投影に対応する。
【００５０】
式（６）の基底関数およびプレフィルタとしてガウシアンを使用する。これは、式（５）に類似した次式を与える。これをオブジェクト空間ＥＷＡリサンプリングフィルタと呼ぶ。
【００５１】
【数９】
2004164593.tif 000011
【００５２】
最後に、式（６）および（７）を用いて、式（２）の連続出力関数を、オブジェクト空間ＥＷＡリサンプリングフィルタの加重和として次のように再定式化する。
【００５３】
【数１０】
2004164593.tif 000012
【００５４】
図２Ｂは、局所サーフェスパラメータ表示におけるガウシアンリサンプリングフィルタ２１１および像空間におけるその対応物２１２を示し、図２Ｃは、チェッカーボードテクスチャの対応するワーピングおよびリサンプリングを示す。
【００５５】
ハードウェア高速化レンダリング
本発明のハードウェア高速化サーフェススプラッティングアルゴリズムは、式（８）に基づき、Ａバッファをエミュレートする２パス手法を使用する。Carpenter著「The A-buffer, an Antialiased Hidden Surface Method」In Computer Graphics, Volume 18 of SIGGRAPH Proceedings, pages 103-108, 1984を参照されたい。
【００５６】
第１パスは、以下でさらに詳細に説明するが、不透明ポリゴンを各ポイントの奥行き（ｚ）値として奥行き像５のＺバッファ内にレンダリングすることにより、可視スプラッティングを実行する。第２パスは、式（８）の演算を以下のように実行する。
【００５７】
オブジェクト空間ＥＷＡリサンプリングフィルタを、半透明アルファテクスチャを有するポリゴンとして設定する。多くの最新のＧＰＵに見られるプログラマブル頂点シェーダを使用する。すると、像空間へのテクスチャ化ポリゴンの投影により、像空間ＥＷＡリサンプリングフィルタが得られる。これをＥＷＡスプラットと呼ぶ。スプラットを、ピクセル中心で評価し、現ポイントの色ｗｒｋ、ｗｇｋ、ｗｂｋを乗じ、結果として得られる値を各ピクセルで累算する。
【００５８】
ラスタ化の間に、第１レンダリングパス中に生成されたＺバッファすなわち奥行き像５における奥行き値を用いて奥行きテストを実行し、スプラットが可視かどうかを判定する。これは、各ピクセルに、視者に最も近いサーフェスを表現するスプラットのみが累算されることを保証する。
【００５９】
従来技術とは対照的に、本発明のポイントベースのレンダリングは、アンチエイリアス処理を有する半透明スプラットと、テクスチャ化ポリゴンを用いて、各ポイント１を表現する。また、従来技術の手法では、オブジェクト空間内の各ポリゴンの位置は静的である、すなわちレンダリング前に決定されている。これに対して本発明は、以下で説明するように、エイリアシングを避けるために、レンダリング中にビュー依存ポイント位置を動的に決定する。
【００６０】
可視スプラッティング
図３に示すように、第１パス中の可視スプラッティング３００の目的は、奥行き像がいかなる「穴」も含まないようにオブジェクトの奥行き像５をＺバッファ内にレンダリングすることである。穴のない像を「ウォータータイト」であるという。奥行き像５は、以下で説明するように、第２レンダリングパスで半透明スプラットの累算を制御するために使用される。各ポイントＰｋ１を中心として、そのポイントの法線ｎｋ３０４に垂直な不透明四辺形３０２を配置する。四辺形３０２はＺバッファ内にのみラスタ化され、他のフレームバッファの属性を変更することはない。奥行き像５における穴の発生を避けるため、四辺形の辺の長さは２ｈ（３０５）に選択される。ただしｈは、ポイントＰｋ１の周りの小さい近傍内のポイント間の最大距離である。
【００６１】
オブジェクトのポイントベースのモデルをアーティファクトなしにレンダリングするため、視者に最も近い可視サーフェスのすべてのスプラットを累算する一方で、他のすべてのスプラットを捨てなければならない。スプラットのラスタ化中に、各ピクセルに、スプラットの奥行き値を上記のように生成された奥行き像５と比較することにより、現在の貢献を捨てるべきかそれとも累算すべきかを決める。しかし、可視サーフェスの貢献が偶然に捨てられないようにするため、奥行き像は、小さい奥行きしきい値ｚｔだけ視点から離れるように平行移動される。
【００６２】
簡単な解決法は、Rusinkiewicz等著「QSplat: A Multiresolution Point Rendering System for Large Meshes」SIGGRAPH 2000 Proceedings, pages 343-352, 2000に記載されているように、カメラ空間内で奥行き像５をｚｔだけｚ軸に沿って平行移動することである。
【００６３】
しかし、図４Ａに示すように、これはオクルージョンアーティファクトにつながる。図４Ａは、カメラ空間のｚ軸に沿った平行移動を示す。サーフェスＢはサーフェスＡにより部分的にオクルージョン処理されている。しかし、Ａをカメラ空間ｚ軸に沿って平行移動することにより生成される奥行き像は、Ｂの追加領域を誤ってオクルージョン処理している。図４Ｂは、本発明による視線に沿った平行移動を示す。可視スプラッティングは依然として、ｚｔが小さすぎる場合に可視サーフェスを捨てる可能性があり、ｚｔが大きすぎる場合にいくつかのサーフェスの混合につながる可能性がある。ｚｔの良好な選択は、ポイント間の平均距離である。
【００６４】
図５Ａは、オブジェクト輪郭に近いエリアにおける、オクルージョンアーティファクトを有する像の例を示す。本発明は、これらの問題点を、図４Ｂに示すように、代わりに視線に沿って奥行き像を平行移動することにより回避する。結果として、サーフェスＢにおける同じ領域がサーフェスＡおよび奥行き像によりオクルージョン処理され、図５Ｂに示す像の例にはオクルージョンアーティファクトは現れていない。
【００６５】
オブジェクト空間ＥＷＡリサンプリングフィルタの決定
図７は、式（７）のオブジェクト空間ＥＷＡリサンプリングフィルタρ′ｋを求めるためにヤコビアンＪｋ−１を評価するステップを示す。まず、局所サーフェスパラメータ表示の座標ｕをビューポート座標ｘに写像するＪｋの分解形を導出した後、その逆を求める。本発明の手法は、レイキャスティングを避け、少数の演算で決定することができる。
【００６６】
ポイントＰｋ１の周りのオブジェクトサーフェスの局所パラメータ表示を、そのサーフェスを法線ｎｋにより与えられるその接平面で近似することによって構成する。パラメータ表示は、ポイントＰｋの位置ｏ（〜）を始点とする、この平面内の２つの直交する基底ベクトルｓ（〜）およびｔ（〜）を選択することにより定義される。ｓ（〜）、ｔ（〜）、およびｏ（〜）はオブジェクト空間で定義される３×１ベクトルであることに留意されたい。したがって、局所サーフェス座標で成分ｕ０およびｕ１を有するポイントｕは、オブジェクト空間内のポイントｐｏ（ｕ）＝ｏ（〜）＋ｕ０ｓ（〜）＋ｕ１ｔ（〜）に対応する。
【００６７】
オブジェクト空間からカメラ空間への変換が一様なスケーリングＳ、回転Ｒおよび平行移動Ｔのみを含むと仮定すれば、ポイントｕはカメラ空間内の次のポイントｐｃ（ｕ）に対応する。
【００６８】
【数１１】
2004164593.tif 000013
【００６９】
ただしｏはカメラ空間内のポイント位置であり、一方ｓおよびｔはカメラ空間内で局所サーフェスパラメータ表示を定義する基底ベクトルである。
【００７０】
次に、ポイントをカメラ空間から像すなわちスクリーン空間に写像する。これは、投影分割により像平面への投影を行い、続いて像座標に係数ηのスケーリングを行うこと、すなわちビューポート変換を含む。スケーリング係数ηは、視錐台により次のように求められる。
【００７１】
【数１２】
2004164593.tif 000014
【００７２】
ただしｖｈはビューポート高さを表し、ｆｏｖは視錐台の視野であり、ｚｎｅａｒは近クリップ平面を指定する。よって、投影されたポイント（ｕ０，ｕ１）の像空間座標ｘ＝（ｘ０，ｘ１）は次のように求められる。
【００７３】
【数１３】
2004164593.tif 000015
【００７４】
したがって、式（１０）の偏導関数を含み、（ｕ０，ｕ１）＝（０，０）で評価したヤコビアンＪｋは次のようになる。
【００７５】
【数１４】
2004164593.tif 000016
【００７６】
ポイント平行四辺形の頂点位置の決定
ヤコビアン行列が求められた後、局所パラメータ表示されたサーフェス上で定義されるオブジェクト空間ＥＷＡリサンプリングフィルタは次のように書かれる。
【００７７】
【数１５】
2004164593.tif 000017
【００７８】
ただし
【００７９】
【数１６】
2004164593.tif 000018
【００８０】
図８Ａに示すように、間隔が約１のポイントに対して、再構成カーネルは単位ガウシアン、すなわちＶｋｒ＝Ｉと選択される。対称行列Ｍｋを次のように分解する。
【００８１】
【数１７】
2004164593.tif 000019
【００８２】
ただし
【００８３】
【数１８】
2004164593.tif 000020
【００８４】
回転行列Ｒ（θ）は固有ベクトルを含み、スケーリング行列ΛはＭｋの固有値の平方根を含む。次の線形関係により、ｙＴｙ＝ｕＴＭｋ−１ｕが得られる。
【００８５】
【数１９】
2004164593.tif 000021
【００８６】
そして、ＧＭｋを次のように書き直すことができる。
【００８７】
【数２０】
2004164593.tif 000022
【００８８】
式（１３）は、ｙにおける単位ガウシアンを表し、これが図８Ｂに示すように式（１２）を用いて楕円ガウシアンリサンプリングフィルタに写像される。本発明のアルファテクスチャは単位ガウシアンをエンコードしているため、式（１２）を用いて単位四辺形を回転およびスケーリングした後、変形された四辺形にアルファテクスチャを適用することにより、楕円リサンプリングフィルタがテクスチャ化平行四辺形として得られる。
【００８９】
ガウシアンリサンプリングフィルタは、理論的には無限の対応を有するが、実際には、限られた範囲の指数Ｂ（ｙ）＝（１／２）ｙＴｙに対してのみ求められる。したがって、Ｂ（ｙ）≦ｃとなるようなカットオフ半径ｃを選択する。ただし通常の選択はｃ＝１である。したがって、アルファテクスチャは実際には次のドメインで単位ガウシアンをエンコードする。
【００９０】
【数２１】
2004164593.tif 000023
【００９１】
各頂点ｖは、変形された四辺形の頂点位置をエンコードしテクスチャマッピングを実行するために、テクスチャ座標｛（０，０），（０，１），（１，１），（１，０）｝を有する。与えられた頂点テクスチャ座標ｖ＝（ｖ０，ｖ１）に対して、われわれは、図９に示すようにカメラ空間位置ｐｃｕを求めた。
【００９２】
まず、次のように、カットオフ半径ｃに従ってテクスチャ座標ｖをスケーリングすることにより、テクスチャ座標ｖを単位ガウシアンのドメイン内の座標ｙに写像する必要がある。
【００９３】
【数２２】
2004164593.tif 000024
【００９４】
次に、式（１２）を用いてテクスチャ化四辺形を変形することにより、局所サーフェスパラメータ表示の座標ｕが得られる。式（９）により、最終的にカメラ空間内の平行四辺形の頂点位置ｐｃｕを求める。
【００９５】
最適なテクスチャサイズの決定
アルファテクスチャの８ビットの精度を最大限に利用するため、各テクセルにおいて式（１３）からの非定数部分、すなわちｇ（ｙ）＝ｅａ１、（ただしａ１＝−１／２ｙＴｙ）をエンコードする。したがって、関数値域［０、・・・、１］はすべてのテクセル値の全値域［０、・・・、２５５］に写像される。
【００９６】
テクスチャサイズが大きくなると２Ｄガウシアン関数の離散表現の精度は増大するが、８ビットへの関数値の量子化は高解像度アルファテクスチャにおける冗長性につながる。というのは、近くのテクセルが常に同じ量子化値に写像される可能性があるからである。
【００９７】
本発明は、解像度ｌｅｎ×ｌｅｎの正方形テクスチャを使用する。単位ガウシアン関数は回転不変であるため、ｇ（ｙ）を極座標でｇ′（ｒ）＝ｅａ２、（ただしａ２＝−１／２ｒ２）と表すことができる。テクセルあたり８ビットを最大限に利用するためには、すべてのｒ∈［０，√（２ｃ）］に対して次の条件が満たされるべきである。
【００９８】
【数２３】
2004164593.tif 000025
【００９９】
これから、次式が従う。
【０１００】
【数２４】
2004164593.tif 000026
【０１０１】
最適なテクスチャ解像度は、上記の条件を満たすｌｅｎの最小値に対応する。典型的な選択ｃ＝１の場合、ｌｅｎ＝４３８と求められる。
【０１０２】
実施態様
プログラマブルシェーダの計算
本発明のハードウェア高速化サーフェススプラッティング方法は、プログラマブルな頂点およびピクセルシェーダを用いて実施される。プログラマブルシェーダは、効率的なＧＰＵレベルの計算を提供する。Lindholm著「A User-Programmable Vertex Engine」SIGGRAPH 2001 Proceedings, pages 149-158, 2001を参照されたい。
【０１０３】
頂点シェーダの計算
第１レンダリングパスの間に、カメラ空間における視線に沿った奥行きオフセットが、頂点シェーダを用いて求められる。第２レンダリングパスにおいて、ポイントポリゴンの頂点位置もまた頂点シェーダにより求められる。頂点シェーダの命令セットは単純であるため、式（１１）の対称行列分解の実施は注意深い設計を必要とする。本発明は、２つの最も強力なシェーダ命令、すなわち逆数平方根（ＲＳＱ）および逆数（ＲＣＰ）を最大限に利用する。これらの計算の詳細は付録Ａで説明する。
【０１０４】
式（１３）の定数部分１／（２π・ｒ０・ｒ１）は、拡散色レジスタのアルファチャネルに出力される。このようにして、それは後でピクセルシェーダによりアクセスされることが可能となる。頂点シェーダは新しい頂点の生成をサポートしないため、同じ頂点ごとの計算をそれぞれの四辺形について４回実行する必要がある。
【０１０５】
ピクセルシェーダの計算
式（２）のｗｋρｋ（ｘ）の決定は、ピクセルシェーダのフラグメントごとの処理を用いて実行される。色ｗｒｋ、ｗｇｋ、ｗｂｋは、拡散色に対する入力レジスタの赤、緑、および青チャネルから取得される。テクセルアルファ値に定数１／（２π・ｒ０・ｒ１）、（これはアルファチャネルの拡散色レジスタに記憶されている）、を乗じることによりρｋ（ｘ）が得られる。最後に、式（２）のＥＷＡスプラットの累算が、加算アルファ混合により実行される。
【０１０６】
階層的レンダリング
本発明の好ましい実施形態では、階層的レンダリングのためにポイントベースの階層化奥行きキューブ（ＬＤＣ）ツリーを使用する。しかし、バウンディング球面階層のような他の階層的データ構造も使用可能である。
【０１０７】
ＬＤＣツリーを最低解像度ブロックから最高解像度ブロックまでトラバースする間に、ブロックの視錐台カリング、および可視円錐を用いた背面カリングを実行する。投影されるべき適当な８進木レベルを選択するため、ブロックバウンディングボックスワーピングを実行する。これにより、ピクセルごとに投影されるポイントの数を推定することができ、プログレッシブレンダリングが容易になる。
【０１０８】
効率的なハードウェア高速化のために、複数のＬＤＣツリーブロックのポイントがともにいくつかの大きい頂点バッファに記憶される。これは、レンダリング中の頂点バッファの切り替えを最小化し、性能を向上させる。頂点バッファは、グラフィクスカードのローカルメモリまたは加速グラフィクスポート（ＡＧＰ）メモリに割り当てられる。それらのサイズは、グラフィクスレンダリングエンジンのために最適になるように、かつ性能を最大化するように選択される。ＬＤＣツリー内のブロックの頂点データにアクセスするため、対応する頂点バッファＩＤおよびその頂点データの開始位置を頂点バッファに記憶する。
【０１０９】
前処理
ポイントベースのモデルの不規則なサンプリングおよびガウシアンカーネルの打ち切りにより、オブジェクト空間における基底関数ｒｋは一般に均一の分割を形成しない。像空間におけるリサンプリングカーネルも同様である。均一の分割を強制するためには、スプラッティング後にフレームバッファ内でピクセルごとの正規化を実行することがある。しかし、このような後処理演算は現在のグラフィクスハードウェアによってサポートされていない。さらに、ピクセルごとの正規化のためにレンダリング中にフレームバッファを直接ロックしアクセスすることは、レンダリング速度を遅くする。しかし正規化がなければ、最終像の明るさは累算されるフィルタ重みとともに変動し、可視アーティファクトにつながる。この問題点を解決するため、本発明は前処理正規化ステップを提供する。
【０１１０】
ポイント正規化
式（１）の基底関数ｒｋがいたるところで１まで足し上げられれば、ローパスフィルタの適用は依然として、像空間におけるリサンプリングフィルタが均一の分割を形成することを保証する。その結果、本発明の前処理は、レンダリング中のプレフィルタリングステップを考慮せず、ビュー非依存プロセスとなる。オブジェクト空間における正規化されたビュー非依存テクスチャ関数は次のように書かれ得る。
【０１１１】
【数２５】
2004164593.tif 000027
【０１１２】
残念ながら、上記の有理基底関数ｒｋ（＾）は、閉じた形のリサンプリングフィルタの導出を無効にする。代わりに本発明は、各ポイントでの重みの和を用いて上記の公式を近似し、次式を得る。
【０１１３】
【数２６】
2004164593.tif 000028
【０１１４】
ただし
【０１１５】
【数２７】
2004164593.tif 000029
【０１１６】
ｓｋをポイントの正規化重みと呼ぶ。これは、以下で説明するビュー非依存プロセスにより獲得される。式（７）に基づいて、本発明のオブジェクト空間ＥＷＡリサンプリングフィルタを重みｓｋで調整し、次式を得る。
【０１１７】
【数２８】
2004164593.tif 000030
【０１１８】
これは、ポイントごとの正規化を有するオブジェクト空間ＥＷＡサーフェススプラッティングにより使用されるリサンプリングフィルタである。
【０１１９】
ポイント正規化重みの獲得
ポイントの正規化重みを獲得するため、まず、ポイントサンプリングされたモデルが本発明の２パス方法を用いてプレフィルタリングおよびポイントごとの正規化なしでレンダリングされる。次に、Ｚバッファおよびフレームバッファが、正規化重みを獲得するために読み戻される。その第３パスでは、ＬＤＣツリーをトラバースして、各ポリゴンの中心ポイントの奥行き値および像空間における投影位置を求める。
【０１２０】
Ｚバッファ情報に基づいて、可視ポイントが検出される。レンダリング後、各フレームバッファピクセルのアルファチャネルは、そのピクセルに投影されるすべてのＥＷＡスプラットからの累算された貢献の和Ｓを記憶している。したがって、可視ポイントの正規化重みはｓｋ＝１／Ｓとなる。あるビューから不可視のポイントに対する正規化重みを捕捉するためには、複数ビュー重み捕捉が適用される。これは自動的に、またはインタラクティブに実行可能である。
【０１２１】
自動捕捉の場合、バウンディング球面がポイントベースのモデルの周りに構成される。次に、ポイント重みが、球面のサーフェス上に一様分布する相異なるビューポイントから獲得される。インタラクティブ捕捉の場合、ユーザは手動で、獲得されるべきポイントモデルの部分を指定する。いずれの方法でも、同じポイントの正規化重みが複数回獲得され得る。ノイズを除くため、そのメジアン値を最終的な正規化重みとして選択する。
【０１２２】
ポイントごとの正規化は、正規化重みがポイントのポリゴンによりカバーされる小さい近傍内で同じであることを仮定している。ポイントごとに、ポイント四辺形の中心で捕捉される正規化重みが、レンダリング中にそのポリゴン頂点にコピーされる。しかし上記の仮定は、ポイントモデルのエッジでは正しくない。この場合には、ポイントポリゴンの各頂点に正規化重みを獲得する。したがって、エッジにおけるポイント四辺形は、各頂点に相異なる正規化重みを有する。
【０１２３】
獲得プロセスにおいて、ポイントベースのモデルの直接レンダリングは、相異なるスプラットからの貢献の累算が１より大きいようなフレームバッファピクセルのアルファチャネルにおいてオーバーフローを引き起こす可能性がある。この場合、ポイント正規化重みは、アルファチャネルにおけるクランプのために不正確に計算される。この問題点を解決するため、本発明は大域パラメータγを用いてオーバーフローを回避する。本発明の実施態様では、重み捕捉プロセスは次のオブジェクト空間テクスチャ関数を使用する。
【０１２４】
【数２９】
2004164593.tif 000031
【０１２５】
γを１より小さい適当な値に設定することにより、ピクセルにおけるスプラットの累算された貢献がクランプされるほど大きくなりすぎることはない。結果として、正規化重み捕捉中にレンダリングされる像は暗くなる。通常の選択はγ＝０．７３であり、これはほとんどのポイントモデルに対してうまく働く。正規化重みｓ′ｋ、および大域パラメータγに対して、最終的なポイント正規化重みはｓｋ＝ｓ′ｋγである。
【０１２６】
以上、本発明は、好ましい実施形態の例を用いて説明されたが、さまざまな他の適応および変更が、本発明の精神および範囲内でなされ得ることが理解されるべきである。したがって、本発明の真の精神および範囲内に入るすべてのそのような変形形態および変更形態を包含することが、併記の特許請求の範囲の目的である。
【０１２７】
付録Ａ：頂点シェーダ実施態様のための対称行列分解
本発明の頂点シェーダ実施態様のために以下の対称行列分解方法を選択する。Ｍｋは次のように書き換えられる。
【０１２８】
【数３０】
2004164593.tif 000032
【０１２９】
そして、次のように定義する。
【０１３０】
【数３１】
2004164593.tif 000033
【０１３１】
次の変数が、頂点シェーダ一時レジスタに記憶される。
【０１３２】
【数３２】
2004164593.tif 000034
【０１３３】
これらの一時変数により、スケーリング行列を次のように計算することができる。
【０１３４】
【数３３】
2004164593.tif 000035
【０１３５】
Ｒｏｔ（θ）もまた計算することができる。ｔ＝０の場合は次のようになる。
【０１３６】
【数３４】
2004164593.tif 000036
【０１３７】
ｔ≠０の場合は次のようになる。
【０１３８】
【数３５】
2004164593.tif 000037
【０１３９】
上記の公式における平方根演算および除算は、それぞれ頂点シェーダ命令「ＲＳＱ」および「ＲＣＰ」を用いて効率的に計算することができる。
【図面の簡単な説明】
【０１４０】
【図１】従来技術の３Ｄオブジェクト空間の局所パラメータ表示の図である。
【図２Ａ】オブジェクト空間と像すなわちスクリーン空間の間のリサンプリングフィルタの変換の図である。
【図２Ｂ】オブジェクト空間と像すなわちスクリーン空間の間のＥＷＡリサンプリングフィルタの変換の図である。
【図２Ｃ】チェッカーボードテクスチャのワーピングおよびリサンプリングの図である。
【図３】本発明によるレンダリング中の可視スプラッティングの図である。
【図４Ａ】従来技術のｚ軸に沿った奥行きオフセットの図である。
【図４Ｂ】本発明による視線に沿った奥行きオフセットおよび平行移動の図である。
【図５Ａ】図４Ａの奥行きオフセットにより生成される、従来技術の像である。
【図５Ｂ】図４Ｂの奥行きオフセットによる、オクルージョンのない像である。
【図６】本発明によるレンダリング中のテクスチャ化ポリゴンを用いたＥＷＡスプラッティングの流れ図である。
【図７】本発明によるオブジェクト空間ＥＷＡリサンプリングフィルタの決定を示す図である。
【図８Ａ】単位円再構成カーネルおよびワーピングされたローパスフィルタの図である。
【図８Ｂ】図８Ａのフィルタの単位円から楕円への写像の図である。
【図９】オブジェクト空間ＥＷＡリサンプリングフィルタを表現するテクスチャマッピングされたポリゴンを構成する図である。
【図１０】本発明によるポイントベースのグラフィクスモデルのためのハードウェア高速化レンダリングシステムおよび方法のブロック図である。
【図１】
2004164593.tif 000038
【図２Ａ】
2004164593.tif 000039
【図２Ｂ】
2004164593.tif 000040
【図２Ｃ】
2004164593.tif 000041
【図３】
2004164593.tif 000042
【図４Ａ】
2004164593.tif 000043
【図４Ｂ】
2004164593.tif 000044
【図５Ａ】
2004164593.tif 000045
【図５Ｂ】
2004164593.tif 000046
【図６】
2004164593.tif 000047
【図７】
2004164593.tif 000048
【図８Ａ】
2004164593.tif 000049
【図８Ｂ】
2004164593.tif 000050
【図９】
2004164593.tif 000051
【図１０】
2004164593.tif 000052
【外国語明細書】
2004164593.tif 000053
2004164593.tif 000054
2004164593.tif 000055
2004164593.tif 000056
2004164593.tif 000057
2004164593.tif 000058
2004164593.tif 000059
2004164593.tif 000060
2004164593.tif 000061
2004164593.tif 000062
2004164593.tif 000063
2004164593.tif 000064
2004164593.tif 000065
2004164593.tif 000066
2004164593.tif 000067
2004164593.tif 000068
2004164593.tif 000069
2004164593.tif 000070
2004164593.tif 000071
2004164593.tif 000072
2004164593.tif 000073
2004164593.tif 000074
2004164593.tif 000075
2004164593.tif 000076
2004164593.tif 000077
2004164593.tif 000078
2004164593.tif 000079
2004164593.tif 000080
2004164593.tif 000081
2004164593.tif 000082
2004164593.tif 000083
2004164593.tif 000084
2004164593.tif 000085
2004164593.tif 000086
2004164593.tif 000087
2004164593.tif 000088
2004164593.tif 000089
2004164593.tif 000090
2004164593.tif 000091
2004164593.tif 000092
2004164593.tif 000093
2004164593.tif 000094
2004164593.tif 000095