Article
Full entry |
PDF
(5.6 MB)
Feedback
PDF
(5.6 MB)
Feedback
Keywords:
Lagrangian evolution; patch layout; non-conforming mesh; mesh partitioning
Lagrangian evolution; patch layout; non-conforming mesh; mesh partitioning
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.
References:
[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. DOI 10.1016/j.jcp.2007.11.023 | MR 2406538 | Zbl 1145.65068
[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. DOI 10.1111/cgf.12014
[3] Bommes, D., Zimmer, H., Kobbelt, L.: Mixed-integer quadrangulation. ACM Trans. Graph. 28 (2009), Article ID 77, 10 pages. DOI 10.1145/1531326.1531383
[4] Campen, M.: Partitioning surfaces into quadrilateral patches: A survey. Comput. Graph. Forum 36 (2017), 567-588. DOI 10.2312/egt.20171033
[5] Cignoni, P., Rocchini, C., Scopigno, R.: Metro: Measuring error on simplified surfaces. Comput. Graph. Forum 17 (1998), 167-174. DOI 10.1111/1467-8659.00236
[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. DOI 10.1007/978-3-319-18461-6_47 | MR 3394961
[7] Dong, S., Bremer, P.-T., Garland, M., Pascucci, V., Hart, J. C.: Spectral surface quadrangulation. ACM Trans. Graph. 25 (2006), 1057-1066. DOI 10.1145/1179352.1141993
[8] Dziuk, G.: Algorithm for evolutionary surfaces. Numer. Math. 58 (1991), 603-611. DOI 10.1007/BF01385643 | MR 1083523 | Zbl 0714.65092
[9] Dziuk, G., Elliott, C. M.: Finite element methods for surface PDEs. Acta Numerica 22 (2013), 289-396. DOI 10.1017/S0962492913000056 | MR 3038698 | Zbl 1296.65156
[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. DOI 10.1093/imanum/drw020 | MR 3649420 | Zbl 1433.65219
[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. DOI 10.1038/ncomms9674
[12] Fecko, M.: Differential Geometry and Lie Groups for Physicists. Cambridge University Press, Cambridge (2006). DOI 10.1017/CBO9780511755590 | MR 2260667 | Zbl 1121.53001
[13] Gray, A.: Modern Differential Geometry of Curves and Surfaces with Mathematica. CRC Press, Boca Raton (1998). DOI 10.1201/9781315276038 | MR 1688379 | Zbl 0942.53001
[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. DOI 10.1006/jcph.1998.5977 | MR 1631208 | Zbl 0917.76063
[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. DOI 10.1006/jcph.1994.1170 | MR 1294935 | Zbl 0810.76095
[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. DOI 10.1145/1409060.1409100
[17] Huska, M., Lazzaro, D., Morigi, S.: Shape partitioning via $L_p$ compressed modes. J. Math. Imaging Vis. 60 (2018), 1111-1131. DOI 10.1007/s10851-018-0799-8 | MR 3832136 | Zbl 1435.65035
[18] Kimura, M.: Numerical analysis for moving boundary problems using the boundary tracking method. Japan J. Ind. Appl. Math. 14 (1997), 373-398. DOI 10.1007/BF03167390 | MR 1475140 | Zbl 0892.76065
[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.
[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. DOI 10.1109/TVCG.2009.59
[21] Lévy, B., Liu, Y.: $L_p$ Centroidal Voronoi Tessellation and its applications. ACM Trans. Graph. 29 (2010), Article ID 119, 11 pages. DOI 10.1145/1833349.1778856
[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. DOI 10.1016/j.camwa.2007.04.047 | MR 2394345 | Zbl 1152.65115
[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.
[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. DOI 10.1007/978-3-662-05105-4_2 | MR 2047000 | Zbl 1069.53004
[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. DOI 10.1137/130927668 | MR 3226752 | Zbl 1328.53086
[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. DOI 10.1137/S0036139999359288 | MR 1824511 | Zbl 0980.35078
[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. DOI 10.1002/mma.514 | MR 2077443 | Zbl 1049.35019
[28] Morigi, S.: Geometric surface evolution with tangential contribution. J. Comput. Appl. Math. 233 (2010), 1277-1287. DOI 10.1016/j.cam.2007.04.052 | MR 2559363 | Zbl 1179.65021
[29] Myles, A., Pietroni, N., Kovacs, D., Zorin, D.: Feature-aligned T-meshes. ACM Trans. Graph. 29 (2010), Article ID 117, 11 pages. DOI 10.1145/1778765.1778854
[30] Neumann, T., Varanasi, K., Theobalt, C., Magnor, M., Wacker, M.: Compressed manifold modes for mesh processing. Comput. Graph. Forum 33 (2014), 35-44. DOI 10.1111/cgf.12429
[31] Osher, S., Fedkiw, R.: Level Set Methods and Dynamic Implicit Surfaces. Applied Mathematical Sciences 153. Springer, Berlin (2003). DOI 10.1007/b98879 | MR 1939127 | Zbl 1026.76001
[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). MR 1700751 | Zbl 0973.76003
[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. DOI 10.1002/mma.2554 | MR 2982466 | Zbl 1255.35148
[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. MR 1234354 | Zbl 0820.65016
[35] Tarini, M., Pietroni, N., Cignoni, P., Panozzo, D., Puppo, E.: Practical quad mesh simplification. Comput. Graph. Forum 29 (2010), 407-418. DOI 10.1111/j.1467-8659.2009.01610.x
[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. DOI 10.2312/SGP/SGP06/201-210
[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. DOI 10.1145/2809785
[38] Wenzel, J., Tarini, M., Panozzo, D., Sorkine-Hornung, O.: Instant field-aligned meshes. ACM Trans. Graph. 34 (2015), Article ID 189, 15 pages. DOI 10.1145/2816795.2818078
[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. DOI 10.1111/j.1467-8659.2009.01521.x
[40] Zhao, H.-K.: A fast sweeping method for Eikonal equations. Math. Comput. 74 (2005), 603-627. DOI 10.1090/S0025-5718-04-01678-3 | MR 2114640 | Zbl 1070.65113
[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. DOI 10.1109/VLSM.2001.938900 | MR 1836523
[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. DOI 10.1006/cviu.2000.0875 | Zbl 1011.68538
Search
Partner of
