A Planar Triangle Mesh Generator Using Quadtrees and Bresenham’S Algorithm
DOI:
https://doi.org/10.70567/mc.v42.ocsid8559Keywords:
Mesh Generation, triangles, quadtrees, Bresenham’s algorithmAbstract
In this work, we present a mesh generator for planar triangles based on quadtrees. Quadtree mesh generators have the advantage of adapting to data density, refining the mesh only where necessary and providing highly efficient meshes. A polygonal boundary is assumed, and only the cells representing the boundary and the interior of the domain are selected. These cells are subdivided along one of their diagonals, producing a mesh of triangles. To select the boundary cells, Bresenham’s algorithm is used. This algorithm, originally developed for computer graphics to rasterize lines, has variants for different types of curves and also for quadtrees. It selects the nodes of the grid that best approximate the boundary.
References
Bergmann M., Fondanèche A., y Iollo A. An Eulerian finite-volume approach of fluid-structure interaction problems on quadtree meshes. Journal of Computational Physics, 471:111647, 2022. http://doi.org/10.1016/j.jcp.2022.111647.
Bern M. y Eppstein D. Mesh generation and optimal triangulation. En Computing in Euclidean Geometry, volumen 4 de Lecture Notes Series on Computing, páginas 47–123. World Scientific, 2 edición, 1995.
Bern M., Eppstein D., y Gilbert J. Provably good mesh generation. Journal of Computer and System Sciences, 48(3):384–409, 1994. http://doi.org/10.1016/S0022-0000(05)80059-5.
Bresenham J.E. Algorithm for computer control of a digital plotter. IBM Systems Journal, 4(1), 1965.
Castellazzi G., D’Altri A.M., Bitelli G., Selvaggi I., y Lambertini A. From Laser Scanning to Finite Element Analysis of Complex Buildings by Using a Semi-Automatic Procedure. Sensors, 15(8):18360–18380, 2015. http://doi.org/10.3390/s150818360.
Dari E. Contribuciones a la Triangulación Automática de Dominios Tridimensionales. Tesis Doctoral, Instituto Balseiro, Universidad de Cuyo, San Carlos de Bariloche, Argentina, 1994.
Frey P. y George P.L. Mesh Generation: Application to Finite Elements. John Wiley & Sons, 2nd ed. edición, 2008.
Gravenkamp H. y Duczek S. Automatic image-based analyses using a coupled quadtree-SBFEM/SCM approach. Computational Mechanics, 60(4), 2017. http://doi.org/10.1007/s00466-017-1424-1.
Hwang J.P. y Cheng K.Y. Bresenham’s Algorithm in Quadcodes. Research Report TR-88-021, Academia Sinica, Taiwan, 1988.
Rivara M.C. e Iribarren G. The 4-Triangles Longest-Side Partition of Triangles and Linear Refinement Algorithms. Mathematics of Computation, 65(216):1485–1502, 1996.
Rivara M.C. Algorithms for refining triangular grids suitable for adaptive and multigrid techniques. International Journal for Numerical Methods in Engineering, 20(4):745–756, 1984. http://doi.org/10.1002/nme.1620200412.
Shephard M.S., Yerry M.A., y Baehmann P.L. Automatic mesh generation allowing for efficient a priori and a posteriori mesh refinement. Computer Methods in Applied Mechanics and Engineering, 55(1):161–180, 1986. http://doi.org/10.1016/0045-7825(86)90090-3.
Yerry M.A. y Shephard M.S. Automatic three-dimensional mesh generation by the modified-octree technique. International Journal for Numerical Methods in Engineering, 20(11):1965–1990, 1984. http://doi.org/10.1002/nme.1620201103.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Argentine Association for Computational Mechanics
This work is licensed under a Creative Commons Attribution 4.0 International License.
This publication is open access diamond, with no cost to authors or readers.
Only those papers that have been accepted for publication and have been presented at the AMCA congress will be published.
