Congratulations Diego García Espinoza! 🎓

Exam Details

• Student: Diego Alejandro García Espinoza
• Thesis Title: Parallelization of a Compact Data Structure on the GPU for the Representation of Geometric Figures
• Degrees obtained: Magíster en Ciencias, Mención Computación + Título de Ingeniero Civil en Computación
• Advisor: Nancy Hitschfeld Kahler
• Co-advisor: Sergio Salinas Fernández
• Committee Members:
  • José Fuentes Sepúlveda
  • Gonzalo Navarro Badino
  • Cristóbal Navarro Guerrero
• Funding: FONDECYT Regular 1241596

Thesis Abstract

Parallelization of a Compact Data Structure on the GPU for the Representation of Geometric Figures

As technology has advanced, the size of files containing geometrical information has grown to the point of causing problems for storage, processing, and execution times. One solution is to use compact data structures, but this further increases execution times.

This work presents a new compact half-edge data structure for storing polygonal meshes designed to work on the GPU, enabling parallel reading and traversal of mesh information. A planar graph compact data structure called PEMB was adapted for use inside the GPU. The proposed structure maintains low memory usage, storing edge connectivity information in less than 2% of the space used by non-compact structures, and achieves a speedup of up to 51× compared to compact sequential structures, and about 1.33× compared to non-compact sequential structures.

To validate the data structure, a new GPU version of the polygonal mesh generator Polylla was built using the proposed structure. The algorithm is divided into four phases:

1. Label phase — identifies the edges to be preserved in the output
2. Tree phase — generates a spanning tree needed to build the new mesh
3. Tour phase — traverses the spanning tree
4. Construction phase — builds the new compact polygonal mesh

The algorithm takes a compact triangular mesh as input and generates a compact polygonal mesh as output. Results show that this new version achieves a 2× speedup over Compact Polylla. Further optimization of the tree and tour phases is identified as the main direction for future work.

Related Publications

• GPU-accelerated processing of polygonal meshes in compact space Proceedings of the 34th International Meshing Roundtable (SIAM IMR 2026)

Congratulations to Diego for this outstanding achievement — we are very proud of your work and wish you all the best in your future career! 🎊

“The question of whether a computer can think is no more interesting than the question of whether a submarine can swim.” — Edsger W. Dijkstra