(57)【要約】   【課題】  メッシュを生成するときに、効率的な節点検索ができ、かつ、複数の処理エレメントで並列処理が可能となる。  【解決手段】  各処理エレメント１２は、物体の内部に配置された節点および物体の表面形状を画定させる表面パッチに基づいて、各要素が拘束デローニ（ＣＤＴ）分割となるようなメッシュを生成するＣＤＴ処理部１６と、要素がＣＤＴを満たさない場合に、ある要素の節点と新たな要素を形成する衛星節点を探索するために、要素の節点と新たな節点とで作られる図形が、何れの表面パッチとも交わらず、かつ、既にできた要素の何れとも交わらないような新たな節点であって、要素の節点および新たな節点で作られる図形の内部に何れの節点も存在しないような新たな節点を選択する準拘束デローニ分割（ＳＣＤＴ）処理部１８とを備える。【選択図】  図１
2005196273.tif 000002
【特許請求の範囲】
【請求項１】
物体の内部に配置された節点および物体の表面形状を画定させる表面パッチに基づいて、各要素が拘束デローニ（ＣＤＴ）分割となるようなメッシュを生成する拘束デローニ分割手段を備えたメッシュ生成システムであって、
生成された要素がＣＤＴを満たさない場合に、ある要素の節点と、新たな要素を形成するような衛星節点を探索するために、前記要素の節点と、新たな節点とで作られる図形が、何れの表面パッチとも交わらず、かつ、それまでに作られた要素の何れとも交わらないような新たな節点であって、要素の節点および新たな節点で作られる図形の内部に何れの節点も存在しないような新たな節点を選択する準拘束デローニ分割（ＳＣＤＴ）手段を備え、
前記準拘束デローニ分割手段が、連続したＣＤＴ境界面を求め、ＣＤＴ分割とならない領域を隔離した後、
（ａ）前記隔離された領域において、所定の順序にしたがってＣＤＴ境界面に位置する図形を選択し、
（ｂ）当該選択された図形に接する新たな要素を生成し、その後、新たな要素を前記隔離された領域から除外し、
前記（ａ）および（ｂ）を繰り返すことによりＣＤＴ分割となるような要素を生成することを特徴とするメッシュ生成システム。
【請求項２】
さらに、各要素がデローニ分割となるようなメッシュを生成するデローニ分割手段を備え、
前記デローニ分割手段により得られた要素がＣＤＴでない場合に、前記拘束デローニ分割手段により新たな要素の生成が実行されることを特徴とする請求項１に記載のメッシュ生成システム。
【請求項３】
前記準拘束デローニ分割手段が、前記図形を形成する節点を一意的に特定する番号をキーとするソート順で、前記新たな図形を生成することを特徴とする請求項１または２に記載のメッシュ生成システム。
【請求項４】
複数の処理エレメントを有し、処理エレメントが、それぞれ、物体を分割した独立した領域においてメッシュを生成するメッシュ生成システムであって、
各処理エレメントが、
物体の内部に配置された節点および物体の表面形状を画定させる表面パッチに基づいて、各要素が拘束デローニ（ＣＤＴ）分割となるようなメッシュを生成する拘束デローニ分割手段と、
生成された要素がＣＤＴを満たさない場合に、ある要素の節点と、新たな要素を形成するような衛星節点を探索するために、前記要素の節点と、新たな節点とで作られる図形が、何れの表面パッチとも交わらず、かつ、それまでに作られた要素の何れとも交わらないような新たな節点であって、要素の節点および新たな節点で作られる図形の内部に何れの節点も存在しないような新たな節点を選択する準拘束デローニ分割（ＳＣＤＴ）手段とを備え、
前記準拘束デローニ分割手段が、連続したＣＤＴ境界面を求め、ＣＤＴ分割とならない領域を隔離した後、
（ａ）前記隔離された領域において、所定の順序にしたがってＣＤＴ境界面に位置する図形を選択し、
（ｂ）当該選択された図形に接する新たな要素を生成し、その後、新たな要素を前記隔離された領域から除外し、
前記（ａ）および（ｂ）を繰り返すことによりＣＤＴ分割となるような要素を生成することを特徴とするメッシュ生成システム。
【請求項５】
前記各処理エレメントにおいて、予め表面パッチの情報がそれぞれの記憶装置に記憶され、
前記処理エレメントが、前記独立した領域の内部に位置する内部節点を生成する内部節点生成手段を備えたことを特徴とする請求項４に記載のメッシュ生成システム。
【請求項６】
コンピュータを、物体の内部に配置された節点および物体の表面形状を画定させる表面パッチに基づいて、各要素が拘束デローニ（ＣＤＴ）分割となるようなメッシュを生成する拘束デローニ分割手段として機能させる、当該コンピュータにより読み取り可能なメッシュ生成プログラムであって、
さらに、前記コンピュータを、
生成された要素がＣＤＴを満たさない場合に、ある要素の節点と、新たな要素を形成するような衛星節点を探索するために、前記要素の節点と、新たな節点とで作られる図形が、何れの表面パッチとも交わらず、かつ、それまでに作られた要素の何れとも交わらないような新たな節点であって、要素の節点および新たな節点で作られる図形の内部に何れの節点も存在しないような新たな節点を選択する準拘束デローニ分割（ＳＣＤＴ）手段として機能させ、
前記準拘束デローニ分割手段として機能させるときに、前記コンピュータに、連続したＣＤＴ境界面を求め、ＣＤＴ分割とならない領域を隔離するステップを実行させ、当該隔離ステップの後、前記コンピュータに、
（ａ）前記隔離された領域において、所定の順序にしたがってＣＤＴ境界面に位置する図形を選択するステップと、
（ｂ）当該選択された図形に接する新たな要素を生成し、その後、新たな要素を前記隔離された領域から除外するステップとを実行させ、
前記（ａ）および（ｂ）を繰り返すことによりＣＤＴ分割となるような要素を、前記コンピュータに生成させることを特徴とするメッシュ生成プログラム。
【請求項７】
さらに、前記コンピュータを、各要素がデローニ分割となるようなメッシュを生成するデローニ分割手段として機能させ、
前記コンピュータがデローニ分割手段として機能したときに得られた要素がＣＤＴでない場合に、前記コンピュータを、前記拘束デローニ分割手段として機能させて、新たな要素の生成が実行されることを特徴とする請求項６に記載のメッシュ生成プログラム。
【請求項８】
前記コンピュータを、準拘束デローニ分割手段として機能させるときに、前記図形を形成する節点を一意的に特定する番号をキーとするソート順で、前記新たな図形を生成するように、前記コンピュータを動作させることを特徴とする請求項６または７に記載のメッシュ生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限要素法（FEM）を用いたメッシュ生成システムおよび生成プログラムに関する。
【背景技術】
【０００２】
有限要素法（FEM）は、複雑形状への適応性が優れているという長所を持つ一方で、メッシュ生成に多大な労力を要するのが大きな欠点である。現在では、多数の優れた自動要素生成ソフトも市販されるには至っているものの、その大部分は単一のCPU環境を前提としている。一部のソフトでは、並列処理が可能なものもあるが、使用可能なCPUの個数は、数個のレベルに留まっている。これは要素生成のアルゴリズム自体に逐次的な処理が多く含まれていることに起因する。
【非特許文献１】Ｇ．ヤガワ（G. Yagawa）、Ｔ．ヤマダ（T. Yamada）共著、「フリーメッシュ法(Free mesh method)」、A Newmeshless finite element method、Comp. 第３８３頁〜３８６頁  １９９６年３月１８日
【非特許文献２】Ｇ．ヤガワ（G. Yagawa）、Ｔ．フルカワ(T. Furukawa)共著、「フリーメッシュ法の最近の開発(Recent developmentsof free mesh method)」、Int. J. Numer. Meth. Engng.、第１４１９頁〜第１４４３頁、２０００年
【非特許文献３】Ｍ．タメガワ(M. Tamegawa)、Ｔ．オガワ(T. Ogawa)、Ｎ．オギタ(N. Ogita)共著、「A new algorithm forthree-dimensional Voronoi tessellation」、Journal of Xomputational Physics 51、第１９１頁〜第２０７頁、１９８３年
【非特許文献４】Ｒ．Ａ．ドゥイヤー(R. A. Dwyer)著  「Hither-dimensional Voronoi diagrams in linearexpected time」、Discrete & Computational Geometry 6(4)、第３４３頁〜第３６７頁、１９９１年
【非特許文献５】Ｌ．Ｐ．チュウ(L. P. Chew)著、「Constrained Delaunay triangulations」、Algorithmica4(1)、第９７頁〜第１０８頁、１９８９年
【発明の開示】
【発明が解決しようとする課題】
【０００３】
その一方、フリーメッシュ法（FMM）は、FEMのメッシュ生成の労力を軽減することを目的に提案された計算手法であり、メッシュ生成を各節点の周囲に局所的に生成する（たとえば、非特許文献１および非特許文献２参照）。
【０００４】
この局所的な要素生成は、節点を単位として独立して処理することができ、多数のプロセッサーを用いた並列処理においても高い並列化効率を得ることができる。しかしながら、従来のFMMには、以下に挙げるような欠点がある。
(1) 単一プロセッサーで処理する場合では、大局的な要素生成、すなわち、通常のFEMを前提としたメッシュ生成の方が、圧倒的に計算時間が速い。
(2) 比較的単純な形状しか扱えない。亀裂のような鋭角を持つ形状に対しては、適用が困難である。
【０００５】
その一方で、デローニ分割を局所的に求めるためのアルゴリズムとして包装法（非特許文献３および非特許文献４参照）と呼ばれる手法が提案されている。この手法は、節点数をnとすると平均的な計算量はO(n)であるものの、次の問題点がある。
(3) 近接節点の検索に均等なバケットを用いるため、FEMに用いるような密度に大きな粗密がある節点配置では、計算量が急激に増大する。
【０００６】
また、本来、デローニ分割は節点のみで定まるものであるが、幾何形状を保持しつつ、デローニ分割を行う手法（拘束デローニ(Constrained Delaunay)分割：非特許文献５参照）として、包装法の修正アルゴリズムが提案されているが、次のような問題点がある。
(4) 計算量がO(n３)であり、実用的な規模の問題には適用できない。
(5) 表面パッチと節点が‘Ridge-protected’条件を満たしていない場合には、節点を追加する必要がある。ここで、‘Ridge-protected’条件とは、３次元の場合には、すべての表面パッチの三角形の各辺について、その両端の２点を通る球で、その内部と境界上に他の節点を含まないようなものが存在することである。
【０００７】
本発明は、上記種々の問題点を解決するため、効率的な節点検索ができ、かつ、複数の処理エレメントで並列処理が可能なメッシュ生成システムおよびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の目的は、物体の内部に配置された節点および物体の表面形状を画定させる表面パッチに基づいて、各要素が拘束デローニ（ＣＤＴ）分割となるようなメッシュを生成する拘束デローニ分割手段を備えたメッシュ生成システムであって、
生成された要素がＣＤＴを満たさない場合に、ある要素の節点と、新たな要素を形成するような衛星節点を探索するために、前記要素の節点と、新たな節点とで作られる図形が、何れの表面パッチとも交わらず、かつ、それまでに作られた要素の何れとも交わらないような新たな節点であって、要素の節点および新たな節点で作られる図形の内部に何れの節点も存在しないような新たな節点を選択する準拘束デローニ分割（ＳＣＤＴ）手段を備え、
前記準拘束デローニ分割手段が、連続したＣＤＴ境界面を求め、ＣＤＴ分割とならない領域を隔離した後、
（ａ）前記隔離された領域において、所定の順序にしたがってＣＤＴ境界面に位置する図形を選択し、
（ｂ）当該選択された図形に接する新たな要素を生成し、その後、新たな要素を前記隔離された領域から除外し、
前記（ａ）および（ｂ）を繰り返すことによりＣＤＴ分割となるような要素を生成することを特徴とするメッシュ生成システムにより達成される。
【０００９】
本発明によれば、ＣＤＴ分割とならない領域として隔離された領域で、所定の順序で要素を生成し、それを隔離された領域から取り出していく。これにより、ＣＤＴ分割とならない場合でも要素は一意的に決定される。
【００１０】
ここで、２次元の場合、要素は三角形であり、当該三角形の一辺の両端の節点と、新たな節点とにより、新たな図形、つまり三角形が形成され、これがＣＤＴであれば、新たな要素となる。また、３次元の場合、要素は四面体であり、当該四面体の一面を形成する三角形の３つの頂点に相当する節点と、新たな節点とにより新たな図形、つまり四面体が形成される。これがＣＤＴであれば、新たな要素となる。
【００１１】
好ましい実施態様においては、さらに、各要素がデローニ分割となるようなメッシュを生成するデローニ分割手段を備え、前記デローニ分割手段により得られた要素がＣＤＴでない場合に、前記拘束デローニ分割手段により新たな要素の生成が実行される。
【００１２】
より好ましい実施態様においては、前記準拘束デローニ分割手段が、前記図形を形成する節点を一意的に特定する番号をキーとするソート順で、前記新たな図形を生成する。
【００１３】
別の好ましい実施態様においては、メッシュ生成システムは、複数の処理エレメントを有し、処理エレメントが、それぞれ、物体を分割した独立した領域においてメッシュを生成する。この実施態様にかかる各処理エレメントは、
物体の内部に配置された節点および物体の表面形状を画定させる表面パッチに基づいて、各要素が拘束デローニ（ＣＤＴ）分割となるようなメッシュを生成する拘束デローニ分割手段と、
生成された要素がＣＤＴを満たさない場合に、ある要素の節点と、新たな要素を形成するような衛星節点を探索するために、前記要素の節点と、新たな節点とで作られる図形が、何れの表面パッチとも交わらず、かつ、それまでに作られた要素の何れとも交わらないような新たな節点であって、要素の節点および新たな節点で作られる図形の内部に何れの節点も存在しないような新たな節点を選択する準拘束デローニ分割（ＳＣＤＴ）手段とを備え、
前記準拘束デローニ分割手段が、連続したＣＤＴ境界面を求め、ＣＤＴ分割とならない領域を隔離した後、
（ａ）前記隔離された領域において、所定の順序にしたがってＣＤＴ境界面に位置する図形を選択し、
（ｂ）当該選択された図形に接する新たな要素を生成し、その後、新たな要素を前記隔離された領域から除外し、
前記（ａ）および（ｂ）を繰り返すことによりＣＤＴ分割となるような要素を生成する。
【００１４】
より好ましくは、前記各処理エレメントにおいて、予め表面パッチの情報がそれぞれの記憶装置に記憶され、前記処理エレメントが、前記独立した領域の内部に位置する内部節点を生成する内部節点生成手段を備えている。
【００１５】
また、本発明の目的は、コンピュータを、物体の内部に配置された節点および物体の表面形状を画定させる表面パッチに基づいて、各要素が拘束デローニ（ＣＤＴ）分割となるようなメッシュを生成する拘束デローニ分割手段として機能させる、当該コンピュータにより読み取り可能なメッシュ生成プログラムであって、
さらに、前記コンピュータを、
生成された要素がＣＤＴを満たさない場合に、ある要素の節点と、新たな要素を形成するような衛星節点を探索するために、前記要素の節点と、新たな節点とで作られる図形が、何れの表面パッチとも交わらず、かつ、それまでに作られた要素の何れとも交わらないような新たな節点であって、要素の節点および新たな節点で作られる図形の内部に何れの節点も存在しないような新たな節点を選択する準拘束デローニ分割（ＳＣＤＴ）手段として機能させ、
前記準拘束デローニ分割手段として機能させるときに、前記コンピュータに、連続したＣＤＴ境界面を求め、ＣＤＴ分割とならない領域を隔離するステップを実行させ、当該隔離ステップの後、前記コンピュータに、
（ａ）前記隔離された領域において、所定の順序にしたがってＣＤＴ境界面に位置する図形を選択するステップと、
（ｂ）当該選択された図形に接する新たな要素を生成し、その後、新たな要素を前記隔離された領域から除外するステップとを実行させ、
前記（ａ）および（ｂ）を繰り返すことによりＣＤＴ分割となるような要素を、前記コンピュータに生成させることを特徴とするメッシュ生成プログラムによっても達成される。
【００１６】
好ましい実施態様においては、さらに、前記コンピュータを、各要素がデローニ分割となるようなメッシュを生成するデローニ分割手段として機能させ、
前記コンピュータがデローニ分割手段として機能したときに得られた要素がＣＤＴでない場合に、前記コンピュータを、前記拘束デローニ分割手段として機能させて、新たな要素の生成が実行される。
【００１７】
この実施態様によれば、各処理エレメントで実質的に独立して、処理エレメント間の通信なしに、要素を生成することが可能となる。
【００１８】
より好ましい実施態様においては、前記コンピュータを、準拘束デローニ分割手段として機能させるときに、前記図形を形成する節点を一意的に特定する番号をキーとするソート順で、前記新たな図形を生成するように、前記コンピュータを動作させる。
【発明の効果】
【００１９】
本発明によれば、効率的な節点検索ができ、かつ、複数の処理エレメントで並列処理が可能なメッシュ生成システムおよびプログラムを提供することが可能となる。
【発明を実施するための最良の形態】
【００２０】
以下、添付図面を参照して本発明の実施の形態について説明する。図１は、本発明の実施の形態にかかるメッシュ生成システムの概略を示すブロックダイヤグラムである。本実施の形態においては、メッシュ生成システム１０は、Ｎ個の処理エレメント（ＰＥ）１２−１、１２−２、・・・、１２−Ｎを含み、それぞれが、バスなどで接続される。処理エレメント１２は、後述するデローニ(Delaunay)四面体分割（ＤＴ）を実行するＤＴ処理部１４と、拘束デローニ（Constrained Delaunay）四面体分割（ＣＤＴ）を実行するＣＤＴ処理部１６と、ＣＤＴを改良した分割手法である準拘束デローニ（sub-Constrained
Delaunay）四面体分割（ＳＣＤＴ）を実行するＳＣＤＴ処理部１８と、記憶装置２０とを備えている。記憶装置２０には、定義すべき物体中に位置する節点に関する節点情報（たとえば座標）２２および生成されたメッシュに関するメッシュ情報２４が含まれる。
【００２１】
本実施の形態においては、物体形状を定義するために、それぞれの処理エレメントが、通信することなく局地的に処理を実行し、メッシュ情報により定義される四面体がずれたりするような不整合が生じることなく、物体全体の形状を定義することができる。
【００２２】
以下、メッシュ生成システムの説明に先立って、本実施の形態において利用される用語を定義する。
【００２３】
［節点］
身の回りに存在する物体は連続体である。これをコンピュータで扱うためには離散化する必要がある。そこで、有限個の点を物体内に発生させ、これをもとに物体を表現する。これらの点を節点と呼ぶ。
【００２４】
［表面パッチ］
物体の形状を定義するための三角形の集まりを表面パッチという。
［メッシュ］
物体内に発生させた節点を結んで四面体の集合にしてから、各四面体について種々の処理が実行される。その四面体の集合をメッシュと呼ぶ。なお、四面体に限定されず六面体によりメッシュが構成されていても良い。
【００２５】
［デローニ分割］
図２（ａ）に示すような節点の集合が与えられたときに、三角形でその凸包領域を分割したものを三角形分割と呼ぶ（図２（ｂ）参照）。図２（ｂ）において、三角形ｂｃｄを考える。三角形ｂｃｄの外接円について、他の全ての節点ａ，ｅ，ｆ，ｇ，ｈはこの外接円の内部に一つも存在しない。このように、ある三角形についてその外接円の中に節点が一つも存在しないならば、その三角形をデローニ（Delaunay）の三角形（ＤＴ）と呼ぶ。なお、図２の例は２次元であったが、３次元の場合には、三角形が四面体になる。
【００２６】
図２（ｂ）に示す三角形分割において、それを構成するすべての３角形がDelaunay三角形であれば、その三角形分割をDelaunayの三角形分割（デローニ分割：ＤＴ）と呼ぶ。以下、本明細書において、「三角形」という語句には、２次元および３次元を区別しない場合には、「四面体」も含むものとする。
【００２７】
［包装法］
包装法は、デローニ分割を求めるアルゴリズムのうちの一つであり、図３（ａ）〜（ｄ）に示すように、デローニ三角形を一つずつ求めていくのが包装法である。図４に示すように、包装法では、まず、節点ａ、ｂを結ぶ辺ａｂの右側にある適当な節点が選ばれる（ステップ４０１）。初期的には選択された節点が候補節点となる。なお本実施の形態において、辺ａｂの右側とは、辺の終点ｂから始点ａを見た場合の「右側」と考える。
【００２８】
次いで、節点ａ，ｂと先に設定された候補節点を通る円の内部に選択された節点が存在するか否かが判断される（ステップ４０２）。ステップ４０２でイエス(Yes)と判断された場合には、ステップ４０１で選択された節点が、新たな候補節点として設定される（ステップ４０３）。
【００２９】
ステップ４０１〜４０３の処理が、辺ａｂの右側に位置する全ての節点について終了すると（ステップ４０４でイエス(Yes)）、最後の時点での候補節点の情報が、辺ａｂの右側に位置する三角形を形成する節点として記憶装置に記憶される（ステップ４０５）。この処理は、３次元の場合（四面体を形成する場合）も同様である。ここでは、辺に対する節点を考える代わりに、四面体に対する節点を考え、外接円の代わりに外接球を考えればよい。このような処理により得られる三角形がデローニ三角形となる。
【００３０】
［衛星節点探索］
ある節点を中心節点として、この節点から周囲の節点を候補節点とする処理を繰り返し、デローニ三角形を形成する処理について説明する。図５（ａ）に示すような節点が与えられていると考える。この例では中心節点を節点ａと考える。
【００３１】
衛星節点を探索する場合には、まず、中心節点に直近の節点が検索される（ステップ６０１）。図５（ａ）に示す例では、節点ｂが見出される（図５（ｂ）参照）。検索された節点が衛星節点として設定される（ステップ６０２）。次いで、最後にみつかった衛星節点と中心節点とを結ぶ線分について、図４のアルゴリズムを適用して、次の衛星節点が求められる（ステップ６０３）。線分ａｂについては、節点ｃがデローニ三角形を構成する節点になるため、これが衛星節点となる（図５（ｃ）参照）。同様の処理を、求めた衛星節点が、最初に見出された衛星節点（図５の例では節点ｂ）と一致するまで、ステップ６０３の処理が繰り返される（ステップ６０４参照）。これにより、図５（ｄ）、（ｅ）に示すように衛星節点が決定され、デローニ三角形を形成することができる。
【００３２】
図６の処理は、いわゆる内部節点のときに適用される。次に、表面パッチを含む境界節点について適用される処理について説明する。図７（ａ）に示すような節点が与えられていると考える。なお、図７（ａ）〜（ｅ）において、破線は表面パッチを示している。この場合には、中心節点は表面パッチ上の節点が選択される。図７（ａ）においては、中心節点を節点ａと考える。
【００３３】
図８に示すように、まず、中心節点を始点或いは終点とする表面パッチが検索される（ステップ８０１）。図７（ａ）の例では、表面パッチｅａ，ａｂが見出され、これにより、節点ｂおよびｅが見出される。これら表面パッチには向きが含まれる。次いで、中心節点を終点とする表面パッチの他方の節点が最初の衛星節点に設定される（ステップ８０２）。図７（ａ）では、節点ｅが最初の衛星節点になる。
【００３４】
その後、最後にみつかった衛星節点と中心節点とを結ぶ線分について、図４に示すアルゴリズムを適用して次の衛星節点が求められる（ステップ８０３）。図７（ｂ）のように線分ｅａ（辺ａｅ）については、節点ｄが衛星節点として設定される（図７（ｃ）参照）。最後の衛星節点（上記例では、節点ｂ）に到達するまで、ステップ８０３の処理が繰り返される（ステップ８０４参照）。図７（ｃ）の状態からは、辺ａｄについて節点ｃが衛星節点として設定される（図７（ｄ）参照）。図７（ｅ）は、最終節点ｂが衛星節点として設定され処理が終了した状態を示す。
【００３５】
次に、３次元の場合の衛星節点探索について説明する。内部節点では、包装法を適用するための種となる最初のデローニ三角形（ここで、三角形は２次元の三角形を意味する）が求められ、三角形の表面および裏面がリストに登録される。次いで、リストからある三角形が取り出され、その情報がリストから消去される。この三角形について、図４に示すアルゴリズムを適用してその三角形の表面に接する四面体を求める。図９において、三角形ａｂｃが基になった三角形、節点ｄが新たに求められた節点である。四面体ａｂｃｄの持つ四つの面のうち中心節点を含む面で基となった三角形以外の三角形、つまり、三角形ａｄｂおよび三角形ａｃｄがリストに登録される。このような処理が、リストが空になるまで繰り返される。
【００３６】
次に、境界節点の場合について説明する。まず、中心節点を頂点にもつ表面パッチが選択される。その表面パッチの三角形の物体内部側の面のみがリストに登録される。次いで、リストからある三角形が取り出され、その情報がリストから消去される。この三角形について、図４のアルゴリズムを適用してその三角形の表面に接する三角形が求められる。図９において、図９において、三角形ａｂｃが基になった三角形、節点ｄが新たに求められた節点である。四面体ａｂｃｄの持つ四つの面のうち中心節点を含む面で基となった三角形以外の三角形で、かつ、表面パッチでない三角形がリストに登録される。このような処理が、リストが空になるまで繰り返される。
【００３７】
［拘束デローニ（Constrained Delaunay）分割］
節点の集合をDelaunay分割したときに得られる三角形（四面体）の集合がなす領域はもとの節点の集合の凸包に一致する。しかしながら、メッシュとして要求される形状は、凸ばかりではなく凹を含む一般の任意複雑形状である。これに対応するように拘束デローニ（Constrained
Delaunay）分割が用いられる。
【００３８】
ここで、三角形から他の節点が「みえる」、「みえない」というのは以下のことを意味する。与えられたある節点Ａについて、三角形内部のいかなる節点Ｂに対しても、線分ＡＢがいずれかの表面パッチと交わるときに、その三角形から節点Ａは「見えない」と定義する。
【００３９】
ある三角形について、その外接円の内部にその三角形から見える節点が一つも存在しないならば、その三角形はＣＤＴ（拘束デローニ三角形：Constrained Delaunay Triangle）であるという。また、与えられた三角形分割について、それを構成する全ての三角形がＣＤＴであるならば、その三角形分割を拘束デローニ（Constrained
Delaunay）分割という。ＣＤＴ分割を行うための包装法のアルゴリズムについて以下に説明する。図１０に示すように、ある辺の右側に存在する節点で、その節点と辺とで形成される三角形がいずれの表面パッチと交わらないものが検索される（ステップ１００１）。このような節点と前記辺の両端の節点とを通る円の内部に対象の節点が存在すれば（ステップ１００２でイエス(Yes)）、このような存在する節点が新たな候補節点に設定される（ステップ１００３）。ステップ１００４およびステップ１００５は、図４のＤＴ分割を行うための包装法のアルゴリズムと同様である。衛星節点探索には、図６、図８に示す処理を適用することができる。
【００４０】
３次元の場合にも、「みえる」、「みえない」ということを以下のように定義することができる。ある与えられた節点Ａに対して四面体内部にある点Ｂが存在し、線分ＡＢがいかなる表面パッチとも交わらないのであれば、四面体から節点Ａは「みえる」と定義する。その一方、ある与えられた節点Ａに対して、四面体内部のいかなる点Ｂに対しても、線分ＡＢがいずれかの表面パッチと交わるとき、その四面体から節点Ａは「みえない」と定義する。
【００４１】
ある四面体について、その外接球の内部にその三角形からみえる節点が存在しないならば、その四面体はＣＤＴである。また、与えられた四面体分割について、それを構成するすべての四面体がＣＤＴであれば、その四面体分割を拘束デローニ（Constrained Delaunay）分割であるという。
【００４２】
３次元の場合に、ＣＤＴ分割を行うための包装法のアルゴリズムについて、図１１を参照して説明する。まず、ある三角形の表面空間の半空間に存在し、当該三角形の３点（頂点）とその節点とで構成される四面体が何れの表面パッチとも交わらないような節点が検索される（ステップ１１０１）。次いで、上記三角形の３点と検索された節点とを通る球の内部に、対象の節点が存在するか否かが判断される（ステップ１１０２）。ステップ１１０２でイエス(Yes)と判断された場合には、存在する節点が新たな候補節点に設定される（ステップ１１０３）。このような処理が、半空間に存在する全ての節点について実行され（ステップ１１０４参照）、最後の時点での候補節点が、半空間に存在する節点とされ、必要な情報が記憶装置に記憶される（ステップ１１０５）。
【００４３】
［ＳＣＤＴ］
本実施の形態においては、上記ＣＤＴを修正したアルゴリズムが導入される。これを、便宜上、準拘束デローニ分割（Sub−CDT: SCDT）と称する。図１２は、ＳＣＤＴ分割を行うための包装法のアルゴリズムを示すフローチャートである。図１２に示すアルゴリズムは、ステップ１２０１の一部を除き、図１１に示す処理と同様である。異なる点は、ステップ１２０１において、ある三角形の表面空間の半空間に存在し、その節点と三角形の３点とで構成される四面体が何れの表面パッチとも交わらず、かつ、それまでに作られた要素の何れとも交わらないような節点が検索される。ここで、要素とは、いままで作られた三角形（確定した四面体の面）をいう。
【００４４】
［ＤＴ、ＣＤＴおよびＳＣＤＴを利用した衛星節点探索］
図１３は、本実施の形態にかかる衛星節点探索アルゴリズムを示すフローチャートである。図１３において、ステップ１３０１は、図１のＤＴ処理部１４にて実行され、ステップ１３０３は、ＳＤＴ処理部１６にて実行される。また、ステップ１３０５およびステップ１３０６は、ＳＣＤＴ処理部１８にて実行される。節点情報は、予め記憶装置に記憶されており、処理が進められるのに従って、メッシュ情報として、生成された三角形や四面体の情報が記憶装置に記憶される。
【００４５】
まず、ＤＴ処理部１４は、記憶装置２０中のメッシュ情報からある三角形の情報と取り出し、その三角形の表面側に存在する次の四面体を求めようとする。ここでは、デローニ分割による包装法アルゴリズム（図６、図８参照）を用いて、次の節点を求め、これにより次の要素（四面体）を求める（ステップ１３０１）。
【００４６】
ここで、求められた要素がＣＤＴであるかが判断される（ステップ１３０２）。このステップは、ＤＴ処理部１４にて実行されても良いし、ＣＤＴ処理部１６にて実行されても良い。ステップ１３０２でイエス(Yes)と判断されれば、新たな要素に関する情報をメッシュ情報として記憶装置に記憶した後、次の要素を求める処理に進む。
【００４７】
その一方、ステップ１３０２でノー(No)と判断された場合には、ＣＤＴ実行部１８が、拘束デローニ分割による包装法アルゴリズム（図１１参照）を用いて次の節点を求め、これにより、次の要素を求める（ステップ１３０３）。ここでも、求められた要素がＣＤＴであるかが判断される（ステップ１３０４）。ステップ１３０４にてイエス(Yes)と判断された場合には、新たな要素に関する情報をメッシュ情報として記憶装置に記憶した後、次の要素を求める処理に進む。
【００４８】
ステップ１３０４でノー(No)と判断された場合には、ＳＣＤＴ処理部１８は、連続したＣＤＴ境界面を求め、領域を隔離する（ステップ１３０５）。次いで、ＳＣＤＴ処理部１８は、隔離された領域内について、ＳＣＤＴ分割による包装法アルゴリズム（図１３参照）を用いて、元の三角形を一面としてもつ四面体を取り出し、次の要素とする（ステップ１３０６）。取り出された要素の情報は、メッシュ情報として記憶装置に記憶される。
【００４９】
たとえば、ＣＤＴであるかどうかのチェックは、先に述べたＣＤＴの定義にしたがって、その外接円（外接球）の内部に他の節点が存在するか否かを調べればよい。なお、外接円（外接球）内部に存在する節点は、包装法を実行する際にバケットで調査しているため、それら節点をキャッシュしておくことで検索を省き、処理の高速化を実現することができる。なお、バケットについては後に簡単に説明する。
【００５０】
［連続したＣＤＴ境界面の探索］
ステップ１３０５における連続する境界面ついて以下に説明する。ここでは３次元の場合のみを対象としており、２次元では成立しない。しかしながら、理解を用意にするため、便宜上、２次元の図を利用して説明する。
【００５１】
図１４（ａ）に示すように、節点と表面パッチの集合が与えられていると考える。図中、黒丸が節点であり、破線が表面パッチである。表面パッチが特定の条件を満たすと、図１４（ｂ）に示すように、領域の内部をＣＤＴで完全に分割することができる。この表面パッチが満たすべき条件は、Edge‐protected条件と称される。このとき、ＣＤＴは与えられた節点と表面パッチに対してただ一通りしか存在しないという特徴がある。
【００５２】
しかしながら、一般の場合、すべての表面パッチが最初からEdge‐Protected条件を満たすことはない。図１４（ｃ）において、表面パッチのうち鎖線で示す部分はEdge‐Protected条件を満たさないとする。その場合、上記鎖線で示す表面パッチの周辺にＣＤＴが存在しない領域ができる。これは、図中、ハッチングで示される領域が相当する。このハッチングで示される領域の境界をＣＤＴ境界面と称する。なお、ハッチングで示される領域以外の領域にはＣＤＴが存在し、それは与えられた節点および表面パッチの集合に大して一通りしか存在しない。
【００５３】
ＳＣＤＴ処理部１８は、図１４（ｃ）においてハッチングで示される領域について、上述したＳＣＤＴ分割のアルゴリズムに基づいて要素を生成する。なお、ＣＤＴには一意性があるが、上述した隔離された領域の四面体には、このままでは一意性はない。一意性は、後述するように、分割された領域について、それぞれの処理エレメント１２が独立して要素を生成する場合に必要となる。そこで、本実施の形態においては、一意性を得るために以下のようなルールが導入されている。
【００５４】
図１５に示すように、所定の順序にしたがって境界の三角形（２次元で概略的に描いた図１４においては２次元の線分）からひとつが選ばれ（ステップ１５０１）、それに接する四面体が作られる（ステップ１５０２）。作成された四面体は、隔離された領域から取り除かれ、上記作成された四面体が除かれるように隔離された領域が更新される（ステップ１５０３）。ステップ１５０１〜１５０３の処理を繰り返すことにより、ＣＤＴおよびＳＣＤＴの全要素の一意性を得ることができる。
【００５５】
ここでステップ１５０１においては、一意性を得るために、境界を構成する三角形同士の順序付けのルールを定め、その順序に基づく最小或いは最大の三角形から要素を生成する。
【００５６】
順序付けの例として以下のようなものがある。
境界の三角形の集合を以下の４つと考える
{{０，９，７}，{９，７，２}，{２，７，０}，{０，２，９}}
ここで、数字は三角形を構成する節点番号を表す。まず、各三角形について、それを構成する３つの頂点のうち、番号が小さい頂点が先頭にくるように順序を循環させる。上記例では集合は以下のように書き換えられる。
{{０，９，７}，{２，９，７}，{０，２，７}，{０，２，９}}
次に、三角形同士は以下のように順序付ける。
【００５７】
三角形Ａ{ａ１，ａ２，ａ３}および三角形Ｂ{ｂ１，ｂ２，ｂ３}について、
ａ１＜ｂ２ならＡ＜Ｂ
ａ１＝ｂ１かつａ２＜ｂ２ならＡ＜Ｂ
ａ１＝ｂ１かつａ２＝ｂ２かつａ３＜ｂ３ならＡ＜Ｂ
ａ１＝ｂ１かつａ２＝ｂ２かつａ３＝ｂ３ならＡ＝Ｂ
上記以外の場合には、Ａ＞Ｂ
【００５８】
このような順序付けに従えば、例示した三角形の集合は以下のように並べ替えられる。
{{０，２，７}，{０，２，９}，{０，９，７}，{２，９，７}}
図１５の処理においては、このように並べ替えられた順序で三角形を選択すれば良い。
【００５９】
［バケット処理］
本実施の形態において、ＤＴ処理部１４やＣＤＴ処理部１６は、バケットを使用して節点を検索している。バケット処理においてはある辺の中点を中心にして、そのまわりの節点をらせん状に検索する。より具体的には、まず、ある辺の右側に存在する最初の節点を候補節点とする。次いで、対象節点が辺の右側に存在し、かつ、辺の両端の節点および候補節点の３点を通る円の内部に対象節点が存在すれば、その節点が新たな候補節点に設定される。バケットを用いた節点探索において、その時点での候補節点と、辺の両端の節点をとおる円内の全てを検索していれば処理を終了する。終了時点での候補節点が求める節点となる。この処理は２次元の場合も３次元の場合も同様に実現できる。
【００６０】
[並列化]
次に、複数の処理エレメント１２−１、１２−２、・・・、１２−Ｎによる並列化について説明する。本実施の形態においては、節点生成および要素（四面体）の生成を、実質的に処理エレメント間の通信なしに実現することができる。
【００６１】
本実施の形態においては、物体を覆うバウンディングボックスを、「Ｎ（＝ｉ×ｊ×ｍ）」分割して、分割された３次元領域の表面パッチのみを定義し、その情報を、各処理エレメント１２の記憶装置中に記憶しておく。各処理エレメント１２は、前記領域の境界以外の領域において、節点密度場に応じて、２次元の場合には四分木、３次元の場合には八分木を用いて節点を生成する。この処理では、ツリー構造の上位部分についてのみ、処理エレメント間で通信をなして、各処理エレメントの担当領域が決定される。その後、下位の部分については、各処理エレメントが独立して節点を生成できる。
【００６２】
また、要素の生成は、それぞれの受け持ちとなる領域について各処理エレメント１２が独立して（通信することなしに）実現可能である。先に説明したように、本実施の形態にかかる処理エレメントで実行されるＤＴ分割、ＣＤＴ分割およびＳＣＤＴ分割を行う包装法アルゴリズム、これらを利用した衛星節点探索アルゴリズム（図１３参照）により、生成される要素に一意性を担保することができる。したがって、各処理エレメントが独立して要素を生成しても境界面における不整合を防止することができる。
【００６３】
［仮想的な並列化］
本実施の形態にかかる要素の生成においては、処理エレメント間の通信が実質的に存在しないことが特徴の一つである。つまり、各処理エレメントの計算がほぼ完全に独立しているといえる。したがって、各処理エレメントの演算を、一台のコンピュータで入れ替えて実行することで仮想的な並列化を実現できる。
【００６４】
［実例］
本発明者らは本実施の形態を用いて、１億要素からなるパンテオンについて、並列処理にて要素を生成した。ここでは、パンテオンを覆うバウンティングボックスを、２６２１４４（＝６４×６４×６４）個のセルに分割した。各処理エレメントは、分割されたセルのうち、６４（４×４×４）個を受け持つこととした。したがって、全体では４０９６個の処理エレメントが独立して要素を生成した。各処理エレメントは、自己の担当の６４個のセルの内部の要素を生成するが、データとしては、縦／横／奥行きの各方向に１つずつ余分にセルの情報を有している。すなわち、各処理エレメントは、２１６（６×６×６）個分のデータを有している。
【００６５】
以下、上述した仮想並列技術により単一のＣＰＵで演算を実行した結果を示す。
モデル：パンテオン
節点数：約２１００万
要素数：約１億２０００万
時間：約４時間４０分（内部節点生成および要素生成）
ＣＰＵ：ＡｔｈｒｏｎＸＰ２１００＋  （1.73GHz）
メモリ：２ＧＢ
図１６は生成されたメッシュを示す図であり、左下の図は柱部分、右下図は天井部分をそれぞれ拡大したものである。
【００６６】
本発明は、以上の実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【図面の簡単な説明】
【００６７】
【図１】図１は、本発明の実施の形態にかかるメッシュ生成システムの概略を示すブロックダイヤグラムである。
【図２】図２は、デローニ分割を説明するための図である。
【図３】図３は、包装法を説明するための図である。
【図４】図４は、ＤＴ分割を行うための包装法アルゴリズムを示すフローチャートである。
【図５】図５は、内部節点に対する衛星節点探索を説明するための図である。
【図６】図６は、内部節点に対する衛星節点探索アルゴリズムを示すフローチャートである。
【図７】図７は、境界節点に対する衛星節点探索を説明するための図である。
【図８】図８は、境界節点に対する衛星節点探索アルゴリズムを示すフローチャートである。
【図９】図９は、３次元の衛星節点探索を説明するための図である。
【図１０】図１０は、ＣＤＴ分割を行うための包装法アルゴリズムを示すフローチャートである。
【図１１】図１１は、３次元の場合のＣＤＴ分割を行うための包装法アルゴリズムを示すフローチャートである。
【図１２】図１２は、本実施の形態にかかるＳＣＤＴ分割を行うための包装法アルゴリズムを示すフローチャートである。
【図１３】図１３は、本実施の形態にかかる処理エレメントで実行される衛星節点探索アルゴリズムを示すフローチャートである。
【図１４】図１４は、本実施の形態における連続したＣＤＴ境界面の探索を説明するための図である。
【図１５】図１５は、本実施の形態において隔離された領域の三角形の選択および四面体の生成を示すフローチャートである。
【図１６】図１６は、本実施の形態にかかるメッシュ生成システムを利用して生成されたメッシュを示す図であり、中央上側は全体図、左下の図は柱部分、右下図は天井部分をそれぞれ拡大した図である。
【符号の説明】
【００６８】
１０    メッシュ生成システム
１２    処理エレメント
１４    ＤＴ処理部
１６    ＣＤＴ処理部
１８    ＳＣＤＴ処理部
２０    記憶装置
【図１】
2005196273.tif 000003
【図２】
2005196273.tif 000004
【図３】
2005196273.tif 000005
【図４】
2005196273.tif 000006
【図５】
2005196273.tif 000007
【図６】
2005196273.tif 000008
【図７】
2005196273.tif 000009
【図８】
2005196273.tif 000010
【図９】
2005196273.tif 000011
【図１０】
2005196273.tif 000012
【図１１】
2005196273.tif 000013
【図１２】
2005196273.tif 000014
【図１３】
2005196273.tif 000015
【図１４】
2005196273.tif 000016
【図１５】
2005196273.tif 000017
【図１６】
2005196273.tif 000018