TOP > 国内特許検索 > ボリュームメッシュ細分割装置、及び、ボリュームメッシュ細分割方法 > 明細書

明細書 :ボリュームメッシュ細分割装置、及び、ボリュームメッシュ細分割方法

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5614684号 (P5614684)
公開番号 特開2012-118714 (P2012-118714A)
登録日 平成26年9月19日(2014.9.19)
発行日 平成26年10月29日(2014.10.29)
公開日 平成24年6月21日(2012.6.21)
発明の名称または考案の名称 ボリュームメッシュ細分割装置、及び、ボリュームメッシュ細分割方法
国際特許分類 G06F  17/50        (2006.01)
FI G06F 17/50 612J
請求項の数または発明の数 8
全頁数 33
出願番号 特願2010-267229 (P2010-267229)
出願日 平成22年11月30日(2010.11.30)
審査請求日 平成25年11月12日(2013.11.12)
特許権者または実用新案権者 【識別番号】503359821
【氏名又は名称】独立行政法人理化学研究所
発明者または考案者 【氏名】川原田 寛
【氏名】加瀬 究
個別代理人の代理人 【識別番号】110000338、【氏名又は名称】特許業務法人HARAKENZO WORLD PATENT & TRADEMARK
審査官 【審査官】早川 学
参考文献・文献 特開平7-121579(JP,A)
特開2003-216661(JP,A)
調査した分野 G06F 17/50
特許請求の範囲 【請求項1】
ボリュームメッシュに含まれる各境界セルの位相構造と、第1のセル点生成規則に従って生成されたセル点による細分割を繰り返したときに2次元に退化する境界セルの位相構造として予め登録された特定位相構造とが一致するか否かを判定する境界セル位相構造判定手段と、
上記ボリュームメッシュに含まれる各境界セルを細分割するためのセル点を生成するセル点生成手段であって、位相構造が上記特定位相構造に一致しないと判定された境界セルを細分割するためのセル点を、上記第1のセル点生成規則に従って生成し、位相構造が上記特定位相構造に一致すると判定された境界セルを細分割するためのセル点を、上記第1のセル点生成規則とは異なる第2のセル点生成規則に従って生成するセル点生成手段と、を備えている、
ことを特徴とするボリュームメッシュ細分割装置。
【請求項2】
上記第2のセル点生成規則は、境界セルを細分割するためのセル点を、該境界セルを構成する各頂点の重み付き平均を取ることによって生成するものであり、
上記重み付き平均における重み係数は、上記ボリュームメッシュの境界に含まれる各頂点に係る重み係数の和と、上記ボリュームメッシュの内部に含まれる各頂点に係る重み係数の和とが一致するように設定されている、
ことを特徴とする請求項1に記載のボリュームメッシュ細分割装置。
【請求項3】
上記第1のセル点生成規則は、六面体状の境界セルを細分割するためのセル点を、該境界セルを構成する各頂点の単純平均を取ることによって生成するものであり、
上記特定位相構造は、(1)頂点を共有する2つの境界辺を有する境界セル、(2)頂点を共有する3つの境界辺を有する境界セル、(3)頂点を共有する1つの境界面と1つの境界辺とを有する境界セル、(4)辺を共有する2つの境界面を有する境界セル、及び(5)頂点を共有する3つの境界面を有する境界セルが有する位相構造である、
ことを特徴とする請求項1又は2に記載のボリュームメッシュ細分割装置。
【請求項4】
上記第2のセル点生成規則は、境界セルを細分割するためのセル点を、上記第1のセル点生成規則に従って生成した第1のセル点と上記第1のセル点生成規則とは異なる第3のセル点生成規則に従って生成した第2のセル点との重み付き平均を取ることによって生成するものであり、
上記重み付き平均における重み係数は、上記第1のセル点に係る重みが細分割の繰り返し回数が増えるに従って軽くなり、上記第2のセル点に係る重みが細分割の繰り返し回数が増えるに従って重くなるように設定されている、
ことを特徴とする請求項1に記載のボリュームメッシュ細分割装置。
【請求項5】
上記境界セル位相構造判定手段は、各境界セルの位相構造が上記特定位相構造と一致するか否かを、該境界セルにおける境界点、境界辺、及び境界面の配置を示す境界情報を参照して判定する、
ことを特徴とする請求項1から4までの何れか1項に記載のボリュームメッシュ細分割装置。
【請求項6】
上記ボリュームメッシュに含まれる各境界セル対の位相構造と、第1の面点生成規則に従って生成された面点による細分割を繰り返したときに境界セル間面が1次元に退化する境界セル対の位相構造として予め登録された特定位相構造とが一致するか否かを判定する境界セル対位相構造判定手段と、
上記ボリュームメッシュに含まれる各境界セル対の境界セル間面を細分割するための面点を生成する面点生成手段であって、位相構造が上記特定位相構造に一致しないと判定された境界セル対の境界セル間面を細分割するための面点を、上記第1の面点生成規則に従って生成し、位相構造が上記特定位相構造に一致すると判定された境界セル対の境界セル間面を細分割するための面点を、上記第1の面点生成規則とは異なる第2の面点生成規則に従って生成する面点生成手段と、を更に備えている、
ことを特徴とする請求項1から5までの何れか1項に記載のボリュームメッシュ細分割装置。
【請求項7】
上記境界セル対位相構造判定手段は、各境界セル対の位相構造が上記特定位相構造と一致するか否かを、該境界セル対を構成する2つの境界セルにおける境界点、境界辺、及び境界面の配置を示す境界情報を参照して判定する、
ことを特徴とする請求項6に記載のボリュームメッシュ細分割装置。
【請求項8】
境界セル位相構造判定手段とセル点生成手段とを備えたボリュームメッシュ細分割装置がボリュームメッシュを細分割するボリュームメッシュ細分割方法であって、
上記境界セル位相構造判定手段が、上記ボリュームメッシュに含まれる各境界セルの位相構造と、第1のセル点生成規則に従って生成されたセル点による細分割を繰り返したときに2次元に退化する境界セルの位相構造として予め登録された特定位相構造とが一致するか否かを判定する境界セル位相構造判定ステップと、
上記セル点生成手段が、上記ボリュームメッシュに含まれる各境界セルを細分割するためのセル点を生成するセル点生成ステップであって、位相構造が上記特定位相構造に一致しないと判定された境界セルを細分割するためのセル点を、上記第1のセル点生成規則に従って生成し、位相構造が上記特定位相構造に一致すると判定された境界セルを細分割するためのセル点を、上記第1のセル点生成規則とは異なる第2のセル点生成規則に従って生成するセル点生成ステップと、を含んでいる、
ことを特徴とするボリュームメッシュ細分割方法。
発明の詳細な説明 【技術分野】
【0001】
本発明は、ボリュームメッシュを細分割するボリュームメッシュ細分割装置、及び、ボリュームメッシュ細分割方法に関する。
【背景技術】
【0002】
物体の表面を表現するメッシュを細分割する手法として、Catmall-Clarkの表面細分割法(surface subdivision)が広く用いられている。四角形のセルからなる四角形メッシュMが与えられた場合、Catmall-Clarkの表面細分割法では、以下のステップ1~5を実行することによって、与えられたメッシュMから新たなメッシュM’を生成する。
【0003】
ステップ1:メッシュMを構成する各面に対応する新頂点(以下「面点」と記載)を生成する。面Sに対応する面点SPは、図10(a)に示すように、面Sを構成する頂点をV1~V4として、SP=(V1+V2+V3+V4)/4により与えられる。
【0004】
ステップ2:メッシュMを構成する各辺に対応する新頂点(以下「辺点」と記載)を生成する。辺Eに対応する辺点EPは、図10(b)に示すように、辺Eを構成する2頂点をV1~V2、辺Eを含む2つの面の各々に対応する面点(ステップS1にて生成されたもの)をSP1~SP2として、EP=(V1+V2+SP1+SP2)/4により与えられる。
【0005】
ステップ3:メッシュMを構成する各面Sについて、図10(c)に示すように、面Sに対応する面点SP(ステップ1にて生成されたもの)を始点とし、面Sを構成する辺E1~E4に対応する辺点EP1~EP4(ステップ2にて生成されたもの)の各々を終点とする4本の新辺を生成する。
【0006】
ステップ4:メッシュMを構成する各辺Eについて、図10(c)に示すように、辺Eに対応する辺点(ステップ2にて生成されたもの)を始点とし、辺Eの2つの端点を終点とする2本の新辺を生成した上で、辺Eを破棄する。これにより各面Sが4つの新面に置き換えられる。
【0007】
ステップ5:メッシュMを構成する各頂点を移動する。移動後の頂点V’は、図10(d)に示すように、移動前の頂点をV、頂点Vを含む面の個数をn(図示した例では3)、頂点Vを含む面S1~Snに対応する面点SP1~SPn(ステップ1にて生成されたもの)の平均をQ=(SP1+SP2+…+SPn)/n、頂点Vを含む辺E1~Enの中点EM1~EMnの平均をR=(EM1+EM2+…+EMn)/nとして、{Q+2R+(n-3)V}/nにより与えられる。
【0008】
これにより、ステップS1~S2にて生成された各新頂点、及び、ステップS4にて移動された各旧頂点を頂点とし、ステップS3にて生成された各新辺を辺とする新たなメッシュM’が生成される。
【0009】
また、物体の内部を表現するボリュームメッシュを細分割する手法として、上述したCatmall-Clarkの表面細分割法を拡張した、Catmall-Clarkのボリューム細分割法が知られている(非特許文献1参照)。六面体のセルからなる六面体メッシュMが与えられた場合、Catmall-Clarkのボリューム細分割法では、以下のステップ1~7を実行することによってメッシュMを細分割する。
【0010】
ステップ1:ボリュームメッシュMを構成する各セルに対応する新頂点(以下「セル点」と記載)を生成する。セルCに対応するセル点CPは、図11(a)に示すように、セルCを構成する頂点をV1~V8として、CP=(V1+V2+…+V8)/8により与えられる。
【0011】
ステップ2:ボリュームメッシュMを構成する各面に対応する新頂点(以下「面点」と記載)を生成する。面Sに対応する面点SPは、図11(b)に示すように、面Sを構成する頂点V1~V4の平均をα=(V1+V2+V3+V4)/4、面Sを含むセルC1~C2の各々における面Sの対面をS1~S2、面S1を構成する頂点V5~V8及び面S2を構成する頂点V9~V12の平均をβ=(V5+V6+…+V12)/8として、SP=(3/4)α+(1/4)βにより与えられる。
【0012】
ステップ3:ボリュームメッシュMを構成する各辺に対応する新頂点(以下「辺点」と記載)を生成する。辺Eに対応する辺点EPは、図11(c)に示すように、辺Eの中点をEM、辺Eを含む面の数をn(図示した例では4)、辺Eを含む面S1~Snの各々における辺Eの対辺をE1~En、辺E1~Enの中点EM1~EMnの平均をγ=(EM1+EM2+…+EMn)/n、辺Eを含むセルC1~Cnの各々における辺Eの対辺をEC1~ECn、辺EC1~ECnの中点ECM1~ECMnの平均をη=(ECM1+ECM2+…+ECMn)/nとして、EP=(9/16)EM+(3/8)γ+(1/16)ηにより与えられる。
【0013】
ステップ4:ボリュームメッシュMを構成する各セルCについて、図11(d)に示すように、セルCに対応するセル点CP(ステップ1にて生成されたもの)を始点とし、セルCを構成する面S1~S6に対応する面点SP1~SP6(ステップ2にて生成されたもの)の各々を終点とする6本の新辺を生成する。
【0014】
ステップ5:ボリュームメッシュMを構成する各面Sについて、図11(e)に示すように、面Sに対応する面点SP(ステップ2にて生成されたもの)を始点とし、面Sを構成する辺E1~E4に対応する辺点EP1~EP4(ステップ3にて生成されたもの)の各々を終点とする4本の新辺を生成する。
【0015】
ステップ6:ボリュームメッシュMを構成する各辺Eについて、図11(e)に示すように、辺Eに対応する辺点EP(ステップ3にて生成されたもの)を始点とし、辺Eの2つの端点を終点とする2本の新辺を生成した上で、辺Eを破棄する。これにより、各面Sが4つの新面に置き換えられ、各セルCが8つの新セルに置き換えられる。
【0016】
ステップ7:ボリュームメッシュを構成する各頂点を移動する。移動後の頂点V’は、図11(f)に示すように、移動前の頂点をV、頂点Vに隣接する頂点V1~Vnの平均をP=(V1+V2+…+Vn)/n(図示した例ではn=6)、頂点Vを含む面S1~Skの各々におけるVの対点VS1~VSkの平均をQ=(VS1+VS2+…+VSk)/k(図示した例ではk=12)、頂点Vを含むセルC1~Cjの各々におけるVの対点VC1~VCjの平均をR=(VC1+VC2+…+VCj)/j(図示した例ではj=8)として、V’=(27/64)V+(27/64)P+(9/64)Q+(1/64)Rにより与えられる。
【0017】
なお、ボリュームメッシュMをCatmall-Clarkのボリューム細分割法を用いて細分割する際、ボリュームメッシュMの表面をCatmall-Clarkの表面細分割法を用いて細分割し、前者の細分割により得られた境界点(ボリュームメッシュを構成する頂点のうち、ボリュームメッシュの境界上にある頂点)を後者の細分割により得られた境界点で上書きする。あるいは、ボリュームメッシュMの表面に対してCatmall-Clarkの表面細分割法を適用し、ボリュームメッシュMの内部に対して上述した各ステップを適用する。何れの場合であっても、ボリュームメッシュMの表面に対してCatmall-Clarkの表面細分割法が適用されるので、ボリュームメッシュMをn回細分割することにより得られるボリュームメッシュMnがn→∞の極限で滑らかな表面をもつことが保証される。
【先行技術文献】
【0018】

