(57)【特許請求の範囲】
【請求項１】
頂点により規定される３次元多面体、すなわち
それぞれ対応する多面体Ｐが頂点（ｖ）、グロー法線（ｎ）、および面分（ｆ）を有し、
該頂点、グロー法線、および面分に関して次の定義を有する、
すなわち頂点は３Ｄ座標（ｘ，ｙ，ｚ）であり、面分は頂点（ｖｉ，ｖｊ，ｖｋ）によって形成される三角形を示すトリプレット（ｉ，ｊ，ｋ）であり、それぞれの面分の頂点は関連するベクトルｆｎ＝（ｖｊ−ｖｉ）×（ｖｋ−ｖｉ）が多面体の外側を指示するように配向されており、該ベクトルはここでは面分（ｉ，ｊ，ｋ）の面分法線と称され、グロー法線は頂点に関連するベクトルである、
３次元多面体を有する対象物の表面をスムージングするコンピュータグラフィック処理方法において、
処理装置により、
頂点ｖを一時的なコピーｖ’として記憶するステップと、
頂点ｖにガウシアンスムージングを適用し、充分な度合で対象物のスムージングが達成されるまで複数回反復して滑らかな対象物を得るステップと、
滑らかな対象物を用いてグロー法線の新たな集合を補間するステップと、
予め存在していた法線と新たな法線の集合とを置換するステップと、
頂点ｖ’をｖに戻すステップと、
グロー法線の新たな集合を表現する出力多面体を出力するステップと
を実行する
ことを特徴とする３次元多面体を有する対象物の表面をスムージングするコンピュータグラフィック処理方法。
【請求項２】
グロー法線の新たな集合を補間するステップは、頂点ｖiでのグロー法線を計算するステップを有する、請求項１記載の方法。
【請求項３】
ガウシアンスムージングを適用し、充分な度合で対象物のスムージングが充分な度合で達成されるまで複数回反復して滑らかな対象物を得るステップにより対象物の縮小を生じさせる、請求項１記載の方法。
【請求項４】
ガウシアンスムージングを適用するステップを、
【数１】
0004383585.tif 000007
ここでＩiはｖiとエッジを共有する全ての頂点のインデクスの集合であり、ｗijは重みづけウェイトである
により行う、請求項１記載の方法。
【請求項５】
重みづけウェイトはｗij＝１／ｎiであり、ここでｎiはｖiとエッジを共有する頂点の数である、請求項４記載の方法。
【請求項６】
重みづけウェイトは
【数２】
0004383585.tif 000008
である、請求項４記載の方法。
【請求項７】
頂点ｖiでのグロー法線を計算するステップを、次のアルゴリズム、すなわちグロー法線
【数３】
0004383585.tif 000009
ここでＩiは頂点ｖiを有する全ての面分ｆの面分インデクスの集合であり、ｆｎjは面分ｆjの面分法線であり、重みづけ係数ｗjは所定である
で行う、請求項２記載の方法。
【請求項８】
重みづけ係数ｗjは面分ｆjの領域である、請求項７記載の方法。
【請求項９】
重みづけ係数ｗjは頂点ｖiを共有する面分ｆjの２つのエッジの間の角度である、請求項７記載の方法。
【請求項１０】
重みづけ係数は１である、請求項７記載の方法。
【請求項１１】
多面体の表面エレメント、すなわち
それぞれ対応する多面体Ｐを頂点（ｖ）、グロー法線（ｎ）、および面分（ｆ）で表し、
頂点は３Ｄ座標（ｘ，ｙ，ｚ）を有し、面分は頂点（ｖｉ，ｖｊ，ｖｋ）によって形成される三角形を示すトリプレット（ｉ，ｊ，ｋ）であり、それぞれの面分の頂点は関連するベクトルｆｎ＝（ｖｊ−ｖｉ）×（ｖｋ−ｖｉ）が多面体の外側を指示するように配向されており、該ベクトルはここでは面分（ｉ，ｊ，ｋ）の面分法線と称され、グロー法線は頂点に関連するベクトルである、
多面体の表面エレメントを有する対象物の表面をスムージングするコンピュータグラフィック処理方法において、
処理装置により、
対応する頂点にガウシアンスムージングを適用するステップと、
前記ステップを反復して滑らかな対象物の表面を得るステップと、
滑らかな対象物のグロー法線を計算するステップと、
頂点を対応する初期の位置に戻すステップと
を実行する
ことを特徴とする多面体の表面エレメントを有する対象物の表面をスムージングするコンピュータグラフィック処理方法。
【請求項１２】
滑らかな表面のグロー法線を計算するステップを、グロー法線すなわち
【数４】
0004383585.tif 000010
ここでＩiは頂点ｖiを有する全ての面分ｆの面分インデクスの集合であり、ｆｎjは面分ｆjの面分法線であり、重みづけ係数ｗjは所定である
に相応して行う、請求項１１記載の方法。
【請求項１３】
重みづけ係数ｗjは面分ｆjの領域である、請求項１２記載の方法。
【請求項１４】
重みづけ係数ｗjは頂点ｖiを共有する面分ｆjの２つのエッジの間の角度である、請求項１２記載の方法。
【請求項１５】
重みづけ係数は１である、請求項１２記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、頂点により規定される３次元多面体、すなわちそれぞれ対応する多面体Ｐが頂点、グロー法線、および面分を有し、該頂点、グロー法線、および面分に関して次の定義を有する、すなわち頂点は３Ｄ座標（ｘ，ｙ，ｚ）であり、面分は頂点（ｖｉ，ｖｊ，ｖｋ）によって形成される三角形を示すトリプレット（ｉ，ｊ，ｋ）であり、それぞれの面分の頂点は関連するベクトルｆｎ＝（ｖｊ−ｖｉ）×（ｖｋ−ｖｉ）が多面体の外側を指示するように配向されており、該ベクトルはここでは面分（ｉ，ｊ，ｋ）の面分法線と称され、グロー法線は頂点に関連するベクトルである、３次元多面体を有する対象物の表面をスムージングするコンピュータグラフィック処理方法に関する。本発明はまた、多面体の表面エレメント、すなわちそれぞれ対応する多面体Ｐを頂点、グロー法線、および面分で表し、頂点は３Ｄ座標（ｘ，ｙ，ｚ）を有し、面分は頂点（ｖｉ，ｖｊ，ｖｋ）によって形成される三角形を示すトリプレット（ｉ，ｊ，ｋ）であり、それぞれの面分の頂点は関連するベクトルｆｎ＝（ｖｊ−ｖｉ）×（ｖｋ−ｖｉ）が多面体の外側を指示するように配向されており、該ベクトルはここでは面分（ｉ，ｊ，ｋ）の面分法線と称され、グロー法線は頂点に関連するベクトルである、多面体の表面エレメントを有する対象物の表面をスムージングするコンピュータグラフィック処理方法に関する。
【０００２】
【従来の技術】
画像のサイエンティフィックビジュアライゼーションでは、滑らかな対象物の画像を多面体の表面エレメントで表し、離散的な標本ポイントの集合として構成することが多い。このタイプの表現はいくらか不自然な印象の“切り子面”形状の外観を呈する傾向がある。これは基本的には一種の量子化エラーである。望ましくないこの“切り子面”形状の外観を回避または低減するために、種々のスムージング技術が適用されている。
【０００３】
通常使用されているこの種の技術はグローシェーディングである。これについては例えば H.Gouraud, "Continuous Shading of Curved Surfaces", IEEE Trans. on Computers, vol.C-20, 623頁〜629頁を参照されたい。ここでは表面エレメントを形成している多面体の形状を実際に変更はしないが、ディスプレイにレンダリングする際に、法線から成る切り子面の共有の頂点での輝度を補完することにより、滑らかな外観を形成している。各頂点では、この頂点を共有する切り子面の法線の重みづけ平均としてグロー法線が計算される。レンダリングされると、それぞれの頂点での輝度はグロー法線に基づいて計算され、切り子面の内部で線形的に補完される。共有されている頂点は同じグロー法線を有しているので輝度の跳躍的変化はなく、表面全体が滑らかに見えるようになる。
【０００４】
グローシェーディングは、多面体の表面に凹凸がある場合にはサンプリングエラーが発生するために充分な効果が得られない。これは表面の実際のジオメトリックな欠陥が隠されないからである。高密度にサンプリングされた表面のサンプリングエラーがサンプリング間隔に近似する場合には、グローシェーディングを用いても表面は粗雑に見える。
【０００５】
ジオメトリックスムージングはこのような表面を改善するのに用いられる。その１つの技術にガウシアンスムージング法がある。例えば G.Taubin "Curve andsurface smoothing without shrinkage", Fifth Inernat. Conference on Computer Vision, June 1995 852頁〜857頁、および G.Taubin "Curve and surface smoothing without shrinkage", Technical Report RC-19536, IBM Research, April 1994 を参照されたい。それぞれの頂点の新しい位置ｖi'は現在の頂点の位置自体と隣接する頂点との重みづけ平均として計算され、現在の頂点とエッジを共有している頂点が計算される。
【０００６】
ｖi'は
【０００７】
【数５】
0004383585.tif 000002
【０００８】
から得られる。ここでＩiはｖiとエッジを共有する全ての頂点のインデクスの集合であり、λはスケール係数であって０＜λ＜１であり、Ｗijは適切な重みづけウェイトであって現在の頂点から隣接する頂点までの距離の逆数であり、ポイントどうしが近くなるにつれてその影響も大きくなる。例えば、ジオメトリックスムージングのための重みづけウェイトＷijは
【０００９】
【数６】
0004383585.tif 000003
【００１０】
であり、これは距離の逆数である。そうでなければｖiは単純に１／ｎiとして定められ、ここでのｎiはｖiとエッジを共有している頂点の数である。このプロセスは、所望の滑らかさが得られるまで何度も繰り返される。
【００１１】
この手法は複数の利点を有している。任意のトポロジーの区分的線形表面に適用される。これは簡単に利用でき、隣接する頂点は簡単に多面体の表現から得られるので付加的な記憶装置も必要ない。また頂点の数に対して線形である。
【００１２】
ただしこの手法の大きな欠点は、他の多くの手法と同じくモデルを縮小してしまうことである。一般的にはスムージングを達成するには複数回の反復が必要なので、縮小は重大な欠点である。
【００１３】
この縮小化の問題を回避するために、従来、修正されたガウシアンスムージング法を用いることが提案されている。これは式（１）で表されるガウシアンスムージング法を用い、その際に正のスケール係数λと負のスケール係数とを交互に変化させる。これにより縮小化は低減されるが、この手法においても充分なスムージングを達成するためには複数回の反復を必要とする。これについては上掲のG.Taubin "Curve and surface smoothing without shrinkage", Technical Report RC-19536,IBM Research, April 1994 を参照されたい。
【００１４】
スムージングアルゴリズムについての別の問題に、頂点の移動が不可能だという点がある。なぜなら表面の頂点は同時に、より大きなデータ構造の一部だからである。有限要素法を応用する場合、例えば頂点は３次元の４面体のメッシュの一部である。移動する頂点は簡単にトポロジーの不一致を生じさせる。本発明によれば頂点は実質的には移動しない。すなわち、頂点は一時的に移動することはあるが、グロー法線の計算後リセットされ、元に戻される。
【００１５】
従来技術に関する情報は、例えば１９９６年４月９日付米国特許第５５０６９４７号明細書 Taubin "CURVE AND SURFACE SMOOTHING WITHOUT SHRINKAGE"、１９９４年４月１２日付米国特許第５３０３３３９号明細書 Ikuma "THREE-DIMENSIONAL GRAPHIC PROCESSING APPARATUS"、１９９２年１１月１０日付米国特許第５１６３１２５号明細書 Einkauf et al. "METHOD FOR ADAPTIVELY PROVIDING NEAR PHONG GRADE SHADING FOR PATTERNS IN A GRAPHICS DISPLAY SYSTEM"、１９９１年１１月５日付米国特許第５０６３３７５号明細書 Lien et al. "METHOD AND APPARATUS FOR SHADING IMAGES"、１９９３年１月１２日付米国特許第５１７９６３８号明細書 Dawson et al. "METHOD AND APPARATUS FOR GENERATING A TEXTURE MAPPED PERSPECTIVE VIEW"、１９９７年３月１８日付米国特許第５６１３０５０号明細書 Hochmuth et al. "METHOD AND APPARATUS FOR REDUCING ILLUMINATION CALCULATIONS TUROUGH EFFICIENT VISIBILITY DETERMINATION" に記載されている。
【００１６】
【発明が解決しようとする課題】
本発明の課題は、多面体を有する対象物の表面のスムージング方法を提供し、上述の欠点を回避することである。
【００１７】
【課題を解決するための手段】
この課題は、処理装置により、頂点ｖを一時的なコピーｖ’として記憶するステップと、頂点ｖにガウシアンスムージングを適用し、充分な度合で対象物のスムージングが達成されるまで複数回反復して滑らかな対象物を得るステップと、滑らかな対象物を用いてグロー法線の新たな集合を補間するステップと、予め存在していた法線と新たな法線の集合とを置換するステップと、頂点ｖ’をｖに戻すステップと、グロー法線の新たな集合を表現する出力多面体を出力するステップとを実行する方法により解決される。課題はまた、処理装置により、対応する頂点にガウシアンスムージングを適用するステップと、前記ステップを反復して滑らかな対象物の表面を得るステップと、滑らかな対象物のグロー法線を計算するステップと、頂点を対応する初期の位置に戻すステップとを実行する方法により解決される。
【００１８】
【発明の実施の形態】
本発明の１つの実施形態によれば、ガウシアンスムージングはグロー法線のみに適用される。式（１）は複数回反復されて適用され、その後滑らかになった新たな表面のグロー法線が計算され、最終的に頂点は初期の位置へリセットされる。頂点がリセットされるので、縮小をともなう手法を上述の従来の技術よりも迅速に用いることができる。対象物の境界でのスムージングは達成されないが、内部へ向かう面分は滑らかな表面と同様のシェーディングでレンダリングされる。本発明の方法ではガウシアンスムージングの全ての利点が得られ、しかも縮小が生じない。さらに本発明の方法は、対象物のジオメトリを変化させることが不可能な場合にも使用することができる。
【００１９】
本発明の対象物の表面のスムージング法の別の実施形態によれば、対象物は頂点によって規定される３次元の多面体を有しており、それぞれ形状を表現する多面体Ｐに関して頂点ｖ、グロー法線ｎ、面分ｆを有している。これらは次のような定義で用いられる。すなわち、頂点は３Ｄ座標（ｘ，ｙ，ｚ）であり、面分は頂点（ｖi，ｖj，ｖk）によって形成される三角形を示すトリプレット（ｉ，ｊ，ｋ）であり、それぞれの面分の頂点は関連するベクトルｆｎ＝（ｖj−ｖi）×（ｖk−ｖi）が多面体の外側を指示するように配向されており、このベクトルはここでは面分（ｉ，ｊ，ｋ）の面分法線と称され、グロー法線は頂点に関連するベクトルである。本発明の方法は、頂点ｖを一時的なコピーｖ’として記憶するステップと、頂点ｖにガウシアンスムージングを適用し、充分な度合で対象物のスムージングが達成されるまで複数回反復して滑らかな対象物を得るステップと、滑らかな対象物を用いてグロー法線の新しい集合を補間するステップと、予め存在していた法線と新たな法線の集合とを置換するステップと、頂点ｖ’をｖに戻すステップと、グロー法線の新たな集合を示す出力多面体を出力するステップとを有する。
【００２０】
本発明の別の実施形態によれば、グロー法線の新たな集合を補間するステップは頂点ｖiでのグロー法線を計算するステップを有する。
【００２１】
本発明の別の実施形態によれば、頂点ｖにガウシアンスムージングを適用し、充分な度合で対象物のスムージングが達成されるまで複数回反復して滑らかな対象物を得るステップにより、対象物の縮小を生じさせる。
【００２２】
本発明の別の実施形態によれば、ガウシアンスムージングを適用するステップは、
【００２３】
【数７】
0004383585.tif 000004
【００２４】
に相応に行われる。ここでＩiはｖiとエッジを共有する全ての頂点のインデクスの集合である。ｗijは重みづけウェイトであって、例えばｖiとエッジを共有する複数の頂点の数ｎiを用いて表すと１／ｎiである。λはスケール係数であって０＜λ＜１である。
【００２５】
本発明の別の実施形態によれば、頂点ｖiでのグロー法線を計算するステップは、次のアルゴリズムに相応に計算される。すなわちグロー法線は
【００２６】
【数８】
0004383585.tif 000005
【００２７】
ここでＩiは頂点ｖiを有する全ての面分の面分インデクスの集合であり、ｆｎjは面分ｆjの面分法線であり、重みづけ係数ｗjは６に定められている。請求項５に記載の対象物の表面のスムージング法では、重みづけ係数ｗjは面分ｆjの領域である。
【００２８】
本発明の別の実施形態によれば、重みづけ係数ｗjは頂点ｖiを共有する面分ｆjの２つのエッジ間の角度である。
【００２９】
本発明の別の実施形態によれば、重みづけ係数は１である。
【００３０】
本発明の多面体の表面エレメントで表現される対象物の表面のスムージング法の別の実施形態によれば、対応する多面体Ｐは頂点ｖ、グロー法線ｎ、面分ｆによって示される。頂点は３Ｄ座標（ｘ，ｙ，ｚ）であり、面分は頂点（ｖi，ｖj，ｖk）によって形成される三角形を示すトリプレット（ｉ，ｊ，ｋ）であり、それぞれの面分の頂点は、関連するベクトルｆｎ＝（ｖj−ｖi）×（ｖk−ｖi）が多面体の外側を指示するように配向されており、このベクトルはここでは面分（ｉ，ｊ，ｋ）の面分法線と称され、グロー法線は頂点に関連するベクトルである。本発明の方法は、相応の頂点にガウシアンスムージングを適用するステップと、スムージングのステップを反復して滑らかな対象物の表面を得るステップと、滑らかな対象物のグロー法線を計算するステップと、頂点を相応の初期の位置に戻すステップとを有する。
【００３１】
【実施例】
本発明を完全に理解するために、以下に図に関連した実施例を説明する。
【００３２】
本発明の方法の有利な実施例を以下に説明する。ここでは対象物は３次元の多面体であり、頂点によって規定され、画像は２次元スクリーンまたは２次元平面分への対象物の投影である。これには例えば従来のレンダリング技術が用いられる。入力データは頂点ｖ、グロー法線ｎ、面分ｆを有する多面体Ｐと見なされる。頂点は３Ｄ座標（ｘ，ｙ，ｚ）であり、面分は頂点（ｖi，ｖj，ｖk）によって形成される三角形を示すトリプレット（ｉ，ｊ，ｋ）である。それぞれの面分の頂点は関連するベクトルｆｎ＝（ｖj−ｖi）×（ｖk−ｖi）が多面体の外側を指示するように配向されており、この場合の積はクロス積である。このベクトルはここでは面分（ｉ，ｊ，ｋ）の面分法線と称される。グロー法線は頂点に関連するベクトルである。グロー法線は本発明によれば、プロシージャの期間中新たに再計算されるので、考慮または使用する必要はない。
【００３３】
頂点は一時的なコピーｖ’としてセーブされる。ガウシアンスムージングはｖに対して、充分なスムージングが達成されるまで複数回適用される。このプロシージャは対象物を縮小するが、効果的に頂点ｖを新たなロケーションへ移動させる。ガウシアンスムージングは前述の式（１）に相応に行われる。
【００３４】
縮小されたけれども滑らかになった対象物を用いて、グロー法線の新しい集合が補間される。旧い法線は新たな法線によって置換される。頂点ｖiでのグロー法線は次のアルゴリズムにより次の定義を用いて計算される。Ｉiを頂点ｖiを有する全ての面分ｆの面分インデクスの集合とし、ｆｎjを面分ｆjの面分法線とし、重みづけ係数ｗjを定め、ｖiでのグロー法線ｇiを次のように計算する。すなわち
【００３５】
【数９】
0004383585.tif 000006
【００３６】
重みづけ係数ｗjはｆjの領域であってもよいし、または頂点ｖiを共有する面分ｆjの２つのエッジの間の角度であってもよいし、または単純に１、すなわち一般的にグロー法線の良好な近似となる値であってもよい。重みづけ係数は必要な計算時間に影響する。つまり角度を計算するにはより多くの計算時間が必要となるが、面分の領域または単純に１を用いて計算するよりも正確である。
【００３７】
オリジナルの頂点ｖ’はｖに戻される。出力された多面体は異なるグロー法線を有するが、面分および頂点は同じである。
【００３８】
図１には本発明の方法がフローチャートの形で示されている。図２には、多面体モデルが実際のジオメトリから計算されたグロー法線により表示されている。図３には図２と同じモデルが、ガウシアンスムージングの後に計算されたグロー法線により示されている。図４および図５には、別のモデルについて同じ処理が行われたものが示されている。反復数は８回であり、λ＝０.３３である。画像の改善点が図に見てとれる。
【００３９】
本発明を実施例によって説明したが、本発明の範囲から離れないかぎり当業者による種々の修正ないし補完も可能である。このような修正および補完は請求項に示されている本発明の内容の範囲内で行われる。
【図面の簡単な説明】
【図１】本発明の方法のステップを示すフローチャートである。
【図２】実際のジオメトリから計算されたグロー法線で表示される多面体モデルを示す図である。
【図３】ガウシアンスムージング後に計算されたグロー法線で図２と同じモデルを示した図である。
【図４】実際のジオメトリから計算されたグロー法線で表示される別のモデルを示す図である。
【図５】ガウシアンスムージング後に計算されたグロー法線で図４と同じモデルを示した図である。
【図１】
0004383585.tif 000011
【図２】
0004383585.tif 000012
【図３】
0004383585.tif 000013
【図４】
0004383585.tif 000014
【図５】
0004383585.tif 000015