Designシンポジウム2021 講演論文集

Agent based simulation を用いた六面体メッシュ自動生成
Agent-based simulation aided hexahedral mesh generation
菅野∗

Topological Arts 株式会社

朋典 ∗†
†

東京大学大学院工学系研究科

キーワード：CAD, CAM, CAE, 六面体メッシュ, Agent AI

はじめに

1

３ D スキャニング技術の発達により，実測データを基にした工学シミュレーションに対する需要が高まってきている．精密なシミュレーションを行う際においては，六面体メッシュを計算に用いることが多い．にもかかわらず，構造計算用六面体メッシュの生成に関しては未だに人力に頼るところが大きく，自動生成の手段が確立されているとは言えない状況にある．
本研究では，任意形状に対する高品質な六面体メッシュ自動生成を可能とするための新しい手法として，エージェントベースシミュレーションを利用したメッシュ生成方を提案する．

1.1

先行研究

これまで様々な自動六面体メッシュ生成技術が提案されているものの，品質の良い六面体メッシュを生成する決定的な手法は提案されていない．主な自動六面体メッシュ生成技術には，以下のものが挙げられる．

• Spatial partitioning [4]• Plastering method [5]• Mapping-based method [6]• Tetra-to-Hexa mesh [7]Spatial partitioning は，モデルの内部に直交格子を作成し，六面体メッシュに変換した後，モデル表面と内部の六面体メッシュを接続する手法である．Plastering
method は，六面体要素ひとつひとつをモデル内部の端から順番に敷き詰めていく手法である．Mapping-based
method は，一度モデル表面を別の空間に写像し，その空間で表面の四辺形分割を行った後，元のモデル表面に写像し直す手法である．Tetra-to-Hexa mesh は，予め生成された四面体メッシュに対して，1 つの四面体メッシュを 3 つの六面体メッシュに変換する事によって，形状の美しさは保証しないものの確実に六面体のみでメッシュを生成する手法である．
これらの手法の他にも数多くの手法が提案されているが，いずれの手法も得意不得意なモデル形状が存在するため，任意の形状に対して品質のよい六面体メッシュを自動生成することはできず，生成したとしても，メッシュに大きな歪みが生じることが指摘されている．
このため，現在ではモデルに依存して使用するメッシュ生成アルゴリズムを変更することがしばしば行われている．

本研究では，種々のアルゴリズムを場合分けして使用する代わりに，六面体 (四角形) としてのエージェン
ト AI に対していくつかの単純な性質を実装し，同様の成果の獲得を目指す．

1.2

特色

2

提案手法

2.1

輪郭線の分割2.2

表面の四角形分割

2.3

六面体充填

本手法では与えられたモデルを容器に，四角形／六面体要素を結晶に見立てて空間充填のエージェントベー
ス結晶成長シミュレーションを行う．
六面体を配置／充填してゆくという意味では Plastering に似ているが，配置の順序はエージェントの嗜好によって定まる上，充填の過程でエージェント同士の相互作用によるスムージングを行う点で決定的に異なる．また，エージェント自体に空間認識能力をもたせることにより，表面付近では法線方向にならい，内部では近傍エージェントとの結合を行う等の特殊な挙動をシンプルに実装することが可能となる．
本手法ではモデル形状の表面情報と輪郭線情報を利用し，以下の手順でメッシュを生成する．
モデルの輪郭線情報を何らかな手段で抽出した後に，これを生成されるメッシュの標準的なエッジ長に分割する．この際に，輪郭線によって囲まれた各領域が，必ずのべ偶数個のエッジによって囲われる様に，分割数を調整する必要がある．領域を囲うエッジ数が奇数である場合，その領域を四角形で分割し切ることができない．

前のステップで生成されたエッジ (初期エッジ) を元に四角形を生成する．この際，四角形生成に利用できるエッジの組を足場とし，これを列挙する．なるべく多くの初期エッジを含む足場から順に採用し，生成の際に不足するノードやエッジは，後述のエージェント(四角形) の幸福度を最大にする様に配置する．
前のステップで生成された四角形（初期／表面フェイス）を元に六面体を生成する．四角形分割の際と同様

