Un Generador de Mallas Planas de Triángulos Usando Quadtrees y el Algoritmo de Bresenham
DOI:
https://doi.org/10.70567/mc.v42.ocsid8559Palabras clave:
Generación de mallas, triángulos, árboles cuaternarios, algoritmo de BresenhamResumen
En este trabajo se presenta un generador de mallas planas de triángulos basado en árboles cuaternarios (quadtrees). Los generadores de malla quadtree tienen la ventaja de adaptarse a la densidad de los datos, refinando la malla sólo donde es necesario conduciendo a mallas muy eficientes. Se asume un contorno poligonal y se seleccionan aquellas celdas cuadradas de la grilla que representan al contorno y al interior del dominio. Luego se subdividen estas celdas por alguna de sus diagonales y queda conformada una malla de triángulos. Para seleccionar las celdas del contorno se utiliza el algoritmo de Bresenham. Este algoritmo se utiliza en computación gráfica para rasterizar líneas y existen variantes para diferentes tipos de curvas y también para quadtrees. Este algoritmo también permite seleccionar los nodos de la grilla que mejor aproximan cada recta de contorno.
Citas
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.
Descargas
Publicado
Número
Sección
Licencia
Derechos de autor 2025 Asociación Argentina de Mecánica Computacional
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
Esta publicación es de acceso abierto diamante, sin ningún tipo de costo para los autores ni los lectores.
Solo se publicarán aquellos trabajos que han sido aceptados para su publicación y han sido presentados en el congreso de AMCA.
