﻿ 基于离散微分几何的3D网格模型分析进展综述 Review on 3D Mesh Model Analysis Based on the Discrete Differential Geometry

Mechanical Engineering and Technology
Vol. 08  No. 05 ( 2019 ), Article ID: 32491 , 11 pages
10.12677/MET.2019.85041

Review on 3D Mesh Model Analysis Based on the Discrete Differential Geometry

Dong-Qing Wu1,2, Jian Gao1*, Zheng-Tao Xiao1,3

1State Key Laboratory of Precision Electronic Manufacturing Technology & Equipment, Guangdong University of Technology, Guangzhou, Guangdong

2School of Computational Science, Zhongkai University of Agriculture and Engineering, Guangzhou, Guangdong

3School of Electro-mechnical Engineering, Guangdong Polytechnic of Industry and Commerce, Guangzhou, Guangdong

Received: Sep. 19th, 2019; accepted: Oct. 4th, 2019; published: Oct. 11th, 2019

ABSTRACT

The analysis of 3D models has become a hot topic in computer graphics research in recent years. Aiming at the application problems of mesh denoising and smoothing, mesh parameterization and non-rigid registration in the field of discrete differential geometry, this paper reviews the literature on the application of discrete differential geometry theory in analysis, mathematical modeling and algorithm design in recent years, and introduces the research progress of discrete differential geometry in the field of 3D model analysis. The difficulties and possible research directions in the future are summarized.

Keywords:3D Model Analysis, Discrete Differential Geometry, Mesh Smoothness, Mesh Parameterization, Non-Rigid Registration

1精密电子制造技术与装备省部共建国家重点实验室广东工业大学机电工程学院，广东 广州

2仲恺农业工程学院计算科学学院，广东 广州

3广东工贸职业技术学院机电学院，广东 广州

3D网格模型的分析越来越成为近年来计算机图形学研究的热点问题。文中针对3D网格模型分析领域内的网格去噪平滑、网格参数化以及非刚性配准等应用问题,评述和回顾近年来应用离散微分几何理论进行分析、数学建模和算法设计的文献，介绍离散微分几何在3D模型分析领域的研究进展，并对相关问题难点和未来可能的研究方向进行了归纳和总结。

1. 引言

2. 离散微分几何的理论框架

2.1. 基本概念

2.2. 算子

$\nabla u\left(v\right)=\underset{i}{\sum }{u}_{i}\nabla {\delta }_{i}\left(v\right).$ (1)

$\nabla \cdot w\left({v}_{i}\right):=\underset{{f}_{j}\in {N}_{f}\left({v}_{i}\right)}{\sum }{A}_{{f}_{j}}w\left({f}_{j}\right)\cdot {\nabla {\delta }_{i}|}_{{f}_{j}},$ (2)

$\Delta u=\nabla \cdot \nabla u=\underset{j\in {i}^{\ast }}{\sum }{\omega }_{ij}\left({u}_{i}-{u}_{j}\right),$ (3)

$\left(\Delta -\frac{\partial }{\partial t}\right)u\left(x,t\right)=0.$ (4)

${h}_{t}\left(x,y\right)=\underset{i=0}{\overset{\infty }{\sum }}{\text{e}}^{-{\lambda }_{i}t}{\varphi }_{i}\left(x\right){\varphi }_{i}\left(y\right),$ (5)

3. 基于离散微分几何的3D模型分析

3.1. 网格去噪光滑

$\Delta u=-Ku,$ (6)

${u}^{N}=h{\left(K\right)}^{N}u.$ (7)

3.2. 网格参数化

(1) Dirichlet能量方法的网格参数化

$E\left({v}_{i}\right)=\lambda {E}_{A}\left({v}_{i}\right)+\mu {E}_{\chi }\left({v}_{i}\right),$ (8)

${E}_{A}\ge \frac{1}{2}\underset{M}{\int }{f}_{u}×{f}_{v}\text{d}u\text{d}v$ .

${E}_{A}\left({x}_{i}\right)=\underset{j\in {i}^{*}}{\sum }\mathrm{cot}{\alpha }_{ij}{‖{v}_{i}-{v}_{j}‖}^{2}.$ (9)