【非特許文献1】Bajaj,C.,etal.,"A Subdivision scheme for hexahedral Meshes",Visual Computer 18,2002,343-356
【発明の概要】
【発明が解決しようとする課題】
【0019】
しかしながら、従来のボリューム細分割法には、平面的な境界セル(ボリュームメッシュ細分割法を繰り返し適用したときに2次元に退化する境界セル)を生じるという問題があった。
【0020】
ボリュームメッシュ細分割法は、内部セルのヤコビアンを上昇させるという、有限要素法にとって好適な性質を有している。しかしながら、細分割したボリュームメッシュに平面的なセルが含まれていると、そのボリュームメッシュを有限要素法に利用することができない。したがって、従来のボリューム細分割法では、有限要素法に利用可能なボリュームメッシュを生成することができない。
【0021】
なお、「境界セル」とは、少なくとも1つの辺又は面がボリュームメッシュの境界を構成するセルのことを指す。
【0022】
また、境界セルCが「平面的な境界セル」であるとは、(1)ボリューム細分割法を繰り返し適用することによって、その境界セルCと同一の位相構造を有する(境界セルCの位相構造を継承する)境界セルの縮小列C→C(1)→C(2)→…→C(k)→…を作ることができ、かつ、(2)境界セルC(k)のヤコビアンがk→∞の極限で0になることを指す。
【0023】
Catmall-Clarkのボリューム細分割法を用いた場合に平面的な境界セルが生じ得ることを、図12を参照して説明する。図12(a)は、境界セルCの斜視図である。この境界セルCは、「頂点を共有する3つの面が境界面になる」という位相構造を有している。このような位相構造を有する境界セルは、以下に説明するように平面的な境界セルになる。
【0024】
境界セルCにCatmall-Clarkのボリューム細分割法を適用すると、8個の小さな境界セルが得られる。このうち、頂点v0を移動することにより得られた頂点v0(1)を含む境界セルは、頂点v0(1)を共有する3つの境界面を有するという境界セルCの位相構造を継承した境界セルとなる。この境界セルをC(1)とし、再びCatmall-Clarkのボリューム細分割法を適用すると、8個の更に小さな境界セルが得られる。このうち、頂点v0(1)を移動することにより得られた頂点v0(2)を含む境界セルは、頂点v0(2)を共有する3つの境界面を有するという境界セルCの位相構造を継承した境界セルとなる。このようにして、Catmall-Clarkのボリューム細分割法を繰り返し適用すれば、頂点を共有する3つの境界面を有するという境界セルCの位相構造を継承する境界セルの縮小列C→C(1)→C(2)→…→C(k)→…を作ることができる。この縮小列を構成する境界セルC(k)のヤコビアンは、k→∞の極限で0になる。
【0025】
実際、境界セルC(k)の8つの頂点のうち、ボリュームメッシュMの表面上に配置された7つの頂点v1(k),v2(k),v3(k),v4(k),v5(k),v7(k),v0(k)は、細分割に際してCatmall-Clarkの表面細分割法の適用を受ける。したがって、これら7つの頂点v1(k),v2(k),v3(k),v4(k),v5(k),v7(k),v0(k)は、図12(b)に示すように、k→∞の極限で同一平面上に配置される。これは、Catmall-Clarkの表面細分割法がk→∞の極限で滑らかな表面を生成するアルゴリズムだからである。
【0026】
このとき、これら7つの頂点の間に、式(1)の関係が成り立つ。
【0027】
v0(k)+v1(k)+v2(k)+v3(k)+v4(k)
+v5(k)+v7(k)=7v0(k) … (1)
これら7つの頂点v1(k),v2(k),v3(k),v4(k),v5(k),v7(k),v0(k)が同一平面上にある状態でCatmall-Clarkのボリューム細分割法を適用すると、7つの頂点v1(k+1),v2(k+1),v3(k+1),v4(k+1),v5(k+1),v7(k+1),v0(k+1)と共に境界セルC(k+1)を構成する頂点v6(k+1)は、Catmall-Clarkのボリューム細分割法におけるセル点の生成規則に従って、式(2)により与えられる。
【0028】
v6(k+1)=(v0(k)+v1(k)+v2(k)+v3(k)
+v4(k)+v5(k)+v7(k)+v6(k))/8 … (2)
(1)式と(2)式とを合わせると、(3)式の関係が得られる。
【0029】
v6(k+1)-v0(k)={v6(k)-v0(k)}/8 …(3)
k→∞の極限ではv0(k)=v0(k+1)が成り立つため、(3)式は、以下のように書き換えることができる。
【0030】
v6(k+1)-v0(k+1)={v6(k)-v0(k)}/8 …(3’)
(3’)式は、境界セルC(k)の「厚み」に相当する対角線(v0(k),v6(k))の長さが(1/8)のオーダーで縮小することを示している。これに対して、ボリュームメッシュMの表面上にある境界セルC(k)の各境界辺(境界セルC(k)を構成する辺のうち、ボリュームメッシュMの表面上にある辺)の長さは、(1/2)のオーダーで縮小する。したがって、境界セルC(k)は、k→∞の極限で2次元に退化する。すなわち、境界セルC(k)のヤコビアンは、k→∞の極限で0になる。
【0031】
また、従来のボリューム細分割法では、上述した平面的な境界セルに加えて、直線的な境界セル間面(ボリュームメッシュ細分割法を繰り返し適用したときに1次元に退化する境界セル間面)も生じ得る。細分割したボリュームメッシュに直線的な境界セル間面が含まれていると、やはり、そのボリュームメッシュを有限要素法に利用することができない。
【0032】
なお、「境界セル間面」とは、互いに隣接する2つの境界セルからなる境界セル対に挟まれた面のことを指す。境界セル間面は、それ自身が境界を構成する「境界面」とは異なる概念であるので留意されたい。
【0033】
また、境界セル対(C1,C2)の境界セル間面Sが「直線的な境界セル間面」であるとは、ボリューム細分割法を繰り返し適用することによって、境界セル対(C1,C2)と同一の位相構造を有する(境界セル対(C1,C2)の位相構造を継承する)境界セル対の縮小列(C1,C2)→(C1(1),C2(1))→(C1(2),C2(2))→…→(C1(k),C2(k))→…を作ることができ、かつ、(2)境界セル対(C1(k),C2(k))に挟まれた境界セル間面S(k)のヤコビアンがk→∞の極限で0になることを指す。
【0034】
Catmall-Clarkのボリューム細分割法を用いた場合に直線的な境界セル間面が生じ得ることを、図13を参照して説明する。図13(a)は、互いに隣接する2つの境界セルC1,C2からなる境界セル対(C1,C2)を示す斜視図である。この境界セル対(C1,C2)は、「境界セル間面、及び、境界セル間面に対向する2つの面が何れも2つの境界辺を含む」という位相構造を有している。このような位相構造を有する境界セル対(C1,C2)に挟まれた境界セル間面Sは、以下に示すように、直線的な境界セル間面になる。
【0035】
境界セル対(C1,C2)にCatmall-Clarkのボリューム細分割法を適用すると、16個の小さな境界セルが得られる。このうち、頂点v0を移動することにより得られた頂点v0(1)を含む2つの境界セルは、境界セル間面、及び、境界セル間面に対向する2つの面が何れも2つの境界辺を含むという境界セル対(C1,C2)の位相構造を継承した境界セル対を構成する。この境界セル対を(C1(1),C2(1))とし、再びCatmall-Clarkのボリューム細分割法を適用すると、16個の更に小さな境界セルが得られる。このうち、頂点v0(1)を移動することにより得られた頂点v0(2)を含む2つの境界セルは、境界セル間面、及び、境界セル間面に対向する2つの面が何れも2つの境界辺を含むという境界セル対(C1,C2)の位相構造を継承した境界セル対を構成する。このようにして、Catmall-Clarkのボリューム細分割法を繰り返し適用すれば、境界セル間面、及び、境界セル間面に対向する2つの面が何れも2つの境界辺を含むという境界セル対(C1,C2)の位相構造を継承する境界セルの縮小列(C1,C2)→(C1(1),C2(1))→(C1(2),C2(2))→…→(C1(k),C2(k))→…を作ることができる。この縮小列を構成する境界セル対(C1(k),C2(k))間の境界面S(k)のヤコビアンは、k→∞の極限で0になる。
【0036】
実際、境界セル対(C1,C2)の12個の頂点のうち、ボリュームメッシュMの表面上に配置された9つの頂点v0(k),v1(k),v3(k),v4(k),v5(k),v7(k),v8(k),v9(k),v11(k)は、細分割に際してCatmall-Clarkの表面細分割法の適用を受ける。したがって、これら9つの頂点v0(k),v1(k),v3(k),v4(k),v5(k),v7(k),v8(k),v9(k),v11(k)は、k→∞の極限で同一平面上に配置される。この際、3つの頂点v0(k),v1(k),v3(k)は同一直線上に配置される。これは、Catmall-Clarkの表面細分割法がk→∞の極限で滑らかな表面を生成するアルゴリズムだからである。
【0037】
このとき、これら9つの頂点の間に、以下の関係式が成り立つ。
【0038】
v0(k)+v1(k)+v3(k)=3v0(k) … (4a)
v4(k)+v5(k)+v7(k)=3v4(k) … (4b)
v8(k)+v9(k)+v11(k)=3v8(k) … (4c)
v0(k)+v4(k)+v8(k)=3v0(k) … (4d)
また、これら9つの頂点以外の頂点v2(k),v6(k),v10(k)についても、以下の関係が成り立つ。
【0039】
v2(k)+v6(k)+v10(k)=3v2(k) … (4e)
これら9つの頂点v0(k),v1(k),v3(k),v4(k),v5(k),v7(k),v8(k),v9(k),v11(k)が同一平面上にある状態でCatmall-Clarkのボリューム細分割法を適用すると、3つの頂点v0(k+1),v1(k+1),v3(k+1)と共に境界セル間面S(k+1)を構成する頂点v2(k+1)は、Catmall-Clarkのボリューム細分割法における面点の生成規則に従って、式(6)により与えられる。
【0040】
v2(k+1)=3/16(v0(k)+v1(k)+v2(k)+v3(k))
+1/32(v4(k)+v5(k)+v6(k)+v7(k)
+v8(k)+v9(k)+v10(k)+v11(k)) …(5)
(4a)~(4e)式と(5)式とを合わせると、(6)式の関係が得られる。
【0041】
v2(k+1)-v0(k)={v2(k)-v0(k)}/4 …(6)
k→∞の極限ではv0(k)=v0(k+1)が成り立つため、(6)式は、以下のように書き換えることができる。
【0042】
v2(k+1)-v0(k+1)={v2(k)-v0(k)}/4 …(6’)
(6’)式は、境界セル間面S(k)の「厚み」に相当する対角線(v0(k),v2(k))の長さが(1/4)のオーダーで縮小することを示している。これに対して、ボリュームメッシュMの表面上にある境界セル間面S(k)の各境界辺(境界セル間面S(k)を構成する辺のうち、ボリュームメッシュMの表面上にある辺)の長さは、(1/2)のオーダーで縮小する。したがって、境界セル間面S(k)は、k→∞の極限で1次元に退化する。すなわち、境界セル間面S(k)のヤコビアンは、k→∞の極限で0になる。
【0043】
本発明は上記の課題に鑑みてなされたものであり、その目的は、繰り返し適用しても平面的なセルを生じ難いボリューム細分割装置を実現することにある。
【課題を解決するための手段】
【0044】
上記課題を解決するために、本発明に係るボリューム細分割装置は、ボリュームメッシュに含まれる各境界セルの位相構造と、第1のセル点生成規則に従って生成されたセル点による細分割を繰り返したときに2次元に退化する境界セルの位相構造として予め登録された特定位相構造とが一致するか否かを判定する境界セル位相構造判定手段と、上記ボリュームメッシュに含まれる各境界セルを細分割するためのセル点を生成するセル点生成手段であって、位相構造が上記特定位相構造に一致しないと判定された境界セルを細分割するためのセル点を、上記第1のセル点生成規則に従って生成し、位相構造が上記特定位相構造に一致すると判定された境界セルを細分割するためのセル点を、上記第1のセル点生成規則とは異なる第2のセル点生成規則に従って生成するセル点生成手段と、を備えている。
【0045】
また、上記の課題を解決するために、本発明に係るボリューム細分割方法は、ボリュームメッシュに含まれる各境界セルの位相構造と、第1のセル点生成規則に従って生成されたセル点による細分割を繰り返したときに2次元に退化する境界セルの位相構造として予め登録された特定位相構造とが一致するか否かを判定する境界セル位相構造判定ステップと、上記ボリュームメッシュに含まれる各境界セルを細分割するためのセル点を生成するセル点生成ステップであって、位相構造が上記特定位相構造に一致しないと判定された境界セルを細分割するためのセル点を、上記第1の生成規則に従って生成し、位相構造が上記特定位相構造に一致すると判定された境界セルを細分割するためのセル点を、上記第1の生成規則とは異なる第2の生成規則に従って生成するセル点生成ステップと、を含んでいる。
【0046】
上記の構成によれば、第1のセル点生成規則に従って生成されたセル点による細分割を繰り返したときに2次元に退化する位相構造を有する境界セルは、第1のセル点生成規則とは異なる第2のセル点生成規則に従って生成したセル点により細分割される。したがって、第1のセル点生成規則に従って生成したセル点による細分割を繰り返すことにより境界セルが2次元に退化することを回避することができる。すなわち、繰り返し適用しても平面的なセルを生じ難いボリューム細分割を実現することができる。
【0047】
本発明に係るボリュームメッシュ細分割装置において、上記第2のセル点生成規則は、境界セルを細分割するためのセル点を、該境界セルを構成する各頂点の重み付き平均を取ることによって生成するものであり、上記重み付き平均における重み係数は、上記ボリュームメッシュの境界に含まれる各頂点に係る重み係数の和と、上記ボリュームメッシュの内部に含まれる各頂点に係る重み係数の和とが一致するように設定されている、ことが好ましい。
【0048】
上記の構成によれば、境界セルにおいて、ボリュームメッシュの表面上に配置された頂点間の距離が0に収束する速さと、ボリュームメッシュの表面からボリュームメッシュの内部に配置された頂点までの距離が0に収束する速さとが均衡するので、境界セルが2次元に退化することをより確実に回避することができる。
【0049】
本発明に係るボリューム細分割装置において、上記第1のセル点生成規則は、六面体状の境界セルを細分割するためのセル点を、該境界セルを構成する各頂点の単純平均を取ることによって生成するものであり、上記特定位相構造は、(1)頂点を共有する2つの境界辺を有する境界セル、(2)頂点を共有する3つの境界辺を有する境界セル、(3)頂点を共有する1つの境界面と1つの境界辺とを有する境界セル、(4)辺を共有する2つの境界面を有する境界セル、及び(5)頂点を共有する3つの境界面を有する境界セルが有する位相構造である、ことが好ましい。
【0050】
上記の構成によれば、繰り返し適用しても平面的なセルを生じ難いCatmall-Clarkのボリューム細分割を実現することができる。
【0051】
本発明に係るボリュームメッシュ細分割装置において、上記第2のセル点生成規則は、境界セルを細分割するためのセル点を、上記第1の生成規則に従って生成した第1のセル点と上記第1生成規則とは異なる第3の生成規則に従って生成した第2のセル点との重み付き平均を取ることによって生成するものであり、上記重み付き平均における重み係数は、上記第1のセル点に係る重みが細分割の繰り返し回数が増えるに従って軽くなり、上記第2のセル点に係る重みが細分割の繰り返し回数が増えるに従って重くなるように設定されている、ことが好ましい。
【0052】
上記第1の生成規則を用いた細分割が繰り返し回数が小さいときに精度が良いものであり、かつ、上記第3の生成規則を用いた細分割が繰り返し回数が大きいときに精度が良いものであるときに、上記の構成によれば、細分割の繰り返し回数が小さいときであっても、細分割の繰り返し回数が大きいときであっても、精度のよいボリューム細分割を実現することができる。
【0053】
なお、上記境界セル位相構造判定手段は、各境界セルの位相構造が上記特定位相構造と一致するか否かを、例えば、該境界セルにおける境界点、境界辺、及び境界面の配置を示す境界情報を参照して判定することができる。
【0054】
本発明に係るボリュームメッシュ細分割装置は、上記ボリュームメッシュに含まれる各境界セル対の位相構造と、第1の面点生成規則に従って生成された面点による細分割を繰り返したときに境界セル間面が1次元に退化する境界セル対の位相構造として予め登録された特定位相構造とが一致するか否かを判定する境界セル対位相構造判定手段と、上記ボリュームメッシュに含まれる各境界セル対の境界セル間面を細分割するための面点を生成する面点生成手段であって、位相構造が上記特定位相構造に一致しないと判定された境界セル対の境界セル間面を細分割するための面点を、上記第1の面点生成規則に従って生成し、位相構造が上記特定位相構造に一致すると判定された境界セル対の境界セル間面を細分割するための面点を、上記第1の面点生成規則とは異なる第2の面点生成規則に従って生成する面点生成手段と、を更に備えている、ことが好ましい。
【0055】
上記の構成によれば、第1の面点生成規則に従って生成された面点による細分割を繰り返したときに1次元に退化する位相構造を有する境界セル間面は、第1の面点生成規則とは異なる第2の面点生成規則に従って生成した面点により細分割される。したがって、第1の面点生成規則に従って生成した面点による細分割を繰り返すことにより境界セル間面が1次元に退化することを回避することができる。すなわち、繰り返し適用しても直線的な面を生じ難いボリューム細分割を実現することができる。
【0056】
なお、上記境界セル対位相構造判定手段は、各境界セル対の位相構造が上記特定位相構造と一致するか否かを、例えば、該境界セル対を構成する2つの境界セルにおける境界点、境界辺、及び境界面の配置を示す境界情報を参照して判定することができる。
【発明の効果】
【0057】
本発明によれば、繰り返し適用しても平面的なセルを生じ難いボリューム細分割を行うことができる。
【図面の簡単な説明】
【0058】
【図1】本発明の実施形態に係るボリュームメッシュ細分割装置の構成を示すブロック図である。
【図2】図1に示すボリュームメッシュ細分割装置の動作を示すフローチャートである。
【図3】図1に示すボリュームメッシュ細分割装置として機能するコンピュータのブロック図である。
【図4】ボリュームメッシュに含まれる境界セルのうち、境界面を有さないタイプの境界セルを例示する図である。(a)は、境界辺を有さないものを示しており、(b)は、1つの境界辺を有するものを示しており、(c)は、頂点を共有しない2つの境界辺であって、何れかの面において互いに対向する2つの境界辺を有するものを示しており、(d)は、頂点を共有する2つの境界辺を有するものを示しており、(e)は、頂点を共有しない2つの境界辺であって、何れかの面において互いに対向する2つの境界辺を有するものを示しており、(f)は、何れかの頂点を共有する3つの境界辺を有するものを示している。
【図5】ボリュームメッシュに含まれる境界セルのうち、単一の境界面を有するタイプの境界セルを例示する図である。(a)は、境界辺を有さないものを示しており、(b)は、境界面と頂点を共有する1つの境界辺を有するものを示しており、(c)は、境界面と頂点を共有しない1つの境界辺を有するものを示している。
【図6】ボリュームメッシュに含まれる境界セルのうち、2つの境界面を有するタイプの境界セルを例示する図である。(a)は、2つの境界面が1つの境界辺を共有しており、境界面の境界以外に境界辺を含まないものを示しており、(b)は、2つの境界面が境界辺を共有していないものを示しており、(c)は、2つの境界面が1つの境界辺を共有しており、2つの境界面の何れかと頂点を共有する1つの境界辺を有するものを示しており、(d)は、2つの境界面が1つの境界辺を共有しており、2つの境界面の何れとも頂点を共有しない1つの境界辺を有するものを示している。
【図7】ボリュームメッシュに含まれる境界セルのうち、3つの境界面を有するタイプの境界セルを例示する図である。(a)は、3つの境界面全てによって共有される頂点を有するものを示しており、(b)は、3つの境界面全てによって共有される頂点を有しないものを示している。
【図8】本発明の実施形態に係るボリュームメッシュ細分割装置を用いた実験結果の例を説明するための図であって、(a)は、実験に用いた初期ボリュームメッシュを示しており、(b)は、ボリューム細分割を複数ステップ行った後の、コーナー部分についてのボリュームメッシュの状態を示しており、(c)は、Catmall-Clarkのボリューム細分割法、および本発明に係るボリューム細分割法のそれぞれについて、各ステップにおけるスケールドヤコビアンの値を示している。
【図9】本発明の実施形態に係るボリュームメッシュ細分割装置を用いた実験結果の他の例を説明するための図であって、(a)は、実験に用いた初期ボリュームメッシュを示しており、(b)は、ボリューム細分割を複数ステップ行った後の、コーナー部分についてのボリュームメッシュの状態を示しており、(c)は、Catmall-Clarkのボリューム細分割法、および本発明に係るボリューム細分割法のそれぞれについて、各ステップにおけるスケールドヤコビアンの値を示している。
【図10】従来知られているCatmall-Clarkの表面細分割法を説明するための図であって、(a)は、当該表面細分割法によって生成される面点を示しており、(b)は、当該表面細分割法によって生成される辺点を示しており、(c)は、当該表面細分割法によって生成される新辺を示しており、(d)は、当該表面細分割法によって生成される移動後の頂点を示している。
【図11】従来知られているCatmall-Clarkのボリューム細分割法を説明するための図であって、(a)は、当該ボリューム細分割法によって生成されるセル点を示しており、(b)は、当該ボリューム細分割法によって生成される面点を示しており、(c)は、当該ボリューム細分割法によって生成される辺点を示しており、(d)および(e)は、当該ボリューム細分割法によって生成される新辺を示しており、(f)は、当該ボリューム細分割法によって生成される移動後の頂点を示している。
【図12】Catmall-Clarkのボリューム細分割法によって生成される平面的な境界セルについて説明するための図であって、(a)は、Catmall-Clarkのボリューム細分割法により生成される縮小列における各境界セルの頂点を示しており、(b)は、k番目のステップ終了後の各頂点と、k+1番目のステップ終了後の各頂点とを模式的に示す図である。
【図13】ボリュームメッシュに含まれる境界セル対のうち、境界セル間面Sが2つの境界辺を有する場合を例示する図である。(a)は、境界セル間面の2つの対面S1,S2の両方が2つの境界辺を有するものを例示しており、(b)は、境界セル間面の2つの対面の片方が境界面であり、もう片方が2つの境界辺を有するものの例を示しており、(c)は、境界セル間面の2つの対面の片方が2つの境界辺を有しており、もう片方が1つの境界辺を有するものの例を示しており、(d)は、境界セル間面の2つの対面の片方が1つの境界辺を有しており、もう片方が境界辺を有しないものの例を示しており、(e)は、境界セル間面の2つの対面の両方が境界辺を有していないものの例を示しており、(f)は、境界セル間面の2つの対面の片方が2つの境界辺を有しており、もう片方が境界辺を有しないものの例を示している。
【発明を実施するための形態】
【0059】
本実施形態に係るボリュームメッシュ細分割装置は、Catmall-Clarkのボリューム細分割法を改良したボリューム細分割法を用いて、六面体セルからなるボリュームメッシュを細分割するものである。主な改良点は以下の2点である。

