(57)【要約】    【課題】  コンピュータ・シミュレーションの形状データを用いて階層的格子上で界面近傍の場所の図形を、低減された計算コストで所望の解像度で表現することができる階層的格子生成方法を提供する。    【解決手段】  各格子の胞と頂点との双対性を利用し、頂点が属する胞内で関数の値が負と正の値両方を混合して持つ場合、その頂点に値−１を与え、そうでない場合、値１を与えるという操作を全頂点に対して行う。この後、胞に着目し、胞に属する頂点が値−１を含む場合、胞をより細かい格子に分割するという操作を繰り返すことにより、界面近傍をより詳細に表現する階層的格子を得る。【選択図】      図１３
2005275614.tif 000002
【特許請求の範囲】
【請求項１】
所定の領域内に存在する、頂点および線分を構成要素とする胞の集合に対し、解像度に応じて、前記胞を分割して階層的格子を生成する工程を有し、前記領域内に用意された界面図形に対して該界面近傍の胞を階層的に分割することによって前記界面図形を前記階層的格子で表現する階層的格子生成方法において、
初期状態において、前記領域内の全ての頂点に第１の値を付与する第１の工程と、
前記第１の値または第２の値を保持している全ての頂点のうち着目した頂点の各々について、該着目した頂点が属する胞のうち、いずれかが前記界面図形を含む場合、前記着目した頂点に前記第２の値を付与し、そうでない場合、前記着目した頂点に第３の値を付与する第２の工程と、
前記領域内の全ての胞に対し、前記第２の値を保持している前記頂点が属する胞を分割し、この分割されることによって新たに生じた頂点を中点とする線分の両端の頂点に保持されている値が、共に前記第３の値である場合、前記新たに生じた頂点に当該第３の値を付与し、そうでない場合、前記新たに生じた頂点に前記第１の値を付与する第３の工程とを有することを特徴とする階層的格子生成方法。
【請求項２】
所定の領域内に存在する、頂点および線分を構成要素とする胞の集合に対し、解像度に応じて、前記胞を分割して階層的格子を生成する工程を有し、前記領域内に用意された界面図形に対して該界面近傍の胞を階層的に分割することによって前記界面図形を前記階層的格子で表現する階層的格子生成方法において、
前記領域全体に界面の内側であれば正の値、外側であれば負の値を持つ関数が予め用意されており、
初期状態において、前記領域内の全ての頂点に第１の値を付与する第１の工程と、
前記第１の値または第２の値を保持している全ての頂点のうち着目した頂点の各々について、該着目した頂点が属する胞のうち、いずれかの胞内で関数の値が負と正の値両方を混合して持つ場合、該着目した頂点に前記第２の値を付与し、そうでない場合、前記着目した頂点に第３の値を付与する第２の工程と、
前記領域内の全ての胞に対し、前記第２の値を保持している前記頂点が属する胞を分割し、この分割されることによって新たに生じた頂点を中点とする線分の両端の頂点に保持されている値が、共に前記第３の値である場合、前記新たに生じた頂点に前記第３の値を付与し、そうでない場合、前記新たに生じた頂点に前記第１の値を付与する第３の工程とを有することを特徴とする階層的格子生成方法。
【請求項３】
前記第３の工程を行った後、任意の複数の胞が含む頂点のうち前記第３の値を保持しかつ消滅可能な頂点に着目し、前記任意の複数の胞に属する全ての頂点が前記第３の値を保持する場合、前記着目した頂点を消滅させ、前記任意の複数の胞を少なくとも１つに統合する第４の工程を有することを特徴とする請求項１または２記載の階層的格子生成方法。
【請求項４】
前記領域内の最高解像度が所定の解像度になるまで、前記第２の工程および前記第３の工程を、この順で繰り返し行うことを特徴とする請求項１または２記載の階層的格子生成方法。
【請求項５】
前記領域内の最高解像度が所定の解像度になるまで、前記第２の工程、前記第３の工程および前記第４の工程を、この順で繰り返し行うことを特徴とする請求項３記載の階層的格子生成方法。
【請求項６】
前記胞は多角形状を有することを特徴とする請求項１、２または３記載の階層的格子生成方法。
【請求項７】
前記胞は立方体であることを特徴とする請求項１、２または３記載の階層的格子生成方法。
【請求項８】
所定の領域内に存在する、頂点および線分を構成要素とする胞の集合に対し、解像度に応じて、前記胞を分割して階層的格子を生成する手段を有し、前記領域内に用意された界面図形に対して該界面近傍の胞を階層的に分割することによって前記界面図形を前記階層的格子で表現する階層的格子生成装置において、
初期状態において、前記領域内の全ての頂点に第１の値を付与する第１の付与手段と、
前記第１の値または第２の値を保持している全ての頂点のうち着目した頂点の各々について、該着目した頂点が属する胞のいずれかが前記界面図形を含む場合、前記着目した頂点に前記第２の値を付与し、そうでない場合、前記着目した頂点に第３の値を付与する第２の付与手段と、
前記領域内の全ての胞に対し、前記第２の値を保持している前記頂点が属する胞を分割し、この分割されることによって新たに生じた頂点を中点とする線分の両端の頂点に保持されている値が、共に前記第３の値である場合、前記新たに生じた頂点に当該第３の値を付与し、そうでない場合、前記新たに生じた頂点に前記第１の値を付与する第３の付与手段とを備えたことを特徴とする階層的格子生成装置。
【請求項９】
所定の領域内に存在する、頂点および線分を構成要素とする胞の集合に対し、解像度に応じて、前記胞を分割して階層的格子を生成する生成手段を有し、前記領域内に用意された界面図形に対して該界面近傍の胞を階層的に分割することによって前記界面図形を前記階層的格子で表現する階層的格子生成装置において、
前記領域全体に界面の内側であれば正の値、外側であれば負の値を持つ関数が予め用意されており、
初期状態において、前記領域内の全ての頂点に第１の値を付与する第１の付与手段と、
前記第１の値または第２の値を保持している全ての頂点のうち着目した頂点の各々について、該着目した頂点が属する胞のうち、いずれかの胞内で関数の値が負と正の値両方を混合して持つ場合、前記着目した頂点に前記第２の値を付与し、そうでない場合、前記着目した頂点に第３の値を付与する第２の付与手段と、
前記領域内の全ての胞に対し、前記第２の値を保持している前記頂点が属する胞を分割し、この分割されることによって新たに生じた頂点を中点とする線分の両端の頂点に保持されている値が、共に前記第３の値である場合、前記新たに生じた頂点に前記第３の値を付与し、そうでない場合、前記新たに生じた頂点に前記第１の値を付与する第３の付与手段とを備えたことを特徴とする階層的格子生成装置。
【請求項１０】
前記第３の付与手段による処理後、任意の複数の胞が含む頂点のうち前記第３の値を保持しかつ消滅可能な頂点に着目し、前記任意の複数の胞に属する全ての頂点が前記第３の値を保持する場合、前記着目した頂点を消滅させ、前記任意の複数の胞を少なくとも１つに統合する統合手段を備えたことを特徴とする請求項８または９記載の階層的格子生成装置。
【請求項１１】
前記領域内の最高解像度が所定の解像度になるまで、前記第２の付与手段および前記第３の付与手段による処理を、この順で繰り返し実行することを特徴とする請求項８または９記載の階層的格子生成装置。
【請求項１２】
前記領域内の最高解像度が所定の解像度になるまで、前記第２の付与手段、前記第３の付与手段および前記統合手段による処理を、この順で繰り返し実行することを特徴とする請求項１０記載の階層的格子生成装置。
【請求項１３】
前記胞は多角形状を有することを特徴とする請求項８、９または１０記載の階層的格子生成装置。
【請求項１４】
前記胞は立方体であることを特徴とする請求項８、９または１０記載の階層的格子生成装置。
【請求項１５】
請求項１乃至７のいずれかに記載の階層的格子生成方法を実現するためのプログラムコードを有するプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ・シミュレーションを実行する際に、所望の解像度に応じ、物体の境界部分において階層的格子を生成する階層的格子生成方法、階層的格子生成装置およびプログラムに関する。
【背景技術】
【０００２】
現在、階層的格子(Hierarchical Lattice)を利用する多くのコンピュータ・シミュレータが開発されている（例えば、非特許文献１参照）。この非特許文献１およびその参考文献には、上述したようなコンピュータ・シミュレータが詳しく述べられている。
【０００３】
これらの刊行物には、高い解像度によって表現したい物体の界面近傍の場所において、当該場所の解像度（階層）を自由に上げて表現できる仕組みが示されている。この仕組みでは、物体の界面近傍の場所を数学的にフィルタ空間と呼ばれるもので構成することによって上述した解像度を適切に定義できる。同様の仕組みは、物体の表現方法としてコンピュータ・グラフィックの分野でも提案されている（例えば、特許文献１〜３参照）。
【０００４】
多くのコンピュータ・シミュレーションを行う際、物体の形状、特にその物体における境界部分の形状を入力する必要がある。当該境界部分における界面は余次元（codimension）１のものである場合が多い。例えば、２次元面内で行われるシミュレーションにおいて、界面は曲線あるいは区分的線形図形としての折れ線によって構成される。また、３次元空間内で行われるシミュレーションにおいて、界面は２次元曲面や区分的に平面で構成された曲面によって構成される。
【０００５】
これらの界面を含む境界部分は、コンピュータ・シミュレーションにおいて、偏微分方程式の境界条件を付与する領域として重要な役割を果たすことが多い。よって、これらの境界部分は、階層の深い（細かい）格子で表現されるべきである。例えば、前述した非特許文献１では、レベルセット法（Level Set Method）と呼ばれる手法を利用することによって所望の精度で境界部分の解像度を上げる計算方法が提案されている。このStrainが提案するレベルセット法を以下に簡単に示す。
【０００６】
レベルセット法は、例えば、下記の非特許文献２にその詳細が示されている。
【０００７】
レベルセット法とは、余次元１の界面に垂直方向な領域内において自然な距離に基づいて定まる座標を設定し、当該座標の値を領域内のスカラー関数とみなす方法である。数学的には、界面が十分滑らかである場合、界面の管状近傍（Tubular Neighborhoods）では、法線束（Normal Bundle）と管状近傍とが微分同相(diffeomophism)であることを根拠とする。
【０００８】
慣例として、レベルセット法では、垂直座標のゼロ点を界面上に設定する。一般に、数学的には、界面から十分離れた点において垂直座標は意味を持たなくなるが、レベルセット関数はそのような数学的詳細を考慮することなく、数値計算的に決まる値を座標値としている。このように、レベルセット法は、一般に非常に粗く且つ解釈による任意性があるが、ユークリッド空間内の十分滑らかな界面に対しては十分に実用的な方法である。Strainの方法とは、このレベルセット関数の大きさ（即ち、余次元法線方向の界面からの距離）に応じて、解像度を変える方法のことである。
【０００９】
また、特許文献１〜３では、コンピュータグラフィックの分野においても、解像度の向上方法として、同様に、距離関数を用いて解像度を向上する方法が提案されている。これらの方法の基本的な考え方はStrainとほぼ同一である。
【００１０】
但し、特許文献２では、解像度の昇降に関連する物体の界面近傍の場所が数学的なフィルタ空間になっていないので、Strain等を始めとするシミュレーション分野の解像度空間（階層性のある空間）とは異なる。
【００１１】
一般に、レベルセット関数を求める際には、余次元法線方向の界面からの距離を計算することになる。Strainはレベルセット関数を求める際に、区分的線分曲線からの距離を計算している。
【特許文献１】特開平６−２１５０７６号公報
【特許文献２】特開平９−１９８５２４号公報
【特許文献３】特開２００１−５２２０６号公報
【非特許文献１】John Strain, "Fast Tree-Based Resistanting for Level Set Computations", Journal of Computational Physics 152, p.664-686(1999) Michael Griebel, Gerhard Zumbusch, "Parallel adaptive subspace correction schemes with applications to elasticity" Computer Methods in applied mechanics and engineering 184 p.303-332(2000)
【非特許文献２】J.A.Sethian "Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry Fluid Mechanics, Computer Vision, and Materials Science" Cambridge University Press(1996)
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、計算機での距離の計算は計算コストが一般に高く、浮動小数点演算には様々な不都合が生じることが知られている。よって、距離計算を含むアルゴリズムは同様の問題を含むこととなる。
【００１３】
そこで、本発明は、コンピュータ・シミュレーションの形状データを用いて階層的格子上で界面近傍の場所の図形を、低減された計算コストで所望の解像度で表現することができる階層的格子生成方法、階層的格子生成装置およびプログラムを提供することを目的とする。
【００１４】
また、本発明が扱う課題は、コンピュータグラフィックス分野の課題と共通するものがあり、同様な課題に対しては同様な解決を与えるものである。
【課題を解決するための手段】
【００１５】
上記目的を達成するために、本発明の階層的格子生成方法は、所定の領域内に存在する、頂点および線分を構成要素とする胞の集合に対し、解像度に応じて、前記胞を分割して階層的格子を生成する工程を有し、前記領域内に用意された界面図形に対して該界面近傍の胞を階層的に分割することによって前記界面図形を前記階層的格子で表現する階層的格子生成方法において、初期状態において、前記領域内の全ての頂点に第１の値を付与する第１の工程と、前記第１の値または第２の値を保持している全ての頂点のうち着目した頂点の各々について、該着目した頂点が属する胞のうち、いずれかが前記界面図形を含む場合、前記着目した頂点に前記第２の値を付与し、そうでない場合、前記着目した頂点に第３の値を付与する第２の工程と、前記領域内の全ての胞に対し、前記第２の値を保持している前記頂点が属する胞を分割し、この分割されることによって新たに生じた頂点を中点とする線分の両端の頂点に保持されている値が、共に前記第３の値である場合、前記新たに生じた頂点に当該第３の値を付与し、そうでない場合、前記新たに生じた頂点に前記第１の値を付与する第３の工程とを有することを特徴とする。
【００１６】
本発明の階層的格子生成方法は、所定の領域内に存在する、頂点および線分を構成要素とする胞の集合に対し、解像度に応じて、前記胞を分割して階層的格子を生成する工程を有し、前記領域内に用意された界面図形に対して該界面近傍の胞を階層的に分割することによって前記界面図形を前記階層的格子で表現する階層的格子生成方法において、前記領域全体に界面の内側であれば正の値、外側であれば負の値を持つ関数が予め用意されており、初期状態において、前記領域内の全ての頂点に第１の値を付与する第１の工程と、前記第１の値または第２の値を保持している全ての頂点のうち着目した頂点の各々について、該着目した頂点が属する胞のうち、いずれかの胞内で関数の値が負と正の値両方を混合して持つ場合、該着目した頂点に前記第２の値を付与し、そうでない場合、前記着目した頂点に第３の値を付与する第２の工程と、前記領域内の全ての胞に対し、前記第２の値を保持している前記頂点が属する胞を分割し、この分割されることによって新たに生じた頂点を中点とする線分の両端の頂点に保持されている値が、共に前記第３の値である場合、前記新たに生じた頂点に前記第３の値を付与し、そうでない場合、前記新たに生じた頂点に前記第１の値を付与する第３の工程とを有することを特徴とする。
【００１７】
また、前記第３の工程を行った後、任意の複数の胞が含む頂点のうち前記第３の値を保持しかつ消滅可能な頂点に着目し、前記任意の複数の胞に属する全ての頂点が前記第３の値を保持する場合、前記着目した頂点を消滅させ、前記任意の複数の胞を少なくとも１つに統合する第４の工程を有することを特徴とする。
【００１８】
本発明の階層的格子生成装置は、所定の領域内に存在する、頂点および線分を構成要素とする胞の集合に対し、解像度に応じて、前記胞を分割して階層的格子を生成する手段を有し、前記領域内に用意された界面図形に対して該界面近傍の胞を階層的に分割することによって前記界面図形を前記階層的格子で表現する階層的格子生成装置において、初期状態において、前記領域内の全ての頂点に第１の値を付与する第１の付与手段と、前記第１の値または第２の値を保持している全ての頂点のうち着目した頂点の各々について、該着目した頂点が属する胞のいずれかが前記界面図形を含む場合、前記着目した頂点に前記第２の値を付与し、そうでない場合、前記着目した頂点に第３の値を付与する第２の付与手段と、前記領域内の全ての胞に対し、前記第２の値を保持している前記頂点が属する胞を分割し、この分割されることによって新たに生じた頂点を中点とする線分の両端の頂点に保持されている値が、共に前記第３の値である場合、前記新たに生じた頂点に当該第３の値を付与し、そうでない場合、前記新たに生じた頂点に前記第１の値を付与する第３の付与手段とを備えたことを特徴とする。
【００１９】
本発明の階層的格子生成装置は、所定の領域内に存在する、頂点および線分を構成要素とする胞の集合に対し、解像度に応じて、前記胞を分割して階層的格子を生成する生成手段を有し、前記領域内に用意された界面図形に対して該界面近傍の胞を階層的に分割することによって前記界面図形を前記階層的格子で表現する階層的格子生成装置において、前記領域全体に界面の内側であれば正の値、外側であれば負の値を持つ関数が予め用意されており、初期状態において、前記領域内の全ての頂点に第１の値を付与する第１の付与手段と、前記第１の値または第２の値を保持している全ての頂点のうち着目した頂点の各々について、該着目した頂点が属する胞のうち、いずれかの胞内で関数の値が負と正の値両方を混合して持つ場合、前記着目した頂点に前記第２の値を付与し、そうでない場合、前記着目した頂点に第３の値を付与する第２の付与手段と、前記領域内の全ての胞に対し、前記第２の値を保持している前記頂点が属する胞を分割し、この分割されることによって新たに生じた頂点を中点とする線分の両端の頂点に保持されている値が、共に前記第３の値である場合、前記新たに生じた頂点に前記第３の値を付与し、そうでない場合、前記新たに生じた頂点に前記第１の値を付与する第３の付与手段とを備えたことを特徴とする。
【００２０】
また、前記第３の付与手段による処理後、任意の複数の胞が含む頂点のうち前記第３の値を保持しかつ消滅可能な頂点に着目し、前記任意の複数の胞に属する全ての頂点が前記第３の値を保持する場合、前記着目した頂点を消滅させ、前記任意の複数の胞を少なくとも１つに統合する統合手段を備えたことを特徴とする。
【発明の効果】
【００２１】
本発明によれば、コンピュータ・シミュレーションの形状データを用いて階層的格子上で界面近傍の場所の図形を段階的に変更可能な所望の解像度で精確に表現することができる。また、階層的格子は、自分の格子内により小さい格子を内包しているか否かの２値情報で構成されたデジタルなものであるので、整数値情報だけを利用した計算方法によって、形状を表現でき、階層的格子の生成過程がデジタル的な計算のみによるロバストな生成方法となっているため、計算コストを削減できると共に浮動小数点計算に伴う様々な不都合を回避できる。また、コンピュータグラフィックス等のコンピュータによる物体の表現においても同様な効果を与えることができる。
【発明を実施するための最良の形態】
【００２２】
本発明の実施の形態について図面を参照しながら説明する。
【００２３】
［第１の実施形態］
図１は第１の実施形態における階層的格子生成方法が適用される計算機システムの構成を示す図である。この計算機システムは、計算機本体１１１、ディスプレイ１１２、キーボード１１５およびマウス１１４から構成される。図２は計算機本体１１１の構成を示すブロック図である。計算機本体１１１には、ＣＰＵ１１６、メモリ１１８、ハードディスク１１７、およびフロッピー（登録商標）ディスク（フレキシブルディスク）１１０が挿入されるフロッピー（登録商標）ディスクドライブ１１３が設けられている。
【００２４】
本実施形態では、界面表現アルゴリズムを実装した実行用ファイルがハードディスク１１７あるいはフレキシブルディスク１１０に予め格納されており、キーボード１１５あるいはマウス１１４等の入力装置からの信号によりメモリ１１８上にロードされると、界面表現アルゴリズムが実行される。ここでは、界面表現アルゴリズムのみに言及するが、他のアルゴリズムも、計算機本体１１１内のＣＰＵ１１６やメモリ１１８を用いて実行される。
【００２５】
本実施形態では、頂点、および線分を構成要素とする、多面体あるいは多角形の胞によって構成される階層的格子に、予め２次元あるいは１次元の界面図形が含まれている。
【００２６】
図３は界面表現アルゴリズムを実行する際の処理手順を示すフローチャートである。この処理プログラムの実行用ファイルは、前述したように、ハードディスク１１７あるいはフレキシブルディスク１１０に格納されており、ＣＰＵ１１６によって実行される。
【００２７】
まず、初期化処理として、階層的格子内の処理すべき領域内の格子形状を持った基本格子の全ての頂点に値０を付与する（ステップＳ１）。この後、所望の解像度の階層的格子となるまで、後述する２つの操作Ａ、Ｂを繰り返し行うことによって（ステップＳ２〜Ｓ１９）、界面図形を階層的格子で表現する。
【００２８】
ステップＳ２〜Ｓ８における操作Ａでは、全格子の最初の頂点に着目し（ステップＳ２）、着目頂点の保持している値が１未満であり（ステップＳ３でＹＥＳ）、着目頂点を含む胞のいずれかが界面を含む場合（ステップＳ４でＹＥＳ）、これらの頂点に値−１を付与し（ステップＳ５）、そうでない場合（ステップＳ４でＮＯ）、値１を付与する操作を行う（ステップＳ６）。これを全頂点について順次行なう（ステップＳ７〜８）また、ステップＳ９〜Ｓ１９における操作Ｂでは、領域内の最初の胞に着目し（ステップＳ９）、この胞内のいずれかにおける少なくとも１つの頂点が値−１を保持している場合（ステップＳ１０でＹＥＳ）、この胞を分割し（ステップＳ１１）、この分割によって新たに生じた１つの頂点に着目し（ステップＳ１２）、この頂点を中点とする線分の両端の頂点の値が共に値１である場合（ステップＳ１３でＹＥＳ）、新たに生じた頂点に値１を付与し（ステップＳ１４）、そうでない場合（ステップＳ１３でＮＯ）、値０を付与する操作を行う（ステップＳ１５）。ステップＳ１３〜１５を新たに生じた全頂点について順次行なう（ステップＳ１６〜１７）。そして、ステップＳ１０〜Ｓ１６を全ての胞について順次行なう（ステップＳ１８〜１９）。全ての胞と頂点をリナンバし（ステップＳ２０）、所定の解像度になれば（ステップＳ２１でＹＥＳ）、処理を終了する。所定の解像度でなければ、ステップＳ２に戻って処理を繰り返す。
【００２９】
具体的に、階層的格子として、２次元平面内の正方形で与えられた正方格子を基本とする場合を示す。階層的格子の生成は、計算機本体１１１内のＣＰＵ１１６によって実行され、階層的格子はメモリ１１８上に整数や浮動小数点の数の集合として構成される。そして、最終的に、後述する図５に示すような場所によって解像度の異なる階層的な正方格子が構成される。
【００３０】
図４は階層的格子の生成手順を示す図である。まず、図４（Ａ）に示す通常の正方格子を用意する。図４（Ａ）中、太線で示された界面１１が予め与えられている。本実施形態では、この界面１１は、区分的線分図形として与えられ、十分細かい１次元の頂点列によって構成されている。このため、胞が線分を内包するか否かの判断は、簡単のため、胞における頂点の内外判定によって行われるものとする。
【００３１】
この頂点の内外判定方法としては、例えば、特開平１１−１１０５６９号公報に記載の内点判定法を利用することができる。この内外判定は、凸多角形に対するものであり、正方格子に適用できる。すなわち、着目する点Ｐに対し、正方形を構成する点をＱ１、Ｑ２、Ｑ３、Ｑ４とすると、ベクトルＰＱ１とベクトルＰＱ２、ＰＱ３、ＰＱ４それぞれとの外積が全て同符号である場合、点Ｐは内点であり、そうでない場合、点Ｐは外点であるという事実によって判定を行うものである。このように、この内外判定は代数的な計算のみで行うことができる。この内外判定を使い、また、界面を表現する十分細かく細分化された１次元頂点列を利用すると、各正方格子（胞）が界面を含むか否かの判定を簡単に行うことができる。
【００３２】
すなわち、図３のステップＳ１において、全ての頂点に対し、その値を「０」にする。ステップＳ２〜Ｓ５の操作Ａにおいて、頂点の値が「１」未満の頂点に着目し、着目した頂点を含む胞のいずれかが界面を含む場合、この頂点に「−１」を与える。そうでない場合、この頂点に「１」を与える。全ての頂点に、この操作Ａを施した後、操作Ｂを行う。
【００３３】
ステップＳ６〜Ｓ１１の操作Ｂにおいて、全ての胞に着目し、着目した胞内の頂点のいずれかが値−１を保持する場合、この胞を分割する。この分割に際し、新たに生じた頂点に対し、この頂点を中点とする最小線分の両端の頂点の値が「１」である場合、値１を付与し、そうでない場合、値０を付与する。
【００３４】
ステップＳ１２において、当該領域内の最大の解像度が予め与えておいた所望の解像度であるか否かを判別し、所望の解像度である場合（ステップＳ１２でＹＥＳ）、この処理を終了する。一方、所望の解像度に達していない場合（ステップＳ１２でＮＯ）、ステップＳ２に戻り、操作Ａおよび操作Ｂを繰り返し行う。
【００３５】
図４（Ａ）は操作Ａを終えた状態を示す。ここで、図中、黒丸は値１を表し、白丸は値−１を表す。界面１１の周囲には、白丸が点在している。図４（Ｂ）は操作Ｂを終えた状態を示す。図４（Ａ）で白丸を含む胞は全て分割されている。図４（Ｂ）中、２重の白丸は値０を表している。操作Ｂによって新たに生じた頂点に対し、値１または値０が付与されていることがわかる。
【００３６】
図４（Ｃ）は図４（Ｂ）で示した新たな格子群に対し、改めて操作Ａを行った後の状態を示す。界面１１の周囲には、白丸が局在していることがわかる。ここで、図４（Ａ）における白丸の局在と、図４（Ｃ）における白丸の局在とでは、その解像度が異なっている。図４（Ｄ）は図４（Ｃ）に対し、操作Ｂを行った後の状態を示す。
【００３７】
このようにして、所定の領域内の最大解像度が所望の解像度となるまで、操作Ａおよび操作Ｂを繰り返す。
【００３８】
図５は操作Ａおよび操作Ｂを繰り返し行って所望の解像度に達した状態の階層的格子を示す図である。このように、階層的格子上で界面近傍を段階的に変更可能な所望の解像度でかつ精確に表現できる。
【００３９】
尚、上記実施形態では、正方形の胞を有する格子に適用した場合を示したが、本発明は胞の形状に依存しないので、種々の多角形の格子、例えば、三角格子、ランダム格子等に適用可能である。
【００４０】
図６は三角形の階層的格子を示す図である。同図（Ａ）は初期状態の三角格子を示し、同図（Ｂ）は図３の界面表現アルゴリズムを実行した後の階層的三角格子を示す。このように、界面３１は、階層的三角格子によって精確に所望の高解像度で表現される。
【００４１】
また、上記実施形態では、２次元の階層的格子の場合を示したが、本発明は次元に影響されないため、立方体胞によって構成される３次元の階層的格子にも適用できる。図７は３次元の階層的格子を示す図である。
【００４２】
このように、２次元の場合と同様の処理により、３次元の階層的格子を表現することができる。
【００４３】
更には、図３のステップＳ２〜Ｓ８において、頂点の値が１未満の頂点に着目して、それらの値をまず全て、＋２にした後に、＋２の値を持つ頂点を含むすべての胞に着目して、着目した胞が界面を含む場合は胞に属するすべての頂点に−１を与え、そうでない場合は何もしないという操作を胞全体に行い、その後に＋２を＋１に変更するということを行うとステップＳ２〜Ｓ８と同様の効果を得ることができる。このように、本発明の離散的アルゴリズムの実現においては様々な類似の実施方法が考えられる。
【００４４】
しかしながら、本発明の特徴は、ステップＳ２〜Ｓ８における「隣接胞の距離情報を含まない離散的情報を頂点に格納する」というステップと、ステップＳ９〜Ｓ１９における「自胞に属する頂点の値によって分割の判定を行う」というステップとの２つによって構成されていることにある。これらのステップを含む上記のような変形例は、本発明を構成することが理解できる。同時に、上記変形例の詳細な相違は本発明に影響を与えない。
【００４５】
［第２の実施形態］
第２の実施形態における計算機システムの構成は、第１の実施形態と同じであるので、その説明を省略する。ここでは、第１の実施形態と異なる界面表現アルゴリズムについてだけ説明する。
【００４６】
本実施形態では、第１の実施形態と同様、頂点、および線分を構成要素とする、多面体あるいは多角形の胞によって構成される階層的格子に対し、予め２次元あるいは１次元の界面図形が用意されている。図８は第２の実施形態における界面表現アルゴリズムを実行する際の処理手順を示すフローチャートである。この処理プログラムの実行用ファイルは、前述したように、ハードディスク１１７あるいはフレキシブルディスク１１０に格納されており、ＣＰＵ１１６によって実行される。
【００４７】
まず、初期化処理として、階層的格子内の処理すべき領域内の格子形状を持った基本格子の全ての頂点に値０を付与する（ステップＳ３１）。この後、所望の解像度の階層的格子となるまで、後述する３つの操作、つまり操作Ａ、操作Ｂおよび操作Ｃを繰り返し行うことによって（ステップＳ３２〜Ｓ５６）、界面図形を階層的格子で表現する。
【００４８】
ここで、ステップＳ３２〜Ｓ５０における操作Ａ、Ｂでは、図３につき上述したステップＳ２〜２０と同一の操作Ａ、Ｂを実行する。
【００４９】
さらに、ステップＳ５１〜Ｓ５６における操作Ｃでは、最初の頂点に着目し（ステップＳ５１）、胞に含まれる全ての頂点の値が「１」である場合（ステップＳ５２でＹＥＳ）、着目した頂点が消滅可能であれば（ステップＳ５３でＹＥＳ）、着目した消滅可能な頂点を消滅させる（ステップＳ５４）ことで、複数の胞を統合して階層を下げる、つまり解像度を緩めるという操作を行う。この操作を全頂点について順次繰り返す（ステップＳ５５〜５６）。全ての胞と頂点をリナンバし（ステップＳ５７）、所定の解像度になれば（ステップＳ５８でＹＥＳ）、処理を終了する。所定の解像度でなければ、ステップＳ３２に戻って処理を繰り返す。
【００５０】
具体的に、階層的格子として、２次元平面内の正方形で与えられた正方格子を基本とする場合を示す。階層的格子の生成は、計算機本体１１１内のＣＰＵ１１６によって実行され、階層的格子はメモリ１１８上に整数や浮動小数点の数の集合として構成される。そして、最終的に、後述する図１０に示すような場所によって解像度の異なる階層的な正方格子が構成される。
【００５１】
図９は階層的格子の生成手順を示す図である。まず、図９（Ａ）に示す通常の正方格子を用意する。図中、太線で示された界面５１が予め与えられている。本実施形態では、この界面５１は、区分的線分図形として与えられ、十分細かい１次元の頂点列によって構成されている。このため、胞が線分を内包するか否かの判断は、簡単のため、胞における頂点の内外判定によって行われるものとする。
【００５２】
この頂点の内外判定方法としては、第１の実施形態と同様、例えば、特開平１１−１１０５６９号公報に記載の内点判定法を利用することができる。この内外判定を使い、また、界面を表現する十分細かく細分化された１次元頂点列を利用すると、各正方格子（胞）が界面を含むか否かの判定を簡単に行うことができる。
【００５３】
すなわち、図８におけるステップＳ３１において、全ての頂点に対し、その値を「０」にする。ステップＳ３２〜Ｓ３８の操作Ａにおいて、着目した頂点の値が「１」未満であり、着目した頂点を含む胞が界面を含む場合、この頂点に「−１」を与える。そうでない場合、この頂点に「１」を与える。全ての頂点に、この操作Ａを施した後、操作Ｂを行う。
【００５４】
ステップＳ３９〜Ｓ５０の操作Ｂにおいて、着目した胞内の頂点のいずれかが値−１を保持する場合、この胞を分割する。この分割に際し、新たに生じた頂点に対し、この頂点を中点とする最小線分の両端の頂点の値が「１」である場合、値１を付与し、そうでない場合、値０を付与する。全ての胞に、この操作Ｂを施した後、操作Ｃを行う。
【００５５】
ステップＳ５１〜Ｓ５７の操作Ｃでは、着目する頂点を含む胞の全頂点が値１である場合、この着目する頂点が消滅可能であれば消滅させ、胞を統合する。
【００５６】
ステップＳ５８において、所定の領域内の最大の解像度が予め与えておいた所望の解像度であるか否かを判別し、所望の解像度である場合（ステップＳ５８でＹＥＳ）、この処理を終了する。一方、所望の解像度に達していない場合（ステップＳ５８でＮＯ）、ステップＳ３２に戻り、操作Ａ、操作Ｂおよび操作Ｃを繰り返し行う。
【００５７】
図９（Ａ）は操作Ａを終えた状態を示す。ここで、図中、黒丸は値１を表し、白丸は値−１を表す。界面５１の周囲には、白丸が点在している。図９（Ｂ）は操作Ｂを終えた状態を示す。図９（Ａ）で白丸を含む胞は全て分割されている。図９（Ｂ）中、２重の白丸は値０を表している。操作Ｂによって新たに生じた頂点に対し、値１または値０が付与されていることがわかる。
【００５８】
図９（Ｃ）は図９（Ｂ）で示した新たな格子群に対し、改めて操作Ａを行った後の状態を示す。界面５１の周囲には、白丸が局在していることがわかる。ここで、図９（Ａ）における白丸の局在と、図９（Ｃ）における白丸の局在とでは、その解像度が異なっている。図９（Ｄ）は図９（Ｃ）に対し、操作Ｂおよび操作Ｃを行った後の状態を示す。前記第１の実施形態の図４（Ｄ）と比べ、界面から離れた場所では、胞が統合されていることがわかる。
【００５９】
このようにして、所定の領域内の最大解像度が所望の解像度となるまで、操作Ａ、操作Ｂおよび操作Ｃを繰り返す。図１０は操作Ａ、操作Ｂおよび操作Ｃを繰り返し行って所望の解像度に達した状態の階層的格子を示す図である。
【００６０】
尚、上記実施形態では、正方形の胞を有する格子に適用した場合を示したが、本発明は胞の形状に依存しないので、種々の多角形の格子、例えば、三角格子、ランダム格子等に適用可能である。図１１は三角形の階層的格子を示す図である。図１１（Ａ）は前記第１の実施形態と同様、初期状態の三角格子を示し、図１１（Ｂ）は図８の界面表現アルゴリズムを実行した後の階層的三角格子を示す。このように、界面６１は、階層的三角形格子によって正確に所望の高解像度表現されると共に、界面６１から離れた場所では、前記第１の実施形態の図６（Ｂ）と比べ、統合された胞が多い。
【００６１】
また、上記実施形態では、２次元の階層的格子の場合を示したが、本発明は次元によらず、立方体胞によって構成される３次元の格子系にも適用できる。図１２は３次元の階層的格子を示す図である。このように、２次元の場合と同様の処理により、３次元の階層的格子を表現することができる。
【００６２】
更には、図８におけるＳ３２〜Ｓ３８のステップにおいて、頂点の値が１未満の頂点に着目して、それらの値をまず全て、＋２にした後に、＋２の値を持つ頂点を含むすべての胞に着目して、着目した胞が界面を含む場合は胞に属するすべての頂点に−１を与え、そうでない場合は何もしないという操作を胞全体に行い、その後に＋２を＋１に変更するということを行うとステップＳ３２〜Ｓ３８と同様の効果を得ることができる。このように、本発明の離散的アルゴリズムの実現においては様々な類似の実施方法が考えられる。しかしながら、本発明の特徴は、Ｓ３２〜Ｓ３８における「隣接胞の距離情報を含まない離散的情報を頂点に格納する」というステップと、Ｓ３９〜Ｓ５０における「自胞に属する頂点の値によって分割の判定を行う」というステップと、Ｓ５１〜Ｓ５７における「自胞に属する頂点の値によって統合の判定を行う」というステップとの３つによって構成されている事である。これらのステップを含む上記のような変更例は、本発明を構成することが理解できる。つまり、本発明はそのような詳細な変更から影響を受けない。
【００６３】
［第３の実施形態］
第３の実施形態における階層的格子生成方法が適用される計算機システムは、前記第１の実施形態の図１、図２に示したものと同様であるので、同一の符号を用いることにより、その説明を省略する。また、界面表面アルゴリズムを実行するまでの手順は前記第１の実施形態と同じである。
【００６４】
本実施形態では、頂点、および線分を構成要素とする、多面体あるいは多角形の胞によって構成される階層的格子に、予め２次元あるいは１次元の界面図形を表現する、対象となる領域全面で定義された関数が用意されている。この関数は、二値の特性関数のように、離散的なものを値にとっても、レベルセット関数のような連続的なものを値として取ってもよい。本実施形態では、簡単のために、界面の内部では正の値を取り、界面の外部で負の値を取る特性関数を利用しているが、関数の微分値や積分値がそのような正負の変化を与えるものでも、勿論よい。
【００６５】
さらに、ゼロ値を界面とするのではなく、ある特定の値を界面の値として、その値からの大小で、界面の内部か否かの判定を行ってもよい。また、物質の種類まで取り入れた、多値の離散特性関数であっても構わない。また、本実施形態では、領域内の点を入力として与えると、そこでの値が帰ってくるような仕組みを持つサブルーチンを組み込むことで、関数を実現している。よって、同一の効果を得るものの総称として、正負値を持つ関数であって、界面で符号を変え、界面の内部において正、界面の外部において負の符号を持つものについて説明する。
【００６６】
図１３は第３の実施形態における界面表現アルゴリズムを実行する際の処理手順を示すフローチャートである。前記第１の実施形態の図３に示した手順と同一のステップ処理については、同一の符号が付されている。この処理プログラムの実行用ファイルは、前述したように、ハードディスク１１７あるいはフレキシブルディスク１１０に格納されており、ＣＰＵ１１６によって実行される。
【００６７】
図３との相違は、図３のステップＳ４では、着目頂点を含む胞のいずれかが界面を含むかを判定するのに対し、図１３のステップＳ４Ａでは、着目頂点を含む胞のいずれかで関数の値が正と負の両方を同時に含むかを判定する点だけである。それ以外は同様であるので、説明を省略する。
【００６８】
尚、上記第３の実施形態では、正方形の胞を有する格子に適用した場合を示したが、本発明は胞の形状に依存しないので、種々の多角形の格子、例えば、三角格子、ランダム格子等に適用可能である。
【００６９】
図６（Ａ）は初期状態の三角格子を示し、図６（Ｂ）は図１３の界面表現アルゴリズムを実行した後の階層的三角格子を示す。このように、界面３１は、階層的三角格子によって正確に所望の高解像度で表現される。
【００７０】
また、上記実施形態では、２次元の階層的格子の場合を示したが、本発明は次元に影響されないため、立方体胞によって構成される３次元の階層的格子にも適用できる。３次元の階層的格子は、前述した図７に示す通りである。このように、２次元の場合と同様の処理により、３次元の階層的格子を表現することができる。
【００７１】
［第４の実施形態］
第４の実施形態における計算機システムの構成は、第１の実施形態と同じであるので、その説明を省略する。
【００７２】
本実施形態では、第１の実施形態と同様、頂点、および線分を構成要素とする、多面体あるいは多角形の胞によって構成される階層的格子に対し、予め２次元あるいは１次元の界面図形が用意されている。
【００７３】
第４の実施形態における界面表現アルゴリズムを実行する際の処理手順は、前記第２の実施形態の図８に示した手順とほぼ同一であり、両者の相違は、図８では、ステップＳ４と同様に、着目頂点を含む胞のいずれかが界面を含むかを判定するのに対し、第４の実施形態では、図１３のステップＳ４Ａと同様に、着目頂点を含む胞のいずれかで関数の値が正と負の両方を同時に含むかを判定する点だけである。それ以外は図８と同様であるので、説明を省略する。
【００７４】
具体的に、階層的格子として、２次元平面内の正方形で与えられた正方格子を基本とする場合を示す。階層的格子の生成は、計算機本体１１１内のＣＰＵ１１６によって実行され、階層的格子はメモリ１１８上に整数や浮動小数点の数の集合として構成される。そして、最終的に、前述した図１０に示すような場所によって解像度の異なる階層的な正方格子が構成される。
【００７５】
階層的格子の生成手順は、前述した図９に示す通りである。まず、図９（Ａ）に示す通常の正方格子を用意する。図中、太線で示された界面５１は関数のゼロ値として予め与えられている。つまり、界面を挟んで関数の値は正と負となる。本実施形態では、この関数は前記第３の実施形態と同様に、サブルーチンとして実現されている。このため、着目する胞が界面５１を内包するか否かの判断は、この胞内での関数の値によって判断することが可能である。ここでは、第３の実施形態と同様、代表点を抽出した後に、その胞内での関数の値をもって、界面の存在を判断している。
【００７６】
尚、上記実施形態では、正方形の胞を有する格子に適用した場合を示したが、本発明は胞の形状に依存しないので、種々の多角形の格子、例えば、三角格子、ランダム格子等に適用可能である。図１１（Ａ）は第３の実施形態と同様、初期状態の三角格子を示し、図１１（Ｂ）は第４の実施形態の界面表現アルゴリズムを実行した後の階層的三角格子を示す。このように、界面６１は、階層的三角形格子によって精確に所望の高解像度表現されると共に、界面６１から離れた場所では、第３の実施形態の図６（Ｂ）と比べ、統合された胞が多い。
【００７７】
また、上記実施形態では、２次元の階層的格子の場合を示したが、本発明は次元によらず、立方体胞によって構成される３次元の格子系にも適用できる。３次元の階層的格子は、前述した図１２に示す通りである。このように、２次元の場合と同様の処理により、３次元の階層的格子を表現することができる。
【００７８】
以上が本発明の実施形態の説明であるが、本発明は、これら実施形態の構成に限られるものではなく、特許請求の範囲で示した機能、または実施形態の構成が持つ機能が達成できる構成であればどのようなものであっても適用可能である。
【００７９】
また、本発明の目的は、上述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）が記憶媒体に格納されたプログラムコードを読み出して実行することによっても達成される。
【００８０】
この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【００８１】
又、プログラムコードを供給するための記憶媒体としては、例えば、フロッピー（登録商標）ディスク、ハードディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＤＶＤ−ＲＷ、ＤＶＤ＋ＲＷ、磁気テープ、不揮発性のメモリカード、ＲＯＭ等を用いることができる。
【００８２】
また、コンピュータが読み出したプログラムコードを実行することにより、上記実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ（オペレーティングシステム）等が実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれる。
【００８３】
更に、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵ等が実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれる。
【図面の簡単な説明】
【００８４】
【図１】本発明の第１の実施形態における階層的格子生成方法が適用される計算機システムの構成を示す図である。
【図２】図１における計算機本体１１１の構成を示すブロック図である。
【図３】第１の実施形態における界面表現アルゴリズムを実行する際の処理手順を示すフローチャートである。
【図４】図３の界面表現アルゴリズムにおける階層的格子の生成手順を示す図である。
【図５】図３の界面表現アルゴリズムにおける操作Ａおよび操作Ｂを繰り返し行って所望の解像度に達した状態の階層的格子を示す図である。
【図６】図３の界面表現アルゴリズムを実行した後の三角形の階層的格子を示す図である。
【図７】図３の界面表現アルゴリズムを実行した後の３次元の階層的格子を示す図である。
【図８】第２の実施形態における界面表現アルゴリズムを実行する際の処理手順を示すフローチャートである。
【図９】図８の界面表現アルゴリズムにおける階層的格子の生成手順を示す図である。
【図１０】図８の界面表現アルゴリズムにおける操作Ａ、操作Ｂおよび操作Ｃを繰り返し行って所望の解像度に達した状態の階層的格子を示す図である。
【図１１】図８の界面表現アルゴリズムを実行した後の三角形の階層的格子を示す図である。
【図１２】図８の界面表現アルゴリズムを実行した後の３次元の階層的格子を示す図である。
【図１３】第３の実施形態における界面表現アルゴリズムを実行する際の処理手順を示すフローチャートである。
【符号の説明】
【００８５】
１１、３１、５１、６１  界面
１１１  計算機システム
１１６  ＣＰＵ
１１８  メモリ
【図１】
2005275614.tif 000003
【図２】
2005275614.tif 000004
【図３】
2005275614.tif 000005
【図４】
2005275614.tif 000006
【図５】
2005275614.tif 000007
【図６】
2005275614.tif 000008
【図７】
2005275614.tif 000009
【図８】
2005275614.tif 000010
【図９】
2005275614.tif 000011
【図１０】
2005275614.tif 000012
【図１１】
2005275614.tif 000013
【図１２】
2005275614.tif 000014
【図１３】
2005275614.tif 000015