(57)【要約】【課題】高品質なメッシュを生成する新規なメッシュ生成手法を提供する。【解決手段】データ変換部２は、物体の構造データをポリトープで表現した形状データに変換する。１次元処理部３は、形状データに対する１次元の結晶化処理として、１次元ポリトープである辺を特定の基準長に基づいて分割する。ｎ次元処理部４は、形状データに対するｎ次元（ｎは２以上の次元数）の結晶化処理として、ｎ次元ポリトープ内をエージェント群で充填する。この充填処理では、エージェントの品質指標が最大限良好になるような形状でｎ次元ポリトープ内にエージェントが配置される。それとともに、ｎ次元ポリトープ内で隣り合ったエージェントにおける品質指標の合計が現状よりも良好になるように、これらの形状が最適化される。メッシュ生成部５は、ｎ次元のポリトープ内に充填されたエージェント群に基づいて、メッシュを生成する。
2019229965.tif 000002
【特許請求の範囲】
【請求項１】
エージェントベースモデルを用いたメッシュ生成システムにおいて、
物体の構造データをポリトープで表現した形状データに変換するデータ変換部と、
前記形状データに対する１次元の処理として、１次元ポリトープである辺を特定の基準長に基づいて分割する１次元処理部と、
（ｎ−１）次元（ｎは２以上の次元数）の処理が行われた形状データに対するｎ次元の処理として、エージェントの形状的な品質を示しており、所定の目的関数によってエージェント毎に算出される品質指標が最大限良好になるような形状で、前記ｎ次元ポリトープ内にエージェントを配置すると共に、前記ｎ次元ポリトープ内で隣り合ったエージェントにおける前記品質指標の合計が現状よりも良好になるように、隣り合ったエージェントの形状を最適化することによって、前記ｎ次元ポリトープ内をエージェント群で充填するｎ次元処理部と、
前記ｎ次元のポリトープ内に充填されたエージェント群に基づいて、メッシュを生成するメッシュ生成部と
を有することを特徴とするメッシュ生成システム。
【請求項２】
前記品質指標は、前記エージェントにおける内角のばらつきが小さいほど良好であることを特徴とする請求項１に記載されたメッシュ生成システム。
【請求項３】
前記品質指標は、前記エージェントにおけるエッジ長のばらつきが小さいほど良好であることを特徴とする請求項２に記載されたメッシュ生成システム。
【請求項４】
前記１次元処理部は、２次元ポリトープのファセット数が偶数になるように、当該２次元ポリトープが所有する１次元ポリトープの分割数を調整することを特徴とする請求項１に記載されたメッシュ生成システム。
【請求項５】
前記１次元処理部は、前記物体の物性および表面形状の少なくとも一方に応じて、前記基準長を調整することを特徴とする請求項１に記載されたメッシュ生成システム。
【請求項６】
前記ｎ次元処理部は、ファセット数が２ｎではないポリトープに対して前記ｎ次元の処理を行い、前記ファセット数が２ｎであるポリトープに対しては前記ｎ次元の処理を行わないことを特徴とする請求項１に記載されたメッシュ生成システム。
【請求項７】
前記エージェントのファセット数は２ｎであることを特徴とする請求項１に記載されたメッシュ生成システム。
【請求項８】
前記形状データにおける次元間のポリトープの主従関係を管理すると共に、前記１次元の処理および前記ｎ次元の処理に応じて、前記主従関係を更新するポリトープ管理部をさらに有することを特徴とする請求項１に記載されたメッシュ生成システム。
【請求項９】
前記メッシュ生成部は、前記ｎ次元のポリトープ内に充填されたエージェント群を更に細分化することによって、前記メッシュを生成することを特徴とする請求項１に記載されたメッシュ生成システム。
【請求項１０】
エージェントベースモデルを用いたメッシュ生成プログラムにおいて、
物体の構造データをポリトープで表現した形状データに変換する第１のステップと、
前記形状データに対する１次元の処理として、１次元ポリトープである辺を特定の基準長に基づいて分割する第２のステップと、
（ｎ−１）次元（ｎは２以上の次元数）の処理が行われた形状データに対するｎ次元の処理として、エージェントの形状的な品質を示しており、所定の目的関数によってエージェント毎に算出される品質指標が最大限良好になるような形状で、前記ｎ次元ポリトープ内にエージェントを配置すると共に、前記ｎ次元ポリトープ内で隣り合ったエージェントにおける前記品質指標の合計が現状よりも良好になるように、隣り合ったエージェントの形状を最適化することによって、前記ｎ次元ポリトープ内をエージェント群で充填する第３のステップと、
前記ｎ次元のポリトープ内に充填されたエージェント群に基づいて、メッシュを生成する第４のステップと
を有する処理をコンピュータに実行させることを特徴とするメッシュ生成プログラム。
【請求項１１】
前記品質指標は、前記エージェントにおける内角のばらつきが小さいほど良好であることを特徴とする請求項１０に記載されたメッシュ生成プログラム。
【請求項１２】
前記品質指標は、前記エージェントにおけるエッジ長のばらつきが小さいほど良好であることを特徴とする請求項１１に記載されたメッシュ生成プログラム。
【請求項１３】
前記第２のステップは、２次元ポリトープのファセット数が偶数になるように、当該２次元ポリトープが所有する１次元ポリトープの分割数を調整するステップを含むことを特徴とする請求項１０に記載されたメッシュ生成プログラム。
【請求項１４】
前記第２のステップは、前記物体の物性および表面形状の少なくとも一方に応じて、前記基準長を調整するステップを含むことを特徴とする請求項１０に記載されたメッシュ生成プログラム。
【請求項１５】
前記ステップ３における前記ｎ次元の処理は、ファセット数が２ｎではないポリトープに対して実行され、前記ファセット数が２ｎであるポリトープに対しては実行されないことを特徴とする請求項１０のいずれかに記載されたメッシュ生成プログラム。
【請求項１６】
前記エージェントのファセット数は２ｎであることを特徴とする請求項１０に記載されたメッシュ生成プログラム。
【請求項１７】
前記形状データにおける次元間のポリトープの主従関係を管理すると共に、前記１次元の処理および前記ｎ次元の処理に応じて、前記主従関係を更新する第５のステップをさらに有することを特徴とする請求項１０に記載されたメッシュ生成プログラム。
【請求項１８】
前記第４のステップは、前記ｎ次元のポリトープ内に充填されたエージェント群を更に細分化するステップを含むことを特徴とする請求項１０に記載されたメッシュ生成プログラム。
【請求項１９】
エージェントベースモデルを用いたメッシュ生成方法において、
物体の構造データをポリトープで表現した形状データに変換する第１のステップと、
前記形状データに対する１次元の処理として、１次元ポリトープである辺を特定の基準長に基づいて分割する第２のステップと、
（ｎ−１）次元（ｎは２以上の次元数）の処理が行われた形状データに対するｎ次元の処理として、エージェントの形状的な品質を示しており、所定の目的関数によってエージェント毎に算出される品質指標が最大限良好になるような形状で、前記ｎ次元ポリトープ内にエージェントを配置すると共に、前記ｎ次元ポリトープ内で隣り合ったエージェントにおける前記品質指標の合計が現状よりも良好になるように、隣り合ったエージェントのそれぞれの形状を最適化することによって、前記ｎ次元ポリトープ内をエージェント群で充填する第３のステップと、
前記ｎ次元のポリトープ内に充填されたエージェント群に基づいて、メッシュを生成する第４のステップと
を有することを特徴とするメッシュ生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッシュ生成システム、メッシュ生成プログラムおよびメッシュ生成方法に係り、特に、エージェントベースモデル（Agent-based model，ＡＢＭ）を用いたメッシュ生成手法に関する。
【背景技術】
【０００２】
例えば、特許文献１には、動力学的モデルを用いたバブル充填によって、非多様体形状のデータ構造であっても最適なメッシュを生成する自動メッシュ生成方法が記載されている。具体的には、まず、非多様体データ・モデルの頂点および稜線上に複数のバブルが配置される。つぎに、バブル間力およびバブル質量に基づき、粘性の項も含めて、ニュートン方程式を数値解析技法で解いてバブルを移動させ、バブルの移動がある程度安定した時点で、バブルの中心点を結んで線分を生成する。つぎに、非多様体データ・モデルの面上にバブルを配置した上で同様にバブルを移動させ、バブルの移動がある程度安定した時点で、バブルの中心点を２次元のドロネー三角形分割で結んで三角形要素を生成する。最後に、非多様体データ・モデルのソリッド領域内部にバブルを配置した上でバブルを移動させ、バブルの移動がある程度安定した時点で、バブルの中心点を３次元のドロネー三角形分割で結んで四面体要素を生成する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平７−２３０４８７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の目的は、高品質なメッシュを生成する新規なメッシュ生成手法を提供することである。
【課題を解決するための手段】
【０００５】
かかる課題を解決すべく、第１の発明は、データ変換部と、１次元処理部と、ｎ次元処理部と、メッシュ生成部とを有し、エージェントベースモデルを用いたメッシュ生成システムを提供する。データ変換部は、物体の構造データをポリトープで表現した形状データに変換する。１次元処理部は、形状データに対する１次元の処理として、１次元ポリトープである辺を特定の基準長に基づいて分割する。ｎ次元処理部は、（ｎ−１）次元（ｎは２以上の次元数）の処理が行われた形状データに対するｎ次元の処理として、ｎ次元ポリトープ内をエージェント群で充填する。この充填処理では、エージェントの品質指標が最大限良好になるような形状でｎ次元ポリトープ内にエージェントが配置される。それとともに、ｎ次元ポリトープ内で隣り合ったエージェントにおける品質指標の合計が現状よりも良好になるように、隣り合ったエージェントの形状が最適化される。品質指標は、エージェントの形状的な品質を示しており、所定の目的関数によってエージェント毎に算出される。メッシュ生成部は、ｎ次元のポリトープ内に充填されたエージェント群に基づいて、メッシュを生成する。【０００６】
ここで、第１の発明において、上記品質指標は、エージェントにおける内角のばらつきが小さいほど良好であることが好ましく、これに加えて、エージェントにおけるエッジ長のばらつきが小さいほど良好であることが好ましい。【０００７】
第１の発明において、上記１次元処理部は、２次元ポリトープのファセット数が偶数になるように、この２次元ポリトープが所有する１次元ポリトープの分割数を調整することが好ましい。また、上記１次元処理部は、物体の物性および表面形状の少なくとも一方に応じて、基準長を調整してもよい。【０００８】
第１の発明において、上記ｎ次元処理部は、ファセット数が２ｎではないポリトープに対してｎ次元の処理を行い、ファセット数が２ｎであるポリトープに対してはｎ次元の処理を行わないことが好ましい。また、上記エージェントのファセット数は２ｎであることが好ましい。【０００９】
第１の発明において、ポリトープ管理部を設けてもよい。ポリトープ管理部は、形状データにおける次元間のポリトープの主従関係を管理すると共に、上記１次元の処理および上記ｎ次元の処理に応じて、ポリトープの主従関係を更新する。また、上記メッシュ生成部は、ｎ次元のポリトープ内に充填されたエージェント群を更に細分化することによって、メッシュを生成してもよい。【００１０】
第２の発明は、第１のステップから第４のステップを有する処理をコンピュータに実行させる、エージェントベースモデルを用いたメッシュ生成プログラムを提供する。第１のステップでは、物体の構造データをポリトープで表現した形状データに変換する。第２のステップでは、形状データに対する１次元の処理として、１次元ポリトープである辺を特定の基準長に基づいて分割する。第３のステップでは、（ｎ−１）次元（ｎは２以上の次元数）の処理が行われた形状データに対するｎ次元の処理として、ｎ次元ポリトープ内をエージェント群で充填する。この充填処理では、品質指標が最大限良好になるような形状で、ｎ次元ポリトープ内にエージェントを配置する。それとともに、ｎ次元ポリトープ内で隣り合ったエージェントにおける品質指標の合計が現状よりも良好になるように、隣り合ったエージェントの形状が最適化される。品質指標は、エージェントの形状的な品質を示しており、所定の目的関数によってエージェント毎に算出される。第４のステップでは、ｎ次元のポリトープ内に充填されたエージェント群に基づいて、メッシュを生成する。【００１１】
ここで、第２の発明において、上記品質指標は、エージェントにおける内角のばらつきが小さいほど良好であることが好ましく、これに加えて、エージェントにおけるエッジ長のばらつきが小さいほど良好であることが好ましい。【００１２】
第２の発明において、上記第２のステップは、２次元ポリトープのファセット数が偶数になるように、当該２次元ポリトープが所有する１次元ポリトープの分割数を調整するステップを含むことが好ましい。また、上記第２のステップは、物体の物性および表面形状の少なくとも一方に応じて、基準長を調整するステップを含んでいてもよい。【００１３】
第２の発明において、上記ステップ３におけるｎ次元の処理は、ファセット数が２ｎではないポリトープに対して実行され、ファセット数が２ｎであるポリトープに対しては実行されないことが好ましい。また、上記エージェントのファセット数は２ｎであることが好ましい。【００１４】
第２の発明において、さらに第５のステップを有する処理をコンピュータに実行させてもよい。第５のステップでは、形状データにおける次元間のポリトープの主従関係を管理すると共に、１次元の処理およびｎ次元の処理に応じて、主従関係を更新する。また、上記第４のステップは、ｎ次元のポリトープ内に充填されたエージェント群を更に細分化するステップを含んでいてもよい。【００１５】
第３の発明は、第１のステップから第４のステップを有し、エージェントベースモデルを用いたメッシュ生成方法を提供する。第１のステップでは、物体の構造データをポリトープで表現した形状データに変換する。第２のステップでは、形状データに対する１次元の処理として、１次元ポリトープである辺を特定の基準長に基づいて分割する。第３のステップでは、（ｎ−１）次元（ｎは２以上の次元数）の処理が行われた形状データに対するｎ次元の処理として、ｎ次元ポリトープ内をエージェント群で充填する。この充填処理では、品質指標が最大限良好になるような形状で、ｎ次元ポリトープ内にエージェントを配置する。それとともに、ｎ次元ポリトープ内で隣り合ったエージェントにおける品質指標の合計が現状よりも良好になるように、隣り合ったエージェントの形状が最適化される。品質指標は、エージェントの形状的な品質を示しており、所定の目的関数によってエージェント毎に算出される。第４のステップでは、ｎ次元ポリトープ内に充填されたエージェント群に基づいて、メッシュを生成する。
【発明の効果】
【００１６】
本発明によれば、構造データより変換され、かつ、ポリトープで表現された形状データに対して１次元ポリトープである辺を基準長に基づいて分割した上で、（ｎ−１）次元の処理が行われた形状データに対するｎ次元の処理として、ｎ次元ポリトープ内にエージェントを配置していく。エージェントのサイズは基準長に依存しており、その形状は品質指標が最大限良好になるように設定される。また、隣り合ったエージェントの形状は、これらの品質指標の合計が現状、すなわち、最適化を行う前の状態よりも良好になるように最適化される。これにより、形状的に良好なエージェント群によってｎ次元ポリトープの内部空間が隙間なく充填・細分化されるので、高品質なメッシュを生成することができる。
【図面の簡単な説明】
【００１７】
【図１】メッシュ生成システムのブロック図
【図２】メッシュ生成処理のフローチャート
【図３】２次元構造データを示す図
【図４】２次元形状データを示す図
【図５】次元間におけるポリトープの主従関係を示す概念図
【図６】１次元の結晶化処理後の形状データを示す図
【図７】ｎ次元の結晶化処理ルーチンのフローチャート
【図８】エージェント形状の最適化における簡易手法の説明図
【図９】エージェントＡ１，Ａ２の配置説明図
【図１０】エージェントＡ３の配置説明図
【図１１】エージェントＡ３の配置に伴うエージェント形状の最適化説明図
【図１２】エージェントＡ４の配置説明図
【図１３】エージェントＡ５の配置説明図
【図１４】エージェント群Ａ１〜Ａ９による充填状態の説明図
【図１５】メッシュデータを示す図
【発明を実施するための形態】
【００１８】
図１は、本実施形態に係るメッシュ生成システムのブロック図である。メッシュ生成システム１は、物体の構造データを入力とし、この物体の形状をメッシュで表現したメッシュデータを出力する。メッシュの生成過程では、エージェントベースモデル（Agent-based model，ＡＢＭ）が用いられる。ここで、「エージェントベースモデル」とは、自律的なエージェントの振る舞いと、エージェント間の相互作用とが系全体に与える影響を評価するためのシミュレーションモデルの一つであり、マルチエージェントシミュレーションと称されることもある。また、「エージェント」とは、自己の状況および自己の周囲の状況に基づいて、予め定められた規則の下で自律的に行動する主体をいう。本実施形態の特徴は、物体の領域を細分化するためにエージェントベースモデルを用いること、より具体的には、ある領域の内部空間において、隣り合ったエージェントの相互作用を考慮しながらエージェントを配置していき、この領域内に充填されたエージェント群に基づいて、メッシュを生成することにある。
【００１９】
メッシュ生成システム１は、データ変換部２と、１次元処理部３と、ｎ次元処理部４と、メッシュ生成部５と、ポリトープ管理部６とを有する。データ変換部２は、処理対象として入力された構造データを形状データに変換する。変換前の構造データは、物体の構造（形状を含む。）を規定する任意形式のデータであり、２次元ＣＡＤデータや、ＳＴＥＰ形式やＳＴＬ形式などの３次元ＣＡＤデータである。この構造データは、自己が規定する形状として曲線や曲面を含んでいてもよい。一方、変換後の形状データは、物体の形状をポリトープで表現したデータである。特に、構造データが曲線や曲面を含んでいる場合には、これらが線分で離散化され、曲線は直線群、曲面は平面群でそれぞれ近似される。形状データの実装（クラス定義）の仕方は任意であるが、後述するように、異なる次元を参照する結晶化処理が行われる関係上、ポリトープおよびファセットの対応関係を保持・管理することが好ましい。ここで、「ポリトープ」とは、初等幾何学における超多面体をいい、０次元ポリトープは「点」、１次元ポリトープは「辺」、２次元ポリトープは「面」、３次元ポリトープは「立体」である。また、「ファセット」とは、ある次元のポリトープが所有する一つ下の次元ポリトープをいう。例えば、３次元ポリトープ（立体）に対しての「面」、２次元ポリトープ（面）に対しての「辺」、１次元ポリトープ（辺）に対しての「点」がファセットに相当する。
【００２０】
１次元処理部３は、データ変換部２によって変換された形状データに対する１次元の結晶化処理として、１次元ポリトープである辺を特定の基準長に基づいて分割する。１次元の結晶化処理は、形状データに含まれる１次元ポリトープ（辺）のうち、後述する条件を満たすものに対して行われる。ここで、基準長は、ユーザによって長さが定義され、これによってエージェントのサイズが規定される。具体的には、基準長が長くなるほどエージェントが大きくなり（領域分解能＝粗）、これが短くなるほどのエージェントが小さくなる（領域分解能＝密）。また、基準長は、物体全体に対して一定値を固定的に適用してもよいが、物体の物性および表面形状の少なくとも一方に応じて可変値を適用してもよい。例えば、材質が柔らかく変形が生じ易い部位については、他の部位よりも基準長を短くしたり、表面の曲率が大きい部位については、他の部位よりも基準長を短くするといった如くである。
【００２１】
ｎ次元処理部４は、（ｎ−１）次元（ｎは２以上の次元数）の処理が行われた形状データに対するｎ次元の結晶化処理として、ｎ次元ポリトープの内部空間をエージェント群（エージェントの次元数＝ｎ）で充填・細分化する。例えば、ｎ＝２の場合、１次元処理部３によって１次元の結晶化処理が行われた形状データに対して２次元の結晶化処理が行われ、２次元ポリトープ（面）の内部空間が２次元エージェント群で充填・細分化される。また、ｎ＝３の場合、ｎ次元処理部４によって２次元の結晶化処理が行われた形状データに対して３次元の結晶化処理が行われ、３次元ポリトープ（立体）の内部空間が３次元エージェント群で充填・細分化される。有効性が期待できるｎの上限は４、すなわち、４次元ポリトープ（多胞体：polychoron）と考えられるが、ｎ≧５を特段排除するものではない。
【００２２】
１次元を除くｎ次元の結晶化処理では、自律的な行動主体であるエージェントがｎ次元ポリトープの内部空間に個別に配置される。この内部空間において隣り合った複数のエージェント（隣接エージェント）は相互に作用し、この相互作用に基づいて、これらのエージェントの形状が最適化される。個々のエージェントの形状、および、自己を含む隣接エージェントの最適化形状は、品質指標という概念に基づいて決定される。詳細については後述するが、この品質指標は、エージェントの形状的な品質を示し、所定の目的関数（効用関数）によってエージェント毎に算出される。概略的にいえば、エージェントの個別的な形状は、このエージェントの品質指標が最大限良好になるように設定される。また、自己を含む隣接エージェントの最適化形状は、これらの品質指標の合計が現状、すなわち、最適化される前の状態よりも良好になるように設定される。
【００２３】
ｎ次元処理部４は、出力目標であるメッシュデータの次元数に応じた回数で結晶化処理を実行する。例えば、２次元メッシュデータを出力する場合、２次元ポリトープ（面）に対する結晶化処理という１回の処理が行われる。また、３次元メッシュデータを出力する場合、２次元ポリトープ（面）に対する結晶化処理、および、これに続く３次元ポリトープ（立体）に対する結晶化処理という計２回の処理が行われる。
【００２４】
メッシュ生成部５は、ｎ次元ポリトープ内に充填されたエージェント群に基づいて、四角形や六面体などの要素群で表現されたメッシュを生成する。その際、所望のメッシュ分解能を確保すべく、必要に応じて、個々のエージェントの内部を等分割するなどして、エージェント内を更に細分化してもよい。生成されたメッシュは、所定の出力形式に変換された上で、メッシュデータとして外部に出力される。
【００２５】
ポリトープ管理部６は、メッシュ生成システム１が備えるメモリ空間上において、データ変換部２によって変換された形状データにおける次元間のポリトープの主従関係、すなわち、高次元ポリトープがどの低次元ポリトープを所有しているのかを記憶・管理する。具体的には、データ変換部２によって形状データが生成された場合、この形状データに関するポリトープの主従関係が登録される。また、１次元処理部３の処理過程では、１次元ポリトープ（辺）の分割、および、これに伴う０次元ポリトープ（点）の追加に応じて、ポリトープの主従関係が随時更新される。さらに、ｎ次元処理部４の処理過程では、ｎ次元ポリトープの細分化に応じて、ポリトープの主従関係が随時更新される。ポリトープ管理部６によって管理されるポリトープの主従関係は、１次元処理部３およびｎ次元処理部４の双方によって随時参照される。
【００２６】
図２は、メッシュ生成処理のフローチャートである。同図に示すメッシュ生成処理は、コンピュータにプログラム（メッシュ生成プログラム）をインストールし、このプログラムによって規定された手順でコンピュータを動作させることによって実現される。以下、図３に示す形状の２次元構造データを一例として本処理の内容について詳述する。まず、ステップ１では、データ変換部２に処理対象となる構造データが入力される。
【００２７】
つぎに、ステップ２では、データ変換部２によって、構造データから形状データへの変換が行われる。例えば、図３に示した２次元構造データは、図４に示す２次元形状データに変換される。具体的には、構造データにおける３つの点が０次元ポリトープＰ0(1)〜Ｐ0(3)に変換され、２本の直線が１次元ポリトープＰ1(1)〜Ｐ1(2)に変換される。また、形状データへの変換過程では、図３に示した１本の円弧が複数の線分で直線近似される。これによって、隣り合った線分を接続する接続点のそれぞれが０次元ポリトープＰ0(4)〜Ｐ0(6)に変換され、それぞれの線分が１次元ポリトープＰ1(3)〜Ｐ1(6)に変換される。
【００２８】
図５は、図４の形状データに関するポリトープの主従関係を示す概念図である。ポリトープの主従関係は、２次元ポリトープＰ2が所有する１次元ポリトープＰ1、１次元ポリトープＰ2が所有する０次元ポリトープＰ0の如く、ポリトープとファセットとの関係を次元毎に規定する。同図の例では、２次元ポリトープＰ2(1)は、そのファセット（辺）として、６つの１次元ポリトープＰ1(1)〜Ｐ1(6)を所有している。また、例えば１次元ポリトープＰ1(1)は、このファセット（点）として、２つの０次元ポリトープＰ0(1)，Ｐ0(2)を所有している。２次元ポリトープＰ2が複数存在する場合には、それぞれの２次元ポリトープＰ2について、上記のようなポリトープの主従関係が管理される。また、３次元形状データの場合、３次元ポリトープ（面）を含めたポリトープの主従関係が管理される。以後の説明は省略するが、ポリトープの主従関係は、以下のステップ３，４の処理過程で随時変更・更新される。
【００２９】
ステップ３では、１次元処理部３によって、特定の基準長を用いた１次元の結晶化処理が行われる。１次元の結晶化処理の対象となるのは、基準長よりも長い１次元ポリトープＰ1であり、この１次元ポリトープＰ1（辺）が基準長程度の長さに分割される。辺の分割数としては、例えば、１次元ポリトープＰ1の長さを基準長で除算し、この除算値を切り捨てまたは切り上げた整数とすることができる。
【００３０】
図６は、１次元の結晶化処理後の形状データを示す図である。図４に示された１本の辺に相当する１次元ポリトープＰ1(1)，Ｐ1(2)のそれぞれが３つに分割される。これにより、１次元ポリトープＰ1(1)は削除され、その代わりに、３つの１次元ポリトープＰ1(1-1)〜Ｐ1(1-3)と、２つの０次元ポリトープＰ0(7)〜Ｐ0(8)とが追加される。同様に、１次元ポリトープＰ1(2)は削除され、その代わりに、３つの１次元ポリトープＰ1(2-1)〜Ｐ1(2-3)と、２つの０次元ポリトープＰ0(9)〜Ｐ0(10)とが追加される。
【００３１】
１次元の結晶化処理では、２次元ポリトープＰ2が所有する１次元ポリトープＰ1の数、すなわち、２次元ポリトープＰ2のファセット数が偶数になるように、１次元ポリトープＰ1の分割数が調整される。図６の例では、２次元ポリトープＰ2(1)のファセット数が１０なので、本条件を満たしている。分割数の調整を行う理由は、これ以降の処理過程でファセット数が２ｎ（ｎは次元数）以外のポリトープが出現しないようにして、これに対する例外処理の発生を回避するためである。従来のメッシャーの場合、メッシングの過程で四角形の中に三角形、あるいは、六面体の中に四面体が混ざってしまうことがあるため、これらを取り除くために特殊な例外処理を施す必要がある。これに対して、本手法では、上記のような偶数化の調整を行うことで、フェセット数が２ｎ以外のポリトープが以後の処理過程で発生することを有効に抑制できる。
【００３２】
ステップ４では、ｎ次元処理部４によって、自律的な行動主体であるエージェントを用いたｎ次元の結晶化処理が行われる。図７は、ｎ次元の結晶化処理ルーチンのフローチャートである。まず、ステップ４１では、処理対象となるｎ次元ポリトープ（例えば、図６に示した２次元ポリトープＰ2(1)）が指定される。処理対象となるｎ次元ポリトープはファセット数が２ｎでないこと、具体的には、２次元の結晶化処理では２次元ポリトープのファセット数が４でないこと、３次元の結晶化処理では３次元ポリトープのファセット数が６でないことが条件となる。すなわち、ｎ次元の結晶化処理は、ファセット数が２ｎではないポリトープに対して行われ、ファセット数が２ｎであれば、このポリトープ自身が一個のエージェントとなり得るので、このポリトープに対しては行われない。
【００３３】
つぎに、ステップ４２では、ステップ４１で指定された処理対象の内部空間において、エージェントの配置場所が指定される。エージェントの配置場所およびその順序として、どのような規則を設定するかは任意であるが、本実施形態では、一例として、図１４に示すように、（i）２つの端部への配置（Ａ１→Ａ２）、（ii）これらを結ぶ辺上への配置（Ａ３）、（iii）上記（i），（ii）に基づくすべての辺上への配置（Ａ４→Ａ５→Ａ６→Ａ７）、（iv）空間内側への配置（Ａ８）といった順序で、個々のエージェントを順次配置していく。
【００３４】
エージェントの配置等に関する規則としては次のものが挙げられる。第１の規則として、エージェントのファセット数は２ｎである。すなわち、２次元の結晶化処理における２次元エージェントは四角形であり、３次元の結晶化処理における３次元エージェントは六面体である。これは、２次元形状を四角形メッシュ、３次元形状を六面体メッシュでそれぞれ表現することに由来する。第２の規則として、エージェントのファセットは、このエージェントの配置場所の近傍にある既存のファセットを共有する。「既存のファセット」とは、エージェントが属するｎ次元ポリトープのファセット、あるいは、このｎ次元ポリトープ内に既に配置された他のエージェントのファセットである。これは、ｎ次元ポリトープの内部空間にエージェントを隙間なく配置することに由来する。
【００３５】
ステップ４３では、エージェントの品質指標Ｑが最大限良好になるように、このエージェントの形状が設定される。上述したように、エージェントの品質指標Ｑは、このエージェントの形状的な品質を示しており、一例として、以下の目的関数によって算出される「不満度」とすることができる。
【００３６】
（不満度） ＝ （内角の分散）*ａ＋（エッジ長の（最長／最短））*ｂ
【００３７】
上記数式において、ａ，ｂはユーザ定義の定数である。また、（内角の分散）は、エージェントにおける内角のばらつきを示す。エージェントが四角形ならば内角θiは４個（ｉ＝４）、六面体ならば内角θiは２４個（ｉ＝２４）存在し、これらの分散は下式に基づいて算出される。なお、内角のばらつきは、内角の分散の代わりに、内角の（最大／最小）などの散布度を表す指標によって評価してもよい。
【００３８】
（内角の分散）＝１／Ｎ*Σ（θi−Π／２）2
【００３９】
エッジ長の（最長／最短）、すなわち、エッジ長の長短比は、エージェンにおけるエッジ長のばらつきを示す。ここで、「エッジ長」とは、２次元の結晶化処理の場合、辺すなわち１次元ポリトープＰ1の長さことである。なお、エッジ長のばらつきは、エッジの長短比の代わりに、エッジの分散などの散布度を表す指標によって評価してもよい。
【００４０】
不満度は、その傾向として、内角のばらつきが小さくなるほど、そして、エッジ長のばらつきが小さくなるほど小さくなり、正方形や正六面体が最小となる。そして、不満度が小さくなるほどエージェントの形状的な品質は良好とされ、不満度が大きくなるほどその品質は良好でないとされる。このような傾向から理解できるように、「品質指標Ｑが最大限良好になる」ような形状とは、既存のファセットを共有するという制約条件の下、正方形や正六面体に極力近くなるような形状ということができる。なお、「品質指標Ｑが最大限良好になる」とは、品質指標Ｑが最大値をとることを条件としてもよいが、例えば、不満度が所定のしきい値よりも小さい、あるいは、以下に述べる幸福度が所定のしきい値よりも大きいといった如く、品質指標Ｑが所定のしきい値を超えるほど良好であることをもって、本条件を満たすとしてもよい。
【００４１】
品質指標Ｑとしては、上記数式に限定されるものではなく、様々なものが考えられる。例えば、エッジ長のばらつきを考慮することなく、内角のばらつきのみを評価してもよい。また、内角のばらつきに加えて、他の要件（例えば、エッジ長はなるべく大きいほうがよい等）も考慮した評価を行ってもよい。また、上記数式の不満度に−１を乗じたものを「幸福度」とし、この幸福度を評価指標Ｑとしてもよい。この場合、幸福度が大きくなるほどエージェントの形状的な品質は良好とされ、幸福度が小さくなるほどその品質は良好でないとされる。
【００４２】
ステップ４４では、ｎ次元ポリトープの内部空間において隣り合った複数のエージェント（自己を含む。）について、これらの形状が最適化される（スムージング）。この最適化は、自己を含む隣接エージェントにおける個々の品質指標Ｑの合計、すなわち、全体品質指標Ｑsumが現状、すなわち、最適化を行う前の状態よりも良好になるような変形を行うことで達成される。
【００４３】
ここで、全体品質指標Ｑsum（以下「関数Ｕ」とする。）は、各内角（θ）や各エッジ長（ｌ）に依存して決定されるが、内角やエッジ長は各Ｐ0の座標（ベクトルｘ）によって表現可能なので、以下のように表現できる。
【００４４】
【数１】
2019229965.tif 000003
【００４５】
この際に任意のＰ0の移動量（Δベクトルｘi）を以下のように定義する。
【００４６】
【数２】
2019229965.tif 000004
【００４７】
この移動操作を形状の最適化のタイミングで繰り返し行う。繰り返し終了の条件は｜Δベクトルｘ｜／Δｔがすべてのｉに対して所定の閾値を下回ることである。
【００４８】
上記シミュレーションでは、Δｔを十分に小さくすることにより厳密に全体品質指標Ｑsumの上昇を保証する。しかし、計算コストが非常に高い場合には、計算を近似するような簡易手法を用いることができる。この簡易手法では、各Ｐ0の移動量をＰ1の長さおよび基準長の乖離に由来する値（δベクトルｘlength）と、Ｐ1同士の作る角度のπ／２からの乖離に由来する値（δベクトルｘangle）とによって決定する。各タイムステップで２つの値をエージェント毎に評価してＰ0に移動量を加算していき、すべてのエージェントに関する評価が終了したタイミングで、移動量の合計分（Δベクトルｘ）だけＰ0を実際に移動させる。
【００４９】
図８は、エージェント形状の最適化における簡易手法の説明図である。同図は、２つのＰ1が接続するＰ0について例示している。簡単のため２つのＰ1をそれぞれＶi，Vjというベクトルに置き換えて説明する。
【００５０】
【数３】
2019229965.tif 000005
【００５１】
ただし、ｋangleおよびｋlengthはエージェントの不満度に比例する所定の定数である。また、上記数式において、イテレータｉをある条件（cond.）下で１ずつインクリメントしながら、オペランドを足し合わせる演算記号を以下のように表現している。
【００５２】
【数４】
2019229965.tif 000006
【００５３】
以上の簡易手法は、全体品質指標Ｑsumを直接演算するものではないが、これに基づく処理結果として、全体品質指標Ｑsumが現状よりも良好になるような変形が行われる。なお、図７に示したフローチャートでは、形状の最適化をエージェントの配置毎に毎回行っているが、毎回行う必要は必ずしもなく、所定の条件を満たす場合のみ行ってもよい。
【００５４】
ステップ４５では、処理対象となるｎ次元ポリトープの内部空間がエージェント群によって充填されたか否かが判定される。この判定結果が否定の場合、すなわち、ｎ次元ポリトープ内の充填が完了していない場合には、次のエージェントに処理対象を移行し（ステップ４６）、このエージェントについての処理が行われる（ステップ４２〜４４）。そして、エージェント毎の繰り返し処理によって、ｎ次元ポリトープ内の充填が完了した場合、ステップ４５の判定結果が否定から肯定に変わって、ステップ４７に進む。
【００５５】
ステップ４７では、すべてのｎ次元ポリトープに対する処理が完了したか否かが判定される。この判定結果が否定の場合、すなわち、同一次元に属する全ポリトープに対する処理が完了していない場合には、同一次元における次のポリトープに処理対象を移行し（ステップ４８）、同様の処理が行われる（ステップ４１〜４６）。そして、同一次元におけるポリトープ毎の処理が繰り返されることよって、全ポリトープの処理が完了した場合、ステップ４７の判定結果が否定から肯定に変わり、本ルーチンが終了する。
【００５６】
２次元メッシュを生成する場合には、２次元の結晶化処理の終了により、ステップ４の処理が終了する。また、３次元メッシュを生成する場合には、２次元の結晶化処理に続いて、３次元ポリトープを対象とした３次元の結晶化処理が行われ、その終了をもってステップ４の処理が終了する。
【００５７】
以下、図９から図１４を参照しつつ、エージェント群による２次元ポリトープＰ2(1)の充填プロセスについて説明する。まず、図９に示すように、２次元ポリトープＰ2(1)の右下端にエージェントＡ１が配置される。エージェントＡ１は、２次元ポリトープＰ2(1)が所有するファセットＰ1(2-3)，Ｐ1(1-1)を共有する。ファセットの共有に関する実装上の手法としては、例えば、共役ファセットという鏡写しのようなファセットを別途に生成・所持することによって取り扱うことができる。３つの点Ｐ0(1)，Ｐ0(7)，Ｐ0(10)が既に特定された制約条件の下で残された自由度は、残りの点Ｘ1の配置場所ということになる。点Ｘ1は、エージェントＡ１の品質指標Ｑ１が最大限良好になる位置に配置され、これによって、エージェントＡ１の形状が決定される。エージェントＡ１については、隣り合ったエージェントが存在しないので、形状の最適化は行われない。
【００５８】
つぎに、２次元ポリトープＰ2(1)の左下端にエージェントＡ２が配置される。エージェントＡ２は、２次元ポリトープＰ2(1)が所有するファセットＰ1(2-1)，Ｐ1(6)を共有する。３つの点Ｐ0(3)，Ｐ0(6)，Ｐ0(9)が既に特定された制約条件の下で残された自由度は、残りの点Ｘ2の配置場所ということになる。点Ｘ2は、エージェントＡ２の品質指標Ｑ２が最大限良好になる位置に配置され、これによって、エージェントＡ２の形状が決定される。エージェントＡ２については、隣り合ったエージェントが存在しないので、形状の最適化は行われない。
【００５９】
つぎに、図１０に示すように、２つのエージェントＡ１，Ａ２の間にエージェントＡ３が配置される。エージェントＡ３は、２次元ポリトープＰ2(1)が所有するファセットＰ1(2-2)と、エージェントＡ１，Ａ２のファセットとを共有する。よって、エージェントＡ３の品質指標Ｑ３を評価するまでもなく、エージェントＡ４の形状が一義的に特定される。また、エージェントＡ３については、２つのエージェントＡ１，Ａ２と隣り合っている。よって、３つのエージェントＡ１〜Ａ３の合計品質指標Ｑsumが現状よりも良好になるように、エージェントＡ１〜Ａ３の形状が最適化される。これにより、エージェントＡ１〜Ａ３の形状は、図１１に示すように、破線の状態から実線の状態に最適化される。
【００６０】
つぎに、図１２に示すように、２次元ポリトープＰ2(1)の右上端にエージェントＡ４が配置される。エージェントＡ４は、２次元ポリトープＰ2(1)が所有するファセットＰ1(1-3)，Ｐ1(3)を共有する。この制約条件の下で、エージェントＡ４の品質指標Ｑ４が最大限良好になるように、エージェントＡ４の形状が決定される。エージェントＡ４については、隣り合ったエージェントが存在しないので、形状の最適化は行われない。
【００６１】
つぎに、図１３に示すように、２つのエージェントＡ１，Ａ４の間にエージェントＡ５が配置される。エージェントＡ５は、２次元ポリトープＰ2(1)が所有するファセットＰ1(1-2)と、エージェントＡ１，Ａ４のファセットとを共有する。よって、エージェントＡ５の品質指標Ｑ５を評価するまでもなく、エージェントＡ５の形状が一義的に特定される。また、エージェントＡ５については、２つのエージェントＡ１，Ａ２と隣り合っている。よって、３つのエージェントＡ１，Ａ４，Ａ５の全体品質指標Ｑsumが現状よりも良好になるように、エージェントＡ１〜Ａ３の形状は破線の状態から実線の状態に最適化される。
【００６２】
以後、図１４に示すように、エージェントＡ６〜Ａ８が形状の最適化を伴いながら順次配置されていく。これによって、２次元ポリトープＰ2(1)の内部空間は、８つのエージェントＡ１〜Ａ８によって隙間なく充填される。
【００６３】
ステップ５では、メッシュ生成部５によってメッシュデータが生成される。この過程では、必要に応じてエージェントの領域が等分割され、これによって、図１５に示すようなメッシュデータが生成される。生成されたメッシュデータは、最終的な出力データとして外部に出力される。
【００６４】
このように、本実施形態によれば、構造データより変換され、かつ、ポリトープで表現された形状データに対して、１次元ポリトープＰ1である辺を基準長に基づき分割する。そして、（ｎ−１）次元の処理が行われた形状データに対するｎ次元の処理として、ｎ次元ポリトープ内にエージェントを配置していく。エージェントのサイズは基準長に依存しており、その形状はエージェントの品質指標Ｑが最大限良好になるように設定される。また、隣り合ったエージェントの形状は、全体品質指標Ｑsumが現状、すなわち、最適化を行う前の状態よりも良好になるように最適化される。これにより、形状的に良好なエージェント群によってｎ次元ポリトープの内部空間が隙間なく充填・細分化されるので、高品質なメッシュを生成することができる。
【００６５】
また、本実施形態によれば、１次元処理部３およびｎ次元処理部４を組み合わせて、２次元データの場合には１次元から２次元に至る結晶化処理、３次元データの場合には１次元から３次元に至る結晶化処理を行うことで、ほぼあらゆる形状のメッシングを安定して行うことができ、例外処理を要することなくメッシングの完了を保証できる。メッシングの途中で続行不能となることを防止できることは、従来のメッシャーとの比較において、非常に重要かつ効果的である。
【００６６】
さらに、本実施形態によれば、メッシャーとしてのカスタマイズ性の向上を図ることができる。実際にメッシュを作成する過程では、単純にメッシュを均一に切るだけではなく、物体の物性（例えば材質）や表面形状（例えば曲率）といった条件に応じて、メッシュの細かさを調整することが多い。本実施形態では、物体の物性および表面形状の少なくとも一方に応じて基準長を調整することで、これらのファクターをメッシュの細かさに自動的に反映することができる。
【００６７】
なお、上述した実施形態では、ｎ次元の結晶化処理において、ｎ次元ポリトープの内部空間にエージェントを順次配置していく逐次処理を例について説明したが、処理の高速化を図るために、可能な範囲で、複数のエージェントを同時並行的に配置していく並列処理を行ってもよい。例えば、図１４に示したエージェントＡ１〜Ａ３などは、互いに独立しており、他のエージェントとの相互作用を考慮する必要がないため、並列処理が可能である。
【符号の説明】
【００６８】
１  メッシュ生成システム
２  データ変換部
３  １次元処理部
４  ｎ次元処理部
５  メッシュ生成部
６  ポリトープ管理部
【図１】
2019229965.tif 000007
【図２】
2019229965.tif 000008
【図３】
2019229965.tif 000009
【図４】
2019229965.tif 000010
【図５】
2019229965.tif 000011
【図６】
2019229965.tif 000012
【図７】
2019229965.tif 000013
【図８】
2019229965.tif 000014
【図９】
2019229965.tif 000015
【図１０】
2019229965.tif 000016
【図１１】
2019229965.tif 000017
【図１２】
2019229965.tif 000018
【図１３】
2019229965.tif 000019
【図１４】
2019229965.tif 000020
【図１５】
2019229965.tif 000021
【国際調査報告】
2019229965.tif 000022
2019229965.tif 000023