【0060】
改良点1:Catmall-Clarkのボリューム細分割法において、どのような位相構造を有する境界セルが平面的になるかを特定したうえで、そのような位相構造を有する境界セルに適用するセル点の生成規則を、従来の生成規則とは異なる生成規則に変更する。これにより、与えられたボリュームメッシュに含まれている平面的な境界セルが2次元に退化することを防止する。

【0061】
改良点2:Catmall-Clarkのボリューム細分割法において、どのような位相構造を有する境界セル対の境界セル間面が直線的になるかを特定したうえで、そのような位相構造を有する境界セル対の境界セル間面に適用する面点の生成規則を、従来の生成規則とは異なる生成規則に変更する。これにより、与えられたボリュームメッシュに含まれている直線的な境界セル間面が1次元に退化することを防止する。

【0062】
〔平面的な境界セル〕
本実施形態に係るボリュームメッシュ細分割装置の説明に入る前に、まず、Catmall-Clarkのボリューム細分割法において、どのような位相構造を有する境界セルが平面的なセルになるかについて説明する。

【0063】
ボリュームメッシュに含まれる境界セルは、(1)境界面を有さないタイプ、(2)単一の境界面を有するタイプ、(3)2つの境界面を有するタイプ、(4)3つの境界面を有するタイプに大別される。以下、これらのタイプの各々について、どのような位相構造を有する境界セルが平面的になるかを述べる。

