「メッシュ処理」の版間の差分

2016年8月1日 (月) 22:21時点における版

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

基礎

Fig. 1

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

メッシュ（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の並び順が右（又は左）周りで統一されたメッシュである．向き付けされたメッシュでは，三角形の法線ベクトルを導出する場合に，二つの辺の外積を統一した順番で計算するとメッシュ全体で揃った向きの法線が得られ，曲面の向きとなる．

Fig. 2

データ構造

最も簡単なデータ構造は，次元毎にポリトープを多次元（又は複数やオブジェクト指向型言語でのクラスの）配列等に格納する方法である．例えば，三角形メッシュであれば面に基づくデータ構造が簡単で，頂点ID順に頂点位置を格納した頂点列と，頂点IDを三つ組みである面を面ID順に格納した面列で表現できる．このとき，向き付けされたメッシュの場合は，頂点IDの並び順を入れ替えない注意が必要である．

• セルに基づくデータ構造

各セル毎に構造体やオブジェクト指向言語のクラスを用いてセルを定義し，その関係性を構造体・クラスのメンバー変数やポインターとして持つ構造もよく用いられている．例えば三角形メッシュであれば，頂点，辺，面毎にクラスを作成し，それぞれにポインターや変数で参照を行う（half）edgeデータ構造^[1]が有名である．また，progressive mesh ^[2]等のメッシュの粗密階層を表現するデータ構造もある．

ファイルフォーマット

様々な種類があり，曲面メッシュではoff, ply, obj, stl等が有名である．最も簡単なascii offファイルフォーマットは，asciiテキストにて，一行目に「OFF」という文字列，二行目に頂点数，面数，辺数をスペース区切，３行目から頂点の３次元座標をスペース区切（一行一頂点），頂点情報の後に面の頂点IDを一面一行毎にスペース区切で並べるだけである（頂点IDはゼロから始まる）．

• STL（STereoLithography）の注意点

stlは様々なCAD/CAEソフトウェアで読み込みが可能な曲面メッシュで幅広く用いられている．ファイルフォーマット名であり，メッシュ自体の呼称ではない．幾何学的な注意点として，頂点を面毎に重複して持つため，データ量が多くなるだけではなく，同一頂点である事に一意性が無い．offやobjフォーマットなどは，その様な曖昧さを回避出来るだけではなく，重複頂点も表せる．

応用

幅広い分野で様々な目的にメッシュ処理は用いられている．特に，CG（Computer Graphics），CAD（Computer Aided Design），CV（Computer Vision），及び計算物理学/CAE（Computational Physics/Computer Aided Engineering）での形状・計算領域の表現にて重要である．

メッシュ処理に有用・必要な学問

メッシュ処理は幾何学全般に基づいており，数学モデル・定理，離散化やアルゴリズムなど幅広い数学的・情報学的な知識が必要である．

微分幾何学^[3][4]

メッシュを多様体の近似として用いる場合に，長さや曲率などの計量を考えるのに必要である．

位相幾何学^[5][6]

穴やハンドル（topological handle）の数などメッシュの繋がり具合を考える場合に必要．多様体を近似しているメッシュだけでなく，有名なオイラー数（Euler Characteristics）や種数（genus）などメッシュ自体の位相構造でも重要である．

計算幾何学/組合せ幾何学/多面体幾何学^{[7][8][9][10]}

ボロノイ図（Voronoi diagram）やその双対（dual）であるドロネー図（Delaunay三角形分割）の構成方法や幾何構造の組合せ・配置に関する数学．

曲線と曲面の幾何学/スプライン^[11][12][13]

メッシュを曲線・曲面の近似として用いる場合に必要である．また，スプライン（spline）の制御メッシュなど空間を定義するのに用いる．

グラフ理論^[14]

媒介変数化（mesh parameterization）でのグラフの埋め込みやグラフラプラス作用素の固有値解析などメッシュ構造自体の解析に有用である．また，EMST（Euclidean minimum spanning tree）やGabriel/Reebグラフなどは点群のメッシュ化，曲面メッシュの分割，メッシュのスケルトン（アニメーションや変形のための中心構造）抽出にて有用である．

アルゴリズムとデータ構造^[15]

通常，メッシュの要素数は大きいため，メッシュ構造の探索や並び替え等の基本操作にて効率的なデータ構造と計算方法が必要である．また，木構造の操作なども広義のメッシュ処理と言える．

近似理論・数値解析^[16]

曲線や曲面の離散化，多元線形連立方程式や偏微分方程式の解法，最適化問題の解法などの数値解析はメッシュ処理で必要な技術である．

信号・画像処理^[17]

離散化された一次元信号や画像は，メッシュの特殊な場合と考えられる．それゆえ，フィルタや多重解像度解析などの数理モデル・方法論を一般のメッシュ処理に拡張する場合に有用である．