${E}_{\chi }$ 为欧拉示性数的变形能量，定义为：

${E}_{\chi }\left({x}_{i}\right)=\underset{j\in {i}^{*}}{\sum }\frac{\mathrm{cot}{\xi }_{ij}+\mathrm{cot}{\zeta }_{ij}}{{‖{v}_{i}-{v}_{j}‖}^{2}}{‖{p}_{i}-{p}_{j}‖}^{2},$ (10)

Figure 1. A ring on a mesh mapped to a ring on a plane domain

$\frac{\partial {E}_{A}}{\partial {p}_{i}}=\underset{j\in {i}^{*}}{\sum }\left(\mathrm{cot}{\alpha }_{ij}+\mathrm{cot}{\beta }_{ij}\right)|{p}_{i}-{p}_{j}|=0$ (11)

$\frac{\partial {E}_{\chi }}{\partial {p}_{i}}=\underset{j\in {i}^{*}}{\sum }\frac{\left(\mathrm{cot}{\xi }_{ij}+\mathrm{cot}{\zeta }_{ij}\right)|{p}_{i}-{p}_{j}|}{{‖{v}_{i}-{v}_{j}‖}^{2}}=0$ (12)

(2) Circle packing的网格参数化

Thurston首先提出了用一系列变化的圆来近似从平面到单位圆盘的黎曼映射，从而实现网格到平面的保角映射 [31] 。文献 [32] 提出一种新的构造任意拓扑面网格到平面的离散共形映射的方法。该方法是基于圆模式(Circle packing)，即每个三角面与一个圆相对应，按照预设的夹角来调整圆的半径来达到保角映射的目的。该方法相对于调和映射有两方面的优势：1) 支持自然边界条件和规定的曲率控制边界形状的边界；2) 该解是基于作为函数的凸能量，用简单的显式表达式表示对数半径变量梯度和Hessian矩阵，因而更为稳健和高效。

$\frac{\text{d}{\gamma }_{i}}{\text{d}t}=\left({\stackrel{˜}{K}}_{{v}_{i}}-{K}_{{v}_{i}}\right){\gamma }_{i},$ (13)

$F\left(u\right)=-{\int }_{0}^{u}\underset{i}{\sum }\left({\stackrel{˜}{K}}_{{v}_{i}}-{K}_{{v}_{i}}\right)\text{d}{u}_{i}.$ (14)

3.3. 非刚性配准

3D刚性配准问题是指同一个实体在不同坐标系下采集得到的两个3D模型，经过刚体变换到同一个坐标系的同样姿态。这类算法是目标识别，误差估计算法的上游算法，具有广泛的应用意义，实现的算法也非常多。一般的分类如图2

Figure 2. Classification of registration algorithms

$\left({\mathcal{D}}^{*},{\gamma }^{*}\right)=\underset{\mathcal{D}\in SO\left(3\right),\gamma \in \Gamma }{\mathrm{arg}\mathrm{min}}\stackrel{˜}{d}\left({S}_{1},\mathcal{D}{S}_{2}\circ \gamma \right),$ (15)

Figure 3. Transitional deformation between two models measured by geodesic lines, extracted from Figure 7.2(c) in reference [1]

$L\left(\Theta \right)={\int }_{0}^{1}{〈{\nabla }_{\tau }\Theta \left(\tau \right),{\nabla }_{\tau }\Theta \left(\tau \right)〉}^{1/2}\text{d}\tau .$ (16)

${\Theta }^{*}=\underset{\left(D,\gamma \right)\in SO\left(3\right)×\Gamma }{\mathrm{arg}\mathrm{min}}\left\{\underset{\begin{array}{l}\Theta :\left[0,1\right]\to S,\\ \Theta \left(0\right)={S}_{1},\\ \Theta \left(1\right)=D\left({S}_{1}\circ \gamma \right)\end{array}}{\mathrm{min}}L\left(\Theta \right)\right\}.$ (17)

4. 总结

Review on 3D Mesh Model Analysis Based on the Discrete Differential Geometry[J]. 机械工程与技术, 2019, 08(05): 354-364. https://doi.org/10.12677/MET.2019.85041

