| Title:
|
Lagrangian evolution approach to surface-patch quadrangulation (English) |
| Author:
|
Húska, Martin |
| Author:
|
Medl'a, Matej |
| Author:
|
Mikula, Karol |
| Author:
|
Morigi, Serena |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
66 |
| Issue:
|
4 |
| Year:
|
2021 |
| Pages:
|
509-551 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
We present a method for the generation of a pure quad mesh approximating a discrete manifold of arbitrary topology that preserves the patch layout characterizing the intrinsic object structure. A three-step procedure constitutes the core of our approach which first extracts the patch layout of the object by a topological partitioning of the digital shape, then computes the minimal surface given by the boundaries of the patch layout (basic quad layout) and then evolves it towards the object boundaries. The Lagrangian evolution of the initial surface (basic quad layout) in the direction of the gradient of the signed distance function is smoothed by a mean curvature term. The direct control over the global quality of the generated quad mesh is provided by two types of tangential redistributions: area-based, to equally distribute the size of the quads, and angle-based, to preserve quad corner angles. Experimental results showed that the proposed method generates pure quad meshes of arbitrary topology objects, composed of well-shaped evenly distributed elements with few extraordinary vertices. (English) |
| Keyword:
|
Lagrangian evolution |
| Keyword:
|
patch layout |
| Keyword:
|
non-conforming mesh |
| Keyword:
|
mesh partitioning |
| MSC:
|
35K55 |
| MSC:
|
35K93 |
| MSC:
|
65M08 |
| idZBL:
|
07396166 |
| idMR:
|
MR4283302 |
| DOI:
|
10.21136/AM.2021.0366-19 |
| . |
| Date available:
|
2021-07-09T08:12:21Z |
| Last updated:
|
2023-09-04 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148971 |
| . |
| Reference:
|
[1] Barrett, J. W., Garcke, H., Nürnberg, R.: On the parametric finite element approximation of evolving hypersurfaces in $\mathbb R^3$.J. Comput. Phys. 227 (2008), 4281-4307. Zbl 1145.65068, MR 2406538, 10.1016/j.jcp.2007.11.023 |
| Reference:
|
[2] Bommes, D., Lévy, B., Pietroni, N., Puppo, E., Silva, C., Tarini, M., Zorin, D.: Quad-Mesh generation and processing: A survey.Comput. Graph. Forum 32 (2013), 51-76. 10.1111/cgf.12014 |
| Reference:
|
[3] Bommes, D., Zimmer, H., Kobbelt, L.: Mixed-integer quadrangulation.ACM Trans. Graph. 28 (2009), Article ID 77, 10 pages. 10.1145/1531326.1531383 |
| Reference:
|
[4] Campen, M.: Partitioning surfaces into quadrilateral patches: A survey.Comput. Graph. Forum 36 (2017), 567-588. 10.2312/egt.20171033 |
| Reference:
|
[5] Cignoni, P., Rocchini, C., Scopigno, R.: Metro: Measuring error on simplified surfaces.Comput. Graph. Forum 17 (1998), 167-174. 10.1111/1467-8659.00236 |
| Reference:
|
[6] Daniel, P., Medl'a, M., Mikula, K., Remešíková, M.: Reconstruction of surfaces from point clouds using a Lagrangian surface evolution model.Scale Space and Variational Methods in Computer Vision Lecture Notes in Computer Science 9087. Springer, Cham (2015), 589-600. MR 3394961, 10.1007/978-3-319-18461-6_47 |
| Reference:
|
[7] Dong, S., Bremer, P.-T., Garland, M., Pascucci, V., Hart, J. C.: Spectral surface quadrangulation.ACM Trans. Graph. 25 (2006), 1057-1066. 10.1145/1179352.1141993 |
| Reference:
|
[8] Dziuk, G.: Algorithm for evolutionary surfaces.Numer. Math. 58 (1991), 603-611. Zbl 0714.65092, MR 1083523, 10.1007/BF01385643 |
| Reference:
|
[9] Dziuk, G., Elliott, C. M.: Finite element methods for surface PDEs.Acta Numerica 22 (2013), 289-396. Zbl 1296.65156, MR 3038698, 10.1017/S0962492913000056 |
| Reference:
|
[10] Elliott, C. M., Fritz, H.: On approximations of the curve shortening flow and of the mean curvature flow based on the DeTurck trick.IMA J. Numer. Anal. 37 (2017), 543-603. Zbl 1433.65219, MR 3649420, 10.1093/imanum/drw020 |
| Reference:
|
[11] Faure, E., Savy, T., Rizzi, B., al., et: A workflow to process 3D+time microscopy images of developing organisms and reconstruct their cell lineage.Nature Communications 7 (2016), Article ID 8674, 10 pages. 10.1038/ncomms9674 |
| Reference:
|
[12] Fecko, M.: Differential Geometry and Lie Groups for Physicists.Cambridge University Press, Cambridge (2006). Zbl 1121.53001, MR 2260667, 10.1017/CBO9780511755590 |
| Reference:
|
[13] Gray, A.: Modern Differential Geometry of Curves and Surfaces with Mathematica.CRC Press, Boca Raton (1998). Zbl 0942.53001, MR 1688379, 10.1201/9781315276038 |
| Reference:
|
[14] Hou, T. Y., Klapper, I., Si, H.: Removing the stiffness of curvature in computing 3-D filaments.J. Comput. Phys. 143 (1998), 628-664. Zbl 0917.76063, MR 1631208, 10.1006/jcph.1998.5977 |
| Reference:
|
[15] Hou, T. Y., Lowengrub, J. S., Shelley, M. J.: Removing the stiffness from interfacial flows with surface tension.J. Comput. Phys. 114 (1994), 312-338. Zbl 0810.76095, MR 1294935, 10.1006/jcph.1994.1170 |
| Reference:
|
[16] Huang, J., Zhang, M., Ma, J., Liu, X., Kobbelt, L., Bao, H.: Spectral quadrangulation with orientation and alignment control.ACM Trans. Graph. 27 (2008), Article ID 147, 9 pages. 10.1145/1409060.1409100 |
| Reference:
|
[17] Huska, M., Lazzaro, D., Morigi, S.: Shape partitioning via $L_p$ compressed modes.J. Math. Imaging Vis. 60 (2018), 1111-1131. Zbl 1435.65035, MR 3832136, 10.1007/s10851-018-0799-8 |
| Reference:
|
[18] Kimura, M.: Numerical analysis for moving boundary problems using the boundary tracking method.Japan J. Ind. Appl. Math. 14 (1997), 373-398. Zbl 0892.76065, MR 1475140, 10.1007/BF03167390 |
| Reference:
|
[19] Kósa, B., Haličková-Brehovská, J., Mikula, K.: New efficient numerical method for 3D point cloud surface reconstruction by using level set methods.Proceedings of Equadiff 14 Slovak University of Technology, SPEKTRUM STU Publishing, Bratislava (2017), 387-396. |
| Reference:
|
[20] Lai, Y.-K., Jin, M., Xie, X., He, Y., Palacios, J., Zhang, E., Hu, S.-M., Gu, X.: Metric-driven RoSy field design and remeshing.IEEE Trans. Visualization Comput. Graph. 16 (2010), 95-108. 10.1109/TVCG.2009.59 |
| Reference:
|
[21] Lévy, B., Liu, Y.: $L_p$ Centroidal Voronoi Tessellation and its applications.ACM Trans. Graph. 29 (2010), Article ID 119, 11 pages. 10.1145/1833349.1778856 |
| Reference:
|
[22] Liu, D., Xu, G., Zhang, Q.: A discrete scheme of Laplace-Beltrami operator and its convergence over quadrilateral meshes.Comput. Math. Appl. 55 (2008), 1081-1093. Zbl 1152.65115, MR 2394345, 10.1016/j.camwa.2007.04.047 |
| Reference:
|
[23] Medl'a, M., Mikula, K.: Gaussian curvature based tangential redistribution of points on evolving surfaces.Proceedings of Equadiff 14 Slovak University of Technology, SPEKTRUM STU Publishing, Bratislava (2017), 255-264. |
| Reference:
|
[24] Meyer, M., Desbrun, M., Schröder, P., Barr, A. H.: Discrete differential-geometry operators for triangulated 2-manifolds.Visualization and Mathematics III Springer, Berlin (2003), 35-57. Zbl 1069.53004, MR 2047000, 10.1007/978-3-662-05105-4_2 |
| Reference:
|
[25] Mikula, K., Remešíková, M., Sarkoci, P., Ševčovič, D.: Manifold evolution with tangential redistribution of points.SIAM J. Sci. Comput. 36 (2014), A1384--A1414. Zbl 1328.53086, MR 3226752, 10.1137/130927668 |
| Reference:
|
[26] Mikula, K., Ševčovič, D.: Evolution of plane curves driven by a nonlinear function of curvature and anisotropy.SIAM J. Appl. Math. 61 (2001), 1473-1501. Zbl 0980.35078, MR 1824511, 10.1137/S0036139999359288 |
| Reference:
|
[27] Mikula, K., Ševčovič, D.: A direct method for solving an anisotropic mean curvature flow of plane curves with an external force.Math. Methods Appl. Sci. 27 (2004), 1545-1565. Zbl 1049.35019, MR 2077443, 10.1002/mma.514 |
| Reference:
|
[28] Morigi, S.: Geometric surface evolution with tangential contribution.J. Comput. Appl. Math. 233 (2010), 1277-1287. Zbl 1179.65021, MR 2559363, 10.1016/j.cam.2007.04.052 |
| Reference:
|
[29] Myles, A., Pietroni, N., Kovacs, D., Zorin, D.: Feature-aligned T-meshes.ACM Trans. Graph. 29 (2010), Article ID 117, 11 pages. 10.1145/1778765.1778854 |
| Reference:
|
[30] Neumann, T., Varanasi, K., Theobalt, C., Magnor, M., Wacker, M.: Compressed manifold modes for mesh processing.Comput. Graph. Forum 33 (2014), 35-44. 10.1111/cgf.12429 |
| Reference:
|
[31] Osher, S., Fedkiw, R.: Level Set Methods and Dynamic Implicit Surfaces.Applied Mathematical Sciences 153. Springer, Berlin (2003). Zbl 1026.76001, MR 1939127, 10.1007/b98879 |
| Reference:
|
[32] Sethian, J. A.: Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Material Science.Cambridge Monographs on Applied and Computational Mathematics 3. Cambridge University Press, Cambridge (1999). Zbl 0973.76003, MR 1700751 |
| Reference:
|
[33] Ševčovič, D., Yazaki, S.: Computational and qualitative aspects of motion of plane curves with a curvature adjusted tangential velocity.Math. Methods Appl. Sci. 35 (2012), 1784-1798. Zbl 1255.35148, MR 2982466, 10.1002/mma.2554 |
| Reference:
|
[34] Sleijpen, G. L. G., Fokkema, D. R.: BiCGstab$(l)$ for linear equations involving unsymmetric matrices with complex spectrum.ETNA, Electron. Trans. Numer. Anal. 1 (1993), 11-32. Zbl 0820.65016, MR 1234354 |
| Reference:
|
[35] Tarini, M., Pietroni, N., Cignoni, P., Panozzo, D., Puppo, E.: Practical quad mesh simplification.Comput. Graph. Forum 29 (2010), 407-418. 10.1111/j.1467-8659.2009.01610.x |
| Reference:
|
[36] Tong, Y., Alliez, P., Cohen-Steiner, D., Desbrun, M.: Designing quadrangulations with discrete harmonic forms.Symposium on Geometry Processing, SGP '06 Eurographics Association (2006), 201-210. 10.2312/SGP/SGP06/201-210 |
| Reference:
|
[37] Usai, F., Livesu, M., Puppo, E., Tarini, M., Scateni, R.: Extraction of the quad layout of a triangle mesh guided by its curve skeleton.ACM Trans. Graph. 35 (2015), Article ID 6, 13 pages. 10.1145/2809785 |
| Reference:
|
[38] Wenzel, J., Tarini, M., Panozzo, D., Sorkine-Hornung, O.: Instant field-aligned meshes.ACM Trans. Graph. 34 (2015), Article ID 189, 15 pages. 10.1145/2816795.2818078 |
| Reference:
|
[39] Yan, D.-M., Lévy, B., Liu, Y., Sun, F., Wang, W.: Isotropic remeshing with fast and exact computation of restricted Voronoi diagram.Comput. Graph. Forum 28 (2009), 1445-1454. 10.1111/j.1467-8659.2009.01521.x |
| Reference:
|
[40] Zhao, H.-K.: A fast sweeping method for Eikonal equations.Math. Comput. 74 (2005), 603-627. Zbl 1070.65113, MR 2114640, 10.1090/S0025-5718-04-01678-3 |
| Reference:
|
[41] Zhao, H.-K., Osher, S., Fedkiw, R.: Fast surface reconstruction using the level set method.Proceedings IEEE Workshop on Variational and Level Set Methods in Computer Vision IEEE, Los Alamitos (2001), 194-201. MR 1836523, 10.1109/VLSM.2001.938900 |
| Reference:
|
[42] Zhao, H.-K., Osher, S., Merriman, B., Kang, M.: Implicit and nonparametric shape reconstruction from unorganized data using a variational level set method.Comput. Vis. Image Underst. 80 (2000), 295-314. Zbl 1011.68538, 10.1006/cviu.2000.0875 |
| . |
