Algoritmi per le distanze geodetiche: uno studio comparativo

Abstract

La tesi presenta uno studio comparativo di algoritmi per la risoluzione del problema chiamato “Single Source Geodesic Distances (SSGD)” su superfici discrete, in particolare su mesh triangolari. Questo è un problema cruciale in campi come Computer Graphics e Geometry Processing. Lo studio valuta metodi appartenenti a tre principali categorie: approcci basati su equazioni differenziali alle derivate parziali (PDE), metodi esatti su superfici poliedriche, e metodi basati su grafi. Ogni metodo è analizzato in termini di accuratezza, efficienza computazionale e adattabilità a mesh con geometrie e dimensioni variabili. L'accuratezza di ciascun metodo è valutata rispetto alle distanze di riferimento, ottenute tramite il metodo Vertex-oriented Triangle Propagation (VTP). L'efficienza è determinata analizzando i tempi di preprocessing e di query, mentre l’adattabilità è studiata utilizzando mesh organiche e meccaniche. È stato sviluppato un programma con l’interfaccia grafica (GUI) per facilitare la visualizzazione interattiva, il calcolo e il confronto dei risultati. I risultati ottenuti con metodi basati sulle PDE o con metodi esatti su superfici poliedriche migliorano con il raffinamento della mesh. Al contrario, i metodi basati su grafi forniscono risultati poco accurati su mesh piatte e a bassa curvatura. Questo problema deriva anche dalla tecnica di generazione delle mesh. Le mesh organiche con triangolazione regolare producono errori inferiori per tutti i metodi rispetto alle mesh meccaniche con triangolazione irregolare. Inoltre, i tempi di preprocessing e di query evidenziano un compromesso tra velocità e accuratezza. Questo lavoro, infine, offre spunti utili per la scelta degli algoritmi che calcolano le distanze geodetiche più adatti a requisiti specifici dell’applicazione.

This thesis presents a comparative study of algorithms for solving the Single Source Geodesic Distances (SSGD) problem on discrete surfaces, specifically triangular meshes, which is a crucial problem in fields like computer graphics and geometry processing. The study evaluates methods across three main categories: PDE-based, exact polyhedral, and graph-based approaches. Each method is evaluated in terms of accuracy, computational efficiency, and adaptability to meshes of varying geometries and scales. The accuracy of each method is assessed against ground truth distances obtained through the Vertex-oriented Triangle Propagation (VTP) method, efficiency is determined by analyzing preprocessing and query times, and adaptability is evaluated using both organic and mechanical meshes. A GUI program was developed to facilitate interactive visulization, computation and comparison of results. The findings reveal that while PDE-based and exact polyhedral methods improve with mesh refinement, graph-based methods struggle with accuracy on flat or low-curvature meshes and this is strictly related to the mesh generation technique used. Organic meshes with regular triangulation yield lower errors across methods compared to mechanical meshes with irregular triangulation. Additionally, preprocessing and query times highlight a trade-off between speed and accuracy. Ultimately, this work provides insights into the selection of geodesic algorithms tailored to application-specific requirements.