Parallel Shortest Path Algorithm for Voronoi Diagrams with Generalized Distance Functions

Résumé : Les Diagrammes de Voronoï sont des structures de données fondamentales de la géométrie algorithmique, avec des applications dans différents domaines. Des nouveaux algorithmes de simulation d'objets déformables, en temps réels, nécessitent le calcul des diagrammes de Voronoï sur des images 3D avec des distances non euclidiennes. Dans ce cas, le calcul doit être effectué sur un graphe, où les arêtes codent l'information de distance requise. Cependant, le temps de calcul des diagrammes de Voronoï est trop coûteux et empêche des déformations plus complexes qui nécessitent des modifications topologiques interactives, telles que la coupe ou la couture utilisée dans les simulations de chirurgie virtuelle. Le goulot d'étranglement majeur dans le calcul de Voronoï dans ce cas est un algorithme du plus court chemin qui doit être calculé plusieurs fois au cours de la déformation. Dans cet article, nous nous attaquons à ce problème en proposant un algorithme de GPU pour le probléme du plus court chemin à partir de plusieurs sources utilisant une fonctions de distance généralisées. Notre algorithme a été conçu pour tirer parti de la nature basé sur une grille du graphe sous-jacent utilisé dans la simulation. Les résultats expérimentaux indiquent des accélérations jusqu'à 65x sur une méthode séquentielle de référence.
Type de document :
Communication dans un congrès
XXVII SIBGRAPI, Conference on Graphics Patterns and Images, Aug 2014, Rio de Janerio, Brazil. 2014
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01026159
Contributeur : Julio Toss <>
Soumis le : vendredi 12 septembre 2014 - 20:59:46
Dernière modification le : mercredi 11 avril 2018 - 01:53:53
Document(s) archivé(s) le : samedi 13 décembre 2014 - 10:08:07

Fichier

sibgrapi_2014.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01026159, version 1

Citation

Julio Toss, João Luiz Dihl Comba, Bruno Raffin. Parallel Shortest Path Algorithm for Voronoi Diagrams with Generalized Distance Functions. XXVII SIBGRAPI, Conference on Graphics Patterns and Images, Aug 2014, Rio de Janerio, Brazil. 2014. 〈hal-01026159〉

Partager

Métriques

Consultations de la notice

213

Téléchargements de fichiers

715