69

Designシンポジウム2021 講演論文集に，六面体生成に利用可能なフェイスの組を足場とし，なるべく多くの表面フェイスを含む足場から採用する．
六面体生成の際に不足するフェイスやエッジ，ノードについても同様に，後述のエージェント (六面体) の幸福度を最大化する様に配置する．

エージェントについて

2.4

今研究ではエージェントの空間認識を用いた特殊な実装を用いているが，紙面の都合上，最も一般的なモデルを用いて以下に概要を示す．
−→−→
各エージェントは，内角 θ と各エッジの長さ l−→ −→に 応 じ て 幸 福 度 ui ( θ , l ) を 持 ち ，全 体 の 幸 福 度−→−→
U ({ θ }, { l }) を最大化する様に吸着・変形する．
→
変形の際の各ノードの運動 (∆−xj ) は以下の様に記述できる．
∑ −−
→−
→→ −
→
U ({ θ }, { l }) =ui ( θ , l )図１：橋脚への六面体充填iただし−→−→→U ({−x }) = U ({ θ }, { l })∂→→∆−xj ∝ −U ({−x }) ∗ ∆t∂→xj

0 < ∆t << 1
この移動操作を各スムージングのタイミングで繰り返−|∆→x |
し行う．繰り返し終了の条件は ∆ti がすべての i に対して所定の閾値を下回ることである．

3

実験結果

今回は橋脚を模した簡易形状に対して六面体充填試験を行った．表面情報や特徴線情報についての抽出は予め用意した独自形式の形状ファイルを用いて入力した．
出力結果を以下に示す．想定のとおりに隅から充填されており，内部の充填が最後になっていることがわかる．上部の五角柱部分の分割品質も期待通りになっている．

4

まとめと展望今回の研究では，六面体をエージェントとして扱い，その幸福度を定義し，これを六面体の配置及びスムージングに用いることにより，六面体メッシュの生成を自動で行うことが可能であることが示せた．
今回は特徴線情報の抽出を自動化していなかったが，曲面形状を含む複雑なモデルや球体等の形状に対し，特徴線を自動で抽出する事ができれば，適応可能なモデル形状が増えるため，今後の課題としたい．

70References[1] D. Sinclair. ”S-hull: a fast sweep-hull routine fordelaunay triangulation”, 2016.
[2] Ramsay Dyer, Hao Zhang and Torsten Möller:”Delaunay Mesh Construction”, Eurographics
Symposium on Geometry Processing, 2007.
[3] Stefan Gumhold, Xinlong Wang and Rob
Macleod:”Feature Extraction From PointClouds”, Proceedings of the 10th InternationalMeshing Roundtable, Sandia National Laboratories, pp.293-305, October 7-10 2001.
[4] L. Yufei, L. Yang, X. Weiwei, W. Wenping andG. Baining, All-hex meshing using singularityrestricted ﬁeld, ACM TOG, No. 6, p. 177 (2012).
[5] M. J. Ray, T. J. Timothy and T. M. Philip,
The” Hex-Tet” Hex-Dominant Meshing Algorithm as Implemented in CUBIT, IMR, pp. 151–158 (1998).
[6] M. Loı̈c, Advances in octree-based all-hexahedralmesh generation: handling sharp features, Proceedings of the 18th International Meshing
Roundtable, pp. 65–84 (2009).
[7] B. D. Ted and M. J. Ray, Seams and wedges inplastering: a 3-D hexahedral mesh generation algorithm, Engineering with computers, No. 2, pp.
83–93 (1993).
[8] L. Xin, G. Ziaohu, W. Hongyu, H. Ying, G. Xianfeng and Q. Hong, Harmonic volumetric mapping for solid modeling applications, Proceedingsof the 2007 ACM symposium on Solid and physical modeling, pp. 109–120 (2007).