サーフェス法線ベクトルを求めるための装置又は方法
【課題】メモリ及びメモリ帯域幅の使用を最小にしながら高度な計算能力をもたらす方法で再帰細分割を使用して、パラメトリックモデリングデータをポリゴンベースデータに変換することを目的とする。
【解決手段】システムによってシェーディングされることになるオブジェクトのモデリングに使用されるサーフェスパッチの頂点に対するサーフェス法線ベクトルを求めるための装置を備える3次元グラフィック処理において、各々がコーナー頂点を有する複数のサブパッチを生成するために前記パッチを細分割する手段と、頂点に対するサーフェス法線を導出するために必要とされる制御ポイントの位置を導出する手段と、前記制御ポイントの位置から頂点における複数の候補正接ベクトルを導出する手段と、前記候補正接ベクトルからサーフェス法線を導出する手段とを備える。
【解決手段】システムによってシェーディングされることになるオブジェクトのモデリングに使用されるサーフェスパッチの頂点に対するサーフェス法線ベクトルを求めるための装置を備える3次元グラフィック処理において、各々がコーナー頂点を有する複数のサブパッチを生成するために前記パッチを細分割する手段と、頂点に対するサーフェス法線を導出するために必要とされる制御ポイントの位置を導出する手段と、前記制御ポイントの位置から頂点における複数の候補正接ベクトルを導出する手段と、前記候補正接ベクトルからサーフェス法線を導出する手段とを備える。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、パラメトリックモデリングユニット及びポリゴンベースレンダリングシステムを備える3次元グラフィックシステムで使用するためのインターフェースに関する。
【背景技術】
【0002】
従来の3次元レンダリングシステムは、ポリゴン(通常は三角形)のメッシュを使用してシーン内のオブジェクトをモデリングする。三角形は、形状が単純であり、従って、表示用画像を生成するために変換、ライティング、テクスチャリング、及びラスタライゼーションなどの演算を実行するのが比較的容易である利点がある。
【0003】
ポリゴンメッシュを使用してオブジェクトをモデリングする既知の別の方法は、オブジェクトを領域にセグメント化して、モデリングされるオブジェクトの異なる領域に多数の湾曲した高次サーフェス(多くの場合パッチと呼ばれる)を適合させる。これらのパッチは一般に、制御ポイントのグリッドによって規定されたサーフェス形状を有するパラメトリックサーフェスとして定義される。高次サーフェスを用いる利点は、一般的に、特定のモデルを表示するために必要としているデータ量が、相当するポリゴンメッシュと比較して制御ポイントの集合の方がはるかに少ないという点である。また一般的に、高次サーフェスは、形状が変化するオブジェクトをアニメ化する際の操作が比較的簡単である。高次サーフェスを使用するモデリングの主な欠点は、レンダリングシステムのラスタライゼーション段階で、複雑さが付加的に導入されることである。
【0004】
また、ラスタライゼーションなどの処理段階を実行する前に、モデリング段階用に高次サーフェスを使用すること、及びサーフェスを一連のテセレーション三角形に変換することが知られている。この組み合わされた方法は、ラスタライゼーション段階に複雑さを付加することなく湾曲サーフェスを用いることができる利点が得られるが、サーフェスパッチデータを処理してポリゴンベースデータを形成するために好適なインターフェースを必要とする。湾曲平面を一連のポリゴンに変換するテセレーション過程では、2つの方法が通常良く使用され、すなわち、前方差分又は再帰細分割のいずれかである。本発明は再帰細分割法から導出される。
【0005】
組み合わされた3次元グラフィックシステムのパラメトリックモデリング段階(すなわち、後のレンダリング段階に対してポリゴンを生成するためにテセレーション段階を組み合わせたもの)では、複数の湾曲サーフェスのパッチをオブジェクトのサーフェスに適合させてオブジェクトの領域を定義する。このようなパッチの作用を定義するための、これらの定義する制御ポイントに対する幾つかの異なる規格が知られている。このような規格の1つはベジェパッチであり、例えば、Watt & Wattによる「Advanced Animation and Rendering Techniques」pp66−68、又はForey Van Damらによる「Computer Graphics Principles and Practice」pp471−530を参照されたい。また、1つのフォーマットのパッチに対応した制御ポイントを異なるパッチ形式に対応した新しい位置に、最終サーフェスが等しくなるように変換する方法も知られている。これらのパッチは双3次数である場合が多い。
【0006】
共通のパラメトリックパッチには要に2つのバリエーションがある。第1のバリエーションは「標準の」mpm有理サーフェスパッチ群であり、一方、第2のバリエーションは有理パッチの拡張集合である。有理パッチは、特定のモデリングがより単純な非有理的変化において利点を有しているといえるが、幾つかの点では処理が幾分複雑になる可能性がある。両方のタイプのパッチは前述の2つの引用文献で十分に説明されるが、しかしながら、本実施形態の説明を簡略化するために、次の要約が示される。非有理的パラメトリックサーフェスに対して、3次元位置は以下のように記述することができる。
ここで、x(s,t)、y(s,t)、及びz(s,t)の各々は、同次数のスカラパラメータの多項式であり、0≦s,t≦1である。双三次(すなわち2つの3次式の積)のベジェサーフェスの場合、多項式の次数は6である。ベジェ方程式とサーフェスの制御ポイントの各x、y、z成分とがサーフェスの形状を定義する。
【0007】
非有理的サーフェスは、制御ポイントの各々に対応した正の値「w」をさらに有する第4の多項式w(s,t)を導入することによって定義を拡張する。この場合、サーフェス位置は次のように定義される。
【0008】
また、一般によく使用されている種類のパラメトリックサーフェスパッチが行列形式で表現可能であることは、当該技術分野ではよく知られている(前述の引用を参照)。例えば、双三次ベジェパッチ
は、次のように表すことができる。
ここでQはスカラー定数行列、Pはサーフェスに対する制御ポイントの行列である。
【0009】
PはPSTとして番号付けられる点に留意されたい。
【0010】
再帰細分割手法によるパッチのテセレーション三角形への変換は、最初に各パッチをその2つのパラメータ次元(すなわちs又はt)のいずれか1つにわたって2つのサブパッチに分割することよって達成される。これは図1a及び1bに示され、ここでは制御ポイントを有するパッチがパラメータ空間に表現されている。サブパッチの各々は、的確な細分割レベルが達成されるまでさらに細分割される。これが達成されると、結果として得られるサブパッチはそれぞれ同一平面上にない四辺形として扱われ、三角形の規定のパターンが、サブパッチ、計算された三角形の頂点、及び出力された三角形に重畳される。
【0011】
図2は、3つのレベルの細分割が適用された、細分割によるパッチの概念的処理を示す概略図である。図2から、処理は、オリジナルパッチ、すなわち「ルート」パッチから中間レベルのパッチを介して、「リーフ」パッチと呼ばれるエンドポイントパッチまで進む2分木の形態をとることが分かる。各リーフパッチは、レンダリングのラスタライゼーション段階のために必要とされる、テセレーション三角形を定義する頂点を生成するために使用される。
【0012】
再帰細分割の既知のシステムにおいて、テセレーションは、各段階に対して多数の計算が必要とされるので従来からCPU上で実行される。これに伴う一連の計算を検討すると、CPU使用時には、リーフパッチに対する多くのパスに関して同じ中間結果が使用されるので、この中間結果をスタック上に格納することが効率的であることが分かる。従って、スタックを使用することにより、実行される計算の数が最小となる。ハードウェアの実装の面からすると、内部(すなわちオンチップの)記憶装置がコスト高であること、及び外部に格納された多大な量のデータを検索することがシステム性能の面でボトルネックとなる可能性があるということは実際的ではないということに留意されたい。
【先行技術文献】
【非特許文献】
【0013】
【非特許文献1】Watt & Wattによる「Advanced Animation and Rendering Techniques」pp66−68
【非特許文献2】Forey Van Damらによる「Computer Graphics Principles and Practice」pp471−530
【非特許文献3】Clarkによる「A Fast Scan Line Algorithm for Rendering Parametric Surfaces」、Computer Graphics 13(2)、289−99
【非特許文献4】Watt & Watt、Forley他、及びFakinによる「Curves and Surfaces for GAGD. A Practical Guide, 4th Edition, Academic Press, ISBN−0−12−249054−1, pp244−247
【非特許文献5】Watt & Wattの「Advanced Animation and Rendering Techniques. Theory and Practice」, ACM Press. ISBN 0−201−54412−1
【発明の概要】
【課題を解決するための手段】
【0014】
本発明の第1の態様は、これらの問題を改善することを目的としている。これは、メモリ及びメモリ帯域幅の使用を最小にしながら高度な計算能力をもたらす方法で再帰細分割を使用して、パラメトリックモデリングデータをポリゴンベースデータに変換するためのインターフェースを提供する。
本発明の第1の態様によれば、請求項12によるインターフェースが提供される。本発明の第1の態様の好適な特徴は、従属請求項13から16で定義される。
【0015】
また、請求項16により、パラメトリックモデリングユニットとポリゴンベースレンダリングシステムとの間でインターフェースをとる方法が提供される。好適な方法の各段階は、従属請求項16から19で定義される。
【0016】
組み合わされたグラフィックシステムにおいて、パラメトリックモデリングユニットとポリゴンベースのデータとの間でインターフェースをとるときに発生する第2の問題は、モデリングされるオブジェクトの隣接する領域を示す第1と第2のパッチにおいて、第1のパッチに関係するパラメータデータと第2のパッチに関係するパラメータデータとを変換するために、細分割の異なるレベルが要求される場合があることである。高度に湾曲したサーフェスを定義するパッチは、パラメトリックモデリングの利点が失われることがない場合には、パラメータデータをポリゴンベースのデータに変換するときに、平坦なサーフェスを示すパッチよりも高度に細分割されなければならない。隣接するパッチの変換が同じレベルの細分割を各パッチに適用するように制約されない場合には、モデリングされたオブジェクトにクラックが生じる恐れがあり、これは細分割のより高度なレベルのサーフェスが余分なサンプル点を有しており、要するに形状が僅かに異なることに起因する。クラックの問題は図4に示される。
【0017】
クラックの問題に対する1つの解決方法は、すべてのパッチに対して同じレベルの細分割を使用ことである。しかしながら、これは、幾つかのパッチがより小さく分割されたレベルで適切にテセレーションされるときには過度に細分割される結果となり、適切な結果をもたらすのに必要な領域に対しての処理になっていない。
【0018】
別の解決方法は、サーフェスを適切に表すのに十分な細分割レベルまで各パッチを処理し、次いで、細分割のレベルが異なる隣接するサーフェスパッチ間にいわゆる「ステッチメッシュ」を挿入することである。従って、図5aに示されるように、ステッチメッシュは可能性のある任意のクラックをカバーする。図において、2つの隣接パッチは異なるレベルまで細分割されており、すなわち一方は2×4のサブパッチを使用し、他方は細分割されず、すなわち単一の四辺形で示される。2×4パッチ上に「隣接する」輪郭は頂点A、B、C、D、及びEから成り、一方、1×1細分割に相当するものはエッジAEから成る。サーフェスにギャップが出現するのを回避するために、三角形ABC、ACE、及びCDEがさらに生成される。
【0019】
残念なことに、このようなメッシュの接続はサーフェス方向に急激な変化が生じる可能性がある。隣接するパッチのエッジを共にステッチすることは、計算集約的であり、且つ細分割レベルが変化するときにステッチメッシュの再生成が必要となることは同様に理解される。
【0020】
Clarkは、「A Fast Scan Line Algorithm for Rendering Parametric Surfaces」、Computer Graphics 13(2)、289−99により、各パッチ内で細分割が異なるレベルであっても可能な別の技法を提案した。この方法の一部として、クラック問題が「解決」されなければならなかった。Clarkの解決方法は、より高い細分割の領域のエッジがより低い細分割の領域に適合する場合に、これを意図的に「平坦化する」ことである。これは図5bに示される。高い細分割領域と低い細分割領域間で「共有された」境界は、低細分割領域の境界に数学的に適合するように高細分割領域上で「平坦化」されていた。これを図5aの方法と比較すると、頂点B、C、及びDが線AE上にあることが分かる。
【0021】
この手法は数式的には正しいが、僅かな欠点がある。コンピュータグラフィックスハードウエアの精度は限界があり、正確なポリゴン頂点位置を表示することができない。従って、共有境界上の平坦化された頂点を正しく配置することが不可能である場合が多い。これは、当該技術分野でよく知られている「T−ジョイント」によって引き起こされる問題につながる。これは図5cに示されており、ここでは不正確さによって極めて狭いギャップが現われる。このギャップは極めて小さいのが典型的であるが、それでも尚、他の場合では、隣接する三角形のエッジに沿って位置するセミランダムピクセルホールの集合としてレンダリングされた画像において見ることができる。画像がアニメ化されると、これらは断続して「輝き」、容易に見られるようになる。
【0022】
これらのT−ジョイントは、ステッチポリゴンを再度導入することによって固定することができることは理解されるが、しかしながらこのようなポリゴンは極めて小さく、ポリゴンのレンダリングに伴う「設定」コストがより有意に大きなサイズのポリゴンに対して良好に役立つことから、これはむしろ非効率な方法である。
【0023】
さらに別の手法は、Pixar’s Rendermanシステムで使用されるように、結果として得られるポリゴンが画素よりも小さくなるまでパッチを細分割することである。そのため、これらのマイクロポリゴンは「点」として取り扱うことができる。この方法は膨大な量のデータを生成し、リアルタイムのレンダリングには実際には適していない。
【0024】
従って、現在の技術におけるクラックのない細分割のための選択肢としては、以下のように要約することができる。
(1)モデルのすべてのパッチを同一の細分割レベルまで細分割する。これは単純であるがリソースを浪費する。
(2)各パッチ内で一様に細分割し、次いでステッチポリゴンを使用して非一様に分割されたパッチ間のギャップを隠す。これは、ステッチポリゴンが追加コストとなり、(図5aに見られるように)方向の急激な変化を誘導する可能性があるので理想的ではない。
(3)Clarkの方法を使用することにより、パッチ内でも非一様な細分割が可能となるが、T−ジョイント問題を欠点として有する。
(4)Clarkの方法にさらなるステッチポリゴンを適用する。
(5)メッシュをマイクロポリゴンに細分割する。
【0025】
パッチのエッジに沿って非一様な細分割をできるようにすることは、結合部にクラックが発生することなく異なるパッチを結合することができるので望ましいことが理解される。また、Clarkの方法を用いて可能なように、パッチ内で非一様な細分割をできるようにすることは、パッチの1つの側面上の高細分割のエッジから反対側面上の低細分割のエッジまでの漸次的移行が、パッチが内部的に一様に細分割されるシステムにおけるよりも少ないポリゴンしか必要とせず、より効率的なポリゴンの使用を可能にするので望ましいことである。また、内部的又は境界上でステッチポリゴンを必要としないシステム、及び同様にT−ジョイントを導入しないシステムは非常に望ましいことが理解される。
【0026】
従って、本発明は第2の態様において、パッチ内でパッチデータを異なる細分割方向に異なる細分割レベルまで処理し、Clarkの方法による問題を回避する、「不規則なパッチ」の処理をサポートする。異なる数の頂点を「不規則なパッチ」の異なるエッジ上に形成することによって、オブジェクトの隣接領域をモデリングするテセレーションパッチ間のクラックを防止するステッチメッシュが不必要となる。不規則なテセレーションに対応することにより、隣接するパッチの隣接エッジが、残りのエッジについてパッチの細分割のレベルに影響を与えることなく、同じ数のポリゴンの頂点を保持できるようになる。2つの均等に細分割されたパッチの境界を示す実施例が図13bに与えられる。
【0027】
本発明の第2の態様によれば、請求項8によるインターフェースが提供される。本発明の第2の態様の好適な特徴は、従属請求項9に詳細に記載される。また、請求項10により、パラメトリックモデリングユニットとポリゴンベースレンダリングシステムとの間でインターフェースをとる方法が提供される。
【0028】
細分割の不規則なレベルは、最終のサブパッチから四辺形の各エッジに沿って適切な数の頂点を有するメッシュを自動的に生成することによって対応される。これによりクラックの発生なしにポリゴン化されたパッチを簡単に結合することが可能になる。
【0029】
既知のインターフェース技法に関する別の問題は、いわゆるポリゴンポッピングである。異なるパッチのインターフェースにおいて、すべてのパッチの各エッジは自己細分割制御値を有すると仮定する。細分割変化の手段としてオブジェクトの平滑なアニメ化を可能にするために、これらの値は、浮動小数点を取るか、又は少なくとも小数点部分を包含すると仮定する。ポリゴンポッピングは、テセレーションポリゴンにおいて急激に点が移動するときの説明に使用される用語であり、細分割制御値の小さな小数部分の変化により処理の追加段階(パッチの追加の2元細分割)を実行させる場合に生じる可能性がある。エッジの細分割制御値は任意の値を取ることができるが、好適なテセレーション手法は、次の直近の2の累乗にまで2元パッチ細分割を実行するように制約される。従って、細分割比率が僅かでも増加すると、細分割の実際のレベルが大幅に増加する可能性がある。例えば、各エッジに対して規定された細分割の値が4の場合、細分割は16のリーフパッチをもたらす。各エッジに対して規定された細分割の値が4から4.1に増加すると、次のより大きな2の累乗は8であり、結果として得られる細分割は64のリーフパッチを生じる。従って、多くの新しい三角形がオブジェクト内に現われる。このプロセスが適切に制御されない場合には、図3に示されるように、アニメーションに望ましくない視覚的な影響が引き起こされる。
【0030】
図3aにおいて、湾曲サーフェスは既に2つの四辺形領域に細分割されている。従って、パッチの「最前部」の湾曲エッジは線分AB及びBCによって近似される。図3bでは、前エッジに沿って2つの新しいポイントD及びEが生成されるように、細分割のレベルは増加(1次元だけにおいて)されている。従って、パッチの前エッジは線分AD、DB、BE、及びECによって表される。ABCからADBECへの形状の変化は比較的大きく、新しいポイントD及びEはジャンプ、又は「ポップ」して見えるようになったと言うことができる。これは、位置E’からジャンプして出現したポイントEを有するこの実施例において最も容易に分かる。
【0031】
本発明は第3の態様において、ポリゴンポッピングに関連する視覚の問題を改善することを意図している。
【0032】
本発明による第3の態様では、請求項1によるインターフェースが提供される。本発明の第3の態様の好適な特徴は、従属請求項2及び3で定められる。また、請求項4により、パラメトリックモデリングユニットとポリゴンベースレンダリングシステムとの間でインターフェースをとる方法が提供される。好適な方法の段階は従属請求項5から7で定められる。
【0033】
本発明は第3の態様において、高次サーフェスを使用するモデルの詳細レベルを変えるときに、よりスムーズに見えるアニメ化された画像を生成する。これは、最終的にテセレーションリーフパッチの線形細分割と3次細分割の間で重み付けされた混合を好適に使用する。この混合に対する重み付け因子は、必要とされる細分割値と次のより小さな2の累乗との比率によって好適に決定される。
【0034】
ライティング及びシェーディング演算が3次元グラフィックのサーフェスに適用されるときには、通常は1つの点におけるサーフェスの法線、すなわちその位置でのサーフェスに垂直なベクトルが、既知であることが要件である。テセレーションされたサーフェスをシェーディングするために、サーフェス法線は計算された三角形の頂点のみにおいて計算される必要がある。
【0035】
Watt & Watt、Forley他、及びFakinによる「Curves and Surfaces for GAGD. A Practical Guide, 4th Edition, Academic Press, ISBN−0−12−249054−1, pp244−247」で述べられているように、1つの点で法線を得るための標準的な方法は、その点で2つの(1次独立の)接線ベクトルを計算して、これらの外積を取ることである。必要であれば、その結果を後に、s及びtのパラメータに関係するサーフェスの1次偏導関数を計算するユニットに変換することができる。
【0036】
普遍性を損なうこと無く、サーフェス法線の計算がパッチのコーナー点においてのみ行われるように制限した場合、非有理的ベジェサーフェスは、コーナーの制御点とその2つの直近のエッジ制御点との間の差が、それぞれの1次偏導関数のスカラー積であるという極めて好都合な特性を有することになる。これは図19に示され、ここで「正接S」はコーナー点P00とその隣接する制御点P10間の差と一致し、一方、「正接T」はコーナーと制御点P01間の差と一致する。
【0037】
幾つかのシステムは、この事実(繰り返される細分割に加えて)を使用してパッチ上の種々の位置において法線を計算する。
【0038】
残念なことにこの計算は成功しない場合が多い。正接ベクトルが1次独立で、ベジェパッチの制御点が、特にこれらの隣接するコーナー点と一致していることが要求される場合がある。これは1次偏導関数の1つ又は両方が0とすることができ、不正確な法線が得られることを意味する。このようなサーフェスパッチは多くの場合「縮退」と呼ばれ、幾つかのシステムはこれらを「不正」であると見なす。これは、このような制御点でのサーフェス構成が完全に有効である形状をモデリングする必要性が高く、モデリングソフトウエアパッケージによって容易に生成することができるので、むしろ残念なことである。
【0039】
より実用的な既知の1つの解決方法は、s及びt方向のパラメータにおいてコーナーから僅かにオフセットした2つのポイントでサーフェスの数値を求めることである。従って、2つの接線ベクトルはこれらの計算されたポイントとパッチコーナーとの間の差を取ることによって近似される。これは通常は適切な結果を与えるが、追加の計算の観点から言えばコスト高である。
【0040】
接線ベクトルの定義を再度参照して微積分計算を適用すると、1次が0である場合、2次偏導関数を用いることができるのが分かる。Watt & Wattの「Advanced Animation and Rendering Techniques. Theory and Practice」, ACM Press. ISBN 0−201−54412−1は、同様に非有理的ベジェパッチに関して、この状況におけるコーナー制御点と後続の2次偏導関数の積との間の差を論証している。図19を再度参照すると、例えばP01とP00が一致する場合、P02とP00の差は潜在的正接をもたらす。同様にこれも0である場合、P03との差を取ることによって、3次偏導関数に対して同様のプロセスを用いることができる。
【0041】
残念なことに、この方法でも尚成功しない可能性がある。パッチのエッジに沿ったすべての点は一致する場合があり、パッチが球体の8分空間をモデリングしている際に起きるように、パッチは「三角形」になっている。この特定の状況では、2次偏導関数を選択することができる。Farinはまた、さらにより微妙な問題、すなわちs及びt方向に0でない偏導関数が存在できるが、幾つかの状況においてこれらが平行とすることができることを述べている。その結果、外積は0を与え、従って無効な法線である。Farinは1つの特定の場合に対する解決方法を述べている。
【0042】
本発明は第4の態様において、有理的ベジェサーフェスに対する法線をロバストであるばかりでなく効率よくサーフェス法線を計算する計算方法を示している。
【図面の簡単な説明】
【0043】
【図1a】上半分のn番目のレベルのサブパッチと下半分のn番目のレベルのサブパッチとを形成するためのt方向のn−1番目のレベルのパッチの細分割を示す概略図である(理解しやすいように、これらは図中物理的に分けて示されている)。
【図1b】左半分のn番目のレベルのサブパッチと右半分のn番目のレベルのサブパッチとを形成するためのs方向のn−1番目のレベルのパッチの細分割を示す概略図である。
【図2】各々の段階におけるS又はTの細分割方向の選択肢が供給される細分割のパラメータによって決定される、中間パッチと最終的に8つのリーフサブパッチに分割されるパッチのためのリーフパッチとに対するルートパッチの細分割の可能性のある選択肢を示す概略線図である。
【図3a】「前エッジ」に沿って頂点ABCを生成する、第1のテセレーションプロセスによって近似された湾曲サーフェスを示す線図である。
【図3b】ポリゴンポッピングを生じるテセレーションプロセス間の比較的大きな形状の変化を示す、「前エッジ」に沿って頂点ABCDEを生成する第2のテセレーションプロセスによって近似された同じサーフェスを示す図である。
【図4】隣接するパッチが別々の細分割比率に細分割されるときのクラックの問題を示す図である。
【図5a】クラックの問題を克服するための既知のポリゴン生成システムによって使用されるステッチメッシュである。
【図5b】クラックの問題を解消するためのClarkの手法を示す。
【図5c】コンピュータグラフィックにおける「T−継ぎ手」の問題を示す。
【図6】インターフェースの好適な実施形態を示す概略図である。
【図7】下位計算ユニットの計算段階を示す概略図である。
【図8a】図7の計算を使用したt方向の上半分の細分割に関するパッチデータの行及び列の索引付けを示す。
【図8b】図7の計算を使用したt方向の下半分の細分割に関するパッチデータの行及び列の索引付けを示す。
【図8c】図7の計算を使用したS方向の左半分の細分割に関するパッチデータの行及び列の索引付けを示す。
【図8d】図7の計算を使用したS方向の右半分の細分割に関するパッチデータの行及び列の索引付けを示す。
【図9】2段階細分割ユニットの概略図である。
【図10】制御ユニットの演算を示すフローチャートである。
【図11】好適なテセレーションパターンである。
【図12】別のテセレーションパターンである。
【図13a】右エッジの不規則リーフパッチのテセレーションパターンである。
【図13b】13aの不規則なパッチと高レベルの細分割パッチの結合を示す。
【図14】図13aの不規則パッチの追加の頂点を推定するための扇状パッチの生成を示す概略図である。
【図15】扇状パッチ処理中の制御ユニットの演算を示すフローチャートである。
【図16】リーフパッチの制御点P00、P30、及びP33と、テセレーション三角形の頂点V0、V2、V6、及びV4との間の対応を示す概略図である。
【図17】頂点V1、V3、V5、V7、及びV8の結合値の生成を示す概略図である。
【図18】異なるリーフパッチのための中心の頂点V8の計算でどの頂点が使用されるかに関する線図である。
【図19】非有理双三次ベジェパッチのコーナーにおける接線ベクトルの挙動の1つの実施例を示す。
【図20】9つの「テセレーション」頂点(すなわち図11に示されるような)においてサーフェス法線を構成するのに好適な制御点を生成するために(規則的な)リーフパッチに適用された追加の部分細分割段階を示す。
【図21】パッチの特定のコーナー点に対するサーフェス法線を生成するために本発明によって使用される有理双三次ベジェパッチの制御点のサブセットを示す。
【図22】aはテセレーションリーフパッチに対する9つの頂点法線を生成するため必要とされる制御点を生成するために取られる段階を説明する。bはこの法線生成プロセスの一部をさらに説明する。
【図23】有理ベジェパッチのコーナーで1つのパラメータ次元の候補接線ベクトルの導出で使用される段階/装置を説明する。
【図24】サーフェス法線を生成するためにパッチのコーナーにおいて3つの候補接線ベクトルを結合するために使用される段階/装置を説明する。
【発明を実施するための形態】
【0044】
本発明の実施形態を添付図面を参照してより詳細に説明する。
【0045】
本インターフェースは、パラメトリックモデリングユニット及びポリゴンベースのレンダリングシステムを使用した3次元グラフィックシステムでの使用を目的とするものであり、オブジェクトをモデリングするパラメトリックデータが、ポリゴンベースレンダリングシステムによって、該データを表示用に処理するために使用可能なフォーマットに変換されることができるようになる。
【0046】
図6はインターフェースのブロック図である。インターフェース10は、入力バッファ12、フォーマット変換器14、再帰バッファ16、細分割ユニット18、重み付けプロセッサ20、方向プロセッサ24、出力バッファ26、及び制御ユニット22を含む。
【0047】
パラメトリックモデリングユニットにおいて、パッチを用いてサーフェスを定義する。典型的な双三次パッチは、16個の制御点によって定義される。各制御点は、幾つかの要素(通常は(xyzw)位置、色、及びテクスチャマッピング情報を含む)を定義するN次元のベクトルである。典型的な3次元グラフィックシステムにおいては、各パッチのデータは制御点によってグループ化され、入力バッファ12を介してインターフェース10に入力されるのは、この制御点グループ化データである。細分割ユニットは、制御点ではなく要素によってデータをグループ化することを要求する。
【0048】
入力バッファ12は、制御点グループ化データを取り入れ、該データを細分割ユニット18によって要求される要素的なフォーマットに再配置して、これをフォーマット変換器に出力する。
【0049】
インターフェース10の細分割ユニットは、ベジェ双三次パッチとして知られる特別な標準のパッチを処理するように設計される。同様に、例えば、Catmull−Rom及びB−スプラインに基づく他のパッチのフォーマットも3次元モデリングで使用される。インターフェース10が他のパッチフォーマットを処理できるようにするために、フォーマット変換器14を設ける。入力バッファ12が出力する要素的データで表示されたパッチのフォーマットが決定される。データのフォーマットがベジェ双三次フォーマットではない場合には、フォーマット変換器14は、最適化された一連の行列乗算によりデータをベジェ双三次フォーマットに変換する。種々のパッチフォーマット間の変換方法は、3次元グラフィックの分野で公知であるので本明細書では説明しない。フォーマット変換器14は、変換アルゴリズムのライブラリを維持し、データに対して適切な変換アルゴリズムを適用して、ベジェ双三次フォーマットに変換する。
【0050】
再帰バッファ又はストア16は、2つのパッチ、すなわちルートパッチと中間パッチに対応するデータの記憶領域を与える。ルートパッチは各中間パッチに対する出発点であるので、細分割処理中に複数回アクセスする必要がある。中間パッチデータを再帰バッファ16内に格納すると、インターフェース内でのデータ転送が減少し、効率が改善されて処理時間が短縮される。再帰バッファ16のこの領域は中間結果用の作業領域を効果的に与える。
【0051】
要求レベルに対するパッチの細分割は、細分割ユニット18によって実行される。細分割ユニット18への入力は再帰バッファ16から供給される。細分割は4つのカテゴリ、すなわち、パッチの上半分を取り込むtの細分割、パッチの下半分を取り込むtの細分割、パッチの左半分を取り込むsの細分割、及びパッチの右半分を取り込むsの細分割に分けられる。
【0052】
ベジェパッチは16個の制御点を有し、制御点のデータは4×4行列で配列される。任意のカテゴリにおける第1レベルのパッチn−1から次のレベルのパッチnまでの細分割は、パッチデータに対して次の再帰方程式を適用することによって実現される。
ここで、Ai、Bi、Ci、及びDiは、細分割のカテゴリによる4×4制御点の行列の適切な要素を表す。要素の索引付けが制御される方法は、細分割の各カテゴリに関して以下で説明する。
【0053】
細分割の計算は、図7に示され且つ以下に説明されるように、演算をパイプライン形式にすることによって効率よく実行される。
【0054】
図7は下位計算ユニットを示す。下位計算ユニットに対する入力は、n−1番目レベルのパッチの4つの制御点値An-1、Bn-1、Cn-1、及びDn-1である。第1の計算段階は、並列に配置され各々が入力と第2の計算段階に結合された3つの加算器46、48、及び50を有する。加算器46の1つはまた第4の計算段階にも結合される。
【0055】
第2の計算段階は並列に配置された2つの加算器52及び54を含む。各加算器は、第1の計算段階の3つの加算器の2つの出力に結合される。1つの加算器52は第4の計算段階に直接結合される。加算器52及び54は両方とも第3の計算段階に結合される。
【0056】
第3の計算段階は、その入力として第2の計算段階の加算器52及び54の両方からの出力を取り込む単一の加算器56を含む。加算器56の出力は、第4の計算段階に結合される。
【0057】
第4の計算段階は、並列に配置された3つの除算器58、60、及び62を含み、これらはそれぞれ、加算器46の出力を2で除算し、加算器52の出力を4で除算し、加算器56の出力を8で除算する。
【0058】
下位計算ユニットが出力する出力は、n番目レベルのパッチ、すなわちAn=An-1の制御点の値であり、3つの除算器58、60、及び62の出力はそれぞれBn、Cn、及びDnである。
【0059】
パイプライン形式のシステムは、高速なシステムクロックを実現する。
【0060】
サブパッチにおける制御点値An、Bn、Cn、及びDnの計算は、細分されているパッチ内の対応する制御点値、An-1、Bn-1、Cn-1、及びDn-1からの一連の加算において下位計算ユニットにより実行される。計算の第1の段階は、該第1の段階における中間値P、Q、及びRの並列計算であり、ここで、
P=An-1+Bn-1
Q=Bn-1+Cn-1
R=Cn-1+Dn-1
である。
【0061】
第2の段階は、該第2の段階における中間値S及びTの並列計算であり、ここで、
S=P+Q
T=Q+R
である。
【0062】
第3の段階は、該第3の段階における中間値Uの計算であり、ここで、
U=S+T
である。
【0063】
第4の段階において、値V=P/2、W=S/4、及びX=U/8が並列計算され、値An=An-1、Bn=V、Cn=W、及びDn=Xが下位計算ユニットから出力される。
【0064】
各下位計算ユニットは、n番目レベルでのサブパッチ内の4つの新しい制御点の値を計算する。4つの新しい制御点の各セットの計算は、他の12個の制御点の計算とは独立している。このように、4つの下位計算ユニットを並列使用することによって、最小数のクロックサイクルでn番目レベルでのサブパッチの16個の新しい制御点を計算することが可能となり、高いスループットを達成することができる。4つの下位計算ユニットの出力は、出力マルチプレクサ(mux)44において組み立てられて、n番目レベルのサブパッチの制御点行列を生成する。
【0065】
下位計算ユニットは、細分割のどのカテゴリが実行されているかに応じて4×4の制御点行列の様々な要素上で動作することが要求される。しかしながら、細分割ユニットに入力及び出力マルチプレクサを組み込むことによって、4つの同一な細分割ユニットを使用して新しい制御点を計算することができる。入力及び出力マルチプレクサの機能について以下に説明する。
【0066】
<入力マルチプレクサ>
入力マルチプレクサの機能は、n−1番目レベルのパッチ制御点行列の行と列とを入れ替え、下位計算ユニットによって実行される細分割のカテゴリを制御できるようにすることである。
【0067】
t方向の細分割において、制御点行列の行はAからDまで索引付けられ、制御点行列の列は左から右に1から4まで索引付けられる。行における索引付けの方向は、上半分のパッチ又は下半分のパッチが生成されることになるかどうかによって決まる。上半分のパッチを生成するために、行は、行列の最上行としてAから始まって行列の最下行としてDで終了するように索引付けられる。このように、n番目レベルの上半分のサブパッチの制御点の最上行は、n−1番目レベルのパッチの制御点の最上行と同一である。n番目の上半分のサブパッチの残りの3つの行は、上の式1で定義されたn番目レベルのパッチの制御点の行に関係している。同様に、n番目レベルの下半分のサブパッチの制御点の最下行は、n−1番目レベルのサブパッチの制御点の最下行と同一であり、残りの行は式1と対応してn−1番目レベルの行列の行に関係する。
【0068】
図8a及び8bはそれぞれ、上半分のサブパッチを取り込むt方向の分割と、下半分のサブパッチを取り込むt方向の分割とを実行するための、n−1番目レベルのパッチの適切な索引付けを示す。このように、t方向の細分割から下半分を生成するためには、最初に行が反転されて、次に暫定的なデータを形成する上半分のサブパッチの生成に対して処理され、該データは次いで、必要とされるサブパッチデータを形成するように配列されなければならない。
【0069】
s方向の細分割においては、パッチの列はAからDに索引付けられ、行は上から下まで1から4に索引付けされる。列の索引付けの方向は、左のサブパッチ又は右のサブパッチのいずれかが生成されることになるかによって決まる。左半分のサブパッチを生成するためには、列はパッチの左側の列としてAから始まり、右側の列としてDで終わるように索引付けされる。従って、レベルの左半分のサブパッチの制御点の左側の列は、n−1番目レベルのパッチの制御点の左側の列と同一である。左半分のサブパッチの残り3つの列は、上の式1で定義されたようにn−1番目レベルのパッチの制御点の列に関係する。同様に、n番目レベルの右半分のサブパッチの制御点の右側の列は、n−1番目レベルのパッチの制御点の右側の列と同一であり、残りの列は式1と対応してn−1番目レベルのパッチの制御点の列に関係する。
【0070】
図8c及び8dは、左半分のサブパッチを取り込むs方向の分割と、右半分のサブパッチを取り込むs方向の分割とを実行するためのn−1番目レベルのパッチの適切な索引付けをそれぞれ示す。このように、s方向の細分割から左半分のサブパッチを生成するためには、最初にパッチの行と列を入れ替えて、再配置されたパッチを上半分のサブパッチの生成に対して処理することができる。同様にs方向の細分割から右半分のサブパッチを生成するためには、行を反転させて、次に行と列を入れ替える。t方向に分割された上半分のサブパッチの処理が実行され、結果として得られる制御点は出力マルチプレクサによって要求された右半分のサブパッチに対応するように再配置される。
【0071】
<出力マルチプレクサ>
出力マルチプレクサの機能は入力マルチプレクサの機能に類似している。該マルチプレクサは細分割のカテゴリに応じて、細分割ユニットによる暫定的なデータ出力を配置して、要求されたサブパッチ制御点行列を形成する。下位計算ユニットがt方向の上半分の細分割を実行するように設定されたと仮定すると、t方向の下半分の細分割とs方向の左及び右半分の細分割を生成するよう下位計算ユニットの出力を再配置する必要がある。出力マルチプレクサは下位計算ユニットの4つの出力を組み立てて単一の行列にし、入力マルチプレクサによって実行された再配置を反転させて、要求されたサブパッチ制御点行列を生成する。
【0072】
n番目レベルのサブパッチに対する要素的な制御データが、図7a、7b、7c、及び7dに示されるように細分割のカテゴリに従って適切な順序に組み立てられると、該データは、リーフパッチに関係する場合には重み付けプロセッサ20と方向プロセッサ24に出力され、或いは中間パッチに関係する場合には再帰バッファ16に戻される。
【0073】
インターフェースでは、図9に示されるように下位計算が実行される。この細分割のアーキテクチャの実行は、極めて効率的であることが分かっている。Watt & Wattで示された従来技術の方法はより多くの「計算」段階を必要とし、ハードウェア浮動小数点の実装の点で著しくコスト高になる可能性がある。細分割ユニット18は幾つかの段階を含む。各段階は1つのレベルの細分割を実行する。第2段階の細分割は、第1段階による処理の後に細分割の要求レベルが達成される場合にバイパスさせることができる。現在のところ好ましいとされる実施形態においては、2つの段階、すなわち第1の段階30と第2の段階32は、細分割ユニット18において実行される。2つの細分割段階を含むと、再帰バッファからの所定量のデータ帯域幅に対してシステムの原計算効率が向上するという利点がある。多くの段階は、最終のシステムにおいて要求されるサイズ/性能のトレードオフを与えるように変更することができる。各段階は、入力マルチプレクサ34、4つの下位計算プロセッサ36、38、40、42、及び出力マルチプレクサ44から成る。
【0074】
第1の段階では、パッチの要素のデータは再帰バッファ16から読み取られる。入力及び出力マルチプレクサ34及び44それぞれにより、要素の行列の行と列を再配置して実行される計算を制御することができるようになる。計算のオプションは以下の通りである。
s方向に細分割、左半分を出力,
s方向に細分割、右半分を出力,
t方向に細分割、上半分を出力,
t方向に細分割、下半分を出力,
バイパス
【0075】
入力マルチプレクサ34は、要求された細分割のカテゴリに応じて行列を再配置し、n−1番目レベルのパッチの4つの制御点を処理のために各下位計算ユニットに送る。各下位計算ユニットの出力はマルチプレクサ44に供給され、該マルチプレクサは下位計算ユニットの出力を組み立てて、要求された細分割のカテゴリに応じて必要とされたサブパッチに行列を再配置する。段階1の出力マルチプレクサ44からの出力は、段階2の入力マルチプレクサ34に対する入力として処理される。段階2の出力は、再帰バッファ16に送り返されるか、又はリーフパッチが達成された場合には次の計算段階に供給される。
【0076】
入力及び出力マルチプレクサを使用すると、下位計算ユニットの4つの別々のブロックの必要が無くなるので、湾曲サーフェス細分割システムの要素部品の数が最小になる。
【0077】
細分割ユニット18の演算は制御ユニット22から示される一連の命令によって制御される。制御ユニット22は、図10のフローチャートに示されるアルゴリズム上で動作する。制御ユニット22により、再帰バッファ16からルートパッチが取り込まれて、第1段階の入力マルチプレクサ34に送られる。
【0078】
パッチの4つのエッジに対応する4つのパッチの細分割レベルの割り当てが、ソフトウエア又はハードウェアのいずれかにおいて外部的に計算されていたと仮定する。
【0079】
制御ユニット22は、ルートパッチ制御行列の左エッジ及び右エッジの細分割値を調べることによって、t次元の細分割が必要とされるかどうかを判断する。左エッジ値及び右エッジ値のどちらも1.0と2.0の間の値にない場合は、t方向のパッチの細分割が必要とされる。左エッジ値及び右エッジ値は2で除算される。t方向に分割するコマンドは、制御ユニット22によって細分割ユニット18に送られ、これにより入力マルチプレクサによるデータの適切な再配置と、出力マルチプレクサによる暫定的なデータの配置とが行われる。t方向に分割されると、次に、上エッジ及び下エッジの新しい細分割値の計算が必要になる。上半分の細分割が実行される場合、制御行列の最上行は変化せず、上半分のサブパッチにおける最上部の値は、分割されていない行列から繰り越される。しかしながら、上半分の細分割は、分割されていない行列のものとは異なるサブパッチの最下行が得られる。従って最下部の値は更新されなければならない。新しい値は、分割されていない行列の上部値及び下部値の平均値又は好ましくは相乗平均値のいずれかとして計算される。相乗平均は、細分割のレベルをパッチ全体にわたってより有用に分布するので好ましい。下半分の細分割については、計算される必要があるのは細分割された行列の最上部の値であり、一方、最下エッジの値は分割されていない行列から繰り越される。最上エッジの値は上半分の細分割における最下エッジ部の値と同じ方法で計算される。
【0080】
制御ユニット22は、点の処理がs次元に進む終了条件に適合するまでt方向の細分割を継続する。パッチ全体のt方向のこれ以上の細分割が必要でないことを示す、左エッジ又は右エッジのいずれかの値が1.0と2.0の間にある時に終了条件は満たされる。しかしながら、結果としてのパッチが不規則な場合にはパッチの追加処理を必要とすることができる。不規則なパッチの処理は後で説明される。
【0081】
s方向の細分割が必要かどうかを判定するために試験される最上エッジ及び最下エッジの値を除いて、s方向の処理は同様にして進められる。新しい右エッジ及び左エッジの値が、左半分の細分割及び右半分の細分割のそれぞれに対して計算される。新しい右エッジ及び左エッジの値は、分割されていない行列の右エッジ及び左エッジの値の平均値又は好適には幾何平均値のいずれかとして計算される。s次元終了条件が満たされると、tが再チェックされて要求に合わせて処理が繰り替えされる。sの細分割に対する終了条件は、左エッジ及び右エッジのいずれかの値が1.0と2.0の間にある時に満たされる。tの細分割と同様に、パッチが不規則な場合には生じたパッチをさらに処理されるよう要求できる。
【0082】
s及びtの終了条件が両方とも満たされると、ルートパッチ又は中間パッチは、細分割の第1レベルに進んでおり、エンド点、リーフパッチを表すデータを生成している。次にコマンドは、制御ユニット22から細分割ユニット18に送られ、該リーフパッチデータを出力する。
【0083】
制御ユニット22は完成されたアルゴリズムを介してパスの数をモニタする。第1のパスでは、制御ユニット22は下位計算ユニット18に制御信号を送り、上半分のサブパッチにt方向の分割の計算を行わせ、左半分のサブパッチにs方向の分割の計算を行わせる。制御ユニット22から細分割ユニット18に送られたコマンドの履歴は記録される。次にこのコマンドの履歴は、他のすべてのシーケンスが確実に機能するよう後続のパスで使用される。制御ユニットアルゴリズムの最終のパスは、t方向への分割が常に下半分のサブパッチを出力として取り込み、s方向への分割が常に右半分のサブパッチを出力として取り込むときに実行されている。
【0084】
<規則的なリーフパッチの処理>
リーフパッチの最終エッジの値の各々が1.0と2.0の間である場合、リーフパッチは規則的であると言える。規則的なリーフパッチが処理されて、変換器により、図11に示されるようなパッチをカバーするように配置された三角形のグリッドの9つの頂点を生成する。好適には変換器はプロセッサ20を組み込む。三角形のテセレーションは、正方形の各辺に規則的配列で並べられた3つの頂点と、正方形の中心に配置された9番目の頂点とを有する正方形をカバーする。三角形は正方形を回転しながら扇形に配置され、その結果8つの三角形の各々は正方形の中心の頂点を共有する。図12に示され、従来技術でよく見られるような別のパターンもまた使用することができる。
【0085】
図12の構成に優る図11の構成の1つの利点は、生成される三角形が元のパッチの制御点の順序とは無関係になることである。すなわち、元のパッチのSとTの定義を入れ替えること、又は制御点の順序を反転させることは、同じ結果をもたらすことになる。第2の利点は、パターンが「不規則な」リーフパッチを処理するときに生成されたものに、より近いということである。
【0086】
リーフパッチから9つの出力頂点位置への変換は、「リーフパッチテセレーションユニット」20において実行される。これらの頂点に対応するサーフェス法線は、「サーフェス法線生成ユニット」24において同様に計算される。処理演算のこの段階において、ポリゴンポッピングを最小にするアルゴリズムが実行される。
【0087】
図16は規則的なパッチの制御点データからテセレーション三角形の9つの頂点への変換を概略的に示している。パッチの16の制御点は、該点がPijで索引付けられた4×4の行列で配列され、ここでjは0から3まで変わる行列の行を示し、且つ制御点は行0が最上行であるように配置されており、iは0から3まで変わる行列の列を示し、制御点は列0が左列であるように配置されていると仮定する。また、テセレーション三角形の9つの頂点が3×3の正方形で配列され、左上の頂点がV0に索引付けられ、索引付けは3×3の正方形を時計回りに左中央の頂点V7まで増分し、中央の頂点がV8に索引付けられると仮定する。
【0088】
テセレーション三角形の4つの外側の頂点は、規則的なリーフパッチの外側の制御点から直接導出される。左上の頂点V0は左上の制御点の値P00を取り込み、右上の頂点V2は右上の制御点の値P30を取り込み、左下の頂点V6は左下の制御点の値P03を取り込み、及び右下の頂点V4は右下の制御点の値P33を取り込む。
【0089】
残りの5つの頂点V1、V3、V5、V7、及びV8の取り込みは多少複雑である。
【0090】
図17の線図を考察すると、曲線は、コーナーの頂点の2つ(例えばV0及びV2)である点AとBを有するリーフパッチのエッジの1つであると考えることができる。さらに細分割が実行された場合には、これは、曲線C上に新しい点を生成することになり、該点は中間の頂点V1の可能な位置に対応する。反対に、細分割の数が同じままであった場合には、曲線は線ABで近似され、V1は点Dの線上に存在することになる。細分割のレベルが変化するときに点CとDの間で平滑な転移を実現するために、線分CDに沿って新しい点Eが計算され、これがV1の値として使用される。これは次の式で表される。
E=wC+(1−w)D …式2
ここでwは、エッジ細分割比率の小数部分から導出された重み付け因子、Dはリーフパッチの細分割レベルで導出された第1の頂点の値、及びCはサブリーフパッチの細分割レベルで導出された第2の頂点の値である。(エッジ比率の小数部分は、その値の2進浮動小数点表示の仮数部を調べることによって自明に得られる点に留意されたい)。
【0091】
Dは2つのコーナーの頂点、すなわち図16の場合では点A及びBにそれぞれ相当するV0及びV2の平均を取ることによって計算される。Cを計算するために、s方向の左半分の細分割が実行され、Cは左半分の細分割パッチの右上の制御点の値を取る。左(右)エッジに対するCの値を計算するために、リーフパッチの左(右)エッジに沿ったベジェ曲線をt=1/2において求める。これは、まさしく図7でのDnの計算に等しい点に留意されたい。最上エッジ及び最下エッジの「C」点の計算は類似している。Cの値(第2の値)とDの値(第1の値)が計算されると、頂点V1は式2に基づいて計算される。この計算は結合器によって実行される。結合器は、テセレーションユニット20の整数部分とすることができる。
【0092】
この計算はリーフパッチの四辺形の各エッジについて繰り返される。中央の点は同様の方法で計算されるが、しかしながらV8の点Cの計算はs及びt次元の両方で細分割を必要とする。これは、つまり最上エッジ及び最下エッジから計算された「C」の値を使用し、制御点の2つの中央の行から2つの追加の「C」値を計算して、次いでこれら4つの値の方法を再適用することにより効率的に行うことができる。
【0093】
V8のDの計算では、図11に示されたテセレーションパターンが好適であることから、頂点の対角線ペアの1つである、(V0、V4)又は(V2、V6)のいずれかが使用される。いずれの対角線ペアを選択するかは、ルートパッチに対するリーフパッチの相対的位置に基づく。図18aは16のリーフパッチについてルートパッチに対するリーフパッチの相対位置を表すチェッカーボード構成を示している。リーフパッチの正方形は、4行及び4列で配列され、ルートパッチをカバーする。交互配置パターンで正方形の半分には陰影が付けられ、残りの正方形には陰影が付けられていない。左上の正方形には陰影が付けられている。図18を参照すると、シェーディングされたリーフパッチは点Dの計算で(V0、V4)を使用し、一方、陰影が付けられていないリーフパッチのDの計算には(V2、V6)を使用する。リーフパッチの他の数については、同様のパターン化手法を適用する同様の線図を構成することができる。
【0094】
この好適なパターン化手法は、細分割レベルが「2つの境界のパワーをクロスさせる」ときに、三角形構成が急には変わらないことを保証する。細分割レベルが増大すると、生成された任意の新しい三角形は親の三角形に「内在する」ことが保証される。これは図18bに示される。例えば、より高度にテセレーションされた領域(右側に示される)の左上のリーフパッチ内に導入された中央の点は、「親」リーフ(左側)から中央の半対角線までの左上に依存することになる。これは図12に示された三角測量パターンには必要ではない代替の演算である点に留意されたい。
【0095】
<不規則パッチ処理>
細分割は、関連するエッジのいずれか1つの値が1.0と2.0との間にある場合に、s又はtの任意の方向で終了する。不規則である場合、すなわち1つ又はそれ以上のエッジの値が1.0から2.0の範囲の外にある場合には、リーフパッチのさらなる処理が必要とされる。不規則リーフパッチは、細分割値が隣接するパッチに結合させることが可能な範囲の外にあるエッジ上に追加の頂点を必要とする、規則的なリーフパッチと考えることができる。不規則リーフパッチは最初に規則的なリーフパッチとして取り扱われ、パッチの9つの頂点は上述のようにして計算される。追加の頂点を計算するために、さらなる細分割を実行する。さらなる細分割は、リーフパッチを形成するための細分割と同一の細分割ユニット内で実行することができ、制御ユニット22によって制御することができる。追加の頂点を得るための扇状パッチの変換は、リーフパッチ用の変換器内か、又は別の変換器内で実行することができる。
【0096】
右エッジの値が1.0から2.0の範囲外にある不規則リーフパッチに対する細分割処理の実施例は、図13a及び14に示される。この実施例では、右エッジの細分割値は2.0と4.0の間にあり、細分割の付加的レベルの1つは、クラッキングを防止するために、右エッジ上に必要な2つの余分の頂点(V23とV34)を生成することが求められることを示している。追加の頂点は、エッジの値が1.0から2.0の範囲外であるリーフパッチのエッジ上に設けられ、この場合は右エッジ上にある。追加の頂点によって記述された三角形はパッチの中央の頂点から扇状に広がり、このエッジにまたがる元の三角形を2つに分割する。このように、実施例では不規則パッチの右エッジは5つの頂点(3つではなく)、すなわち反時計回りにV2、V23、V3、V34、及びV4を有し、すべてがV8において共通の頂点を有する、V8−V2−V23、V8−V23−V3、V8−V3−V34、及びV8−V34−V4の4つの三角形を定義する。
【0097】
V23及びV34は、右エッジの値が1.0と2.0の間になるまで、t方向にさらなる細分割を実行することによって計算され、及び追加の細分割の出力を使用して新しい頂点V23とV34とを生成するのに使用される一連の扇状パッチを形成することによって計算される。扇状のパッチは、規則的なリーフパッチにおける頂点に相当する、9つの標準的な頂点であるV0からV8までの計算には使用されない。
【0098】
図13a及び14の不規則リーフパッチの追加の頂点を生成するために必要とされる処理を実施例を用いて説明する。以下の実施例により、当業者であれば、他の種類の不規則パッチの追加の頂点を生成する方法は明らかであろう。
【0099】
実施例では右エッジの値が2.0から4.0の範囲にあるときに、右エッジの値を1.0から2.0の範囲に入れるためには、細分割の1つだけのレベルが必要とされることが分かるであろう。不規則パッチの処理ステップは、図15のフローチャートに要約される。不規則パッチのエッジの値が試験され、どのエッジの値が1.0から2.0の範囲の外にあるかが判定される。処理はエッジ関係を基に進められる。図13a及び14に示された実施例の場合、右エッジの値だけが範囲外である。これはt方向の細分割だけが必要であることを示す。制御ユニット22は細分割ユニット18に適切なコマンド信号を送出し、不規則パッチをt方向に分割する。扇状パッチのエッジの値は、適切な一般的形態の細分割に関して前述のように計算される。18によって戻された上半分及び下半分のサブパッチは、追加の頂点V23及びV34を計算するために使用することができる上部及び下部扇状パッチを定義する。制御ユニット22は扇状パッチ形成の履歴を保持して、すべての適切な扇状パッチの形成を保証する。この場合、上半分の扇状パッチと下半分の扇状パッチの形成後、すべてのエッジの値は1.0と2.0の範囲内にあり、扇状パッチを形成するさらなる細分割は必要とされない。
【0100】
追加の頂点V23は、上述の式2に従って上部扇状パッチの中央右の頂点を計算することによって得られる。追加の頂点V24は、上の式2に従って下部扇状パッチの中央右側の頂点を見積もることによって計算される。
【0101】
扇状のパッチの他の頂点のいずれもテセレーションプロセスでは必要とされない。不規則なリーフポリゴンデータは、通常の細分割プロセスによって形成された頂点を結合して、リーフパッチ、「第1の複数の頂点」、及び扇状パッチから計算された追加の頂点、並びに「扇状パッチの値」を形成することによって生成される。
【0102】
<頂点のサーフェス法線の方向の計算に対する背景>
サーフェス法線生成ユニット24は、細分割ユニット18の出力を取り込み、各頂点に関係するサーフェス法線を計算する。(好適な実施形態では、ユニット20及び24は別個のものであるが、別の実施形態では、これらは共通している幾つかの計算値を共有することができることに留意されたい)。サーフェス法線は、サンプルの点においてモデリングされているサーフェスが面している方向を示すのに使用され、後続のライティングとテクスチャの計算のために必要とされる。方向プロセッサ24は、不規則パッチから計算された任意の追加の頂点を含むリーフパッチの各々の頂点に対する法線を計算する。ポリゴンポッピングのシェーディングされた相似形を最小にするために、式2による前述のような線形補間法が、内部頂点の法線に対して適用され、すなわち出力法線は隣接する頂点の法線と「正しい」法線の混合とすることができる。
【0103】
理想的には該出力法線は実際には「混合」されるべき最終のシェーディング及びテクスチャ値である点に留意されたい。好適な実施形態では、外部グラフィックス標準(例えば、MicrosoftのDirectX)によって制約を受けているためにこれは行われない。頂点のシェーディングが計算された後でこれらの制約は取り除かれるべきである場合には、呈示された「ポリゴンポッピングの減少」法を容易に適用できることは同業者には明らかである。
【0104】
従来技術において知られているように、非有理的ベジェパッチのコーナーに配置された4つの頂点については、サーフェス法線の計算はより簡単なはずである。この実施例は図19に示されている。本発明はこの原理を有理パッチを用いる用途に適合させる。
【0105】
最初は4つの点だけがリーフパッチのコーナーに存在するので、本発明ではリーフの追加の「部分的な」細分割が実行される。この処理は図20に示される。規則的なリーフパッチの9つの頂点の場合(番号付けは図11で使用されているもの)、3つの追加の部分的細分割(1つはS方向(図20(iii))、1つはT方向(図20(ii))、及び追加の細分割(図20(iv))は、V1、V3、V5、V7、及びV8の位置が少なくとも1つのサブパッチのコーナーであるように、子のサブパッチを生成するのに十分である。頂点の法線を生成するためには各サブパッチのすべての制御点が必要ではなく、好適な実施形態では必要最小限の制御点だけが計算されることに留意されたい。図20では、(コーナーの法線の計算のため、又は必要な子のパッチの制御点を生成のためのいずれかが直接的に)必要とされる制御点は灰色又は黒で示され、一方、必要とされないものは白で示される。
【0106】
上記のように、本発明は有理ベジェパッチの法線を効率的な方法で計算するが、その方法及び背景理由を以下に示す。
パラメータ位置(s、t)(s、t)における有理サーフェスの位置は以下の式で与えられる。
一方、(0,0)における(a,b)方向の単位長さの接線ベクトルの定義は次式で与えられる。
【0107】
式中の「差分」項を考察すると、次式が得られる。
これは、以下のことを意味する。
【0108】
スカラー値w(ea,eb)w(0,0)が正でありゼロではないので、これは上の制約式の上部と下部の両方に適用することができ、次式で与えられる。
【0109】
有理的なベジェパラメトリックサーフェスに限定して注目し、ベジェパッチの(0,0)(0,0)点が
の制御点に相当する点に留意すると、次式の挙動を調べる必要がある。
【0110】
便宜上、以下のように定義する。
【0111】
好適な実施形態では、ベジェ関数は双三次である。より高次のサーフェスを使用する実施形態に対するこの手法の拡張は、当業者に容易なものでなければならない。
【0112】
取得される行列形式の(ea,eb)において(すなわちw成分によるx、y、及びz成分の除法の前に)双三次の均質なベジェサーフェスを表す。
【0113】
従って、これは次のように表し得ることが分かる。
【0114】
Q行列の特定の特性に留意すると、これは次のように簡略化される。
これは以下のように変形される。
【0115】
本発明の方法は、「S」、「T」、及び「対角線」の接線候補である最大3つまでの可能性のある接線候補を計算する。
【0116】
<「S」方向の候補接線ベクトルの導出>
【0117】
「S」方向の接線ベクトルを生成する場合を考えると、式3と4はそれぞれ次のように変形される。
【0118】
を考察すると、次の式が求められる。
【0119】
ここで次の3つの場合が考えられる
1.
2.
3.
【0120】
上のケースの各々に関して、e→0のような極限値が分子と分母の両方に存在すると(及び極限値がゼロでない)場合、式全体の極限値が存在することが計算から分かる。
【0121】
ケース1:
分子/分母の「内容」から始めると、次式が得られる。
【0122】
の場合に限り、極限値は明らかに存在し且つゼロではない。
この条件が成り立つ場合は、S方向の接線ベクトルは次の式で与えられる。
この点ではベクトルの長さは重要ではないことに留意されたい。
【0123】
ケース2:
ケース1の条件が当てはまらない場合、
は、ケース2の極限値が調べられ、次式が与えられる。
【0124】
であることに留意すると、上式の和の第2の部分は、0と仮定されたケース1の結果と同じであることが分かる。従って次式が得られる。
【0125】
同様に、
と仮定していたので、これは次式になる。
【0126】
従って、選択された条件が成り立つ場合、これが0でなければ次のような有効な「S」正接が存在する。
【0127】
ケース3:
ケース2及び3が両方とも成り立たない場合には、示されたのと同じ引数を使用して、0でないという前提で次式によって「S」を計算することができる。
【0128】
<「T」方向の候補接線ベクトルの導出>
これはまさしく「S」正接と同じ論証に従うので、ここでは説明しない。
【0129】
【0130】
【0131】
上述の方法では、特定のコーナーの頂点の法線を計算するために、最大9つまでの制御点が必要とされる可能性があることは明らかである。図21は、V0(すなわち、(s、t)=(0,0))のコーナー頂点の場合における組を示す。制御点の選択は、計算される頂点の法線に応じて変わるので、残りの説明では別の命名法が適用されることになろう。特定の頂点の法線を計算するために使用される制御点は、C、S1、S2、S3、T1、T2、T3、及びDと呼ばれる。また、実施例として、この命名法と頂点V0に必要な制御頂点の間の相関性は図21に示される。
【0132】
<「サーフェス法線生成ユニット」の好適な実施形態>
ここでサーフェス法線生成ユニット24を図22aに関連して説明する。
【0133】
リーフパッチの制御点が提供され(200)、頂点V0、V2、V4、及びV6の各々に対して正しい8つの制御点(C、S1、S2、S3、T1、T2、T3、D)の組が選択され(201)、次にコーナー法線ユニットに供給される(202)。サーフェス法線生成ユニットにおいては、制御点の成分X、Y、Z、及びWだけが必要とされる点に留意されたい。
【0134】
ユニット201は、元のリーフパッチ制御点のどれが8つの点の4つの組の各々に対応するかを選択するMUXである。好適な実施形態では、4つの選択は以下の通りである。
頂点V0:これは図21に示されている。
【0135】
好適な実施形態では、「仮想の」S、T及び対角線の正接候補の方向は、後続のコーナー頂点に対して90°だけ回転している点に留意されたい。
【0136】
代替の実施形態では、実在する軸方向のミラーリングによる制御点の選択を使用することができるが、外積の結果が相殺されるべきかどうかを示すために、これはユニット「202」に供給されるべきフラッグの追加を必要とする。このような相殺は少なくとも頂点V2とV6に対して示されるべきであった。(頂点V4は両方の軸が反転されるので相殺を必要としないであろう)。
【0137】
ユニット203は、頂点V1及びV5のサーフェス法線を生成するのに適した新しい制御点を計算するために、リーフパッチの部分的な細分割を実行する。必要とされるセットは図20(iii)に示されている。ユニット204は、V1とV5の各々に対してそれぞれ必要とされる点を選択する別のマルチプレクサであり、該点をコーナー法線ユニット202に供給する。選択プロセスはユニット201のプロセスに類似しており、事前の説明があれば当業者にとっては明らかなはずである。
【0138】
同様な方法で、ユニット205及び206は、頂点V3及びV7の法線のために必要な2セットの制御点を生成する(図20(iii)参照)。
【0139】
ユニット207及び208は、V8のサーフェス法線を生成するのに必要な8つの制御点のセットを生成する。この組は図20(iv)に示される。図20(iv)の右エッジに示された4つの制御点は、図20(ii)の右エッジの1回の細分割によって得ることができ、一方、下エッジの制御点は、図20(iii)の下エッジの1回の細分割から計算される点に留意すべきである。「D」に対応する制御点は、図20(iii)の下から2番目の行か、又は代替として20(ii)の右から2番目の列のいずれかから得ることができる。
【0140】
性能的に、好適な実施形態は、複数のユニットとパイプライン形式のアーキテクチャとを組み合わせることにより、幾つかの頂点法線の計算が部分的に重なる。代替の実施形態では、並列処理のレベルはコスト/性能のトレードオフに応じて変えることができる。
【0141】
次に「コーナー法線ユニット」202を図22bと関連して説明する。この図は、理解しやすいように単一の法線の計算だけを説明している点に留意すべきである。8つの選択された制御点が入力される(220)。C点と3つのS点は「S候補」計算ユニット(221)に送られ、C点及び3つのT点は「T候補」計算ユニット(222)に送られると共に、C及びDは「対角線候補」ユニットに送られる。次に、3つの計算された正接候補TS、TT、及びTDiagは「候補選択及び法線計算」ユニット(224)に入力される。
【0142】
【0143】
別の実施形態では、追加の「最適化」を組み込んで、任意選択的に乗算を実行する前に、wすなわち「重み付け」要素の値が同一であるかどうかを最初に調べる。これはパッチが非有理的である場合、すなわちwの値が一定である場合の計算遅延を潜在的に低減することができる。
【0144】
従って、1つのベクトル減算ユニットだけが必要とされ、好適な実施形態ではこれはパイプライン形式である点に留意されたい。別の実施形態では、減算ユニットはまた、ユニット222及び223と共有することが可能である。
ユニット222はTTを計算すること以外はユニット221と同一であり、一方、ユニット223は単にTDiag=DXYZCW−CXYZDWを計算するだけである。
【0145】
次にユニット224を図24に関連して説明する。試験250及び252は、TS又はTTのいずれかを0ベクトルとすることができる特別な場合をチェックし、それぞれ−TT(251)又はTS(253)のいずれかである中間ベクトルTNZに設定する。両方のベクトルが0でない場合には、TS及びTTのベクトルの外積を取ることによって、ステップ254で候補サーフェス法線が生成される。次いで、候補法線は0に対して比較される(255)。0でない場合には、サーフェス法線として使用される(256)。0である場合には、ステップ253で中間ベクトルが設定される。
【0146】
中間ベクトルが必要とされた場合には、別の法線の計算が使用される(257)。これは中間ベクトルの外積と対角線の正接候補を計算する。ステップ251でTNZがマイナスのTTとして送られたことに留意すべきである。これは法線の方向の整合性を保つために行われる。浮動小数点の相殺が自明であることは理解されたい。
【0147】
前述のように、このようにして頂点V1、V3、V5、V7、及びV8について計算された法線は、これらの頂点をリーフパッチ内における最大の小数部分の細分割レベルで表示する。より小さな小数部分レベルについては、ポリゴンポッピングを除去するために使用された同じブレンディングプロセスが同様に適用され、最終的な法線ベクトルの結果を生成する。同様に不規則パッチの法線の計算は、前述したものと類似した追加のレベルの細分割を受けなければならない。
【0148】
このように本発明では、費用のかかる分割演算を必要とせずに有理ベジェサーフェスに対するサーフェス法線を計算することを理解されたい。これは有意な節約である。好適な実施形態では、出力される法線は単位ベクトルではなく、すなわち、好適な実施形態では、後続のシェーディング及び変換ユニット(本明細書には記載されていない)は、必要に応じてこの簡単なタスクを実行することが可能であると仮定する。
【0149】
図6を参照すると、パイプライン形式のテセレーション処理の最終段階は出力バッファ26内で実行される。入力バッファ12は、制御点(ポイント)を取得し、データをグループ化して、データを要素毎に再配置した。出力バッファ26は、頂点毎に計算段階からのデータをグループ化する反転タスクを実行することが必要とされる。出力バッファ26は、重み付けプロセッサ24によって計算された頂点と、サーフェス法線プロセッサ24によって計算された法線とを取り込み、各要素のデータを頂点毎に共にグループ化してこれを出力し、ディスプレー用に画像の変換、ライティング、テクスチャリング、及びラスタライゼーションで続いて使用する。
【0150】
特定の図に関連して説明され且つ説明の様々な点で説明された特徴は、特に説明又は図示されたもの以外を組み合わせて使用することができることに留意されたい。このような変更はすべて、以下の請求項に記載の本発明の範囲内に包含される。
【0151】
上記説明に関して、当業者であれば均等な装置及び方法を容易に思いつくことができ、且つ図面に示され本明細書に記載されたものに均等なすべての装置及び方法は、本発明に包含されることが意図されるものであることは理解されるべきである。従って、前述のものは本発明の原理のみを示すものと考えるべきである。さらに、当業者には多くの修正及び変更を容易に行うことができるので、本発明を図示及び説明された厳密な構成及び実施に限定することは望ましいものではなく、従ってすべての適切な修正及び均等物は本発明の範囲として行使され且つ包含されることになる。
【0152】
例えば、テセレーション三角形の代替のパターンは本発明の範囲内に包含されると考えられる。
【符号の説明】
【0153】
10 インターフェース
12 入力バッファ
14 フォーマット変換器
16 再帰バッファ
18 細分割ユニット
20 リーフパッチテセレーションユニット
22 制御ユニット
24 サーフェス法線生成ユニット
26 出力バッファ
【技術分野】
【0001】
本発明は、パラメトリックモデリングユニット及びポリゴンベースレンダリングシステムを備える3次元グラフィックシステムで使用するためのインターフェースに関する。
【背景技術】
【0002】
従来の3次元レンダリングシステムは、ポリゴン(通常は三角形)のメッシュを使用してシーン内のオブジェクトをモデリングする。三角形は、形状が単純であり、従って、表示用画像を生成するために変換、ライティング、テクスチャリング、及びラスタライゼーションなどの演算を実行するのが比較的容易である利点がある。
【0003】
ポリゴンメッシュを使用してオブジェクトをモデリングする既知の別の方法は、オブジェクトを領域にセグメント化して、モデリングされるオブジェクトの異なる領域に多数の湾曲した高次サーフェス(多くの場合パッチと呼ばれる)を適合させる。これらのパッチは一般に、制御ポイントのグリッドによって規定されたサーフェス形状を有するパラメトリックサーフェスとして定義される。高次サーフェスを用いる利点は、一般的に、特定のモデルを表示するために必要としているデータ量が、相当するポリゴンメッシュと比較して制御ポイントの集合の方がはるかに少ないという点である。また一般的に、高次サーフェスは、形状が変化するオブジェクトをアニメ化する際の操作が比較的簡単である。高次サーフェスを使用するモデリングの主な欠点は、レンダリングシステムのラスタライゼーション段階で、複雑さが付加的に導入されることである。
【0004】
また、ラスタライゼーションなどの処理段階を実行する前に、モデリング段階用に高次サーフェスを使用すること、及びサーフェスを一連のテセレーション三角形に変換することが知られている。この組み合わされた方法は、ラスタライゼーション段階に複雑さを付加することなく湾曲サーフェスを用いることができる利点が得られるが、サーフェスパッチデータを処理してポリゴンベースデータを形成するために好適なインターフェースを必要とする。湾曲平面を一連のポリゴンに変換するテセレーション過程では、2つの方法が通常良く使用され、すなわち、前方差分又は再帰細分割のいずれかである。本発明は再帰細分割法から導出される。
【0005】
組み合わされた3次元グラフィックシステムのパラメトリックモデリング段階(すなわち、後のレンダリング段階に対してポリゴンを生成するためにテセレーション段階を組み合わせたもの)では、複数の湾曲サーフェスのパッチをオブジェクトのサーフェスに適合させてオブジェクトの領域を定義する。このようなパッチの作用を定義するための、これらの定義する制御ポイントに対する幾つかの異なる規格が知られている。このような規格の1つはベジェパッチであり、例えば、Watt & Wattによる「Advanced Animation and Rendering Techniques」pp66−68、又はForey Van Damらによる「Computer Graphics Principles and Practice」pp471−530を参照されたい。また、1つのフォーマットのパッチに対応した制御ポイントを異なるパッチ形式に対応した新しい位置に、最終サーフェスが等しくなるように変換する方法も知られている。これらのパッチは双3次数である場合が多い。
【0006】
共通のパラメトリックパッチには要に2つのバリエーションがある。第1のバリエーションは「標準の」mpm有理サーフェスパッチ群であり、一方、第2のバリエーションは有理パッチの拡張集合である。有理パッチは、特定のモデリングがより単純な非有理的変化において利点を有しているといえるが、幾つかの点では処理が幾分複雑になる可能性がある。両方のタイプのパッチは前述の2つの引用文献で十分に説明されるが、しかしながら、本実施形態の説明を簡略化するために、次の要約が示される。非有理的パラメトリックサーフェスに対して、3次元位置は以下のように記述することができる。
ここで、x(s,t)、y(s,t)、及びz(s,t)の各々は、同次数のスカラパラメータの多項式であり、0≦s,t≦1である。双三次(すなわち2つの3次式の積)のベジェサーフェスの場合、多項式の次数は6である。ベジェ方程式とサーフェスの制御ポイントの各x、y、z成分とがサーフェスの形状を定義する。
【0007】
非有理的サーフェスは、制御ポイントの各々に対応した正の値「w」をさらに有する第4の多項式w(s,t)を導入することによって定義を拡張する。この場合、サーフェス位置は次のように定義される。
【0008】
また、一般によく使用されている種類のパラメトリックサーフェスパッチが行列形式で表現可能であることは、当該技術分野ではよく知られている(前述の引用を参照)。例えば、双三次ベジェパッチ
は、次のように表すことができる。
ここでQはスカラー定数行列、Pはサーフェスに対する制御ポイントの行列である。
【0009】
PはPSTとして番号付けられる点に留意されたい。
【0010】
再帰細分割手法によるパッチのテセレーション三角形への変換は、最初に各パッチをその2つのパラメータ次元(すなわちs又はt)のいずれか1つにわたって2つのサブパッチに分割することよって達成される。これは図1a及び1bに示され、ここでは制御ポイントを有するパッチがパラメータ空間に表現されている。サブパッチの各々は、的確な細分割レベルが達成されるまでさらに細分割される。これが達成されると、結果として得られるサブパッチはそれぞれ同一平面上にない四辺形として扱われ、三角形の規定のパターンが、サブパッチ、計算された三角形の頂点、及び出力された三角形に重畳される。
【0011】
図2は、3つのレベルの細分割が適用された、細分割によるパッチの概念的処理を示す概略図である。図2から、処理は、オリジナルパッチ、すなわち「ルート」パッチから中間レベルのパッチを介して、「リーフ」パッチと呼ばれるエンドポイントパッチまで進む2分木の形態をとることが分かる。各リーフパッチは、レンダリングのラスタライゼーション段階のために必要とされる、テセレーション三角形を定義する頂点を生成するために使用される。
【0012】
再帰細分割の既知のシステムにおいて、テセレーションは、各段階に対して多数の計算が必要とされるので従来からCPU上で実行される。これに伴う一連の計算を検討すると、CPU使用時には、リーフパッチに対する多くのパスに関して同じ中間結果が使用されるので、この中間結果をスタック上に格納することが効率的であることが分かる。従って、スタックを使用することにより、実行される計算の数が最小となる。ハードウェアの実装の面からすると、内部(すなわちオンチップの)記憶装置がコスト高であること、及び外部に格納された多大な量のデータを検索することがシステム性能の面でボトルネックとなる可能性があるということは実際的ではないということに留意されたい。
【先行技術文献】
【非特許文献】
【0013】
【非特許文献1】Watt & Wattによる「Advanced Animation and Rendering Techniques」pp66−68
【非特許文献2】Forey Van Damらによる「Computer Graphics Principles and Practice」pp471−530
【非特許文献3】Clarkによる「A Fast Scan Line Algorithm for Rendering Parametric Surfaces」、Computer Graphics 13(2)、289−99
【非特許文献4】Watt & Watt、Forley他、及びFakinによる「Curves and Surfaces for GAGD. A Practical Guide, 4th Edition, Academic Press, ISBN−0−12−249054−1, pp244−247
【非特許文献5】Watt & Wattの「Advanced Animation and Rendering Techniques. Theory and Practice」, ACM Press. ISBN 0−201−54412−1
【発明の概要】
【課題を解決するための手段】
【0014】
本発明の第1の態様は、これらの問題を改善することを目的としている。これは、メモリ及びメモリ帯域幅の使用を最小にしながら高度な計算能力をもたらす方法で再帰細分割を使用して、パラメトリックモデリングデータをポリゴンベースデータに変換するためのインターフェースを提供する。
本発明の第1の態様によれば、請求項12によるインターフェースが提供される。本発明の第1の態様の好適な特徴は、従属請求項13から16で定義される。
【0015】
また、請求項16により、パラメトリックモデリングユニットとポリゴンベースレンダリングシステムとの間でインターフェースをとる方法が提供される。好適な方法の各段階は、従属請求項16から19で定義される。
【0016】
組み合わされたグラフィックシステムにおいて、パラメトリックモデリングユニットとポリゴンベースのデータとの間でインターフェースをとるときに発生する第2の問題は、モデリングされるオブジェクトの隣接する領域を示す第1と第2のパッチにおいて、第1のパッチに関係するパラメータデータと第2のパッチに関係するパラメータデータとを変換するために、細分割の異なるレベルが要求される場合があることである。高度に湾曲したサーフェスを定義するパッチは、パラメトリックモデリングの利点が失われることがない場合には、パラメータデータをポリゴンベースのデータに変換するときに、平坦なサーフェスを示すパッチよりも高度に細分割されなければならない。隣接するパッチの変換が同じレベルの細分割を各パッチに適用するように制約されない場合には、モデリングされたオブジェクトにクラックが生じる恐れがあり、これは細分割のより高度なレベルのサーフェスが余分なサンプル点を有しており、要するに形状が僅かに異なることに起因する。クラックの問題は図4に示される。
【0017】
クラックの問題に対する1つの解決方法は、すべてのパッチに対して同じレベルの細分割を使用ことである。しかしながら、これは、幾つかのパッチがより小さく分割されたレベルで適切にテセレーションされるときには過度に細分割される結果となり、適切な結果をもたらすのに必要な領域に対しての処理になっていない。
【0018】
別の解決方法は、サーフェスを適切に表すのに十分な細分割レベルまで各パッチを処理し、次いで、細分割のレベルが異なる隣接するサーフェスパッチ間にいわゆる「ステッチメッシュ」を挿入することである。従って、図5aに示されるように、ステッチメッシュは可能性のある任意のクラックをカバーする。図において、2つの隣接パッチは異なるレベルまで細分割されており、すなわち一方は2×4のサブパッチを使用し、他方は細分割されず、すなわち単一の四辺形で示される。2×4パッチ上に「隣接する」輪郭は頂点A、B、C、D、及びEから成り、一方、1×1細分割に相当するものはエッジAEから成る。サーフェスにギャップが出現するのを回避するために、三角形ABC、ACE、及びCDEがさらに生成される。
【0019】
残念なことに、このようなメッシュの接続はサーフェス方向に急激な変化が生じる可能性がある。隣接するパッチのエッジを共にステッチすることは、計算集約的であり、且つ細分割レベルが変化するときにステッチメッシュの再生成が必要となることは同様に理解される。
【0020】
Clarkは、「A Fast Scan Line Algorithm for Rendering Parametric Surfaces」、Computer Graphics 13(2)、289−99により、各パッチ内で細分割が異なるレベルであっても可能な別の技法を提案した。この方法の一部として、クラック問題が「解決」されなければならなかった。Clarkの解決方法は、より高い細分割の領域のエッジがより低い細分割の領域に適合する場合に、これを意図的に「平坦化する」ことである。これは図5bに示される。高い細分割領域と低い細分割領域間で「共有された」境界は、低細分割領域の境界に数学的に適合するように高細分割領域上で「平坦化」されていた。これを図5aの方法と比較すると、頂点B、C、及びDが線AE上にあることが分かる。
【0021】
この手法は数式的には正しいが、僅かな欠点がある。コンピュータグラフィックスハードウエアの精度は限界があり、正確なポリゴン頂点位置を表示することができない。従って、共有境界上の平坦化された頂点を正しく配置することが不可能である場合が多い。これは、当該技術分野でよく知られている「T−ジョイント」によって引き起こされる問題につながる。これは図5cに示されており、ここでは不正確さによって極めて狭いギャップが現われる。このギャップは極めて小さいのが典型的であるが、それでも尚、他の場合では、隣接する三角形のエッジに沿って位置するセミランダムピクセルホールの集合としてレンダリングされた画像において見ることができる。画像がアニメ化されると、これらは断続して「輝き」、容易に見られるようになる。
【0022】
これらのT−ジョイントは、ステッチポリゴンを再度導入することによって固定することができることは理解されるが、しかしながらこのようなポリゴンは極めて小さく、ポリゴンのレンダリングに伴う「設定」コストがより有意に大きなサイズのポリゴンに対して良好に役立つことから、これはむしろ非効率な方法である。
【0023】
さらに別の手法は、Pixar’s Rendermanシステムで使用されるように、結果として得られるポリゴンが画素よりも小さくなるまでパッチを細分割することである。そのため、これらのマイクロポリゴンは「点」として取り扱うことができる。この方法は膨大な量のデータを生成し、リアルタイムのレンダリングには実際には適していない。
【0024】
従って、現在の技術におけるクラックのない細分割のための選択肢としては、以下のように要約することができる。
(1)モデルのすべてのパッチを同一の細分割レベルまで細分割する。これは単純であるがリソースを浪費する。
(2)各パッチ内で一様に細分割し、次いでステッチポリゴンを使用して非一様に分割されたパッチ間のギャップを隠す。これは、ステッチポリゴンが追加コストとなり、(図5aに見られるように)方向の急激な変化を誘導する可能性があるので理想的ではない。
(3)Clarkの方法を使用することにより、パッチ内でも非一様な細分割が可能となるが、T−ジョイント問題を欠点として有する。
(4)Clarkの方法にさらなるステッチポリゴンを適用する。
(5)メッシュをマイクロポリゴンに細分割する。
【0025】
パッチのエッジに沿って非一様な細分割をできるようにすることは、結合部にクラックが発生することなく異なるパッチを結合することができるので望ましいことが理解される。また、Clarkの方法を用いて可能なように、パッチ内で非一様な細分割をできるようにすることは、パッチの1つの側面上の高細分割のエッジから反対側面上の低細分割のエッジまでの漸次的移行が、パッチが内部的に一様に細分割されるシステムにおけるよりも少ないポリゴンしか必要とせず、より効率的なポリゴンの使用を可能にするので望ましいことである。また、内部的又は境界上でステッチポリゴンを必要としないシステム、及び同様にT−ジョイントを導入しないシステムは非常に望ましいことが理解される。
【0026】
従って、本発明は第2の態様において、パッチ内でパッチデータを異なる細分割方向に異なる細分割レベルまで処理し、Clarkの方法による問題を回避する、「不規則なパッチ」の処理をサポートする。異なる数の頂点を「不規則なパッチ」の異なるエッジ上に形成することによって、オブジェクトの隣接領域をモデリングするテセレーションパッチ間のクラックを防止するステッチメッシュが不必要となる。不規則なテセレーションに対応することにより、隣接するパッチの隣接エッジが、残りのエッジについてパッチの細分割のレベルに影響を与えることなく、同じ数のポリゴンの頂点を保持できるようになる。2つの均等に細分割されたパッチの境界を示す実施例が図13bに与えられる。
【0027】
本発明の第2の態様によれば、請求項8によるインターフェースが提供される。本発明の第2の態様の好適な特徴は、従属請求項9に詳細に記載される。また、請求項10により、パラメトリックモデリングユニットとポリゴンベースレンダリングシステムとの間でインターフェースをとる方法が提供される。
【0028】
細分割の不規則なレベルは、最終のサブパッチから四辺形の各エッジに沿って適切な数の頂点を有するメッシュを自動的に生成することによって対応される。これによりクラックの発生なしにポリゴン化されたパッチを簡単に結合することが可能になる。
【0029】
既知のインターフェース技法に関する別の問題は、いわゆるポリゴンポッピングである。異なるパッチのインターフェースにおいて、すべてのパッチの各エッジは自己細分割制御値を有すると仮定する。細分割変化の手段としてオブジェクトの平滑なアニメ化を可能にするために、これらの値は、浮動小数点を取るか、又は少なくとも小数点部分を包含すると仮定する。ポリゴンポッピングは、テセレーションポリゴンにおいて急激に点が移動するときの説明に使用される用語であり、細分割制御値の小さな小数部分の変化により処理の追加段階(パッチの追加の2元細分割)を実行させる場合に生じる可能性がある。エッジの細分割制御値は任意の値を取ることができるが、好適なテセレーション手法は、次の直近の2の累乗にまで2元パッチ細分割を実行するように制約される。従って、細分割比率が僅かでも増加すると、細分割の実際のレベルが大幅に増加する可能性がある。例えば、各エッジに対して規定された細分割の値が4の場合、細分割は16のリーフパッチをもたらす。各エッジに対して規定された細分割の値が4から4.1に増加すると、次のより大きな2の累乗は8であり、結果として得られる細分割は64のリーフパッチを生じる。従って、多くの新しい三角形がオブジェクト内に現われる。このプロセスが適切に制御されない場合には、図3に示されるように、アニメーションに望ましくない視覚的な影響が引き起こされる。
【0030】
図3aにおいて、湾曲サーフェスは既に2つの四辺形領域に細分割されている。従って、パッチの「最前部」の湾曲エッジは線分AB及びBCによって近似される。図3bでは、前エッジに沿って2つの新しいポイントD及びEが生成されるように、細分割のレベルは増加(1次元だけにおいて)されている。従って、パッチの前エッジは線分AD、DB、BE、及びECによって表される。ABCからADBECへの形状の変化は比較的大きく、新しいポイントD及びEはジャンプ、又は「ポップ」して見えるようになったと言うことができる。これは、位置E’からジャンプして出現したポイントEを有するこの実施例において最も容易に分かる。
【0031】
本発明は第3の態様において、ポリゴンポッピングに関連する視覚の問題を改善することを意図している。
【0032】
本発明による第3の態様では、請求項1によるインターフェースが提供される。本発明の第3の態様の好適な特徴は、従属請求項2及び3で定められる。また、請求項4により、パラメトリックモデリングユニットとポリゴンベースレンダリングシステムとの間でインターフェースをとる方法が提供される。好適な方法の段階は従属請求項5から7で定められる。
【0033】
本発明は第3の態様において、高次サーフェスを使用するモデルの詳細レベルを変えるときに、よりスムーズに見えるアニメ化された画像を生成する。これは、最終的にテセレーションリーフパッチの線形細分割と3次細分割の間で重み付けされた混合を好適に使用する。この混合に対する重み付け因子は、必要とされる細分割値と次のより小さな2の累乗との比率によって好適に決定される。
【0034】
ライティング及びシェーディング演算が3次元グラフィックのサーフェスに適用されるときには、通常は1つの点におけるサーフェスの法線、すなわちその位置でのサーフェスに垂直なベクトルが、既知であることが要件である。テセレーションされたサーフェスをシェーディングするために、サーフェス法線は計算された三角形の頂点のみにおいて計算される必要がある。
【0035】
Watt & Watt、Forley他、及びFakinによる「Curves and Surfaces for GAGD. A Practical Guide, 4th Edition, Academic Press, ISBN−0−12−249054−1, pp244−247」で述べられているように、1つの点で法線を得るための標準的な方法は、その点で2つの(1次独立の)接線ベクトルを計算して、これらの外積を取ることである。必要であれば、その結果を後に、s及びtのパラメータに関係するサーフェスの1次偏導関数を計算するユニットに変換することができる。
【0036】
普遍性を損なうこと無く、サーフェス法線の計算がパッチのコーナー点においてのみ行われるように制限した場合、非有理的ベジェサーフェスは、コーナーの制御点とその2つの直近のエッジ制御点との間の差が、それぞれの1次偏導関数のスカラー積であるという極めて好都合な特性を有することになる。これは図19に示され、ここで「正接S」はコーナー点P00とその隣接する制御点P10間の差と一致し、一方、「正接T」はコーナーと制御点P01間の差と一致する。
【0037】
幾つかのシステムは、この事実(繰り返される細分割に加えて)を使用してパッチ上の種々の位置において法線を計算する。
【0038】
残念なことにこの計算は成功しない場合が多い。正接ベクトルが1次独立で、ベジェパッチの制御点が、特にこれらの隣接するコーナー点と一致していることが要求される場合がある。これは1次偏導関数の1つ又は両方が0とすることができ、不正確な法線が得られることを意味する。このようなサーフェスパッチは多くの場合「縮退」と呼ばれ、幾つかのシステムはこれらを「不正」であると見なす。これは、このような制御点でのサーフェス構成が完全に有効である形状をモデリングする必要性が高く、モデリングソフトウエアパッケージによって容易に生成することができるので、むしろ残念なことである。
【0039】
より実用的な既知の1つの解決方法は、s及びt方向のパラメータにおいてコーナーから僅かにオフセットした2つのポイントでサーフェスの数値を求めることである。従って、2つの接線ベクトルはこれらの計算されたポイントとパッチコーナーとの間の差を取ることによって近似される。これは通常は適切な結果を与えるが、追加の計算の観点から言えばコスト高である。
【0040】
接線ベクトルの定義を再度参照して微積分計算を適用すると、1次が0である場合、2次偏導関数を用いることができるのが分かる。Watt & Wattの「Advanced Animation and Rendering Techniques. Theory and Practice」, ACM Press. ISBN 0−201−54412−1は、同様に非有理的ベジェパッチに関して、この状況におけるコーナー制御点と後続の2次偏導関数の積との間の差を論証している。図19を再度参照すると、例えばP01とP00が一致する場合、P02とP00の差は潜在的正接をもたらす。同様にこれも0である場合、P03との差を取ることによって、3次偏導関数に対して同様のプロセスを用いることができる。
【0041】
残念なことに、この方法でも尚成功しない可能性がある。パッチのエッジに沿ったすべての点は一致する場合があり、パッチが球体の8分空間をモデリングしている際に起きるように、パッチは「三角形」になっている。この特定の状況では、2次偏導関数を選択することができる。Farinはまた、さらにより微妙な問題、すなわちs及びt方向に0でない偏導関数が存在できるが、幾つかの状況においてこれらが平行とすることができることを述べている。その結果、外積は0を与え、従って無効な法線である。Farinは1つの特定の場合に対する解決方法を述べている。
【0042】
本発明は第4の態様において、有理的ベジェサーフェスに対する法線をロバストであるばかりでなく効率よくサーフェス法線を計算する計算方法を示している。
【図面の簡単な説明】
【0043】
【図1a】上半分のn番目のレベルのサブパッチと下半分のn番目のレベルのサブパッチとを形成するためのt方向のn−1番目のレベルのパッチの細分割を示す概略図である(理解しやすいように、これらは図中物理的に分けて示されている)。
【図1b】左半分のn番目のレベルのサブパッチと右半分のn番目のレベルのサブパッチとを形成するためのs方向のn−1番目のレベルのパッチの細分割を示す概略図である。
【図2】各々の段階におけるS又はTの細分割方向の選択肢が供給される細分割のパラメータによって決定される、中間パッチと最終的に8つのリーフサブパッチに分割されるパッチのためのリーフパッチとに対するルートパッチの細分割の可能性のある選択肢を示す概略線図である。
【図3a】「前エッジ」に沿って頂点ABCを生成する、第1のテセレーションプロセスによって近似された湾曲サーフェスを示す線図である。
【図3b】ポリゴンポッピングを生じるテセレーションプロセス間の比較的大きな形状の変化を示す、「前エッジ」に沿って頂点ABCDEを生成する第2のテセレーションプロセスによって近似された同じサーフェスを示す図である。
【図4】隣接するパッチが別々の細分割比率に細分割されるときのクラックの問題を示す図である。
【図5a】クラックの問題を克服するための既知のポリゴン生成システムによって使用されるステッチメッシュである。
【図5b】クラックの問題を解消するためのClarkの手法を示す。
【図5c】コンピュータグラフィックにおける「T−継ぎ手」の問題を示す。
【図6】インターフェースの好適な実施形態を示す概略図である。
【図7】下位計算ユニットの計算段階を示す概略図である。
【図8a】図7の計算を使用したt方向の上半分の細分割に関するパッチデータの行及び列の索引付けを示す。
【図8b】図7の計算を使用したt方向の下半分の細分割に関するパッチデータの行及び列の索引付けを示す。
【図8c】図7の計算を使用したS方向の左半分の細分割に関するパッチデータの行及び列の索引付けを示す。
【図8d】図7の計算を使用したS方向の右半分の細分割に関するパッチデータの行及び列の索引付けを示す。
【図9】2段階細分割ユニットの概略図である。
【図10】制御ユニットの演算を示すフローチャートである。
【図11】好適なテセレーションパターンである。
【図12】別のテセレーションパターンである。
【図13a】右エッジの不規則リーフパッチのテセレーションパターンである。
【図13b】13aの不規則なパッチと高レベルの細分割パッチの結合を示す。
【図14】図13aの不規則パッチの追加の頂点を推定するための扇状パッチの生成を示す概略図である。
【図15】扇状パッチ処理中の制御ユニットの演算を示すフローチャートである。
【図16】リーフパッチの制御点P00、P30、及びP33と、テセレーション三角形の頂点V0、V2、V6、及びV4との間の対応を示す概略図である。
【図17】頂点V1、V3、V5、V7、及びV8の結合値の生成を示す概略図である。
【図18】異なるリーフパッチのための中心の頂点V8の計算でどの頂点が使用されるかに関する線図である。
【図19】非有理双三次ベジェパッチのコーナーにおける接線ベクトルの挙動の1つの実施例を示す。
【図20】9つの「テセレーション」頂点(すなわち図11に示されるような)においてサーフェス法線を構成するのに好適な制御点を生成するために(規則的な)リーフパッチに適用された追加の部分細分割段階を示す。
【図21】パッチの特定のコーナー点に対するサーフェス法線を生成するために本発明によって使用される有理双三次ベジェパッチの制御点のサブセットを示す。
【図22】aはテセレーションリーフパッチに対する9つの頂点法線を生成するため必要とされる制御点を生成するために取られる段階を説明する。bはこの法線生成プロセスの一部をさらに説明する。
【図23】有理ベジェパッチのコーナーで1つのパラメータ次元の候補接線ベクトルの導出で使用される段階/装置を説明する。
【図24】サーフェス法線を生成するためにパッチのコーナーにおいて3つの候補接線ベクトルを結合するために使用される段階/装置を説明する。
【発明を実施するための形態】
【0044】
本発明の実施形態を添付図面を参照してより詳細に説明する。
【0045】
本インターフェースは、パラメトリックモデリングユニット及びポリゴンベースのレンダリングシステムを使用した3次元グラフィックシステムでの使用を目的とするものであり、オブジェクトをモデリングするパラメトリックデータが、ポリゴンベースレンダリングシステムによって、該データを表示用に処理するために使用可能なフォーマットに変換されることができるようになる。
【0046】
図6はインターフェースのブロック図である。インターフェース10は、入力バッファ12、フォーマット変換器14、再帰バッファ16、細分割ユニット18、重み付けプロセッサ20、方向プロセッサ24、出力バッファ26、及び制御ユニット22を含む。
【0047】
パラメトリックモデリングユニットにおいて、パッチを用いてサーフェスを定義する。典型的な双三次パッチは、16個の制御点によって定義される。各制御点は、幾つかの要素(通常は(xyzw)位置、色、及びテクスチャマッピング情報を含む)を定義するN次元のベクトルである。典型的な3次元グラフィックシステムにおいては、各パッチのデータは制御点によってグループ化され、入力バッファ12を介してインターフェース10に入力されるのは、この制御点グループ化データである。細分割ユニットは、制御点ではなく要素によってデータをグループ化することを要求する。
【0048】
入力バッファ12は、制御点グループ化データを取り入れ、該データを細分割ユニット18によって要求される要素的なフォーマットに再配置して、これをフォーマット変換器に出力する。
【0049】
インターフェース10の細分割ユニットは、ベジェ双三次パッチとして知られる特別な標準のパッチを処理するように設計される。同様に、例えば、Catmull−Rom及びB−スプラインに基づく他のパッチのフォーマットも3次元モデリングで使用される。インターフェース10が他のパッチフォーマットを処理できるようにするために、フォーマット変換器14を設ける。入力バッファ12が出力する要素的データで表示されたパッチのフォーマットが決定される。データのフォーマットがベジェ双三次フォーマットではない場合には、フォーマット変換器14は、最適化された一連の行列乗算によりデータをベジェ双三次フォーマットに変換する。種々のパッチフォーマット間の変換方法は、3次元グラフィックの分野で公知であるので本明細書では説明しない。フォーマット変換器14は、変換アルゴリズムのライブラリを維持し、データに対して適切な変換アルゴリズムを適用して、ベジェ双三次フォーマットに変換する。
【0050】
再帰バッファ又はストア16は、2つのパッチ、すなわちルートパッチと中間パッチに対応するデータの記憶領域を与える。ルートパッチは各中間パッチに対する出発点であるので、細分割処理中に複数回アクセスする必要がある。中間パッチデータを再帰バッファ16内に格納すると、インターフェース内でのデータ転送が減少し、効率が改善されて処理時間が短縮される。再帰バッファ16のこの領域は中間結果用の作業領域を効果的に与える。
【0051】
要求レベルに対するパッチの細分割は、細分割ユニット18によって実行される。細分割ユニット18への入力は再帰バッファ16から供給される。細分割は4つのカテゴリ、すなわち、パッチの上半分を取り込むtの細分割、パッチの下半分を取り込むtの細分割、パッチの左半分を取り込むsの細分割、及びパッチの右半分を取り込むsの細分割に分けられる。
【0052】
ベジェパッチは16個の制御点を有し、制御点のデータは4×4行列で配列される。任意のカテゴリにおける第1レベルのパッチn−1から次のレベルのパッチnまでの細分割は、パッチデータに対して次の再帰方程式を適用することによって実現される。
ここで、Ai、Bi、Ci、及びDiは、細分割のカテゴリによる4×4制御点の行列の適切な要素を表す。要素の索引付けが制御される方法は、細分割の各カテゴリに関して以下で説明する。
【0053】
細分割の計算は、図7に示され且つ以下に説明されるように、演算をパイプライン形式にすることによって効率よく実行される。
【0054】
図7は下位計算ユニットを示す。下位計算ユニットに対する入力は、n−1番目レベルのパッチの4つの制御点値An-1、Bn-1、Cn-1、及びDn-1である。第1の計算段階は、並列に配置され各々が入力と第2の計算段階に結合された3つの加算器46、48、及び50を有する。加算器46の1つはまた第4の計算段階にも結合される。
【0055】
第2の計算段階は並列に配置された2つの加算器52及び54を含む。各加算器は、第1の計算段階の3つの加算器の2つの出力に結合される。1つの加算器52は第4の計算段階に直接結合される。加算器52及び54は両方とも第3の計算段階に結合される。
【0056】
第3の計算段階は、その入力として第2の計算段階の加算器52及び54の両方からの出力を取り込む単一の加算器56を含む。加算器56の出力は、第4の計算段階に結合される。
【0057】
第4の計算段階は、並列に配置された3つの除算器58、60、及び62を含み、これらはそれぞれ、加算器46の出力を2で除算し、加算器52の出力を4で除算し、加算器56の出力を8で除算する。
【0058】
下位計算ユニットが出力する出力は、n番目レベルのパッチ、すなわちAn=An-1の制御点の値であり、3つの除算器58、60、及び62の出力はそれぞれBn、Cn、及びDnである。
【0059】
パイプライン形式のシステムは、高速なシステムクロックを実現する。
【0060】
サブパッチにおける制御点値An、Bn、Cn、及びDnの計算は、細分されているパッチ内の対応する制御点値、An-1、Bn-1、Cn-1、及びDn-1からの一連の加算において下位計算ユニットにより実行される。計算の第1の段階は、該第1の段階における中間値P、Q、及びRの並列計算であり、ここで、
P=An-1+Bn-1
Q=Bn-1+Cn-1
R=Cn-1+Dn-1
である。
【0061】
第2の段階は、該第2の段階における中間値S及びTの並列計算であり、ここで、
S=P+Q
T=Q+R
である。
【0062】
第3の段階は、該第3の段階における中間値Uの計算であり、ここで、
U=S+T
である。
【0063】
第4の段階において、値V=P/2、W=S/4、及びX=U/8が並列計算され、値An=An-1、Bn=V、Cn=W、及びDn=Xが下位計算ユニットから出力される。
【0064】
各下位計算ユニットは、n番目レベルでのサブパッチ内の4つの新しい制御点の値を計算する。4つの新しい制御点の各セットの計算は、他の12個の制御点の計算とは独立している。このように、4つの下位計算ユニットを並列使用することによって、最小数のクロックサイクルでn番目レベルでのサブパッチの16個の新しい制御点を計算することが可能となり、高いスループットを達成することができる。4つの下位計算ユニットの出力は、出力マルチプレクサ(mux)44において組み立てられて、n番目レベルのサブパッチの制御点行列を生成する。
【0065】
下位計算ユニットは、細分割のどのカテゴリが実行されているかに応じて4×4の制御点行列の様々な要素上で動作することが要求される。しかしながら、細分割ユニットに入力及び出力マルチプレクサを組み込むことによって、4つの同一な細分割ユニットを使用して新しい制御点を計算することができる。入力及び出力マルチプレクサの機能について以下に説明する。
【0066】
<入力マルチプレクサ>
入力マルチプレクサの機能は、n−1番目レベルのパッチ制御点行列の行と列とを入れ替え、下位計算ユニットによって実行される細分割のカテゴリを制御できるようにすることである。
【0067】
t方向の細分割において、制御点行列の行はAからDまで索引付けられ、制御点行列の列は左から右に1から4まで索引付けられる。行における索引付けの方向は、上半分のパッチ又は下半分のパッチが生成されることになるかどうかによって決まる。上半分のパッチを生成するために、行は、行列の最上行としてAから始まって行列の最下行としてDで終了するように索引付けられる。このように、n番目レベルの上半分のサブパッチの制御点の最上行は、n−1番目レベルのパッチの制御点の最上行と同一である。n番目の上半分のサブパッチの残りの3つの行は、上の式1で定義されたn番目レベルのパッチの制御点の行に関係している。同様に、n番目レベルの下半分のサブパッチの制御点の最下行は、n−1番目レベルのサブパッチの制御点の最下行と同一であり、残りの行は式1と対応してn−1番目レベルの行列の行に関係する。
【0068】
図8a及び8bはそれぞれ、上半分のサブパッチを取り込むt方向の分割と、下半分のサブパッチを取り込むt方向の分割とを実行するための、n−1番目レベルのパッチの適切な索引付けを示す。このように、t方向の細分割から下半分を生成するためには、最初に行が反転されて、次に暫定的なデータを形成する上半分のサブパッチの生成に対して処理され、該データは次いで、必要とされるサブパッチデータを形成するように配列されなければならない。
【0069】
s方向の細分割においては、パッチの列はAからDに索引付けられ、行は上から下まで1から4に索引付けされる。列の索引付けの方向は、左のサブパッチ又は右のサブパッチのいずれかが生成されることになるかによって決まる。左半分のサブパッチを生成するためには、列はパッチの左側の列としてAから始まり、右側の列としてDで終わるように索引付けされる。従って、レベルの左半分のサブパッチの制御点の左側の列は、n−1番目レベルのパッチの制御点の左側の列と同一である。左半分のサブパッチの残り3つの列は、上の式1で定義されたようにn−1番目レベルのパッチの制御点の列に関係する。同様に、n番目レベルの右半分のサブパッチの制御点の右側の列は、n−1番目レベルのパッチの制御点の右側の列と同一であり、残りの列は式1と対応してn−1番目レベルのパッチの制御点の列に関係する。
【0070】
図8c及び8dは、左半分のサブパッチを取り込むs方向の分割と、右半分のサブパッチを取り込むs方向の分割とを実行するためのn−1番目レベルのパッチの適切な索引付けをそれぞれ示す。このように、s方向の細分割から左半分のサブパッチを生成するためには、最初にパッチの行と列を入れ替えて、再配置されたパッチを上半分のサブパッチの生成に対して処理することができる。同様にs方向の細分割から右半分のサブパッチを生成するためには、行を反転させて、次に行と列を入れ替える。t方向に分割された上半分のサブパッチの処理が実行され、結果として得られる制御点は出力マルチプレクサによって要求された右半分のサブパッチに対応するように再配置される。
【0071】
<出力マルチプレクサ>
出力マルチプレクサの機能は入力マルチプレクサの機能に類似している。該マルチプレクサは細分割のカテゴリに応じて、細分割ユニットによる暫定的なデータ出力を配置して、要求されたサブパッチ制御点行列を形成する。下位計算ユニットがt方向の上半分の細分割を実行するように設定されたと仮定すると、t方向の下半分の細分割とs方向の左及び右半分の細分割を生成するよう下位計算ユニットの出力を再配置する必要がある。出力マルチプレクサは下位計算ユニットの4つの出力を組み立てて単一の行列にし、入力マルチプレクサによって実行された再配置を反転させて、要求されたサブパッチ制御点行列を生成する。
【0072】
n番目レベルのサブパッチに対する要素的な制御データが、図7a、7b、7c、及び7dに示されるように細分割のカテゴリに従って適切な順序に組み立てられると、該データは、リーフパッチに関係する場合には重み付けプロセッサ20と方向プロセッサ24に出力され、或いは中間パッチに関係する場合には再帰バッファ16に戻される。
【0073】
インターフェースでは、図9に示されるように下位計算が実行される。この細分割のアーキテクチャの実行は、極めて効率的であることが分かっている。Watt & Wattで示された従来技術の方法はより多くの「計算」段階を必要とし、ハードウェア浮動小数点の実装の点で著しくコスト高になる可能性がある。細分割ユニット18は幾つかの段階を含む。各段階は1つのレベルの細分割を実行する。第2段階の細分割は、第1段階による処理の後に細分割の要求レベルが達成される場合にバイパスさせることができる。現在のところ好ましいとされる実施形態においては、2つの段階、すなわち第1の段階30と第2の段階32は、細分割ユニット18において実行される。2つの細分割段階を含むと、再帰バッファからの所定量のデータ帯域幅に対してシステムの原計算効率が向上するという利点がある。多くの段階は、最終のシステムにおいて要求されるサイズ/性能のトレードオフを与えるように変更することができる。各段階は、入力マルチプレクサ34、4つの下位計算プロセッサ36、38、40、42、及び出力マルチプレクサ44から成る。
【0074】
第1の段階では、パッチの要素のデータは再帰バッファ16から読み取られる。入力及び出力マルチプレクサ34及び44それぞれにより、要素の行列の行と列を再配置して実行される計算を制御することができるようになる。計算のオプションは以下の通りである。
s方向に細分割、左半分を出力,
s方向に細分割、右半分を出力,
t方向に細分割、上半分を出力,
t方向に細分割、下半分を出力,
バイパス
【0075】
入力マルチプレクサ34は、要求された細分割のカテゴリに応じて行列を再配置し、n−1番目レベルのパッチの4つの制御点を処理のために各下位計算ユニットに送る。各下位計算ユニットの出力はマルチプレクサ44に供給され、該マルチプレクサは下位計算ユニットの出力を組み立てて、要求された細分割のカテゴリに応じて必要とされたサブパッチに行列を再配置する。段階1の出力マルチプレクサ44からの出力は、段階2の入力マルチプレクサ34に対する入力として処理される。段階2の出力は、再帰バッファ16に送り返されるか、又はリーフパッチが達成された場合には次の計算段階に供給される。
【0076】
入力及び出力マルチプレクサを使用すると、下位計算ユニットの4つの別々のブロックの必要が無くなるので、湾曲サーフェス細分割システムの要素部品の数が最小になる。
【0077】
細分割ユニット18の演算は制御ユニット22から示される一連の命令によって制御される。制御ユニット22は、図10のフローチャートに示されるアルゴリズム上で動作する。制御ユニット22により、再帰バッファ16からルートパッチが取り込まれて、第1段階の入力マルチプレクサ34に送られる。
【0078】
パッチの4つのエッジに対応する4つのパッチの細分割レベルの割り当てが、ソフトウエア又はハードウェアのいずれかにおいて外部的に計算されていたと仮定する。
【0079】
制御ユニット22は、ルートパッチ制御行列の左エッジ及び右エッジの細分割値を調べることによって、t次元の細分割が必要とされるかどうかを判断する。左エッジ値及び右エッジ値のどちらも1.0と2.0の間の値にない場合は、t方向のパッチの細分割が必要とされる。左エッジ値及び右エッジ値は2で除算される。t方向に分割するコマンドは、制御ユニット22によって細分割ユニット18に送られ、これにより入力マルチプレクサによるデータの適切な再配置と、出力マルチプレクサによる暫定的なデータの配置とが行われる。t方向に分割されると、次に、上エッジ及び下エッジの新しい細分割値の計算が必要になる。上半分の細分割が実行される場合、制御行列の最上行は変化せず、上半分のサブパッチにおける最上部の値は、分割されていない行列から繰り越される。しかしながら、上半分の細分割は、分割されていない行列のものとは異なるサブパッチの最下行が得られる。従って最下部の値は更新されなければならない。新しい値は、分割されていない行列の上部値及び下部値の平均値又は好ましくは相乗平均値のいずれかとして計算される。相乗平均は、細分割のレベルをパッチ全体にわたってより有用に分布するので好ましい。下半分の細分割については、計算される必要があるのは細分割された行列の最上部の値であり、一方、最下エッジの値は分割されていない行列から繰り越される。最上エッジの値は上半分の細分割における最下エッジ部の値と同じ方法で計算される。
【0080】
制御ユニット22は、点の処理がs次元に進む終了条件に適合するまでt方向の細分割を継続する。パッチ全体のt方向のこれ以上の細分割が必要でないことを示す、左エッジ又は右エッジのいずれかの値が1.0と2.0の間にある時に終了条件は満たされる。しかしながら、結果としてのパッチが不規則な場合にはパッチの追加処理を必要とすることができる。不規則なパッチの処理は後で説明される。
【0081】
s方向の細分割が必要かどうかを判定するために試験される最上エッジ及び最下エッジの値を除いて、s方向の処理は同様にして進められる。新しい右エッジ及び左エッジの値が、左半分の細分割及び右半分の細分割のそれぞれに対して計算される。新しい右エッジ及び左エッジの値は、分割されていない行列の右エッジ及び左エッジの値の平均値又は好適には幾何平均値のいずれかとして計算される。s次元終了条件が満たされると、tが再チェックされて要求に合わせて処理が繰り替えされる。sの細分割に対する終了条件は、左エッジ及び右エッジのいずれかの値が1.0と2.0の間にある時に満たされる。tの細分割と同様に、パッチが不規則な場合には生じたパッチをさらに処理されるよう要求できる。
【0082】
s及びtの終了条件が両方とも満たされると、ルートパッチ又は中間パッチは、細分割の第1レベルに進んでおり、エンド点、リーフパッチを表すデータを生成している。次にコマンドは、制御ユニット22から細分割ユニット18に送られ、該リーフパッチデータを出力する。
【0083】
制御ユニット22は完成されたアルゴリズムを介してパスの数をモニタする。第1のパスでは、制御ユニット22は下位計算ユニット18に制御信号を送り、上半分のサブパッチにt方向の分割の計算を行わせ、左半分のサブパッチにs方向の分割の計算を行わせる。制御ユニット22から細分割ユニット18に送られたコマンドの履歴は記録される。次にこのコマンドの履歴は、他のすべてのシーケンスが確実に機能するよう後続のパスで使用される。制御ユニットアルゴリズムの最終のパスは、t方向への分割が常に下半分のサブパッチを出力として取り込み、s方向への分割が常に右半分のサブパッチを出力として取り込むときに実行されている。
【0084】
<規則的なリーフパッチの処理>
リーフパッチの最終エッジの値の各々が1.0と2.0の間である場合、リーフパッチは規則的であると言える。規則的なリーフパッチが処理されて、変換器により、図11に示されるようなパッチをカバーするように配置された三角形のグリッドの9つの頂点を生成する。好適には変換器はプロセッサ20を組み込む。三角形のテセレーションは、正方形の各辺に規則的配列で並べられた3つの頂点と、正方形の中心に配置された9番目の頂点とを有する正方形をカバーする。三角形は正方形を回転しながら扇形に配置され、その結果8つの三角形の各々は正方形の中心の頂点を共有する。図12に示され、従来技術でよく見られるような別のパターンもまた使用することができる。
【0085】
図12の構成に優る図11の構成の1つの利点は、生成される三角形が元のパッチの制御点の順序とは無関係になることである。すなわち、元のパッチのSとTの定義を入れ替えること、又は制御点の順序を反転させることは、同じ結果をもたらすことになる。第2の利点は、パターンが「不規則な」リーフパッチを処理するときに生成されたものに、より近いということである。
【0086】
リーフパッチから9つの出力頂点位置への変換は、「リーフパッチテセレーションユニット」20において実行される。これらの頂点に対応するサーフェス法線は、「サーフェス法線生成ユニット」24において同様に計算される。処理演算のこの段階において、ポリゴンポッピングを最小にするアルゴリズムが実行される。
【0087】
図16は規則的なパッチの制御点データからテセレーション三角形の9つの頂点への変換を概略的に示している。パッチの16の制御点は、該点がPijで索引付けられた4×4の行列で配列され、ここでjは0から3まで変わる行列の行を示し、且つ制御点は行0が最上行であるように配置されており、iは0から3まで変わる行列の列を示し、制御点は列0が左列であるように配置されていると仮定する。また、テセレーション三角形の9つの頂点が3×3の正方形で配列され、左上の頂点がV0に索引付けられ、索引付けは3×3の正方形を時計回りに左中央の頂点V7まで増分し、中央の頂点がV8に索引付けられると仮定する。
【0088】
テセレーション三角形の4つの外側の頂点は、規則的なリーフパッチの外側の制御点から直接導出される。左上の頂点V0は左上の制御点の値P00を取り込み、右上の頂点V2は右上の制御点の値P30を取り込み、左下の頂点V6は左下の制御点の値P03を取り込み、及び右下の頂点V4は右下の制御点の値P33を取り込む。
【0089】
残りの5つの頂点V1、V3、V5、V7、及びV8の取り込みは多少複雑である。
【0090】
図17の線図を考察すると、曲線は、コーナーの頂点の2つ(例えばV0及びV2)である点AとBを有するリーフパッチのエッジの1つであると考えることができる。さらに細分割が実行された場合には、これは、曲線C上に新しい点を生成することになり、該点は中間の頂点V1の可能な位置に対応する。反対に、細分割の数が同じままであった場合には、曲線は線ABで近似され、V1は点Dの線上に存在することになる。細分割のレベルが変化するときに点CとDの間で平滑な転移を実現するために、線分CDに沿って新しい点Eが計算され、これがV1の値として使用される。これは次の式で表される。
E=wC+(1−w)D …式2
ここでwは、エッジ細分割比率の小数部分から導出された重み付け因子、Dはリーフパッチの細分割レベルで導出された第1の頂点の値、及びCはサブリーフパッチの細分割レベルで導出された第2の頂点の値である。(エッジ比率の小数部分は、その値の2進浮動小数点表示の仮数部を調べることによって自明に得られる点に留意されたい)。
【0091】
Dは2つのコーナーの頂点、すなわち図16の場合では点A及びBにそれぞれ相当するV0及びV2の平均を取ることによって計算される。Cを計算するために、s方向の左半分の細分割が実行され、Cは左半分の細分割パッチの右上の制御点の値を取る。左(右)エッジに対するCの値を計算するために、リーフパッチの左(右)エッジに沿ったベジェ曲線をt=1/2において求める。これは、まさしく図7でのDnの計算に等しい点に留意されたい。最上エッジ及び最下エッジの「C」点の計算は類似している。Cの値(第2の値)とDの値(第1の値)が計算されると、頂点V1は式2に基づいて計算される。この計算は結合器によって実行される。結合器は、テセレーションユニット20の整数部分とすることができる。
【0092】
この計算はリーフパッチの四辺形の各エッジについて繰り返される。中央の点は同様の方法で計算されるが、しかしながらV8の点Cの計算はs及びt次元の両方で細分割を必要とする。これは、つまり最上エッジ及び最下エッジから計算された「C」の値を使用し、制御点の2つの中央の行から2つの追加の「C」値を計算して、次いでこれら4つの値の方法を再適用することにより効率的に行うことができる。
【0093】
V8のDの計算では、図11に示されたテセレーションパターンが好適であることから、頂点の対角線ペアの1つである、(V0、V4)又は(V2、V6)のいずれかが使用される。いずれの対角線ペアを選択するかは、ルートパッチに対するリーフパッチの相対的位置に基づく。図18aは16のリーフパッチについてルートパッチに対するリーフパッチの相対位置を表すチェッカーボード構成を示している。リーフパッチの正方形は、4行及び4列で配列され、ルートパッチをカバーする。交互配置パターンで正方形の半分には陰影が付けられ、残りの正方形には陰影が付けられていない。左上の正方形には陰影が付けられている。図18を参照すると、シェーディングされたリーフパッチは点Dの計算で(V0、V4)を使用し、一方、陰影が付けられていないリーフパッチのDの計算には(V2、V6)を使用する。リーフパッチの他の数については、同様のパターン化手法を適用する同様の線図を構成することができる。
【0094】
この好適なパターン化手法は、細分割レベルが「2つの境界のパワーをクロスさせる」ときに、三角形構成が急には変わらないことを保証する。細分割レベルが増大すると、生成された任意の新しい三角形は親の三角形に「内在する」ことが保証される。これは図18bに示される。例えば、より高度にテセレーションされた領域(右側に示される)の左上のリーフパッチ内に導入された中央の点は、「親」リーフ(左側)から中央の半対角線までの左上に依存することになる。これは図12に示された三角測量パターンには必要ではない代替の演算である点に留意されたい。
【0095】
<不規則パッチ処理>
細分割は、関連するエッジのいずれか1つの値が1.0と2.0との間にある場合に、s又はtの任意の方向で終了する。不規則である場合、すなわち1つ又はそれ以上のエッジの値が1.0から2.0の範囲の外にある場合には、リーフパッチのさらなる処理が必要とされる。不規則リーフパッチは、細分割値が隣接するパッチに結合させることが可能な範囲の外にあるエッジ上に追加の頂点を必要とする、規則的なリーフパッチと考えることができる。不規則リーフパッチは最初に規則的なリーフパッチとして取り扱われ、パッチの9つの頂点は上述のようにして計算される。追加の頂点を計算するために、さらなる細分割を実行する。さらなる細分割は、リーフパッチを形成するための細分割と同一の細分割ユニット内で実行することができ、制御ユニット22によって制御することができる。追加の頂点を得るための扇状パッチの変換は、リーフパッチ用の変換器内か、又は別の変換器内で実行することができる。
【0096】
右エッジの値が1.0から2.0の範囲外にある不規則リーフパッチに対する細分割処理の実施例は、図13a及び14に示される。この実施例では、右エッジの細分割値は2.0と4.0の間にあり、細分割の付加的レベルの1つは、クラッキングを防止するために、右エッジ上に必要な2つの余分の頂点(V23とV34)を生成することが求められることを示している。追加の頂点は、エッジの値が1.0から2.0の範囲外であるリーフパッチのエッジ上に設けられ、この場合は右エッジ上にある。追加の頂点によって記述された三角形はパッチの中央の頂点から扇状に広がり、このエッジにまたがる元の三角形を2つに分割する。このように、実施例では不規則パッチの右エッジは5つの頂点(3つではなく)、すなわち反時計回りにV2、V23、V3、V34、及びV4を有し、すべてがV8において共通の頂点を有する、V8−V2−V23、V8−V23−V3、V8−V3−V34、及びV8−V34−V4の4つの三角形を定義する。
【0097】
V23及びV34は、右エッジの値が1.0と2.0の間になるまで、t方向にさらなる細分割を実行することによって計算され、及び追加の細分割の出力を使用して新しい頂点V23とV34とを生成するのに使用される一連の扇状パッチを形成することによって計算される。扇状のパッチは、規則的なリーフパッチにおける頂点に相当する、9つの標準的な頂点であるV0からV8までの計算には使用されない。
【0098】
図13a及び14の不規則リーフパッチの追加の頂点を生成するために必要とされる処理を実施例を用いて説明する。以下の実施例により、当業者であれば、他の種類の不規則パッチの追加の頂点を生成する方法は明らかであろう。
【0099】
実施例では右エッジの値が2.0から4.0の範囲にあるときに、右エッジの値を1.0から2.0の範囲に入れるためには、細分割の1つだけのレベルが必要とされることが分かるであろう。不規則パッチの処理ステップは、図15のフローチャートに要約される。不規則パッチのエッジの値が試験され、どのエッジの値が1.0から2.0の範囲の外にあるかが判定される。処理はエッジ関係を基に進められる。図13a及び14に示された実施例の場合、右エッジの値だけが範囲外である。これはt方向の細分割だけが必要であることを示す。制御ユニット22は細分割ユニット18に適切なコマンド信号を送出し、不規則パッチをt方向に分割する。扇状パッチのエッジの値は、適切な一般的形態の細分割に関して前述のように計算される。18によって戻された上半分及び下半分のサブパッチは、追加の頂点V23及びV34を計算するために使用することができる上部及び下部扇状パッチを定義する。制御ユニット22は扇状パッチ形成の履歴を保持して、すべての適切な扇状パッチの形成を保証する。この場合、上半分の扇状パッチと下半分の扇状パッチの形成後、すべてのエッジの値は1.0と2.0の範囲内にあり、扇状パッチを形成するさらなる細分割は必要とされない。
【0100】
追加の頂点V23は、上述の式2に従って上部扇状パッチの中央右の頂点を計算することによって得られる。追加の頂点V24は、上の式2に従って下部扇状パッチの中央右側の頂点を見積もることによって計算される。
【0101】
扇状のパッチの他の頂点のいずれもテセレーションプロセスでは必要とされない。不規則なリーフポリゴンデータは、通常の細分割プロセスによって形成された頂点を結合して、リーフパッチ、「第1の複数の頂点」、及び扇状パッチから計算された追加の頂点、並びに「扇状パッチの値」を形成することによって生成される。
【0102】
<頂点のサーフェス法線の方向の計算に対する背景>
サーフェス法線生成ユニット24は、細分割ユニット18の出力を取り込み、各頂点に関係するサーフェス法線を計算する。(好適な実施形態では、ユニット20及び24は別個のものであるが、別の実施形態では、これらは共通している幾つかの計算値を共有することができることに留意されたい)。サーフェス法線は、サンプルの点においてモデリングされているサーフェスが面している方向を示すのに使用され、後続のライティングとテクスチャの計算のために必要とされる。方向プロセッサ24は、不規則パッチから計算された任意の追加の頂点を含むリーフパッチの各々の頂点に対する法線を計算する。ポリゴンポッピングのシェーディングされた相似形を最小にするために、式2による前述のような線形補間法が、内部頂点の法線に対して適用され、すなわち出力法線は隣接する頂点の法線と「正しい」法線の混合とすることができる。
【0103】
理想的には該出力法線は実際には「混合」されるべき最終のシェーディング及びテクスチャ値である点に留意されたい。好適な実施形態では、外部グラフィックス標準(例えば、MicrosoftのDirectX)によって制約を受けているためにこれは行われない。頂点のシェーディングが計算された後でこれらの制約は取り除かれるべきである場合には、呈示された「ポリゴンポッピングの減少」法を容易に適用できることは同業者には明らかである。
【0104】
従来技術において知られているように、非有理的ベジェパッチのコーナーに配置された4つの頂点については、サーフェス法線の計算はより簡単なはずである。この実施例は図19に示されている。本発明はこの原理を有理パッチを用いる用途に適合させる。
【0105】
最初は4つの点だけがリーフパッチのコーナーに存在するので、本発明ではリーフの追加の「部分的な」細分割が実行される。この処理は図20に示される。規則的なリーフパッチの9つの頂点の場合(番号付けは図11で使用されているもの)、3つの追加の部分的細分割(1つはS方向(図20(iii))、1つはT方向(図20(ii))、及び追加の細分割(図20(iv))は、V1、V3、V5、V7、及びV8の位置が少なくとも1つのサブパッチのコーナーであるように、子のサブパッチを生成するのに十分である。頂点の法線を生成するためには各サブパッチのすべての制御点が必要ではなく、好適な実施形態では必要最小限の制御点だけが計算されることに留意されたい。図20では、(コーナーの法線の計算のため、又は必要な子のパッチの制御点を生成のためのいずれかが直接的に)必要とされる制御点は灰色又は黒で示され、一方、必要とされないものは白で示される。
【0106】
上記のように、本発明は有理ベジェパッチの法線を効率的な方法で計算するが、その方法及び背景理由を以下に示す。
パラメータ位置(s、t)(s、t)における有理サーフェスの位置は以下の式で与えられる。
一方、(0,0)における(a,b)方向の単位長さの接線ベクトルの定義は次式で与えられる。
【0107】
式中の「差分」項を考察すると、次式が得られる。
これは、以下のことを意味する。
【0108】
スカラー値w(ea,eb)w(0,0)が正でありゼロではないので、これは上の制約式の上部と下部の両方に適用することができ、次式で与えられる。
【0109】
有理的なベジェパラメトリックサーフェスに限定して注目し、ベジェパッチの(0,0)(0,0)点が
の制御点に相当する点に留意すると、次式の挙動を調べる必要がある。
【0110】
便宜上、以下のように定義する。
【0111】
好適な実施形態では、ベジェ関数は双三次である。より高次のサーフェスを使用する実施形態に対するこの手法の拡張は、当業者に容易なものでなければならない。
【0112】
取得される行列形式の(ea,eb)において(すなわちw成分によるx、y、及びz成分の除法の前に)双三次の均質なベジェサーフェスを表す。
【0113】
従って、これは次のように表し得ることが分かる。
【0114】
Q行列の特定の特性に留意すると、これは次のように簡略化される。
これは以下のように変形される。
【0115】
本発明の方法は、「S」、「T」、及び「対角線」の接線候補である最大3つまでの可能性のある接線候補を計算する。
【0116】
<「S」方向の候補接線ベクトルの導出>
【0117】
「S」方向の接線ベクトルを生成する場合を考えると、式3と4はそれぞれ次のように変形される。
【0118】
を考察すると、次の式が求められる。
【0119】
ここで次の3つの場合が考えられる
1.
2.
3.
【0120】
上のケースの各々に関して、e→0のような極限値が分子と分母の両方に存在すると(及び極限値がゼロでない)場合、式全体の極限値が存在することが計算から分かる。
【0121】
ケース1:
分子/分母の「内容」から始めると、次式が得られる。
【0122】
の場合に限り、極限値は明らかに存在し且つゼロではない。
この条件が成り立つ場合は、S方向の接線ベクトルは次の式で与えられる。
この点ではベクトルの長さは重要ではないことに留意されたい。
【0123】
ケース2:
ケース1の条件が当てはまらない場合、
は、ケース2の極限値が調べられ、次式が与えられる。
【0124】
であることに留意すると、上式の和の第2の部分は、0と仮定されたケース1の結果と同じであることが分かる。従って次式が得られる。
【0125】
同様に、
と仮定していたので、これは次式になる。
【0126】
従って、選択された条件が成り立つ場合、これが0でなければ次のような有効な「S」正接が存在する。
【0127】
ケース3:
ケース2及び3が両方とも成り立たない場合には、示されたのと同じ引数を使用して、0でないという前提で次式によって「S」を計算することができる。
【0128】
<「T」方向の候補接線ベクトルの導出>
これはまさしく「S」正接と同じ論証に従うので、ここでは説明しない。
【0129】
【0130】
【0131】
上述の方法では、特定のコーナーの頂点の法線を計算するために、最大9つまでの制御点が必要とされる可能性があることは明らかである。図21は、V0(すなわち、(s、t)=(0,0))のコーナー頂点の場合における組を示す。制御点の選択は、計算される頂点の法線に応じて変わるので、残りの説明では別の命名法が適用されることになろう。特定の頂点の法線を計算するために使用される制御点は、C、S1、S2、S3、T1、T2、T3、及びDと呼ばれる。また、実施例として、この命名法と頂点V0に必要な制御頂点の間の相関性は図21に示される。
【0132】
<「サーフェス法線生成ユニット」の好適な実施形態>
ここでサーフェス法線生成ユニット24を図22aに関連して説明する。
【0133】
リーフパッチの制御点が提供され(200)、頂点V0、V2、V4、及びV6の各々に対して正しい8つの制御点(C、S1、S2、S3、T1、T2、T3、D)の組が選択され(201)、次にコーナー法線ユニットに供給される(202)。サーフェス法線生成ユニットにおいては、制御点の成分X、Y、Z、及びWだけが必要とされる点に留意されたい。
【0134】
ユニット201は、元のリーフパッチ制御点のどれが8つの点の4つの組の各々に対応するかを選択するMUXである。好適な実施形態では、4つの選択は以下の通りである。
頂点V0:これは図21に示されている。
【0135】
好適な実施形態では、「仮想の」S、T及び対角線の正接候補の方向は、後続のコーナー頂点に対して90°だけ回転している点に留意されたい。
【0136】
代替の実施形態では、実在する軸方向のミラーリングによる制御点の選択を使用することができるが、外積の結果が相殺されるべきかどうかを示すために、これはユニット「202」に供給されるべきフラッグの追加を必要とする。このような相殺は少なくとも頂点V2とV6に対して示されるべきであった。(頂点V4は両方の軸が反転されるので相殺を必要としないであろう)。
【0137】
ユニット203は、頂点V1及びV5のサーフェス法線を生成するのに適した新しい制御点を計算するために、リーフパッチの部分的な細分割を実行する。必要とされるセットは図20(iii)に示されている。ユニット204は、V1とV5の各々に対してそれぞれ必要とされる点を選択する別のマルチプレクサであり、該点をコーナー法線ユニット202に供給する。選択プロセスはユニット201のプロセスに類似しており、事前の説明があれば当業者にとっては明らかなはずである。
【0138】
同様な方法で、ユニット205及び206は、頂点V3及びV7の法線のために必要な2セットの制御点を生成する(図20(iii)参照)。
【0139】
ユニット207及び208は、V8のサーフェス法線を生成するのに必要な8つの制御点のセットを生成する。この組は図20(iv)に示される。図20(iv)の右エッジに示された4つの制御点は、図20(ii)の右エッジの1回の細分割によって得ることができ、一方、下エッジの制御点は、図20(iii)の下エッジの1回の細分割から計算される点に留意すべきである。「D」に対応する制御点は、図20(iii)の下から2番目の行か、又は代替として20(ii)の右から2番目の列のいずれかから得ることができる。
【0140】
性能的に、好適な実施形態は、複数のユニットとパイプライン形式のアーキテクチャとを組み合わせることにより、幾つかの頂点法線の計算が部分的に重なる。代替の実施形態では、並列処理のレベルはコスト/性能のトレードオフに応じて変えることができる。
【0141】
次に「コーナー法線ユニット」202を図22bと関連して説明する。この図は、理解しやすいように単一の法線の計算だけを説明している点に留意すべきである。8つの選択された制御点が入力される(220)。C点と3つのS点は「S候補」計算ユニット(221)に送られ、C点及び3つのT点は「T候補」計算ユニット(222)に送られると共に、C及びDは「対角線候補」ユニットに送られる。次に、3つの計算された正接候補TS、TT、及びTDiagは「候補選択及び法線計算」ユニット(224)に入力される。
【0142】
【0143】
別の実施形態では、追加の「最適化」を組み込んで、任意選択的に乗算を実行する前に、wすなわち「重み付け」要素の値が同一であるかどうかを最初に調べる。これはパッチが非有理的である場合、すなわちwの値が一定である場合の計算遅延を潜在的に低減することができる。
【0144】
従って、1つのベクトル減算ユニットだけが必要とされ、好適な実施形態ではこれはパイプライン形式である点に留意されたい。別の実施形態では、減算ユニットはまた、ユニット222及び223と共有することが可能である。
ユニット222はTTを計算すること以外はユニット221と同一であり、一方、ユニット223は単にTDiag=DXYZCW−CXYZDWを計算するだけである。
【0145】
次にユニット224を図24に関連して説明する。試験250及び252は、TS又はTTのいずれかを0ベクトルとすることができる特別な場合をチェックし、それぞれ−TT(251)又はTS(253)のいずれかである中間ベクトルTNZに設定する。両方のベクトルが0でない場合には、TS及びTTのベクトルの外積を取ることによって、ステップ254で候補サーフェス法線が生成される。次いで、候補法線は0に対して比較される(255)。0でない場合には、サーフェス法線として使用される(256)。0である場合には、ステップ253で中間ベクトルが設定される。
【0146】
中間ベクトルが必要とされた場合には、別の法線の計算が使用される(257)。これは中間ベクトルの外積と対角線の正接候補を計算する。ステップ251でTNZがマイナスのTTとして送られたことに留意すべきである。これは法線の方向の整合性を保つために行われる。浮動小数点の相殺が自明であることは理解されたい。
【0147】
前述のように、このようにして頂点V1、V3、V5、V7、及びV8について計算された法線は、これらの頂点をリーフパッチ内における最大の小数部分の細分割レベルで表示する。より小さな小数部分レベルについては、ポリゴンポッピングを除去するために使用された同じブレンディングプロセスが同様に適用され、最終的な法線ベクトルの結果を生成する。同様に不規則パッチの法線の計算は、前述したものと類似した追加のレベルの細分割を受けなければならない。
【0148】
このように本発明では、費用のかかる分割演算を必要とせずに有理ベジェサーフェスに対するサーフェス法線を計算することを理解されたい。これは有意な節約である。好適な実施形態では、出力される法線は単位ベクトルではなく、すなわち、好適な実施形態では、後続のシェーディング及び変換ユニット(本明細書には記載されていない)は、必要に応じてこの簡単なタスクを実行することが可能であると仮定する。
【0149】
図6を参照すると、パイプライン形式のテセレーション処理の最終段階は出力バッファ26内で実行される。入力バッファ12は、制御点(ポイント)を取得し、データをグループ化して、データを要素毎に再配置した。出力バッファ26は、頂点毎に計算段階からのデータをグループ化する反転タスクを実行することが必要とされる。出力バッファ26は、重み付けプロセッサ24によって計算された頂点と、サーフェス法線プロセッサ24によって計算された法線とを取り込み、各要素のデータを頂点毎に共にグループ化してこれを出力し、ディスプレー用に画像の変換、ライティング、テクスチャリング、及びラスタライゼーションで続いて使用する。
【0150】
特定の図に関連して説明され且つ説明の様々な点で説明された特徴は、特に説明又は図示されたもの以外を組み合わせて使用することができることに留意されたい。このような変更はすべて、以下の請求項に記載の本発明の範囲内に包含される。
【0151】
上記説明に関して、当業者であれば均等な装置及び方法を容易に思いつくことができ、且つ図面に示され本明細書に記載されたものに均等なすべての装置及び方法は、本発明に包含されることが意図されるものであることは理解されるべきである。従って、前述のものは本発明の原理のみを示すものと考えるべきである。さらに、当業者には多くの修正及び変更を容易に行うことができるので、本発明を図示及び説明された厳密な構成及び実施に限定することは望ましいものではなく、従ってすべての適切な修正及び均等物は本発明の範囲として行使され且つ包含されることになる。
【0152】
例えば、テセレーション三角形の代替のパターンは本発明の範囲内に包含されると考えられる。
【符号の説明】
【0153】
10 インターフェース
12 入力バッファ
14 フォーマット変換器
16 再帰バッファ
18 細分割ユニット
20 リーフパッチテセレーションユニット
22 制御ユニット
24 サーフェス法線生成ユニット
26 出力バッファ
【特許請求の範囲】
【請求項1】
システムによってシェーディングされることになるオブジェクトのモデリングに使用されるサーフェスパッチの頂点に対するサーフェス法線ベクトルを求めるための装置を備える3次元グラフィックシステムであって、
各々がコーナー頂点を有する複数のサブパッチを生成するために前記パッチを細分割する手段と、
頂点に対するサーフェス法線を導出するために必要とされる制御ポイントの位置を導出する手段と、
前記制御ポイントの位置から頂点における複数の候補正接ベクトルを導出する手段と、 前記候補正接ベクトルからサーフェス法線を導出する手段と、
を含む装置を備えるシステム。
【請求項2】
3次元グラフィックシステムにおいてシェーディングされることになるオブジェクトのモデリングに使用されるサーフェスパッチの頂点に対してサーフェス法線ベクトルを求める方法であって、
各々がコーナー頂点を有する複数のサブパッチを生成するために前記パッチを細分割し、
頂点に対するサーフェス法線を求めるために必要とされる制御ポイントの位置を導出し、
前記制御ポイントデータから頂点における複数の候補正接ベクトルを導出し、
前記候補正接ベクトルからサーフェス法線を導出する、
各段階を含む方法。
【請求項3】
前記制御ポイントの位置を導出する段階が、
選択されたコーナーに隣接する前記パッチの1つのエッジに沿って制御ポイントの第1のサブセットを導出し、
前記選択されたコーナーに隣接する前記パッチの別のエッジに沿って制御ポイントの第2のサブセットを導出し、
選択されたパラメータ次元のセットの各々において前記パッチのコーナーから制御ポイントオフセットから成る制御ポイントの第3のサブセットを導出する、
段階を含み、
複数の候補正接ベクトルを導出する前記段階は、制御ポイントのそれぞれの各サブセットと前記コーナーポイントとから第1、第2、及び第3の候補正接ベクトルを導出する段階と、前記選択されたコーナーでサーフェス法線を導出するために前記3つの候補正接ベクトルの内の2つを選択する段階を含むことを特徴とする請求項2に記載の方法。
【請求項4】
3次元グラフィックシステムでシェーディングされることになるオブジェクトのモデリングで使用されるサーフェスパッチの頂点に対するサーフェス法線ベクトルを求める方法であって、
4つのコーナーの頂点に対してサーフェス法線を導出し、
第1のサブパッチの制御ポイントの第1のサブセットを導出するために前記パッチを第1のパラメータ次元に部分的に細分割し、
第2のサブパッチの制御ポイントの第2のサブセットを導出するために第2のパラメータの次元に部分的に細分割し、
前記制御ポイントの第1及び第2のサブセットから制御ポイントの第3のサブセットを導出するために第3の部分的な細分割を実行し、
前記制御ポイントの第1のサブセットを使用して2つの中間ポイントの頂点に対するサーフェス法線を導出し、
前記制御ポイントの第2のサブセットから残りの2つの中間ポイントの頂点に対するサーフェス法線を導出し、
前記制御ポイントの第3のサブセットから前記パッチの中心の頂点に対するサーフェス法線を導出する、
段階を含む方法。
【請求項5】
コーナーの制御ポイントにおける候補正接ベクトルが、
制御ポイントの所定のサブセットから任意の所与の順番で制御ポイントを選択する段階と、
選択された制御ポイントの成分と前記コーナーの制御ポイントの重み付け成分とを乗算することによって第1の重み付けされたベクトルを導出する段階と、
前記コーナーの制御ポイントの成分と選択された制御ポイントの重み付けベクトルとを乗算することによって第2の重み付けされたベクトルを導出する段階と、
前記第1と第2の重み付けされたベクトル間の差分ベクトルを導出する段階と、
前記差分ベクトルが0の場合には該差分ベクトルを前記候補正接ベクトルとして使用し、0でない場合には前記サブセットの次の制御ポイントに進む段階と、
を繰り返すことによって導出されることを特徴とする請求項2又は3の何れか1項に記載の方法。
【請求項1】
システムによってシェーディングされることになるオブジェクトのモデリングに使用されるサーフェスパッチの頂点に対するサーフェス法線ベクトルを求めるための装置を備える3次元グラフィックシステムであって、
各々がコーナー頂点を有する複数のサブパッチを生成するために前記パッチを細分割する手段と、
頂点に対するサーフェス法線を導出するために必要とされる制御ポイントの位置を導出する手段と、
前記制御ポイントの位置から頂点における複数の候補正接ベクトルを導出する手段と、 前記候補正接ベクトルからサーフェス法線を導出する手段と、
を含む装置を備えるシステム。
【請求項2】
3次元グラフィックシステムにおいてシェーディングされることになるオブジェクトのモデリングに使用されるサーフェスパッチの頂点に対してサーフェス法線ベクトルを求める方法であって、
各々がコーナー頂点を有する複数のサブパッチを生成するために前記パッチを細分割し、
頂点に対するサーフェス法線を求めるために必要とされる制御ポイントの位置を導出し、
前記制御ポイントデータから頂点における複数の候補正接ベクトルを導出し、
前記候補正接ベクトルからサーフェス法線を導出する、
各段階を含む方法。
【請求項3】
前記制御ポイントの位置を導出する段階が、
選択されたコーナーに隣接する前記パッチの1つのエッジに沿って制御ポイントの第1のサブセットを導出し、
前記選択されたコーナーに隣接する前記パッチの別のエッジに沿って制御ポイントの第2のサブセットを導出し、
選択されたパラメータ次元のセットの各々において前記パッチのコーナーから制御ポイントオフセットから成る制御ポイントの第3のサブセットを導出する、
段階を含み、
複数の候補正接ベクトルを導出する前記段階は、制御ポイントのそれぞれの各サブセットと前記コーナーポイントとから第1、第2、及び第3の候補正接ベクトルを導出する段階と、前記選択されたコーナーでサーフェス法線を導出するために前記3つの候補正接ベクトルの内の2つを選択する段階を含むことを特徴とする請求項2に記載の方法。
【請求項4】
3次元グラフィックシステムでシェーディングされることになるオブジェクトのモデリングで使用されるサーフェスパッチの頂点に対するサーフェス法線ベクトルを求める方法であって、
4つのコーナーの頂点に対してサーフェス法線を導出し、
第1のサブパッチの制御ポイントの第1のサブセットを導出するために前記パッチを第1のパラメータ次元に部分的に細分割し、
第2のサブパッチの制御ポイントの第2のサブセットを導出するために第2のパラメータの次元に部分的に細分割し、
前記制御ポイントの第1及び第2のサブセットから制御ポイントの第3のサブセットを導出するために第3の部分的な細分割を実行し、
前記制御ポイントの第1のサブセットを使用して2つの中間ポイントの頂点に対するサーフェス法線を導出し、
前記制御ポイントの第2のサブセットから残りの2つの中間ポイントの頂点に対するサーフェス法線を導出し、
前記制御ポイントの第3のサブセットから前記パッチの中心の頂点に対するサーフェス法線を導出する、
段階を含む方法。
【請求項5】
コーナーの制御ポイントにおける候補正接ベクトルが、
制御ポイントの所定のサブセットから任意の所与の順番で制御ポイントを選択する段階と、
選択された制御ポイントの成分と前記コーナーの制御ポイントの重み付け成分とを乗算することによって第1の重み付けされたベクトルを導出する段階と、
前記コーナーの制御ポイントの成分と選択された制御ポイントの重み付けベクトルとを乗算することによって第2の重み付けされたベクトルを導出する段階と、
前記第1と第2の重み付けされたベクトル間の差分ベクトルを導出する段階と、
前記差分ベクトルが0の場合には該差分ベクトルを前記候補正接ベクトルとして使用し、0でない場合には前記サブセットの次の制御ポイントに進む段階と、
を繰り返すことによって導出されることを特徴とする請求項2又は3の何れか1項に記載の方法。
【図1a】
【図1b】
【図2】
【図3a】
【図3b】
【図4】
【図5a】
【図5b】
【図5c】
【図6】
【図7】
【図8a】
【図8b】
【図8c】
【図8d】
【図9】
【図10】
【図11】
【図12】
【図13a】
【図13b】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【図1b】
【図2】
【図3a】
【図3b】
【図4】
【図5a】
【図5b】
【図5c】
【図6】
【図7】
【図8a】
【図8b】
【図8c】
【図8d】
【図9】
【図10】
【図11】
【図12】
【図13a】
【図13b】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【公開番号】特開2010−191991(P2010−191991A)
【公開日】平成22年9月2日(2010.9.2)
【国際特許分類】
【出願番号】特願2010−103076(P2010−103076)
【出願日】平成22年4月28日(2010.4.28)
【分割の表示】特願2004−504186(P2004−504186)の分割
【原出願日】平成15年5月8日(2003.5.8)
【出願人】(501176037)イマジネイション テクノロジーズ リミテッド (59)
【Fターム(参考)】
【公開日】平成22年9月2日(2010.9.2)
【国際特許分類】
【出願日】平成22年4月28日(2010.4.28)
【分割の表示】特願2004−504186(P2004−504186)の分割
【原出願日】平成15年5月8日(2003.5.8)
【出願人】(501176037)イマジネイション テクノロジーズ リミテッド (59)
【Fターム(参考)】
[ Back to top ]