User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Lloyd's energy minimization in the L p norm for quadrilateral surface mesh generation

Primary tabs

Carrier-Baudouin, Tristan [UCL] Remacle, Jean-François [UCL] Marchandise, Emilie [UCL] Lambrechts, Jonathan [UCL] Henrotte, François [UCL]

Indirect methods recombine the elements of triangular meshes to produce quadrilaterals. The resulting quadrilaterals are usually randomly oriented, which is not desirable. However, by aligning the vertices of the initial triangular mesh, precisely oriented quads can be produced. Levy's algorithm is a non-linear optimization procedure that can align points according to a locally defined orientation matrix. It minimizes an energy functional based on the L p distance. The triangulation of a set of vertices smoothed with Levy's algorithm is mainly composed of right-angled triangles, which is ideal for quad recombination. An implementation of Levy's algorithm based on numerical integration is presented. The implementation has the advantage of not modifying the edge meshes. It also features automatic calculation of the orientation angle. When used in combination with an indirect recombination algorithm, it can create quads of varying size and orientation. It has been tested on two-dimensional surfaces as well as globally parametrized three-dimensional surfaces. The results demonstrate an increase in the number of nodes having four neighbors and an improvement of the quads quality. The development took place in the framework of the Gmsh free software. © 2012 Springer-Verlag London.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès interdit
Publication date 2012
Language Anglais
Journal information "Engineering with Computers" - Vol. 30, no.1, p. 97-110 (2012)
Peer reviewed yes
issn 0177-0667
Publication status Publié
Affiliation UCL - SST/IMMC/MEMA - Applied mechanics and mathematics
Keywords Centroidal Voronoi tessellations ; Clipped Voronoi diagrams ; Non-linear optimization ; Quad mesh generation
Links
  1. Blundell Barry G., An Introduction to Computer Graphics and Creative 3-D Environments, ISBN:9781848000414, 10.1007/978-1-84800-042-1
  2. Bochkanov S, Bystritsky V (1999–2011) Alglib. http://www.alglib.net
  3. Du Qiang, Wang Desheng, Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations, 10.1002/nme.616
  4. Du Qiang, Faber Vance, Gunzburger Max, Centroidal Voronoi Tessellations: Applications and Algorithms, 10.1137/s0036144599352836
  5. Ferziger Joel H., Perić Milovan, Computational Methods for Fluid Dynamics, ISBN:9783540780915, 10.1007/978-3-642-98037-4
  6. Hausner Alejo, Simulating decorative mosaics, 10.1145/383259.383327
  7. Hughes T (2000) The finite element method: linear static and dynamic finite element analysis. Dover Publications, New York
  8. Lai Yu-Kun, Hu Shi-Min, Martin Ralph R., Surface mosaics, 10.1007/s00371-006-0047-x
  9. Lai Yu-Kun, Kobbelt Leif, Hu Shi-Min, Feature aligned quad dominant remeshing using iterative local updates, 10.1016/j.cad.2009.02.017
  10. Levy B, Liu Y (2010) l p centroidal voronoi tessellation and its applications. In: Hoppe H (ed) ACM Transactions on Graphics, University of California, Los Angeles
  11. Liu Yang, Wang Wenping, Lévy Bruno, Sun Feng, Yan Dong-Ming, Lu Lin, Yang Chenglei, On centroidal voronoi tessellation—energy smoothness and fast computation, 10.1145/1559755.1559758
  12. Liu Yang, Xu Weiwei, Wang Jun, Zhu Lifeng, Guo Baining, Chen Falai, Wang Guoping, General planar quadrilateral mesh design using conjugate direction field, 10.1145/2024156.2024174
  13. Liziér Mario A. S., Siqueira Marcelo F., Daniels Joel, Silva Claudio T., Nonato L. Gustavo, Template-based quadrilateral mesh generation from imaging data, 10.1007/s00371-011-0603-x
  14. Marchandise E., de Wiart C. Carton, Vos W. G., Geuzaine C., Remacle J.-F., High-quality surface remeshing using harmonic maps-Part II: Surfaces with high genus and of large aspect ratio, 10.1002/nme.3099
  15. Prakash Sujata, Ethier C. Ross, Requirements for Mesh Resolution in 3D Computational Hemodynamics, 10.1115/1.1351807
  16. Remacle J. -F., Henrotte F., Baudouin T. Carrier, Geuzaine C., Béchet E., Mouton Thibaud, Marchandise E., A Frontal Delaunay Quad Mesh Generator Using the L  ∞  Norm, Proceedings of the 20th International Meshing Roundtable (2011) ISBN:9783642247330 p.455-472, 10.1007/978-3-642-24734-7_25
  17. Remacle J.-F., Lambrechts J., Seny B., Marchandise E., Johnen A.,  Geuzainet C., Blossom-Quad: A non-uniform quadrilateral mesh generator using a minimum-cost perfect-matching algorithm : QUADRILATERAL MESH GENERATOR USING PERFECT MATCHING, 10.1002/nme.3279
  18. Roache P (1992) Computational fluid dynamics. Hermosa, Albuquerque
  19. Sherwin S. J., Peiró J., Mesh generation in curvilinear domains using high-order elements : MESH GENERATION IN CURVILINEAR DOMAINS, 10.1002/nme.397
  20. Shimada K, Liao JH, Itoh T (1998) Quadrilateral meshing with directionality control through the packing of square cells. In: Proceedings of the 7th International Meshing Roundtable, Dearborn
  21. Tarini Marco, Puppo Enrico, Panozzo Daniele, Pietroni Nico, Cignoni Paolo, Simple quad domains for field aligned mesh parametrization, 10.1145/2024156.2024176
  22. Tchon Ko-Foa, Camarero Ricardo, Quad-Dominant Mesh Adaptation Using Specialized Simplicial Optimization, Proceedings of the 15th International Meshing Roundtable ISBN:9783540349570 p.21-38, 10.1007/978-3-540-34958-7_2
  23. Longest P. Worth, Vinchurkar Samir, Effects of mesh style and grid convergence on particle deposition in bifurcating airway models with comparisons to experimental data, 10.1016/j.medengphy.2006.05.012
  24. Vinchurkar Samir, Longest P. Worth, Evaluation of hexahedral, prismatic and hybrid mesh styles for simulating respiratory aerosol dynamics, 10.1016/j.compfluid.2007.05.001
  25. Yamakawa Soji, Shimada Kenji, Fully-automated hex-dominant mesh generation with directionality control via packing rectangular solid cells, 10.1002/nme.754
  26. Yan DM, Wang W, Levy B, Liu Y (2010) Efficient computation of 3d clipped voronoi diagram. In: Mourrain B, Schaefer S, Xu G (eds) GMP 2010 Conference Proceedings, Castro Urdiales
  27. Zienkiewicz OC, Taylor RL (2000) The finite element method: the basis, vol 1. Butterworth-Heinemann, Oxford
  28. Zienkiewicz O. C., Rojek J., Taylor R. L., Pastor M., Triangles and tetrahedra in explicit dynamic codes for solids, 10.1002/(sici)1097-0207(19981015)43:3<565::aid-nme454>3.0.co;2-9
Bibliographic reference Carrier-Baudouin, Tristan ; Remacle, Jean-François ; Marchandise, Emilie ; Lambrechts, Jonathan ; Henrotte, François. Lloyd's energy minimization in the L p norm for quadrilateral surface mesh generation. In: Engineering with Computers, Vol. 30, no.1, p. 97-110 (2012)
Permanent URL http://hdl.handle.net/2078.1/136845