(57)【要約】【課題】複雑な形状に対しても低品質メッシュモデルから高品質のメッシュモデルを生成する。【解決手段】メッシュ細分化部２により、低品質メッシュモデル５を各面分の稜線が細分化パラメータσsizeよりも小さくなるように細分化してメッシュの操作自由度を上げ、その後に、メッシュ簡略化部３により、頂点対統合後のメッシュモデルの形状近似誤差が品質を規定する簡略化パラメータτtol以下に抑えられる頂点対を絞り込み、面分歪と面分粗密に関する総合評価値が最大の頂点対を統合して簡略化することで、高品質のメッシュモデルを生成する。【選択図】図２
2005242651.tif 000002
【特許請求の範囲】
【請求項１】
低品質メッシュモデル、細分化パラメータ、簡略化パラメータを記憶したデータベースから低品質メッシュモデルと細分化パラメータを読み出し、低品質メッシュモデルの各面分要素を細分化パラメータに適合するように細分化する細分化手段と、
細分化されたメッシュモデルの各頂点対を統合したときの新頂点の位置を算出する新頂点位置算出手段と、
前記データベースから簡略化パラメータを読み出し、新頂点の位置が簡略化パラメータに適合する頂点対を絞り込み、その中から面分歪と面分粗密に関する総合評価値が最大の頂点対を決定する統合頂点対決定手段と、
前記細分化されたメッシュモデルについて、決定された頂点対を統合して新頂点の位置を設定する新頂点位置設定手段と、
新頂点の位置設定で生成されたメッシュモデルを前記細分化されたメッシュモデルに入れ替えて前記新頂点位置算出手段、前記統合頂点対決定手段、前記新頂点位置設定手段に処理を繰り返させる繰返手段と、
を有することを特徴とする高品質メッシュモデルの生成システム。
【請求項２】
前記細分化パラメータは、面分の稜線の長さを規定するものであって、
前記細分化手段は、細分化パラメータよりも長い稜線に中点を生成する稜線中点生成手段と、
中点を他の中点あるいは頂点と結んで面分を分割する面分分割手段と、
を有することを特徴とする請求項１記載の高品質メッシュモデルの生成システム。
【請求項３】
前記新頂点位置算出手段は、頂点対に隣接する頂点の重心を新頂点の位置として算出することを特徴とする請求項１又は２記載の高品質メッシュモデルの生成システム。
【請求項４】
前記新頂点位置算出手段は、頂点対に接する各面分と新頂点との自乗距離の和が最小となる位置を新頂点の位置として算出することを特徴とする請求項１又は２記載の高品質メッシュモデルの生成システム。
【請求項５】
前記簡略化パラメータは、形状近似許容誤差を規定するものであって、
前記統合頂点対決定手段は、
前記新頂点位置算出手段によって算出された新頂点のうち、形状近似誤差が前記簡略化パラメータ以下の新頂点に対応する頂点対を絞り込む頂点対絞込み手段と、
絞り込まれた各頂点対について、頂点対に接する各面分についてのストレッチの最低値・平均値と、新頂点に接する各面分についてのストレッチの最低値・平均値とのそれぞれの比を求めて歪最低値評価値と歪平均値評価値を算出するとともに、頂点対に接する面分の面積の逆数を求めて面分粗密評価値を算出し、歪最低値評価と歪平均値評価値と面分粗密評価値とを乗じて総合評価値を算出する評価値算出手段と、
前記総合評価値が最大の頂点対を選定する頂点対選定手段と、
を有することを特徴とする請求項１乃至４のいずれかに記載の高品質メッシュモデルの生成システム。
【請求項６】
前記データベースは面分要素数を記憶したものであって、
前記繰返手段は、前記データベースから前記面分要素数を読み出し、生成された高品質メッシュモデルの面分要素の数が前記面分要素数に一致するまで繰り返させることを特徴とする請求項１乃至５のいずれかに記載の高品質メッシュモデルの生成システム。
【請求項７】
低品質メッシュモデル、細分化パラメータ、簡略化パラメータを記憶したデータベースから低品質メッシュモデルと細分化パラメータを読み出し、低品質メッシュモデルの各面分要素を細分化パラメータに適合するように細分化する処理と、
細分化されたメッシュモデルの各頂点対を統合したときの新頂点の位置を算出する処理と、
前記データベースから簡略化パラメータを読み出し、新頂点の位置が簡略化パラメータに適合する頂点対を絞り込み、その中から面分歪と面分粗密に関する総合評価値が最大の頂点対を決定する処理と、
前記細分化されたメッシュモデルについて、決定された頂点対を統合して新頂点の位置を設定する処理と、
新頂点の位置設定で生成されたメッシュモデルを前記細分化されたメッシュモデルに入れ替えて前記新頂点の位置の算出、前記頂点対の決定、前記新頂点の位置の設定を繰り返させる処理と、
をコンピュータに実行させることを特徴とする高品質メッシュモデルの生成プログラム。
【請求項８】
前記細分化パラメータは、面分の稜線の長さを規定するものであって、
前記細分化する処理は、細分化パラメータよりも長い稜線に中点を生成する処理と、
中点を他の中点あるいは頂点と結んで面分を分割する処理と、
を実行させることを特徴とする請求項７記載の高品質メッシュモデルの生成プログラム。
【請求項９】
前記新頂点の位置を算出する処理は、頂点対に隣接する頂点の重心を新頂点の位置として算出することを特徴とする請求項７又は８記載の高品質メッシュモデルの生成プログラム。
【請求項１０】
前記新頂点の位置を算出する処理は、頂点対に接する各面分と新頂点との自乗距離の和が最小となる位置を新頂点の位置として算出することを特徴とする請求項７又は８記載の高品質メッシュモデルの生成プログラム。
【請求項１１】
前記簡略化パラメータは、形状近似許容誤差を規定するものであって、
前記頂点対を決定する処理は、
算出された新頂点のうち、形状近似誤差が前記簡略化パラメータ以下の新頂点に対応する頂点対を絞り込む処理と、
絞り込まれた各頂点対について、頂点対に接する各面分についてのストレッチの最低値・平均値と、新頂点に接する各面分についてのストレッチの最低値・平均値とのそれぞれの比を求めて歪最低値評価値と歪平均値評価値を算出するとともに、頂点対に接する面分の面積の逆数を求めて面分粗密評価値を算出し、歪最低値評価と歪平均値評価値と面分粗密評価値とを乗じて総合評価値を算出する処理と、
前記総合評価値が最大の頂点対を選定する処理と、
を実行させることを特徴とする請求項７乃至１０のいずれかに記載の高品質メッシュモデルの生成プログラム。
【請求項１２】
前記データベースは面分要素数を記憶したものであって、
前記繰り返させる処理は、前記データベースから前記面分要素数を読み出し、生成された高品質メッシュモデルの面分要素の数が前記面分要素数に一致するまで繰り返させることを特徴とする請求項７乃至１１のいずれかに記載の高品質メッシュモデルの生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、低品質のメッシュモデルから高品質のメッシュモデルを生成する生成システムおよび生成プログラムに関する。
【背景技術】
【０００２】
近年、表面を細かい面分要素（メッシュ)の集合体として表現したメッシュモデルは、コンピュータグラフィックスの表示用モデルとしてだけではなく、工業製品の設計・生産分野にも広く利用されるようになってきている。
【０００３】
要求されるメッシュの性質は分野によって様々であり、表示や製品設計においては高い形状表現精度や面分数の削減が要求される。製品の強度や衝突、熱変形などの評価を行うための有限要素解析では、更に面分歪が少ないといった高いメッシュ品質が要求される。
【０００４】
メッシュ品質を改善する手法としては、ドローネ法とラプラシアンスムージング法に基づく手法（非特許文献１参照）、パラメタライゼーション法に基づく手法（非特許文献２参照）が挙げられる。その他、関連する文献としては非特許文献３、非特許文献４がある。
【非特許文献１】E. Bechet, J. C. Cuilliere and F. Trochu: Generation of a finite element MESH from stereolithography (STL) files, Computer Aided Design, 34, pp. 1-17, 2002
【非特許文献２】Michael S. Floater: Parametarization and smooth approximation of surface triangulations, Computer Aided Geometric Design, pp. 231-250, 1997
【非特許文献３】M. Garland and P. S. Heckbert: Surface Simplification Using Quadric Error Metrics, proc. of SIGGRAPH 97, pp.209-216, 1997
【非特許文献４】H. Hoppe: Progressive Meshes, Computer Graphics (SIGGRAPH'96), pp. 98-108, 1996
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１の手法は、高品質メッシュモデルの解像度を変更しようとした場合に、その都度、初期状態の低品質メッシュモデルを用いてその面分数を変更する処理を行う必要があるため、計算コストがかかるという問題がある。
【０００６】
また、非特許文献２の手法は、形状近似の管理ができず複雑な形状では適用が困難であり、また計算コストもかかるという問題がある。
【０００７】
本発明は、上記に鑑みてなされたものであり、その目的とするところは、複雑な形状に対しても低品質メッシュモデルから高品質のメッシュモデルを高速に生成し得る高品質メッシュモデルの生成システムおよび生成プログラムを提供することにある。
【課題を解決するための手段】
【０００８】
第１の本発明に係る高品質メッシュモデルの生成システムは、低品質メッシュモデル、細分化パラメータ、簡略化パラメータを記憶したデータベースから低品質メッシュモデルと細分化パラメータを読み出し、低品質メッシュモデルの各面分要素を細分化パラメータに適合するように細分化する細分化手段と、細分化されたメッシュモデルの各頂点対を統合したときの新頂点の位置を算出する新頂点位置算出手段と、前記データベースから簡略化パラメータを読み出し、新頂点の位置が簡略化パラメータに適合する頂点対を絞り込み、その中から面分歪と面分粗密に関する総合評価値が最大の頂点対を決定する統合頂点対決定手段と、前記細分化されたメッシュモデルについて、決定された頂点対を統合して新頂点の位置を設定する新頂点位置設定手段と、新頂点の位置設定で生成された高品質メッシュモデルを前記細分化されたメッシュモデルに入れ替えて前記新頂点位置算出手段、前記統合頂点対決定手段、前記新頂点位置設定手段に処理を繰り返させる繰返手段と、を有することを特徴とする。
【０００９】
第２の本発明に係る高品質メッシュモデルの生成プログラムは、低品質メッシュモデル、細分化パラメータ、簡略化パラメータを記憶したデータベースから低品質メッシュモデルと細分化パラメータを読み出し、低品質メッシュモデルの各面分要素を細分化パラメータに適合するように細分化する処理と、細分化されたメッシュモデルの各頂点対を統合したときの新頂点の位置を算出する処理と、前記データベースから簡略化パラメータを読み出し、新頂点の位置が簡略化パラメータに適合する頂点対を絞り込み、その中から面分歪と面分粗密に関する総合評価値が最大の頂点対を決定する処理と、前記細分化されたメッシュモデルについて、決定された頂点対を統合して新頂点の位置を設定する処理と、新頂点の位置設定で生成されたメッシュモデルを前記細分化されたメッシュモデルに入れ替えて前記新頂点の位置の算出、前記頂点対の決定、前記新頂点の位置の設定を繰り返させる処理と、をコンピュータに実行させることを特徴とする。
【００１０】
第１、第２の本発明にあっては、低品質メッシュモデルを細分化パラメータに適合するように細分化することでメッシュの操作自由度を上げ、その後に、品質を規定する簡略化パラメータに適合するようにメッシュモデルを簡略化することで、低品質メッシュモデルから高品質のメッシュモデルを生成する。
【００１１】
簡略化の処理では、細分化されたメッシュモデルの新頂点を算出し、新頂点が簡略化パラメータに適合する頂点対に絞り込むことで、高品質化に適した頂点対を統合の対象にするとともに、その頂点対の中で面分歪と面分粗密に関する総合評価値が最大のものを統合することで新頂点を設定してメッシュモデルを生成し、このメッシュモデルを低品質メッシュモデルに入れ替えて上記一連の処理を繰り返し行うことで、複雑な形状に対しても高品質化を図れるようにしている。
【００１２】
また、処理度に高品質メッシュモデルの頂点の数が１つずつ異なる多重解像度表現としたことで、高品質メッシュモデルを一旦生成した後は、その面分数を変更する処理を高速にできるようにしている。
【発明の効果】
【００１３】
本発明に係る高品質メッシュモデルの生成システム、生成プログラムによれば、複雑な形状に対しても低品質メッシュモデルから高品質のメッシュモデルを生成することができる。また、面分数の異なるメッシュモデルを高速に生成することができる。
【発明を実施するための最良の形態】
【００１４】
［１］基本概念
まず、本実施の形態における高品質メッシュモデルの生成手法の基本概念について図１を用いて説明する。同図では、本手法のアプローチの方向をａ１とａ２、非特許文献１，非特許文献２の手法のものをａ３で示してある。同図に示すように、非特許文献１、非特許文献２のいずれの手法も、低品質メッシュモデルから直接的に高品質メッシュモデルを生成しようと試みたものである。
【００１５】
これに対し、本実施形態の高品質メッシュモデルの生成システムは、低品質メッシュモデルの面分数を増加させることで細分化し(ａ１)、高密度化して操作性を高めた後に、品質を考慮しながら面分数を削減させることで簡略化する(ａ２)というアプローチをとることで、高品質メッシュモデルの生成を実現するものである。
【００１６】
ここでは、面分歪みが小さく、面分の粗密分布が一様であるものを高品質と定義する。また、本実施の形態で扱うメッシュモデルは、全ての面分を三角形で表すようにした三角形メッシュモデルとする。
【００１７】
［２］システムの概略構成
図２の機能ブロック図に示すように、高品質メッシュモデルの生成システム１は、メッシュ細分化部２、メッシュ簡略化部３、を備えた構成である。本生成システム１はコンピュータによって構成され、データベース４は大容量の記憶装置で構成される。データベース４には、製品の設計形状をコンピュータグラフィックス化したソリッドモデルが、ＣＧ３次元ＣＡＤ(Computer Adied Design)やＣＧ(Computer Graphics)モデラ等によって細かい面分要素に分割(メッシュ分割)された低品質メッシュモデル５、面分の最長辺の長さの上限値を指定する閾値として細分化パラメータσsize、形状近似許容誤差を示す簡略化パラメータτtolが記憶される。
【００１８】
メッシュ細分化部２、メッシュ簡略化部３における各処理は、本システムにインストールされた生成プログラムによって実行される。以下、各部の処理について詳細に説明する。
【００１９】
［３］メッシュ細分化部２の構成・処理
図３の機能ブロック図に示すように、メッシュ細分化部２は、稜線中点生成部８、面分分割部９を備えた構成である。メッシュ細分化部２は、低品質メッシュモデル５、細分化パラメータσsizeをデータベース４から読み出し、低品質メッシュモデル５を細分化して高密度メッシュモデル６を生成する。細分化に際しては、入力された低品質メッシュモデル５の基本形状を損なうことなく面分サイズ(面分の最長辺の長さ)の均一化を図る。
【００２０】
具体的には、まず、稜線中点生成部８で、各面分要素について、細分化パラメータσsizeよりも長い稜線に中点を生成する。次に、面分分割部９で、図４(ａ)に示すように、３辺の全てに中点が発生した面分についてはその３つの中点を結ぶことで面分分割し、図４(ｂ)に示すように、２辺に中点が発生した面分についてはその２つの中点を結ぶとともに、これによって生じた四角形を三角形に面分分割し、図４(ｃ)に示すように、１辺に中点が発生した面分についてはその中点と対向する頂点とを結ぶことで面分分割する。
【００２１】
メッシュ細分化部２では、この処理を全ての稜線の長さが細分化パラメータσsizeよりも小さくなるまで行うことで、高密度メッシュモデル６を生成し、メッシュ簡略化部３へ出力する。
【００２２】
［４］メッシュ簡略化部３の構成・処理
図５の機能ブロック図に示すように、メッシュ簡略化部３は、新頂点位置算出部１１、統合頂点対決定部１２、新頂点位置設定部１３を備えた構成である。メッシュ簡略化部３は、高密度メッシュモデル６とデータベース４から読み出した簡略化パラメータτtolとを用いて低解像度の高品質メッシュモデル７を生成する。以下、各部の処理について詳細に説明する。
【００２３】
［５］新頂点位置算出部１１の処理
新頂点位置算出部１１では、高密度メッシュモデル６の頂点数を減らして低解像度化を図るため、図６に示すように、高密度メッシュモデル６における任意の頂点対(ｉ，ｊ)を統合したときの新たな頂点ｋの位置ｐｋを算出する。
【００２４】
新たな頂点の位置算出では、頂点対(ｉ，ｊ)に隣接する頂点の重心を算出するか、又は頂点対に接する面分の集合と新頂点との自乗距離の和が最小となる位置(ＱＥＭ点(Quadric Error Metrics))を新頂点の位置として算出する。重心の算出は次式に基づいて行う。
【００２５】
ｐｋ＝Σ(ｍ∈ｋ＊)ｐｍ /|ｋ＊|       (１)
ここで、ｋ＊は頂点ｋに隣接する頂点の集合を表している。重心を算出した場合には、頂点対を統合した後の面分の歪みを小さくし、隣接面分間の面積を均一化することができる。
【００２６】
一方、ＱＥＭ点は、非特許文献３に記載の手法で求める。具体的には、まず、図７に示すように、位置がｐｉの頂点ｉに接する各面分ｆの集合Ｆｉと新頂点位置ｐｋとの自乗距離の和を次式に基づいて計算する。
【００２７】
Δｉ(ｐｋ)＝Σ(ｆ∈Ｆｉ)(ｆｆＴ ｐｋ)２
＝ｐｋＴ(Σ(ｆ∈Ｆｉ)Ｋｆ)ｐｋ
＝ｐｋＴＱｉｐｋ         (２)
ここで、Ｑｉは(４×４)の行列である。
【００２８】
次に、頂点対(ｉ，ｊ)に接する各面分の集合と頂点位置ｐｋとの自乗距離の和を次式に基づいて計算する。
【００２９】
Δij(ｐｋ)＝ｐｋＴ(Ｑｉ＋Ｑｊ)ｐｋ  (３)
この自乗距離Δij(ｐｋ)が最小となる頂点位置ｐｋがＱＥＭ点である。
【００３０】
式(３)において下記条件
∂Δij／∂ｘ＝∂Δij／∂ｙ＝∂Δij／∂ｚ＝０
を満たす頂点位置ｐｋは、次式(４)で求められる。
【数１】
2005242651.tif 000003
【００３１】
ここで、Ｑｉ＋Ｑｊ＝｛ｑｍｎ｝である。ＱＥＭ点を算出した場合には、新頂点の位置を形状近似誤差が最小となるようにすることができる。
【００３２】
新頂点位置算出部１１では、上記処理を繰り返すことにより、全ての頂点対について統合後の候補となる新たな頂点の位置を算出する。
【００３３】
［６］統合頂点対決定部１２の処理
統合頂点対決定部１２は、高密度メッシュモデル６と簡略化パラメータτtolを用いて、新頂点位置算出部１１が算出した新頂点位置の候補の中から最も適切な新頂点を１つ選択し、これに対応する統合すべき頂点対を決定する。
【００３４】
簡略化パラメータτtolは、形状近似許容値である。形状近似誤差には、式(３)で表したΔij(ｐｋ)を用いる。また、データベース４には次のものを予め記憶させておく。
【００３５】
Ｇ：面分要素数
ｖｎ：面分内積閾値
図８の機能ブロック図に示すように、統合頂点対決定部１２は、頂点対絞込み部２１、評価値算出部２２、頂点対選定部２３を備えた構成である。頂点対絞込み部２１、評価値算出部２２、頂点対選定部２３の各処理は、本システムにインストールされた生成プログラムによって実行される。以下、各部の処理について説明する。
【００３６】
［７］頂点対絞込み部２１の処理
頂点対絞込み部２１は、データベース４から簡略化パラメータτtol、面分内積閾値ｖｎを読み出し、高密度メッシュモデル６の頂点対集合、新頂点位置算出部１１によって算出された新頂点位置集合｛ｐｋ｝を用いて、統合後の新頂点が目標値に適合する頂点対を絞り込む。具体的には次の処理を行う。
【００３７】
［形状近似誤差の保証］
次式を満たし、統合後の新頂点の形状近似誤差が一定値以内となる頂点対を選別する。
【００３８】
ｐｋＴ(Ｑｉ＋Ｑｊ)ｐｋ≦τtol    (５)
［面裏返りの抑制］
次式を満たし、新頂点の位置が面分の反対側にならない頂点対を選別する。
【００３９】
∀ｆａ∈Ｆｉ∪Ｆｊ，∀ｆｂ∈Ｆｋ
ｎfb・ｎfa≧ｖｎ                       (６)
ここで、ｎfaは統合前の頂点対に接する面分ｆの法線ベクトルであり、ｎfbは統合後の新頂点に接する面分ｆの法線ベクトルである。閾値ｖｎは、一例として０〜−０．９の値とする。図９に示すように、Ｆｉ∪Ｆｊは頂点対(ｉ，ｊ)に接する面分の集合であり、Ｆｋは新頂点ｋに接する面分の集合である。
【００４０】
上記処理によって、頂点対に接するいずれかの面分の法線ベクトルの向きが統合の前後で反転するような頂点対については統合の対象から除外されることになる。
【００４１】
頂点対絞込み部２１は、上記各目標値に適合する頂点対の集合を評価値算出部２２および頂点対選定部２３へ出力する。
【００４２】
［８］評価値算出部２２の処理
評価値算出部２２では、頂点対絞込み部２１で絞り込まれた頂点対集合、新頂点位置算出部１１で算出した新頂点位置集合｛ｐｋ｝を用いて、新頂点位置集合｛ｐｋ｝に含まれる新頂点のうち、頂点対絞込み部２１で絞り込まれた頂点対に対応するものについて面分歪と面分粗密の評価値を算出する。
【００４３】
本実施の形態では、面分歪みの指標としてストレッチを用いる。ストレッチは、面分歪みを示す指標であり、面分要素の内接円半径×√(１２)/(面分要素の最長辺長さ)として定義される。面分ｆについてのストレッチは次式(７)で表される。
【数２】
2005242651.tif 000004
【００４４】
ここで、ｓ＝(ｌ1f＋ｌ2f＋ｌ3f )/２である。図１０に示すように、ストレッチの値が１に近いほど面分要素の形状は正三角形に近づき、０に近づくほど歪みが大きくなる。評価値算出部２２は、ストレッチを用いて次の処理を行う。
【００４５】
［面分歪評価値の算出］
次式(８)に示すように、統合前の頂点対(ｉ，ｊ)に接する面分集合Ｆｉ∪Ｆｊについてのストレッチの最低値と、統合後の新頂点ｋに接する面分集合Ｆｋについてのストレッチの最低値との比を求めることにより歪最低値評価値を算出する。
【００４６】
ΔijSTmin＝minｆ'∈ＦｋSTCH(ｆ')/minｆ∈wSTCH(ｆ)  (８)
ここで、ｗ＝Ｆｉ∪Ｆｊである。
【００４７】
また、次式(９)に示すように、統合前の頂点対(ｉ，ｊ)に接する面分集合Ｆｉ∪Ｆｊについてのストレッチの平均値と、新頂点ｋに接する面分集合Ｆｋについてのストレッチの平均値との比を求めることにより、歪平均値評価値を算出する。
【００４８】
ΔijSTave＝|ｗ|Σｆ'∈ＦｋSTCH(ｆ')/(|Ｆｋ|Σｆ∈wSTCH(ｆ))  (９)
歪最低値評価値、歪平均値評価値が大きい場合は、頂点対の近傍に極端に歪んだ面分もしくは平均的に歪みの大きなメッシュをもつ一方、統合後には新頂点の近傍に極端に歪んだ面分をもたず高い形状品質になると評価できる。
【００４９】
［面分粗密評価値の算出］
メッシュ内の面分分布の一様化を図るために、統合によって小さな面分を除去できる頂点対を統合する。このための評価値は、次式で表される、頂点ｉ，ｊに接する各面分の総和面積の逆数を用いる。
【００５０】
αij＝１/Σｆ∈ Ｆｉ∩ＦｊArea(ｆ)  (１０)
ここで、Area(ｆ)は面分ｆの面積である。評価値算出部２２は、算出した各評価値の集合を頂点対選定部２３へ出力する。
【００５１】
［９］頂点対選定部２３の処理
頂点対選定部２３は、頂点対絞込み部２１で絞り込まれた頂点対のうち、統合するのに最も適した１つの頂点対を各評価値に基づいて選定する。具体的には、頂点対(ｉ，ｊ)の総合評価値εijを次式に基づき算出する。
【００５２】
εij＝ΔijSTmin×ΔijSTave×αij     (１１)
そして、総合評価値εijが最も大きな頂点対(ｉ，ｊ)を統合対象の頂点対(統合頂点対)として選定する。頂点対選定部２３は、選定した統合頂点対(ｉ，ｊ)を新頂点位置設定部１３へ出力する。
【００５３】
［１０］新頂点位置設定部１３の処理
新頂点位置設定部１３では、高密度メッシュモデル６、新頂点位置ｐｋ、統合頂点対(ｉ，ｊ)を用い、edge collapse手法(非特許文献４参照)により統合頂点対(ｉ，ｊ)を統合して新頂点の位置を設定する。これによって総合頂点対(ｉ，ｊ)と総合頂点対に接続された稜線とが削除されるとともに、新頂点と新頂点に接続される稜線とが設定される。新頂点位置設定部１３は、このようにして生成された高品質メッシュモデル７を出力する。
【００５４】
［１１］繰り返し処理
メッシュ簡略化部３では、新頂点位置設定部１３が出力した高品質メッシュモデル７を上記各処理で用いた高密度メッシュモデル６と入れ替えて、新頂点位置算出部１１、統合頂点対決定部１２、新頂点位置設定部１３の各部における処理を繰り返し行う。
【００５５】
１回の処理では、メッシュモデル全体のうちの２つの頂点が１つに統合されるだけであるので、繰り返し処理を行うことで低解像度化を図る。繰り返し処理は、生成した高品質メッシュモデル７の面分の要素数が予め設定された面分要素数Ｇに一致するまで繰り返す。
【００５６】
具体的には、新頂点位置設定部１３は、面分要素数Ｇをデータベース４から読み出し、高品質メッシュモデル７の面分要素数がＧよりも大きい場合には、高品質メッシュモデル７を新頂点位置算出部１１、統合頂点対決定部１２、新頂点位置設定部１３へ出力して上記各処理を繰り返させ、高品質メッシュモデル７の面分要素数がＧに一致したところで各処理を停止させる。
【００５７】
［１２］適用結果と評価
次に、本手法を適用した結果と評価について説明する。
【００５８】
図１１(ａ)は、本生成システム１での処理の対象とする低品質メッシュモデルを生成するためのソリッドモデルを示す図である。図１１(ｂ)は、ソリッドモデルを用いてＦＥＭメッシャで生成した低品質メッシュモデルを示す図である。この低品質メッシュモデルの面分要素数は8,720個とした。
【００５９】
図１２(ａ)は、図１１(ｂ)の低品質メッシュモデルを用いて本生成システム１のメッシュ細分化部２により細分化した高密度メッシュモデルを示す図であり、面分要素数は68,844となっている。細分化パラメータσsizeの値は0.2とした。
【００６０】
図１２(ｂ)乃至(ｅ)は、図１２(ａ)の高密度メッシュモデルを用いてメッシュ簡略化部３により簡略化した高品質メッシュモデルであり、それぞれの面分要素数は15,000、9,000、6,000、3,092となっている。簡略化パラメータτtolの値は0.01とした。
【００６１】
市販のパソコンで処理を行ったところ、細分化の処理時間は2.16秒、図１２(ａ)から(ｅ)までの簡略化の処理時間は11.59秒であった。
【００６２】
図１３は、各メッシュモデルについてストレッチの分布をまとめたグラフである。同グラフの(１)，(２)，(３)，(４)，(５)は、それぞれ図１１(ｂ)，図１２(ａ)，(ｂ)，(ｃ)，(ｄ)のメッシュモデルに対応している。
【００６３】
本生成システム１によって生成された面分要素数6,000の高品質メッシュモデルのストレッチ分布(同グラフの(５))は、これよりも面分要素数が8,720と多いメッシュ分割されたメッシュモデル(同グラフの(１))と比べて、1.0の値近傍に多く分布しており、歪みの少ないメッシュモデルが生成されていることが確認された。
【００６４】
したがって、本実施の形態によれば、低品質メッシュモデルを稜線長さを規定する細分化パラメータに適合するように細分化することでメッシュの操作自由度を向上させ、その後に品質を規定する簡略化パラメータに適合するように簡略化することで、低品質メッシュモデルを確実かつ高精度に高品質化することができる。
【００６５】
本実施の形態によれば、簡略化パラメータを形状近似許容誤差として規定し、細分化されたメッシュモデルの頂点対のうち、新頂点の形状近似誤差が簡略化パラメータ以下に抑えられる頂点対に絞り込むことで、高品質化に適した頂点対を統合の対象にすることができる。
【００６６】
本実施の形態によれば、絞り込まれた頂点対の中で面分歪と面分粗密に関する総合評価値が最大のものを統合して新頂点を設定することでメッシュモデルを生成し、このメッシュモデルを低品質メッシュモデルに入れ替えて一連の処理を繰り返し行うことで、複雑な形状に対しても確実かつ高精度に高品質化を図ることができる。
【００６７】
本実施の形態によれば、処理を繰り返す度に高品質メッシュモデルの頂点の数が１つずつ異なるようにした多重解像度表現を行うようにしたことで、高品質メッシュモデルを一旦生成した後は、その面分数を変更する処理を高速に実行することができる。
【００６８】
本実施の形態によれば、新頂点ｋの算出に際して、頂点対(ｉ，ｊ)に隣接する頂点の重心を新頂点ｋの位置として算出することで、頂点対(ｉ，ｊ)を統合した後の面分の歪みを小さくでき、隣接面分間の面積を均一化することができる。
【００６９】
本実施の形態によれば、新頂点ｋの算出に際して、頂点対(ｉ，ｊ)に接する面分の集合と新頂点ｋとの自乗距離の和が最小となる位置を新頂点ｋの位置として算出することで、形状近似誤差が最小となる新頂点ｋの位置を算出することができる。
【図面の簡単な説明】
【００７０】
【図１】高品質メッシュモデル生成手法のアプローチを示す概念図である。
【図２】一実施形態における高品質メッシュモデルの生成システムの構成を示す機能ブロック図である。
【図３】メッシュ細分化部の構成を示す機能ブロック図である。
【図４】面分分割の規則を説明するための図である。
【図５】メッシュ簡略化部の構成を示す機能ブロック図である。
【図６】頂点対を１つの新頂点に統合する様子を示す図である。
【図７】新頂点についての形状近似誤差を説明するための図である。
【図８】統合頂点対決定部の構成を示す機能ブロック図である。
【図９】同図(ａ)は統合前の頂点対に接する面分集合を示す図であり、同図(ｂ)は統合後の新頂点に接する面分集合を示す図である。
【図１０】ストレッチを説明するための図である。
【図１１】同図(ａ)はソリッドモデル、同図(ｂ)はメッシュ分割した高密度メッシュモデルを示す図である。
【図１２】同図(ａ)は上記生成システムによって細分化された高密度メッシュモデルを示す図であり、面分要素数は68,844である。同図(ｂ)乃至(ｅ)は簡略化された高品質メッシュモデルであり、同図(ｂ)の面分要素数は15,000、同図(ｃ)の面分要素数は9,000、同図(ｄ)の面分要素数は6,000、同図(ｅ)の面分要素数は3,092である。
【図１３】メッシュ分割、細分化、簡略化によって生成された各メッシュモデルについてのストレッチの分布を示すグラフである。
【符号の説明】
【００７１】
１…高品質メッシュモデルの生成システム
２…メッシュ細分化部
３…メッシュ簡略化部
４…データベース
５…低品質メッシュモデル
６…高密度メッシュモデル
７…高品質メッシュモデル
８…稜線中点生成部
９…面分分割部
１１…新頂点位置算出部
１２…統合頂点対決定部
１３…新頂点位置設定部
２１…頂点対絞込み部
２２…評価値算出部
２３…頂点対選定部
【図１】
2005242651.tif 000005
【図２】
2005242651.tif 000006
【図３】
2005242651.tif 000007
【図４】
2005242651.tif 000008
【図５】
2005242651.tif 000009
【図６】
2005242651.tif 000010
【図７】
2005242651.tif 000011
【図８】
2005242651.tif 000012
【図９】
2005242651.tif 000013
【図１０】
2005242651.tif 000014
【図１１】
2005242651.tif 000015
【図１２】
2005242651.tif 000016
【図１３】
2005242651.tif 000017