Lagrangian evolution approach to surface-patch quadrangulation

Martin Húska; Matej Medl'a; Karol Mikula; Serena Morigi

Applications of Mathematics (2021)

  • Volume: 66, Issue: 4, page 509-551
  • ISSN: 0862-7940

Abstract

top
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.

How to cite

top

Húska, Martin, et al. "Lagrangian evolution approach to surface-patch quadrangulation." Applications of Mathematics 66.4 (2021): 509-551. <http://eudml.org/doc/297993>.

@article{Húska2021,
abstract = {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.},
author = {Húska, Martin, Medl'a, Matej, Mikula, Karol, Morigi, Serena},
journal = {Applications of Mathematics},
keywords = {Lagrangian evolution; patch layout; non-conforming mesh; mesh partitioning},
language = {eng},
number = {4},
pages = {509-551},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Lagrangian evolution approach to surface-patch quadrangulation},
url = {http://eudml.org/doc/297993},
volume = {66},
year = {2021},
}

TY - JOUR
AU - Húska, Martin
AU - Medl'a, Matej
AU - Mikula, Karol
AU - Morigi, Serena
TI - Lagrangian evolution approach to surface-patch quadrangulation
JO - Applications of Mathematics
PY - 2021
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 66
IS - 4
SP - 509
EP - 551
AB - 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.
LA - eng
KW - Lagrangian evolution; patch layout; non-conforming mesh; mesh partitioning
UR - http://eudml.org/doc/297993
ER -

References

top
  1. Barrett, J. W., Garcke, H., Nürnberg, R., 10.1016/j.jcp.2007.11.023, J. Comput. Phys. 227 (2008), 4281-4307. (2008) Zbl1145.65068MR2406538DOI10.1016/j.jcp.2007.11.023
  2. Bommes, D., Lévy, B., Pietroni, N., Puppo, E., Silva, C., Tarini, M., Zorin, D., 10.1111/cgf.12014, Comput. Graph. Forum 32 (2013), 51-76. (2013) DOI10.1111/cgf.12014
  3. Bommes, D., Zimmer, H., Kobbelt, L., 10.1145/1531326.1531383, ACM Trans. Graph. 28 (2009), Article ID 77, 10 pages. (2009) DOI10.1145/1531326.1531383
  4. Campen, M., 10.2312/egt.20171033, Comput. Graph. Forum 36 (2017), 567-588. (2017) DOI10.2312/egt.20171033
  5. Cignoni, P., Rocchini, C., Scopigno, R., 10.1111/1467-8659.00236, Comput. Graph. Forum 17 (1998), 167-174. (1998) DOI10.1111/1467-8659.00236
  6. Daniel, P., Medl'a, M., Mikula, K., Remešíková, M., 10.1007/978-3-319-18461-6_47, Scale Space and Variational Methods in Computer Vision Lecture Notes in Computer Science 9087. Springer, Cham (2015), 589-600. (2015) MR3394961DOI10.1007/978-3-319-18461-6_47
  7. Dong, S., Bremer, P.-T., Garland, M., Pascucci, V., Hart, J. C., 10.1145/1179352.1141993, ACM Trans. Graph. 25 (2006), 1057-1066. (2006) DOI10.1145/1179352.1141993
  8. Dziuk, G., 10.1007/BF01385643, Numer. Math. 58 (1991), 603-611. (1991) Zbl0714.65092MR1083523DOI10.1007/BF01385643
  9. Dziuk, G., Elliott, C. M., 10.1017/S0962492913000056, Acta Numerica 22 (2013), 289-396. (2013) Zbl1296.65156MR3038698DOI10.1017/S0962492913000056
  10. Elliott, C. M., Fritz, H., 10.1093/imanum/drw020, IMA J. Numer. Anal. 37 (2017), 543-603. (2017) Zbl1433.65219MR3649420DOI10.1093/imanum/drw020
  11. Faure, E., Savy, T., Rizzi, B., al., et, 10.1038/ncomms9674, Nature Communications 7 (2016), Article ID 8674, 10 pages. (2016) DOI10.1038/ncomms9674
  12. Fecko, M., 10.1017/CBO9780511755590, Cambridge University Press, Cambridge (2006). (2006) Zbl1121.53001MR2260667DOI10.1017/CBO9780511755590
  13. Gray, A., 10.1201/9781315276038, CRC Press, Boca Raton (1998). (1998) Zbl0942.53001MR1688379DOI10.1201/9781315276038
  14. Hou, T. Y., Klapper, I., Si, H., 10.1006/jcph.1998.5977, J. Comput. Phys. 143 (1998), 628-664. (1998) Zbl0917.76063MR1631208DOI10.1006/jcph.1998.5977
  15. Hou, T. Y., Lowengrub, J. S., Shelley, M. J., 10.1006/jcph.1994.1170, J. Comput. Phys. 114 (1994), 312-338. (1994) Zbl0810.76095MR1294935DOI10.1006/jcph.1994.1170
  16. Huang, J., Zhang, M., Ma, J., Liu, X., Kobbelt, L., Bao, H., 10.1145/1409060.1409100, ACM Trans. Graph. 27 (2008), Article ID 147, 9 pages. (2008) DOI10.1145/1409060.1409100
  17. Huska, M., Lazzaro, D., Morigi, S., 10.1007/s10851-018-0799-8, J. Math. Imaging Vis. 60 (2018), 1111-1131. (2018) Zbl1435.65035MR3832136DOI10.1007/s10851-018-0799-8
  18. Kimura, M., 10.1007/BF03167390, Japan J. Ind. Appl. Math. 14 (1997), 373-398. (1997) Zbl0892.76065MR1475140DOI10.1007/BF03167390
  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. (2017) 
  20. Lai, Y.-K., Jin, M., Xie, X., He, Y., Palacios, J., Zhang, E., Hu, S.-M., Gu, X., 10.1109/TVCG.2009.59, IEEE Trans. Visualization Comput. Graph. 16 (2010), 95-108. (2010) DOI10.1109/TVCG.2009.59
  21. Lévy, B., Liu, Y., 10.1145/1833349.1778856, ACM Trans. Graph. 29 (2010), Article ID 119, 11 pages. (2010) DOI10.1145/1833349.1778856
  22. Liu, D., Xu, G., Zhang, Q., 10.1016/j.camwa.2007.04.047, Comput. Math. Appl. 55 (2008), 1081-1093. (2008) Zbl1152.65115MR2394345DOI10.1016/j.camwa.2007.04.047
  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. (2017) 
  24. Meyer, M., Desbrun, M., Schröder, P., Barr, A. H., 10.1007/978-3-662-05105-4_2, Visualization and Mathematics III Springer, Berlin (2003), 35-57. (2003) Zbl1069.53004MR2047000DOI10.1007/978-3-662-05105-4_2
  25. Mikula, K., Remešíková, M., Sarkoci, P., Ševčovič, D., 10.1137/130927668, SIAM J. Sci. Comput. 36 (2014), A1384--A1414. (2014) Zbl1328.53086MR3226752DOI10.1137/130927668
  26. Mikula, K., Ševčovič, D., 10.1137/S0036139999359288, SIAM J. Appl. Math. 61 (2001), 1473-1501. (2001) Zbl0980.35078MR1824511DOI10.1137/S0036139999359288
  27. Mikula, K., Ševčovič, D., 10.1002/mma.514, Math. Methods Appl. Sci. 27 (2004), 1545-1565. (2004) Zbl1049.35019MR2077443DOI10.1002/mma.514
  28. Morigi, S., 10.1016/j.cam.2007.04.052, J. Comput. Appl. Math. 233 (2010), 1277-1287. (2010) Zbl1179.65021MR2559363DOI10.1016/j.cam.2007.04.052
  29. Myles, A., Pietroni, N., Kovacs, D., Zorin, D., 10.1145/1778765.1778854, ACM Trans. Graph. 29 (2010), Article ID 117, 11 pages. (2010) DOI10.1145/1778765.1778854
  30. Neumann, T., Varanasi, K., Theobalt, C., Magnor, M., Wacker, M., 10.1111/cgf.12429, Comput. Graph. Forum 33 (2014), 35-44. (2014) DOI10.1111/cgf.12429
  31. Osher, S., Fedkiw, R., 10.1007/b98879, Applied Mathematical Sciences 153. Springer, Berlin (2003). (2003) Zbl1026.76001MR1939127DOI10.1007/b98879
  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). (1999) Zbl0973.76003MR1700751
  33. Ševčovič, D., Yazaki, S., 10.1002/mma.2554, Math. Methods Appl. Sci. 35 (2012), 1784-1798. (2012) Zbl1255.35148MR2982466DOI10.1002/mma.2554
  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. (1993) Zbl0820.65016MR1234354
  35. Tarini, M., Pietroni, N., Cignoni, P., Panozzo, D., Puppo, E., 10.1111/j.1467-8659.2009.01610.x, Comput. Graph. Forum 29 (2010), 407-418. (2010) DOI10.1111/j.1467-8659.2009.01610.x
  36. Tong, Y., Alliez, P., Cohen-Steiner, D., Desbrun, M., 10.2312/SGP/SGP06/201-210, Symposium on Geometry Processing, SGP '06 Eurographics Association (2006), 201-210. (2006) DOI10.2312/SGP/SGP06/201-210
  37. Usai, F., Livesu, M., Puppo, E., Tarini, M., Scateni, R., 10.1145/2809785, ACM Trans. Graph. 35 (2015), Article ID 6, 13 pages. (2015) DOI10.1145/2809785
  38. Wenzel, J., Tarini, M., Panozzo, D., Sorkine-Hornung, O., 10.1145/2816795.2818078, ACM Trans. Graph. 34 (2015), Article ID 189, 15 pages. (2015) DOI10.1145/2816795.2818078
  39. Yan, D.-M., Lévy, B., Liu, Y., Sun, F., Wang, W., 10.1111/j.1467-8659.2009.01521.x, Comput. Graph. Forum 28 (2009), 1445-1454. (2009) DOI10.1111/j.1467-8659.2009.01521.x
  40. Zhao, H.-K., 10.1090/S0025-5718-04-01678-3, Math. Comput. 74 (2005), 603-627. (2005) Zbl1070.65113MR2114640DOI10.1090/S0025-5718-04-01678-3
  41. Zhao, H.-K., Osher, S., Fedkiw, R., 10.1109/VLSM.2001.938900, Proceedings IEEE Workshop on Variational and Level Set Methods in Computer Vision IEEE, Los Alamitos (2001), 194-201. (2001) MR1836523DOI10.1109/VLSM.2001.938900
  42. Zhao, H.-K., Osher, S., Merriman, B., Kang, M., 10.1006/cviu.2000.0875, Comput. Vis. Image Underst. 80 (2000), 295-314. (2000) Zbl1011.68538DOI10.1006/cviu.2000.0875

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.