A concise representation for adaptive hexagonal meshes

Luiz Henrique de Figueiredo

doi:10.5753/jbcs.2025.5186

Authors

Luiz Henrique de Figueiredo IMPA https://orcid.org/0000-0001-5683-693X

DOI:

https://doi.org/10.5753/jbcs.2025.5186

Keywords:

Mesh representation, mesh generation, geometric modeling, data structures

Abstract

Adaptive hexagonal meshes yield high-quality planar quadrilateral meshes, which are desirable in applications. We propose a concise exact representation for adaptive hexagonal meshes that is based solely on the faces. We represent each face by its position, type, orientation, and scale. Our representation is simple to use and requires a small fraction of the memory required by topological data structures. Although no other topological elements or relations are explicitly represented, the mesh and all its topological relations can be reconstructed in linear time.

Downloads

Download data is not yet available.

References

Bern, M. and Eppstein, D. (2000). Quadrilateral meshing by circle packing. International Journal of Computational Geometry & Applications, 10(4):347-360. DOI: 10.1142/S0218195900000206.

de Figueiredo, L. H. (2024a). A concise representation for adaptive hexagonal meshes. Available online [link].

de Figueiredo, L. H. (2024b). A vertex-centric representation for adaptive diamond-kite meshes. Computers & Graphics, 119:103910. DOI: 10.1016/j.cag.2024.103910.

De Floriani, L. and Hui, A. (2007). Shape representations based on simplicial and cell complexes. In Eurographics 2007 State of the Art Reports, pages 63-87. Eurographics. DOI: 10.2312/egst.20071055.

Diaz, R., Dreux, M., Lopes, H., and Lewiner, T. (2010). A simple compression of tri-quad meshes with handles. In Full Papers Proceedings of WSCG 2010, pages 205-212. Available online [link].

Dobkin, D. P., Wilks, A. R., Levy, S. V. F., and Thurston, W. P. (1990). Contour tracing by piecewise linear approximations. ACM Transactions on Graphics, 9(4):389-423. DOI: 10.1145/88560.88575.

Eppstein, D. (2014). Diamond-kite adaptive quadrilateral meshing. Engineering with Computers, 30(2):223-235. DOI: 10.1007/s00366-013-0327-9.

Frey, P. J. and George, P. (2008). Mesh Generation: Application to Finite Elements. Wiley. DOI: 10.1002/9780470611166.

King, D., Rossignac, J., and Szymczak, A. (2000). Connectivity compression for irregular quadrilateral meshes. DOI: 10.48550/arXiv.cs/0005005.

Liang, X. and Zhang, Y. (2011). Hexagon-based all-quadrilateral mesh generation with guaranteed angle bounds. Computer Methods in Applied Mechanics and Engineering, 200(23):2005-2020. DOI: j.cma.2011.03.002.

McMains, S., Hellerstein, J. M., and Séquin, C. H. (2001). Out-of-core build of a topological data structure from polygon soup. In Proceedings of the Sixth ACM Symposium on Solid Modeling and Applications, pages 171-182. DOI: 10.1145/376957.376977.

Middleton, L. and Sivaswamy, J. (2005). Hexagonal image processing: a practical approach. Springer. DOI: 10.1007/1-84628-203-9.

Patel, A. (2021). Hexagonal grids.

Sahr, K., White, D., and Kimerling, A. J. (2003). Geodesic discrete global grid systems. Cartography and Geographic Information Science, 30(2):121-134. DOI: 10.1559/152304003100011090.

Soto Sánchez, J. E., Weyrich, T., Medeiros e Sá, A., and de Figueiredo, L. H. (2021). An integer representation for periodic tilings of the plane by regular polygons. Computers & Graphics, 95:69-80. DOI: 10.1016/j.cag.2021.01.007.

Suffern, K. G. (1990). Quadtree algorithms for contouring functions of two variables. The Computer Journal, 33(5):402-407. DOI: 10.1093/comjnl/33.5.402.

Sußner, G., Dachsbacher, C., and Greiner, G. (2005). Hexagonal LOD for interactive terrain rendering. In Vision Modeling and Visualization, pages 437-444. Available online [link].

Sußner, G. and Greiner, G. (2009). Hexagonal Delaunay triangulation. In Proceedings of the 18th International Meshing Roundtable, pages 519-538. Springer. DOI: 10.1007/978-3-642-04319-2_30.

Taubin, G. (1994). Distance approximations for rasterizing implicit curves. ACM Transactions on Graphics, 13(1):3-42. DOI: 10.1145/174462.174531.