【0064】
(1)境界面を有さないタイプ
まず、境界面を有さないタイプの境界セルについて、図4を参照して説明する。図4は、境界面を有さないタイプの境界セルを例示した図である。

【0065】
境界面を有さないタイプの境界セルの位相構造には、図4に示すように、(a)境界辺を有さないもの、(b)1つの境界辺を有するもの、(c)頂点を共有しない2つの境界辺であって、何れかの面において互いに対向する2つの境界辺を有するもの、(d)頂点を共有する2つの境界辺を有するもの、(e)頂点を共有しない2つの境界辺であって、何れかの面において互いに対向する2つの境界辺を有するもの、(f)何れかの頂点を共有する3つの境界辺を有するものなどがある。

【0066】
これらの境界セルのうち、図4(d)に示す位相構造(頂点を共有する2つの境界辺を有する)をもつ境界セル、及び、図4(f)に示す位相構造(何れかの頂点を共有する3つの境界辺を有する)をもつ境界セルは、図12に示した位相構造をもつ境界セルと同様、平面的な境界セルであることが確かめられる。

【0067】
一方、図4(c)及び図4(e)に示す位相構造(頂点を共有しない2つの境界辺を有する)をもつ境界セルは、消失する境界セルであることが確かめられる。ここで、ある境界セルが「消失する境界セル」であるとは、ボリューム細分割法を繰り返し適用することによって、その境界セルの位相構造を継承する境界セルの縮小列を構成し得ないことを指す。

【0068】
また、図4(a)に示す位相構造(境界辺を有さない)をもつ境界セル、及び、図4(b)に示す位相構造(1つの境界辺を有する)をもつ境界セルは、立体的な境界セルであることが確かめられる。ここで、ある境界セルが「立体的な境界セル」であるとは、ボリューム細分割法を繰り返し適用することによって、その境界セルの位相構造を継承する境界セルの縮小列C→C(1)→C(2)→…→C(k)→…を構成することができ、かつ、(2)境界セルC(k)のヤコビアンが、k→∞の極限で0でない値をもつことを指す。

【0069】
(2)単一の境界面を有するタイプ
次に、単一の境界面を有するタイプの境界セルについて、図5を参照して説明する。図5は、単一の境界面を有するタイプの境界セルを例示した図である。

【0070】
単一の境界面を有するタイプの境界セルの位相構造には、図5に示すように、(a)境界辺を有さないもの、(b)境界面と頂点を共有する1つの境界辺を有するもの、(c)境界面と頂点を共有しない1つの境界辺を有するものなどがある。また、2つ以上の境界辺を有するもの(不図示)もある。

【0071】
これらの境界セルのうち、図5(b)に示す位相構造(境界面と頂点を共有する1つの境界辺を有する)をもつ境界セルは、平面的な境界セルであることが確かめられる。一方、図5(a)に示す位相構造(境界辺を有さない)をもつ境界セルは、立体的な境界セルであることが確かめられる。また、図5(c)に示す位相構造(境界面と頂点を共有しない1つの境界辺を有する)をもつ境界セルは、消失する境界セルであることが確かめられる。なお、「2つ以上の境界辺を有する」という位相構造をもつ境界セルも、境界辺の配置を問わず消失する境界セルである。

【0072】
(3)2つの境界面を有するタイプ
次に、2つの境界面を有するタイプの境界セルについて、図6を用いて説明する。図6は、2つの境界面を有するタイプの境界セルを例示した図である。

【0073】
2つの境界面を有するタイプの境界セルの位相構造には、図6に示すように、(a)2つの境界面が1つの境界辺を共有しており、境界面の境界以外に境界辺を含まないもの、(b)2つの境界面が境界辺を共有していないもの、(c)2つの境界面が1つの境界辺を共有しており、2つの境界面の何れかと頂点を共有する1つの境界辺を有するもの、(d)2つの境界面が1つの境界辺を共有しており、2つの境界面の何れとも頂点を共有しない1つの境界辺を有するものなどがある。また、2つ以上の境界辺を有するもの(不図示)もある。

【0074】
これらの境界セルのうち、図6(a)に示す位相構造(2つの境界面が1つの境界辺を共有しており、境界面の境界以外に境界辺を含まない)をもつ境界セルは、平面的な境界セルであることが確かめられる。一方、図6(b)~(d)に示す位相構造をもつ境界セルは、消失する境界セルであることが確かめられる。「2つ以上の境界辺を有する」という位相構造をもつ境界セルも、境界辺の配置を問わず消失する境界セルである。

【0075】
(4)3つの境界面を有するタイプ
最後に、3つの境界面を有するタイプの境界セルについて、図7を参照して説明する。図7は、3つの境界面を有するタイプの境界セルを例示した図である。

【0076】
3つの境界面を有するタイプの境界セルの位相構造には、図7に示すように、(a)3つの境界面全てによって共有される頂点を有するもの、(b)3つの境界面全てによって共有される頂点を有しないものなどがある。

【0077】
これらの境界セルのうち、図7(a)に示す位相構造(3つの境界面全てによって共有される頂点を有する)をもつ境界セルは、既に図12を用いて説明したように、平面的な境界セルであることが確かめられる。一方で、図7(b)に示す位相構造(3つの境界面全てによって共有される頂点を有しない)をもつ境界セルは、消失する境界セルであることが確かめられる。