1. 1. Xiong, L., et al. (2017) Robust Non-Rigid Registration Based on Affine ICP Algorithm and Part-Based Method. Neural Processing Letters, 48, 1305-1321. https://doi.org/10.1007/s11063-017-9760-x

2. 2. Khader, M., Schiavi, E. and Hamza, A.B. (2015) A Multicomponent Approach to Nonrigid Registration of Diffusion Tensor Images. Applied Intelligence, 46, 241-253. https://doi.org/10.1007/s10489-016-0833-8

3. 3. Lebedev, V.I. and Agoshkov, V.I. (2019) Poincaré-Steklov Operators and Their Applications in Analysis. Computational Processes and Systems, 2, 173-227.

4. 4. Yu, W., et al. (2018) Steklov Spec-tral Geometry for Extrinsic Shape Analysis. ACM Transactions on Graphics, 38, 1-21.

5. 5. Liu, J., Sun, J. and Turner, T. (2018) Spectral Indicator Method for a Non-Self Adjoint Steklov Eigenvalue Problem.

6. 6. Ma, J., et al. (2017) Feature Guided Gaussian Mixture Model with Semi-Supervised EM and Local Geometric Constraint for Retinal Image Registration. Information Sciences, 417, 128-142. https://doi.org/10.1016/j.ins.2017.07.010

7. 7. Laga, H., et al. (2018) 3D Shape Analysis: Fundamentals, Theory, and Applications. Wiley, Hoboken, 368. https://doi.org/10.1002/9781119405207

8. 8. Adamczewski, K., Suh, Y. and Lee, K.M. (2016) Discrete Tabu Search for Graph Matching. IEEE International Conference on Computer Vision, Santiago, 7-13 December 2015, 109-117. https://doi.org/10.1109/ICCV.2015.21

9. 9. Meyer, M. (2002) Discrete Differential-Geometry Operator for Triangu-lated 2-Manifolds. Visualization & Mathematics, 3, 35-57. https://doi.org/10.1007/978-3-662-05105-4_2

10. 10. Ma, J., et al. (2019) Locality Preserving Matching. International Journal of Computer Vision, 127, 512-531. https://doi.org/10.1007/s11263-018-1117-z

11. 11. Sun, J., Ovsjanikov, M. and Guibas, L. (2010) A Concise and Provably Informative Multi-Scale Signature Based on Heat Diffusion. Computer Graphics Forum, 28, 1383-1392. https://doi.org/10.1111/j.1467-8659.2009.01515.x

12. 12. Schroff, F., Kalenichenko, D. and Philbin, J. (2015) FaceNet: A Unified Embedding for Face Recognition and Clustering. IEEE Conference on Computer Vision & Pattern Recognition, Boston, 7-12 June 2015, 815-823. https://doi.org/10.1109/CVPR.2015.7298682

13. 13. Benguria, R.D., Brandolini, B. and Chiacchio, F. (2019) A Sharp Estimate for Neumann Eigenvalues of the Laplace-Beltrami Operator for Domains in a Hemisphere. Communications in Contemporary Mathematics. https://doi.org/10.1142/S0219199719500184

14. 14. Peyré, G. and Cuturi, M. (2019) Computational Optimal Transport. Working Paper.

15. 15. Qi, C.R., et al. (2017) PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space.

16. 16. Bonneel, N. and Coeurjolly, D. (2019) SPOT: Sliced Partial Optimal Transport. ACM Transactions on Graphics, 38, Article No. 89. https://doi.org/10.1145/3306346.3323021

17. 17. Wang, Y., et al. (2018) Dynamic Graph CNN for Learning on Point Clouds.

18. 18. Han, Z., et al. (2017) Mesh Convolutional Restricted Boltzmann Machines for Unsupervised Learning of Fea-tures with Structure Preservation on 3-D Meshes. IEEE Transactions on Neural Networks & Learning Systems, 28, 2268-2281. https://doi.org/10.1109/TNNLS.2016.2582532

