粒子系を用いた陰関数曲面のポリゴン化方法
【課題】陰関数形式で表現された三次元モデルの曲面から、穴などの欠陥が無く且つ正三角形に近い均一な三角形メッシュを生成可能とする。
【解決手段】ａ１．生成すべきポリゴンメッシュの節点を粒子と見なし、粒子間に働く力を斥力として設定すると共に前記曲面上に向けて働く力を重力として設定するステップ、ａ２．前記粒子が有する斥力及び重力のポテンシャルエネルギーを算出するステップ、ａ３．前記粒子の近傍点の位置に仮想粒子を配置し、仮想粒子が有する前記ポテンシャルエネルギーを算出するステップ、ａ４．当該粒子及びその近傍点に配置された前記仮想粒子のうち前記ポテンシャルエネルギーが最小の位置へ当該粒子を移動させるステップ、ａ５．各粒子の状態が安定状態に到達するまで前記ステップａ２〜ａ４の処理を繰り返すステップ、ａ６．得られた粒子群のデータを基にメッシュを生成するステップを備える。
【解決手段】ａ１．生成すべきポリゴンメッシュの節点を粒子と見なし、粒子間に働く力を斥力として設定すると共に前記曲面上に向けて働く力を重力として設定するステップ、ａ２．前記粒子が有する斥力及び重力のポテンシャルエネルギーを算出するステップ、ａ３．前記粒子の近傍点の位置に仮想粒子を配置し、仮想粒子が有する前記ポテンシャルエネルギーを算出するステップ、ａ４．当該粒子及びその近傍点に配置された前記仮想粒子のうち前記ポテンシャルエネルギーが最小の位置へ当該粒子を移動させるステップ、ａ５．各粒子の状態が安定状態に到達するまで前記ステップａ２〜ａ４の処理を繰り返すステップ、ａ６．得られた粒子群のデータを基にメッシュを生成するステップを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元モデルの曲面をポリゴン化する技術、及び既存のポリゴンメッシュをスムージング化する技術に関し、特に、陰関数形式で表現された三次元モデルの曲面から、穴などの欠陥が無く高品質なポリゴンメッシュを生成できると共に、既存のポリゴンメッシュのデータを入力してスムージング化することが可能な陰関数曲面のポリゴン化方法に関するものである。
【背景技術】
【０００２】
近年、三次元レーザースキャナなどの計測技術や情報処理技術の進展に伴って、製品を開発する際に、例えば製品の立体モデルから計算機の内部モデルを作成する「リバースエンジニアリング」が使用されており、また、リバースエンジニアリングについて多くの研究も発表されている。リバースエンジニアリングは、例えば、計測機器で計測して得た点群データから曲線を作成し、それらの曲線から面を作成するといった方法で立体モデルの構造を再構成し、コンピュータ上で性能評価などのシミュレーションをしたり、ＣＡＤデータと実際の製品とを比較したりする場合などに利用されている。
【０００３】
実際の製品など三次元のオブジェクトの表面形状を表現する場合、オブジェクトの表面の座標値を用いて形状を定義するパラメトリック表現と、陰形式の関数を用いて曲面を表現する陰関数表現とがある。陰関数はＣＳＧ（Constructive Solid Geometry）との相性がよく、特に陰関数のブール結合を用いると、三次元空間で定義された実数値関数ｗ＝Ｆ（ｘ，ｙ，ｚ）とすると、レベル集合ｗ＝ｋ（ｋは定数）によってほとんど全ての形状を表現することができる。後者の陰関数による表現方法は、例えば空間の内外判定や表面形状の変形、ＣＳＧによる集合演算が容易に行えるなどの利点がある。そして、陰関数により表現されたオブジェクト（以下、三次元モデルとする）をメッシュによってモデリングする手法としては、マーチング・キューブ法が周知である（例えば非特許文献１を参照）。
【０００４】
ところで、陰関数を用いて表現された曲面（陰関数曲面）をポリゴン化するために共通する手法には、いくつかの欠点がある。例えば、マーチング・キューブ法のような手法では、第１に、ポリゴン化が行われるバウンディング・ボックスが、ユーザによって決められなければならないという問題がある。そして、第２に、グリッド（格子点）のサンプリングサイズの問題がある。例えば、グリッドのサンプリングサイズが大きすぎれば、形状の一部を失うかもしれないし、一部の複雑な特徴をただの平面要素によって近似してしまうかもしれない。一方、小さいサイズのグリッドを用いた場合は、計算量が非常に大きくなってしまう。なぜなら、全ての節点での関数値を計算する必要があるからである。いずれにせよ、正則（レギュラー）グリッドを用いることにより、曲面のほぼ平面に近い部分でも、曲率の高い部分でも、同じ近似を用いてしまうことにある。そして、それによって極めて悪い近似メッシュが生成されてしまうことになる。また、曲面上の良い正則（レギュラー）メッシュが望まれるが、正則性は２次元射影よって得られるのみである。
【０００５】
これらの問題は、部分的にブルーメンサル（Bloomenthal）の研究（例えば非特許文献２を参照）とベルホー（Velho）の研究（例えば非特許文献３を参照）による取り組みがあるのみである。ブルーメンサルは、あるシード点から出発し、曲面に沿ってのみ、グリッドでの関数値を調べることを提案している。一方、ベルホーは曲率の高い領域を見つけるために、得られたメッシュ上の関数の勾配を利用し、そのようなメッシュ要素を細分割してアダプティブ・メッシュを得ることを提案している。
【非特許文献１】ダブリュー．イー．ローレンセン（W.E.Lorensen），マーチン．キューブ（Marching cubes）共著、「ハイ リゾリューション スリーディー サーフィス コンストラクション アルゴリズム（A high resolution 3D surface Construction algorithm）」、プロシーディング オブ ザ フォーティーンス アニュアル カンファレンス オブ コンピュータ グラフィックス アンド インターラクティブ テクニック（Proceedings of the 14th annual conference of Computer graphics and interactive techniques）、１９８７年，ｐ．１６３−１６９
【非特許文献２】ジェイ．ブルーメンサル（J.Bloomenthal）著、「ポリゴナイゼイション オブ インプリシット サーフィス（Polygonization of Implicit Surfaces）」、コンピューター エイディド ジオメトリック デザイン（Computer Aided Geometric Design）、１９８８年，第５巻（第４号），ｐ．３４１−３５５
【非特許文献３】エル．ベルホー（L.Velho）著、「ポリゴナイゼイション オブ インプリシット サーフィス（Polygonization of Implicit surfaces）」、ジャーナル オブ グラフィックス ツールズ（Journal of Graphics Tools）、１９９６年，第１巻（第２号），ｐ．５−２４
【非特許文献４】エヌ．コジェキネ（N.Kojekine），アイ．ハギワラ（I.Hagiwara），ブイ．サブチェンコ（V．Savchenko）共著、「ソフトウェア ツールズ ユージング シーエスアールビーエフ フォア プロセッシング スキャタード データ（Software tools using CSRBFs for processing scattered data）」、コンピュータ アンド グラフィックス ジャーナル（Computers & Graphics Journal）、２００３年，第２２巻（第２号），ｐ．３０９−３１７
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところが、ブルーメンサルの手法については、計算時間を大幅に減少させることができるが、ただ一つの表面メッシュしか見つけることができないという制約をもたらすといった問題がある。そして、ベルホーの手法については、曲率の高い領域を見つけることはできるが、バウンディング・ボックスの問題のような、マーチング・キューブ法にある他の制約には未だ取り組みがなされていなかった。
【０００７】
ここで、バウンディング・ボックスの問題について図面を参照して説明する。例えば、ＲＢＦ（Radial Basis Functions）によって構成された陰関数はいつも閉曲面を定義するが、ブルーメンサルのアルゴリズムでは、例えば図１１に示されるように、ポリゴン化された貝殻モデル１の曲面上に穴１ａ（本来は存在しない穴）が見られる。図１１の例は、貝殻モデル上でサンプリングした９１５点の点群に対してＣＳＲＢＦ（Compactly Supported Radial Basis Functions）（非特許文献４を参照）によってフィッティングされた陰関数曲面のメッシュ（ブルーメンサルのアルゴリズムによってポリゴン化された結果）を示したものであるが、図１１中の穴１ａは、バウンディング・ボックスが正しく定義されなかった（小さすぎた）ことによる。もし、取り扱う関数についてほとんど知らない場合は、バウンディング・ボックスの適当な大きさと位置を推測することは容易くない。このように、陰関数形式で表現された三次元モデルの曲面をポリゴン化する方法は従来から提案されていたが、従来の方法では、バウンディング・ボックスの定義が容易ではなく、また、三次元モデルの形状を完全に再現できない場合が起こり得るなどの問題があった。
【０００８】
本発明は、上述のような事情よりなされたものであり、本発明の目的は、陰関数形式で表現された三次元モデルの曲面から、穴などの欠陥が無い高品質のポリゴンメッシュを生成することができると共に、正三角形に近い均一な三角形メッシュを生成することが可能な陰関数曲面のポリゴン化方法を提供することにある。また、本発明の更なる目的は、陰関数に対して生成された既存のメッシュのスムージング化にも適用することが可能なポリゴン化方法を提供することにある。
【課題を解決するための手段】
【０００９】
本発明は、陰関数曲面のポリゴン化方法に関し、本発明の上記目的は陰関数形式で表現された三次元モデルの曲面上に複数の粒子から構成される粒子群を分布させてポリゴン化する方法であって、ａ１．生成すべきポリゴンメッシュの節点を前記粒子と見なし、粒子間に働く力を斥力として設定すると共に前記曲面上に向けて働く力を重力として設定するステップと、ａ２．前記曲面を覆う空間内に存在する各粒子について、前記粒子に働く前記斥力の総和に前記重力を加えた結果を前記粒子が有するポテンシャルエネルギーとして算出するステップと、ａ３．与えられた刻み幅に応じて前記粒子の近傍点を複数設定して前記近傍点の位置に仮想粒子を配置し、前記空間内に存在する各粒子について、当該粒子に対応して配置された前記仮想粒子毎に、前記仮想粒子に働く前記斥力の総和に前記重力を加えた結果を当該仮想粒子が有するポテンシャルエネルギーとして算出するステップと、ａ４．前記空間内に存在する各粒子について、当該粒子及びその近傍点に配置された前記仮想粒子のうち前記ポテンシャルエネルギーが最小の位置へ当該粒子を移動させるステップと、ａ５．前記ステップａ４の処理にて移動しない粒子数の割合が所定値以上となった状態を安定状態として、前記空間内に存在する各粒子の状態が少なくとも前記安定状態に到達するまで前記ステップａ２〜前記ステップａ４の処理を繰り返すステップと、ａ６．前記ステップａ５により得られた粒子群のデータを基にポリゴンメッシュを生成するステップと、を有することによって達成される。
【００１０】
さらに、本発明の上記目的は、前記ステップａ５は、前記空間内に存在する各粒子について、与えられたサンプリング距離で当該粒子の周りに規定数の粒子が存在するか否かを判定し、存在する粒子数が前記規定数より少ない場合は、前記規定数となるように前記当該粒子の位置に新しい粒子を置いて粒子数を増加させた後に前記ステップａ２〜前記ステップａ４の処理を繰り返すこと、前記ステップａ５は、前記空間内に存在する各粒子について、与えられたサンプリング距離で当該粒子の周りに規定数の粒子が存在するか否かを判定し、存在する粒子数が前記規定数より多い場合は、前記与えられた粒子数となるように前記サンプリング距離内に既にある粒子を除外して粒子数を減少させた後に前記ステップａ２〜前記ステップａ４の処理を繰り返すこと、前記ステップａ５における前記規定数の粒子が存在するか否かの判定は、前記各粒子の状態が前記安定状態に近い状態となった場合に実施すること、前記曲面上に分布させる粒子の最大数又は粒子数の範囲が予め与えられている場合、前記ステップａ５は、前記安定状態に到達し、且つ前記空間内に存在する粒子数が前記最大数又は前記粒子数の範囲に到達したときに、前記ステップａ６へ移行すること、前記節点の生成元となる粒子が既存のメッシュの節点群であって、該節点群のデータを入力すると共に前記刻み幅の値をスムージング化のパラメータとして入力し、前記ステップａ２以降の処理を実行して当該モデルのメッシュを再生成すること、によってそれぞれ一層効果的に達成される。
【００１１】
また、本発明の上記目的は、前記ステップａ４にて当該粒子が移動しなかった場合、前記ステップａ５は、前記刻み幅の値を小さな値に変更した後に前記ステップａ２〜前記ステップａ４の処理を繰り返すこと、前記ステップａ４にて当該粒子が移動した場合、前記ステップａ５は、前記刻み幅の値を大きな値に変更した後に前記ステップａ２〜前記ステップａ４の処理を繰り返すこと、前記重力が、前記粒子の存在する点での陰関数値に比例した値であること、によってそれぞれ一層効果的に達成される。
【発明の効果】
【００１２】
本発明によれば、節点を粒子と見なし、斥力が作用する空間内に存在する各粒子の力学的な力の釣り合いによって一様な粒子の分布を陰関数曲面上で求め、その粒子系を用いてメッシュを生成するようにしているので、穴などの欠陥が無い高品質のポリゴンメッシュを生成することができると共に、正三角形に近い均一な三角形メッシュを生成することができるといった優れた効果を奏する。また、既存のメッシュの節点群のデータを入力して当該モデルのメッシュを再生成するステップを設けることによって、メッシュのスムージング化など、既存のメッシュの品質の向上を図ることが可能となる。さらに、与えられた規定数に応じて粒子数を増加又は減少させるステップを設けることによって、平滑化の度合を最適化することが可能となる。
【発明を実施するための最良の形態】
【００１３】
先ず、本発明の着眼点について説明する。陰関数形式で表現された三次元モデルの曲面をポリゴンで表現する際、閉曲面での穴などの欠陥が無く、且つ形状の良いポリゴンで曲面を完全に覆い尽くすような高品質のメッシュを生成するには、そのメッシュを構成する節点をどのように配置するかが問題となる。本発明では、メッシュを構成する節点を、曲面上を運動する粒子に見立てて、各粒子の力学的な力の釣り合いによって一様な粒子の分布を得るようにしている。その際、粒子間に働く力は、メッシュの要素サイズとしてある距離を保つ必要があるので、「斥力」として与えられる。さらに、曲面上若しくは曲面に非常に近いところに、節点を保つために、粒子の存在する点での陰関数値に比例した値を「重力」として加える。粒子に働くこれらの力のポテンシャルの和の低いところに、その粒子が移動するように反復計算を行えば、粒子が曲面上に釣り合いを保った状態として得られ、その結果として一様な分布をした粒子群を得ることができる。また、計算量を低減するために、例えば、周りの点のポテンシャルは中心の点のポテンシャルの近似によって代用する。そして、本発明では、このようにして得た粒子群のデータを節点群のデータとして利用することによって、バウンディング・ボックス等の従来技術の問題を解決し、穴などの欠陥が無く且つ形状の良い高品質なメッシュを生成するようにしている。なお、上記粒子群のデータは、陰関数曲面のポリゴン化の他に、陰関数曲面から得られたポリゴンの改良、例えば既に生成されている節点座標の平滑化など、既存のポリゴンメッシュのスムージング化などに利用することができる。
【００１４】
以下、本発明の好適な実施の形態について図面を参照して詳細に説明する。
＜１＞粒子系を用いた陰関数曲面のポリゴン化方法
＜１−１＞陰関数曲面への粒子の分布方法
本発明では、与えられた陰関数Ｆ（ｘ，ｙ，ｚ）に対して、関数の０−等値面Ｆ（ｘ，ｙ，ｚ）＝０を三角形メッシュによって表現することを考える。陰関数曲面Ｓは、この陰関数形式Ｆ（ｘ，ｙ，ｚ）＝０で定義される。
【００１５】
メッシュの節点を粒子に見立てたとき次の２つのタイプの技術的課題が考えられる。
課題（１）．与えられたＮ個の粒子を曲面Ｓ上に「うまく配置」する。
課題（２）．与えられたサンプリング距離ｓの条件の下で、曲面Ｓ上の粒子の「適した分布」を見つける。この場合、粒子はいくつ用いても良い。
【００１６】
粒子はそれらの間に働く斥力に従って曲面Ｓ上を移動する。課題（１）は、メッシュのスムージング化に対応し、もし、この斥力が大変距離が離れている粒子間でも互いに影響を及ぼしあうならば、課題（１）は解決可能である。すなわち、粒子間に斥力が作用しないような場が存在する場合、単に斥力を変化させただけでは、何らかの特別な制約条件がなければ、最終的には、曲面の突出部に粒子が集積した分布が得られるかもしれないが、そのような場が存在しない場合は粒子が斥力によって分散され、粒子の密度が平滑化されるからである。
【００１７】
課題（２）は、曲面のポリゴン化に対応し、もし、この力、及び各点の有効半径Ｒが定義され、三次元モデルの曲面Ｓを覆う空間内（有効半径Ｒ内）に存在する粒子のみが互いに影響しあうならば、課題（２）は解決可能である。このような粒子系を「コンパクトな台を持つ粒子系」と呼ぶ。
【００１８】
粒子間に斥力を与えることによって、各粒子は三次元空間内に一様に分布するが、曲面Ｓ上に粒子を保持するためには、重力を考慮に入れる必要がある。ポリゴン曲面の場合と同様に、陰関数曲面上での粒子の移動も反復プロセスとしてモデル化される。そして反復プロセスの各ステップでは、各粒子はそれに影響を及ぼす力のポテンシャルの和が最小となる場所へ移動する。重力としては、単に陰関数値に比例する力Ｋ＊｜Ｆ（ｘ，ｙ，ｚ）｜を用いれば良い。図１に示すように、与えられた陰関数曲面Ｓにおいて、粒子Ｐに作用する「重力のポテンシャル」をｇ（ｘ，ｙ，ｚ）、図２に示すように、半径Ｒの空間内に存在する他の粒子（Ｐ２〜Ｐ４）との間で、距離ｒに応じて当該粒子Ｐに対して作用する「斥力のポテンシャル」をｆ（ｒ）とする。
【００１９】
このような定義のもとに、陰関数曲面への粒子の分布に係るアルゴリズムを示すと以下のようになる。
ステップＡ１：
先ず、重力に関する係数Ｋとサンプリング距離ｓ（コンパクトな台を持つ粒子系に対してのみ）、及び粒子の移動のためのサンプリングの刻み幅（本例では、グリッド幅ｄｘ＝ｄｙ＝ｄｚ）を決定する。
ステップＡ２：
先ず、各粒子に対して、与えられた半径Ｒ内（台がコンパクトでない場合はＲ＝∞）に存在する粒子の寄与に因るｆ（ｒ）の総和を計算し、その総和にｇ（ｘ）の値を加える。ここで求めた結果、すなわち当該粒子に作用する斥力と重力のポテンシャルの総和を、以下、当該粒子が有する「ポテンシャルエネルギー」と呼ぶ。
ステップＡ３：
次に、各粒子に対して、刻み幅の設定値（本例では、グリッド幅ｄｘ＝ｄｙ＝ｄｚ）に基づいて、粒子の移動先の候補としてその粒子の近傍点を複数設定し、それらの近傍点での粒子（以下「仮想粒子」と呼ぶ）が有するポテンシャルエネルギーを、上記ステップＡ２と同様に求める。粒子の移動先の候補としては、グリッド幅ｄｘ，ｄｙ，ｄｚを基に、例えば図３に示すように、６つの近傍点Ｐｊ１〜ＰＪ６、すなわち、Ｐｊ１（ｘ＋ｄｘ，ｙ，ｚ）、Ｐｊ２（ｘ−ｄｘ，ｙ，ｚ）、Ｐｊ３（ｘ，ｙ＋ｄｙ，ｚ），Ｐｊ４（ｘ，ｙ−ｄｙ，ｚ），Ｐｊ５（ｘ，ｙ，ｚ＋ｄｚ），Ｐｊ６（ｘ，ｙ，ｚ−ｄｚ）を設定し、それらの６つの近傍点においても、同様に仮想粒子が有するポテンシャルエネルギーを計算する。例えば、粒子を囲む立方体を設定し、その立方体の中心と各正方形面の中心を調べるということは、粒子の移動のために合計７点が形成されたことを意味する。また、粒子の移動は、座標軸の方向（±ｘ，±ｙ，±ｚ方向）に限るものではなく、例えば粒子の対角線的移動も許容される。その場合、図４に示すように、立方体の中心と各面の中心Ｐｊｏ及び立方体の各項点Ｐｋ（合計１５点）、又は立方体の中心、各面の中心、各辺の中点及び立方体の各項点（合計２７点）をそれぞれ調べることになる。なお、近傍点を設定する空間は、格子状の空間に限るものではなく、刻み幅に応じた球状の空間であっても良い。
ステップＡ４：
上記ステップＡ３のように複数の近傍点を移動先の候補として設定すると、粒子はポテンシャルが最小となる点へジャンプする。言い換えると、当該粒子及びその近傍点に配置された仮想粒子のうち、ポテンシャルエネルギーが最小の位置に当該粒子がグリッド上を移動する。
【００２０】
このグリッド上を移動させる精度を改良するために、各粒子に対する刻み分割係数（グリッド幅の設定値）を保存しておく。これはもし、粒子ｊがステップＡ３（ｉ）で移動しなかったとすると、反復プロセス（上記ステップＡ２〜Ａ４を繰り返すプロセス）における次のステップＡ３（ｉ＋１）では、より小さな刻み幅（例えばｄｘ＝ｄｘ／２）を用いて粒子ｊを移動させようと試みる。一方、もし、粒子ｊが移動したのなら、次のステップでより大きな刻み幅（例えばｄｘ＝２＊ｄｘ）を用いても良い。結果として、このプロセスの最後（粒子系が安定した状態に到達しつつあるとき）に、粒子は与えられた許容範囲内において曲面Ｓ上で略均一に分布するはずである。その均一さの度合や処理速度は、最大や最小の刻み幅の値によって制御可能である。
【００２１】
このように、本発明においては、与えられた陰関数曲面に対して粒子系を用い、「良い分布」（例えば、斥力を変化させることによって様々な分布の正則性（規則正しさ）やその他の性質が得られる分布）を生成するので、最終的な粒子の分布は、ポリゴン化や陰関数曲面から得られたポリゴンの改良に利用することができる。
【００２２】
次に、台がコンパクトでない場合の考慮について説明する。
【００２３】
台がコンパクトでない場合、すなわち、斥力が大変距離が離れている粒子間でも互いに影響を及ぼしあう場合は、粒子の最適分布化にかかる演算時間を短縮するためにキャッシングを実装する。斥力は一つの粒子から他の粒子へと向き付けられたベクトルであるから、もし粒子がお互いに遠距離にあり、且つそれらの位置が少ししか移動しない場合は、この影響を保存し、そして各移動方向の修正値を得ることができる。このとき、近傍点での近似ポテンシャルを得るためには、立方体の中心に対して計算されたポテンシャルＦ（ｒ）をこれら修正値に加えれば良い（例えばＦ’≒Ｆ＋ｄｘ）。また、もし、固定された刻み幅ｄｘ，ｄｙ，ｄｚが使われるなら、全ての修正値は同じであるとして良い。このような処理をすることによって演算時間を短縮することができる。
【００２４】
次に、粒子の増加（若しくは減少）による分布の最適化について説明する。
【００２５】
台がコンパクトな粒子系の場合、初期の粒子（以下、「シード粒子」と呼ぶ）の数を選択すること及び粒子システムの展開プロセスを考えなければならない。粒子の位置は、曲面に近いことが望ましい。但し、粒子が曲面から離れていても重力によって曲面上に引き付けられてしまうので、シード粒子の初期の位置が限定されるものではない。また、本発明では、粒子の密度が所望の密度となるように、シード粒子を増減させる機能を備えるようにしているので、シード粒子の数も限定されない。
【００２６】
そのようなシード粒子がポテンシャルの最も低い近傍点の位置に移動し、センサー粒子系（移動中若しくは移動後の粒子を「センサー粒子」と呼ぶ）がほとんど安定した状態に初めて到達するとき、例えば９５％以上のセンサー粒子は静止しているが、５％未満のセンサー粒子が依然として移動している状態においては、初期のシード粒子はほとんど曲面上にあり、曲面上のある部分を与えられたサンプリング距離で覆っている。本発明においては、各粒子に対して、理想的な価数として予め設定された規定数（例えば少なくとも６つ）の粒子が与えられたサンプリング距離ｓでその周りにあるかどうかをチェックする。もし、規定数より少ないなら、それはこの点が現在の分布の境界にあること（あるいはシード粒子の初期の総数が少ないこと）を意味する。そのときは新しい粒子を例えば同じ場所に置いて、近傍点の数が規定数になるように境界粒子として数に加える（粒子としては元の粒子とは異なるので次のステップでは斥力によって離れていってしまう）。展開が終了した後は全ての初期のシード粒子の移動をやめ、新しく生成された粒子（これは境界粒子として重なって存在しているものである）に対して、移動シミュレーションプロセスが再び開始される。全プロセスは決められた粒子の最大数Ｎまで到達するか、又は各点の周りに点が分布し、全ての点が与えられたサンプリング距離内に理想的な価数の近傍点が存在すれば終了となる。
【００２７】
図５（Ａ）〜（Ｃ）は、陰的球面関数上の粒子の移動シミュレーションを表わすいくつかのこまを示す図であり、図５（Ａ）から同図（Ｂ）、同図（Ｃ）へと、上述したアルゴリズムによって粒子が曲面上に分布化されていく様子を示している。図５（Ａ）〜（Ｃ）中の粒子Ｐｉａ（○で示す粒子）は、既に固定されたものを表わし、粒子Ｐｉｂ（■で示す粒子）は、現在移動しているものを表わしており、移動シミュレーションプロセスが繰り返されることによって、図５（Ｃ）に示されるように殆どの粒子Ｐｉが固定されて安定状態となっていく。
＜１−２＞粒子系を用いたメッシュの生成方法
以上のような粒子群の最適分布化の処理によって、メッシュの形成に用いる節点の分布が得られたなら、それに公知の技術（例えば三次元のドローネの三角形分割法）を適用し、四面体メッシュを生成する。陰関数値によって点の内外判定は容易にできるので、それにより内部の点とそれに接続する線分を除去すれば表面の三角形メッシュを得ることができる。図５（Ｄ）は、図５（Ｃ）に示した粒子群を用いてポリゴン化した最終結果を示している。
＜１−３＞陰関数曲面のポリゴン化手順の一例
上述した陰関数曲面のポリゴン化アルゴリズムをフローチャートに示すと、図６及び図７のようになる。なお、初期パラメータ（陰関数Ｆ（ｘ，ｙ，ｚ）、重力係数Ｋ、台の半径Ｒ、サンプリング距離ｓ、粒子の移動のためのサンプリングのグリッド幅ｄｘ，ｄｙ、ｄｚ等）は予め与えられているものとする。
【００２８】
図６に示されるように、先ず、生成すべきポリゴンのメッシュの節点を粒子と見なし、節点の生成元となる粒子に対して他の粒子との間で距離ｒに応じて相互に働く力を、斥力のポテンシャルｆ（ｒ）として設定すると共に、曲面上に向けて働く力を重力のポテンシャルｇ（ｘ）（ｇ（ｘ）＝Ｋ＊｜Ｆ（ｘ，ｙ，ｚ）｜）として設定する（ステップＳ１）。次に、斥力が作用する空間内（本例では半径Ｒの空間におけるサンプリング距離ｓで設定される空間内）に存在する粒子毎に、粒子に働く斥力ｆ（ｒ）のポテンシャルの総和を算出し、その斥力のポテンシャルの総和に対して重力のポテンシャルｇ（ｘ）を加え、前記粒子が有するポテンシャルエネルギーとして算出すると共に（ステップＳ２）、刻み幅の設定値ｄに応じて複数の近傍点を設定して各近傍点の位置に仮想粒子を配置し、サンプリング距離ｓで設定された空間内に存在する各粒子について、当該粒子に対応して配置された仮想粒子毎に、仮想粒子に働く斥力のポテンシャルｆ’（ｒ）の総和を算出すると共に、該斥力のポテンシャルの総和に対して前記重力のポテンシャルｇ’（ｘ）を加え、当該仮想粒子が有するポテンシャルエネルギーを算出する。なお、各粒子のポテンシャルエネルギーを算出する際、粒子がお互いに遠距離にあり、且つそれらの位置が少ししか移動しない場合は、この影響を保存し、そして各移動方向の修正値を得て、立方体の中心に対して計算されたポテンシャルＦ（ｒ）を加えるようにしても良い（ステップＳ３）。
【００２９】
続いて、各粒子について、当該粒子及びその近傍点に配置された仮想粒子のうちポテンシャルエネルギーが最小の位置へ当該粒子を移動させる（ステップＳ４）。続いて、ステップＳ４の処理において移動しない粒子数の割合が所定値（例えば９５％）以上となった状態を安定状態として、あるいは、各粒子が有するポテンシャルエネルギーが予め設定された範囲内にある状態を安定状態として、空間内に存在する各粒子の状態が少なくとも安定状態に到達するまで前記ステップＳ２〜Ｓ４の処理を繰り返す。この反復処理は、曲面上に分布させる粒子の最大数（Ｎ）又は粒子数の範囲（Ｎｍｉｎ，Ｎｍａｘ）が、予め与えられている場合は、各粒子の状態が安定状態に到達し、且つ空間内に存在する粒子数が最大数又は粒子数の許容範囲に到達するまで繰り返され、条件を満たした場合に、次のステップＳ６へ移行する。
【００３０】
なお、例えば既に生成されている節点座標の平滑化など、既存のポリゴンメッシュのスムージング化に本アルゴリズムを適用する場合は、そのポリゴンメッシュの節点群のデータを外部装置等から入力すると共に、刻み幅ｄの値をスムージング化の制御パラメータとして入力し、前記ステップＳ２以降の処理を実行して当該モデルのメッシュを再生成する。また、前記ステップＳ４において当該粒子が移動しなかった場合には、刻み幅ｄの設定値を小さな値に変更した後に前記ステップＳ２〜Ｓ４の処理を繰り返し、また前記ステップＳ４において当該粒子が移動した場合には、刻み幅の設定値ｄを大きな値に変更した後に前記ステップＳ２〜Ｓ４の処理を繰り返すようにしても良い（ステップＳ５）。
【００３１】
次に、上記ステップＳ５により得られた粒子群のデータを基に曲面を形成するポリゴンメッシュを生成する。その際、例えば粒子群のデータから三次元のドローネの三角形分割法によって四面体メッシュを生成した後、その四面体メッシュを構成する各節点の陰関数値によって各節点の三次元モデルの面に対する内外を判定し、内部の点とそれに接続する線分を除去することで三次元モデルの表面を形成する三角形メッシュを生成し、ポリゴン化に係る処理を終了する（ステップＳ６）。
【００３２】
次に、与えられたサンプリング距離ｓにおいて当該粒子の周りに存在すべき理想的な価数ＰＮが設定されている場合の処理を、図７のフローチャートに従って説明する。
【００３３】
前記ステップＳ５において、サンプリング距離ｓの空間内に存在する粒子数を計数し（ステップＳ１１）、当該粒子の周りに理想的な価数ＰＮの粒子が存在するか否かを判定する。そして、存在する粒子数が理想的な価数ＰＮより少ない場合は（ステップＳ１２）、理想的な価数ＰＮとなるように所定の位置（例えば当該粒子自身の位置）に新しい粒子を置いて増加させた後に、前記ステップＳ２〜Ｓ４の処理を繰り返す（ステップＳ１３）。一方、当該粒子の周りに存在する粒子数が理想的な価数ＰＮより多い場合は、理想的な価数ＰＮとなるようにサンプリング距離ｓ内に既にある粒子を減少させた後に（ステップＳ１４）、前記ステップＳ２〜Ｓ４の処理を繰り返す。これらの理想的な価数の粒子が存在するか否かの判定は、各粒子の状態が安定状態に近い状態となった場合に実施するのが望ましい。なお、理想的な価数は、与えられた陰関数曲面の曲率に応じて可変させるようにしても良い。
＜１−４＞本発明に係る粒子系を用いた三次元モデルのポリゴン化方法と従来技術のポリゴン化方法との比較
ここで、本発明に係る粒子系を用いた陰関数曲面へのポリゴン化方法（以下便宜上、粒子群の生成アルゴリズムを「本発明のアルゴリズム」と呼ぶ）を実際の三次元モデルに適用した三つの例を挙げて、従来技術によるものと比較することにする。
【００３４】
図８は、本発明のアルゴリズムによって生成した粒子群を用いて三次元モデルをポリゴン化した第１の例を示している。この第１の例は、図１１に示した従来例と同一の貝殻モデルをポリゴン化したものであるが、図１１に例示したような穴は発生せず（図１１中の穴１ａを参照）、ポリゴン化された貝殻モデル１Ａは、均一なメッシュによって完全に埋め尽くされていることがわかる。
【００３５】
第２の例として、人間の頭部モデルをポリゴン化した例を比較する。図９（Ａ）は、ブルーメンサルのアルゴリズムによってポリゴン化された頭部モデル２の例を示す図である。この例は、頭部モデル上でサンプリングした１４８７点の点群に対して、ＣＳＲＢＦによってフィッティングされた陰関数曲面のメッシュを示したものである。そして、図９（Ｂ）は、本発明のアルゴリズムによって同一の頭部モデルをポリゴン化した例であり、図９（Ｃ）は、その粒子群Ｐｉの最終分布を模式的に示した図である。この例は、台がコンパクトな粒子系によるアプローチの例であり、ここで用いた斥力、サンプリング距離はそれぞれｆ（ｒ）＝１／ｒ２、サンプリング距離ｓ＝０．０５である。従来技術によってポリゴン化された図９（Ａ）の頭部モデル２では、均一なメッシュが生成できていないため、例えば鼻２ａの部分が滑らかに表現されていない。これに対して、本発明では、図９（Ｃ）に示すように、均一に分布された粒子群のデータを用いてポリゴン化するので、ポリゴン化されたモデル２Ａは正三角形に近い均一な三角形メッシュで形成されている。そのため、図９（Ｂ）に示すように、モデルどの部分も滑らかに表現されていることがわかる。
【００３６】
第３の例として、既存の手法を用いて陰関数に対して生成されたメッシュと、本発明のアルゴリズムを適用してそのメッシュの品質の向上を図った例を示して比較する。図１０（Ａ）は、マーチング・キューブ法によって得られた陰的球面のメッシュを示しており、図１０（Ｂ）は、そのマーチング・キューブ法を用いて陰関数に対して生成されたメッシュに、本発明の粒子系によるアルゴリズムを適用してその品質の向上を図ったものである。図１０（Ｂ）の例は、粒子シミュレーションのたった４回の反復によって改良されたメッシュである。ポリゴン化された球面モデル３，３Ａの一部を拡大した部分３１ａ、３１Ａを比較するとわかるように、マーチング・キューブ法では様々な形状の三角形パッチでメッシュが形成されているが、本発明の粒子系による手法を適用してメッシュを再構築することによって、正三角形に近い均一な三角形パッチでメッシュが形成され、スムージング化されることがわかる。なお、スムージング化の処理は、陰的球面のメッシュに限るものではなく、陰的でない球面のメッシュや任意の曲面のメッシュに適用することができる。
【図面の簡単な説明】
【００３７】
【図１】本発明に用いる粒子系に作用させる重力を説明するための模式図である。
【図２】本発明に用いる粒子系に作用させる斥力を説明するための模式図である。
【図３】本発明に係る仮想粒子の設定手順を説明するための模式図である。
【図４】本発明に係る粒子の移動手順を説明するための模式図である。
【図５】本発明に係る粒子系を用いた陰関数曲面のポリゴン化方法を説明するための模式図である。
【図６】本発明に係る陰関数曲面のポリゴン化アルゴリズムを説明するための第１のフローチャートである。
【図７】本発明に係る陰関数曲面のポリゴン化アルゴリズムを説明するための第２のフローチャートである。
【図８】本発明のアルゴリズムによってポリゴン化された貝殻モデルの例を、図１１の従来技術による例と対比して示す図である。
【図９】従来技術によってポリゴン化された頭部モデルの例と、本発明によってポリゴン化された頭部モデルとを対比して示す図である。
【図１０】従来技術によってポリゴン化された球面モデルの例と、そのメッシュを本発明のアルゴリズムを適用してメッシュを再構築したものとを対比して示す図である。
【図１１】従来技術によってポリゴン化された頭部モデルの例を示す図である。
【技術分野】
【０００１】
本発明は、三次元モデルの曲面をポリゴン化する技術、及び既存のポリゴンメッシュをスムージング化する技術に関し、特に、陰関数形式で表現された三次元モデルの曲面から、穴などの欠陥が無く高品質なポリゴンメッシュを生成できると共に、既存のポリゴンメッシュのデータを入力してスムージング化することが可能な陰関数曲面のポリゴン化方法に関するものである。
【背景技術】
【０００２】
近年、三次元レーザースキャナなどの計測技術や情報処理技術の進展に伴って、製品を開発する際に、例えば製品の立体モデルから計算機の内部モデルを作成する「リバースエンジニアリング」が使用されており、また、リバースエンジニアリングについて多くの研究も発表されている。リバースエンジニアリングは、例えば、計測機器で計測して得た点群データから曲線を作成し、それらの曲線から面を作成するといった方法で立体モデルの構造を再構成し、コンピュータ上で性能評価などのシミュレーションをしたり、ＣＡＤデータと実際の製品とを比較したりする場合などに利用されている。
【０００３】
実際の製品など三次元のオブジェクトの表面形状を表現する場合、オブジェクトの表面の座標値を用いて形状を定義するパラメトリック表現と、陰形式の関数を用いて曲面を表現する陰関数表現とがある。陰関数はＣＳＧ（Constructive Solid Geometry）との相性がよく、特に陰関数のブール結合を用いると、三次元空間で定義された実数値関数ｗ＝Ｆ（ｘ，ｙ，ｚ）とすると、レベル集合ｗ＝ｋ（ｋは定数）によってほとんど全ての形状を表現することができる。後者の陰関数による表現方法は、例えば空間の内外判定や表面形状の変形、ＣＳＧによる集合演算が容易に行えるなどの利点がある。そして、陰関数により表現されたオブジェクト（以下、三次元モデルとする）をメッシュによってモデリングする手法としては、マーチング・キューブ法が周知である（例えば非特許文献１を参照）。
【０００４】
ところで、陰関数を用いて表現された曲面（陰関数曲面）をポリゴン化するために共通する手法には、いくつかの欠点がある。例えば、マーチング・キューブ法のような手法では、第１に、ポリゴン化が行われるバウンディング・ボックスが、ユーザによって決められなければならないという問題がある。そして、第２に、グリッド（格子点）のサンプリングサイズの問題がある。例えば、グリッドのサンプリングサイズが大きすぎれば、形状の一部を失うかもしれないし、一部の複雑な特徴をただの平面要素によって近似してしまうかもしれない。一方、小さいサイズのグリッドを用いた場合は、計算量が非常に大きくなってしまう。なぜなら、全ての節点での関数値を計算する必要があるからである。いずれにせよ、正則（レギュラー）グリッドを用いることにより、曲面のほぼ平面に近い部分でも、曲率の高い部分でも、同じ近似を用いてしまうことにある。そして、それによって極めて悪い近似メッシュが生成されてしまうことになる。また、曲面上の良い正則（レギュラー）メッシュが望まれるが、正則性は２次元射影よって得られるのみである。
【０００５】
これらの問題は、部分的にブルーメンサル（Bloomenthal）の研究（例えば非特許文献２を参照）とベルホー（Velho）の研究（例えば非特許文献３を参照）による取り組みがあるのみである。ブルーメンサルは、あるシード点から出発し、曲面に沿ってのみ、グリッドでの関数値を調べることを提案している。一方、ベルホーは曲率の高い領域を見つけるために、得られたメッシュ上の関数の勾配を利用し、そのようなメッシュ要素を細分割してアダプティブ・メッシュを得ることを提案している。
【非特許文献１】ダブリュー．イー．ローレンセン（W.E.Lorensen），マーチン．キューブ（Marching cubes）共著、「ハイ リゾリューション スリーディー サーフィス コンストラクション アルゴリズム（A high resolution 3D surface Construction algorithm）」、プロシーディング オブ ザ フォーティーンス アニュアル カンファレンス オブ コンピュータ グラフィックス アンド インターラクティブ テクニック（Proceedings of the 14th annual conference of Computer graphics and interactive techniques）、１９８７年，ｐ．１６３−１６９
【非特許文献２】ジェイ．ブルーメンサル（J.Bloomenthal）著、「ポリゴナイゼイション オブ インプリシット サーフィス（Polygonization of Implicit Surfaces）」、コンピューター エイディド ジオメトリック デザイン（Computer Aided Geometric Design）、１９８８年，第５巻（第４号），ｐ．３４１−３５５
【非特許文献３】エル．ベルホー（L.Velho）著、「ポリゴナイゼイション オブ インプリシット サーフィス（Polygonization of Implicit surfaces）」、ジャーナル オブ グラフィックス ツールズ（Journal of Graphics Tools）、１９９６年，第１巻（第２号），ｐ．５−２４
【非特許文献４】エヌ．コジェキネ（N.Kojekine），アイ．ハギワラ（I.Hagiwara），ブイ．サブチェンコ（V．Savchenko）共著、「ソフトウェア ツールズ ユージング シーエスアールビーエフ フォア プロセッシング スキャタード データ（Software tools using CSRBFs for processing scattered data）」、コンピュータ アンド グラフィックス ジャーナル（Computers & Graphics Journal）、２００３年，第２２巻（第２号），ｐ．３０９−３１７
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところが、ブルーメンサルの手法については、計算時間を大幅に減少させることができるが、ただ一つの表面メッシュしか見つけることができないという制約をもたらすといった問題がある。そして、ベルホーの手法については、曲率の高い領域を見つけることはできるが、バウンディング・ボックスの問題のような、マーチング・キューブ法にある他の制約には未だ取り組みがなされていなかった。
【０００７】
ここで、バウンディング・ボックスの問題について図面を参照して説明する。例えば、ＲＢＦ（Radial Basis Functions）によって構成された陰関数はいつも閉曲面を定義するが、ブルーメンサルのアルゴリズムでは、例えば図１１に示されるように、ポリゴン化された貝殻モデル１の曲面上に穴１ａ（本来は存在しない穴）が見られる。図１１の例は、貝殻モデル上でサンプリングした９１５点の点群に対してＣＳＲＢＦ（Compactly Supported Radial Basis Functions）（非特許文献４を参照）によってフィッティングされた陰関数曲面のメッシュ（ブルーメンサルのアルゴリズムによってポリゴン化された結果）を示したものであるが、図１１中の穴１ａは、バウンディング・ボックスが正しく定義されなかった（小さすぎた）ことによる。もし、取り扱う関数についてほとんど知らない場合は、バウンディング・ボックスの適当な大きさと位置を推測することは容易くない。このように、陰関数形式で表現された三次元モデルの曲面をポリゴン化する方法は従来から提案されていたが、従来の方法では、バウンディング・ボックスの定義が容易ではなく、また、三次元モデルの形状を完全に再現できない場合が起こり得るなどの問題があった。
【０００８】
本発明は、上述のような事情よりなされたものであり、本発明の目的は、陰関数形式で表現された三次元モデルの曲面から、穴などの欠陥が無い高品質のポリゴンメッシュを生成することができると共に、正三角形に近い均一な三角形メッシュを生成することが可能な陰関数曲面のポリゴン化方法を提供することにある。また、本発明の更なる目的は、陰関数に対して生成された既存のメッシュのスムージング化にも適用することが可能なポリゴン化方法を提供することにある。
【課題を解決するための手段】
【０００９】
本発明は、陰関数曲面のポリゴン化方法に関し、本発明の上記目的は陰関数形式で表現された三次元モデルの曲面上に複数の粒子から構成される粒子群を分布させてポリゴン化する方法であって、ａ１．生成すべきポリゴンメッシュの節点を前記粒子と見なし、粒子間に働く力を斥力として設定すると共に前記曲面上に向けて働く力を重力として設定するステップと、ａ２．前記曲面を覆う空間内に存在する各粒子について、前記粒子に働く前記斥力の総和に前記重力を加えた結果を前記粒子が有するポテンシャルエネルギーとして算出するステップと、ａ３．与えられた刻み幅に応じて前記粒子の近傍点を複数設定して前記近傍点の位置に仮想粒子を配置し、前記空間内に存在する各粒子について、当該粒子に対応して配置された前記仮想粒子毎に、前記仮想粒子に働く前記斥力の総和に前記重力を加えた結果を当該仮想粒子が有するポテンシャルエネルギーとして算出するステップと、ａ４．前記空間内に存在する各粒子について、当該粒子及びその近傍点に配置された前記仮想粒子のうち前記ポテンシャルエネルギーが最小の位置へ当該粒子を移動させるステップと、ａ５．前記ステップａ４の処理にて移動しない粒子数の割合が所定値以上となった状態を安定状態として、前記空間内に存在する各粒子の状態が少なくとも前記安定状態に到達するまで前記ステップａ２〜前記ステップａ４の処理を繰り返すステップと、ａ６．前記ステップａ５により得られた粒子群のデータを基にポリゴンメッシュを生成するステップと、を有することによって達成される。
【００１０】
さらに、本発明の上記目的は、前記ステップａ５は、前記空間内に存在する各粒子について、与えられたサンプリング距離で当該粒子の周りに規定数の粒子が存在するか否かを判定し、存在する粒子数が前記規定数より少ない場合は、前記規定数となるように前記当該粒子の位置に新しい粒子を置いて粒子数を増加させた後に前記ステップａ２〜前記ステップａ４の処理を繰り返すこと、前記ステップａ５は、前記空間内に存在する各粒子について、与えられたサンプリング距離で当該粒子の周りに規定数の粒子が存在するか否かを判定し、存在する粒子数が前記規定数より多い場合は、前記与えられた粒子数となるように前記サンプリング距離内に既にある粒子を除外して粒子数を減少させた後に前記ステップａ２〜前記ステップａ４の処理を繰り返すこと、前記ステップａ５における前記規定数の粒子が存在するか否かの判定は、前記各粒子の状態が前記安定状態に近い状態となった場合に実施すること、前記曲面上に分布させる粒子の最大数又は粒子数の範囲が予め与えられている場合、前記ステップａ５は、前記安定状態に到達し、且つ前記空間内に存在する粒子数が前記最大数又は前記粒子数の範囲に到達したときに、前記ステップａ６へ移行すること、前記節点の生成元となる粒子が既存のメッシュの節点群であって、該節点群のデータを入力すると共に前記刻み幅の値をスムージング化のパラメータとして入力し、前記ステップａ２以降の処理を実行して当該モデルのメッシュを再生成すること、によってそれぞれ一層効果的に達成される。
【００１１】
また、本発明の上記目的は、前記ステップａ４にて当該粒子が移動しなかった場合、前記ステップａ５は、前記刻み幅の値を小さな値に変更した後に前記ステップａ２〜前記ステップａ４の処理を繰り返すこと、前記ステップａ４にて当該粒子が移動した場合、前記ステップａ５は、前記刻み幅の値を大きな値に変更した後に前記ステップａ２〜前記ステップａ４の処理を繰り返すこと、前記重力が、前記粒子の存在する点での陰関数値に比例した値であること、によってそれぞれ一層効果的に達成される。
【発明の効果】
【００１２】
本発明によれば、節点を粒子と見なし、斥力が作用する空間内に存在する各粒子の力学的な力の釣り合いによって一様な粒子の分布を陰関数曲面上で求め、その粒子系を用いてメッシュを生成するようにしているので、穴などの欠陥が無い高品質のポリゴンメッシュを生成することができると共に、正三角形に近い均一な三角形メッシュを生成することができるといった優れた効果を奏する。また、既存のメッシュの節点群のデータを入力して当該モデルのメッシュを再生成するステップを設けることによって、メッシュのスムージング化など、既存のメッシュの品質の向上を図ることが可能となる。さらに、与えられた規定数に応じて粒子数を増加又は減少させるステップを設けることによって、平滑化の度合を最適化することが可能となる。
【発明を実施するための最良の形態】
【００１３】
先ず、本発明の着眼点について説明する。陰関数形式で表現された三次元モデルの曲面をポリゴンで表現する際、閉曲面での穴などの欠陥が無く、且つ形状の良いポリゴンで曲面を完全に覆い尽くすような高品質のメッシュを生成するには、そのメッシュを構成する節点をどのように配置するかが問題となる。本発明では、メッシュを構成する節点を、曲面上を運動する粒子に見立てて、各粒子の力学的な力の釣り合いによって一様な粒子の分布を得るようにしている。その際、粒子間に働く力は、メッシュの要素サイズとしてある距離を保つ必要があるので、「斥力」として与えられる。さらに、曲面上若しくは曲面に非常に近いところに、節点を保つために、粒子の存在する点での陰関数値に比例した値を「重力」として加える。粒子に働くこれらの力のポテンシャルの和の低いところに、その粒子が移動するように反復計算を行えば、粒子が曲面上に釣り合いを保った状態として得られ、その結果として一様な分布をした粒子群を得ることができる。また、計算量を低減するために、例えば、周りの点のポテンシャルは中心の点のポテンシャルの近似によって代用する。そして、本発明では、このようにして得た粒子群のデータを節点群のデータとして利用することによって、バウンディング・ボックス等の従来技術の問題を解決し、穴などの欠陥が無く且つ形状の良い高品質なメッシュを生成するようにしている。なお、上記粒子群のデータは、陰関数曲面のポリゴン化の他に、陰関数曲面から得られたポリゴンの改良、例えば既に生成されている節点座標の平滑化など、既存のポリゴンメッシュのスムージング化などに利用することができる。
【００１４】
以下、本発明の好適な実施の形態について図面を参照して詳細に説明する。
＜１＞粒子系を用いた陰関数曲面のポリゴン化方法
＜１−１＞陰関数曲面への粒子の分布方法
本発明では、与えられた陰関数Ｆ（ｘ，ｙ，ｚ）に対して、関数の０−等値面Ｆ（ｘ，ｙ，ｚ）＝０を三角形メッシュによって表現することを考える。陰関数曲面Ｓは、この陰関数形式Ｆ（ｘ，ｙ，ｚ）＝０で定義される。
【００１５】
メッシュの節点を粒子に見立てたとき次の２つのタイプの技術的課題が考えられる。
課題（１）．与えられたＮ個の粒子を曲面Ｓ上に「うまく配置」する。
課題（２）．与えられたサンプリング距離ｓの条件の下で、曲面Ｓ上の粒子の「適した分布」を見つける。この場合、粒子はいくつ用いても良い。
【００１６】
粒子はそれらの間に働く斥力に従って曲面Ｓ上を移動する。課題（１）は、メッシュのスムージング化に対応し、もし、この斥力が大変距離が離れている粒子間でも互いに影響を及ぼしあうならば、課題（１）は解決可能である。すなわち、粒子間に斥力が作用しないような場が存在する場合、単に斥力を変化させただけでは、何らかの特別な制約条件がなければ、最終的には、曲面の突出部に粒子が集積した分布が得られるかもしれないが、そのような場が存在しない場合は粒子が斥力によって分散され、粒子の密度が平滑化されるからである。
【００１７】
課題（２）は、曲面のポリゴン化に対応し、もし、この力、及び各点の有効半径Ｒが定義され、三次元モデルの曲面Ｓを覆う空間内（有効半径Ｒ内）に存在する粒子のみが互いに影響しあうならば、課題（２）は解決可能である。このような粒子系を「コンパクトな台を持つ粒子系」と呼ぶ。
【００１８】
粒子間に斥力を与えることによって、各粒子は三次元空間内に一様に分布するが、曲面Ｓ上に粒子を保持するためには、重力を考慮に入れる必要がある。ポリゴン曲面の場合と同様に、陰関数曲面上での粒子の移動も反復プロセスとしてモデル化される。そして反復プロセスの各ステップでは、各粒子はそれに影響を及ぼす力のポテンシャルの和が最小となる場所へ移動する。重力としては、単に陰関数値に比例する力Ｋ＊｜Ｆ（ｘ，ｙ，ｚ）｜を用いれば良い。図１に示すように、与えられた陰関数曲面Ｓにおいて、粒子Ｐに作用する「重力のポテンシャル」をｇ（ｘ，ｙ，ｚ）、図２に示すように、半径Ｒの空間内に存在する他の粒子（Ｐ２〜Ｐ４）との間で、距離ｒに応じて当該粒子Ｐに対して作用する「斥力のポテンシャル」をｆ（ｒ）とする。
【００１９】
このような定義のもとに、陰関数曲面への粒子の分布に係るアルゴリズムを示すと以下のようになる。
ステップＡ１：
先ず、重力に関する係数Ｋとサンプリング距離ｓ（コンパクトな台を持つ粒子系に対してのみ）、及び粒子の移動のためのサンプリングの刻み幅（本例では、グリッド幅ｄｘ＝ｄｙ＝ｄｚ）を決定する。
ステップＡ２：
先ず、各粒子に対して、与えられた半径Ｒ内（台がコンパクトでない場合はＲ＝∞）に存在する粒子の寄与に因るｆ（ｒ）の総和を計算し、その総和にｇ（ｘ）の値を加える。ここで求めた結果、すなわち当該粒子に作用する斥力と重力のポテンシャルの総和を、以下、当該粒子が有する「ポテンシャルエネルギー」と呼ぶ。
ステップＡ３：
次に、各粒子に対して、刻み幅の設定値（本例では、グリッド幅ｄｘ＝ｄｙ＝ｄｚ）に基づいて、粒子の移動先の候補としてその粒子の近傍点を複数設定し、それらの近傍点での粒子（以下「仮想粒子」と呼ぶ）が有するポテンシャルエネルギーを、上記ステップＡ２と同様に求める。粒子の移動先の候補としては、グリッド幅ｄｘ，ｄｙ，ｄｚを基に、例えば図３に示すように、６つの近傍点Ｐｊ１〜ＰＪ６、すなわち、Ｐｊ１（ｘ＋ｄｘ，ｙ，ｚ）、Ｐｊ２（ｘ−ｄｘ，ｙ，ｚ）、Ｐｊ３（ｘ，ｙ＋ｄｙ，ｚ），Ｐｊ４（ｘ，ｙ−ｄｙ，ｚ），Ｐｊ５（ｘ，ｙ，ｚ＋ｄｚ），Ｐｊ６（ｘ，ｙ，ｚ−ｄｚ）を設定し、それらの６つの近傍点においても、同様に仮想粒子が有するポテンシャルエネルギーを計算する。例えば、粒子を囲む立方体を設定し、その立方体の中心と各正方形面の中心を調べるということは、粒子の移動のために合計７点が形成されたことを意味する。また、粒子の移動は、座標軸の方向（±ｘ，±ｙ，±ｚ方向）に限るものではなく、例えば粒子の対角線的移動も許容される。その場合、図４に示すように、立方体の中心と各面の中心Ｐｊｏ及び立方体の各項点Ｐｋ（合計１５点）、又は立方体の中心、各面の中心、各辺の中点及び立方体の各項点（合計２７点）をそれぞれ調べることになる。なお、近傍点を設定する空間は、格子状の空間に限るものではなく、刻み幅に応じた球状の空間であっても良い。
ステップＡ４：
上記ステップＡ３のように複数の近傍点を移動先の候補として設定すると、粒子はポテンシャルが最小となる点へジャンプする。言い換えると、当該粒子及びその近傍点に配置された仮想粒子のうち、ポテンシャルエネルギーが最小の位置に当該粒子がグリッド上を移動する。
【００２０】
このグリッド上を移動させる精度を改良するために、各粒子に対する刻み分割係数（グリッド幅の設定値）を保存しておく。これはもし、粒子ｊがステップＡ３（ｉ）で移動しなかったとすると、反復プロセス（上記ステップＡ２〜Ａ４を繰り返すプロセス）における次のステップＡ３（ｉ＋１）では、より小さな刻み幅（例えばｄｘ＝ｄｘ／２）を用いて粒子ｊを移動させようと試みる。一方、もし、粒子ｊが移動したのなら、次のステップでより大きな刻み幅（例えばｄｘ＝２＊ｄｘ）を用いても良い。結果として、このプロセスの最後（粒子系が安定した状態に到達しつつあるとき）に、粒子は与えられた許容範囲内において曲面Ｓ上で略均一に分布するはずである。その均一さの度合や処理速度は、最大や最小の刻み幅の値によって制御可能である。
【００２１】
このように、本発明においては、与えられた陰関数曲面に対して粒子系を用い、「良い分布」（例えば、斥力を変化させることによって様々な分布の正則性（規則正しさ）やその他の性質が得られる分布）を生成するので、最終的な粒子の分布は、ポリゴン化や陰関数曲面から得られたポリゴンの改良に利用することができる。
【００２２】
次に、台がコンパクトでない場合の考慮について説明する。
【００２３】
台がコンパクトでない場合、すなわち、斥力が大変距離が離れている粒子間でも互いに影響を及ぼしあう場合は、粒子の最適分布化にかかる演算時間を短縮するためにキャッシングを実装する。斥力は一つの粒子から他の粒子へと向き付けられたベクトルであるから、もし粒子がお互いに遠距離にあり、且つそれらの位置が少ししか移動しない場合は、この影響を保存し、そして各移動方向の修正値を得ることができる。このとき、近傍点での近似ポテンシャルを得るためには、立方体の中心に対して計算されたポテンシャルＦ（ｒ）をこれら修正値に加えれば良い（例えばＦ’≒Ｆ＋ｄｘ）。また、もし、固定された刻み幅ｄｘ，ｄｙ，ｄｚが使われるなら、全ての修正値は同じであるとして良い。このような処理をすることによって演算時間を短縮することができる。
【００２４】
次に、粒子の増加（若しくは減少）による分布の最適化について説明する。
【００２５】
台がコンパクトな粒子系の場合、初期の粒子（以下、「シード粒子」と呼ぶ）の数を選択すること及び粒子システムの展開プロセスを考えなければならない。粒子の位置は、曲面に近いことが望ましい。但し、粒子が曲面から離れていても重力によって曲面上に引き付けられてしまうので、シード粒子の初期の位置が限定されるものではない。また、本発明では、粒子の密度が所望の密度となるように、シード粒子を増減させる機能を備えるようにしているので、シード粒子の数も限定されない。
【００２６】
そのようなシード粒子がポテンシャルの最も低い近傍点の位置に移動し、センサー粒子系（移動中若しくは移動後の粒子を「センサー粒子」と呼ぶ）がほとんど安定した状態に初めて到達するとき、例えば９５％以上のセンサー粒子は静止しているが、５％未満のセンサー粒子が依然として移動している状態においては、初期のシード粒子はほとんど曲面上にあり、曲面上のある部分を与えられたサンプリング距離で覆っている。本発明においては、各粒子に対して、理想的な価数として予め設定された規定数（例えば少なくとも６つ）の粒子が与えられたサンプリング距離ｓでその周りにあるかどうかをチェックする。もし、規定数より少ないなら、それはこの点が現在の分布の境界にあること（あるいはシード粒子の初期の総数が少ないこと）を意味する。そのときは新しい粒子を例えば同じ場所に置いて、近傍点の数が規定数になるように境界粒子として数に加える（粒子としては元の粒子とは異なるので次のステップでは斥力によって離れていってしまう）。展開が終了した後は全ての初期のシード粒子の移動をやめ、新しく生成された粒子（これは境界粒子として重なって存在しているものである）に対して、移動シミュレーションプロセスが再び開始される。全プロセスは決められた粒子の最大数Ｎまで到達するか、又は各点の周りに点が分布し、全ての点が与えられたサンプリング距離内に理想的な価数の近傍点が存在すれば終了となる。
【００２７】
図５（Ａ）〜（Ｃ）は、陰的球面関数上の粒子の移動シミュレーションを表わすいくつかのこまを示す図であり、図５（Ａ）から同図（Ｂ）、同図（Ｃ）へと、上述したアルゴリズムによって粒子が曲面上に分布化されていく様子を示している。図５（Ａ）〜（Ｃ）中の粒子Ｐｉａ（○で示す粒子）は、既に固定されたものを表わし、粒子Ｐｉｂ（■で示す粒子）は、現在移動しているものを表わしており、移動シミュレーションプロセスが繰り返されることによって、図５（Ｃ）に示されるように殆どの粒子Ｐｉが固定されて安定状態となっていく。
＜１−２＞粒子系を用いたメッシュの生成方法
以上のような粒子群の最適分布化の処理によって、メッシュの形成に用いる節点の分布が得られたなら、それに公知の技術（例えば三次元のドローネの三角形分割法）を適用し、四面体メッシュを生成する。陰関数値によって点の内外判定は容易にできるので、それにより内部の点とそれに接続する線分を除去すれば表面の三角形メッシュを得ることができる。図５（Ｄ）は、図５（Ｃ）に示した粒子群を用いてポリゴン化した最終結果を示している。
＜１−３＞陰関数曲面のポリゴン化手順の一例
上述した陰関数曲面のポリゴン化アルゴリズムをフローチャートに示すと、図６及び図７のようになる。なお、初期パラメータ（陰関数Ｆ（ｘ，ｙ，ｚ）、重力係数Ｋ、台の半径Ｒ、サンプリング距離ｓ、粒子の移動のためのサンプリングのグリッド幅ｄｘ，ｄｙ、ｄｚ等）は予め与えられているものとする。
【００２８】
図６に示されるように、先ず、生成すべきポリゴンのメッシュの節点を粒子と見なし、節点の生成元となる粒子に対して他の粒子との間で距離ｒに応じて相互に働く力を、斥力のポテンシャルｆ（ｒ）として設定すると共に、曲面上に向けて働く力を重力のポテンシャルｇ（ｘ）（ｇ（ｘ）＝Ｋ＊｜Ｆ（ｘ，ｙ，ｚ）｜）として設定する（ステップＳ１）。次に、斥力が作用する空間内（本例では半径Ｒの空間におけるサンプリング距離ｓで設定される空間内）に存在する粒子毎に、粒子に働く斥力ｆ（ｒ）のポテンシャルの総和を算出し、その斥力のポテンシャルの総和に対して重力のポテンシャルｇ（ｘ）を加え、前記粒子が有するポテンシャルエネルギーとして算出すると共に（ステップＳ２）、刻み幅の設定値ｄに応じて複数の近傍点を設定して各近傍点の位置に仮想粒子を配置し、サンプリング距離ｓで設定された空間内に存在する各粒子について、当該粒子に対応して配置された仮想粒子毎に、仮想粒子に働く斥力のポテンシャルｆ’（ｒ）の総和を算出すると共に、該斥力のポテンシャルの総和に対して前記重力のポテンシャルｇ’（ｘ）を加え、当該仮想粒子が有するポテンシャルエネルギーを算出する。なお、各粒子のポテンシャルエネルギーを算出する際、粒子がお互いに遠距離にあり、且つそれらの位置が少ししか移動しない場合は、この影響を保存し、そして各移動方向の修正値を得て、立方体の中心に対して計算されたポテンシャルＦ（ｒ）を加えるようにしても良い（ステップＳ３）。
【００２９】
続いて、各粒子について、当該粒子及びその近傍点に配置された仮想粒子のうちポテンシャルエネルギーが最小の位置へ当該粒子を移動させる（ステップＳ４）。続いて、ステップＳ４の処理において移動しない粒子数の割合が所定値（例えば９５％）以上となった状態を安定状態として、あるいは、各粒子が有するポテンシャルエネルギーが予め設定された範囲内にある状態を安定状態として、空間内に存在する各粒子の状態が少なくとも安定状態に到達するまで前記ステップＳ２〜Ｓ４の処理を繰り返す。この反復処理は、曲面上に分布させる粒子の最大数（Ｎ）又は粒子数の範囲（Ｎｍｉｎ，Ｎｍａｘ）が、予め与えられている場合は、各粒子の状態が安定状態に到達し、且つ空間内に存在する粒子数が最大数又は粒子数の許容範囲に到達するまで繰り返され、条件を満たした場合に、次のステップＳ６へ移行する。
【００３０】
なお、例えば既に生成されている節点座標の平滑化など、既存のポリゴンメッシュのスムージング化に本アルゴリズムを適用する場合は、そのポリゴンメッシュの節点群のデータを外部装置等から入力すると共に、刻み幅ｄの値をスムージング化の制御パラメータとして入力し、前記ステップＳ２以降の処理を実行して当該モデルのメッシュを再生成する。また、前記ステップＳ４において当該粒子が移動しなかった場合には、刻み幅ｄの設定値を小さな値に変更した後に前記ステップＳ２〜Ｓ４の処理を繰り返し、また前記ステップＳ４において当該粒子が移動した場合には、刻み幅の設定値ｄを大きな値に変更した後に前記ステップＳ２〜Ｓ４の処理を繰り返すようにしても良い（ステップＳ５）。
【００３１】
次に、上記ステップＳ５により得られた粒子群のデータを基に曲面を形成するポリゴンメッシュを生成する。その際、例えば粒子群のデータから三次元のドローネの三角形分割法によって四面体メッシュを生成した後、その四面体メッシュを構成する各節点の陰関数値によって各節点の三次元モデルの面に対する内外を判定し、内部の点とそれに接続する線分を除去することで三次元モデルの表面を形成する三角形メッシュを生成し、ポリゴン化に係る処理を終了する（ステップＳ６）。
【００３２】
次に、与えられたサンプリング距離ｓにおいて当該粒子の周りに存在すべき理想的な価数ＰＮが設定されている場合の処理を、図７のフローチャートに従って説明する。
【００３３】
前記ステップＳ５において、サンプリング距離ｓの空間内に存在する粒子数を計数し（ステップＳ１１）、当該粒子の周りに理想的な価数ＰＮの粒子が存在するか否かを判定する。そして、存在する粒子数が理想的な価数ＰＮより少ない場合は（ステップＳ１２）、理想的な価数ＰＮとなるように所定の位置（例えば当該粒子自身の位置）に新しい粒子を置いて増加させた後に、前記ステップＳ２〜Ｓ４の処理を繰り返す（ステップＳ１３）。一方、当該粒子の周りに存在する粒子数が理想的な価数ＰＮより多い場合は、理想的な価数ＰＮとなるようにサンプリング距離ｓ内に既にある粒子を減少させた後に（ステップＳ１４）、前記ステップＳ２〜Ｓ４の処理を繰り返す。これらの理想的な価数の粒子が存在するか否かの判定は、各粒子の状態が安定状態に近い状態となった場合に実施するのが望ましい。なお、理想的な価数は、与えられた陰関数曲面の曲率に応じて可変させるようにしても良い。
＜１−４＞本発明に係る粒子系を用いた三次元モデルのポリゴン化方法と従来技術のポリゴン化方法との比較
ここで、本発明に係る粒子系を用いた陰関数曲面へのポリゴン化方法（以下便宜上、粒子群の生成アルゴリズムを「本発明のアルゴリズム」と呼ぶ）を実際の三次元モデルに適用した三つの例を挙げて、従来技術によるものと比較することにする。
【００３４】
図８は、本発明のアルゴリズムによって生成した粒子群を用いて三次元モデルをポリゴン化した第１の例を示している。この第１の例は、図１１に示した従来例と同一の貝殻モデルをポリゴン化したものであるが、図１１に例示したような穴は発生せず（図１１中の穴１ａを参照）、ポリゴン化された貝殻モデル１Ａは、均一なメッシュによって完全に埋め尽くされていることがわかる。
【００３５】
第２の例として、人間の頭部モデルをポリゴン化した例を比較する。図９（Ａ）は、ブルーメンサルのアルゴリズムによってポリゴン化された頭部モデル２の例を示す図である。この例は、頭部モデル上でサンプリングした１４８７点の点群に対して、ＣＳＲＢＦによってフィッティングされた陰関数曲面のメッシュを示したものである。そして、図９（Ｂ）は、本発明のアルゴリズムによって同一の頭部モデルをポリゴン化した例であり、図９（Ｃ）は、その粒子群Ｐｉの最終分布を模式的に示した図である。この例は、台がコンパクトな粒子系によるアプローチの例であり、ここで用いた斥力、サンプリング距離はそれぞれｆ（ｒ）＝１／ｒ２、サンプリング距離ｓ＝０．０５である。従来技術によってポリゴン化された図９（Ａ）の頭部モデル２では、均一なメッシュが生成できていないため、例えば鼻２ａの部分が滑らかに表現されていない。これに対して、本発明では、図９（Ｃ）に示すように、均一に分布された粒子群のデータを用いてポリゴン化するので、ポリゴン化されたモデル２Ａは正三角形に近い均一な三角形メッシュで形成されている。そのため、図９（Ｂ）に示すように、モデルどの部分も滑らかに表現されていることがわかる。
【００３６】
第３の例として、既存の手法を用いて陰関数に対して生成されたメッシュと、本発明のアルゴリズムを適用してそのメッシュの品質の向上を図った例を示して比較する。図１０（Ａ）は、マーチング・キューブ法によって得られた陰的球面のメッシュを示しており、図１０（Ｂ）は、そのマーチング・キューブ法を用いて陰関数に対して生成されたメッシュに、本発明の粒子系によるアルゴリズムを適用してその品質の向上を図ったものである。図１０（Ｂ）の例は、粒子シミュレーションのたった４回の反復によって改良されたメッシュである。ポリゴン化された球面モデル３，３Ａの一部を拡大した部分３１ａ、３１Ａを比較するとわかるように、マーチング・キューブ法では様々な形状の三角形パッチでメッシュが形成されているが、本発明の粒子系による手法を適用してメッシュを再構築することによって、正三角形に近い均一な三角形パッチでメッシュが形成され、スムージング化されることがわかる。なお、スムージング化の処理は、陰的球面のメッシュに限るものではなく、陰的でない球面のメッシュや任意の曲面のメッシュに適用することができる。
【図面の簡単な説明】
【００３７】
【図１】本発明に用いる粒子系に作用させる重力を説明するための模式図である。
【図２】本発明に用いる粒子系に作用させる斥力を説明するための模式図である。
【図３】本発明に係る仮想粒子の設定手順を説明するための模式図である。
【図４】本発明に係る粒子の移動手順を説明するための模式図である。
【図５】本発明に係る粒子系を用いた陰関数曲面のポリゴン化方法を説明するための模式図である。
【図６】本発明に係る陰関数曲面のポリゴン化アルゴリズムを説明するための第１のフローチャートである。
【図７】本発明に係る陰関数曲面のポリゴン化アルゴリズムを説明するための第２のフローチャートである。
【図８】本発明のアルゴリズムによってポリゴン化された貝殻モデルの例を、図１１の従来技術による例と対比して示す図である。
【図９】従来技術によってポリゴン化された頭部モデルの例と、本発明によってポリゴン化された頭部モデルとを対比して示す図である。
【図１０】従来技術によってポリゴン化された球面モデルの例と、そのメッシュを本発明のアルゴリズムを適用してメッシュを再構築したものとを対比して示す図である。
【図１１】従来技術によってポリゴン化された頭部モデルの例を示す図である。
【特許請求の範囲】
【請求項１】
陰関数形式で表現された三次元モデルの曲面上に複数の粒子から構成される粒子群を分布させてポリゴン化する方法であって、
ａ１．生成すべきポリゴンメッシュの節点を前記粒子と見なし、粒子間に働く力を斥力として設定すると共に前記曲面上に向けて働く力を重力として設定するステップと、
ａ２．前記曲面を覆う空間内に存在する各粒子について、前記粒子に働く前記斥力の総和に前記重力を加えた結果を前記粒子が有するポテンシャルエネルギーとして算出するステップと、
ａ３．与えられた刻み幅に応じて前記粒子の近傍点を複数設定して前記近傍点の位置に仮想粒子を配置し、前記空間内に存在する各粒子について、当該粒子に対応して配置された前記仮想粒子毎に、前記仮想粒子に働く前記斥力の総和に前記重力を加えた結果を当該仮想粒子が有するポテンシャルエネルギーとして算出するステップと、
ａ４．前記空間内に存在する各粒子について、当該粒子及びその近傍点に配置された前記仮想粒子のうち前記ポテンシャルエネルギーが最小の位置へ当該粒子を移動させるステップと、
ａ５．前記ステップａ４の処理にて移動しない粒子数の割合が所定値以上となった状態を安定状態として、前記空間内に存在する各粒子の状態が少なくとも前記安定状態に到達するまで前記ステップａ２〜前記ステップａ４の処理を繰り返すステップと、
ａ６．前記ステップａ５により得られた粒子群のデータを基にポリゴンメッシュを生成するステップと、
を有することを特徴とする、粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項２】
前記ステップａ５は、前記空間内に存在する各粒子について、与えられたサンプリング距離で当該粒子の周りに規定数の粒子が存在するか否かを判定し、存在する粒子数が前記規定数より少ない場合は、前記規定数となるように前記当該粒子の位置に新しい粒子を置いて粒子数を増加させた後に前記ステップａ２〜前記ステップａ４の処理を繰り返すことを特徴とする請求項１に記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項３】
前記ステップａ５は、前記空間内に存在する各粒子について、与えられたサンプリング距離で当該粒子の周りに規定数の粒子が存在するか否かを判定し、存在する粒子数が前記規定数より多い場合は、前記与えられた粒子数となるように前記サンプリング距離内に既にある粒子を除外して粒子数を減少させた後に前記ステップａ２〜前記ステップａ４の処理を繰り返すことを特徴とする請求項１に記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項４】
前記ステップａ５における前記規定数の粒子が存在するか否かの判定は、前記各粒子の状態が前記安定状態に近い状態となった場合に実施することを特徴とする請求項２又は３に記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項５】
前記曲面上に分布させる粒子の最大数又は粒子数の範囲が予め与えられている場合、前記ステップａ５は、前記安定状態に到達し、且つ前記空間内に存在する粒子数が前記最大数又は前記粒子数の範囲に到達したときに、前記ステップａ６へ移行することを特徴とする請求項１乃至４のいずれかに記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項６】
前記節点の生成元となる粒子が既存のメッシュの節点群であって、該節点群のデータを入力すると共に前記刻み幅の値をスムージング化のパラメータとして入力し、前記ステップａ２以降の処理を実行して当該モデルのメッシュを再生成することを特徴とする請求項１乃至４のいずれかに記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項７】
前記ステップａ４にて当該粒子が移動しなかった場合、前記ステップａ５は、前記刻み幅の値を小さな値に変更した後に前記ステップａ２〜前記ステップａ４の処理を繰り返すことを特徴とする請求項１乃至６のいずれかに記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項８】
前記ステップａ４にて当該粒子が移動した場合、前記ステップａ５は、前記刻み幅の値を大きな値に変更した後に前記ステップａ２〜前記ステップａ４の処理を繰り返すことを特徴とする請求項１乃至６のいずれかに記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項９】
前記重力が、前記粒子の存在する点での陰関数値に比例した値であることを特徴とする請求項１乃至８のいずれかに記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項１】
陰関数形式で表現された三次元モデルの曲面上に複数の粒子から構成される粒子群を分布させてポリゴン化する方法であって、
ａ１．生成すべきポリゴンメッシュの節点を前記粒子と見なし、粒子間に働く力を斥力として設定すると共に前記曲面上に向けて働く力を重力として設定するステップと、
ａ２．前記曲面を覆う空間内に存在する各粒子について、前記粒子に働く前記斥力の総和に前記重力を加えた結果を前記粒子が有するポテンシャルエネルギーとして算出するステップと、
ａ３．与えられた刻み幅に応じて前記粒子の近傍点を複数設定して前記近傍点の位置に仮想粒子を配置し、前記空間内に存在する各粒子について、当該粒子に対応して配置された前記仮想粒子毎に、前記仮想粒子に働く前記斥力の総和に前記重力を加えた結果を当該仮想粒子が有するポテンシャルエネルギーとして算出するステップと、
ａ４．前記空間内に存在する各粒子について、当該粒子及びその近傍点に配置された前記仮想粒子のうち前記ポテンシャルエネルギーが最小の位置へ当該粒子を移動させるステップと、
ａ５．前記ステップａ４の処理にて移動しない粒子数の割合が所定値以上となった状態を安定状態として、前記空間内に存在する各粒子の状態が少なくとも前記安定状態に到達するまで前記ステップａ２〜前記ステップａ４の処理を繰り返すステップと、
ａ６．前記ステップａ５により得られた粒子群のデータを基にポリゴンメッシュを生成するステップと、
を有することを特徴とする、粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項２】
前記ステップａ５は、前記空間内に存在する各粒子について、与えられたサンプリング距離で当該粒子の周りに規定数の粒子が存在するか否かを判定し、存在する粒子数が前記規定数より少ない場合は、前記規定数となるように前記当該粒子の位置に新しい粒子を置いて粒子数を増加させた後に前記ステップａ２〜前記ステップａ４の処理を繰り返すことを特徴とする請求項１に記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項３】
前記ステップａ５は、前記空間内に存在する各粒子について、与えられたサンプリング距離で当該粒子の周りに規定数の粒子が存在するか否かを判定し、存在する粒子数が前記規定数より多い場合は、前記与えられた粒子数となるように前記サンプリング距離内に既にある粒子を除外して粒子数を減少させた後に前記ステップａ２〜前記ステップａ４の処理を繰り返すことを特徴とする請求項１に記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項４】
前記ステップａ５における前記規定数の粒子が存在するか否かの判定は、前記各粒子の状態が前記安定状態に近い状態となった場合に実施することを特徴とする請求項２又は３に記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項５】
前記曲面上に分布させる粒子の最大数又は粒子数の範囲が予め与えられている場合、前記ステップａ５は、前記安定状態に到達し、且つ前記空間内に存在する粒子数が前記最大数又は前記粒子数の範囲に到達したときに、前記ステップａ６へ移行することを特徴とする請求項１乃至４のいずれかに記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項６】
前記節点の生成元となる粒子が既存のメッシュの節点群であって、該節点群のデータを入力すると共に前記刻み幅の値をスムージング化のパラメータとして入力し、前記ステップａ２以降の処理を実行して当該モデルのメッシュを再生成することを特徴とする請求項１乃至４のいずれかに記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項７】
前記ステップａ４にて当該粒子が移動しなかった場合、前記ステップａ５は、前記刻み幅の値を小さな値に変更した後に前記ステップａ２〜前記ステップａ４の処理を繰り返すことを特徴とする請求項１乃至６のいずれかに記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項８】
前記ステップａ４にて当該粒子が移動した場合、前記ステップａ５は、前記刻み幅の値を大きな値に変更した後に前記ステップａ２〜前記ステップａ４の処理を繰り返すことを特徴とする請求項１乃至６のいずれかに記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【請求項９】
前記重力が、前記粒子の存在する点での陰関数値に比例した値であることを特徴とする請求項１乃至８のいずれかに記載の粒子系を用いた陰関数曲面のポリゴン化方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００７−９４６２８（Ｐ２００７−９４６２８Ａ）
【公開日】平成１９年４月１２日（２００７．４．１２）
【国際特許分類】
【出願番号】特願２００５−２８１３７１（Ｐ２００５−２８１３７１）
【出願日】平成１７年９月２８日（２００５．９．２８）
【出願人】（５０３３６０１１５）独立行政法人科学技術振興機構 (1,734)
【出願人】（５０１０３６９８２）
【出願人】（５０４１２９１４６）
【Ｆターム（参考）】
【公開日】平成１９年４月１２日（２００７．４．１２）
【国際特許分類】
【出願日】平成１７年９月２８日（２００５．９．２８）
【出願人】（５０３３６０１１５）独立行政法人科学技術振興機構 (1,734)
【出願人】（５０１０３６９８２）
【出願人】（５０４１２９１４６）
【Ｆターム（参考）】
[ Back to top ]