Analisi e valutazione di strutture dati per la gestione di mesh triangolari in CinoLib

Abstract

Questa tesi analizza l’impatto delle strutture dati e dell’organizzazione topologica sul costo computazionale del calcolo di geodetiche su mesh triangolari.

Il lavoro si concentra sul confronto tra tre varianti di uno stesso algoritmo di shortest path implementato in C++ mediante la libreria Cinolib: una versione Baseline basata su DrawableTrimesh, una variante Hybrid con riordinamento consistente delle adiacenze face-to-face e una versione Fast basata su una struttura dati leggera di tipo triangle-to-triangle (T2T).

L’obiettivo non è introdurre nuove strategie algoritmiche, ma isolare sperimentalmente il contributo del layout topologico e dell’overhead strutturale sul tempo di esecuzione. L’analisi evidenzia come una parte significativa del costo nella versione Baseline sia dovuta all’overhead delle strutture dati general-purpose, mentre l’adozione di layout topologici coerenti o strutture leggere consente di avvicinare il tempo misurato al reale costo computazionale dell’algoritmo geodetico.

Il lavoro dimostra che interventi mirati sull’organizzazione delle adiacenze possono produrre benefici significativi anche senza modificare l’algoritmo geometrico sottostante.

This thesis analyzes the impact of data structures and topological organization on the computational cost of geodesic computation on triangular meshes.

The work focuses on the comparison of three variants of the same shortest path algorithm implemented in C++ using the CinoLib library: a Baseline version based on DrawableTrimesh, a Hybrid variant with consistent reordering of face-to-face adjacencies, and a Fast version based on a lightweight triangle-to-triangle (T2T) data structure.

The goal is not to introduce new algorithmic strategies, but to experimentally isolate the contribution of topological layout and structural overhead to execution time.

The analysis shows that a significant portion of the cost in the Baseline version is due to the overhead of general-purpose data structures, whereas the adoption of coherent topological layouts or lightweight structures makes it possible to bring the measured execution time closer to the actual computational cost of the geodesic algorithm.

This work demonstrates that targeted interventions on adjacency organization can produce significant benefits even without modifying the underlying geometric algorithm.