19. 19. Minakshisundaram, S. and Pleijel, Å. (1949) Some Properties of the Eigenfunctions of the Laplace-Operator on Riemannian Manifolds. Canadian Journal of Mathematics, 3, 242-256. https://doi.org/10.4153/CJM-1949-021-5

20. 20. Bott, R. and Tu, L.W. (2009) Differential Forms in Algebraic Topology. Graduate Texts in Mathematics Book Series (GTM, Volume 82). Springer, New York.

21. 21. Desbrun, M., et al. (1999) Implicit Fairing of Irregular Meshes Using Diffusion and Curvature Flow. ACM SIGGRAPH Proceedings, Los An-geles, 28 July 2019, 317-324. https://doi.org/10.1145/311535.311576

22. 22. Vaxman, A., Ben-Chen, M. and Gotsman, C. (2010) A Multi-Resolution Approach to Heat Kernels on Discrete Surfaces. ACM Transactions on Graphics, 29, 1-10. https://doi.org/10.1145/1778765.1778858

23. 23. Field, D.A. (2010) Laplacian Smoothing and Delaunay Triangulations. International Journal for Numerical Methods in Biomedical Engineering, 4, 709-712. https://doi.org/10.1002/cnm.1630040603

24. 24. Taubin, G. (1995) A Signal Processing Approach to Fair Surface Design. Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques, Los Angeles, 6-11 August 1995, 351-358. https://doi.org/10.1145/218380.218473

25. 25. Ohtake, Y., Belyaev, A. and Bogaevski, I. (2001) Mesh Regularization and Adaptive Smoothing. Computer Aided Design, 33, 789-800. https://doi.org/10.1016/S0010-4485(01)00095-1

26. 26. Yadav, S.K., Reitebuch, U. and Polthier, K. (2017) Robust and High Fidelity Mesh Denoising. IEEE Transactions on Visualization & Computer Graphics, 99, 2304-2310. https://doi.org/10.1109/TVCG.2018.2828818

27. 27. Devito, Z., et al. (2017) Opt: A Domain Specific Language for Non-Linear Least Squares Optimization in Graphics and Imaging. ACM Transactions on Graphics, 36, 1-27. https://doi.org/10.1145/3132188

28. 28. Taime, A., Saaidi, A. and Satori, K. (2015) Comparative Study of Mesh Simplification Algorithms. Proceedings of the Mediterranean Conference on Information & Communication Technologies, Saïdia, 7-9 May 2015, 287-295. https://doi.org/10.1007/978-3-319-30301-7_30

29. 29. Dym, N., Shtengel, A. and Lipman, Y. (2015) Homotopic Morphing of Planar Curves. Computer Graphics Forum, 34, 239-251. https://doi.org/10.1111/cgf.12712

30. 30. Liu, X., et al. (2010) Constrained Fairing for Meshes. Computer Graphics Fo-rum, 20, 115-123. https://doi.org/10.1111/1467-8659.00483

31. 31. Zheng, Y., et al. (2011) Bilateral Normal Filtering for Mesh Denoising. IEEE Transactions on Visualization & Computer Graphics, 17, 1521-1530. https://doi.org/10.1109/TVCG.2010.264

32. 32. Zhang, J., et al. (2018) Static/Dynamic Filtering for Mesh Geometry. IEEE Transactions on Visualization & Computer Graphics, 25, 1774-1787.

33. 33. Yuan, G. and Sheng, Z. (2008) Monotone Finite Volume Schemes for Diffusion Equations on Polygonal Meshes. Journal of Computational Physics, 227, 6288-6312. https://doi.org/10.1016/j.jcp.2008.03.007

34. 34. Seo, S., Chung, M.K. and Vorperian, H.K. (2010) Heat Kernel Smoothing Using Laplace-Beltrami Eigenfunctions. In: International Conference on Medical Image Computing & Computer-Assisted Intervention, Springer, Beijing, 505-512. https://doi.org/10.1007/978-3-642-15711-0_63

35. 35. Wei, M., et al. (2019) Mesh Denoising Guided by Patch Normal Co-Filtering via Kernel Low-Rank Recovery. IEEE Transactions on Visualization and Computer Graphics, 25, 2910-2926. https://doi.org/10.1109/TVCG.2018.2865363

