Node-Based Data Structure for Balancing Process Optimization of Quadtree Meshes

J. Guadalupe Ramos Díaz, Claudio Lobos, Nancy Hitschfeld Kahler
October 2023
DOI

Abstract

In a quadtree mesh, the refinement level of a quadrant is the number of times it has been recursively split into 4 new quadrants. During the refinement process, it is possible to lose balance, meaning that the difference between refinement levels of two neighbor quadrants is greater than one. The balance is necessary because for those type of meshes, a set of patterns have been designed to manage the transition between fine and coarse regions, producing thus, a congruent mesh. In this work, we propose an improvement of the storage and dynamic update information by designing a new data structure based on nodes rather than edges, which allows reducing the execution time and memory usage.

Type
Conference paper
Publication
2023 42nd International Conference of the Chilean Computer Science Society (SCCC)
Quadtree Meshes Mesh Refinement Data Structures
Claudio Lobos
Claudio Lobos
Director of the Computer Science Department of the Universidad Técnica Federico Santa María

Director of the Computer Science Department of the Universidad Técnica Federico Santa María

Nancy Hitschfeld Kahler
Nancy Hitschfeld Kahler
+Lab founder | Full Professor Universidad de Chile

Full Professor at the Department of Computer Science, University of Chile. Her main research interests include geometric modeling, geometric meshes, and parallel algorithms (GPU computing), focused in computational science, and engineering applications.