Computing the Volume of a Union of Balls: A Certified Algorithm
Computing the Volume of a Union of Balls: A Certified Algorithm
复制标题
DOI：
10.1145/2049662.2049665
复制
发表时间：
2011-11-01
影响因子：
2.7
通讯作者：
Loriot, Sebastien
中科院分区：
文献类型：
--
作者：
Cazals, Frederic;Kanhere, Harshad;Loriot, Sebastien
球和球体是最简单的 3D 建模基元之一，计算球体联合的体积是一个基本问题。尽管几个社区已经研究了许多解决这个问题的策略，但我们不知道有任何鲁棒的算法，因此提出了第一个这样的算法。我们的计算依赖于将并集的体积分解为凸区域，即功率图中球对其区域的限制。理论上，我们根据高斯散度定理建立了限制体积的公式。证明是有建设性的，我们开发了相关的算法。在实现方面，我们仔细分析了体积计算中涉及的谓词和结构，并提出了基于区间算术的经过认证的实现。结果在精确体积属于计算区间的意义上得到了验证。实验结果显示在手工制作的模型上，说明了各种困难，以及在 2009 年 7 月 10 日发布的蛋白质数据库中发现的 58,898 个模型。
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.Experimental results are presented on hand-crafted models illustrating various difficulties, as well as on the 58,898 models found in the tenth of July 2009 release of the Protein Data Bank.