36. 36. Tao, L., et al. (2016) Secondary Laplace Operator and Generalized Giaquinta-Hildebrandt Operator with Applications on Surface Segmentation and Smoothing. Computer-Aided Design, 70, 56-66. https://doi.org/10.1016/j.cad.2015.07.009

37. 37. Alexa, M. and Wardetzky, M. (2011) Discrete Laplacians on General Polygonal Meshes. ACM Transactions on Graphics, 30, Article No. 102. https://doi.org/10.1145/2010324.1964997

38. 38. Manzini, G., Russo, A. and Sukumar, N. (2014) New Perspectives on Polygonal and Polyhedral Finite Element Methods. Mathematical Models & Methods in Applied Sciences, 24, 1665-1699. https://doi.org/10.1142/S0218202514400065

39. 39. Carl, W. (2016) A Laplace Operator on Semi-Discrete Surfaces. Foundations of Computational Mathematics, 16, 1115-1150. https://doi.org/10.1007/s10208-015-9271-y

40. 40. 郭凤华, 张彩明, 焦文江. 网格参数化研究进展[J]. 软件学报, 2016, 27(1): 112-135.

41. 41. Pinkall, U. and Polthier, K. (1993) Computing Discrete Minimal Surfaces and Their Conjugates. Experimental Mathematics, 2, 15-36. https://doi.org/10.1080/10586458.1993.10504266

42. 42. Stephenson, K. (2005) Introduction to Circle Packing. Cambridge University Press, Cambridge, 12, 356.

43. 43. Kharevych, L., Springborn, B. and Schröder, P. (2006) Discrete Conformal Mappings via Circle Patterns. ACM Transactions on Graphics, 25, 412-438. https://doi.org/10.1145/1138450.1138461

44. 44. Gu, X.D. and Yau, S.T. (2008) Computational Conformal Geometry. Higher Education Press, Beijing, 389-429. https://doi.org/10.1007/s11786-011-0065-6

45. 45. Rueckert, D. and Aljabar, P. (2015) Non-Rigid Registration Using Free-Form Deformations. In: Handbook of Biomedical Imaging: Methodologies, Springer Science + Business Media, New York, 277-294. https://doi.org/10.1007/978-0-387-09749-7_15

46. 46. Rodriguez, D. and Behnke, S. (2018) Transferring Category-Based Functional Grasping Skills by Latent Space Non-Rigid Registration. IEEE Robotics & Automation Letters, 3, 2662-2669. https://doi.org/10.1109/ICRA.2018.8461169

47. 47. Yan, L., et al. (2018) Automatic Non-Rigid Registration of Multi-Strip Point Clouds from Mobile Laser Scanning Systems. International Journal of Remote Sensing, 39, 1713-1728. https://doi.org/10.1080/01431161.2017.1410248

48. 48. Kuklisova Murgasova, M., et al. (2017) Distortion Correction in Fetal EPI Using Non-Rigid Registration with a Laplacian Constraint. IEEE Transactions on Medical Imaging, 33, 12-19. https://doi.org/10.1109/TMI.2017.2667227

49. 49. Torbati, N. and Ayatollahi, A. (2019) A Transformation Model Based on Dual-Tree Complex Wavelet Transform for Non-Rigid Registration of 3-D MRI Images. International Journal of Wavelets, Multiresolution and Information Processing, 17, Article ID: 1950025. https://doi.org/10.1142/S0219691319500255

50. 50. Zhang, J., et al. (2018) Non-Rigid Image Registration by Minimizing Weighted Residual Complexity. Current Medical Imaging Reviews, 14, 334-346. https://doi.org/10.2174/1573405613666170703122534

51. 51. Lai, R. and Zhao, H. (2017) Multiscale Nonrigid Point Cloud Registration Using Rotation-Invariant Sliced-Wasserstein Distance via Laplace—Beltrami Eigenmap. SIAM Journal on Imaging Sciences, 10, 449-483. https://doi.org/10.1137/16M1068827

52. NOTES

*通讯作者。