【0078】
なお、「4つ以上の境界面を有する」という位相構造をもつ境界セルは、消失する境界セルであることが確かめられる。

【0079】
以上のことから、境界セルは、図4(d),図4(f),図5(b),図6(a),図7(a)に示す位相構造を有しているとき、すなわち、以下の位相構造をもつとき平面的な境界セルとなる。

【0080】
(A1)頂点を共有する2つの境界辺を有する、
(A2)頂点を共有する3つの境界辺を有する、
(A3)頂点を共有する1つの境界面と1つの境界辺とを有する、
(A4)辺を共有する2つの境界面を有する、
(A5)頂点を共有する3つの境界面を有する。

【0081】
なお、上記5つの位相構造を上記の順で位相構造A1~A5と呼んだとき、位相構造An(nは1から5までの何れかの整数)を有する境界セルは、ボリュームメッシュの表面上に配置されたn+2個の頂点と、ボリュームメッシュの内部に配置された6-n個の頂点とを有しているという特徴がある。

【0082】
〔セル点の生成規則〕
次に、Catmall-Clarkのボリューム細分割法におけるセル点の生成規則を、単純平均CP=(v0+v1+…+v7)/8から重み付き平均CP=a・v0+b・v1+c・v2+d・v3+e・v4+f・v5+g・v6+h・v7(a+b+c+d+e+f+g+h=1)に置き換えることによって、位相構造A1~A5をもつ境界セルを2次元に退化させることのないボリューム細分割法が構成できることを示す。なお、本明細書において、記号「・」は、乗算を表すものとする。

【0083】
セル点の生成規則において各頂点に係る重み係数a~hは、ボリュームメッシュの表面上に配置された頂点に係る重み係数の和、及び、ボリュームメッシュの内部に配置された頂点に係る重み係数の和が、それぞれ、1/2になるように設定する。これにより、ボリュームメッシュの表面上に配置された頂点間の距離が0に収束する速さと、ボリュームメッシュの表面からボリュームメッシュの内部に配置された頂点までの距離が0に収束する速さとが均衡するので、境界セルのヤコビアンがk→∞の極限で0に収束するという事態を回避することができる。

【0084】
図12に示した例に即して言うと、ボリュームメッシュの表面上に配置された7つの頂点v0(k),v1(k),v2(k),v3(k),v4(k),v5(k),v7(k)に係る重み係数の和a+b+c+d+e+f+hが1/2になり、かつ、ボリュームメッシュの内部に配置された頂点v6(k)に係る重み係数gが1/2になるように重み係数a~hを定める。

【0085】
なお、ボリュームメッシュの表面上に配置された頂点同士の重みの配分は、位相構造を考慮して適宜決定すればよい。図12に示した例(位相構造A5)に即して言うと、例えば、直接的に頂点v0(k)に隣接する頂点v1(k)、v3(k)、v4(k)には第1の重みを与え、これらの頂点を介して頂点v0(k)に隣接するv2(k)、v5(k)、v7(k)には第2の重みを与えればよい。すなわち、b=d=e、かつ、c=f=hとすればよい。

【0086】
また、前節で列挙した平面的な境界セルの各々についても、位相構造を考慮して、重みの配分を決定することができる。このようにして定められた、セル点の生成規則における重み係数a~hが満たすべき条件を以下の表1に例示する。

【0087】
【表1】
JP0005614684B2_000002t.gif

【0088】
表1に示す条件においては、8個の重み係数a~hに対して、何れの位相構造においても4本の条件式が課されている。したがって、表1に示す条件においては、重み係数a~hに対して、何れの位相構造についても8-4=4本の更なる条件式を課すことにより、重み係数a~hが一意的に定まる。換言すれば、何れの位相構造についても4本の更なる条件式を課すことにより、セル点が一意的に定まる。

【0089】
以下では、一意的に定められた重み係数a~hの例として、(1)等方的に定められた重み係数(以下、等方的重み係数とも呼ぶ)、および、(2)非等方的に定められた重み係数(以下、非等方的重み係数とも呼ぶ)について説明する。

【0090】
(1)等方的重み係数
等方的重み係数は、ボリュームメッシュの表面上に配置された頂点に係る重み係数を互いに等しくとると共に、ボリュームメッシュの内部に配置された頂点に係る重み係数を互いに等しくとることにより求められる。各位相構造についての等方的重み係数を、以下の表2に示す。

【0091】
【表2】
JP0005614684B2_000003t.gif

【0092】
表2からも明らかなように、等方的重み係数を用いると、位相構造An(nは1から5までの何れかの整数)に属する境界セルについてのセル点CP(n)は、
CP(n)=(ボリュームメッシュの表面上に配置されたn+2個の頂点の平均)×1/2+(ボリュームメッシュの内部に配置された6-n個の頂点の平均)×1/2
により求まる。

【0093】
(2)非等方的重み係数
非等方的重み係数の一例を以下の表3に示す。

【0094】
【表3】
JP0005614684B2_000004t.gif

【0095】
表3に示す非等方的重み係数は、所定の条件を満たす重み係数のうち、Catmall-Clarkのボリューム細分割法に最も近い細分割法を与える重み係数である。

【0096】
〔直線的な境界セル間面〕
次に、Catmall-Clarkのボリューム細分割法において、どのような位相構造を有する境界セル対の境界セル間面が直線的になるかについて説明する。

【0097】
ボリュームメッシュに含まれる境界セル対の位相構造は、境界セル間面に含まれる境界辺の本数により分類することができる。つまり、(1)境界セル間面が境界辺を有さないタイプ、(2)境界セル間面が1本の境界辺を有するタイプ、(3)境界セル間面が2本の境界辺を有するタイプ、(4)境界セル間面が3本の境界辺を有するタイプ、(5)境界セル間面が4本の境界辺を有するタイプに分類することができる。

【0098】
ただし、(1)境界セル間面が境界辺を有さないタイプ、(2)境界セル間面が1本の境界辺を有するタイプについては、考慮する必要がない。なぜなら、これらの位相構造を有する境界セル対の境界セル間面は、平面的な境界セル間面であるからである。また、(4)境界セル間面が3本の境界辺を有するタイプ、(5)境界セル間面が4本の境界辺を有するタイプについても、考慮する必要がない。なぜなら、これらの位相構造を有する境界セル対の境界セル間面は1回の細分割により消失するからである。

【0099】
以下、(3)境界セル間面が2本の境界辺を有するタイプの境界セル対について、図13を参照して説明する。図13は、境界セル間面Sが2本の境界辺を有するタイプの境界セル対(C1,C2)を例示した図である。なお、同図においては、境界面に網掛けを付すことによって、境界面と非境界面(内面)とを区別している。

【0100】
境界セル間面Sが2本の境界辺を有するタイプの境界セル対(C1,C2)の位相構造は、境界セル間面Sの2つの対面をS1,S2として、(a)S1,S2の少なくとも一方が境界面であるものと、(b)S1,S2の両方が境界面でないものとに大別される。また、(b)S1,S2の両方が境界面でない位相構造は、更に、(b1)S1,S2の両方が2つの境界辺を有するもの、(b2)S1,S2の何れか一方のみが2つの境界辺を有するもの、(b3)S1,S2の両方が2つの境界辺を有さないものに分類される。

【0101】
境界セル間面Sが2本の境界辺を有する境界セル対のうち、(a)S1,S2の少なくとも一方が境界面である境界セル対が有する位相構造としては、図13(b)に示す位相構造が挙げられる(対面S2は、境界面であっても、非境界面であってもよい)。この位相構造を有する境界セル対の境界セル間面は直線的になることが確かめられる。

【0102】
また、境界セル間面Sが2本の境界辺を有する境界セル対のうち、(b1)S1,S2の両方が2つの境界辺を有する境界セル対の位相構造としては、図13(a)に示す位相構造が挙げられる(対面S2は、非境界面である)。この位相構造を有する境界セル対の境界セル間面が直線的になることは上述したとおりである。

【0103】
また、境界セル間面Sが2本の境界辺を有する境界セル対のうち、(b2)S1,S2の何れか一方のみが2つの境界辺を有する境界セル対の位相構造としては、図13(c)に示す位相構造、及び、図13(f)に示す位相構造が挙げられる。これらの位相構造を有する境界セル対の境界セル間面も、直線的になることが確かめられる。

【0104】
また、境界セル間面Sが2本の境界辺を有する境界セル対のうち、(b3)S1,S2の両方が2つの境界辺を有さない境界セル対の位相構造としては、図13(d)に示す位相構造、及び、図13(e)に示す位相構造が挙げられる。これらの位相構造を有する境界セル対の境界セル間面も、直線的になることが確かめられる。

【0105】
以上のように、境界セル間面Sが2本の境界辺を有する境界セル対は、どのような位相構造を有するものであっても、その境界セル間面が直線的になる。

【0106】
ただし、上述した4種類の位相構造は、後述するように、境界セル間面Sを1次元に退化させることのない面点生成規則が互いに異なる。そこで、本実施形態においては、以下の4種類の位相構造を、境界セル間面Sを1次元に退化させる位相構造として取り扱う。

【0107】
(B1)境界セル間面Sが2本の境界辺を有し、かつ、境界セル間面Sの2つの対面S1,S2の両方が2つの境界辺を有している(上記(b1)に対応)、
(B2)境界セル間面Sが2本の境界辺を有し、かつ、境界セル間面Sの2つの対面S1,S2の少なくとも一方が境界面である(上記(a)に対応)、
(B3)境界セル間面Sが2本の境界辺を有し、かつ、境界セル間面Sの2つの対面S1,S2の何れか一方のみが2つの境界辺を有している(上記(b2)に対応)、
(B4)境界セル間面Sが2本の境界辺を有し、かつ、境界セル間面の2つの対面S1,S2の両方が2つの境界辺を有さない(上記(b3)に対応)。

【0108】
なお、以上の説明において、「2つの境界辺を有する」とは、境界辺の本数が2である場合のことを意味し、境界辺の本数が3本以上であることを含意しない。また、「2つの境界辺を有さない」とは、境界辺の本数が0又は1である場合のことを意味する(3本以上の境界辺を有する対面は境界面になるので、非境界面においては、境界辺の本数が2でないことと、境界辺の本数が0又は1であることとは等価である)。

【0109】
〔面点の生成規則〕
次に、Catmall-Clarkのボリューム細分割法における面点の生成規則を、SP=(3/4)α+(1/4)βから、SP=a’・v0+b’・v1+c’・v2+d’・v3+e’・v4+f’・v5+g’・v6+h’・v7+i’・v8+j’・v9+k’・v10+l’・v11,(a’+b’+c’+d’+e’+f’+g’+h’+i’+j’+k’+l’=1)に置き換えることによって、位相構造B1~B4をもつ境界セル間面を1次元に退化させることのないボリューム細分割法が構成できることを示す。

【0110】
セル間面点の生成規則において、位相構造B1,B3,B4をもつ境界セル間面についての各頂点に係る重み係数a’~l’は、下記の条件(1)~(4)を満たしたうえで、重み係数の総和が1になるように設定する。

