(57)【特許請求の範囲】
【請求項１】
ボリュームメッシュに含まれる各境界セルの位相構造と、第１のセル点生成規則に従って生成されたセル点による細分割を繰り返したときに２次元に退化する境界セルの位相構造として予め登録された特定位相構造とが一致するか否かを判定する境界セル位相構造判定手段と、
上記ボリュームメッシュに含まれる各境界セルを細分割するためのセル点を生成するセル点生成手段であって、位相構造が上記特定位相構造に一致しないと判定された境界セルを細分割するためのセル点を、上記第１のセル点生成規則に従って生成し、位相構造が上記特定位相構造に一致すると判定された境界セルを細分割するためのセル点を、上記第１のセル点生成規則とは異なる第２のセル点生成規則に従って生成するセル点生成手段と、を備えている、
ことを特徴とするボリュームメッシュ細分割装置。
【請求項２】
上記第２のセル点生成規則は、境界セルを細分割するためのセル点を、該境界セルを構成する各頂点の重み付き平均を取ることによって生成するものであり、
上記重み付き平均における重み係数は、上記ボリュームメッシュの境界に含まれる各頂点に係る重み係数の和と、上記ボリュームメッシュの内部に含まれる各頂点に係る重み係数の和とが一致するように設定されている、
ことを特徴とする請求項１に記載のボリュームメッシュ細分割装置。
【請求項３】
上記第１のセル点生成規則は、六面体状の境界セルを細分割するためのセル点を、該境界セルを構成する各頂点の単純平均を取ることによって生成するものであり、
上記特定位相構造は、（１）頂点を共有する２つの境界辺を有する境界セル、（２）頂点を共有する３つの境界辺を有する境界セル、（３）頂点を共有する１つの境界面と１つの境界辺とを有する境界セル、（４）辺を共有する２つの境界面を有する境界セル、及び（５）頂点を共有する３つの境界面を有する境界セルが有する位相構造である、
ことを特徴とする請求項１又は２に記載のボリュームメッシュ細分割装置。
【請求項４】
上記第２のセル点生成規則は、境界セルを細分割するためのセル点を、上記第１のセル点生成規則に従って生成した第１のセル点と上記第１のセル点生成規則とは異なる第３のセル点生成規則に従って生成した第２のセル点との重み付き平均を取ることによって生成するものであり、
上記重み付き平均における重み係数は、上記第１のセル点に係る重みが細分割の繰り返し回数が増えるに従って軽くなり、上記第２のセル点に係る重みが細分割の繰り返し回数が増えるに従って重くなるように設定されている、
ことを特徴とする請求項１に記載のボリュームメッシュ細分割装置。
【請求項５】
上記境界セル位相構造判定手段は、各境界セルの位相構造が上記特定位相構造と一致するか否かを、該境界セルにおける境界点、境界辺、及び境界面の配置を示す境界情報を参照して判定する、
ことを特徴とする請求項１から４までの何れか１項に記載のボリュームメッシュ細分割装置。
【請求項６】
上記ボリュームメッシュに含まれる各境界セル対の位相構造と、第１の面点生成規則に従って生成された面点による細分割を繰り返したときに境界セル間面が１次元に退化する境界セル対の位相構造として予め登録された特定位相構造とが一致するか否かを判定する境界セル対位相構造判定手段と、
上記ボリュームメッシュに含まれる各境界セル対の境界セル間面を細分割するための面点を生成する面点生成手段であって、位相構造が上記特定位相構造に一致しないと判定された境界セル対の境界セル間面を細分割するための面点を、上記第１の面点生成規則に従って生成し、位相構造が上記特定位相構造に一致すると判定された境界セル対の境界セル間面を細分割するための面点を、上記第１の面点生成規則とは異なる第２の面点生成規則に従って生成する面点生成手段と、を更に備えている、
ことを特徴とする請求項１から５までの何れか１項に記載のボリュームメッシュ細分割装置。
【請求項７】
上記境界セル対位相構造判定手段は、各境界セル対の位相構造が上記特定位相構造と一致するか否かを、該境界セル対を構成する２つの境界セルにおける境界点、境界辺、及び境界面の配置を示す境界情報を参照して判定する、
ことを特徴とする請求項６に記載のボリュームメッシュ細分割装置。
【請求項８】
境界セル位相構造判定手段とセル点生成手段とを備えたボリュームメッシュ細分割装置がボリュームメッシュを細分割するボリュームメッシュ細分割方法であって、
上記境界セル位相構造判定手段が、上記ボリュームメッシュに含まれる各境界セルの位相構造と、第１のセル点生成規則に従って生成されたセル点による細分割を繰り返したときに２次元に退化する境界セルの位相構造として予め登録された特定位相構造とが一致するか否かを判定する境界セル位相構造判定ステップと、
上記セル点生成手段が、上記ボリュームメッシュに含まれる各境界セルを細分割するためのセル点を生成するセル点生成ステップであって、位相構造が上記特定位相構造に一致しないと判定された境界セルを細分割するためのセル点を、上記第１のセル点生成規則に従って生成し、位相構造が上記特定位相構造に一致すると判定された境界セルを細分割するためのセル点を、上記第１のセル点生成規則とは異なる第２のセル点生成規則に従って生成するセル点生成ステップと、を含んでいる、
ことを特徴とするボリュームメッシュ細分割方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ボリュームメッシュを細分割するボリュームメッシュ細分割装置、及び、ボリュームメッシュ細分割方法に関する。
【背景技術】
【０００２】
物体の表面を表現するメッシュを細分割する手法として、Catmall-Clarkの表面細分割法（surface subdivision）が広く用いられている。四角形のセルからなる四角形メッシュＭが与えられた場合、Catmall-Clarkの表面細分割法では、以下のステップ１〜５を実行することによって、与えられたメッシュＭから新たなメッシュＭ’を生成する。
【０００３】
ステップ１：メッシュＭを構成する各面に対応する新頂点（以下「面点」と記載）を生成する。面Ｓに対応する面点ＳＰは、図１０（ａ）に示すように、面Ｓを構成する頂点をＶ１〜Ｖ４として、ＳＰ＝（Ｖ１＋Ｖ２＋Ｖ３＋Ｖ４）／４により与えられる。
【０００４】
ステップ２：メッシュＭを構成する各辺に対応する新頂点（以下「辺点」と記載）を生成する。辺Ｅに対応する辺点ＥＰは、図１０（ｂ）に示すように、辺Ｅを構成する２頂点をＶ１〜Ｖ２、辺Ｅを含む２つの面の各々に対応する面点（ステップＳ１にて生成されたもの）をＳＰ１〜ＳＰ２として、ＥＰ＝（Ｖ１＋Ｖ２＋ＳＰ１＋ＳＰ２）／４により与えられる。
【０００５】
ステップ３：メッシュＭを構成する各面Ｓについて、図１０（ｃ）に示すように、面Ｓに対応する面点ＳＰ（ステップ１にて生成されたもの）を始点とし、面Ｓを構成する辺Ｅ１〜Ｅ４に対応する辺点ＥＰ１〜ＥＰ４（ステップ２にて生成されたもの）の各々を終点とする４本の新辺を生成する。
【０００６】
ステップ４：メッシュＭを構成する各辺Ｅについて、図１０（ｃ）に示すように、辺Ｅに対応する辺点（ステップ２にて生成されたもの）を始点とし、辺Ｅの２つの端点を終点とする２本の新辺を生成した上で、辺Ｅを破棄する。これにより各面Ｓが４つの新面に置き換えられる。
【０００７】
ステップ５：メッシュＭを構成する各頂点を移動する。移動後の頂点Ｖ’は、図１０（ｄ）に示すように、移動前の頂点をＶ、頂点Ｖを含む面の個数をｎ（図示した例では３）、頂点Ｖを含む面Ｓ１〜Ｓｎに対応する面点ＳＰ１〜ＳＰｎ（ステップ１にて生成されたもの）の平均をＱ＝（ＳＰ１＋ＳＰ２＋…＋ＳＰｎ）／ｎ、頂点Ｖを含む辺Ｅ１〜Ｅｎの中点ＥＭ１〜ＥＭｎの平均をＲ＝（ＥＭ１＋ＥＭ２＋…＋ＥＭｎ）／ｎとして、｛Ｑ＋２Ｒ＋（ｎ−３）Ｖ｝／ｎにより与えられる。
【０００８】
これにより、ステップＳ１〜Ｓ２にて生成された各新頂点、及び、ステップＳ４にて移動された各旧頂点を頂点とし、ステップＳ３にて生成された各新辺を辺とする新たなメッシュＭ’が生成される。
【０００９】
また、物体の内部を表現するボリュームメッシュを細分割する手法として、上述したCatmall-Clarkの表面細分割法を拡張した、Catmall-Clarkのボリューム細分割法が知られている（非特許文献１参照）。六面体のセルからなる六面体メッシュＭが与えられた場合、Catmall-Clarkのボリューム細分割法では、以下のステップ１〜７を実行することによってメッシュＭを細分割する。
【００１０】
ステップ１：ボリュームメッシュＭを構成する各セルに対応する新頂点（以下「セル点」と記載）を生成する。セルＣに対応するセル点ＣＰは、図１１（ａ）に示すように、セルＣを構成する頂点をＶ１〜Ｖ８として、ＣＰ＝（Ｖ１＋Ｖ２＋…＋Ｖ８）／８により与えられる。
【００１１】
ステップ２：ボリュームメッシュＭを構成する各面に対応する新頂点（以下「面点」と記載）を生成する。面Ｓに対応する面点ＳＰは、図１１（ｂ）に示すように、面Ｓを構成する頂点Ｖ１〜Ｖ４の平均をα＝（Ｖ１＋Ｖ２＋Ｖ３＋Ｖ４）／４、面Ｓを含むセルＣ１〜Ｃ２の各々における面Ｓの対面をＳ１〜Ｓ２、面Ｓ１を構成する頂点Ｖ５〜Ｖ８及び面Ｓ２を構成する頂点Ｖ９〜Ｖ１２の平均をβ＝（Ｖ５＋Ｖ６＋…＋Ｖ１２）／８として、ＳＰ＝（３／４）α＋（１／４）βにより与えられる。
【００１２】
ステップ３：ボリュームメッシュＭを構成する各辺に対応する新頂点（以下「辺点」と記載）を生成する。辺Ｅに対応する辺点ＥＰは、図１１（ｃ）に示すように、辺Ｅの中点をＥＭ、辺Ｅを含む面の数をｎ（図示した例では４）、辺Ｅを含む面Ｓ１〜Ｓｎの各々における辺Ｅの対辺をＥ１〜Ｅｎ、辺Ｅ１〜Ｅｎの中点ＥＭ１〜ＥＭｎの平均をγ＝（ＥＭ１＋ＥＭ２＋…＋ＥＭｎ）／ｎ、辺Ｅを含むセルＣ１〜Ｃｎの各々における辺Ｅの対辺をＥＣ１〜ＥＣｎ、辺ＥＣ１〜ＥＣｎの中点ＥＣＭ１〜ＥＣＭｎの平均をη＝（ＥＣＭ１＋ＥＣＭ２＋…＋ＥＣＭｎ）／ｎとして、ＥＰ＝（９／１６）ＥＭ＋（３／８）γ＋（１／１６）ηにより与えられる。
【００１３】
ステップ４：ボリュームメッシュＭを構成する各セルＣについて、図１１（ｄ）に示すように、セルＣに対応するセル点ＣＰ（ステップ１にて生成されたもの）を始点とし、セルＣを構成する面Ｓ１〜Ｓ６に対応する面点ＳＰ１〜ＳＰ６（ステップ２にて生成されたもの）の各々を終点とする６本の新辺を生成する。
【００１４】
ステップ５：ボリュームメッシュＭを構成する各面Ｓについて、図１１（ｅ）に示すように、面Ｓに対応する面点ＳＰ（ステップ２にて生成されたもの）を始点とし、面Ｓを構成する辺Ｅ１〜Ｅ４に対応する辺点ＥＰ１〜ＥＰ４（ステップ３にて生成されたもの）の各々を終点とする４本の新辺を生成する。
【００１５】
ステップ６：ボリュームメッシュＭを構成する各辺Ｅについて、図１１（ｅ）に示すように、辺Ｅに対応する辺点ＥＰ（ステップ３にて生成されたもの）を始点とし、辺Ｅの２つの端点を終点とする２本の新辺を生成した上で、辺Ｅを破棄する。これにより、各面Ｓが４つの新面に置き換えられ、各セルＣが８つの新セルに置き換えられる。
【００１６】
ステップ７：ボリュームメッシュを構成する各頂点を移動する。移動後の頂点Ｖ’は、図１１（ｆ）に示すように、移動前の頂点をＶ、頂点Ｖに隣接する頂点Ｖ１〜Ｖｎの平均をＰ＝（Ｖ１＋Ｖ２＋…＋Ｖｎ）／ｎ（図示した例ではｎ＝６）、頂点Ｖを含む面Ｓ１〜Ｓｋの各々におけるＶの対点ＶＳ１〜ＶＳｋの平均をＱ＝（ＶＳ１＋ＶＳ２＋…＋ＶＳｋ）／ｋ（図示した例ではｋ＝１２）、頂点Ｖを含むセルＣ１〜Ｃｊの各々におけるＶの対点ＶＣ１〜ＶＣｊの平均をＲ＝（ＶＣ１＋ＶＣ２＋…＋ＶＣｊ）／ｊ（図示した例ではｊ＝８）として、Ｖ’＝（２７／６４）Ｖ＋（２７／６４）Ｐ＋（９／６４）Ｑ＋（１／６４）Ｒにより与えられる。
【００１７】
なお、ボリュームメッシュＭをCatmall-Clarkのボリューム細分割法を用いて細分割する際、ボリュームメッシュＭの表面をCatmall-Clarkの表面細分割法を用いて細分割し、前者の細分割により得られた境界点（ボリュームメッシュを構成する頂点のうち、ボリュームメッシュの境界上にある頂点）を後者の細分割により得られた境界点で上書きする。あるいは、ボリュームメッシュＭの表面に対してCatmall-Clarkの表面細分割法を適用し、ボリュームメッシュＭの内部に対して上述した各ステップを適用する。何れの場合であっても、ボリュームメッシュＭの表面に対してCatmall-Clarkの表面細分割法が適用されるので、ボリュームメッシュＭをｎ回細分割することにより得られるボリュームメッシュＭｎがｎ→∞の極限で滑らかな表面をもつことが保証される。
【先行技術文献】
【非特許文献】
【００１８】
【非特許文献１】Bajaj,C.,etal.,"A Subdivision scheme for hexahedral Meshes",Visual Computer 18,2002,343-356
【発明の概要】
【発明が解決しようとする課題】
【００１９】
しかしながら、従来のボリューム細分割法には、平面的な境界セル（ボリュームメッシュ細分割法を繰り返し適用したときに２次元に退化する境界セル）を生じるという問題があった。
【００２０】
ボリュームメッシュ細分割法は、内部セルのヤコビアンを上昇させるという、有限要素法にとって好適な性質を有している。しかしながら、細分割したボリュームメッシュに平面的なセルが含まれていると、そのボリュームメッシュを有限要素法に利用することができない。したがって、従来のボリューム細分割法では、有限要素法に利用可能なボリュームメッシュを生成することができない。
【００２１】
なお、「境界セル」とは、少なくとも１つの辺又は面がボリュームメッシュの境界を構成するセルのことを指す。
【００２２】
また、境界セルＣが「平面的な境界セル」であるとは、（１）ボリューム細分割法を繰り返し適用することによって、その境界セルＣと同一の位相構造を有する（境界セルＣの位相構造を継承する）境界セルの縮小列Ｃ→Ｃ（１）→Ｃ（２）→…→Ｃ（ｋ）→…を作ることができ、かつ、（２）境界セルＣ（ｋ）のヤコビアンがｋ→∞の極限で０になることを指す。
【００２３】
Catmall-Clarkのボリューム細分割法を用いた場合に平面的な境界セルが生じ得ることを、図１２を参照して説明する。図１２（ａ）は、境界セルCの斜視図である。この境界セルＣは、「頂点を共有する３つの面が境界面になる」という位相構造を有している。このような位相構造を有する境界セルは、以下に説明するように平面的な境界セルになる。
【００２４】
境界セルＣにCatmall-Clarkのボリューム細分割法を適用すると、８個の小さな境界セルが得られる。このうち、頂点ｖ０を移動することにより得られた頂点ｖ０（１）を含む境界セルは、頂点ｖ０（１）を共有する３つの境界面を有するという境界セルＣの位相構造を継承した境界セルとなる。この境界セルをＣ（１）とし、再びCatmall-Clarkのボリューム細分割法を適用すると、８個の更に小さな境界セルが得られる。このうち、頂点ｖ０（１）を移動することにより得られた頂点ｖ０（２）を含む境界セルは、頂点ｖ０（２）を共有する３つの境界面を有するという境界セルＣの位相構造を継承した境界セルとなる。このようにして、Catmall-Clarkのボリューム細分割法を繰り返し適用すれば、頂点を共有する３つの境界面を有するという境界セルＣの位相構造を継承する境界セルの縮小列Ｃ→Ｃ（１）→Ｃ（２）→…→Ｃ（ｋ）→…を作ることができる。この縮小列を構成する境界セルＣ（ｋ）のヤコビアンは、ｋ→∞の極限で０になる。
【００２５】
実際、境界セルＣ（ｋ）の８つの頂点のうち、ボリュームメッシュＭの表面上に配置された７つの頂点ｖ１（ｋ），ｖ２（ｋ），ｖ３（ｋ），ｖ４（ｋ），ｖ５（ｋ），ｖ７（ｋ），ｖ０（ｋ）は、細分割に際してCatmall-Clarkの表面細分割法の適用を受ける。したがって、これら７つの頂点ｖ１（ｋ），ｖ２（ｋ），ｖ３（ｋ），ｖ４（ｋ），ｖ５（ｋ），ｖ７（ｋ），ｖ０（ｋ）は、図１２（ｂ）に示すように、ｋ→∞の極限で同一平面上に配置される。これは、Catmall-Clarkの表面細分割法がｋ→∞の極限で滑らかな表面を生成するアルゴリズムだからである。
【００２６】
このとき、これら７つの頂点の間に、式（１）の関係が成り立つ。
【００２７】
ｖ０（ｋ）＋ｖ１（ｋ）＋ｖ２（ｋ）＋ｖ３（ｋ）＋ｖ４（ｋ）
＋ｖ５（ｋ）＋ｖ７（ｋ）＝７ｖ０（ｋ）                          …  （１）
これら７つの頂点ｖ１（ｋ），ｖ２（ｋ），ｖ３（ｋ），ｖ４（ｋ），ｖ５（ｋ），ｖ７（ｋ），ｖ０（ｋ）が同一平面上にある状態でCatmall-Clarkのボリューム細分割法を適用すると、７つの頂点ｖ１（ｋ＋１），ｖ２（ｋ＋１），ｖ３（ｋ＋１），ｖ４（ｋ＋１），ｖ５（ｋ＋１），ｖ７（ｋ＋１），ｖ０（ｋ＋１）と共に境界セルＣ（ｋ＋１）を構成する頂点ｖ６（ｋ＋１）は、Catmall-Clarkのボリューム細分割法におけるセル点の生成規則に従って、式（２）により与えられる。
【００２８】
ｖ６（ｋ＋１）＝（ｖ０（ｋ）＋ｖ１（ｋ）＋ｖ２（ｋ）＋ｖ３（ｋ）
＋ｖ４（ｋ）＋ｖ５（ｋ）＋ｖ７（ｋ）＋ｖ６（ｋ））／８            …  （２）
（１）式と（２）式とを合わせると、（３）式の関係が得られる。
【００２９】
ｖ６（ｋ＋１）−ｖ０（ｋ）＝｛ｖ６（ｋ）−ｖ０（ｋ）｝／８  …（３）
ｋ→∞の極限ではｖ０（ｋ）＝ｖ０（ｋ＋１）が成り立つため、（３）式は、以下のように書き換えることができる。
【００３０】
ｖ６（ｋ＋１）−ｖ０（ｋ＋１）＝｛ｖ６（ｋ）−ｖ０（ｋ）｝／８  …（３’）
（３’）式は、境界セルＣ（ｋ）の「厚み」に相当する対角線（ｖ０（ｋ），ｖ６（ｋ））の長さが（１／８）ｋのオーダーで縮小することを示している。これに対して、ボリュームメッシュＭの表面上にある境界セルＣ（ｋ）の各境界辺（境界セルＣ（ｋ）を構成する辺のうち、ボリュームメッシュＭの表面上にある辺）の長さは、（１／２）ｋのオーダーで縮小する。したがって、境界セルＣ（ｋ）は、ｋ→∞の極限で２次元に退化する。すなわち、境界セルＣ（ｋ）のヤコビアンは、ｋ→∞の極限で０になる。
【００３１】
また、従来のボリューム細分割法では、上述した平面的な境界セルに加えて、直線的な境界セル間面（ボリュームメッシュ細分割法を繰り返し適用したときに１次元に退化する境界セル間面）も生じ得る。細分割したボリュームメッシュに直線的な境界セル間面が含まれていると、やはり、そのボリュームメッシュを有限要素法に利用することができない。
【００３２】
なお、「境界セル間面」とは、互いに隣接する２つの境界セルからなる境界セル対に挟まれた面のことを指す。境界セル間面は、それ自身が境界を構成する「境界面」とは異なる概念であるので留意されたい。
【００３３】
また、境界セル対（Ｃ１，Ｃ２）の境界セル間面Ｓが「直線的な境界セル間面」であるとは、ボリューム細分割法を繰り返し適用することによって、境界セル対（Ｃ１，Ｃ２）と同一の位相構造を有する（境界セル対（Ｃ１，Ｃ２）の位相構造を継承する）境界セル対の縮小列（Ｃ１，Ｃ２）→（Ｃ１（１），Ｃ２（１））→（Ｃ１（２），Ｃ２（２））→…→（Ｃ１（ｋ），Ｃ２（ｋ））→…を作ることができ、かつ、（２）境界セル対（Ｃ１（ｋ），Ｃ２（ｋ））に挟まれた境界セル間面Ｓ（ｋ）のヤコビアンがｋ→∞の極限で０になることを指す。
【００３４】
Catmall-Clarkのボリューム細分割法を用いた場合に直線的な境界セル間面が生じ得ることを、図１３を参照して説明する。図１３（ａ）は、互いに隣接する２つの境界セルＣ１，Ｃ２からなる境界セル対（Ｃ１，Ｃ２）を示す斜視図である。この境界セル対（Ｃ１，Ｃ２）は、「境界セル間面、及び、境界セル間面に対向する２つの面が何れも２つの境界辺を含む」という位相構造を有している。このような位相構造を有する境界セル対（Ｃ１，Ｃ２）に挟まれた境界セル間面Ｓは、以下に示すように、直線的な境界セル間面になる。
【００３５】
境界セル対（Ｃ１，Ｃ２）にCatmall-Clarkのボリューム細分割法を適用すると、１６個の小さな境界セルが得られる。このうち、頂点ｖ０を移動することにより得られた頂点ｖ０（１）を含む２つの境界セルは、境界セル間面、及び、境界セル間面に対向する２つの面が何れも２つの境界辺を含むという境界セル対（Ｃ１，Ｃ２）の位相構造を継承した境界セル対を構成する。この境界セル対を（Ｃ１（１），Ｃ２（１））とし、再びCatmall-Clarkのボリューム細分割法を適用すると、１６個の更に小さな境界セルが得られる。このうち、頂点ｖ０（１）を移動することにより得られた頂点ｖ０（２）を含む２つの境界セルは、境界セル間面、及び、境界セル間面に対向する２つの面が何れも２つの境界辺を含むという境界セル対（Ｃ１，Ｃ２）の位相構造を継承した境界セル対を構成する。このようにして、Catmall-Clarkのボリューム細分割法を繰り返し適用すれば、境界セル間面、及び、境界セル間面に対向する２つの面が何れも２つの境界辺を含むという境界セル対（Ｃ１，Ｃ２）の位相構造を継承する境界セルの縮小列（Ｃ１，Ｃ２）→（Ｃ１（１），Ｃ２（１））→（Ｃ１（２），Ｃ２（２））→…→（Ｃ１（ｋ），Ｃ２（ｋ））→…を作ることができる。この縮小列を構成する境界セル対（Ｃ１（ｋ），Ｃ２（ｋ））間の境界面Ｓ（ｋ）のヤコビアンは、ｋ→∞の極限で０になる。
【００３６】
実際、境界セル対（Ｃ１，Ｃ２）の１２個の頂点のうち、ボリュームメッシュＭの表面上に配置された９つの頂点ｖ０（ｋ），ｖ１（ｋ），ｖ３（ｋ），ｖ４（ｋ），ｖ５（ｋ），ｖ７（ｋ），ｖ８（ｋ），ｖ９（ｋ），ｖ１１（ｋ）は、細分割に際してCatmall-Clarkの表面細分割法の適用を受ける。したがって、これら９つの頂点ｖ０（ｋ），ｖ１（ｋ），ｖ３（ｋ），ｖ４（ｋ），ｖ５（ｋ），ｖ７（ｋ），ｖ８（ｋ），ｖ９（ｋ），ｖ１１（ｋ）は、ｋ→∞の極限で同一平面上に配置される。この際、３つの頂点ｖ０（ｋ），ｖ１（ｋ），ｖ３（ｋ）は同一直線上に配置される。これは、Catmall-Clarkの表面細分割法がｋ→∞の極限で滑らかな表面を生成するアルゴリズムだからである。
【００３７】
このとき、これら９つの頂点の間に、以下の関係式が成り立つ。
【００３８】
ｖ０（ｋ）＋ｖ１（ｋ）＋ｖ３（ｋ）＝３ｖ０（ｋ）                …  （４ａ）
ｖ４（ｋ）＋ｖ５（ｋ）＋ｖ７（ｋ）＝３ｖ４（ｋ）                …  （４ｂ）
ｖ８（ｋ）＋ｖ９（ｋ）＋ｖ１１（ｋ）＝３ｖ８（ｋ）              …  （４ｃ）
ｖ０（ｋ）＋ｖ４（ｋ）＋ｖ８（ｋ）＝３ｖ０（ｋ）                …  （４ｄ）
また、これら９つの頂点以外の頂点ｖ２（ｋ），ｖ６（ｋ），ｖ１０（ｋ）についても、以下の関係が成り立つ。
【００３９】
ｖ２（ｋ）＋ｖ６（ｋ）＋ｖ１０（ｋ）＝３ｖ２（ｋ）              …  （４ｅ）
これら９つの頂点ｖ０（ｋ），ｖ１（ｋ），ｖ３（ｋ），ｖ４（ｋ），ｖ５（ｋ），ｖ７（ｋ），ｖ８（ｋ），ｖ９（ｋ），ｖ１１（ｋ）が同一平面上にある状態でCatmall-Clarkのボリューム細分割法を適用すると、３つの頂点ｖ０（ｋ＋１），ｖ１（ｋ＋１），ｖ３（ｋ＋１）と共に境界セル間面Ｓ（ｋ＋１）を構成する頂点ｖ２（ｋ＋１）は、Catmall-Clarkのボリューム細分割法における面点の生成規則に従って、式（６）により与えられる。
【００４０】
ｖ２（ｋ＋１）＝３／１６（ｖ０（ｋ）＋ｖ１（ｋ）＋ｖ２（ｋ）＋ｖ３（ｋ））
＋１／３２（ｖ４（ｋ）＋ｖ５（ｋ）＋ｖ６（ｋ）＋ｖ７（ｋ）
＋ｖ８（ｋ）＋ｖ９（ｋ）＋ｖ１０（ｋ）＋ｖ１１（ｋ））  …（５）
（４ａ）〜（４ｅ）式と（５）式とを合わせると、（６）式の関係が得られる。
【００４１】
ｖ２（ｋ＋１）−ｖ０（ｋ）＝｛ｖ２（ｋ）−ｖ０（ｋ）｝／４            …（６）
ｋ→∞の極限ではｖ０（ｋ）＝ｖ０（ｋ＋１）が成り立つため、（６）式は、以下のように書き換えることができる。
【００４２】
ｖ２（ｋ＋１）−ｖ０（ｋ＋１）＝｛ｖ２（ｋ）−ｖ０（ｋ）｝／４      …（６’）
（６’）式は、境界セル間面Ｓ（ｋ）の「厚み」に相当する対角線（ｖ０（ｋ），ｖ２（ｋ））の長さが（１／４）ｋのオーダーで縮小することを示している。これに対して、ボリュームメッシュＭの表面上にある境界セル間面Ｓ（ｋ）の各境界辺（境界セル間面Ｓ（ｋ）を構成する辺のうち、ボリュームメッシュＭの表面上にある辺）の長さは、（１／２）ｋのオーダーで縮小する。したがって、境界セル間面Ｓ（ｋ）は、ｋ→∞の極限で１次元に退化する。すなわち、境界セル間面Ｓ（ｋ）のヤコビアンは、ｋ→∞の極限で０になる。
【００４３】
本発明は上記の課題に鑑みてなされたものであり、その目的は、繰り返し適用しても平面的なセルを生じ難いボリューム細分割装置を実現することにある。
【課題を解決するための手段】
【００４４】
上記課題を解決するために、本発明に係るボリューム細分割装置は、ボリュームメッシュに含まれる各境界セルの位相構造と、第１のセル点生成規則に従って生成されたセル点による細分割を繰り返したときに２次元に退化する境界セルの位相構造として予め登録された特定位相構造とが一致するか否かを判定する境界セル位相構造判定手段と、上記ボリュームメッシュに含まれる各境界セルを細分割するためのセル点を生成するセル点生成手段であって、位相構造が上記特定位相構造に一致しないと判定された境界セルを細分割するためのセル点を、上記第１のセル点生成規則に従って生成し、位相構造が上記特定位相構造に一致すると判定された境界セルを細分割するためのセル点を、上記第１のセル点生成規則とは異なる第２のセル点生成規則に従って生成するセル点生成手段と、を備えている。
【００４５】
また、上記の課題を解決するために、本発明に係るボリューム細分割方法は、ボリュームメッシュに含まれる各境界セルの位相構造と、第１のセル点生成規則に従って生成されたセル点による細分割を繰り返したときに２次元に退化する境界セルの位相構造として予め登録された特定位相構造とが一致するか否かを判定する境界セル位相構造判定ステップと、上記ボリュームメッシュに含まれる各境界セルを細分割するためのセル点を生成するセル点生成ステップであって、位相構造が上記特定位相構造に一致しないと判定された境界セルを細分割するためのセル点を、上記第１の生成規則に従って生成し、位相構造が上記特定位相構造に一致すると判定された境界セルを細分割するためのセル点を、上記第１の生成規則とは異なる第２の生成規則に従って生成するセル点生成ステップと、を含んでいる。
【００４６】
上記の構成によれば、第１のセル点生成規則に従って生成されたセル点による細分割を繰り返したときに２次元に退化する位相構造を有する境界セルは、第１のセル点生成規則とは異なる第２のセル点生成規則に従って生成したセル点により細分割される。したがって、第１のセル点生成規則に従って生成したセル点による細分割を繰り返すことにより境界セルが２次元に退化することを回避することができる。すなわち、繰り返し適用しても平面的なセルを生じ難いボリューム細分割を実現することができる。
【００４７】
本発明に係るボリュームメッシュ細分割装置において、上記第２のセル点生成規則は、境界セルを細分割するためのセル点を、該境界セルを構成する各頂点の重み付き平均を取ることによって生成するものであり、上記重み付き平均における重み係数は、上記ボリュームメッシュの境界に含まれる各頂点に係る重み係数の和と、上記ボリュームメッシュの内部に含まれる各頂点に係る重み係数の和とが一致するように設定されている、ことが好ましい。
【００４８】
上記の構成によれば、境界セルにおいて、ボリュームメッシュの表面上に配置された頂点間の距離が０に収束する速さと、ボリュームメッシュの表面からボリュームメッシュの内部に配置された頂点までの距離が０に収束する速さとが均衡するので、境界セルが２次元に退化することをより確実に回避することができる。
【００４９】
本発明に係るボリューム細分割装置において、上記第１のセル点生成規則は、六面体状の境界セルを細分割するためのセル点を、該境界セルを構成する各頂点の単純平均を取ることによって生成するものであり、上記特定位相構造は、（１）頂点を共有する２つの境界辺を有する境界セル、（２）頂点を共有する３つの境界辺を有する境界セル、（３）頂点を共有する１つの境界面と１つの境界辺とを有する境界セル、（４）辺を共有する２つの境界面を有する境界セル、及び（５）頂点を共有する３つの境界面を有する境界セルが有する位相構造である、ことが好ましい。
【００５０】
上記の構成によれば、繰り返し適用しても平面的なセルを生じ難いCatmall-Clarkのボリューム細分割を実現することができる。
【００５１】
本発明に係るボリュームメッシュ細分割装置において、上記第２のセル点生成規則は、境界セルを細分割するためのセル点を、上記第１の生成規則に従って生成した第１のセル点と上記第１生成規則とは異なる第３の生成規則に従って生成した第２のセル点との重み付き平均を取ることによって生成するものであり、上記重み付き平均における重み係数は、上記第１のセル点に係る重みが細分割の繰り返し回数が増えるに従って軽くなり、上記第２のセル点に係る重みが細分割の繰り返し回数が増えるに従って重くなるように設定されている、ことが好ましい。
【００５２】
上記第１の生成規則を用いた細分割が繰り返し回数が小さいときに精度が良いものであり、かつ、上記第３の生成規則を用いた細分割が繰り返し回数が大きいときに精度が良いものであるときに、上記の構成によれば、細分割の繰り返し回数が小さいときであっても、細分割の繰り返し回数が大きいときであっても、精度のよいボリューム細分割を実現することができる。
【００５３】
なお、上記境界セル位相構造判定手段は、各境界セルの位相構造が上記特定位相構造と一致するか否かを、例えば、該境界セルにおける境界点、境界辺、及び境界面の配置を示す境界情報を参照して判定することができる。
【００５４】
本発明に係るボリュームメッシュ細分割装置は、上記ボリュームメッシュに含まれる各境界セル対の位相構造と、第１の面点生成規則に従って生成された面点による細分割を繰り返したときに境界セル間面が１次元に退化する境界セル対の位相構造として予め登録された特定位相構造とが一致するか否かを判定する境界セル対位相構造判定手段と、上記ボリュームメッシュに含まれる各境界セル対の境界セル間面を細分割するための面点を生成する面点生成手段であって、位相構造が上記特定位相構造に一致しないと判定された境界セル対の境界セル間面を細分割するための面点を、上記第１の面点生成規則に従って生成し、位相構造が上記特定位相構造に一致すると判定された境界セル対の境界セル間面を細分割するための面点を、上記第１の面点生成規則とは異なる第２の面点生成規則に従って生成する面点生成手段と、を更に備えている、ことが好ましい。
【００５５】
上記の構成によれば、第１の面点生成規則に従って生成された面点による細分割を繰り返したときに１次元に退化する位相構造を有する境界セル間面は、第１の面点生成規則とは異なる第２の面点生成規則に従って生成した面点により細分割される。したがって、第１の面点生成規則に従って生成した面点による細分割を繰り返すことにより境界セル間面が１次元に退化することを回避することができる。すなわち、繰り返し適用しても直線的な面を生じ難いボリューム細分割を実現することができる。
【００５６】
なお、上記境界セル対位相構造判定手段は、各境界セル対の位相構造が上記特定位相構造と一致するか否かを、例えば、該境界セル対を構成する２つの境界セルにおける境界点、境界辺、及び境界面の配置を示す境界情報を参照して判定することができる。
【発明の効果】
【００５７】
本発明によれば、繰り返し適用しても平面的なセルを生じ難いボリューム細分割を行うことができる。
【図面の簡単な説明】
【００５８】
【図１】本発明の実施形態に係るボリュームメッシュ細分割装置の構成を示すブロック図である。
【図２】図１に示すボリュームメッシュ細分割装置の動作を示すフローチャートである。
【図３】図１に示すボリュームメッシュ細分割装置として機能するコンピュータのブロック図である。
【図４】ボリュームメッシュに含まれる境界セルのうち、境界面を有さないタイプの境界セルを例示する図である。（ａ）は、境界辺を有さないものを示しており、（ｂ）は、１つの境界辺を有するものを示しており、（ｃ）は、頂点を共有しない２つの境界辺であって、何れかの面において互いに対向する２つの境界辺を有するものを示しており、（ｄ）は、頂点を共有する２つの境界辺を有するものを示しており、（ｅ）は、頂点を共有しない２つの境界辺であって、何れかの面において互いに対向する２つの境界辺を有するものを示しており、（ｆ）は、何れかの頂点を共有する３つの境界辺を有するものを示している。
【図５】ボリュームメッシュに含まれる境界セルのうち、単一の境界面を有するタイプの境界セルを例示する図である。（ａ）は、境界辺を有さないものを示しており、（ｂ）は、境界面と頂点を共有する１つの境界辺を有するものを示しており、（ｃ）は、境界面と頂点を共有しない１つの境界辺を有するものを示している。
【図６】ボリュームメッシュに含まれる境界セルのうち、２つの境界面を有するタイプの境界セルを例示する図である。（ａ）は、２つの境界面が１つの境界辺を共有しており、境界面の境界以外に境界辺を含まないものを示しており、（ｂ）は、２つの境界面が境界辺を共有していないものを示しており、（ｃ）は、２つの境界面が１つの境界辺を共有しており、２つの境界面の何れかと頂点を共有する１つの境界辺を有するものを示しており、（ｄ）は、２つの境界面が１つの境界辺を共有しており、２つの境界面の何れとも頂点を共有しない１つの境界辺を有するものを示している。
【図７】ボリュームメッシュに含まれる境界セルのうち、３つの境界面を有するタイプの境界セルを例示する図である。（ａ）は、３つの境界面全てによって共有される頂点を有するものを示しており、（ｂ）は、３つの境界面全てによって共有される頂点を有しないものを示している。
【図８】本発明の実施形態に係るボリュームメッシュ細分割装置を用いた実験結果の例を説明するための図であって、（ａ）は、実験に用いた初期ボリュームメッシュを示しており、（ｂ）は、ボリューム細分割を複数ステップ行った後の、コーナー部分についてのボリュームメッシュの状態を示しており、（ｃ）は、Catmall-Clarkのボリューム細分割法、および本発明に係るボリューム細分割法のそれぞれについて、各ステップにおけるスケールドヤコビアンの値を示している。
【図９】本発明の実施形態に係るボリュームメッシュ細分割装置を用いた実験結果の他の例を説明するための図であって、（ａ）は、実験に用いた初期ボリュームメッシュを示しており、（ｂ）は、ボリューム細分割を複数ステップ行った後の、コーナー部分についてのボリュームメッシュの状態を示しており、（ｃ）は、Catmall-Clarkのボリューム細分割法、および本発明に係るボリューム細分割法のそれぞれについて、各ステップにおけるスケールドヤコビアンの値を示している。
【図１０】従来知られているCatmall-Clarkの表面細分割法を説明するための図であって、（ａ）は、当該表面細分割法によって生成される面点を示しており、（ｂ）は、当該表面細分割法によって生成される辺点を示しており、（ｃ）は、当該表面細分割法によって生成される新辺を示しており、（ｄ）は、当該表面細分割法によって生成される移動後の頂点を示している。
【図１１】従来知られているCatmall-Clarkのボリューム細分割法を説明するための図であって、（ａ）は、当該ボリューム細分割法によって生成されるセル点を示しており、（ｂ）は、当該ボリューム細分割法によって生成される面点を示しており、（ｃ）は、当該ボリューム細分割法によって生成される辺点を示しており、（ｄ）および（ｅ）は、当該ボリューム細分割法によって生成される新辺を示しており、（ｆ）は、当該ボリューム細分割法によって生成される移動後の頂点を示している。
【図１２】Catmall-Clarkのボリューム細分割法によって生成される平面的な境界セルについて説明するための図であって、（ａ）は、Catmall-Clarkのボリューム細分割法により生成される縮小列における各境界セルの頂点を示しており、（ｂ）は、ｋ番目のステップ終了後の各頂点と、ｋ＋１番目のステップ終了後の各頂点とを模式的に示す図である。
【図１３】ボリュームメッシュに含まれる境界セル対のうち、境界セル間面Ｓが２つの境界辺を有する場合を例示する図である。（ａ）は、境界セル間面の２つの対面Ｓ１，Ｓ２の両方が２つの境界辺を有するものを例示しており、（ｂ）は、境界セル間面の２つの対面の片方が境界面であり、もう片方が２つの境界辺を有するものの例を示しており、（ｃ）は、境界セル間面の２つの対面の片方が２つの境界辺を有しており、もう片方が１つの境界辺を有するものの例を示しており、（ｄ）は、境界セル間面の２つの対面の片方が１つの境界辺を有しており、もう片方が境界辺を有しないものの例を示しており、（ｅ）は、境界セル間面の２つの対面の両方が境界辺を有していないものの例を示しており、（ｆ）は、境界セル間面の２つの対面の片方が２つの境界辺を有しており、もう片方が境界辺を有しないものの例を示している。
【発明を実施するための形態】
【００５９】
本実施形態に係るボリュームメッシュ細分割装置は、Catmall-Clarkのボリューム細分割法を改良したボリューム細分割法を用いて、六面体セルからなるボリュームメッシュを細分割するものである。主な改良点は以下の２点である。
【００６０】
改良点１：Catmall-Clarkのボリューム細分割法において、どのような位相構造を有する境界セルが平面的になるかを特定したうえで、そのような位相構造を有する境界セルに適用するセル点の生成規則を、従来の生成規則とは異なる生成規則に変更する。これにより、与えられたボリュームメッシュに含まれている平面的な境界セルが２次元に退化することを防止する。
【００６１】
改良点２：Catmall-Clarkのボリューム細分割法において、どのような位相構造を有する境界セル対の境界セル間面が直線的になるかを特定したうえで、そのような位相構造を有する境界セル対の境界セル間面に適用する面点の生成規則を、従来の生成規則とは異なる生成規則に変更する。これにより、与えられたボリュームメッシュに含まれている直線的な境界セル間面が１次元に退化することを防止する。
【００６２】
〔平面的な境界セル〕
本実施形態に係るボリュームメッシュ細分割装置の説明に入る前に、まず、Catmall-Clarkのボリューム細分割法において、どのような位相構造を有する境界セルが平面的なセルになるかについて説明する。
【００６３】
ボリュームメッシュに含まれる境界セルは、（１）境界面を有さないタイプ、（２）単一の境界面を有するタイプ、（３）２つの境界面を有するタイプ、（４）３つの境界面を有するタイプに大別される。以下、これらのタイプの各々について、どのような位相構造を有する境界セルが平面的になるかを述べる。
【００６４】
（１）境界面を有さないタイプ
まず、境界面を有さないタイプの境界セルについて、図４を参照して説明する。図４は、境界面を有さないタイプの境界セルを例示した図である。
【００６５】
境界面を有さないタイプの境界セルの位相構造には、図４に示すように、（ａ）境界辺を有さないもの、（ｂ）１つの境界辺を有するもの、（ｃ）頂点を共有しない２つの境界辺であって、何れかの面において互いに対向する２つの境界辺を有するもの、（ｄ）頂点を共有する２つの境界辺を有するもの、（ｅ）頂点を共有しない２つの境界辺であって、何れかの面において互いに対向する２つの境界辺を有するもの、（ｆ）何れかの頂点を共有する３つの境界辺を有するものなどがある。
【００６６】
これらの境界セルのうち、図４（ｄ）に示す位相構造（頂点を共有する２つの境界辺を有する）をもつ境界セル、及び、図４（ｆ）に示す位相構造（何れかの頂点を共有する３つの境界辺を有する）をもつ境界セルは、図１２に示した位相構造をもつ境界セルと同様、平面的な境界セルであることが確かめられる。
【００６７】
一方、図４（ｃ）及び図４（ｅ）に示す位相構造（頂点を共有しない２つの境界辺を有する）をもつ境界セルは、消失する境界セルであることが確かめられる。ここで、ある境界セルが「消失する境界セル」であるとは、ボリューム細分割法を繰り返し適用することによって、その境界セルの位相構造を継承する境界セルの縮小列を構成し得ないことを指す。
【００６８】
また、図４（ａ）に示す位相構造（境界辺を有さない）をもつ境界セル、及び、図４（ｂ）に示す位相構造（１つの境界辺を有する）をもつ境界セルは、立体的な境界セルであることが確かめられる。ここで、ある境界セルが「立体的な境界セル」であるとは、ボリューム細分割法を繰り返し適用することによって、その境界セルの位相構造を継承する境界セルの縮小列Ｃ→Ｃ（１）→Ｃ（２）→…→Ｃ（ｋ）→…を構成することができ、かつ、（２）境界セルＣ（ｋ）のヤコビアンが、ｋ→∞の極限で０でない値をもつことを指す。
【００６９】
（２）単一の境界面を有するタイプ
次に、単一の境界面を有するタイプの境界セルについて、図５を参照して説明する。図５は、単一の境界面を有するタイプの境界セルを例示した図である。
【００７０】
単一の境界面を有するタイプの境界セルの位相構造には、図５に示すように、（ａ）境界辺を有さないもの、（ｂ）境界面と頂点を共有する１つの境界辺を有するもの、（ｃ）境界面と頂点を共有しない１つの境界辺を有するものなどがある。また、２つ以上の境界辺を有するもの（不図示）もある。
【００７１】
これらの境界セルのうち、図５（ｂ）に示す位相構造（境界面と頂点を共有する１つの境界辺を有する）をもつ境界セルは、平面的な境界セルであることが確かめられる。一方、図５（ａ）に示す位相構造（境界辺を有さない）をもつ境界セルは、立体的な境界セルであることが確かめられる。また、図５（ｃ）に示す位相構造（境界面と頂点を共有しない１つの境界辺を有する）をもつ境界セルは、消失する境界セルであることが確かめられる。なお、「２つ以上の境界辺を有する」という位相構造をもつ境界セルも、境界辺の配置を問わず消失する境界セルである。
【００７２】
（３）２つの境界面を有するタイプ
次に、２つの境界面を有するタイプの境界セルについて、図６を用いて説明する。図６は、２つの境界面を有するタイプの境界セルを例示した図である。
【００７３】
２つの境界面を有するタイプの境界セルの位相構造には、図６に示すように、（ａ）２つの境界面が１つの境界辺を共有しており、境界面の境界以外に境界辺を含まないもの、（ｂ）２つの境界面が境界辺を共有していないもの、（ｃ）２つの境界面が１つの境界辺を共有しており、２つの境界面の何れかと頂点を共有する１つの境界辺を有するもの、（ｄ）２つの境界面が１つの境界辺を共有しており、２つの境界面の何れとも頂点を共有しない１つの境界辺を有するものなどがある。また、２つ以上の境界辺を有するもの（不図示）もある。
【００７４】
これらの境界セルのうち、図６（ａ）に示す位相構造（２つの境界面が１つの境界辺を共有しており、境界面の境界以外に境界辺を含まない）をもつ境界セルは、平面的な境界セルであることが確かめられる。一方、図６（ｂ）〜（ｄ）に示す位相構造をもつ境界セルは、消失する境界セルであることが確かめられる。「２つ以上の境界辺を有する」という位相構造をもつ境界セルも、境界辺の配置を問わず消失する境界セルである。
【００７５】
（４）３つの境界面を有するタイプ
最後に、３つの境界面を有するタイプの境界セルについて、図７を参照して説明する。図７は、３つの境界面を有するタイプの境界セルを例示した図である。
【００７６】
３つの境界面を有するタイプの境界セルの位相構造には、図７に示すように、（ａ）３つの境界面全てによって共有される頂点を有するもの、（ｂ）３つの境界面全てによって共有される頂点を有しないものなどがある。
【００７７】
これらの境界セルのうち、図７（ａ）に示す位相構造（３つの境界面全てによって共有される頂点を有する）をもつ境界セルは、既に図１２を用いて説明したように、平面的な境界セルであることが確かめられる。一方で、図７（ｂ）に示す位相構造（３つの境界面全てによって共有される頂点を有しない）をもつ境界セルは、消失する境界セルであることが確かめられる。
【００７８】
なお、「４つ以上の境界面を有する」という位相構造をもつ境界セルは、消失する境界セルであることが確かめられる。
【００７９】
以上のことから、境界セルは、図４（ｄ），図４（ｆ），図５（ｂ），図６（ａ），図７（ａ）に示す位相構造を有しているとき、すなわち、以下の位相構造をもつとき平面的な境界セルとなる。
【００８０】
（Ａ１）頂点を共有する２つの境界辺を有する、
（Ａ２）頂点を共有する３つの境界辺を有する、
（Ａ３）頂点を共有する１つの境界面と１つの境界辺とを有する、
（Ａ４）辺を共有する２つの境界面を有する、
（Ａ５）頂点を共有する３つの境界面を有する。
【００８１】
なお、上記５つの位相構造を上記の順で位相構造Ａ１〜Ａ５と呼んだとき、位相構造Ａｎ（ｎは１から５までの何れかの整数）を有する境界セルは、ボリュームメッシュの表面上に配置されたｎ＋２個の頂点と、ボリュームメッシュの内部に配置された６−ｎ個の頂点とを有しているという特徴がある。
【００８２】
〔セル点の生成規則〕
次に、Catmall-Clarkのボリューム細分割法におけるセル点の生成規則を、単純平均ＣＰ＝（ｖ０＋ｖ１＋…＋ｖ７）／８から重み付き平均ＣＰ＝ａ・ｖ０＋ｂ・ｖ１＋ｃ・ｖ２＋ｄ・ｖ３＋ｅ・ｖ４＋ｆ・ｖ５＋ｇ・ｖ６＋ｈ・ｖ７（ａ＋ｂ＋ｃ＋ｄ＋ｅ＋ｆ＋ｇ＋ｈ＝１）に置き換えることによって、位相構造Ａ１〜Ａ５をもつ境界セルを２次元に退化させることのないボリューム細分割法が構成できることを示す。なお、本明細書において、記号「・」は、乗算を表すものとする。
【００８３】
セル点の生成規則において各頂点に係る重み係数ａ〜ｈは、ボリュームメッシュの表面上に配置された頂点に係る重み係数の和、及び、ボリュームメッシュの内部に配置された頂点に係る重み係数の和が、それぞれ、１／２になるように設定する。これにより、ボリュームメッシュの表面上に配置された頂点間の距離が０に収束する速さと、ボリュームメッシュの表面からボリュームメッシュの内部に配置された頂点までの距離が０に収束する速さとが均衡するので、境界セルのヤコビアンがｋ→∞の極限で０に収束するという事態を回避することができる。
【００８４】
図１２に示した例に即して言うと、ボリュームメッシュの表面上に配置された７つの頂点ｖ０（ｋ），ｖ１（ｋ），ｖ２（ｋ），ｖ３（ｋ），ｖ４（ｋ），ｖ５（ｋ），ｖ７（ｋ）に係る重み係数の和ａ＋ｂ＋ｃ＋ｄ＋ｅ＋ｆ＋ｈが１／２になり、かつ、ボリュームメッシュの内部に配置された頂点ｖ６（ｋ）に係る重み係数ｇが１／２になるように重み係数ａ〜ｈを定める。
【００８５】
なお、ボリュームメッシュの表面上に配置された頂点同士の重みの配分は、位相構造を考慮して適宜決定すればよい。図１２に示した例（位相構造Ａ５）に即して言うと、例えば、直接的に頂点ｖ０（ｋ）に隣接する頂点ｖ１（ｋ）、ｖ３（ｋ）、ｖ４（ｋ）には第１の重みを与え、これらの頂点を介して頂点ｖ０（ｋ）に隣接するｖ２（ｋ）、ｖ５（ｋ）、ｖ７（ｋ）には第２の重みを与えればよい。すなわち、ｂ＝ｄ＝ｅ、かつ、ｃ＝ｆ＝ｈとすればよい。
【００８６】
また、前節で列挙した平面的な境界セルの各々についても、位相構造を考慮して、重みの配分を決定することができる。このようにして定められた、セル点の生成規則における重み係数ａ〜ｈが満たすべき条件を以下の表１に例示する。
【００８７】
【表１】
0005614684.tif 000002
【００８８】
表１に示す条件においては、８個の重み係数ａ〜ｈに対して、何れの位相構造においても４本の条件式が課されている。したがって、表１に示す条件においては、重み係数ａ〜ｈに対して、何れの位相構造についても８−４＝４本の更なる条件式を課すことにより、重み係数ａ〜ｈが一意的に定まる。換言すれば、何れの位相構造についても４本の更なる条件式を課すことにより、セル点が一意的に定まる。
【００８９】
以下では、一意的に定められた重み係数ａ〜ｈの例として、（１）等方的に定められた重み係数（以下、等方的重み係数とも呼ぶ）、および、（２）非等方的に定められた重み係数（以下、非等方的重み係数とも呼ぶ）について説明する。
【００９０】
（１）等方的重み係数
等方的重み係数は、ボリュームメッシュの表面上に配置された頂点に係る重み係数を互いに等しくとると共に、ボリュームメッシュの内部に配置された頂点に係る重み係数を互いに等しくとることにより求められる。各位相構造についての等方的重み係数を、以下の表２に示す。
【００９１】
【表２】
0005614684.tif 000003
【００９２】
表２からも明らかなように、等方的重み係数を用いると、位相構造Ａｎ（ｎは１から５までの何れかの整数）に属する境界セルについてのセル点ＣＰ（ｎ）は、
ＣＰ（ｎ）＝（ボリュームメッシュの表面上に配置されたｎ＋２個の頂点の平均）×１／２＋（ボリュームメッシュの内部に配置された６−ｎ個の頂点の平均）×１／２
により求まる。
【００９３】
（２）非等方的重み係数
非等方的重み係数の一例を以下の表３に示す。
【００９４】
【表３】
0005614684.tif 000004
【００９５】
表３に示す非等方的重み係数は、所定の条件を満たす重み係数のうち、Catmall-Clarkのボリューム細分割法に最も近い細分割法を与える重み係数である。
【００９６】
〔直線的な境界セル間面〕
次に、Catmall-Clarkのボリューム細分割法において、どのような位相構造を有する境界セル対の境界セル間面が直線的になるかについて説明する。
【００９７】
ボリュームメッシュに含まれる境界セル対の位相構造は、境界セル間面に含まれる境界辺の本数により分類することができる。つまり、（１）境界セル間面が境界辺を有さないタイプ、（２）境界セル間面が１本の境界辺を有するタイプ、（３）境界セル間面が２本の境界辺を有するタイプ、（４）境界セル間面が３本の境界辺を有するタイプ、（５）境界セル間面が４本の境界辺を有するタイプに分類することができる。
【００９８】
ただし、（１）境界セル間面が境界辺を有さないタイプ、（２）境界セル間面が１本の境界辺を有するタイプについては、考慮する必要がない。なぜなら、これらの位相構造を有する境界セル対の境界セル間面は、平面的な境界セル間面であるからである。また、（４）境界セル間面が３本の境界辺を有するタイプ、（５）境界セル間面が４本の境界辺を有するタイプについても、考慮する必要がない。なぜなら、これらの位相構造を有する境界セル対の境界セル間面は１回の細分割により消失するからである。
【００９９】
以下、（３）境界セル間面が２本の境界辺を有するタイプの境界セル対について、図１３を参照して説明する。図１３は、境界セル間面Ｓが２本の境界辺を有するタイプの境界セル対（Ｃ１，Ｃ２）を例示した図である。なお、同図においては、境界面に網掛けを付すことによって、境界面と非境界面（内面）とを区別している。
【０１００】
境界セル間面Ｓが２本の境界辺を有するタイプの境界セル対（Ｃ１，Ｃ２）の位相構造は、境界セル間面Ｓの２つの対面をＳ１，Ｓ２として、（ａ）Ｓ１，Ｓ２の少なくとも一方が境界面であるものと、（ｂ）Ｓ１，Ｓ２の両方が境界面でないものとに大別される。また、（ｂ）Ｓ１，Ｓ２の両方が境界面でない位相構造は、更に、（ｂ１）Ｓ１，Ｓ２の両方が２つの境界辺を有するもの、（ｂ２）Ｓ１，Ｓ２の何れか一方のみが２つの境界辺を有するもの、（ｂ３）Ｓ１，Ｓ２の両方が２つの境界辺を有さないものに分類される。
【０１０１】
境界セル間面Ｓが２本の境界辺を有する境界セル対のうち、（ａ）Ｓ１，Ｓ２の少なくとも一方が境界面である境界セル対が有する位相構造としては、図１３（ｂ）に示す位相構造が挙げられる（対面Ｓ２は、境界面であっても、非境界面であってもよい）。この位相構造を有する境界セル対の境界セル間面は直線的になることが確かめられる。
【０１０２】
また、境界セル間面Ｓが２本の境界辺を有する境界セル対のうち、（ｂ１）Ｓ１，Ｓ２の両方が２つの境界辺を有する境界セル対の位相構造としては、図１３（ａ）に示す位相構造が挙げられる（対面Ｓ２は、非境界面である）。この位相構造を有する境界セル対の境界セル間面が直線的になることは上述したとおりである。
【０１０３】
また、境界セル間面Ｓが２本の境界辺を有する境界セル対のうち、（ｂ２）Ｓ１，Ｓ２の何れか一方のみが２つの境界辺を有する境界セル対の位相構造としては、図１３（ｃ）に示す位相構造、及び、図１３（ｆ）に示す位相構造が挙げられる。これらの位相構造を有する境界セル対の境界セル間面も、直線的になることが確かめられる。
【０１０４】
また、境界セル間面Ｓが２本の境界辺を有する境界セル対のうち、（ｂ３）Ｓ１，Ｓ２の両方が２つの境界辺を有さない境界セル対の位相構造としては、図１３（ｄ）に示す位相構造、及び、図１３（ｅ）に示す位相構造が挙げられる。これらの位相構造を有する境界セル対の境界セル間面も、直線的になることが確かめられる。
【０１０５】
以上のように、境界セル間面Ｓが２本の境界辺を有する境界セル対は、どのような位相構造を有するものであっても、その境界セル間面が直線的になる。
【０１０６】
ただし、上述した４種類の位相構造は、後述するように、境界セル間面Ｓを１次元に退化させることのない面点生成規則が互いに異なる。そこで、本実施形態においては、以下の４種類の位相構造を、境界セル間面Ｓを１次元に退化させる位相構造として取り扱う。
【０１０７】
（Ｂ１）境界セル間面Ｓが２本の境界辺を有し、かつ、境界セル間面Ｓの２つの対面Ｓ１，Ｓ２の両方が２つの境界辺を有している（上記（ｂ１）に対応）、
（Ｂ２）境界セル間面Ｓが２本の境界辺を有し、かつ、境界セル間面Ｓの２つの対面Ｓ１，Ｓ２の少なくとも一方が境界面である（上記（ａ）に対応）、
（Ｂ３）境界セル間面Ｓが２本の境界辺を有し、かつ、境界セル間面Ｓの２つの対面Ｓ１，Ｓ２の何れか一方のみが２つの境界辺を有している（上記（ｂ２）に対応）、
（Ｂ４）境界セル間面Ｓが２本の境界辺を有し、かつ、境界セル間面の２つの対面Ｓ１，Ｓ２の両方が２つの境界辺を有さない（上記（ｂ３）に対応）。
【０１０８】
なお、以上の説明において、「２つの境界辺を有する」とは、境界辺の本数が２である場合のことを意味し、境界辺の本数が３本以上であることを含意しない。また、「２つの境界辺を有さない」とは、境界辺の本数が０又は１である場合のことを意味する（３本以上の境界辺を有する対面は境界面になるので、非境界面においては、境界辺の本数が２でないことと、境界辺の本数が０又は１であることとは等価である）。
【０１０９】
〔面点の生成規則〕
次に、Catmall-Clarkのボリューム細分割法における面点の生成規則を、ＳＰ＝（３／４）α＋（１／４）βから、ＳＰ＝ａ’・ｖ０＋ｂ’・ｖ１＋ｃ’・ｖ２＋ｄ’・ｖ３＋ｅ’・ｖ４＋ｆ’・ｖ５＋ｇ’・ｖ６＋ｈ’・ｖ７＋ｉ’・ｖ８＋ｊ’・ｖ９＋ｋ’・ｖ１０＋ｌ’・ｖ１１，（ａ’＋ｂ’＋ｃ’＋ｄ’＋ｅ’＋ｆ’＋ｇ’＋ｈ’＋ｉ’＋ｊ’＋ｋ’＋ｌ’＝１）に置き換えることによって、位相構造Ｂ１〜Ｂ４をもつ境界セル間面を１次元に退化させることのないボリューム細分割法が構成できることを示す。
【０１１０】
セル間面点の生成規則において、位相構造Ｂ１，Ｂ３，Ｂ４をもつ境界セル間面についての各頂点に係る重み係数ａ’〜ｌ’は、下記の条件（１）〜（４）を満たしたうえで、重み係数の総和が１になるように設定する。
【０１１１】
（１）境界セル間面を構成する各頂点に係る重み係数について、ボリュームメッシュの表面上に配置された３頂点の各々に係る重み係数の和が、ボリュームメッシュの内部に配置された１頂点に係る重み係数と等しくなる。
【０１１２】
（２）境界辺の本数が２である（境界面でない）対面を構成する各頂点に係る重み係数について、ボリュームメッシュの表面上に配置された３頂点の各々に係る重み係数の和が、ボリュームメッシュの内部に配置された１頂点に係る重み係数と等しくなる。
【０１１３】
（３）境界辺の本数が１又は０である（境界面でない）対面を構成する各頂点に係る重み係数について、４頂点の各々に係る重み係数が等しくなる。
【０１１４】
（４）境界面となる対面（境界辺の本数が３又は４である対面）を構成する各頂点について、４頂点の各々に係る重み係数が０になる。
【０１１５】
これにより、境界セル間面の頂点のうち、ボリュームメッシュの表面上に配置された頂点間の距離が０に収束する速さと、ボリュームメッシュの表面からボリュームメッシュの内部に配置された頂点までの距離が０に収束する速さとが均衡するので、境界セル間面のヤコビアンがｋ→∞の極限で０に収束するという事態を回避することができる。
【０１１６】
図１３（ａ）に示した例に即して言うと、境界セル間面Ｓの頂点ｖ０，ｖ１，ｖ２，ｖ３に係る係数について、ボリュームメッシュの表面上に配置された頂点ｖ０，ｖ１，ｖ３に係る重み係数ａ’，ｂ’，ｄ’の和ａ’＋ｂ’＋ｄ’が、ボリュームメッシュの内部に配置された頂点ｖ２に係る重み係数ｃ’と等しくなるように設定する。また、対面Ｓ１の頂点ｖ４，ｖ５，ｖ６，ｖ７に係る係数について、対面Ｓ１が２つの境界辺を有しているので、ボリュームメッシュの表面上に配置された頂点ｖ４，ｖ５，ｖ７に係る重み係数ｆ’，ｅ’，ｈ’の和ｆ’＋ｅ’＋ｈ’が、ボリュームメッシュの内部に配置された頂点ｖ６に係る重み係数ｇ’と等しくなるように設定する。対面Ｓ２の頂点ｖ８，ｖ９，ｖ１０，ｖ１１に係る係数についても同様に設定する。
【０１１７】
また、図１３（ｂ）に示した例に即して言うと、境界セル間面Ｓの頂点ｖ０，ｖ１，ｖ２，ｖ３に係る係数について、ボリュームメッシュの表面上に配置された頂点ｖ０，ｖ１，ｖ３に係る重み係数ａ’，ｂ’，ｄ’の和ａ’＋ｂ’＋ｄ’が、ボリュームメッシュの内部に配置された頂点ｖ２に係る重み係数ｃ’と等しくなるように設定する。また、境界面である対面Ｓ１の頂点ｖ４，ｖ５，ｖ６，ｖ７に係る重み係数ｅ’，ｆ’，ｇ’，ｈ’を０に設定する。また、もう一方の対面Ｓ２の頂点ｖ８，ｖ９，ｖ１０，ｖ１１に係る重み係数ｉ’，ｊ’，ｋ’，ｌ’についても、対面Ｓ２が境界面である場合には、０とすればよい。
【０１１８】
このようにして定められた、セル間面点の生成規則における重み係数ａ’〜ｌ’が満たすべき条件を以下の表４に例示する。なお、括弧を付して示した条件は、他の条件から導出可能な条件である。
【０１１９】
【表４】
0005614684.tif 000005
【０１２０】
表４に示す条件においては、１２個の重み係数ａ’〜ｌ’に対して、何れの位相構造においても１２本未満の条件式が課されている。したがって、表４に示す条件においては、重み係数ａ’〜ｌ’に対して、更なる条件式を課すことにより、重み係数ａ’〜ｌ’を一意的に定めることができる。
【０１２１】
以下では、一意的に定められた重み係数ａ’〜ｌ’の例として、（１）等方的に定められた重み係数（以下、等方的重み係数とも呼ぶ）、および、（２）非等方的に定められた重み係数（以下、非等方的重み係数とも呼ぶ）について説明する。
【０１２２】
（１）等方的重み係数
等方的重み係数は、境界セル間面の頂点のうち、ボリュームメッシュの表面上に配置された頂点に係る重み係数を互いに等しくとることにより求められる。各位相構造についての等方的重み係数を、以下の表５に示す。
【０１２３】
【表５】
0005614684.tif 000006
【０１２４】
（２）非等方的重み係数
非等方的重み係数の一例を以下の表６に示す。
【０１２５】
【表６】
0005614684.tif 000007
【０１２６】
表６に示す非等方的重み係数は、所定の条件を満たす重み係数のうち、Catmall-Clarkのボリューム細分割法に最も近い細分割法を与える重み係数である。
【０１２７】
〔ボリュームメッシュ細分割装置〕
次に、本実施形態に係る細分割装置について図１を参照して説明する。図１は、本実施形態に係るボリュームメッシュ細分割装置１の構成を示したブロック図である。
【０１２８】
ボリュームメッシュ細分割装置１は、ボリュームメッシュＭからボリュームメッシュＭ’を生成するための装置であって、データ取得部１１と、記憶部１２と、データ出力部１３と、セル点生成部１４と、面点生成部１５と、辺点生成部１６と、頂点移動部１７と、隣接関係設定部１８と、境界セル位相構造判定部１９と、セル点生成用重み係数設定部２１と、境界セル対位相構造判定部２３と、面点生成用重み係数設定部２５とを備えている。また、ボリュームメッシュ細分割装置１は、境界セル位相構造テーブル２０と、セル点生成用重み係数テーブル２２と、境界セル対位相構造テーブル２４と、面点生成用重み係数テーブル２６とが格納されたテーブル格納部３０を備えている。
【０１２９】
データ取得部１１は、細分割の対象とするボリュームメッシュＭを外部から取得すると共に、取得したボリュームメッシュＭを記憶部１２に格納するための構成である。データ出力部１３は、後述する各部によって生成されたボリュームメッシュＭ’を記憶部１２から読み出すと共に、読み出したボリュームメッシュＭを外部に出力するための構成である。ボリュームメッシュＭ’を繰り返し細分割する場合には、データ取得部１１が細分割済みのボリュームメッシュＭ’を記憶部１２から読み出すと共に、読み出したボリュームメッシュＭ’を細分割の対象とするボリュームメッシュＭとして記憶部１２に格納し直すことによってループを構成する。
【０１３０】
なお、ボリュームメッシュＭの入力元としては、ボリュームメッシュを生成するメッシュ生成装置などが想定される。この場合、ボリュームメッシュ細分割装置１は、メッシュ生成装置のポストプロセッサとして機能することになる。また、ボリュームメッシュＭ’の出力先としては、有限要素法を用いた数値流体計算を行う数値流体計算装置などが想定される。この際、これらの装置を同一のコンピュータ上で動作するモジュールとして構成してもよい。
【０１３１】
セル点生成部１４は、ボリュームメッシュＭを構成する各セルＣを細分割するためのセル点ＣＰを生成するための構成である。ただし、セルＣが境界セルである場合、セル点生成部１４は、セルＣの位相構造が上述した５種類の位相構造Ａ１〜Ａ５（特定位相構造）の何れかに一致するか否かに応じて、セル点ＣＰを生成するための生成規則を切り替える。具体的には、セルＣの位相構造が位相構造Ａ１〜Ａ５の何れかに一致する場合、セルＣを記憶部１２から読み出すと共に、セルＣの位相構造に対応する８個の重み係数ａ〜ｈをセル点生成用重み係数設定部２１から取得した上で、生成規則ＣＰ＝ａ・ｖ０＋ｂ・ｖ１＋ｃ・ｖ２＋ｄ・ｖ３＋ｅ・ｖ４＋ｆ・ｖ５＋ｇ・ｖ６＋ｈ・ｖ７に従ってセル点ＣＰを生成する。ここで、ｖ０〜ｖ７はセルＣを構成する頂点である。一方、セルＣの位相構造が位相構造Ａ１〜Ａ５の何れにも一致しない場合、セル生成部１４は、セルＣを記憶部１２から読み出した上で、生成規則ＣＰ＝（ｖ０＋ｖ１＋…＋ｖ７）／８に従ってセル点ＣＰを生成する。なお、セル点生成部１４は、境界セルＣの位相構造が位相構造Ａ１〜Ａ５の何れかに一致するか否かを、後述する境界セル位相構造判定部１９から通知によって知る。
【０１３２】
なお、セル点生成部１４を、上述した２つの生成規則を適用して得られたセル点の重み付き平均をセル点ＣＰとするように構成してもよい。この点については、後でもう少し詳しく説明する（〔Catmall-Clarkのボリューム細分割法との併用〕参照）。
【０１３３】
面点生成部１５は、ボリュームメッシュＭを構成する各面Ｓに対応する面点ＳＰを生成するための構成である。面点生成部１５は、面Ｓが境界面である場合、Catmall-Clarkの表面細分割法に基づいて面点ＳＰを生成し、面Ｓが内面（境界面以外の面）である場合、Catmall-Clarkのボリューム細分割法に基づいて面点ＳＰを生成する。後者について、面Ｓが境界セル対（Ｃ１，Ｃ２）の境界間セルである場合、面点生成部１５は、境界セル対（Ｃ１，Ｃ２）の位相構造が上述した４種類の位相構造Ｂ１〜Ｂ４（特定位相構造）の何れかに一致するか否かに応じて、面点ＳＰを生成するための生成規則を切り替える。具体的には、境界セル対（Ｃ１，Ｃ２）の位相構造が位相構造Ｂ１〜Ｂ４の何れかに一致する場合、面Ｓ、及び、面Ｓの対面Ｓ１〜Ｓ２を記憶部１２から読み出すと共に、境界セル対（Ｃ１，Ｃ２）の位相構造に対応する１２個の重み係数ａ’〜ｌ’を面点生成用重み係数設定部２５から取得した上で、生成規則ＳＰ＝ａ’・ｖ０＋ｂ’・ｖ１＋ｃ’・ｖ２＋ｄ’・ｖ３＋ｅ’・ｖ４＋ｆ’・ｖ５＋ｇ’・ｖ６＋ｈ’・ｖ７＋ｉ’・ｖ８＋ｊ’・ｖ９＋ｋ’・ｖ１０＋ｌ’・ｖ１１に従って面点ＳＰを生成する。一方、境界セル対（Ｃ１，Ｃ２）の位相構造が位相構造Ｂ１〜Ｂ４の何れにも一致しない場合、面Ｓ、及び、面Ｓの対面Ｓ１〜Ｓ２を記憶部１２から読み出した上で、生成規則ＳＰ＝（３／４）α＋（１／４）βに従って面点ＳＰを生成する。ここで、ｖ１〜ｖ４は面Ｓを構成する頂点、ｖ５〜ｖ８は面Ｓ１を構成する頂点、ｖ９〜ｖ１２は面Ｓ２を構成する頂点、α＝（ｖ１＋ｖ２＋ｖ３＋ｖ４）／４、β＝（ｖ５＋ｖ６＋…＋ｖ１２）／８である。なお、面点生成部１５は、境界セル対（Ｃ１，Ｃ２）の位相構造が位相構造Ｂ１〜Ｂ４の何れかに一致するか否かを、後述する境界セル対位相構造判定部２３からの通知によって知る。
【０１３４】
辺点生成部１６は、ボリュームメッシュＭを構成する各辺Ｅに対応する辺点ＥＰを生成するための構成である。辺点生成部１６は、辺Ｅが境界辺である場合、Catmall-Clarkの表面細分割法に基づいて辺点ＥＰを生成し、辺Ｅが内辺（境界辺以外の辺）である場合、Catmall-Clarkのボリューム細分割法に基づいて辺点ＥＰを生成する。後者について、具体的には、辺Ｅ、辺Ｅを含む面Ｓ１〜Ｓｎの各々における辺Ｅの対辺Ｅ１〜Ｅｎ、及び、辺Ｅを含むセルＣ１〜Ｃｎの各々における辺Ｅの対辺ＥＣ１〜ＥＣｎを記憶部１２から読み出した上で、生成規則ＥＰ＝（９／１６）ＥＭ＋（３／８）γ＋（１／１６）ηに従って辺点ＥＰを生成する。ここで、ＥＭは辺Ｅの中点、ＥＭ１〜ＥＭｎを辺Ｅ１〜Ｅｎの中点としてγ＝（ＥＭ１＋ＥＭ２＋…＋ＥＭｎ）／ｎ、ＥＣＭ１〜ＥＣＭｎを辺ＥＣ１〜ＥＣｎの中点としてη＝（ＥＣＭ１＋ＥＣＭ２＋…＋ＥＣＭｎ）／ｎである。
【０１３５】
頂点移動部１７は、ボリュームメッシュＭを構成する各頂点ｖを移動するための構成である。頂点移動部１７は、頂点ｖが境界点である場合、Catmall-Clarkの表面細分割法に従って頂点ｖを移動し、頂点ｖが内点（境界点以外の頂点）である場合、Catmall-Clarkのボリューム細分割法に従って頂点ｖを移動する。後者について、具体的には、頂点ｖ、頂点ｖに隣接する頂点ｖ１〜ｖｎ、頂点ｖを含む面Ｓ１〜Ｓｋの各々における頂点ｖの対点ｖＳ１〜ｖＳｋ、及び、頂点ｖを含むセルＣ１〜Ｃｊの各々におけるｖの対点ｖＣ１〜ｖＣｊを記憶部１２から読み出した上で、導出規則ｖ’＝（２７／６４）ｖ＋（２７／６４）Ｐ＋（９／６４）Ｑ＋（１／６４）Ｒに従って移動後の頂点ｖ’を導出する。ここで、Ｐ＝（ｖ１＋ｖ２＋…＋ｖｎ）／ｎ、Ｑ＝（ｖＳ１＋ｖＳ２＋…＋ｖＳｋ）／ｋ、Ｒ＝（ｖＣ１＋ｖＣ２＋…＋ｖＣｊ）／ｊである。
【０１３６】
セル点生成部１４が生成したセル点ＣＰ、面点生成部１５が生成した面点ＳＰ、及び、辺点生成部１６が生成した辺点ＥＰは、ボリュームメッシュＭ’の頂点として記憶部１２に格納される。また、頂点移動部１７が生成した移動後の頂点ｖ’も、ボリュームメッシュＭ’の頂点として記憶部１２に格納される。
【０１３７】
隣接関係設定部１８は、記憶部１２に格納されたこれらの頂点の間に隣接関係を設定するための構成である。具体的には、各セルＣに対応するセル点ＣＰを始点とし、セルＣを構成する面Ｓ１〜Ｓ６に対応する面点ＳＰ１〜ＳＰ６の各々を終点とする辺を設定する。また、セルＣを構成する各面Ｓについて、面Ｓに対応する面点ＳＰを始点とし、面Ｓを構成する辺Ｅ１〜Ｅ４に対応する辺点Ｅ１〜Ｅ４の各々を終点とする辺を設定する。
【０１３８】
境界セル位相構造判定部１９は、境界セルＣの位相構造が位相構造Ａ１〜Ａ５の何れかに一致するか否かを、境界セル位相構造テーブル２０を参照して判定する。この境界セル位相構造テーブル２０には、位相構造Ａ１〜Ａ５の各々について、その位相構造ＩＤと、その位相構造とが互いに関連付けて登録されている。境界セル位相構造判定部１９は、境界セルＣの位相構造と一致する位相構造が境界セル位相構造テーブル２０に登録されている場合、境界セルＣの位相構造が位相構造Ａ１〜Ａ５の何れかに一致する旨をセル点生成部１４に通知すると共に、境界セル位相構造テーブル２０において境界セルＣの位相構造に関連付けられた位相構造ＩＤをセル点生成用重み係数設定部２１に通知する。
【０１３９】
セル点生成用重み係数設定部２１は、セル点生成部１４がセル点の生成に利用する８個の重み係数ａ〜ｈを、セル点生成用重み係数テーブル２２を参照して設定する。このセル点生成用重み係数テーブル２２には、位相構造Ａ１〜Ａ５の各々について、その位相構造ＩＤと、その位相構造を有する境界セルを２次元に退化させることのない重み係数ａ〜ｈとが互いに関連付けて登録されている（表３参照）。セル点生成用重み係数設定部２１は、境界セル位相構造判定部１９から通知された位相構造ＩＤに関連付けられた重み係数ａ〜ｈをセル点生成用重み係数テーブル２２から読み出し、読み出した重み係数ａ〜ｈをセル点生成部１４に供給する。
【０１４０】
境界セル対位相構造判定部２３は、境界セル対（Ｃ１，Ｃ２）の位相構造が位相構造Ｂ１〜Ｂ４の何れかに一致するか否かを、境界セル対位相構造テーブル２４を参照して判定する。この境界セル対位相構造テーブル２４には、位相構造Ｂ１〜Ｂ４の各々について、その位相構造ＩＤと、その位相構造とが互いに関連付けて登録されている。境界セル対位相構造判定部２３は、境界セル対（Ｃ１，Ｃ２）の位相構造と一致する位相構造が境界セル対位相構造テーブル２４に登録されている場合、境界セル対（Ｃ１，Ｃ２）の位相構造が位相構造Ｂ１〜Ｂ４の何れかに一致する旨を面点生成部１５に通知すると共に、境界セル対位相構造テーブル２４において境界セル対（Ｃ１，Ｃ２）の位相構造に関連付けられた位相構造ＩＤを面点生成用重み係数設定部２５に通知する。
【０１４１】
面点生成用重み係数設定部２５は、面点生成部１５が面点の生成に利用する１２個の重み係数ａ’〜ｌ’を、面点生成用重み係数テーブル２６を参照して設定する。この面点生成用重み係数テーブル２６には、位相構造Ｂ１〜Ｂ４の各々について、その位相構造ＩＤと、その位相構造を有する境界セル対に挟まれた境界セル間面を１次元に退化させることのない重み係数ａ’〜ｌ’とが互いに関連付けて登録されている（表６参照）。面点生成用重み係数設定部２５は、境界セル対構造判定部２３から通知された位相構造ＩＤに関連付けられた重み係数ａ’〜ｌ’を面点生成用重みテーブル２６から読み出し、読み出した重み係数ａ’〜ｌ’を面点生成部１５に供給する。
【０１４２】
なお、ボリュームメッシュＭを構成する各セルＣは、（１）セルＣを構成する各頂点の頂点ＩＤからなる頂点集合ＶＳ、（２）セルＣを構成する各辺の辺情報からなる辺集合ＥＳ、（３）セルＣを構成する各面の面情報からなる面集合ＦＳ、（４）セルＣにおける境界点、境界辺、及び境界面の配置を示す境界情報ＢＩ、（５）セルＣを構成する各頂点の位置座標からなる位置情報ＰＩにより表現することができる。ここで、辺情報とは、その辺を構成する２つの頂点の頂点ＩＤの集合のことを指し、面情報とは、その面を構成する４つの頂点の頂点ＩＤの集合のことを指す。また、境界情報ＢＩは、セルＣを構成する境界点、境界辺、及び境界面の頂点ＩＤ、辺情報、及び面情報から構成することができる。
【０１４３】
例えば、図７（ａ）に示す境界セルの頂点集合ＶＳ、辺集合ＥＳ、面集合ＦＳ、及び境界情報ＢＩは、以下のように与えられる：
ＶＳ＝｛０，１，２，３，４，５，６，７｝、
ＥＳ＝｛（０，１），（０，３），（０，４），（１，２），（１，５），（２，３），（２，６），（３，７），（４，５），（４，７），（５，６），（６，７）｝、
ＦＳ＝｛（０，１，２，３），（０，４，５，１），（０，３，７，４），（１，５，６，２），（２，６，７，３），（４，５，６，７）｝、
ＢＩ＝｛０，１，２，３，５，７，（０，１），（０，３），（０，４），（１，２），（１，５），（２，３），（３，７），（４，５），（４，７），（０，１，２，３），（０，４，５，１），（０，３，７，４）｝。
【０１４４】
ボリュームメッシュ細分割装置１は、頂点集合ＶＳ、辺集合ＥＳ、面集合ＦＳ、境界情報ＢＩ、及び位置情報ＰＩを用いて上述した各処理を行う。特に、境界セル位相構造判定部１９は、境界セルＣに関する境界情報ＢＩを用いて、境界セルＣの位相構造が位相構造Ａ１〜Ａ５の何れかに一致するか否かを判定する。また、境界セル対位相構造判定部２３は、境界セル対（Ｃ１，Ｃ２）に関する境界情報対（ＢＩ１，ＢＩ２）を用いて、境界セル対（Ｃ１，Ｃ２）の位相構造が位相構造Ｂ１〜Ｂ４の何れかに一致するか否かを判定する。
【０１４５】
この場合、境界セル位相構造テーブル２０には、位相構造Ａ１〜Ａ５の各々に対応する５つの境界情報ＢＩＡｉが格納される（ｉ＝１，２，３，４，５）。そして、境界セル位相構造判定部１９は、境界情報ＢＩが頂点ＩＤを振り直すことによって境界情報ＢＩＡｉに一致する場合、境界セルＣの位相構造が位相構造Ａｉと同一であると判定し、そうでない場合、境界セルＣの位相構造が位相構造Ａｉと相違すると判定する。
【０１４６】
また、境界セル対位相構造テーブル２４には、位相構造Ｂ１〜Ｂ４の各々に対応する４つの境界情報対（ＢＩ１Ｂｊ，ＢＩ２Ｂｊ）が格納される（ｊ＝１，２，３，４）。そして、境界セル対位相構造判定部２３は、境界情報対（Ｃ１，Ｃ２）が頂点ＩＤを振り直すことによって境界情報対（ＢＩ１Ｂｊ，ＢＩ２Ｂｊ）に一致する場合、境界セル対（Ｃ１，Ｃ２）の位相構造が位相構造Ｂｊと同一であると判定し、そうでない場合、境界セル対（Ｃ１，Ｃ２）の位相構造が位相構造Ｂｊと相違すると判定する。
【０１４７】
なお、境界情報ＢＩの一致／不一致に基づいて境界セル及び境界セル対の位相構造の同異を判定することができるのは、ボリュームメッシュを構成する全てのセルが六面体であるためである。ボリュームメッシュに六面体以外のセルが混在し得る場合には、境界情報ＢＩに加え、頂点集合ＶＳ、辺集合ＥＳ、面集合ＦＳの一致／不一致に基づいて境界セル及び境界セル対の位相構造の同異を判定する構成を採用すればよい。
【０１４８】
〔ボリュームメッシュ細分割装置の動作〕
次に、ボリュームメッシュ細分割装置１の動作について、図２を参照して説明する。図２（ａ）は、ボリュームメッシュ細分割装置１の動作の概要を示すフローチャートであり、図２（ｂ）は、図２（ａ）に含まれるセル点生成処理の詳細を示すフローチャートであり、図２（ｃ）は、図２（ａ）に含まれる面点生成処理の詳細を示すフローチャートである。
【０１４９】
ステップＳ０：データ取得部１１がボリュームメッシュＭを取得する。取得したボリュームメッシュＭは、記憶部１２に格納される。
【０１５０】
ステップＳ１：セル点生成部１４が、上述したように、ボリュームメッシュＭを構成する各セルに対応するセル点を生成する（セル点生成処理）。このセル点生成処理の詳細については後述する。
【０１５１】
ステップＳ２：面点生成部１５が、上述したように、ボリュームメッシュＭを構成する各面に対応する面点を生成する（面点生成処理）。この面点生成処理の詳細については後述する。
【０１５２】
ステップＳ３：辺点生成部１６が、上述したように、ボリュームメッシュＭを構成する各辺に対応する辺点を生成する（辺点生成処理）。この辺点生成処理は、従来の辺点生成処理と同様に実現されるので、これ以上の説明は割愛する。
【０１５３】
ステップＳ４：隣接関係設定部１８が、上述したように、ステップＳ１にて生成された各セル点を始点とする新辺を生成する（セル点を始点とする新辺生成処理）。セル点ＣＰを始点とするこの新辺生成処理は、従来の新辺生成処理と同様に実現されるので、これ以上の説明は割愛する。
【０１５４】
ステップＳ５：隣接関係設定部１８が、上述したように、ステップＳ２にて生成された各面点ＳＰを始点とする新辺を生成する（面点を始点とする新辺生成処理）。面点ＳＰを始点とするこの新辺生成処理は、従来の新辺生成処理と同様に実現されるので、これ以上の説明は割愛する。
【０１５５】
ステップＳ６：隣接関係設定部１８が、上述したように、ステップＳ３にて生成された各辺点ＥＰを始点とする新辺を生成する（辺点を始点とする新辺生成処理）。辺点ＥＰを始点とするこの新辺生成処理は、従来の新辺生成処理と同様に実現されるので、これ以上の説明は割愛する。
【０１５６】
ステップＳ７：頂点移動部１７が、上述したように、ボリュームメッシュを構成する各頂点を移動する（頂点移動処理）。この頂点移動処理は、従来の頂点移動処理と同様に実現されるので、これ以上の説明は割愛する。
【０１５７】
セル点生成処理Ｓ１は、図２（ｂ）に示す各ステップにより構成することができる。セル点生成処理Ｓ１を構成する各ステップについて説明すれば以下のとおりである。
【０１５８】
ステップＳ１１：セル点生成部１４は、処理対象セルＣが境界セルであるか否かを判定する。
【０１５９】
ステップＳ１２：処理対象セルＣが境界セルである場合（ステップＳ１１：Ｙｅｓ）、境界セル位相構造判定部１９は、処理対象セルＣの位相構造が境界セル位相構造テーブル２０に登録された位相構造Ａ１〜Ａ５の何れかに一致するか否かを判定する。
【０１６０】
ステップＳ１３：処理対象セルＣが境界セルでない場合（ステップＳ１１：Ｎｏ）、又は、処理対象セルＣの位相構造が位相構造Ａ１〜Ａ５の何れにも一致しない場合（ステップＳ１２：Ｎｏ）、セル点生成部１４は、従来のセル点生成規則ＣＰ＝（ｖ０＋ｖ１＋…＋ｖ７）／８に従ってセル点ＣＰを生成する。
【０１６１】
ステップＳ１４：処理対象セルＣの位相構造が位相構造Ａ１〜Ａ５の何れかに一致する場合（ステップＳ１２：Ｙｅｓ）、セル点生成用重み係数設定部２１は、処理対象セルＣの位相構造に対応する重み係数ａ〜ｈをセル点生成用重み係数テーブル２２から読み出し、セル点生成部１４に供給する。セル点生成部１４は、この重み係数ａ〜ｈを用いて、セル点生成規則ＣＰ＝ａ・ｖ０＋ｂ・ｖ１＋ｃ・ｖ２＋ｄ・ｖ３＋ｅ・ｖ４＋ｆ・ｖ５＋ｇ・ｖ６＋ｈ・ｖ７に従ってセル点ＣＰを生成する。
【０１６２】
面点生成処理Ｓ２は、図２（ｃ）に示す各ステップにより構成することができる。面点生成処理Ｓ２を構成する各ステップについて説明すれば以下のとおりである。
【０１６３】
ステップＳ２１：面点生成部１５は、処理対象面Ｓが境界面であるか否かを判定する。
【０１６４】
ステップＳ２２：処理対象面Ｓが境界面でない場合、面点生成部１５は、Catmall-Clarkの表面細分割法に従って面点ＳＰを生成する。
【０１６５】
ステップＳ２３：処理対象面Ｓが境界面である場合、面点生成部１５は、処理対象面Ｓを介して互いに隣接するセル対（Ｃ１，Ｃ２）が境界セル対であるか否かを判定する。
【０１６６】
ステップＳ２４：処理対象面Ｓを介して互いに隣接するセル対（Ｃ１，Ｃ２）が境界セル対である場合（ステップＳ２３：Ｙｅｓ）、境界セル対位相構造判定部２３は、セル対（Ｃ１，Ｃ２）の位相構造が境界セル対位相構造テーブル２４に登録された位相構造Ｂ１〜Ｂ４の何れかに一致するか否かを判定する。
【０１６７】
ステップＳ２５：セル対（Ｃ１，Ｃ２）が境界セル対でない場合（ステップＳ２３：Ｎｏ）、又は、セル対（Ｃ１，Ｃ２）の位相構造が位相構造Ｂ１〜Ｂ４の何れにも一致しない場合（ステップＳ２４：Ｎｏ）、面点生成部１５は、従来の面点生成規則ＳＰ＝（３／４）α＋（１／４）βに従って面点ＳＰを生成する（α及びβの定義は上述したとおり）。
【０１６８】
ステップＳ２６：セル対（Ｃ１，Ｃ２）の位相構造が位相構造Ｂ１〜Ｂ４の何れかに一致する場合（ステップＳ２４：Ｙｅｓ）、セル対（Ｃ１，Ｃ２）の位相構造に対応する重み係数ａ’〜ｌ’を面点生成用重み係数テーブル２６から読み出し、面点生成部１５に供給する。面点生成部１５は、この重み係数ａ’〜ｌ’を用いて、面点生成規則ＳＰ＝ａ・ｖ０＋ｂ’・ｖ１＋ｃ’・ｖ２＋ｄ’・ｖ３＋ｅ’・ｖ４＋ｆ’・ｖ５＋ｇ’・ｖ６＋ｈ’・ｖ７＋ｉ’・ｖ８＋ｊ’・ｖ９＋ｋ’・ｖ１０＋ｌ’・ｖ１１に従って面点ＳＰを生成する。
【０１６９】
〔ボリュームメッシュ細分割装置の構成例〕
ボリュームメッシュ細分割装置１は、コンピュータ（電子計算機）を用いて構成することができる。図２は、ボリュームメッシュ細分割装置１として利用可能なコンピュータ１００の構成を例示したブロック図である。
【０１７０】
コンピュータ１００は、図２に示したように、バス１１０を介して互いに接続された演算装置１２０と、主記憶装置１３０と、補助記憶装置１４０と、入出力インタフェース１５０とを備えている。演算装置１２０として利用可能なデバイスとしては、ＣＰＵ（Central Processing Unit）を挙げることができる。また、主記憶装置１３０として利用可能なデバイスとしては、例えば、半導体ＲＡＭ（random access memory）を挙げることができる。また、補助記憶装置１４０として利用可能なデバイスとしては、例えば、ハードディスクドライブを挙げることができる。
【０１７１】
入出力インタフェース１５０には、図２に示したように、入力装置２００及び出力装置３００が接続される。入力装置２００としては、キーボードやマウス、出力装置３００としては、ディスプレイ装置が一般的である。キーボードやマウスは、細分割回数の設定等に利用することができる。また、ディスプレイ装置は、細分割前後のボリュームメッシュを表示するために利用することができる。
【０１７２】
補助記憶装置１４０には、コンピュータ１００をボリュームメッシュ細分割装置１として動作させるための各種プログラムが格納されている。具体的には、データ取得プログラム、データ出力プログラム、セル点生成プログラム、面点生成プログラム、辺点生成プログラム、頂点移動プログラム、隣接関係設定プログラム、境界セル位相構造判定プログラム、セル点生成用重み係数設定プログラム、境界セル対位相構造判定プログラム、及び、面点生成用重み係数設定プログラムが格納されている。また、補助記憶装置１４０は、境界セル位相構造テーブル２０、セル点生成用重み係数テーブル２２、境界セル対位相構造テーブル２４、面点生成用重み係数テーブル２６とを格納するテーブル格納部３０としても利用される。
【０１７３】
演算装置１２０は、補助記憶装置１４０に格納された上記各プログラムを主記憶装置１３０上に展開し、主記憶装置１３０上に展開された上記各プログラムに含まれる命令を実行することによって、コンピュータ１００を、データ取得部１１、データ出力部１３、セル点生成部１４、面点生成部１５、辺点生成部１６、頂点移動部１７、隣接関係設定部１８、境界セル位相構造判定部１９、セル点生成用重み係数設定部２１、境界セル対位相構造判定部２３、面点生成用重み係数設定部２５として機能させる。主記憶装置１３０は、図１に示した記憶部１２としても機能する。すなわち、演算装置１２０が参照する細分割前のボリュームメッシュＭ及び細分割後のボリュームメッシュＭ’は、この主記憶装置１３０に格納される。
【０１７４】
〔Catmall-Clarkのボリューム細分割法との併用〕
以上、境界セルについてヤコビアンがｋ→∞の極限で０に収束するという事態を回避するセル点の生成規則を用いた細分割法について説明したが、当該細分割法は、Catmall-Clarkのボリューム細分割法と併用してもよい。
【０１７５】
例えば、境界セルについて、Catmall-Clarkのボリューム細分割法を用いて導出したセル点をＣＰ＿Ｃと表し、上述したセル点の生成規則を用いた細分割法を用いて導出したセル点をＣＰ＿Ａと表すことにすると、セル点ＣＰ＿Ｃとセル点ＣＰ＿Ａとの、ステップ数ｋに依存した重み付き平均
Ｗk×ＣＰ＿Ｃ＋（１−Ｗk）×ＣＰ＿Ａ
を当該境界セルについてのセル点に設定してもよい。このようにセル点ＣＰ＿Ｃとセル点ＣＰ＿Ａとのステップ数ｋに依存した重み付き平均を用いて境界セルについてのセル点を導出する方法を非定常スキームと呼ぶこともある。上記の式において、Ｗは、ステップ数ｋに依存しないパラメータであり、０＜Ｗ＜１を満たす。また、Ｗの最適値は実験的により求めることができ、例えば、Ｗ＝９／１０と定められる。上記の式から明らかなように、ステップ数ｋが小さいときには、Catmall-Clarkのボリューム細分割法を用いて導出したセル点ＣＰ＿Ｃの寄与が大きく、ステップ数ｋが大きくなるに従って、上述したセル点の生成規則を用いた細分割法を用いて導出したセル点ＣＰ＿Ａの寄与が大きくなる。
【０１７６】
上述したセル点の生成規則を用いた細分割法は、ステップ数が大きくなるに従って、その有効性が増すという傾向があるため、上記のようなステップ数ｋに依存した重み付き平均を用いることによって、Catmall-Clarkのボリューム細分割法および上述したセル点の生成規則を用いた細分割法の双方のメリットを併せ持つボリューム細分割が実現できる。
【０１７７】
〔実験結果〕
以下では、上述したセル点の生成規則を用いた細分割法により得られた実験結果について、Catmall-Clarkのボリューム細分割法のみを用いて得られた実験結果と比較しつつ説明する。図８は、ベアリングの形状をボリューム細分割した実験の結果を示すものであり、（ａ）は、初期ボリュームメッシュを示しており、（ｂ）は、上述したセル点の生成規則を用いたボリューム細分割を複数ステップ行った後の、ベアリングのコーナー部分についてのボリュームメッシュの状態を示しており、（ｃ）は、Catmall-Clarkのボリューム細分割法、表２に示した等方的（アイソメトリック）重み係数を用いたボリューム細分割法、および、表３に示した非等方的（アニソメトリック）重み係数を用いたボリューム細分割法のそれぞれについて、各ステップにおけるスケールドヤコビアン（正規化されたヤコビアン）の値を示している。なお、図８（ｂ）においては、各セルは縮小表示されている。また、図８（ｃ）における「全境界以外の最小」および「全境界以外の平均」とは、ボリュームメッシュに含まれるセルのうち、３つの境界辺からなる境界セル以外のセルについてのスケールドヤコビアンの最小値および平均値を示しており、「全平均」とは、ボリュームメッシュに含まれる全てのセルについてのスケールドヤコビアンの平均値を表している。
【０１７８】
図８（ｃ）に示すように、アイソメトリックおよびアニソメトリックの双方における「全境界以外の最小」は、Catmall-Clarkのボリューム細分割法における「全境界以外の最小」よりも大きい。また、Catmall-Clarkのボリューム細分割法における「全境界以外の最小」は、ステップ数が増すにつれて急速に０に近づく傾向があるが、アイソメトリックおよびアニソメトリックの双方における「全境界以外の最小」は、０への近づき方がCatmall-Clarkのボリューム細分割法よりもなだらかである。したがって、アイソメトリックおよびアニソメトリックの双方において、Catmall-Clarkのボリューム細分割法よりも平面的なセルが生じにくくなっている。
【０１７９】
また、図８（ｂ）に示すように、平面的なセルが生じ易いコーナー部分においても、境界セルの体積は、他のセルの体積と大差がない。このことからも、上述したセル点の生成規則を用いたボリューム細分割により、平面的なセルが生じにくくなっていることが分かる。
【０１８０】
図９は、他の形状をボリューム細分割した実験の結果を示すものであり、（ａ）は、当該他の形状についての初期ボリュームメッシュを示しており、（ｂ）は、Catmall-Clarkのボリューム細分割法、アイソメトリック、および、アニソメトリックのそれぞれについて、各ステップにおけるスケールドヤコビアンの値を示している。
【０１８１】
図９（ｂ）は、図８（ｃ）と同様に、アイソメトリックおよびアニソメトリックの双方において、Catmall-Clarkのボリューム細分割法よりも平面的なセルが生じにくくなっていることを示している。
【０１８２】
また、図８（ｃ）および図９（ｂ）から読み取れるように、等方的（アイソメトリック）な重み係数を用いた方が、非等方的（アニソメトリック）な重み係数を用いるよりも、平面的なセルが生じにくくなるという傾向がある。
【０１８３】
（付記事項）
本実施形態に係るボリュームメッシュ細分割法は、Catmall-Clarkのボリューム細分割法をベースにしたものにあるが、ベースとするボリューム細分割法はこれに限定されない。すなわち、例えば、４面体セルからなるボリュームメッシュを細分割する細分割法など、任意のボリューム細分割法をベースとして、２次元に退化する境界セルが生じることのないボリューム細分割法を実現することができる。
【産業上の利用可能性】
【０１８４】
本発明は、有限要素法に用いられるボリュームメッシュを生成するためのボリュームメッシュ細分割装置に好適に用いることができる。
【符号の説明】
【０１８５】
１            ボリュームメッシュ細分割装置
１１          データ取得部
１２          記憶部
１３          データ出力部
１４          セル点生成部（セル点生成手段）
１５          面点生成部（面点生成手段）
１６          辺点生成部
１７          頂点移動部
１８          隣接関係設定部
１９          境界セル位相構造判定部（境界セル位相構造判定手段）
２０          境界セル位相構造テーブル
２１          セル点生成用重み係数設定部
２２          セル点生成用重み係数テーブル
２３          境界セル対位相構造判定部（境界セル対位相構造判定手段）
２４          境界セル対位相構造テーブル
２５          面点生成用重み係数設定部
２６          面点生成用重み係数テーブル
【図１】
0005614684.tif 000008
【図２】
0005614684.tif 000009
【図３】
0005614684.tif 000010
【図４】
0005614684.tif 000011
【図５】
0005614684.tif 000012
【図６】
0005614684.tif 000013
【図７】
0005614684.tif 000014
【図８】
0005614684.tif 000015
【図９】
0005614684.tif 000016
【図１０】
0005614684.tif 000017
【図１１】
0005614684.tif 000018
【図１２】
0005614684.tif 000019
【図１３】
0005614684.tif 000020