処理の種類

メッシュ処理には大別して，幾何・位相・局所・大域及びその組合せの処理がある．幾何及び位相の処理は，それぞれ頂点座標とconnectivityに対して行う処理である．局所的な処理（例えばFig. 3の操作）は，メッシュ内の限定された領域にしか影響を及ぼさない（又は用いない）処理であり，大域的な処理はその逆である．形状や領域の近似精度，滑らかさ，ポリトープ要素の性質（例えば三角形の形など）を基準に処理を行う．具体的なメッシュ処理の目的や方法は非常に多様である．下記に代表的な処理の例を挙げる．

Fig. 3

メッシュ化（meshing）

領域を充足する格子生成^[18]や点群，スプライン，陰関数などからメッシュを構成する処理．特に曲面メッシュの場合は，曲面再構成問題^[19][20]として知られる．また，陰関数からのメッシュ生成はMarching Cube法^[21]が有名である．

再メッシュ化（remeshing）

与えられたメッシュをポリトープのサイズ，数，形状などが異なる性質をもつメッシュに変換する処理．例えば，有限要素解析では均一の大きさの正三角形が良いとされるが，形状近似では主曲率の比と主方向に沿った長細い三角形が最適である事が知られている^[22]．また，二つ以上のメッシュの縫い合わせ（stitching）なども再メッシュ化の一種である．

細分割（subdivision）

ポリトープを細かく分割する処理．ある規則に従って細分割を行うと，B-spline等の連続で滑らかなスプラインに収束する事が知られている^[23]．Chaikin ^[24]やLoop ^[25]のアルゴリズムが有名であり，Wavelet等の多重解像度解析とも密接に関連している ^[23]．

簡略化（simplification/decimation）

元の形状を近似しながらポリトープの数を減らす処理 ^[26]．QSlim ^[27]が非常に有名である．QSlimは，局所的な幾何・位相操作をpriority heap queueを用いて行うなど，メッシュ処理の基礎が詰まっている（Loopの細分割法 ^[25]及び平均曲率流 （mean curvature flow）^[28]と合わせて初学者の学習向けにも優れている）．

Fig. 4

多重解像度・スペクトラム解析（multiresolutional/spectrum analyses）

メッシュを周波数分解・操作する処理．細分割と簡略化を用いてB-spline waveletの 拡張とする方法群 ^[29]やメッシュのラプラス作用素の固有関数展開 ^[30]等がある．周波数別に形状を操作する事で，詳細強調・平滑化・変形など様々な処理に有用である．

関数近似・陰関数化・補間・意匠設計（fitting/implicitization/interpolation/aesthetic design）

メッシュからベジエ/NURBS ^[11][12]等の連続で滑らかな多様体や離散近似としての意匠メッシュ（Euler スプライン，Willmore曲面，Thin-plate spline等）^[31]の生成を行う処理．

平滑化・ノイズ除去（smoothing/noise reduction）

形状を平滑化し，ノイズの除去を行う処理．信号・画像処理のフィルタ理論が適応されているだけではなく，平均曲率流 （mean curvature flow）^[28][32]やScreened Poisson方程式 ^[33]などの幾何学的な偏微分方程式に基づく方法群が多数提案されている．また，平滑化処理は，細分化，多重解像度解析，変形などで基礎操作として用いられている．

変形（deformation/warping）

形状を幾何学的に変形する処理．FFD （Free-Form Deformation）^[34]やRBF（Radial Basis Function）などを使用してメッシュが埋め込まれた空間を変形するアプローチ，力学変形を簡略化する方法群や，メッシュのラプラス作用素とPoisson方程式に基づく方法群 ^[35][36]等がある．Poisson方程式に基づく方法群は，画像や形状のseamless合成へも適用されている．

引用

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