【0111】
(1)境界セル間面を構成する各頂点に係る重み係数について、ボリュームメッシュの表面上に配置された3頂点の各々に係る重み係数の和が、ボリュームメッシュの内部に配置された1頂点に係る重み係数と等しくなる。

【0112】
(2)境界辺の本数が2である(境界面でない)対面を構成する各頂点に係る重み係数について、ボリュームメッシュの表面上に配置された3頂点の各々に係る重み係数の和が、ボリュームメッシュの内部に配置された1頂点に係る重み係数と等しくなる。

【0113】
(3)境界辺の本数が1又は0である(境界面でない)対面を構成する各頂点に係る重み係数について、4頂点の各々に係る重み係数が等しくなる。

【0114】
(4)境界面となる対面(境界辺の本数が3又は4である対面)を構成する各頂点について、4頂点の各々に係る重み係数が0になる。

【0115】
これにより、境界セル間面の頂点のうち、ボリュームメッシュの表面上に配置された頂点間の距離が0に収束する速さと、ボリュームメッシュの表面からボリュームメッシュの内部に配置された頂点までの距離が0に収束する速さとが均衡するので、境界セル間面のヤコビアンがk→∞の極限で0に収束するという事態を回避することができる。

【0116】
図13(a)に示した例に即して言うと、境界セル間面Sの頂点v0,v1,v2,v3に係る係数について、ボリュームメッシュの表面上に配置された頂点v0,v1,v3に係る重み係数a’,b’,d’の和a’+b’+d’が、ボリュームメッシュの内部に配置された頂点v2に係る重み係数c’と等しくなるように設定する。また、対面S1の頂点v4,v5,v6,v7に係る係数について、対面S1が2つの境界辺を有しているので、ボリュームメッシュの表面上に配置された頂点v4,v5,v7に係る重み係数f’,e’,h’の和f’+e’+h’が、ボリュームメッシュの内部に配置された頂点v6に係る重み係数g’と等しくなるように設定する。対面S2の頂点v8,v9,v10,v11に係る係数についても同様に設定する。

【0117】
また、図13(b)に示した例に即して言うと、境界セル間面Sの頂点v0,v1,v2,v3に係る係数について、ボリュームメッシュの表面上に配置された頂点v0,v1,v3に係る重み係数a’,b’,d’の和a’+b’+d’が、ボリュームメッシュの内部に配置された頂点v2に係る重み係数c’と等しくなるように設定する。また、境界面である対面S1の頂点v4,v5,v6,v7に係る重み係数e’,f’,g’,h’を0に設定する。また、もう一方の対面S2の頂点v8,v9,v10,v11に係る重み係数i’,j’,k’,l’についても、対面S2が境界面である場合には、0とすればよい。

【0118】
このようにして定められた、セル間面点の生成規則における重み係数a’~l’が満たすべき条件を以下の表4に例示する。なお、括弧を付して示した条件は、他の条件から導出可能な条件である。

【0119】
【表4】
JP0005614684B2_000005t.gif

【0120】
表4に示す条件においては、12個の重み係数a’~l’に対して、何れの位相構造においても12本未満の条件式が課されている。したがって、表4に示す条件においては、重み係数a’~l’に対して、更なる条件式を課すことにより、重み係数a’~l’を一意的に定めることができる。

【0121】
以下では、一意的に定められた重み係数a’~l’の例として、(1)等方的に定められた重み係数(以下、等方的重み係数とも呼ぶ)、および、(2)非等方的に定められた重み係数(以下、非等方的重み係数とも呼ぶ)について説明する。

【0122】
(1)等方的重み係数
等方的重み係数は、境界セル間面の頂点のうち、ボリュームメッシュの表面上に配置された頂点に係る重み係数を互いに等しくとることにより求められる。各位相構造についての等方的重み係数を、以下の表5に示す。

【0123】
【表5】
JP0005614684B2_000006t.gif

【0124】
(2)非等方的重み係数
非等方的重み係数の一例を以下の表6に示す。

【0125】
【表6】
JP0005614684B2_000007t.gif

【0126】
表6に示す非等方的重み係数は、所定の条件を満たす重み係数のうち、Catmall-Clarkのボリューム細分割法に最も近い細分割法を与える重み係数である。

【0127】
〔ボリュームメッシュ細分割装置〕
次に、本実施形態に係る細分割装置について図1を参照して説明する。図1は、本実施形態に係るボリュームメッシュ細分割装置1の構成を示したブロック図である。

【0128】
ボリュームメッシュ細分割装置1は、ボリュームメッシュMからボリュームメッシュM’を生成するための装置であって、データ取得部11と、記憶部12と、データ出力部13と、セル点生成部14と、面点生成部15と、辺点生成部16と、頂点移動部17と、隣接関係設定部18と、境界セル位相構造判定部19と、セル点生成用重み係数設定部21と、境界セル対位相構造判定部23と、面点生成用重み係数設定部25とを備えている。また、ボリュームメッシュ細分割装置1は、境界セル位相構造テーブル20と、セル点生成用重み係数テーブル22と、境界セル対位相構造テーブル24と、面点生成用重み係数テーブル26とが格納されたテーブル格納部30を備えている。

【0129】
データ取得部11は、細分割の対象とするボリュームメッシュMを外部から取得すると共に、取得したボリュームメッシュMを記憶部12に格納するための構成である。データ出力部13は、後述する各部によって生成されたボリュームメッシュM’を記憶部12から読み出すと共に、読み出したボリュームメッシュMを外部に出力するための構成である。ボリュームメッシュM’を繰り返し細分割する場合には、データ取得部11が細分割済みのボリュームメッシュM’を記憶部12から読み出すと共に、読み出したボリュームメッシュM’を細分割の対象とするボリュームメッシュMとして記憶部12に格納し直すことによってループを構成する。

【0130】
なお、ボリュームメッシュMの入力元としては、ボリュームメッシュを生成するメッシュ生成装置などが想定される。この場合、ボリュームメッシュ細分割装置1は、メッシュ生成装置のポストプロセッサとして機能することになる。また、ボリュームメッシュM’の出力先としては、有限要素法を用いた数値流体計算を行う数値流体計算装置などが想定される。この際、これらの装置を同一のコンピュータ上で動作するモジュールとして構成してもよい。

【0131】
セル点生成部14は、ボリュームメッシュMを構成する各セルCを細分割するためのセル点CPを生成するための構成である。ただし、セルCが境界セルである場合、セル点生成部14は、セルCの位相構造が上述した5種類の位相構造A1~A5(特定位相構造)の何れかに一致するか否かに応じて、セル点CPを生成するための生成規則を切り替える。具体的には、セルCの位相構造が位相構造A1~A5の何れかに一致する場合、セルCを記憶部12から読み出すと共に、セルCの位相構造に対応する8個の重み係数a~hをセル点生成用重み係数設定部21から取得した上で、生成規則CP=a・v0+b・v1+c・v2+d・v3+e・v4+f・v5+g・v6+h・v7に従ってセル点CPを生成する。ここで、v0~v7はセルCを構成する頂点である。一方、セルCの位相構造が位相構造A1~A5の何れにも一致しない場合、セル生成部14は、セルCを記憶部12から読み出した上で、生成規則CP=(v0+v1+…+v7)/8に従ってセル点CPを生成する。なお、セル点生成部14は、境界セルCの位相構造が位相構造A1~A5の何れかに一致するか否かを、後述する境界セル位相構造判定部19から通知によって知る。

【0132】
なお、セル点生成部14を、上述した2つの生成規則を適用して得られたセル点の重み付き平均をセル点CPとするように構成してもよい。この点については、後でもう少し詳しく説明する(〔Catmall-Clarkのボリューム細分割法との併用〕参照)。

【0133】
面点生成部15は、ボリュームメッシュMを構成する各面Sに対応する面点SPを生成するための構成である。面点生成部15は、面Sが境界面である場合、Catmall-Clarkの表面細分割法に基づいて面点SPを生成し、面Sが内面(境界面以外の面)である場合、Catmall-Clarkのボリューム細分割法に基づいて面点SPを生成する。後者について、面Sが境界セル対(C1,C2)の境界間セルである場合、面点生成部15は、境界セル対(C1,C2)の位相構造が上述した4種類の位相構造B1~B4(特定位相構造)の何れかに一致するか否かに応じて、面点SPを生成するための生成規則を切り替える。具体的には、境界セル対(C1,C2)の位相構造が位相構造B1~B4の何れかに一致する場合、面S、及び、面Sの対面S1~S2を記憶部12から読み出すと共に、境界セル対(C1,C2)の位相構造に対応する12個の重み係数a’~l’を面点生成用重み係数設定部25から取得した上で、生成規則SP=a’・v0+b’・v1+c’・v2+d’・v3+e’・v4+f’・v5+g’・v6+h’・v7+i’・v8+j’・v9+k’・v10+l’・v11に従って面点SPを生成する。一方、境界セル対(C1,C2)の位相構造が位相構造B1~B4の何れにも一致しない場合、面S、及び、面Sの対面S1~S2を記憶部12から読み出した上で、生成規則SP=(3/4)α+(1/4)βに従って面点SPを生成する。ここで、v1~v4は面Sを構成する頂点、v5~v8は面S1を構成する頂点、v9~v12は面S2を構成する頂点、α=(v1+v2+v3+v4)/4、β=(v5+v6+…+v12)/8である。なお、面点生成部15は、境界セル対(C1,C2)の位相構造が位相構造B1~B4の何れかに一致するか否かを、後述する境界セル対位相構造判定部23からの通知によって知る。

【0134】
辺点生成部16は、ボリュームメッシュMを構成する各辺Eに対応する辺点EPを生成するための構成である。辺点生成部16は、辺Eが境界辺である場合、Catmall-Clarkの表面細分割法に基づいて辺点EPを生成し、辺Eが内辺(境界辺以外の辺)である場合、Catmall-Clarkのボリューム細分割法に基づいて辺点EPを生成する。後者について、具体的には、辺E、辺Eを含む面S1~Snの各々における辺Eの対辺E1~En、及び、辺Eを含むセルC1~Cnの各々における辺Eの対辺EC1~ECnを記憶部12から読み出した上で、生成規則EP=(9/16)EM+(3/8)γ+(1/16)ηに従って辺点EPを生成する。ここで、EMは辺Eの中点、EM1~EMnを辺E1~Enの中点としてγ=(EM1+EM2+…+EMn)/n、ECM1~ECMnを辺EC1~ECnの中点としてη=(ECM1+ECM2+…+ECMn)/nである。

