(57)【要約】【課題】連続体の表面を保護しながら、当該連続体の要素への分割を容易化し得るプログラムを提供する。【解決手段】Delaunay分割は計算幾何学に基づいた高速な三角形または四面体メッシュ分割の方法であるが、凸包を分割するための方法であるため、凹形状を含む複雑な形状の場合はその表面を破壊する要素を作成することがある。本技術では、メッシュ生成に際して、節点発生順序を表面メッシュ頂点の位置関係に基づいて規制するとともに、生成される内部メッシュを予想することで表面の破壊を回避し、全体として高品位なメッシュの生成を行なう。【選択図】  図２
2005292864.tif 000002
【特許請求の範囲】
【請求項１】
ｎ次元連続体をｎ次元要素に分割する方法であって、
ｎ次元連続体の表面形状を認識する第１処理と、
該連続体の表面上の点を節点として、Delaunay法に従ってｎ−１次元要素を決定する第２処理と、
該ｎ−１次元要素の頂点と、該連続体内部の点とを節点として、Delaunay法に従ってｎ次元要素が決定された場合、該表面の破壊又は保護の別を判定する第３処理と、
第３処理により該表面が破壊されると判定された場合、補助要素を使用して該表面が保護されるようにｎ−１次元要素を確定する第４処理と、
必要に応じて連続体の内部に節点を生成する第５処理と、
第４処理により確定されたｎ−１次元要素の頂点と、第５処理により生成された節点とに基づき、Delaunay法に従って、補助要素を使用して該連続体の表面が保護されるようなｎ次元要素を決定する第６処理とを備えていることを特徴とする連続体分割方法。
【請求項２】
第６処理によってｎ次元要素が決定された後で、
不要な要素を削除する第７処理と、
補助要素の外接球に含まれる内部節点を追加する第８処理とを備えていることを特徴とする請求項１記載の連続体分割方法。
【請求項３】
ｎ次元連続体をｎ次元要素に分割する方法であって、
連続体の表面形状から多数のｎ次元単体要素からなる解析モデルの表面をあらかじめｎ−１次元単体要素の集合として定義し、後で節点追加順序や要素組替え、要素作り替え等を指示するための補助要素を定義する表面メッシュ生成処理と、
必要に応じて該連続体又は表面メッシュから該連続体の内部の節点を定義する内部節点生成処理と、
該表面メッシュと補助要素とからｎ次元単体要素作成時における節点追加順序の規制を行ないつつｎ次元単体要素の集合を生成し、要素組替えや要素作り替えによって内部メッシュを定義する内部メッシュ生成処理とを備えていることを特徴とする連続体分割方法。
【請求項４】
Delaunay分割法によって前記ｎ−１次元単体要素の集合又は前記ｎ次元単体要素の集合を生成することを特徴とする請求項３記載の連続体分割方法。
【請求項５】
コンピュータによる演算処理の対象となる空間において、請求項１、２、３又は４記載の連続体分割方法を実行する機能を、該コンピュータに付与することを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ｎ次元連続体をｎ次元要素に分割する方法、及びコンピュータによる演算処理の対象となる空間において当該分割方法をを実行する機能をコンピュータに付与するプログラムに関する。
【背景技術】
【０００２】
有限要素法や有限体積法によれば、所定形状の連続体が有限の微小な要素に分割・離散化された上で、当該連続体に関する様々な力学的問題が解析されている。
【０００３】
連続体が２次元の場合は三角形又は四角形が分割要素として採用される。また、連続体が３次元の場合は四面体、五面体（プリズム、ピラミッド）又は六面体等が分割要素として採用される。
【０００４】
３次元連続体を四面体要素に分割する方法として「Advancing Front法」や「Delaunay（デローニ）法」が提案されている（例えば、非特許文献１参照）。しかし、Advancing Front法によれば、近傍節点の探索に多大な計算コストを要し、最終段階で要素のねじれが残る可能性がある。また、フロント要素生成にDelaunay分割の性質を利用したGift Wrapping法によれば（例えば、非特許文献２参照）、最後に要素のねじれが残る心配はないが、近傍節点の探索に計算コストが掛かることでは同じである。
【０００５】
Delaunay 分割は、ｎ次元空間において与えられた点列を頂点とする単体（２次元の場合は三角形、３次元の場合は四面体）に分割するものであり、単体（要素）を構成する点の外接球内に他の点を含まない（外接球上は許す）という性質を持つ。Delaunay分割を実現するには、先に挙げたGift Wrapping法でもよいが、逐次添加法（例えば、非特許文献３参照）が最も高速であり、通例Delaunay法と云えば逐次添加法によるDelaunay分割を指す。ここでもDelaunay法をそのような意味で使用する。
【０００６】
逐次添加法は次の手順（ａ）〜（ｄ）に従って実施される。ここでは３次元連続体について説明するが、２次元連続体については、四面体を三角形、多面体を多角形、三角形をエッジ（辺）、表面を境界と読替える。また、４次元以上のｎ次元空間においても、ｎ−１次元要素を「表面」と考えることによって拡張可能である。
（ａ）形状全体を包含する大きな四面体又は予めDelaunay分割された多面体（普通は直方体を５つの四面体に分割）を用意する。これをSuper Tetrahedronと呼ぶ。
（ｂ）与えられた点列から１点を選択しSuper Tetrahedronに追加する。その際、その点を外接球に含む要素を全て集めると１つの多面体となるので、その表面だけを残して要素を削除し、新たに加えた点と多面体の表面三角形とを結んで四面体を作成する。これはDelaunay分割になっている。
（ｃ）（ｂ）を全ての点について繰返す。
（ｄ）最初にSuper Tetrahedronを構成するのに使用した点とそれを含む要素、及び形状外部にできた要素を削除する。
【０００７】
以上により、連続体がDelaunay分割される。ただし、要素が連続体内部にあるか否かを判断するために形状を規定する方法と、追加する点列を予め用意しておく必要がある。形状を規定するには、ＣＡＤのサーフェスをそのまま使う方法や、閉じた空間の表面を三角形の集合で表現した三角形表面パッチを使う方法等がある。追加する点列は、八分木法（例えば、非特許文献１参照）やバケット法（例えば、非特許文献４参照）などで生成できる。三角形表面パッチを構成する点を表面節点とし、八分木法やバケット法などで内部の節点を生成する方法もある。
【０００８】
凸包で、三角形表面パッチを構成する点を表面節点とし三角形がDelaunay分割になっている場合は、三角形表面パッチとDelaunay法で生成される四面体メッシュの表面とは一致する。また、凹形状を含む場合でも、表面三角形がDelaunay分割になっており、適切な節点配置になっていれば生成されるメッシュの表面と一致する。ここではこれを表面メッシュと呼ぶ。ただし、メッシュ表面に現れる三角形の（３次元）外接円上に４点以上の表面節点がある場合（ここでは表面degeneracyと呼ぶ）には、その分割結果に任意性が残る（２次元の場合には、表面に相当するのはエッジ（辺）となるため、表面degeneracyはない）。また、Delaunay分割ではなくても、結果として四面体メッシュの表面と表面パッチが一致するなら、これを表面メッシュと呼ぶ。ここでは、表面degeneracyの任意性を含めて表面メッシュと呼ぶこととする。
【０００９】
なお、普通にdegeneracyという場合は、３次元では、同一球面上に５点以上の点があり、且つ、球の内部に他の点を含まない場合に、その四面体分割の組合せに任意性があることを云う。２次元では、同一円周上に４点以上あり、且つ、円内に他の点を含まない場合の三角形分割の任意性を指す。２次元におけるdegeneracyについて図１４を用いて説明する。
【００１０】
また、連続体内部においても、材料が異なる等の理由によって境界面が必要なこともあるが、ここでは「表面」には、連続体内部の境界面も含まれる。
【００１１】
Delaunay法は計算幾何学に基づいた高速な三角形又は四面体メッシュ分割の方法であるが、凸包を分割するための方法であるため、凹形状を含む複雑な形状の場合はその表面を破壊する要素を作成することがある。Delaunay分割は、四面体（２次元の場合は三角形）を構成する４点の外接球内に他の点を含まないという性質のため、点の配置によっては、表面三角形と形状内部側の近傍点とでできる四面体の外接球内に外側の点を含み、表面三角形が存在できない場合もあるためである。
【００１２】
所定形状の連続体をDelaunay法によってメッシュに分割する場合に連続体の表面を保護する方法として、(A)Conforming Delaunay 法 (a priori な方法)（例えば、非特許文献５参照）及び(B) Constrained Delaunay 法 (a posteriori な方法)（例えば、非特許文献６参照）が提案されている。
【００１３】
方法(A)によれば、内部のメッシュ分割をする前に表面（２次元の場合は境界エッジ）が壊れる可能性のある節点配置を探し、適切な位置に節点を追加することによって表面が壊れない様な表面メッシュを作成してから内部を分割する。
【００１４】
方法(B)によれば、Delaunay 法によってメッシュ分割したあと、形状外部の要素を取り除く前に要素の組替え（swapping）を行なって表面を復元する。
【００１５】
方法(A)は、先に説明した逐次添加法による要素生成の前処理として、生成された四面体メッシュの表面がそのまま表面メッシュに一致する様にする方法である。また、方法(B)は、逐次添加法による要素生成の後処理として、生成された四面体メッシュの表面を表面メッシュに強制的に一致させる方法である。どちらもフランスのINRIA研究所で提唱された方法であり、方法(B)でINRIAが開発したプログラム(GHS3D,URL:http://www.inria.fr/recherche/equipes/gamma.en.html）がメッシュカーネルとして多くのプロダクトで採用されている。日本でも、方法(A)に分類される方法によって独自に開発されたADVENTURE TetMeshがフリーソフトとして公開されている(URL: http://adventure.q.t.u-tokyo.ac.jp/)。なお、基本的には方法(B)に従って、要素の組替えが特に難しい凹形状の角部分のみ方法(A)で節点追加した後、逐次添加法による要素生成を行ない、方法(B)で表面を復元する方法も提案されている（例えば、非特許文献７参照）。
【非特許文献１】Joe F. Thompson, Bharat K. Soni and Nigel P. Weatherill ed., “Handbook of Grid Generation”, CRC Press, (1999).
【非特許文献２】M. Tanemura, T. Ogawa and N. Ogita, “A new Algorithm for three-dimensional Voronoi tessellation”, J. of Computational Physics 51, 19１１２7, (1983).
【非特許文献３】D. F. Watson, “Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes”, The Computer Journal, 24-2, 167-172, (1981).
【非特許文献４】Yagawa, G., Yoshimura, S. and Nakao, K., “Automatic Mesh Generation of Complex Geometries Based on Fuzzy Knowledge Processing and Computational Geometry”, Integrated Computer-Aided Engineering 2, 265-282, (1995).
【非特許文献５】P. P. Pebay and P. J. Frey, “A priori Delaunay-conformity”, 7th Annual International Meshing Roundtable, (1998).
【非特許文献６】P.L. George, F. Hecht and E. Saltel, “Automatic mesh generator with specified boundary”, Computer Methods in Applied Mechanics and Engineering 92, 269-288, (1991).
【非特許文献７】J. R. Shewchuk, “Constrained Delaunay Tetrahedralizations and Provably Good Boundary Recovery”, 11th Annual International Meshing Roundtable, (2002).
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかし、方法(A)及び方法(B)によれば、２次元連続体はごく簡単な操作で分割されるものの、３次元連続体の場合は分割のための処理が複雑になる。すなわち、方法(A)によれば、適切な位置に節点を追加することで収束することが示されているが、追加する点の位置の決定が難しく、多数の点の追加により極端に小さな要素ができる場合がある。また、方法(B)によれば、逐次添加法によってできた四面体メッシュの表面と表面メッシュの全ての三角形要素について、一致しているか否かの比較を行わなければならず、また、３次元での要素の組替えが難しく、複雑形状では要素の組替えに失敗することもあり、要素組替え後は一般にDelaunay 分割ではなくなる。そのため、この方法を適用した後は Delaunay 法は使えなくなる。また、要素組替え後は極端にいびつな要素ができることがある。要素組替え後もDelaunay分割の性質を保持する方法も提案されているが（非特許文献７参照）、要素の組替えが難しいことには変わりがない。
【００１７】
そこで、本発明は、連続体の表面を保護しながら、当該連続体の要素への分割を容易化し得る方法及びプログラムを提供することを解決課題とする。
【課題を解決するための手段】
【００１８】
方法(A)は表面メッシュだけ、方法(B)は内部メッシュだけで表面の破壊を解決しようとするものであるが、本発明は、方法(A)及び方法(B)の組合せであり、表面メッシュと内部メッシュとの連携により、連続体の表面を保護するものである。なお、表面メッシュに対して、逐次添加法により生成された四面体メッシュをここでは「内部メッシュ」という。
【００１９】
表面メッシュ作成時にあらかじめ破壊される面を予想しておき、内部メッシュ作成後に当該要素のみを組替えて形状表面を復元する。表面メッシュ作成の際、簡単な要素組替えで済むならば表面の破壊を許すことにすれば、表面節点の配置だけで表面を保護する方法(A)の様に極端に小さな要素ができるのを回避することができる。図１３に、図１０の表面メッシュから、方法(A)に従って連続体の表面を保護しながら四面体分割した場合のメッシュを示すが、連続体のスリット部分に極端に小さい要素が構成されていることがわかる。
【００２０】
また、方法(B)の様に複雑すぎて要素の組替えに失敗することもなくなる。更に、要素の組替えを１回だけで済ますことで局所的な Delaunay 分割を保証できるため、表面を確定した後に更に内部節点を追加する場合でも、そのままDelaunay 法を続行できる。
【００２１】
方法(A)では、表面メッシュの節点配置を調べて、Delaunay法による四面体メッシュ生成後に表面三角形要素が形成されないと判断した場合は、適切な位置に新たに表面節点を追加する。新たな節点を追加する位置は状況によって異なる。また、表面三角形要素の外接球内に内部節点を生成しないという前提条件がある。ここで、表面三角形要素の外接球とは、要素を構成する３点の外接球のうち、当該３点で定義される平面（以下「定義平面」という。）上に中心があるものを指す。定義平面上での３点の外接円が外接球の大円となり、定義平面によって二等分される。Delaunay法による四面体メッシュ生成後に表面三角形要素が形成されない場合とは、例えば、上記表面三角形要素の外接球を定義平面によって二等分した半球のうち、形状外側の半球内に他の表面節点が存在する場合（この場合は可能性だけであるが、方法(A)では内部節点の位置を知り得ないため、可能性を排除できない）や、形状内側の半球内に他の表面節点が存在し、且つ、当該節点を含めた４点で構成される四面体の外接球内に他の表面節点が存在する場合等である。
【００２２】
本発明では、補助要素が採用されることにより、表面メッシュ生成時に把握された状況が、内部メッシュ生成時に反映されて、新たな表面節点の追加が抑制される。
【００２３】
例えば、連続体外の半球内に他の表面節点が存在し、且つ当該４点で構成される四面体の外接球内に他の表面節点が存在しない場合、当該４点で構成される四面体の外接球に含まれる内部節点については、逐次添加法による要素生成時での点の追加を抑制し、外部の不要な要素を削除して形状表面が確定した後に追加することで表面三角形を守ることができる。
【００２４】
また、方法(A)での表面三角形要素の外接球内に内部節点を生成しないという前提条件も必要ない。ただし、要素の形はなるべく正四面体に近い方が解析には有利であり、いびつな要素ができるのを回避するためにはこの条件がある方がよい。以下ではこの条件を前提とした場合について説明する。
【００２５】
前記課題を解決するための本発明の第１態様の連続体分割方法は、ｎ次元連続体の表面形状を認識する第１処理と、該連続体の表面上の点を節点として、Delaunay法に従ってｎ−１次元要素を決定する第２処理と、該ｎ−１次元要素の頂点と、該連続体内部の点とを節点として、Delaunay法に従ってｎ次元要素が決定された場合、該表面の破壊又は保護の別を判定する第３処理と、第３処理により該表面が破壊されると判定された場合、補助要素を使用して該表面が保護されるようにｎ−１次元要素を確定する第４処理と、必要に応じて連続体の内部に節点を生成する第５処理と、第４処理により確定されたｎ−１次元要素の頂点と、第５処理により生成された節点とに基づき、Delaunay法に従って、補助要素を使用して該連続体の表面が保護されるようなｎ次元要素を決定する第６処理とを備えていることを特徴とする。
【００２６】
また、本発明の第１態様の連続体分割方法は、第６処理によってｎ次元要素が決定された後で、不要な要素を削除する第７処理と、補助要素の外接球に含まれる内部節点を追加する第８処理とを備えていることを特徴とする。
【００２７】
前記課題を解決するための本発明の第２態様の連続体分割方法は、連続体の表面形状から多数のｎ次元単体要素からなる解析モデルの表面をあらかじめｎ−１次元単体要素の集合として定義し、後で節点追加順序や要素組替え、要素作り替え等を指示するための補助要素を定義する表面メッシュ生成処理と、必要に応じて該連続体又は表面メッシュから計算領域内部の節点を定義する内部節点生成処理と、該表面メッシュと補助要素とからｎ次元単体要素作成時における節点追加順序の規制を行ないつつｎ次元単体要素の集合を生成し、要素組替えや要素作り替えによって内部メッシュを定義する内部メッシュ生成処理とを備えていることを特徴とする。
【００２８】
また、本発明の第２態様の連続体分割方法は、Delaunay分割法によって前記ｎ−１次元単体要素の集合又は前記ｎ次元単体要素の集合を生成することを特徴とする。
【００２９】
前記課題を解決するための本発明の連続体分割プログラムは、コンピュータによる演算処理の対象となる空間において、第１態様又は第２態様の連続体分割方法を実行する機能を、該コンピュータに付与することを特徴とする。
【００３０】
本発明の連続体分割方法及び連続体分割プログラムによれば、補助要素を導入することにより、表面メッシュ生成時に把握した状況を内部メッシュ生成時に活用して節点の追加順序を規制するとともに、簡単な要素の組替え及び作り替えを組み合わせることによって、Delaunay法に伴なう表面要素の破壊を回避することが可能となる。従って、不必要な節点の増加を抑制することが可能となり、いびつな要素の生成も抑制できる。これにより、メッシュ生成のロバスト性が向上するとともに、全体として高品位なメッシュの生成を行なうことができる。そして、連続体の表面を保護しながら、当該連続体の要素への分割を容易化し得る。
【００３１】
なお、当該連続体分割方法は、要素決定時に条件が付されることから「Conditioning Delaunay法」と呼ばれるべきものである。
【発明を実施するための最良の形態】
【００３２】
本発明の連続体分割方法及び連続体分割プログラムの実施形態について図面を用いて説明する。
【００３３】
図１は本発明の一実施形態における連続体分割プログラムが格納されたコンピュータの構成説明図である。
【００３４】
図２は連続体分割方法の説明図である。
【００３５】
図３は補助要素SPVertexとSPTriangleの２次元模式による説明図である。
【００３６】
図４は補助要素SPTetrahedronの２次元模式による説明図である。
【００３７】
図５は補助要素SPPentahedronにおける要素の組替えの説明図である。
【００３８】
図６は補助要素SPHexahedron2とSPHexahedron3における要素の組替えの説明図である。
【００３９】
図７は補助要素SPOctahedronにおける要素の組み替えの説明図である。
【００４０】
図８は補助要素SDTriangleにおける要素の作り替えの２次元模式による説明図である。
【００４１】
図９は表面パッチの一例の説明図である。
【００４２】
図１０は表面パッチから生成された表面メッシュの一例の説明図である。
【００４３】
図１１は図１０の表面メッシュから、表面保護を行なわずにDelaunay法で四面体分割した場合のメッシュの説明図である。
【００４４】
図１２は図１０の表面メッシュから、本発明による表面保護を行なって四面体分割した場合のメッシュの説明図である。
【００４５】
図１３は図１０の表面メッシュから、Conforming Delaunay法による表面保護を行なって四面体分割した場合のメッシュの説明図である。
【００４６】
図１４は２次元におけるdegeneracyの説明図である。
【００４７】
まず、本発明の一実施形態における連続体分割プログラムが格納（インストール）されたコンピュータ１００の構成について図１を用いて説明する。
【００４８】
図１に示すコンピュータ１００は、キーボードやマウス等の入力装置１０２と、プログラムやデータが格納される補助記憶装置１０４と、ディスプレイ等の出力装置１０６とを備えている。
【００４９】
また、コンピュータ１００は、第１処理ユニット１１１と、第２処理ユニット１１２と、第３処理ユニット１１３と、第４処理ユニット１１４と、第５処理ユニット１１５と、第６処理ユニット１１６と、第７処理ユニット１１７と、第８処理ユニット１１８と、表示処理ユニット１２０とを備えている。各ユニットは、ハードウェア的にはＣＰＵ、ＲＯＭ、ＲＡＭ、その他種々の電子回路により構成されている。
【００５０】
第１処理ユニット１１１は、連続体の形状を認識する。第２処理ユニット１１２は、表面メッシュを連続体に生成する。第３処理ユニット１１３は、表面メッシュの節点を基礎として、Delaunay法に従ってメッシュ分割された場合の連続体の表面保護又は破壊の別を判定する。第４処理ユニット１１４は、後述する補助要素を使用して表面メッシュ、ひいては表面節点を確定する。第５処理ユニット１１５は、確定した表面節点を基礎として内部節点を生成する。第６処理ユニット１１６は、補助要素を使用して連続体を四面体要素に分割する。第７処理ユニット１１７は不要な要素を削除する。第８処理ユニット１１８は、所定の内部節点を追加する。表示ユニット１２０は、連続体分割の途中経過及び結果を出力装置１０６に出力する。
【００５１】
次に、連続体分割プログラムによってコンピュータ１００に付与された機能により実施される連続体の分割方法について図２〜図１３を用いて説明する。
【００５２】
はじめに、当該分割方法で使用される補助要素について図３〜図８を用いて説明する。補助要素は、それ自体がメッシュに組み込まれるのではなく、要素を作るための指示を与えるためのものであって、要素を作るための補助をするものである。補助要素の名称において「SP」及び「SD」はそれぞれ「Surface Protection」及び「Surface Destruction」の意である。
【００５３】
補助要素(1)SPVertex及び補助要素(2) SPTriangle について図３（２次元模式図）を用いて説明する。
【００５４】
補助要素(1)は、表面節点が他の表面三角形を破壊する位置にあり、且つ、当該表面節点の周囲の表面三角形が特に修復処理をしなくても自然に形成されるか、他の方法で修復可能な場合、逐次添加法による要素生成時における表面節点の追加を抑制し、相手の表面三角形が確定してから表面節点を追加することを指示するものである。
【００５５】
補助要素(2)は、他の表面節点によって破壊される位置関係にあるが、当該節点をSPVertexとして追加を抑制することにより表面三角形を形成可能な場合、表面三角形を先に確定することを指示するものである。
【００５６】
補助要素(3) SPTetrahedronについて図４（２次元模式図）を用いて説明する。
【００５７】
補助要素(3)は、表面三角形の外接球のうち、形状外側の半球内に他の表面節点が存在し、且つ、当該４点で構成される四面体の外接球に他の表面節点が含まれない場合、四面体の外接球に含まれる内部節点については、逐次添加法による要素生成時での内部節点の追加を抑制し、外部の不要な要素を削除して形状表面が確定した後に内部節点を追加することを指示するものである。
【００５８】
補助要素(4) SPPentahedronについて図５を用いて説明する。
【００５９】
補助要素(4)は、表面三角形を構成する３点で定義される平面上で、３点の外接円上にもう１点別の表面節点が存在するdegeneracyの状態であり、且つ、更に別の近傍表面節点で構成される２つの四面体の外接球内に他の表面節点が存在しない場合、逐次添加法による要素生成後、要素の表面と表面三角形が違っている場合は２つの四面体要素を組替えることを指示するものである。
【００６０】
補助要素(5) SPHexahedron2及び補助要素(6) SPHexahedron3について図６を用いて説明する。補助要素(5)及び補助要素(6)は相対関係にある。
【００６１】
補助要素(5)は、四角形ではなく三角形６面により構成される。
【００６２】
表面三角形の外接球のうち、一方の半球内に他の表面節点が存在し、且つ、当該４点で構成される四面体の外接球の当該三角形から見て反対側に他の表面節点が含まれて３つの四面体になる場合、更に、それら３つの四面体の外接球に他の表面節点が含まれない場合、逐次添加法による要素生成後、３つの四面体を２つの四面体要素に組み替えることを指示するものである。
【００６３】
補助要素(6)は、四角形ではなく三角形６面により構成される。
【００６４】
表面エッジ（表面三角形の辺）の両側の三角形が同一平面上にない場合、それらの２つの表面三角形を構成する４点で構成される四面体の外接球内に他の表面節点が存在し、且つ、２つの表面三角形の鈍角側にあって、先の４点との組合せの結果として２つの四面体になる場合、更に、それら２つの四面体の外接球に他の表面節点が含まれない場合、逐次添加法による要素生成後、２つの四面体を３つの四面体要素に組み替えることを指示するものである。
【００６５】
補助要素(7) SPOctahedronについて図７を用いて説明する。
【００６６】
補助要素(7)は、表面三角形の外接球のうち、一方の半球内に他の表面節点が存在し、且つ、当該４点で構成される四面体の外接球の当該三角形から見て反対側に他の表面節点が含まれて３つの四面体になる場合、更に、それら３つの四面体のうち１つの四面体の外接球に当該表面三角形に隣接する表面三角形の当該表面三角形と共有しない表面節点を含むことにより合計４つの四面体になり、それら４つの四面体の外接球に他の表面節点が含まれない場合、逐次添加法による要素生成後、４つの四面体要素に組替えることを指示するものである。補助要素(7)は補助要素(5)の特殊なものである。
【００６７】
補助要素(8) SDTriangleについて図８を用いて説明する。
【００６８】
補助要素(8)は補助要素(1)〜(7)によっても表面三角形が守れない場合、当該三角形をまたぐ要素を全て削除すると、空洞となった多面体は当該三角形によって２つの空間に分割されるので、それぞれの空間に対してGift Wrapping法により新たに要素を生成することを指示するものである。
【００６９】
なお、補助要素(1)〜(8)のうち、補助要素(4)〜(7)は３次元に特有のものであるが、補助要素(1)〜(3),(8)は４次元以上の単体（連続体）にも適用され得る。
【００７０】
続いて、連続体が分割される際の一連の処理について図２のフローチャートに従って説明する。
【００７１】
まず、第１処理ユニット１１１が「第１処理」を実行する（ｓ１０）。具体的には、図９に示されているような表面パッチ（連続体の表面を三角形の集合で表現したもの）等、連続体の形状を特定するデータがコンピュータ１００に入力されることで、第１処理ユニット１１１が連続体の形状を認識する。図９に示されている連続体は、スリット（切り込み）が設けられた直方体であり、このスリットにより直方体が部分的に半分割され、略Ｕ字形状の断面を有する。
【００７２】
また、第２処理ユニット１１２が「第２処理」を実行する（ｓ２０）。具体的には、第２処理ユニット１１２が、Delaunay分割された三角形要素により、図１０に示されているような表面メッシュを連続体に生成する。例えば、連続体の表面上に複数の節点を配置し、Delaunay法に従って節点を頂点とする三角形要素を構成することで、表面メッシュが生成される。また、図１０に示されているような表面パッチや、表面パッチにおいて三角形がスムージングその他の方法で適当に配置替えされたものがDelaunay分割化されることで表面メッシュが生成されてもよい。
【００７３】
さらに、第３処理ユニット１１３が「第３処理」を実行する（ｓ３０）。具体的には、第３処理ユニット１１３が、第２処理ユニット１１２により構成された表面メッシュの節点を基礎として、Delaunay法に従って四面体要素によってメッシュ分割された場合、節点配置が各エッジ（三角形要素の辺）及び各三角形を破壊するものであるか否かを判定する。すなわち、表面メッシュの節点を基礎として、Delaunay法に従ってメッシュ分割された場合、図に示されているように連続体の表面が破壊されるか否かが判定される。図９に示されている連続体におけるスリット部分のように、連続体の表面が対向して近接する等、複雑な形状部分において連続体の表面が破壊される可能性が高い。
【００７４】
第３処理ユニット１１３が節点配置が各エッジ及び各三角形を破壊するものであると判定した場合、第４処理ユニット１１４が「第４処理」を実行する（ｓ４０）。具体的には、第４処理ユニット１１４が補助要素(1)〜(8)のうち、一又は複数を組み合わせて使用する（但し、補助要素(1)及び(2)は組で使用される必要がある）ことで、破壊された連続体の表面が修復されるような表面メッシュを確定する。表面保護のために第４処理ユニット１１４によって使用される補助要素は、入力装置１０２の操作を通じてユーザにより設定（選択）され得る。
【００７５】
補助要素(1)〜(3)は要素の組替えや作り直しの必要がないので特に効率的な補助要素である。また、補助要素(8)は局所に限られるので、近傍節点の探索に掛かる計算コストは問題にはならない。補助要素(8)は補助要素(1)〜(7)の代わりに使用されてもよい。補助要素(1)〜(7)によっても破壊された表面が修復されない場合、補助要素(8)が使用される。一方、補助要素(8)が使用されないことがユーザによって設定された場合は適切な位置に表面節点が追加される。 
【００７６】
新たな表面節点が追加された場合、新しい節点配置を対象として、新たな表面節点を追加しなくても表面が保護されるまで、補助要素(8)を使用しない場合の表面節点の追加処理が繰り返される。これにより、例えば、図１２に示されているように連続体の表面が保護されるように表面メッシュが確定する。補助要素(8)が使用される場合、当該繰返しは省略され得る。
【００７７】
続いて、第５処理ユニット１１５が「第５処理」を実行する（ｓ５０）。具体的には、第５処理ユニット１１５が、確定した表面メッシュ、ひいては表面節点を基礎として内部節点を生成する。この際、内部節点は、表面三角形の外接球内には生成されないようにされる。
【００７８】
また、第６処理ユニット１１６が「第６処理」を実行する（ｓ６０）。具体的には、まず、第６処理ユニット１１６が連続体を余裕をもって包含する「Super Tetrahedron」を生成する（ｓ６１）。
【００７９】
続いて、第６処理ユニット１１６が表面節点と内部節点をSuper Tetrahedron内に順次追加して、逐次添加法による四面体分割を行なう（ｓ６２）。このとき、補助要素(1)により特定される表面節点と、補助要素(3)〜(7)の外接球に含まれる内部節点とは追加されない。
【００８０】
さらに、第６処理ユニット１１６が補助要素(2)により特定される三角形を確定する（ｓ６３）。また、第６処理ユニット１１６が補助要素(1)により特定される表面節点を追加する（ｓ６４）。そして、第６処理ユニット１１６が補助要素(4)〜(7)を組み替える（ｓ６５）。
【００８１】
そして、第６処理ユニット１１６が補助要素(8)で指定された三角形をまたぐ要素を全て削除し、当該三角形で空間を二分したあとGift Wrapping法により空洞となった空間に要素を再び生成する（ｓ６６）。なお、この処理は、補助要素(8)同士が隣接している場合はそれらをまとめて実行される。但し、それらが共有するエッジ（辺）が守られている場合は同時に実行される必要はない。
【００８２】
さらに、第７処理ユニット１１７が「第７処理」を実行する（ｓ７０）。具体的には、第７処理ユニット１１７がSuper Tetrahedronを構成するのに使用した点とそれを含む要素、及び形状外部にできた要素を削除する。
【００８３】
そして、第８処理ユニット１１８が「第８処理を実行する（ｓ８０）。具体的には、第８処理ユニット１１８が補助要素(3)〜(7)の外接球に含まれる内部節点を追加する。
【００８４】
なお、表面三角形要素の外接球内に内部節点を生成しないという前提条件を設けない場合、第５処理における「表面三角形の外接球内には内部節点が生成されない」という処理が不要となり、代わりに第６処理における「表面三角形要素の外接球内に含まれる内部節点を追加しない」という処理及び第８処理における「表面三角形要素の外接球内に含まれる内部節点を追加する」という処理が追加される。
【００８５】
また、第５処理（内部節点の生成）は、第１処理以前に実行されてもよく、第７処理以後に実行されてもよい。さらに、表面節点によってのみ連続体が要素に分割されることがユーザにより設定された場合、第５処理が省略され、内部節点が使用されないで連続体が分割されてもよい。
【００８６】
本発明の連続体分割プログラムによれば、表面メッシュ生成時に決定された条件によって、内部メッシュ生成時の逐次添加法における節点の追加順序が規制されるとともに、簡単な要素の組替え及び作り替えが組み合わせられることによって、Delaunay法に伴なう表面要素の破壊が回避され得る。また、表面degeneracyについても、要素の組替え又は作り替えによってその任意性が排除され得るので、内部メッシュの表面と表面メッシュとを完全に一致させることができる。
【図面の簡単な説明】
【００８７】
【図１】本発明の一実施形態における連続体分割プログラムが格納されたコンピュータの構成説明図
【図２】連続体分割方法の説明図
【図３】補助要素SPVertexとSPTriangleの２次元模式による説明図
【図４】補助要素SPTetrahedronの２次元模式による説明図
【図５】補助要素SPPentahedronにおける要素の組替えの説明図
【図６】補助要素SPHexahedron2とSPHexahedron3における要素の組替えの説明図
【図７】補助要素SPOctahedronにおける要素の組み替えの説明図
【図８】補助要素SDTriangleにおける要素の作り替えの２次元模式による説明図
【図９】表面パッチの一例の説明図
【図１０】表面パッチから生成された表面メッシュの一例の説明図
【図１１】図１０の表面メッシュから、表面保護を行なわずにDelaunay法で四面体分割した場合のメッシュの説明図
【図１２】図１０の表面メッシュから、本発明による表面保護を行なって四面体分割した場合のメッシュの説明図
【図１３】図１０の表面メッシュから、Conforming Delaunay法による表面保護を行なって四面体分割した場合のメッシュの説明図
【図１４】２次元におけるdegeneracyの説明図
【符号の説明】
【００８８】
１００・・コンピュータ、１０２・・入力装置、１０４・・補助記憶装置、１０６・・出力装置、１１１・・第１処理ユニット、１１２・・第２処理ユニット、１１３・・第３処理ユニット、１１４・・第４処理ユニット、１１５・・第５処理ユニット、１１６・・第６処理ユニット、１１７・・第７処理ユニット、１１８・・第８処理ユニット、１２０・・表示処理ユニット
【図１】
2005292864.tif 000003
【図２】
2005292864.tif 000004
【図３】
2005292864.tif 000005
【図４】
2005292864.tif 000006
【図５】
2005292864.tif 000007
【図６】
2005292864.tif 000008
【図７】
2005292864.tif 000009
【図８】
2005292864.tif 000010
【図９】
2005292864.tif 000011
【図１０】
2005292864.tif 000012
【図１１】
2005292864.tif 000013
【図１２】
2005292864.tif 000014
【図１３】
2005292864.tif 000015
【図１４】
2005292864.tif 000016