1. ↑ M. Botsch, L. Kobbelt , M. Pauly , P. Alliez, and B. Levy, “Polygon Mesh Processing”, A K Peters/CRC Press, 2011.
2. ↑ H. Hoppe, “Progressive Meshes”, Proc. ACM SIGGRAPH, pp. 99-108, 1996.
3. ↑ D. Struik, “Lectures on Classical Differential Geometry”, Dover Publications, 1988.
4. ↑ E. Abbena , A. Gray, and S. Salamon, “Modern Differential Geometry of Curves and Surfaces with Mathematica, 4th Ed”, Chapman and Hall/CRC, 2016.
5. ↑ 前原 濶, “直観トポロジー”, 共立出版, 1993.
6. ↑ A. Fomenko and T. Kunii, “Topological Modeling for Visualization”, Springer, 2013.
7. ↑ H. Edelsbrunner, “Algorithms in Combinatorial Geometry”, Springer-Verlag, 1987.
8. ↑ 杉原 厚吉, “計算幾何学”, 朝倉書店, 2013.
9. ↑ 今井 浩, 今井 桂子, “計算幾何学”, 共立出版, 1994.
10. ↑ P. R. クロムウェル (著), 下川航也 (訳), 平澤美可三 (訳), 松本三郎 (訳), 丸本嘉彦 (訳), 村上斉 (訳), “多面体”, 数学書房, 2014.
11. ↑ ^{11.0 11.1} G. Farin, “Curves and Surfaces for CAGD, Fifth Edition: A Practical Guide”, Morgan Kaufmann, 2001.
12. ↑ ^{12.0 12.1} 穂坂 衛(著), 東 正毅 (訳), 久志本 琢也 (訳), 斉藤 剛 (訳), “CAD/CAMにおける曲線曲面のモデリング”, 東京電機大学出版局, 1996.
13. ↑ J. Koenderink, “Solid Shape”, MIT Press 1990.
14. ↑ W. Tutte, “Graph Theory”, Cambridge University Press, 2001.
15. ↑ R. Sedgewick, “Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms”, Addison-Wesley Professional, 2001.
16. ↑ W. Press, S. Teukolsky, W. Vetterling, and B. Flannery, “Numerical Recipes: The Art of Scientific Computing 3rd Edition”, Cambridge University Press, 2007.
17. ↑ R. Gonzalez, “Digital Image Processing”, Prentice Hall; 3rd edition, 2007.
18. ↑ Joe F. Thompson (編), Bharat K. Soni (編), Nigel P. Weatherill (編) , “Handbook of Grid Generation”, CRC Press, 1998.
19. ↑ 大竹 豊, “点群からの表面再構成”, 計算工学 16(2), pp. 2523-2527, 2011.
20. ↑ 長井 超慧, “3Dスキャナによる計算機への現物形状入力”, 精密工学会誌 79(6), pp. 497-501, 2013.
21. ↑ W. Lorensen and H. Cline, “Marching cubes: A high resolution 3D surface construction algorithm”, Proc. ACM SIGGRAPH, pp. 163-169, 1987.
22. ↑ P. Alliez, M. Attene, C. Gotsman, and G. Ucelli, “Recent Advances in Remeshing of Surfaces”, Shape Analysis and Structuring, pp. 53-82 , 2007.
23. ↑ ^{23.0 23.1} D. Zorin, P. Schroeder, T. DeRose, L. Kobbelt, A. Levin, and W. Sweldens, “Subdivision for Modeling and Animation”, ACM SIGGRAPH courses, 2000.
24. ↑ G. Chaikin, "An Algorithm for High Speed Curve Generation", Computer Graphics Image Processing, 3(12), pp. 346-349 , 1974.
25. ↑ ^{25.0 25.1} C. Loop, “Smooth Subdivision Surfaces Based on Triangles”, M.S. Mathematics thesis, University of Utah, 1987.
26. ↑ M. Garland, “Quadric-Based Polygonal Surface Simplification”, PhD Dissertation, Carnegie Mellon University, 1999.
27. ↑ M. Garland and P. Heckbert, “Surface simplification using quadric error metrics”, Proc. ACM SIGGRAPH, pp. 209-216, 1997.
28. ↑ ^{28.0 28.1} M. Desbrun, M. Meyer, P. Schroder, and A. Barr, “Implicit fairing of irregular meshes using diffusion and curvature flow”, Proc. ACM SIGGRAPH, pp. 317-324, 1999.
29. ↑ P. Heckbert, J. Rossignac, H. Hoppe, W. Schroeder, M. Soucy, and A. Varshney, “Multiresolution Surface Modeling”, ACM SIGGRAPH courses, 1997.
30. ↑ B. Levy and H. Zhang, “Spectral mesh processing”, ACM SIGGRAPH courses, 2010.
31. ↑ E. Grinspun, M. Desbrun, K. Polthier, P. Schroder, and A. Stern, “Discrete Differential Geometry: An Applied Introduction”, ACM SIGGRAPH courses, 2007.
32. ↑ J. Sethian, “Level Set Methods and Fast Marching Methods”, 2nd edition, Cambridge University Press, 1999.
33. ↑ M. Chuang and M. Kazhdan, “Interactive and anisotropic geometry processing using the screened Poisson equation”, ACM TOG (SIGGRAPH), 30(4), pp. 57:1--57:10, 2011.
34. ↑ T. Sederberg and S. Parry, “Free-form deformation of solid geometric models”, Proc. ACM SIGGRAPH, pp. 151-160, 1986.
35. ↑ O. Sorkine, “Laplacian Mesh Processing”, EUROGRAPHICS STAR, 2005.
36. ↑ M. Alexa, “Mesh editing based on discrete Laplace and Poisson models”, ACM SIGGRAPH courses, 2006.