(57)【要約】【課題】  非正規型六面体メッシュを生成する。【解決手段】  立体表面を被覆する、偶数個の４辺形要素から構成される４辺形メッシュの双対輪体を境界として内部曲面の配置を立体内部に生成し、当該配置中に現れる３個の内部曲面の交点を６面体要素に変換することによって、６面体メッシュを生成する内部曲面直接配置法において、双対輪体を自己交差点で切断分離した、自己交差を生じさせない部分双対輪体である回路Ａと、回路Ａに基点Ｐで接続する回路Ｂ又は基点Ｐを含む回路の部分回路Ｂと、回路Ａに基点Ｑで隣接する回路Ｃ又は基点Ｑを含む回路の部分回路Ｃからなる三つ組み回路Ｔ＝｛Ａ，Ｂ，Ｃ｝の、基点Ｐ及び基点Ｑにおける自己交差点の型の同一性を参照して単純内部曲面を生成し、単純内部曲面を含む内部曲面を形成することによって非正規型六面体メッシュを生成する。【選択図】図１３
2006201857.tif 000002
【特許請求の範囲】
【請求項１】
立体に対して六面体メッシュを生成する方法であって、
立体表面を被覆し且つ偶数個の四辺形要素から構成される四辺形メッシュ中における、偶数個の自己交差点を有する双対輪体又は奇数個の自己交差点を有する双対輪体を連結して偶数個の自己交差点を有するように変換した双対輪体のデータを、双対輪体データ格納部に格納するステップと、
前記双対輪体データ格納部を参照して、前記双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第１の回路と、前記第１の回路が第１及び第２の基点でそれぞれ接続し且つ前記双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第２及び第３の回路とからなる三つ組み回路を特定し、三つ組み回路データ格納部に格納する三つ組み回路生成ステップと、
前記三つ組み回路データ格納部を参照して、前記三つ組み回路の第１の基点及び第２の基点における自己交差点の型の同一性を判断する同一性判断ステップと、
前記自己交差点の型の同一性の判断結果に応じて前記三つ組み回路に対応して単純内部曲面を生成し、単純内部曲面を含む内部曲面を形成して、当該内部曲面に関するデータを内部曲面データ格納部に格納するステップと、
前記内部曲面データ格納部に格納されたデータを用いて前記立体内部に前記内部曲面の配置を生成し、前記内部曲面の配置において生ずる３つの内部曲面の交点を六面体要素に変換することにより六面体メッシュを生成し、当該六面体メッシュのデータを六面体メッシュデータ格納部に格納する六面体メッシュ生成ステップと、
を含み、コンピュータにより実行される六面体メッシュ生成方法。
【請求項２】
前記第２及び第３の回路が隣接していることを特徴とする請求項１記載の六面体メッシュ生成方法。
【請求項３】
前記三つ組み回路生成ステップが、
前記三つ組み回路を構成する回路についての双対輪体のデータを前記双対輪体データ格納部から除去するステップ
を含む請求項１記載の六面体メッシュ生成方法。
【請求項４】
前記同一性判断ステップにおいて、
前記三つ組み回路における第１の基点及び第２の基点を周回する領域中の点に対する、前記三つ組み回路が作る有向曲線に関する位数の組又は自己交差点に対する向き付けされた回路の包含性を判断することを特徴とする請求項１乃至３のいずれか１つ記載の六面体メッシュ生成方法。
【請求項５】
前記同一性判断ステップにおいて、
前記三つ組み回路を平面投影して自己交差点の型の同一性を判断する
ことを特徴とする請求項１乃至４のいずれか１つ記載の六面体メッシュ生成方法。
【請求項６】
前記同一性判断ステップにおいて、前記三つ組み回路を構成する第１の回路及び第３の回路又は第２の部分回路のうち少なくとも一つが、唯一の他の回路と接続する場合、二つの自己交差点の型が同一であると判断されると、前記六面体メッシュ生成ステップにおいて、前記三つ組み回路に対応する単純内部曲面として向き付け可能な曲面を生成し、
前記同一性判断ステップにおいて、前記三つ組み回路を構成する第１の回路及び第３の回路又は第２の部分回路のうち少なくとも一つが、唯一の他の回路と接続する場合、二つの自己交差点の型が相異すると判断されると、前記六面体メッシュ生成ステップにおいて、前記三つ組み回路に対応する単純内部曲面として向き付け不能な曲面を生成する
ことを特徴とする請求項１乃至５のいずれか１つ記載の六面体メッシュ生成方法。
【請求項７】
前記六面体メッシュ生成ステップが、
前記同一性判断ステップにおいて、前記三つ組み回路を構成する第１の回路及び第３の回路又は第２の部分回路に唯一の他の回路と接続する回路が存在しない場合、二つの自己交差点の型が同一であると判断されると、前記三つ組み回路を一つの回路としてみなし、前記第１の回路及び前記第３の回路又は前記第２の部分回路に接続する前記第２の回路又は前記第１の部分回路以外の２つの回路と組み合わせた新たな三つ組み回路に対応する内部曲面を生成するステップ
を含む請求項１乃至６のいずれか１つ記載の六面体メッシュ生成方法。
【請求項８】
立体に対して六面体メッシュを生成する方法であって、
立体表面を被覆し且つ偶数個の四辺形要素から構成される四辺形メッシュ中における、偶数個の自己交差点を有する双対輪体又は奇数個の自己交差点を有する双対輪体を連結して偶数個の自己交差点を有するように変換した双対輪体のデータを、双対輪体データ格納部に格納するステップと、
前記双対輪体データ格納部を参照して、前記双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第１の回路と、当該第１の回路に第１の基点で接続する第２の回路又は第１の基点を含む回路の第１の部分回路と、前記第１の回路に第２の基点で隣接する第３の回路又は第２の基点を含む回路の第２の部分回路とからなる三つ組み回路を特定し、三つ組み回路データ格納部に格納する三つ組み回路生成ステップと、
前記三つ組み回路データ格納部を参照して、前記三つ組み回路の第１の基点及び第２の基点における自己交差点の型の同一性を判断する同一性判断ステップと、
前記同一性判断ステップにおいて前記自己交差点の型の同一性が同一であると判断された場合のみ、前記三つ組み回路に対応して単純内部曲面を生成し、単純内部曲面を含む内部曲面を形成して、当該内部曲面に関するデータを内部曲面データ格納部に格納するステップと、
前記内部曲面データ格納部に格納されたデータを用いて前記立体内部に前記内部曲面の配置を生成し、前記内部曲面の配置において生ずる３つの内部曲面の交点を六面体要素に変換することにより六面体メッシュを生成し、当該六面体メッシュのデータを六面体メッシュデータ格納部に格納する六面体メッシュ生成ステップと、
を含み、コンピュータにより実行される六面体メッシュ生成方法。
【請求項９】
請求項１乃至８のいずれか１つ記載の六面体メッシュ生成方法をコンピュータに実行させるためのプログラム。
【請求項１０】
立体に対して六面体メッシュを生成するために必要なデータを生成するプログラムであって、
コンピュータに、
立体表面を被覆し且つ偶数個の四辺形要素から構成される四辺形メッシュ中における、偶数個の自己交差点を有する双対輪体又は奇数個の自己交差点を有する双対輪体を連結して偶数個の自己交差点を有するように変換した双対輪体のデータを、双対輪体データ格納部に格納するステップと、
前記双対輪体データ格納部を参照して、前記双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第１の回路と、前記第１の回路が第１及び第２の基点でそれぞれ接続し且つ前記双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第２及び第３の回路とからなる三つ組み回路を特定し、三つ組み回路データ格納部に格納する三つ組み回路生成ステップと、
前記三つ組み回路データ格納部を参照して、前記三つ組み回路の第１の基点及び第２の基点における自己交差点の型の同一性を判断し、判断結果を判断結果格納部に格納するステップと、
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算機を用いて物体の物理現象を数値的に解析する技術に関し、より詳しくは例えば有限要素法（ＦＥＭ：Finite Element Method）において三次元数値解析を行う際に用いられる六面体メッシュ生成技術に関する。
【背景技術】
【０００２】
近年、計算機を用いて物体の物理現象を数値的に解析し、工業製品の設計などに利用することが広く行われている。その中で最も広く用いられている代表的な手法が有限要素法である。有限要素法における物理現象の解析は、二次元又は三次元のメッシュを生成するというメッシュ生成工程と、メッシュに対して解析を行う解析工程に分離される。前者において使用されるシステムはメッシャ（mesher）と呼ばれ、後者で使用されるシステムはソルバ（solver）と呼ばれている。実際の作業においては、解析工程に必要とされる工数よりメッシュ生成工程に必要とされる工数の方が格段に多いため、メッシュ生成工程の合理化が望まれている。また、縦横比（aspect ratio）や要素の最小角（least angle）などが指標とされるメッシュの品質は解析結果に影響を与えるので、高品質のメッシュを生成することも重要であるとされている。
【０００３】
また、三次元的に物理現象を解析する必要がある場合も少なくない。三次元有限要素法において用いられるメッシュは、四面体メッシュ（quad mesh）、完全六面体メッシュ（all-hex mesh）、六面体主体メッシュ（hex dominant mesh）に大別される。なお、六面体主体メッシュは六面体要素以外に少数の五面体又は四面体を許容するメッシュである。これらの種類の中では、計算精度及び計算可能サイズの面で完全六面体メッシュが最も有利であるとされている。ここでは六面体要素だけからなる完全六面体メッシュ（以下六面体メッシュと記す）生成について問題とする。
【０００４】
六面体メッシュは、図１に示すように、（ａ）構造型（structured type）、（ｂ）正規型（regular type）、（ｃ）非正規型（non-regular type）に分類することができる。構造型六面体メッシュは、正規型の一種であり、メッシュ内部の節点（node）に隣接する節点数が一定のメッシュである。ここで、節点とは有限要素法における要素を構成する点を意味する。正規型メッシュとは、節点が層をなし、層と直交する掃引方向に並ぶ、メッシュ内部の節点に隣接する節点数が一定のメッシュをいう。非正規型メッシュとは、構造型でも正規型でもないメッシュをいう。構造型は六面体メッシュ自動生成には有利であるが、図２に示すように、断面に円が含まれる場合円の外周に辺が含まれない四辺形ａが発生するといった不自然な形状が現れ、解析結果に支障を生ずることが知られている。
【０００５】
正規型のメッシャには写像法（mapping）が広く使用され、端面形状の違いに対処可能である。しかしながら、端面の断面積に大きな差がある場合には歪みが大きくなるという問題がある。また、解析精度を上げるため局所的に六面体要素を高密度にするという処理も困難である。
【０００６】
従って、非正規型六面体メッシュの生成が望まれているが、現在のところ適用範囲が狭く、使用が限定されている。例えば、プラスタリング（plastering）という前線前進法（advancing front method）という方法について、内部を位相的な矛盾を生ずることなく埋め尽くすことは困難であることが報告されている。例えば "Seams and Wedges in plastering: A 3-D Hexahedral Mesh Generation Algorithm" Ted D. Blacker and Ray J. Meyers, Engineering with Computers (1993) 9:83-93 参照のこと。
【０００７】
また、特開平７−１２１５７９号公報には、一旦四面体メッシュを生成し、生成された四面体要素を２分割して六面体を生成するという方法も提案されているが、六面体要素の形状が良くないので応用範囲は著しく限定されている。
【０００８】
また、立体内部に六面体メッシュを生成し、立体表面との間に六面体要素を補間するという方法も提案されているが、最も問題となる表面に十分良好な形状の四辺形メッシュを張ることができないため、使用範囲が限定されている。例えば、"A Grid-Based Algorithm for the Generation of Hexahedral Elements Meshes", Robert Schneider, Engineering With Computers, Vol.12, pp.168-177,(1996)参照のこと。
【０００９】
さらに、双対輪体消去法という手法も提案されている。本手法では、与えられた多面体の表面を被覆する四辺形メッシュにおける四辺形要素の対辺を順次連結することにより生成され且つ表面を周回する双対輪体（dual cycle）の中から、側面が明確にシャープであるものを順次選び出し、双対輪体の両側にある一対の節点を一つにする縮約という工程を繰り返して六面体に帰着させ、その後縮約の逆順に縮約により対応する二つの節点を一つにすることにより得られる閉じた節点列を参照して、六面体要素の層を追加しながら縮約を解除することにより、物体内部を六面体要素のみからなるメッシュを生成する。しかし、これは途中の過程において側面が全てシャープでなければならないという制約があり、やはり使用範囲が限定されている。例えば、"Hexahedral Mesh Generation by Successive Dual Cycle Elimination: Matthias Mueller-Hannemann, Proc. of 7th International Meshing Roundtable, 1998"を参照のこと。
【００１０】
そして米国特許第５７６８１５６号には、注目すべき非正規型六面体メッシュ生成技術であるウィスカーウィービング（whisker weaving）が開示されている。本技術においては、立体表面の四辺形メッシュが有している位相構造に着目してこれより六面体メッシュの位相構造を定め、その後節点に座標値を与えるという２段階からなる。本手法では、与えられた多面体の表面を被覆する四辺形メッシュ（図３（ａ）における細線）において、四辺形要素の対辺を順次連結することにより表面を周回する双対輪体（図３（ａ）における太線）を境界とする曲面（図３（ｂ））を立体内部に形成する。ウィスカーウィービングでは、この処理によって形成された曲面を、その固有のデータ構造ＳＴＣ（Spatial Twist Continuum）の基本的な要素と位置付けて「シート」と呼んでいる。３つのシートが交差した点（図３（ｂ）の丸の位置）に六面体要素が存在する。ウィスカーウィービングのＳＴＣでは、シート毎に他のシートとの交差を表現し、保存する。そして、立体表面から順次シートを参照しながら位相的な交差を繰り返し求める。図３（ｃ）では、実線が立体表面を表し、一点鎖線がシートを表している。
【００１１】
ウィスカーウィービングの理論的根拠は、"Scott A. Mitchell, A Characterization of the Quadrilateral Meshes of a Surface Which Admits a Compatible Hexahedral Mesh of Enclosed Volume, Proc. of the 13th, Annual Symposium on Theoretical Aspects of Computer Science (STACS '96) Lecture Notes in Computer Science 1046, Springer, 1996, p.465-476"に開示されている。本手法はある程度の複雑さの非正規型六面体メッシュ生成に成功したが、頑健性（robustness）が不足し、広く使われるまでには至っていない。
【特許文献１】特開平７−１２１５７９号公報
【特許文献２】米国特許第５７６８１５６号
【特許文献３】特開２００３−５０８３０号公報
【非特許文献１】Scott A. Mitchell, A Characterization of the Quadrilateral Meshes of a Surface Which Admits a Compatible Hexahedral Mesh of Enclosed Volume, Proc. of the 13th, Annual Symposium on Theoretical Aspects of Computer Science (STACS '96) Lecture Notes in Computer Science 1046, Springer, 1996, p.465-476
【発明の開示】
【発明が解決しようとする課題】
【００１２】
ウィスカーウィービングにおいて、その固有のデータ構造であるシートは、幾何実体（geometrical entity）を有さない。その結果、双対輪体が自己交差する場合などの複雑な形状を呈する場合には、不適切なシート間の交差を作り出し、全体として位相的な矛盾を発生するのが頑健性に欠ける理由である。なお、シートという用語は、ウィスカーウィービング固有のデータ構造の一つの具体的なデータ表現形式として定義されているので、本願では、双対輪体を境界とする立体内部に形成され且つウィスカーウィービングのシートに対応する曲面を、内部曲面（interior surface）と呼ぶことにする。
【００１３】
本発明の目的は、内部曲面間の適切な位相的交差を得ることを可能とし、矛盾のない、非正規型の六面体メッシュの位相構造を得るための技術を提供することである。
【課題を解決するための手段】
【００１４】
本発明の第１の態様に係る、立体に対して六面体メッシュを生成する方法は、立体表面を被覆し且つ偶数個の四辺形要素から構成される四辺形メッシュ中における、偶数個の自己交差点を有する双対輪体又は奇数個の自己交差点を有する双対輪体を連結して偶数個の自己交差点を有するように変換した双対輪体のデータを、双対輪体データ格納部に格納するステップと、双対輪体データ格納部を参照して、双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第１の回路Ｂと、第１の回路Ｂが第１及び第２の基点Ｐ及びＱでそれぞれ接続し且つ双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第２及び第３の回路Ａ及びＣとからなる三つ組み回路Ｔ（＝｛Ａ，Ｂ，Ｃ｝）を特定し、三つ組み回路データ格納部に格納する三つ組み回路生成ステップと、三つ組み回路データ格納部を参照して、三つ組み回路Ｔの第１の基点Ｐ及び第２の基点Ｑにおける自己交差点の型の同一性を判断する同一性判断ステップと、自己交差点の型の同一性の判断結果に応じて単純内部曲面を生成し、単純内部曲面を含む内部曲面を形成して、当該内部曲面に関するデータを内部曲面データ格納部に格納するステップと、内部曲面データ格納部に格納されたデータを用いて立体内部に内部曲面の配置を生成し、内部曲面の配置において生ずる３つの内部曲面の交点を六面体要素に変換することにより六面体メッシュを生成し、当該六面体メッシュのデータを六面体メッシュデータ格納部に格納する六面体メッシュ生成ステップとを含む。
【００１５】
上で述べたような処理を行うことにより、適切に内部曲面を処理することができ、位相的に矛盾のない六面体メッシュを生成することができる。
【００１６】
なお、三つ組み回路については第２及び第３の回路が隣接しているという条件を付しても良い。より好ましい六面体メッシュが生成される。
【００１７】
上で述べた三つ組み回路生成ステップが、三つ組み回路Ｔを構成する回路についての双対輪体のデータを双対輪体データ格納部から除去するステップを含むようにしてもよい。
【００１８】
また、上で述べた同一性判断ステップにおいて、三つ組み回路Ｔにおける第１の基点Ｐ及び第２の基点Ｑを周回する領域中の点に対する、三つ組み回路Ｔが作る有向曲線に関する位数の組又は自己交差点に対する向き付けされた回路の包含性を判断するようにしてもよい。
【００１９】
さらに、上で述べた同一性判断ステップにおいて、三つ組み回路Ｔを平面投影して自己交差点の型の同一性を判断するようにしてもよい。
【００２０】
また、上で述べた同一性判断ステップにおいて、三つ組み回路Ｔを構成する第１の回路Ａ及び第３の回路Ｃ又は第２の部分回路Ｃのうち少なくとも一つが、唯一の他の回路と接続する場合、二つの自己交差点の型が同一であると判断されると、上記六面体メッシュ生成ステップにおいて、三つ組み回路Ｔに対応する単純内部曲面として向き付け可能な曲面を生成し、上で述べた同一性判断ステップにおいて、三つ組み回路Ｔを構成する第１の回路Ａ及び第３の回路Ｃ又は第２の部分回路Ｃのうち少なくとも一つが、唯一の他の回路と接続する場合、二つの自己交差点の型が相異すると判断されると、上で述べた六面体メッシュ生成ステップにおいて、三つ組み回路Ｔに対応する単純内部曲面として向き付け不能な曲面を生成するようにしてもよい。
【００２１】
上で述べた六面体メッシュ生成ステップが、上で述べた同一性判断ステップにおいて、三つ組み回路Ｔを構成する第１の回路Ａ及び第３の回路Ｃ又は第２の部分回路Ｃに唯一の他の回路と接続する回路が存在しない場合、二つの自己交差点の型が同一であると判断されると、三つ組み回路Ｔを一つの回路としてみなし、第１の回路Ａ及び第３の回路Ｃ又は第２の部分回路Ｃに接続する第２の回路Ｂ又は第１の部分回路Ｂ以外の２つの回路と組み合わせた新たな三つ組み回路Ｔに対応する内部曲面を生成するステップを含むようにしてもよい。
【００２２】
本発明の第２の態様に係る六面体メッシュ生成方法は、立体表面を被覆し且つ偶数個の四辺形要素から構成される四辺形メッシュ中における、偶数個の自己交差点を有する双対輪体又は奇数個の自己交差点を有する双対輪体を連結して偶数個の自己交差点を有するように変換した双対輪体のデータを、双対輪体データ格納部に格納するステップと、双対輪体データ格納部を参照して、双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第１の回路と、当該第１の回路に第１の基点で接続する第２の回路又は第１の基点を含む回路の第１の部分回路と、第１の回路に第２の基点で隣接する第３の回路又は第２の基点を含む回路の第２の部分回路とからなる三つ組み回路を特定し、三つ組み回路データ格納部に格納する三つ組み回路生成ステップと、三つ組み回路データ格納部を参照して、三つ組み回路の第１の基点及び第２の基点における自己交差点の型の同一性を判断する同一性判断ステップと、同一性判断ステップにおいて自己交差点の型の同一性が同一であると判断された場合のみ、上記三つ組み回路に対応して単純内部曲面を生成し、単純内部曲面を含む内部曲面を形成して、当該内部曲面に関するデータを内部曲面データ格納部に格納するステップと、内部曲面データ格納部に格納されたデータを用いて立体内部に前記内部曲面の配置を生成し、内部曲面の配置において生ずる３つの内部曲面の交点を六面体要素に変換することにより六面体メッシュを生成し、当該六面体メッシュのデータを六面体メッシュデータ格納部に格納する六面体メッシュ生成ステップとを含む。このように自己交差点の型が同一な場合のみ六面体メッシュを生成すれば、より品質の良い六面体メッシュを得ることができる。
【００２３】
本発明の第３の態様に係るプログラムは、立体に対して六面体メッシュを生成するために必要なデータを生成するプログラムであって、コンピュータに、立体表面を被覆し且つ偶数個の四辺形要素から構成される四辺形メッシュ中における、偶数個の自己交差点を有する双対輪体又は奇数個の自己交差点を有する双対輪体を連結して偶数個の自己交差点を有するように変換した双対輪体のデータを、双対輪体データ格納部に格納するステップと、双対輪体データ格納部を参照して、双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第１の回路と、第１の回路が第１及び第２の基点でそれぞれ接続し且つ双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第２及び第３の回路とからなる三つ組み回路を特定し、三つ組み回路データ格納部に格納する三つ組み回路生成ステップと、三つ組み回路データ格納部を参照して、三つ組み回路の第１の基点及び第２の基点における自己交差点の型の同一性を判断し、判断結果を判断結果格納部に格納するステップとを実行させるものである。
【００２４】
本発明に係る六面体メッシュ生成方法をコンピュータに実行させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等の記憶媒体又は記憶装置に格納される。また、ネットワークを介してディジタル信号にて頒布される場合もある。なお、処理途中のデータについては、コンピュータのメモリ等の記憶装置に一時保管される。
【発明の効果】
【００２５】
本発明によれば、内部曲面間の適切な位相的交差を得ることを可能とし、矛盾のない、非正規型六面体メッシュの位相構造を得ることができるようになる。
【発明を実施するための最良の形態】
【００２６】
［本発明の概要］
本発明においては、立体表面を被覆する、偶数個の四辺形要素から構成される四辺形メッシュの双対輪体を境界として内部曲面の配置を立体内部に生成し、当該配置中に現れる、内部曲面の３個の交点を六面体要素に変換することによって、六面体メッシュを生成する。本発明に係る六面体メッシュ生成方法を、内部曲面直接配置法（interior surface direct arrangement method）と呼ぶことにする。但し、これ自体は、既知のアイデアである。
【００２７】
本発明では、偶数個の自己交差点（self-intersecting point）を有する双対輪体に着目する。奇数個の自己交差点を有する双対輪体については、これを２個連結して１つの「偶数個の自己交差点を有する双対輪体」として取り扱うことにする。
【００２８】
偶数個の自己交差点を有する双対輪体を自己交差点で切断分離して得られた部分双対輪体が自己交差しないとき、その部分双対輪体を回路（circuit）と規定することができ、回路を規定した自己交差点を基点（base point）と呼ぶことにする。また、回路をその上の基点でない二つの点で切断し、当該二つの点の間を曲線で結ぶことにより形成され且つ基点を含む側の閉曲面を部分回路（sub-circuit）と呼ぶことにする。回路が規定された後、既に規定された回路は存在しないとみなして、さらに再帰的に回路を規定することができる。複数個の自己交差点を有する双対輪体の一例を図４（ａ）に示す。図４（ａ）の例では、双対輪体は基点Ｒ１乃至Ｒ４を有する。なお、点線は自己交差曲線（self-intersecting curve）である。図４（ａ）に示した双対輪体を位相的に等価に変形すると図４（ｂ）のような双対輪体になる。図４（ｂ）のような双対輪体であれば、回路を規定することができる。
【００２９】
二つの回路が一つの基点を共有することを、回路が接続（incident）するということにする。二つの回路が、基点を両端とする一つの辺を介して連結していることを、回路が隣接（adjacent）するということにする。回路Ｃに接続する回路が一つしか存在しないとき、回路Ｃは葉（leaf）であるということにする。
【００３０】
回路Ａと、回路Ａに基点Ｐで接続する回路Ｂあるいは基点Ｐを含む回路の部分回路Ｂと、回路Ａに基点Ｑで隣接する回路Ｃあるいは基点Ｑを含む回路の部分回路Ｃとからなる回路群Ｔ＝｛Ａ，Ｂ，Ｃ｝を三つ組み回路（triple-circuit）ということにする。三つ組み回路には向きを与えることができる。
【００３１】
三つ組み回路は、図５（ａ）乃至（ｅ）に示すような形を有する。これらを得るために三つ組み回路を平面に射影変換する。平面に射影変換された三つ組み回路（plane-projected triple-circuit）に対して自己交差点の型（self-intersecting point type）の同一性を、自己交差点を周回する領域中の点の位数（order）を使用して、具体的には位数の四つ組が円順列として同一ならば自己交差点の型が同一、さもなければ自己交差点の型が同一でないと判定する。但し、位数とは平面上の曲線が、与えられた点の周りに右回り方向（反時計回り）に周回する回数である。なお、左回りは−１回にカウントする。図５においては（ａ）乃至（ｃ）については位数の四つ組が同一であるため自己交差点の型は同一と判定され、（ｄ）及び（ｅ）については位数の四つ組が異なるため自己交差点の型は異なると判定される。なお、図５では紙面裏から見て右回り又は左回りを判定している。
【００３２】
図５（ａ）に示した三つ組み回路に対応する内部曲面は例えば図６に示すような曲面である。また、図５（ｄ）に示した三つ組み回路に対応する内部曲面は例えば図７に示すような曲面である。
【００３３】
自己交差点の型の同一性は、上で述べた位数を用いる方法を変形して判定することも可能である。例えば、双対輪体を自己交差しない三つの回路に分解する。型の同一性は、自己交差点とその対蹠点に関する回路の包含関係と回転方向を用いて判定することができる。また、自己交差点から無限遠点に至る曲線と回路の交差を用いても判定可能である。
【００３４】
三つ組み回路Ｔを構成する回路が少なくとも一つの葉を含み、三つ組み回路Ｔの自己交差点の型が同一である場合には、対になった自己交差点の間に自己交差線を有し且つ三つ組み回路Ｔを境界とする、向き付け可能な曲面を、三つ組み回路Ｔに対応する内部曲面として生成することができる。また、三つ組み回路Ｔを構成する回路が少なくとも一つ葉を含むが、三つ組み回路Ｔの自己交差点の型が同一ではない場合には、対になった自己交差点の間に自己交差線を有し且つ三つ組み回路Ｔを境界とする、向き付け不能な曲面（メビウスの帯と同相である）を、三つ組み回路Ｔに対応する内部曲面として生成することができる。
【００３５】
三つ組み回路Ｔ＝｛Ａ，Ｂ，Ｃ｝を構成する回路が葉を含まず、且つ二つの自己交差点の型が同一である場合、三つ組み回路Ｔを一つの回路とみなし、回路Ａ及びＣに接続するＢでない回路Ｘ及びＹと組み合わせた新たな三つ組み回路Ｔ'＝｛Ｘ，Ｔ，Ｙ｝に対応する内部曲面を、上で述べた三つ組み回路が葉を含む場合の内部曲面生成方法を再帰的に適用することにより生成することができる。図８に示すように、回路Ａ乃至Ｃを一つの回路としてみなせば、Ｘ，Ｙ及びＴにて三つ組み回路Ｔが構成されるようになる。
【００３６】
双対輪体を三つ組み回路の連結和として表現しておき、上で述べた方法で生成した各三つ組み回路に対応する内部曲面の連結和を作る、フィレットを付与する等の方法で、双対輪体を境界とする内部曲面を生成する。
【００３７】
内部曲面が生成されたならば、三次元胞複体（3-dimensional cell-complex）として表現され且つメッシュ生成対象である立体を内部曲面により切断する。三次元胞複体は、立体を次の開集合（open set）である胞体（cell）の直和（direct sum）として表現する。すなわち、三次元胞体（3-cell）により体分（volume）を表し、二次元胞体（2-cell）により面分（face）を表し、一次元胞体（1-cell）により稜線（edge）を表し、０次元胞体（0-cell）により頂点（vertex）を表す。なお、面分の幾何実体は曲面である。また、稜線の幾何実体は曲線である。さらに頂点の幾何実体は点である。
【００３８】
このような表現方法は、既に例えば"H.Masuda et al., A mathematical Theory and Application of Non-manifold Geometric Modeling, GI-IFIP Symposium 89, p.78"において開示されており、六面体メッシュ生成においても既に具体例が示されている。
【００３９】
図９に三次元胞複体を上で述べたような表現方法で表した例を示す。図９（ａ）の三次元胞複体は、体分Ｖ１及びＶ２にて構成され、面分ｆ１乃至ｆ１１で規定される。面分ｆ１は稜線ｅ１乃至ｅ４、面分ｆ２は稜線ｅ３，ｅ７，ｅ８及びｅ１１、面分ｆ３は稜線ｅ４，ｅ５，ｅ８及びｅ１２、といったように規定される。さらに、稜線ｅ１は頂点ｖ１及びｖ２、稜線ｅ２は頂点ｖ２及びｖ３、稜線ｅ３は頂点ｖ３及びｖ４、といったように規定される。また、図９（ａ）で示した体分Ｖ、面分ｆ、稜線ｅ、頂点ｖとの関係をツリー構造で表すと、図９（ｂ）のようになる。すなわち、体分Ｖ１は面分ｆ１乃至ｆ６に関係し、体分Ｖ２は面分ｆ６乃至ｆ１１に関係している。稜線ｅ９は、面分ｆ３、ｆ６及びｆ８に関係している。また、頂点ｖ５は、稜線ｅ５、ｅ９、ｅ１３に関係している。
【００４０】
二次元胞複体を取り扱う境界表現Ｂ−Ｒｅｐのソリッドモデリング（solid modeling）において立体の曲面による切断はよく知られた技術である。立体を三次元胞複体の体分に置き換え、三次元胞複体Ｋを構成する全ての体分Ｖiに対して「立体の曲面による切断」という操作を繰り返し適用することにより、三次元胞複体Ｋとして表現された立体が内部曲面で切断され、三次元胞複体Ｋが更新され、三次元胞複体Ｋ*に変換される。
【００４１】
この三次元胞複体Ｋ*の表面では、双対輪体が稜線ｅ*に、入力された四辺形メッシュＱの四辺形要素が頂点ｖ*に、入力された四辺形メッシュＱの頂点は面分ｆ*に対応している。また、この三次元胞複体Ｋ*の内部では、３つの内部曲面の交点である頂点ｖ*は生成しようとする六面体メッシュＭの六面体要素ｈ、二つの内部曲面の交線である稜線ｅ*は六面体メッシュＭの四辺形要素ｑ、稜線ｅ*で囲まれた面分ｆ*は六面体メッシュＭの節点間の稜線ｅ、面分ｆ*で囲まれた体分Ｖ*は六面体メッシュＭの節点ｎに対応する。これらの関係は双対（duality）と言われている。これは、"Timothy J. Tautges, Ted Blacker, and Scott A. Mitchell, The Whisker Weaving Algorithm: A Connectivity-Based Method for Constructing All-Hexahedral Finite Element Method, Draft submitted to the International Journal of Numerical Methods in Engineering, (Mar. 12, 1996)"等に開示されている。
【００４２】
このような双対関係と胞複体の位相データを使用して、三次元胞複体Ｋ*を六面体メッシュＭに変換する。変換は、例えば一つの六面体要素を出発点にして、上記の位相関係を参照しながら位相を前線前進法で確定する方法で容易に実現可能である。このような方法についても上で述べたウィスカーウィービングの論文で述べられている。
【００４３】
なお、このようにして生成された六面体メッシュＭには、図１０（ａ）及び（ｂ）に示すように、凸性を喪失した四辺形（convexity-lost quad）の対が存在する場合もある。なお、図１０（ｂ）の方が凸性のない一般的な四辺形を示している。位相要素の連結関係（connectivity）により凸性喪失をグラフ論的に表現すれば、六面体メッシュＭにおいて二つの面分を二以上の稜線が連結する状態である。これは、図１１（ａ）に示すように、六面体メッシュＭの双対表現である三次元胞複体Ｋ*において、二つの稜線ｅ１*及びｅ２*が共に二つの面分ｆ１*及びｆ２*に接続する状態である。凸性を回復するためには図１１（ｂ）のように面分ｆ１*及びｆ２*を分割すればよい。このようにすると面分が新たに発生するが、新たに発生した面分をすべて含み、１以上の立体内部で閉じる内部曲面（閉内部曲面（closed interior surfaces））を新たに追加して三次元胞複体Ｋ*を更新する。閉内部曲面については、例えば三次元胞複体Ｋ*の表面を初期状態とする前線を物体内部に前進させ、新たに発生した面分に達した場合には、その位置で前線の面分を固定するという操作を繰り返すことによって得ることができる。例えばこの方法で凸性を回復した三次元胞複体Ｋ*を六面体メッシュ変換の対象とすれば、凸性回復の問題を解決することができる。閉内部曲面を挿入するという方法は、"Timothy J. Tautges, Ted Blacker, and Scott A. Mitchell, The Whisker Weaving Algorithm: A Connectivity-Based Method for Constructing All-Hexahedral Finite Element Method, Draft submitted to the International Journal of Numerical Methods in Engineering, (Mar. 12, 1996)"等に開示されている。
【００４４】
局所的凸性回復は、六面体メッシュＭHの双対頂点の集合Ｖ*と双対稜線の集合Ｅ*が作る掃つりグラフＧV（Ｖ*, Ｅ*）が単純でない場合に適用することができる。これは三次元の場合、内部曲面の位置を局所的に変更するものであり、通常空間ではフィリッピング（Marshall Bern, David Eppstein, Flipping Cubical Meshes, ACM Computer Science Archive June 29, 2002 を参照のこと）という名で知られている。二次元の場合は双対輪体を局所的に変更することによって凸性を回復する。その概念を二次元の場合を例にして図１２Ａに示す。図１２Ａの左に示すように凸性が失われていても、右側に示すように変形される。
【００４５】
また、図１２Ｂにおいて、内部曲面Ｓ上に隣接双対頂点ｖ1*及びｖ2*を結ぶ二つの双対稜線ｅa*及びｅa*'が存在し、二つの内部曲面の交線上に隣接する双対稜線ｅx*及びｅy*並びにｅx*'及びｅy*'が存在し、双対頂点ｖ4*及びｖ4*'が相異なるとする。このとき、内部曲面Ｓに交差する内部曲面Ｔを局所的に変更して双対頂点ｖ3*及びｖ3*'を双対稜線ｅa*及びｅa*'上に移動することによって隣接双対頂点ｖ1*及びｖ2*間の凸性を回復することができる。
【００４６】
なお、このような方法によらずとも凸性を喪失したまま三次元胞複体Ｋ*を六面体メッシュＭに変換し、図１０（ａ）及び（ｂ）のように凸性を喪失したまま三次元胞複体Ｋ*を六面体メッシュＭに変換し、図１２Ｃに示すような六面体の層を挿入することによって凸性を回復するようにしても良い。このような方法は、前記の閉内部曲面挿入の双対形であると解することができる。
【００４７】
以上の方法で六面体メッシュＭの位相を決定した後、節点の座標値を埋め込む。節点の座標値を埋め込む方法としては、ラプラシアンを用いる方法がよく知られている。この方法は、例えば"Matthias Mueller-Hannemann, Hexahedral Mesh Generation by Successive Dual Cycle Elimination: Proc. of 7th International Meshing Roundtable, pp. 365-378(1998)"に開示されている。ラプラシアンは任意の節点に隣接する節点の座標値の平均を更新すると言う処理を繰り返すものである。
【００４８】
以上の方法によって非正規型六面体メッシュを生成することが可能となる。
【００４９】
［具体的な実施の形態］
図１３に、本実施の形態における六面体メッシュ生成装置の機能ブロック図を示す。本実施の形態における六面体メッシュ生成装置は、立体データ格納部１と、四辺形メッシュ生成部３と、四辺形メッシュデータ格納部５と、双対三次元胞複体生成部７と、双対胞複体データ格納部９と、双対輪体テーブル生成部１１と、双対輪体テーブル格納部１３と、双対輪体組合せ表生成部１５と、双対輪体組合せ表格納部１７と、三つ組み回路表生成部１９と、三つ組み回路表格納部２１と、単純内部曲面生成部２３と、内部曲面データ初期化部２５と、内部曲面データ格納部２７と、内部曲面処理部２９と、幾何演算処理部３１と、凸性回復処理部３５と、六面体メッシュ生成部３７と、六面体メッシュデータ格納部３９と、座標算出部４１とを含む。
【００５０】
次に本実施の形態における六面体メッシュ生成装置の処理を図１４及び図１５を用いて説明する。まず、四辺形メッシュ生成部３は、六面体メッシュの生成対象たる立体のデータを格納する立体データ格納部１を参照して、周知の方法で四辺形メッシュを立体に対して生成し、当該四辺形メッシュのデータを四辺形メッシュデータ格納部５に格納する（ステップＳ１）。次に、双対三次元胞複体生成部７は、四辺形メッシュデータ格納部５を参照して、四辺形メッシュＭQの双対三次元胞複体Ｋ*を生成し、当該双対三次元胞複体Ｋ*のデータを双対胞複体データ格納部９に格納する（ステップＳ３）。そして、双対輪体テーブル生成部１１は、四辺形メッシュデータ格納部５及び双対胞複体データ格納部９を参照して、双対三次元胞複体Ｋ*から双対輪体テーブルＤTを生成し、双対輪体テーブル格納部１３に格納する（ステップＳ５）。また、双対輪体組合せ表生成部１５は、双対輪体テーブル格納部１３に格納された双対輪体テ−ブルＤTから双対輪体組合せ表Ｄcを生成し、双対輪体組合せ表格納部１７に格納する（ステップＳ７）。
【００５１】
ここで双対輪体組合せ表Ｄcの全ての要素について処理したか判断する（ステップＳ９）。双対輪体組合せ表Ｄcの全ての要素について処理したと判断された場合には端子Ａを介して図１５の処理に移行する。一方、双対輪体組合せ表Ｄcにおいて未処理の要素が存在する場合には、三つ組み回路表生成部１９は、双対輪体組合せ表格納部１７に格納された双対輪体組合せ表Ｄcから三つ組み回路表ＴTを生成し、三つ組み回路表格納部２１に格納する（ステップＳ１１）。また、内部曲面初期化部２５は、内部曲面データ格納部２７の初期化処理を実施する（ステップＳ１３）。処理は端子Ｂを介して図１５の処理に移行する。
【００５２】
次に、三つ組み回路表ＴTの全ての要素について処理したか判断する（ステップＳ１５）。三つ組み回路表ＴTの全ての要素を処理したと判断された場合にはステップＳ２１に移行する。一方、三つ組み回路表ＴTにおいて未処理の要素が存在する場合には、単純内部曲面生成部２３は、三つ組み回路表格納部２１を参照して、未処理の三つ組み回路Ｔjに対応する内部曲面Ｓijを生成し、内部曲面のデータを内部曲面データ格納部２７に格納する（ステップＳ１７）。そして、内部曲面処理部２９は、内部曲面データ格納部２７を参照して、内部曲面Ｓijを連結して内部曲面Ｓiを生成し、自己交差線を追加する処理を実施し、処理結果を内部曲面データ格納部２７に格納する（ステップＳ１９）。そしてステップＳ１５に戻る。
【００５３】
ステップＳ１５で三つ組み回路表ＴTの全ての要素について処理したと判断された場合には、幾何演算処理部３１は、内部曲面データ格納部２７を参照して、内部曲面Ｓiを双対三次元胞複体Ｋ*に配置する処理を実施し、処理結果を双対胞複体データ格納部９に格納する（ステップＳ２１）。そして端子Ｃを介して図１４に戻る。
【００５４】
そしてステップＳ９で双対輪体表Ｄcの全ての要素について処理したと判断された場合には端子Ａを介して図１５のステップＳ２３に移行する。ステップＳ２３では、凸性回復処理部３５は、双対胞複体データ格納部９を参照して、双対三次元胞複体Ｋ*の凸性を回復させる処理を実施し、処理結果を双対胞複体データ格納部９に格納する。その後、六面体メッシュ生成部３７は、双対胞複体データ格納部９を参照して、双対三次元胞複体Ｋ*を六面体メッシュＭHに変換し、当該六面体メッシュのデータを六面体メッシュデータ格納部３９に格納する（ステップＳ２５）。また、座標算出部４１は、六面体メッシュデータ格納部３９を参照して、六面体メッシュＭHの節点の座標値を算出し、六面体メッシュデータ格納部３９に格納する（ステップＳ２９）。
【００５５】
以上処理の流れを説明したが具体的処理内容については以下に説明する。
【００５６】
（１）四辺形メッシュＭQの双対である三次元胞複体Ｋ*の生成（ステップＳ３）
一般の三次元胞複体は、物体（Body）、体分（volume）、面分（face）、稜線（edge）、頂点（vertex）を位相要素（topological element）とする胞複体として実装される。三次元胞複体Ｋ*をシステムとして実装するためには、各位相要素に識別子を付与し、相互の接続隣接関係を表すデータ構造が必要である。但し、図１６（ａ）に示すように、Loopは面分の境界を表し、右回りが外Loop（親Loop）、左回りが内Loop（子Loop）を表すものとする。面分は外Loopを用いて表現する。外Loopは面分において１個しか存在しない。また、図１６（ａ）における点線はポインタが存在することを表している。このような表現方式を採用すれば、図１６（ｂ）に示されるような「島」を表現することができるようになる。
【００５７】
具体的には、例えば以下に示すようなデータ構造を採用することができる。位相要素に一意な識別子を付して、その関係を表現する方式も採用することができるが、ここでは各体分を独立した二次元多様体として各要素に識別子を与える表現を行い、当該各要素の間の関係を保有する方式を採用している。
【００５８】
なお、以下のBackus-Naum記法では識別子が省略されるが、Body, Volume, Winged Edge, Loop, Vertex は識別子を有し、配列などを用いたダイレクトアクセスが可能である内部データ構造を有するものを採用する。またtopという記号は、上位の位相要素を表現する下位の位相要素の代表であることを意味し、それから他の位相要素の検索が可能である。ＲとＬはそれぞれ右と左を表す。
＜Body＞::=＜Volume_top＞
＜Volume＞::=＜Winged_Edge_top＞
＜Winged_Edge＞::=＜Volume＞
＜Loop_L＞＜Loop_R＞＜Edge_succ_L＞＜Edge_succ_R＞＜Edge_prec_L＞＜Edge_prec_R＞
＜Vertex_succ＞＜Vertex_prec＞＜Curve＞
＜Loop＞::=＜Volume＞＜Volume_opp＞＜Loop_opp＞＜Loop_outer＞{＜Loop_ubber＞}
＜Loop_outer＞::=＜Winged_Edge_top＞＜Loop_Child＞＜Surface＞＜Direction＞
＜Loop_inner＞::=＜Loop_Parent＞＜Loop_Brother＞
＜Vertex＞::=＜Volume＞＜Edge＞＜Point＞
【００５９】
ここではウィングドエッジ構造を採用したが、ハーフエッジ構造を採用しても全く問題はない。更に一般的な非多様体構造を使用することも可能ではあるが、構造が複雑なので得策ではない。これらの構造はよく知られているので、詳細な説明は省略する。詳しくは、"B.G.Baumgart, Geometric Modeling for Computer Vision, Stanford, Artificial Intelligence Laboratory Memo AIM 249 Computer science Department report, No. CS-463, (1974)"、"Martti Mantyla, An Introduction to Sold Modeling, Computer Science Press, (1987)"、"K.J. Weiler, Topological Structure for Geometric Modelling, Rensselaer Polytecnic Institute Doctorial Thesis, (1989)"などを参照のこと。
【００６０】
図１７に示したように、物体が、体分１１０及び１２０から構成されるとする。物体はそれを構成する代表体分にポインタを有する。物体において隣接する体分１１０及び１２０は共通する面分２１０に接続する。この接続関係はLoopに保有される。
【００６１】
体分は独立して一つの二次元胞複体として表現される。体分はそれを構成する代表ウィングドエッジ情報に対するポインタを有する。
【００６２】
面分は、１個の外ループと０個以上の内ループで表現される。面分の幾何データは外ループが管理する。体分の稜線はウィングドエッジ情報で表現される。
【００６３】
ウィングドエッジ情報は図１８のデータとそれが属する体分へのポインタを有する。図１８では、稜線１００は、両端の頂点１０３及び１０７（Vertex_prec, Vertex_succ）と、稜線１０１，１０２，１０６及び１０８（Edge_prec_L, Edge_prec_R, Edge_succ_L, Edge_succ_R）と、ループ１０４及び１０５（Loop_L, Loop_R）とで表現される。頂点は、それが接続する代表稜線のウィングドエッジへのポインタを有する。
【００６４】
なお、上記のデータ構造は位相要素の連結関係を調べるために辿りが発生して、効率が低いことがある。その時はデータを冗長に保有する、リストなどで管理するなどの方法で、計算機環境や処理対象のサイズなどに合わせて適宜対応する必要がある。
【００６５】
上記データ構造を用いて四辺形メッシュＭQの双対である三次元胞複体Ｋ*を表現するためには、上で述べた双対の対応関係を用いて行う。なお、三次元胞複体Ｋ*の頂点ｖ*及び稜線ｅ*は次のようになり、それを通過する後述の内部曲面の識別子を保有する形式にしておくと、処理が高速になり、プログラム作成も容易になる。
＜Edge＞::=＜Winged_edge_top＞＜Interior_surf_1＞＜Interior_Surf_2＞
＜Vertex＞::=＜Volume＞＜Edge＞＜Point＞
＜Interior_surf_1＞＜Interior_Surf_2＞＜Interior_surf_3＞
【００６６】
上記の構造に、入力データである四辺形メッシュＭQの内部空洞に実体が充填されたものとして、三次元胞複体Ｋ*に初期値を格納する。具体的には、四辺形メッシュＭQの各四辺形要素ｑを構成する頂点が作る図心（重心）（centroid）（barycenter）を三次元胞複体Ｋ*の頂点ｖ*に対応させる。三次元胞複体Ｋ*において隣接する頂点ｖ*、ｖ*'の間に稜線ｅ*を作るが、これは四辺形メッシュＭQの二つの四辺形ｑ，ｑ'の間にある稜線ｅに対応する。四辺形メッシュＭQの頂点ｖを周回する稜線ｅの列に対応する稜線ｅ*は、三次元胞複体Ｋ*において四辺形メッシュＭQの頂点ｖに対応する面分ｆ*を形成する。これらの面分ｆ*はただ一つのボリュームＶ*に接続する。
【００６７】
なお本実施の形態において「接続」とは、開集合である位相要素１と開集合である位相要素２の一方が他方の境界になっている状態を意味する。また、「隣接」とは開集合である位相要素１と開集合である位相要素２が共に両者と相異なる位相要素３に接続することをいう。
【００６８】
（２）双対輪体テーブルＤT（dual cycle table）の生成（ステップＳ５）
双対輪体テーブルＤTは、識別子を与えられた双対輪体を構成する、四辺形メッシュＭQの四辺形要素ｑ及び三次元胞複体Ｋ*の頂点ｖ*を管理する表であり、システム構築の必要に応じて自己交差点の数及び頂点ｖ*の識別子、近似平面、図心、法線方向、及び頂点ｖ*毎の四辺形メッシュＭQにおいて隣接する四辺形要素ｑ間の二面角などの属性を保有することができるデータ構造を有する。この双対輪体テーブルＤTは、自動的に双対輪体組合せ表を生成する時、内部曲面の境界である閉曲面を生成する時に、使用される。
【００６９】
双対輪体テーブルＤTは、例えば、四辺形メッシュＭQの四辺形要素ｑを探索して二つの対辺の組を作業テーブルＴWに全て書き込み、作業テーブルＴWが空になるまでその中の一つを基点にして定めた方向に周回しながら上で述べたデータを１周するまで書き込み、作業テーブルから処理を行った対辺の組のデータを削除することにより生成される。
【００７０】
（３）双対輪体組合せ表（dual cycle combination table）Ｄcの生成（ステップＳ７）
双対輪体組合せ表は、一つの内部曲面に対してその境界となる双対輪体の組合せを双対輪体の識別子で表現したテーブルである。
【００７１】
内部曲面の境界を構成する双対輪体組合せ表Ｄcの生成指針は以下のとおりである。なお、図１９（ａ）に示すように、双対輪体がシャープなエッジと交差する場合には双対エッジはシャープ（sharp）であるといい、図１９（ｂ）に示すように、交差しない場合にはフラット（flat）ということとする。
（ａ）自己交差がないシャープな双対輪体は単独とする。（図２０Ａ（ａ））
（ｂ）自己交差がないフラットな双対輪体は対にする。同心円状になる場合には交差しないようにする。（図２０Ａ（ｂ））
（ｃ）自己交差を有するフラットな双対輪体は、自己交差の数と型が同一なものを対とする。（図２０Ａ（ｃ））
（ｄ）型が同一な偶数個の自己交差点を有する双対輪体は単独とする。（図２０Ａ（ｄ））
【００７２】
双対輪体テーブルＤTを参照して選択することになるが、上記の生成指針に従って自動的に決定する。しかし、双対輪体の数はそれほど多くないので、双対輪体テーブルＤTから候補を自動的に抽出して計算機の表示装置に表示し、ユーザが最終的な組合せを決定するようにしても良い。
【００７３】
（４）三つ組み回路表（triple-circuit table）ＴTの生成（ステップＳ１１）
まず、回路を構成する双対輪体の頂点の識別子の対（区間を表す）の列で表現される回路表を生成する。
【００７４】
図２０Ｂに示すような双対輪体が存在する場合には、回路Ｃ1は頂点ｑa, ｑbで表され、回路Ｃ2は頂点ｑc, ｑdで表され、回路Ｃ3はｑe, ｑfで構成され、回路Ｃ4は頂点ｑg, ｑc, ｑd, ｑe, ｑf, ｑhで構成され、回路Ｃ5は頂点ｑi, ｑjで構成され、回路Ｃ6は頂点ｑk, ｑlで構成され、回路Ｃ7は頂点ｑa, ｑb, ｑg, ｑh, ｑi, ｑj, ｑk, ｑlで構成される。
【００７５】
なお、回路表の生成法は一意ではない。例えば、次の方法が実用的である。
（ａ）双対輪体に方向を与える。
（ｂ）葉の回路を一つ選ぶ。
（ｃ）進行方向に最近の葉を選ぶ（繰り返し）
【００７６】
次に、三つ組み回路表を生成する処理を実施するが、三つ組み回路も一意性があるとは限らない。例えば、次の方法が実用的である。
（ａ）回路表に対称性があるか否かを確認する。すなわち、ある区間から両方に進行して到達した自己交差点の対の型が同じであるかどうかを確認する。
【００７７】
（ｂ）対称性がある場合には、以下の規則に従う。
すなわち、図２１に示すように、葉ではない回路Ｃ1，Ｃ2，Ｃ3において、Ｃ1及びＣ3はＣ2を介して隣接するとする。Ｃ1とＣ2間並びにＣ2とＣ3間の基点Ｐ1及びＰ3の自己交差点の型が同一であり、基点Ｐ1及びＰ3間の双対輪体上に存在する自己交差点の数が偶数である時、Ｔ＝｛Ｃ1，Ｃ2，Ｃ3｝を三つ組み回路とすることができる。三つ組み回路Ｔ＝｛Ｃ1，Ｃ2，Ｃ3｝に対応する単純内部曲面を生成することによって回路Ｃ2が二つの回路Ｃ2'及びＣ2"に分離され、回路Ｃ1及びＣ3が同一視される。図２１の場合、回路ＣA，Ｃ1＝Ｃ3，ＣBを新しい三つ組みとすることができる。さらにＣ2"において同じようにして本規則を適用することができる。本規則は、掃引型の六面体メッシュを生成する場合重要な役割を果たす。ちなみに、基点Ｐ1及びＰ3の自己交差点の型が同一であることを要求するのは、メビウスの帯ができることによる六面体メッシュの品質低下を防止するためである。これに意を介さなければ型の同一性の制約を除外することができる。
【００７８】
（ｃ）対称性がない場合には、以下の規則に従う。なお、可能な限り基点の型が同一になるように選択する。
葉である回路Ｃ1、回路Ｃ1に接続する回路Ｃ2、及び回路Ｃ1に隣接する回路Ｃ3を選択し、三つ組み回路Ｔ＝｛Ｃ1，Ｃ2，Ｃ3｝とする。この規則に従えば、図２２Ａに示された（１）乃至（３）の３つの三つ組み回路が特定される。
【００７９】
ここでは隣接する回路間に単純内部曲面を生成する理由は、隣接しない回路間に単純内部曲面を作ろうとすれば、図２２Ｂ（ａ）に示すように自己交差線が交差して八面体ができるが、図２２Ｂ（ｂ）に示すようにハンドルを付けるなどの方法で八面体ができるのを回避するには可能であるものの、六面体のメッシュ品質が著しく低下するためである。なお、品質の低下に意を介さなければ、回路Ｃ2に隣接する２つの回路Ｃ1及びＣ3で三つ組み回路を形成することができる。
【００８０】
（５）内部曲面データの初期化（ステップＳ１３）
内部曲面は、位相的には、境界を有する二次元多様体を胞複体として表現することもできるが、三次元胞複体として実現するのが有利である。また、幾何データは自由曲面／自由曲線で表現しても良いし、三角形メッシュ／点列の形で表現しても良い。自由曲面はベジエ、B-Spline、ＮＵＲＢＳなどの表現方法があり、ＣＡＤ（Computer Aided Design）で広く使用されているので詳細説明は省略する。例えば、Gerald Farin, Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide, Academic Press (1990)を参照のこと。いずれにせよ本工程では、単純な内部曲面Ｓijを生成し、各内部曲面Ｓiを単純な内部曲面Ｓijに設定する。
【００８１】
また、三角形メッシュは曲面を三角形の集合として表現するものであり、ＳＴＬ（Stereolithography）フォーマットのように位相構造を有しないものや、計算を高速化するために位相データを有する形式も使用することができる。
【００８２】
（６）Ｔjに対応する単純な内部曲面Ｓijの生成（ステップＳ１７）
内部曲面Ｓijも三次元胞複体として実現するのが有利である。本実施の形態においては、ホモトピーをベースとした内部曲面生成法を採用する。ホモトピーとは、図２３に示すように、Ｉ＝［０，１］とした場合、位相空間Ｘ，Ｙに対する連続写像の集まりｆv：Ｘ - ＞Ｙ；ｖ∈Ｉに対して、Ｆ（ｕ，ｖ）＝ｆv（ｕ），ｕ∈Ｉが連続であるとき、ｆv及びＦはホモトピー（homotopy）であるといわれる。図２３において曲線ｆ0（ｕ）とｆ1（ｕ）はホモトープ（homotope）であると言われる。また、｛ｆv（ｕ），ｕ∈Ｉ｝を道と呼び、ｆv（０）、ｆv（１）をそれぞれ道の始点、終点という。
【００８３】
なお、パラメトリックな曲線Ｃが正規（regular）であるとは、接線方向がどこでも一意に定まることである。より具体的にいえば、微分可能であり且つ導関数が０でないことを意味する。パラメトリックなホモトピーＦが正規であるとは、ホモトピーＦを構成する道Ｆ（ｕ，ｖ）＝ｆv（ｕ），ｕ∈Ｉにおいて接線ベクトルがホモトピーと連続に移動することであるとする。この条件が成立すれば。内部曲面の任意の点に対して六面体要素を生成することができる。なお、正規でない点、すなわち特異点（singular point）が存在することは六面体要素の層が形成されないことを意味し、六面体メッシュの位相構造に矛盾が発生することを意味する。
【００８４】
次に、単一の双対輪体を境界に有する単純な内部曲面の生成方法を説明する。ここで内部曲面が単純（simple）であるとは自己交差点が一対以下であることを意味するものとする。単純な内部曲面の境界が単一の双対輪体であるとする。双対輪体の自己交差点は０又は２個でなければならず、自己交差点の型の組合せは、図２４に示すように、（ａ）自己交差点なし、（ｂ−１）及び（ｂ−２）自己交差点の型が同一、（ｃ）自己交差点の型が相異なるのいずれかである。
【００８５】
なお、内部曲面生成に要求される共通事項を整理すると、以下の内部曲面生成要件を満足するように内部曲面を生成する必要がある。
（ｉ）内部曲面は双対輪体を通過し、双対輪体にて表面にほぼ直交すること
（ii）内部曲面は滑らかであること
（iii）内部曲面は立体内部に存在すること
（iv）自己交差点を結ぶ自己交差線は滑らかであり、進行方向を複数回反転しないのが望ましい
（ｖ）内部曲面の自己交差線では、自己交差線上の点の二つの近傍（以下「自己交差線上の２近傍」と略記する）が９０度に近い角で交差するのが望ましい
（vi）内部曲面は自己交差点を結ぶ自己交差線以外に自己交差を発生しないことが望ましい
（vii）内部曲面の曲率半径の絶対値は大きい方が望ましい
【００８６】
内部曲面生成の実装においては、図２４のような補助の相手閉曲線を使用する方法に必ずしも拘泥することなく、上で述べた内部曲面生成要件を満足する内部曲面の実装法を図２４の（ａ）、（ｂ−１）及び（ｂ−２）、並びに（ｃ）の分類に従って検討する。
【００８７】
（ａ）自己交差点が存在しない場合
図２５のように双対輪体がシャープなエッジ列に沿っている場合は、内部曲面は立体表面をオフセットした曲面にする。
【００８８】
またこれ以外の場合には、図２４（ａ）に示された補助の相手閉曲線を使用する。すなわち、図２６に示すように、閉曲線を表面に直交する方向をベースに進行させて、整形すると言う工程を繰り返し、閉曲線が十分小さくなった時点で円板によって埋める「閉曲線前進法」を採用する。
【００８９】
（ｂ）自己交差点の型が同一の場合
この場合、図２４（ｂ−１）又は（ｂ−２）を採用するとすれば図２７のような相手閉曲線を選択し、さらに自己交差線と自己交差線上の２近傍の交差角を与える方式で内部曲面生成要件を満足するのが実用的である。しかしながら，これはＣＡＤで言う掃引面（sweep surface）生成と同等あり、掃引面の方が曲面生成には自然であり、且つ実用的である。なお、掃引面生成においては、掃引面の断面を与えて補間するが、このとき自己交差線と自己交差線上の断面線の交差角に注意を払う必要がある。
【００９０】
（ｃ）自己交差点の型が相異なる場合
この場合、メビウスの帯の形で正規な内部曲面を生成する。具体的なメビウスの帯の生成方法を図２８に示す。図２８では、メビウスの帯はＰ0，Ｐ1をそれぞれｆ0（０）＝ｆ1（１）；ｆ1（０）＝ｆ0（０）＝ｆ0（１）とする正規なホモトピーとして表現することができることが示されている。図２８の展開図を図２９に示す。実際にＣＡＤを用いてモデリングした例を図３０及び図３１に示す。メビウスの帯の断面の遷移過程は図３２のようになる。
【００９１】
しかしながら、端点とそのベクトルの方向のみを与えるような単純な方法では、内部曲面生成要件を満足するのは容易ではない。対応点と対応点における構成線の接ベクトルを与えて生成したメビウスの帯のパッチ構成線を図３３に、その断面遷移を図３４に示す。図３２のようなシンプルな形状に制御するのは、単純な方法では容易でないことが実験により判明している。
【００９２】
図３４（ｆ）におけるメビウスの帯のパラメタ一定線を図３５に示す。曲面が連結するとパッチ構成線が連結することが示されている。従って、多数の内部曲面の断面形状と、それを構成するパッチ構成線又はパラメタｖを指定することによって、内部曲面生成要件を満足する内部曲面を生成することができる。断面遷移は図３２によるのが適切であると考えられる。その他の方法としては、図３２の断面を繋ぐ方法もある。
【００９３】
次に、二つの双対輪体を境界にもつ単純な内部曲面生成の実装法について説明する。二つの双対輪体の自己交差点は０又は２個でなければならない。この場合、二つの双対輪体は内部曲面によって連結される。したがって、内部曲面上を滑らかに移動させることによって二つの双対輪体を併合し、一つの閉双対輪体にまとめることができる。図３６の（ａ）、（ｂ−１）、（ｂ−２）、（ｃ）は、図２４の（ａ）自己交差点なし、（ｂ−１）（ｂ−２）自己交差点の型が同一、（ｃ）自己交差点の型が相異なる場合に対応する。このように、一つの単純な閉双対輪体に変換すれば、上で述べた実装法によって正規なホモトピーを作ることができる。
【００９４】
（７）内部曲面ＳijをＳiに連結し、未計算の内部曲面の自己交差線を追加（ステップＳ１９）
内部曲面の連結は、ソリッドモデリングにおける同一境界を有するフェイスの連結として実現される。しばしばＥｕｌｅｒ演算子を使用して実現されるが、よく知られている方法であるので、ここでは詳しい説明を省略する。
【００９５】
演算はボリューム毎に順次行われ、未計算の内部曲面の自己交差線は、異なる幾何曲面間の交差計算となるので、ソリッドモデラで通常行われる曲面間の交差計算と同一であり、再帰分割法やマーチング法等で計算可能である。これはよく知られている技術なので、ここではこれ以上述べない。例えば、"Hiroaki Chiyokura, Solid Modeling with DESIGNBASE, Addison-Wesley (1988)"を参照のこと。
【００９６】
（８）内部曲面Ｓiの双対三次元胞複体Ｋ*への配置（ステップＳ２１）
図３７において、既に存在するＳiは二つのボリューム（六面体）からなっているとする。Ｓijとして円柱が加わるとする。このとき上の六面体から計算するとすれば六面体の底面と円柱が交差する。六面体の底面は下の六面体と共有されるので、次の六面体を計算するという工程が繰り返される。
【００９７】
本処理のための演算もボリューム毎に順次行われる。未計算の内部曲面の自己交差線は、異なる幾何曲面間の交差計算となるので、ソリッドモデラで通常行われる曲面間の交差計算と同一であり、再帰分割法やマーチング法等で計算可能である。これはよく知られている技術なので、ここではこれ以上述べない。
【００９８】
（９）双対三次元胞複体Ｋ*の凸性の回復（ステップＳ２３）
本発明の概要で述べた処理を実施する。
【００９９】
（１０）双対三次元胞複体Ｋ*を六面体メッシュＭHに変換（ステップＳ２５）
本発明の概要で述べた処理を実施する。
【０１００】
（１１）六面体メッシュＭHの節点の座標値の計算（ステップＳ２９）
本発明の概要で述べた処理を実施する。
以上本発明の一実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、図１３に示した機能ブロック図は必ずしも実際のプログラムモジュールに対応しない場合もある。また、上では、三つ組み回路における自己交差点の型が同一ではない場合についても処理を行う例を示したが、六面体メッシュの品質を重視する場合には、同一ではなければ内部曲面生成処理を行わないようにしても良い。このような方法を採用することにより、自己交差点の型の同一性を保持することによって高品質な六面体メッシュを得ることができるようになる。この場合、四辺形メッシュを生成し直す。その際には、自己交差点が発生しないように作り直す。また、自己交差点の型が同一化否かの判断のみ行い、当該判断結果をもって他のプログラムにて後続処理を実施するようにしてもよい。
【０１０１】
向き付け不能曲面を含む内部曲面を直接配置し、交差を求めることよって生成した簡単な双対六面体メッシュの例を図３８に示す。但し、丸は四辺形要素を表し、円板は六面体要素を表す。また、一点鎖線Ａ及び二点鎖線Ｂは閉じるので閉内部曲面を挿入して凸性を回復する必要があるが、ここでは簡明を期すために凸性回復は省略されている。
【０１０２】
また、六面体メッシュ生成装置は、コンピュータ装置であって、図３９に示すように、メモリ２５０１（記憶装置）とＣＰＵ２５０３（処理装置）とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施の形態における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。必要に応じてＣＰＵ２５０３は、表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、必要な動作を行わせる。また、処理途中のデータについては、メモリ２５０１に格納され、必要があればＨＤＤ２５０５に格納される。本発明の実施の形態では、上で述べた処理を実施するためのアプリケーション・プログラムはリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１０３】
（付記１）
立体に対して六面体メッシュを生成する方法であって、
立体表面を被覆し且つ偶数個の四辺形要素から構成される四辺形メッシュ中における、偶数個の自己交差点を有する双対輪体又は奇数個の自己交差点を有する双対輪体を連結して偶数個の自己交差点を有するように変換した双対輪体のデータを、双対輪体データ格納部に格納するステップと、
前記双対輪体データ格納部を参照して、前記双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第１の回路と、前記第１の回路が第１及び第２の基点でそれぞれ接続し且つ前記双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第２及び第３の回路とからなる三つ組み回路を特定し、三つ組み回路データ格納部に格納する三つ組み回路生成ステップと、
前記三つ組み回路データ格納部を参照して、前記三つ組み回路の第１の基点及び第２の基点における自己交差点の型の同一性を判断する同一性判断ステップと、
前記自己交差点の型の同一性の判断結果に応じて前記三つ組み回路に対応して単純内部曲面を生成し、単純内部曲面を含む内部曲面を形成して、当該内部曲面に関するデータを内部曲面データ格納部に格納するステップと、
前記内部曲面データ格納部に格納されたデータを用いて前記立体内部に前記内部曲面の配置を生成し、前記内部曲面の配置において生ずる３つの内部曲面の交点を六面体要素に変換することにより六面体メッシュを生成し、当該六面体メッシュのデータを六面体メッシュデータ格納部に格納する六面体メッシュ生成ステップと、
を含み、コンピュータにより実行される六面体メッシュ生成方法。
【０１０４】
（付記２）
前記第２及び第３の回路が隣接していることを特徴とする付記１記載の六面体メッシュ生成方法。
【０１０５】
（付記３）
前記三つ組み回路生成ステップが、
前記三つ組み回路を構成する回路についての双対輪体のデータを前記双対輪体データ格納部から除去するステップ
を含む付記１記載の六面体メッシュ生成方法。
【０１０６】
（付記４）
前記同一性判断ステップにおいて、
前記三つ組み回路における第１の基点及び第２の基点を周回する領域中の点に対する、前記三つ組み回路が作る有向曲線に関する位数の組又は自己交差点に対する向き付けされた回路の包含性を判断することを特徴とする付記１乃至３のいずれか１つ記載の六面体メッシュ生成方法。
【０１０７】
（付記５）
前記同一性判断ステップにおいて、
前記三つ組み回路を平面投影して自己交差点の型の同一性を判断する
ことを特徴とする付記１乃至４のいずれか１つ記載の六面体メッシュ生成方法。
【０１０８】
（付記６）
前記同一性判断ステップにおいて、前記三つ組み回路を構成する第１の回路及び第３の回路又は第２の部分回路のうち少なくとも一つが、唯一の他の回路と接続する場合、二つの自己交差点の型が同一であると判断されると、前記六面体メッシュ生成ステップにおいて、前記三つ組み回路に対応する単純内部曲面として向き付け可能な曲面を生成し、
前記同一性判断ステップにおいて、前記三つ組み回路を構成する第１の回路及び第３の回路又は第２の部分回路のうち少なくとも一つが、唯一の他の回路と接続する場合、二つの自己交差点の型が相異すると判断されると、前記六面体メッシュ生成ステップにおいて、前記三つ組み回路に対応する単純内部曲面として向き付け不能な曲面を生成する
ことを特徴とする付記１乃至５のいずれか１つ記載の六面体メッシュ生成方法。
【０１０９】
（付記７）
前記六面体メッシュ生成ステップが、
前記同一性判断ステップにおいて、前記三つ組み回路を構成する第１の回路及び第３の回路又は第２の部分回路に唯一の他の回路と接続する回路が存在しない場合、二つの自己交差点の型が同一であると判断されると、前記三つ組み回路を一つの回路としてみなし、前記第１の回路及び前記第３の回路又は前記第２の部分回路に接続する前記第２の回路又は前記第１の部分回路以外の２つの回路と組み合わせた新たな三つ組み回路に対応する内部曲面を生成するステップ
を含む付記１乃至６のいずれか１つ記載の六面体メッシュ生成方法。
【０１１０】
（付記８）
立体に対して六面体メッシュを生成する方法であって、
立体表面を被覆し且つ偶数個の四辺形要素から構成される四辺形メッシュ中における、偶数個の自己交差点を有する双対輪体又は奇数個の自己交差点を有する双対輪体を連結して偶数個の自己交差点を有するように変換した双対輪体のデータを、双対輪体データ格納部に格納するステップと、
前記双対輪体データ格納部を参照して、前記双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第１の回路と、当該第１の回路に第１の基点で接続する第２の回路又は第１の基点を含む回路の第１の部分回路と、前記第１の回路に第２の基点で隣接する第３の回路又は第２の基点を含む回路の第２の部分回路とからなる三つ組み回路を特定し、三つ組み回路データ格納部に格納する三つ組み回路生成ステップと、
前記三つ組み回路データ格納部を参照して、前記三つ組み回路の第１の基点及び第２の基点における自己交差点の型の同一性を判断する同一性判断ステップと、
前記同一性判断ステップにおいて前記自己交差点の型の同一性が同一であると判断された場合のみ、前記三つ組み回路に対応して単純内部曲面を生成し、単純内部曲面を含む内部曲面を形成して、当該内部曲面に関するデータを内部曲面データ格納部に格納するステップと、
前記内部曲面データ格納部に格納されたデータを用いて前記立体内部に前記内部曲面の配置を生成し、前記内部曲面の配置において生ずる３つの内部曲面の交点を六面体要素に変換することにより六面体メッシュを生成し、当該六面体メッシュのデータを六面体メッシュデータ格納部に格納する六面体メッシュ生成ステップと、
を含み、コンピュータにより実行される六面体メッシュ生成方法。
【０１１１】
（付記９）
前記同一性判断ステップにおいて前記自己交差点の型が同一ではないと判断された場合には、前記四辺形メッシュを生成し直すステップ
をさらに含む付記８記載の六面体メッシュ生成方法。
【０１１２】
（付記１０）
前記四辺形メッシュを生成し直すステップにおいて、双対輪体の自己交差点を除去するように四辺形メッシュを生成し直すことを特徴とする付記９記載の六面体メッシュ生成方法。
【０１１３】
（付記１１）
付記１乃至１０のいずれか１つ記載の六面体メッシュ生成方法をコンピュータに実行させるためのプログラム。
【０１１４】
（付記１２）
立体に対して六面体メッシュを生成するために必要なデータを生成するプログラムであって、
コンピュータに、
立体表面を被覆し且つ偶数個の四辺形要素から構成される四辺形メッシュ中における、偶数個の自己交差点を有する双対輪体又は奇数個の自己交差点を有する双対輪体を連結して偶数個の自己交差点を有するように変換した双対輪体のデータを、双対輪体データ格納部に格納するステップと、
前記双対輪体データ格納部を参照して、前記双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第１の回路と、前記第１の回路が第１及び第２の基点でそれぞれ接続し且つ前記双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第２及び第３の回路とからなる三つ組み回路を特定し、三つ組み回路データ格納部に格納する三つ組み回路生成ステップと、
前記三つ組み回路データ格納部を参照して、前記三つ組み回路の第１の基点及び第２の基点における自己交差点の型の同一性を判断し、判断結果を判断結果格納部に格納するステップと、
を実行させるためのプログラム。
【０１１５】
（付記１３）
前記判断結果格納部に格納された、前記自己交差点の型の同一性の判断結果に応じて前記三つ組み回路に対応して単純内部曲面を生成し、単純内部曲面を含む内部曲面を形成して、当該内部曲面に関するデータを内部曲面データ格納部に格納するステップと、
前記内部曲面データ格納部に格納されたデータを用いて前記立体内部に前記内部曲面の配置を生成し、前記内部曲面の配置において生ずる３つの内部曲面の交点を六面体要素に変換することにより六面体メッシュを生成し、当該六面体メッシュのデータを六面体メッシュデータ格納部に格納する六面体メッシュ生成ステップと、
をさらにコンピュータに実行させるための付記１２記載のプログラム。
【０１１６】
（付記１４）
立体に対して六面体メッシュを生成する装置であって、
立体表面を被覆し且つ偶数個の四辺形要素から構成される四辺形メッシュ中における、偶数個の自己交差点を有する双対輪体又は奇数個の自己交差点を有する双対輪体を連結して偶数個の自己交差点を有するように変換した双対輪体のデータを、双対輪体データ格納部に格納する手段と、
前記双対輪体データ格納部を参照して、前記双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第１の回路と、前記第１の回路が第１及び第２の基点でそれぞれ接続し且つ前記双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第２及び第３の回路とからなる三つ組み回路を特定し、三つ組み回路データ格納部に格納する三つ組み回路生成手段と、
前記三つ組み回路データ格納部を参照して、前記三つ組み回路の第１の基点及び第２の基点における自己交差点の型の同一性を判断する同一性判断手段と、
前記自己交差点の型の同一性の判断結果に応じて前記三つ組み回路に対応して単純内部曲面を生成し、単純内部曲面を含む内部曲面を形成して、当該内部曲面に関するデータを内部曲面データ格納部に格納する手段と、
前記内部曲面データ格納部に格納されたデータを用いて前記立体内部に前記内部曲面の配置を生成し、前記内部曲面の配置において生ずる３つの内部曲面の交点を六面体要素に変換することにより六面体メッシュを生成し、当該六面体メッシュのデータを六面体メッシュデータ格納部に格納する六面体メッシュ生成手段と、
を有する六面体メッシュ生成装置。
【０１１７】
（付記１５）
立体に対して六面体メッシュを生成する装置であって、
立体表面を被覆し且つ偶数個の四辺形要素から構成される四辺形メッシュ中における、偶数個の自己交差点を有する双対輪体又は奇数個の自己交差点を有する双対輪体を連結して偶数個の自己交差点を有するように変換した双対輪体のデータを、双対輪体データ格納部に格納する手段と、
前記双対輪体データ格納部を参照して、前記双対輪体を自己交差点で切断分離することにより得られ且つ自己交差を生じさせない部分双対輪体である第１の回路と、当該第１の回路に第１の基点で接続する第２の回路又は第１の基点を含む回路の第１の部分回路と、前記第１の回路に第２の基点で隣接する第３の回路又は第２の基点を含む回路の第２の部分回路とからなる三つ組み回路を特定し、三つ組み回路データ格納部に格納する三つ組み回路生成手段と、
前記三つ組み回路データ格納部を参照して、前記三つ組み回路の第１の基点及び第２の基点における自己交差点の型の同一性を判断する同一性判断ステップと、
前記同一性判断ステップにおいて前記自己交差点の型の同一性が同一であると判断された場合のみ、前記三つ組み回路に対応して単純内部曲面を生成し、単純内部曲面を含む内部曲面を形成して、当該内部曲面に関するデータを内部曲面データ格納部に格納する手段と、
前記内部曲面データ格納部に格納されたデータを用いて前記立体内部に前記内部曲面の配置を生成し、前記内部曲面の配置において生ずる３つの内部曲面の交点を六面体要素に変換することにより六面体メッシュを生成し、当該六面体メッシュのデータを六面体メッシュデータ格納部に格納する六面体メッシュ生成手段と、
を有する六面体メッシュ生成装置。
【図面の簡単な説明】
【０１１８】
【図１】（ａ）は構造型メッシュの一例、（ｂ）は正規型メッシュの一例、（ｃ）は非正規型メッシュの一例を示す図である。
【図２】構造型メッシュの問題点を示す図である。
【図３】（ａ）乃至（ｃ）は、ウィスカーウィービング法の説明を行うための図である。
【図４】（ａ）は自己交差点を有する双対輪体の一例を示す図、（ｂ）は（ａ）の変形を説明するための図である。
【図５】（ａ）乃至（ｅ）は、三つ組み回路の具体例を示す図である。
【図６】図５（ａ）に対応する曲面を示す図である。
【図７】図５（ｄ）に対応する曲面を示す図である。
【図８】三つ組み回路の変形例を示す図である。
【図９】（ａ）は立体の三次元胞複体表現の一例を示す図、（ｂ）は（ａ）のグラフ構造表現である。
【図１０】（ａ）及び（ｂ）は凸性のない四辺形を有する図形の一例を示す図である。
【図１１】（ａ）及び（ｂ）は凸性の回復処理を説明するための図である。
【図１２Ａ】局所的凸性回復について説明するための図である。
【図１２Ｂ】局所的凸性回復について説明するための図である。
【図１２Ｃ】凸性の回復処理を説明するための図である。
【図１３】本発明の一実施の形態に係る六面体メッシュ生成装置の機能ブロック図である。
【図１４】本発明の一実施の形態に係る第１の処理フローを示す図である。
【図１５】本発明の一実施の形態に係る第２の処理フローを示す図である。
【図１６】三次元胞複体の表現方法を説明するための図である。
【図１７】物体における体分及び面分の関係の一例を表す図である。
【図１８】ウィングドエッジ情報の一例を示す図である。
【図１９】（ａ）及び（ｂ）は双対輪体の形状を説明するための図である。
【図２０Ａ】（ａ）乃至（ｄ）は双対輪体の選択を説明するための図である。
【図２０Ｂ】生成される回路表を説明するための図である。
【図２１】三つ組み回路表生成の規則を説明するための図である。
【図２２Ａ】三つ組み回路の一例を示す図である。
【図２２Ｂ】自己交差線の交差の問題及び解決策を示す図である。
【図２３】ホモトピーを説明するための図である。
【図２４】自己交差点の型を説明するための図である。
【図２５】双対輪体を説明するための図である。
【図２６】閉曲線前進法を説明するための図である。
【図２７】自己交差点の型が同一である場合における内部曲面を説明するための図である。
【図２８】メビウスの帯の生成を説明するための図である。
【図２９】メビウスの帯の展開を説明するための図である。
【図３０】ＣＡＤによるメビウスの帯の図である。
【図３１】ＣＡＤによるメビウスの帯の図である。
【図３２】メビウスの帯の断面遷移過程を表す図である。
【図３３】メビウスの帯のパッチ構成線を表す図である。
【図３４】メビウスの帯の断面を表す図である。
【図３５】メビウスの帯のパラメタ一定線を表す図である。
【図３６】（ａ）乃至（ｃ）は双対輪体の連結を表す図である。
【図３７】内部曲面の双対三次元胞複体への配置を説明するための図である。
【図３８】双対六面体メッシュの一例を示す図である。
【図３９】コンピュータの構成図である。
【符号の説明】
【０１１９】
１  立体データ格納部    ３  四辺形メッシュ生成部
５  四辺形メッシュデータ格納部    ７  双対三次元胞複体生成部
９  双対胞複体データ格納部    １１  双対輪体テーブル生成部
１３  双対輪体テーブル格納部    １５  双対輪体組合せ表生成部
１７  双対輪体組合せ表格納部    １９  三つ組み回路表生成部
２１  三つ組み回路表格納部    ２３  単純内部曲面生成部
２５  内部曲面データ初期化部    ２７  内部曲面データ格納部
２９  内部曲面処理部    ３１  幾何演算処理部
３５  凸性回復処理部    ３７  六面体メッシュ生成部
３９  六面体メッシュデータ格納部    ４１  座標算出部
【図１】
2006201857.tif 000003
【図２】
2006201857.tif 000004
【図３】
2006201857.tif 000005
【図４】
2006201857.tif 000006
【図５】
2006201857.tif 000007
【図６】
2006201857.tif 000008
【図７】
2006201857.tif 000009
【図８】
2006201857.tif 000010
【図９】
2006201857.tif 000011
【図１０】
2006201857.tif 000012
【図１１】
2006201857.tif 000013
【図１２Ａ】
2006201857.tif 000014
【図１２Ｂ】
2006201857.tif 000015
【図１２Ｃ】
2006201857.tif 000016
【図１３】
2006201857.tif 000017
【図１４】
2006201857.tif 000018
【図１５】
2006201857.tif 000019
【図１６】
2006201857.tif 000020
【図１７】
2006201857.tif 000021
【図１８】
2006201857.tif 000022
【図１９】
2006201857.tif 000023
【図２０Ａ】
2006201857.tif 000024
【図２０Ｂ】
2006201857.tif 000025
【図２１】
2006201857.tif 000026
【図２２Ａ】
2006201857.tif 000027
【図２２Ｂ】
2006201857.tif 000028
【図２３】
2006201857.tif 000029
【図２４】
2006201857.tif 000030
【図２５】
2006201857.tif 000031
【図２６】
2006201857.tif 000032
【図２７】
2006201857.tif 000033
【図２８】
2006201857.tif 000034
【図２９】
2006201857.tif 000035
【図３２】
2006201857.tif 000036
【図３６】
2006201857.tif 000037
【図３７】
2006201857.tif 000038
【図３８】
2006201857.tif 000039
【図３９】
2006201857.tif 000040
【図３０】
2006201857.tif 000041
【図３１】
2006201857.tif 000042
【図３３】
2006201857.tif 000043
【図３４】
2006201857.tif 000044
【図３５】
2006201857.tif 000045