Computing the Volume of a Union of Balls: a Certified Algorithm

Abstract : Balls and spheres are amongst the simplest 3D modeling primitives, and computing the volume of a union of balls is an elementary problem. Although a number of strategies addressing this problem have been investigated in several communities, we are not aware of any robust algorithm, and present the first such algorithm. Our calculation relies on the decomposition of the volume of the union into convex regions, namely the restrictions of the balls to their regions in the power diagram. Theoretically, we establish a formula for the volume of a restriction, based on Gauss' divergence theorem. The proof being constructive, we develop the associated algorithm. On the implementation side, we carefully analyse the predicates and constructions involved in the volume calculation, and present a certified implementation relying on interval arithmetic. The result is certified in the sense that the exact volume belongs to the interval computed using the interval arithmetic. Experimental results are presented on hand-crafted models presenting various difficulties, as well as on the 58,898 models found in the 2009-07-10 release of the Protein Data Bank.
Type de document :
Rapport
[Research Report] RR-7013, INRIA. 2009, pp.25
Liste complète des métadonnées

https://hal.inria.fr/inria-00409374
Contributeur : Frederic Cazals <>
Soumis le : jeudi 3 septembre 2009 - 11:04:17
Dernière modification le : samedi 21 juillet 2018 - 14:12:01
Document(s) archivé(s) le : lundi 15 octobre 2012 - 16:05:43

Fichier

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

Identifiants

  • HAL Id : inria-00409374, version 1

Collections

Citation

Frédéric Cazals, Kanhere Harshad, Sebastien Loriot. Computing the Volume of a Union of Balls: a Certified Algorithm. [Research Report] RR-7013, INRIA. 2009, pp.25. 〈inria-00409374〉

Partager

Métriques

Consultations de la notice

683

Téléchargements de fichiers

694