【0135】
頂点移動部17は、ボリュームメッシュMを構成する各頂点vを移動するための構成である。頂点移動部17は、頂点vが境界点である場合、Catmall-Clarkの表面細分割法に従って頂点vを移動し、頂点vが内点(境界点以外の頂点)である場合、Catmall-Clarkのボリューム細分割法に従って頂点vを移動する。後者について、具体的には、頂点v、頂点vに隣接する頂点v1~vn、頂点vを含む面S1~Skの各々における頂点vの対点vS1~vSk、及び、頂点vを含むセルC1~Cjの各々におけるvの対点vC1~vCjを記憶部12から読み出した上で、導出規則v’=(27/64)v+(27/64)P+(9/64)Q+(1/64)Rに従って移動後の頂点v’を導出する。ここで、P=(v1+v2+…+vn)/n、Q=(vS1+vS2+…+vSk)/k、R=(vC1+vC2+…+vCj)/jである。

【0136】
セル点生成部14が生成したセル点CP、面点生成部15が生成した面点SP、及び、辺点生成部16が生成した辺点EPは、ボリュームメッシュM’の頂点として記憶部12に格納される。また、頂点移動部17が生成した移動後の頂点v’も、ボリュームメッシュM’の頂点として記憶部12に格納される。

【0137】
隣接関係設定部18は、記憶部12に格納されたこれらの頂点の間に隣接関係を設定するための構成である。具体的には、各セルCに対応するセル点CPを始点とし、セルCを構成する面S1~S6に対応する面点SP1~SP6の各々を終点とする辺を設定する。また、セルCを構成する各面Sについて、面Sに対応する面点SPを始点とし、面Sを構成する辺E1~E4に対応する辺点E1~E4の各々を終点とする辺を設定する。

【0138】
境界セル位相構造判定部19は、境界セルCの位相構造が位相構造A1~A5の何れかに一致するか否かを、境界セル位相構造テーブル20を参照して判定する。この境界セル位相構造テーブル20には、位相構造A1~A5の各々について、その位相構造IDと、その位相構造とが互いに関連付けて登録されている。境界セル位相構造判定部19は、境界セルCの位相構造と一致する位相構造が境界セル位相構造テーブル20に登録されている場合、境界セルCの位相構造が位相構造A1~A5の何れかに一致する旨をセル点生成部14に通知すると共に、境界セル位相構造テーブル20において境界セルCの位相構造に関連付けられた位相構造IDをセル点生成用重み係数設定部21に通知する。

【0139】
セル点生成用重み係数設定部21は、セル点生成部14がセル点の生成に利用する8個の重み係数a~hを、セル点生成用重み係数テーブル22を参照して設定する。このセル点生成用重み係数テーブル22には、位相構造A1~A5の各々について、その位相構造IDと、その位相構造を有する境界セルを2次元に退化させることのない重み係数a~hとが互いに関連付けて登録されている(表3参照)。セル点生成用重み係数設定部21は、境界セル位相構造判定部19から通知された位相構造IDに関連付けられた重み係数a~hをセル点生成用重み係数テーブル22から読み出し、読み出した重み係数a~hをセル点生成部14に供給する。

【0140】
境界セル対位相構造判定部23は、境界セル対(C1,C2)の位相構造が位相構造B1~B4の何れかに一致するか否かを、境界セル対位相構造テーブル24を参照して判定する。この境界セル対位相構造テーブル24には、位相構造B1~B4の各々について、その位相構造IDと、その位相構造とが互いに関連付けて登録されている。境界セル対位相構造判定部23は、境界セル対(C1,C2)の位相構造と一致する位相構造が境界セル対位相構造テーブル24に登録されている場合、境界セル対(C1,C2)の位相構造が位相構造B1~B4の何れかに一致する旨を面点生成部15に通知すると共に、境界セル対位相構造テーブル24において境界セル対(C1,C2)の位相構造に関連付けられた位相構造IDを面点生成用重み係数設定部25に通知する。

【0141】
面点生成用重み係数設定部25は、面点生成部15が面点の生成に利用する12個の重み係数a’~l’を、面点生成用重み係数テーブル26を参照して設定する。この面点生成用重み係数テーブル26には、位相構造B1~B4の各々について、その位相構造IDと、その位相構造を有する境界セル対に挟まれた境界セル間面を1次元に退化させることのない重み係数a’~l’とが互いに関連付けて登録されている(表6参照)。面点生成用重み係数設定部25は、境界セル対構造判定部23から通知された位相構造IDに関連付けられた重み係数a’~l’を面点生成用重みテーブル26から読み出し、読み出した重み係数a’~l’を面点生成部15に供給する。

【0142】
なお、ボリュームメッシュMを構成する各セルCは、(1)セルCを構成する各頂点の頂点IDからなる頂点集合VS、(2)セルCを構成する各辺の辺情報からなる辺集合ES、(3)セルCを構成する各面の面情報からなる面集合FS、(4)セルCにおける境界点、境界辺、及び境界面の配置を示す境界情報BI、(5)セルCを構成する各頂点の位置座標からなる位置情報PIにより表現することができる。ここで、辺情報とは、その辺を構成する2つの頂点の頂点IDの集合のことを指し、面情報とは、その面を構成する4つの頂点の頂点IDの集合のことを指す。また、境界情報BIは、セルCを構成する境界点、境界辺、及び境界面の頂点ID、辺情報、及び面情報から構成することができる。

【0143】
例えば、図7(a)に示す境界セルの頂点集合VS、辺集合ES、面集合FS、及び境界情報BIは、以下のように与えられる:
VS={0,1,2,3,4,5,6,7}、
ES={(0,1),(0,3),(0,4),(1,2),(1,5),(2,3),(2,6),(3,7),(4,5),(4,7),(5,6),(6,7)}、
FS={(0,1,2,3),(0,4,5,1),(0,3,7,4),(1,5,6,2),(2,6,7,3),(4,5,6,7)}、
BI={0,1,2,3,5,7,(0,1),(0,3),(0,4),(1,2),(1,5),(2,3),(3,7),(4,5),(4,7),(0,1,2,3),(0,4,5,1),(0,3,7,4)}。

【0144】
ボリュームメッシュ細分割装置1は、頂点集合VS、辺集合ES、面集合FS、境界情報BI、及び位置情報PIを用いて上述した各処理を行う。特に、境界セル位相構造判定部19は、境界セルCに関する境界情報BIを用いて、境界セルCの位相構造が位相構造A1~A5の何れかに一致するか否かを判定する。また、境界セル対位相構造判定部23は、境界セル対(C1,C2)に関する境界情報対(BI1,BI2)を用いて、境界セル対(C1,C2)の位相構造が位相構造B1~B4の何れかに一致するか否かを判定する。

【0145】
この場合、境界セル位相構造テーブル20には、位相構造A1~A5の各々に対応する5つの境界情報BIAiが格納される(i=1,2,3,4,5)。そして、境界セル位相構造判定部19は、境界情報BIが頂点IDを振り直すことによって境界情報BIAiに一致する場合、境界セルCの位相構造が位相構造Aiと同一であると判定し、そうでない場合、境界セルCの位相構造が位相構造Aiと相違すると判定する。

【0146】
また、境界セル対位相構造テーブル24には、位相構造B1~B4の各々に対応する4つの境界情報対(BI1Bj,BI2Bj)が格納される(j=1,2,3,4)。そして、境界セル対位相構造判定部23は、境界情報対(C1,C2)が頂点IDを振り直すことによって境界情報対(BI1Bj,BI2Bj)に一致する場合、境界セル対(C1,C2)の位相構造が位相構造Bjと同一であると判定し、そうでない場合、境界セル対(C1,C2)の位相構造が位相構造Bjと相違すると判定する。

【0147】
なお、境界情報BIの一致/不一致に基づいて境界セル及び境界セル対の位相構造の同異を判定することができるのは、ボリュームメッシュを構成する全てのセルが六面体であるためである。ボリュームメッシュに六面体以外のセルが混在し得る場合には、境界情報BIに加え、頂点集合VS、辺集合ES、面集合FSの一致/不一致に基づいて境界セル及び境界セル対の位相構造の同異を判定する構成を採用すればよい。

【0148】
〔ボリュームメッシュ細分割装置の動作〕
次に、ボリュームメッシュ細分割装置1の動作について、図2を参照して説明する。図2(a)は、ボリュームメッシュ細分割装置1の動作の概要を示すフローチャートであり、図2(b)は、図2(a)に含まれるセル点生成処理の詳細を示すフローチャートであり、図2(c)は、図2(a)に含まれる面点生成処理の詳細を示すフローチャートである。

【0149】
ステップS0:データ取得部11がボリュームメッシュMを取得する。取得したボリュームメッシュMは、記憶部12に格納される。

【0150】
ステップS1:セル点生成部14が、上述したように、ボリュームメッシュMを構成する各セルに対応するセル点を生成する(セル点生成処理)。このセル点生成処理の詳細については後述する。

【0151】
ステップS2:面点生成部15が、上述したように、ボリュームメッシュMを構成する各面に対応する面点を生成する(面点生成処理)。この面点生成処理の詳細については後述する。

【0152】
ステップS3:辺点生成部16が、上述したように、ボリュームメッシュMを構成する各辺に対応する辺点を生成する(辺点生成処理)。この辺点生成処理は、従来の辺点生成処理と同様に実現されるので、これ以上の説明は割愛する。

【0153】
ステップS4:隣接関係設定部18が、上述したように、ステップS1にて生成された各セル点を始点とする新辺を生成する(セル点を始点とする新辺生成処理)。セル点CPを始点とするこの新辺生成処理は、従来の新辺生成処理と同様に実現されるので、これ以上の説明は割愛する。

【0154】
ステップS5:隣接関係設定部18が、上述したように、ステップS2にて生成された各面点SPを始点とする新辺を生成する(面点を始点とする新辺生成処理)。面点SPを始点とするこの新辺生成処理は、従来の新辺生成処理と同様に実現されるので、これ以上の説明は割愛する。

【0155】
ステップS6:隣接関係設定部18が、上述したように、ステップS3にて生成された各辺点EPを始点とする新辺を生成する(辺点を始点とする新辺生成処理)。辺点EPを始点とするこの新辺生成処理は、従来の新辺生成処理と同様に実現されるので、これ以上の説明は割愛する。

【0156】
ステップS7:頂点移動部17が、上述したように、ボリュームメッシュを構成する各頂点を移動する(頂点移動処理)。この頂点移動処理は、従来の頂点移動処理と同様に実現されるので、これ以上の説明は割愛する。

【0157】
セル点生成処理S1は、図2(b)に示す各ステップにより構成することができる。セル点生成処理S1を構成する各ステップについて説明すれば以下のとおりである。

【0158】
ステップS11:セル点生成部14は、処理対象セルCが境界セルであるか否かを判定する。

【0159】
ステップS12:処理対象セルCが境界セルである場合(ステップS11:Yes)、境界セル位相構造判定部19は、処理対象セルCの位相構造が境界セル位相構造テーブル20に登録された位相構造A1~A5の何れかに一致するか否かを判定する。

【0160】
ステップS13:処理対象セルCが境界セルでない場合(ステップS11:No)、又は、処理対象セルCの位相構造が位相構造A1~A5の何れにも一致しない場合(ステップS12:No)、セル点生成部14は、従来のセル点生成規則CP=(v0+v1+…+v7)/8に従ってセル点CPを生成する。

