QuickCSG: Arbitrary and Faster Boolean Combinations of N Solids

Matthijs Douze 1, 2 Jean-Sébastien Franco 2 Bruno Raffin 3
2 MORPHEO - Capture and Analysis of Shapes in Motion
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
3 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Résumé : Quoique étudié depuis des décennies, le calcul d'opérations booléennes sur des polyèdres est quasiment toujours fait sur deux opérandes. Pour un plus grand nombre de polyèdres et une opération booléenne arbitraire à effectuer, l'opération est décomposée sur un arbre binaire CSG (géométrie constructive), dans lequel chaque nœud est traité séparément en temps quasi-linéaire. Pour de grands arbres, ceci est à la fois source d'erreurs, à cause des calculs géométriques intermédiaires, et inefficace à cause des traitements superflus au niveau des nœuds. Nous introduisons une approche fondamentalement nouvelle qui traite le cas général de N polyèdres. Nous proposons une vue du problème centrée sur les sommets, ce qui simplifie l'algorithme et facilite sa décomposition spatiale. Nous traitons le problème dans un seul KD-tree, qui est dirigé vers le résultat final, en élaguant les régions de l'espace qui ne contribuent pas à la surface finale. Non seulement ceci améliore la robustesse de l'approche mais ça lui donne un avantage en vitesse, car la complexité dépend plus de la taille de la sortie que celle d'entrée. En la combinant avec une parallélisation basée sur du vol de tâche, l'algorithme a des performances inouïes, d'un ou deux ordres de grandeur plus rapide que les algorithmes de l'état de l'art sur CPU et GPU. De plus il produit un résultat exact, sans aucune primitive géométrique superflue.
Liste complète des métadonnées



https://hal.inria.fr/hal-01121419
Contributeur : Douze Matthijs <>
Soumis le : mercredi 27 juillet 2016 - 15:21:27
Dernière modification le : mardi 20 décembre 2016 - 11:59:53

Fichiers

RR-8687.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Pas de modification 4.0 International License

Identifiants

  • HAL Id : hal-01121419, version 1

Citation

Matthijs Douze, Jean-Sébastien Franco, Bruno Raffin. QuickCSG: Arbitrary and Faster Boolean Combinations of N Solids. [Research Report] RR-8687, Inria - Research Centre Grenoble – Rhône-Alpes; INRIA. 2015, pp.36. <hal-01121419>

Partager

Métriques

Consultations de
la notice

1140

Téléchargements du document

1181