メッシュ処理

メッシュ処理（Mesh Processing）とは，幾何形状・領域を一次近似・表現するポリトープ（polytope）網を計算処理する事である．ここでポリトープとは，一般化された図形であり，例えば零次元から三次元までのポリトープはそれぞれ，点，線分，多角形，多面体である．メッシュはポリトープの和集合として与えられる．メッシュ処理では，幾何学全般に基づき幾何的又は位相的な操作を行う事で，新たなメッシュや多様体を生成する．また，メッシュ自体の幾何・位相情報の解析，誤差解析や物理計算の為にメッシュ情報の参照を行う事もメッシュ処理である．古代では多角形・多面体幾何学，近代では設計・近似のためのスプラインやボロノイ図等の研究がされているが，コンピュータの登場により，精密工学に密接なCAD・CAM・CAE・CAT及びCG・CVでの応用が盛んである．

基礎

Meshprocessing Fig1

メッシュはポリトープの集合であり，メッシュ処理とは，メッシュの幾何・位相情報を参照・追加・削除・変更する処理である．

メッシュ（mesh）

ポリトープの集合．例えば，三角形メッシュ（triangle mesh）は，三角形の連結した集合である．多様体の一次近似又は曲線や曲面などの領域・空間を充足するダイアグラム（diagram）として用いる事が多いが，一般のグラフやデジタル画像なども広義のメッシュである．非多様体のメッシュとしては一部の単体的複体（simplical complex）やCW-complex（中心軸：Medial Axis等）などがある．

ポリトープ（polytope）

多角形や多面体等を一般化した幾何要素であり，n次元ポリトープは，ファセット（facet）やセル（cell）と呼ばれる（n-1）次元までのポリトープで構成される．零次元から三次元までのポリトープはそれぞれ，点，線分，多角形，多面体である．例えば，三角形は，３つの0-cellである頂点（vertex），３つの1-cellである辺（edge）及び一つの2-cellである面（face）から構成される．

k-近傍（k-ring, k-link）

頂点に辺で繋がったk番目の近傍．

Valence

頂点に繋がっている辺数．

Degree

面を構成している頂点数．

Connectivity

辺の繋がり情報．

メッシュの状態

• 多様体メッシュ（manifold mesh）

1-linkがtopological disk（高次元ではball）と同位相である頂点のみで構成されたメッシュ．境界ではhalf-diskと同位相．曲面メッシュ（surface mesh）で最も用いられているのは多様体である三角形メッシュである．これは，どの様な位相の曲面でも三角形分割が可能である事と三角形メッシュの面は平面であり，法線ベクトルが一意に決まる事に起因する．また，物理計算やrenderingハードウェアでの三角形メッシュに基づく方法が非常に発達している事も三角形メッシュの普及に大きく寄与している．以後，特に断りがなければメッシュは多様体であることを仮定する．

• n-連結メッシュ（n-connected mesh）

任意のn個の頂点を削除しても連結しているメッシュ．

• 水密（watertight）メッシュ

穴が無いメッシュ．例えば三角形メッシュでは，全ての辺が二つの三角形に共有されているメッシュ．

• 規則（Regular）メッシュ

多角形のdegreeによってvalenceがメッシュ全体の全ての内部頂点で一定のメッシュ．例えば，三角形メッシュは内部頂点でvalenceが６，四角形メッシュは内部頂点でvalenceが４のメッシュ．重要な注意点としては，形状の位相によっては，regular meshがオイラー数の関係より，数学的に存在しない事である．従って大部分の頂点でregularなvalenceを満たすメッシュを準規則メッシュ（semi-regular mesh）と呼び，regularでない頂点をextraordinary vertexと呼ぶ．

• 向き付け（oriented）メッシュ

全てのセルの方向が揃っているメッシュ．例えば三角形メッシュでは，三角形の頂点IDの並び順が右（又は左）周りで統一されたメッシュである．向き付けされたメッシュでは，三角形の法線ベクトルを導出する場合に，二つの辺の外積を統一した順番で計算するとメッシュ全体で揃った向きの法線が得られ，曲面の向きとなる．

Meshprocessing Fig2.bmp

Connectivity

辺の繋がり情報．

Connectivity

辺の繋がり情報．

データ処理

装置からの直接的な出力はX線の投影データ（サイノグラム）であり、計算機上でCT再構成)を行うことにより断面像（トモグラム）を得る。寸法計測のために形状データが必要な場合には、断面像上で注目する物体とそれ以外の領域の境界面をポリゴンメッシュとして抽出する。図2にこれらの処理の例を示す。

引用

原著論文、著書など、他に著作権の存在する出版物等を引用する場合は、ここに脚注のリストを表示するようにしてください。

---