【0161】
ステップS14:処理対象セルCの位相構造が位相構造A1~A5の何れかに一致する場合(ステップS12:Yes)、セル点生成用重み係数設定部21は、処理対象セルCの位相構造に対応する重み係数a~hをセル点生成用重み係数テーブル22から読み出し、セル点生成部14に供給する。セル点生成部14は、この重み係数a~hを用いて、セル点生成規則CP=a・v0+b・v1+c・v2+d・v3+e・v4+f・v5+g・v6+h・v7に従ってセル点CPを生成する。

【0162】
面点生成処理S2は、図2(c)に示す各ステップにより構成することができる。面点生成処理S2を構成する各ステップについて説明すれば以下のとおりである。

【0163】
ステップS21:面点生成部15は、処理対象面Sが境界面であるか否かを判定する。

【0164】
ステップS22:処理対象面Sが境界面でない場合、面点生成部15は、Catmall-Clarkの表面細分割法に従って面点SPを生成する。

【0165】
ステップS23:処理対象面Sが境界面である場合、面点生成部15は、処理対象面Sを介して互いに隣接するセル対(C1,C2)が境界セル対であるか否かを判定する。

【0166】
ステップS24:処理対象面Sを介して互いに隣接するセル対(C1,C2)が境界セル対である場合(ステップS23:Yes)、境界セル対位相構造判定部23は、セル対(C1,C2)の位相構造が境界セル対位相構造テーブル24に登録された位相構造B1~B4の何れかに一致するか否かを判定する。

【0167】
ステップS25:セル対(C1,C2)が境界セル対でない場合(ステップS23:No)、又は、セル対(C1,C2)の位相構造が位相構造B1~B4の何れにも一致しない場合(ステップS24:No)、面点生成部15は、従来の面点生成規則SP=(3/4)α+(1/4)βに従って面点SPを生成する(α及びβの定義は上述したとおり)。

【0168】
ステップS26:セル対(C1,C2)の位相構造が位相構造B1~B4の何れかに一致する場合(ステップS24:Yes)、セル対(C1,C2)の位相構造に対応する重み係数a’~l’を面点生成用重み係数テーブル26から読み出し、面点生成部15に供給する。面点生成部15は、この重み係数a’~l’を用いて、面点生成規則SP=a・v0+b’・v1+c’・v2+d’・v3+e’・v4+f’・v5+g’・v6+h’・v7+i’・v8+j’・v9+k’・v10+l’・v11に従って面点SPを生成する。

【0169】
〔ボリュームメッシュ細分割装置の構成例〕
ボリュームメッシュ細分割装置1は、コンピュータ(電子計算機)を用いて構成することができる。図2は、ボリュームメッシュ細分割装置1として利用可能なコンピュータ100の構成を例示したブロック図である。

【0170】
コンピュータ100は、図2に示したように、バス110を介して互いに接続された演算装置120と、主記憶装置130と、補助記憶装置140と、入出力インタフェース150とを備えている。演算装置120として利用可能なデバイスとしては、CPU(Central Processing Unit)を挙げることができる。また、主記憶装置130として利用可能なデバイスとしては、例えば、半導体RAM(random access memory)を挙げることができる。また、補助記憶装置140として利用可能なデバイスとしては、例えば、ハードディスクドライブを挙げることができる。

【0171】
入出力インタフェース150には、図2に示したように、入力装置200及び出力装置300が接続される。入力装置200としては、キーボードやマウス、出力装置300としては、ディスプレイ装置が一般的である。キーボードやマウスは、細分割回数の設定等に利用することができる。また、ディスプレイ装置は、細分割前後のボリュームメッシュを表示するために利用することができる。

【0172】
補助記憶装置140には、コンピュータ100をボリュームメッシュ細分割装置1として動作させるための各種プログラムが格納されている。具体的には、データ取得プログラム、データ出力プログラム、セル点生成プログラム、面点生成プログラム、辺点生成プログラム、頂点移動プログラム、隣接関係設定プログラム、境界セル位相構造判定プログラム、セル点生成用重み係数設定プログラム、境界セル対位相構造判定プログラム、及び、面点生成用重み係数設定プログラムが格納されている。また、補助記憶装置140は、境界セル位相構造テーブル20、セル点生成用重み係数テーブル22、境界セル対位相構造テーブル24、面点生成用重み係数テーブル26とを格納するテーブル格納部30としても利用される。

【0173】
演算装置120は、補助記憶装置140に格納された上記各プログラムを主記憶装置130上に展開し、主記憶装置130上に展開された上記各プログラムに含まれる命令を実行することによって、コンピュータ100を、データ取得部11、データ出力部13、セル点生成部14、面点生成部15、辺点生成部16、頂点移動部17、隣接関係設定部18、境界セル位相構造判定部19、セル点生成用重み係数設定部21、境界セル対位相構造判定部23、面点生成用重み係数設定部25として機能させる。主記憶装置130は、図1に示した記憶部12としても機能する。すなわち、演算装置120が参照する細分割前のボリュームメッシュM及び細分割後のボリュームメッシュM’は、この主記憶装置130に格納される。

【0174】
〔Catmall-Clarkのボリューム細分割法との併用〕
以上、境界セルについてヤコビアンがk→∞の極限で0に収束するという事態を回避するセル点の生成規則を用いた細分割法について説明したが、当該細分割法は、Catmall-Clarkのボリューム細分割法と併用してもよい。

【0175】
例えば、境界セルについて、Catmall-Clarkのボリューム細分割法を用いて導出したセル点をCP_Cと表し、上述したセル点の生成規則を用いた細分割法を用いて導出したセル点をCP_Aと表すことにすると、セル点CP_Cとセル点CP_Aとの、ステップ数kに依存した重み付き平均
k×CP_C+(1-Wk)×CP_A
を当該境界セルについてのセル点に設定してもよい。このようにセル点CP_Cとセル点CP_Aとのステップ数kに依存した重み付き平均を用いて境界セルについてのセル点を導出する方法を非定常スキームと呼ぶこともある。上記の式において、Wは、ステップ数kに依存しないパラメータであり、0<W<1を満たす。また、Wの最適値は実験的により求めることができ、例えば、W=9/10と定められる。上記の式から明らかなように、ステップ数kが小さいときには、Catmall-Clarkのボリューム細分割法を用いて導出したセル点CP_Cの寄与が大きく、ステップ数kが大きくなるに従って、上述したセル点の生成規則を用いた細分割法を用いて導出したセル点CP_Aの寄与が大きくなる。

【0176】
上述したセル点の生成規則を用いた細分割法は、ステップ数が大きくなるに従って、その有効性が増すという傾向があるため、上記のようなステップ数kに依存した重み付き平均を用いることによって、Catmall-Clarkのボリューム細分割法および上述したセル点の生成規則を用いた細分割法の双方のメリットを併せ持つボリューム細分割が実現できる。

【0177】
〔実験結果〕
以下では、上述したセル点の生成規則を用いた細分割法により得られた実験結果について、Catmall-Clarkのボリューム細分割法のみを用いて得られた実験結果と比較しつつ説明する。図8は、ベアリングの形状をボリューム細分割した実験の結果を示すものであり、(a)は、初期ボリュームメッシュを示しており、(b)は、上述したセル点の生成規則を用いたボリューム細分割を複数ステップ行った後の、ベアリングのコーナー部分についてのボリュームメッシュの状態を示しており、(c)は、Catmall-Clarkのボリューム細分割法、表2に示した等方的(アイソメトリック)重み係数を用いたボリューム細分割法、および、表3に示した非等方的(アニソメトリック)重み係数を用いたボリューム細分割法のそれぞれについて、各ステップにおけるスケールドヤコビアン(正規化されたヤコビアン)の値を示している。なお、図8(b)においては、各セルは縮小表示されている。また、図8(c)における「全境界以外の最小」および「全境界以外の平均」とは、ボリュームメッシュに含まれるセルのうち、3つの境界辺からなる境界セル以外のセルについてのスケールドヤコビアンの最小値および平均値を示しており、「全平均」とは、ボリュームメッシュに含まれる全てのセルについてのスケールドヤコビアンの平均値を表している。

【0178】
図8(c)に示すように、アイソメトリックおよびアニソメトリックの双方における「全境界以外の最小」は、Catmall-Clarkのボリューム細分割法における「全境界以外の最小」よりも大きい。また、Catmall-Clarkのボリューム細分割法における「全境界以外の最小」は、ステップ数が増すにつれて急速に0に近づく傾向があるが、アイソメトリックおよびアニソメトリックの双方における「全境界以外の最小」は、0への近づき方がCatmall-Clarkのボリューム細分割法よりもなだらかである。したがって、アイソメトリックおよびアニソメトリックの双方において、Catmall-Clarkのボリューム細分割法よりも平面的なセルが生じにくくなっている。

【0179】
また、図8(b)に示すように、平面的なセルが生じ易いコーナー部分においても、境界セルの体積は、他のセルの体積と大差がない。このことからも、上述したセル点の生成規則を用いたボリューム細分割により、平面的なセルが生じにくくなっていることが分かる。

【0180】
図9は、他の形状をボリューム細分割した実験の結果を示すものであり、(a)は、当該他の形状についての初期ボリュームメッシュを示しており、(b)は、Catmall-Clarkのボリューム細分割法、アイソメトリック、および、アニソメトリックのそれぞれについて、各ステップにおけるスケールドヤコビアンの値を示している。

【0181】
図9(b)は、図8(c)と同様に、アイソメトリックおよびアニソメトリックの双方において、Catmall-Clarkのボリューム細分割法よりも平面的なセルが生じにくくなっていることを示している。

【0182】
また、図8(c)および図9(b)から読み取れるように、等方的(アイソメトリック)な重み係数を用いた方が、非等方的(アニソメトリック)な重み係数を用いるよりも、平面的なセルが生じにくくなるという傾向がある。

【0183】
(付記事項)
本実施形態に係るボリュームメッシュ細分割法は、Catmall-Clarkのボリューム細分割法をベースにしたものにあるが、ベースとするボリューム細分割法はこれに限定されない。すなわち、例えば、4面体セルからなるボリュームメッシュを細分割する細分割法など、任意のボリューム細分割法をベースとして、2次元に退化する境界セルが生じることのないボリューム細分割法を実現することができる。
【産業上の利用可能性】
【0184】
本発明は、有限要素法に用いられるボリュームメッシュを生成するためのボリュームメッシュ細分割装置に好適に用いることができる。
【符号の説明】
【0185】
1 ボリュームメッシュ細分割装置
11 データ取得部
12 記憶部
13 データ出力部
14 セル点生成部(セル点生成手段)
15 面点生成部(面点生成手段)
16 辺点生成部
17 頂点移動部
18 隣接関係設定部
19 境界セル位相構造判定部(境界セル位相構造判定手段)
20 境界セル位相構造テーブル
21 セル点生成用重み係数設定部
22 セル点生成用重み係数テーブル
23 境界セル対位相構造判定部(境界セル対位相構造判定手段)
24 境界セル対位相構造テーブル
25 面点生成用重み係数設定部
26 面点生成用重み係数テーブル
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12