Boolean operations on 3D selective Nef complexes: Data structure, algorithms, optimized implementation and experiments
Boolean operations on 3D selective Nef complexes: Data structure, algorithms, optimized implementation and experiments
复制标题
DOI：
10.1016/j.comgeo.2006.11.009
复制
发表时间：
2007-09-01
影响因子：
0.6
通讯作者：
Mehlhorn, Kurt
中科院分区：
文献类型：
--
作者：
Hachenberger, Peter;Kettner, Lutz;Mehlhorn, Kurt
D维空间中的NEF多面体是半空间在布尔集合运算下的闭包。因此，它们可以表示非流形情况、开集和闭集、混合维复形，并且它们在所有布尔和拓扑运算(如补和边界)下都是闭合的。它们是由W.Nef在1978年出版的关于多面体的开创性著作中介绍的。Nef复形的通用性对于某些应用是必不可少的，本文提出了一种新的三维Nef多面体边界表示的数据结构和高效的布尔运算算法。我们使用精确算术来避免浮点算术中众所周知的问题，并处理所有退化。此外，我们还对算法进行了重要的优化，并通过大量的实验对优化后的实现进行了评估。实验补充了理论上的运行时间分析，并说明了我们的优化的有效性。我们将我们的实现与ACIS CAD内核进行了比较。ACIS的速度大多更快，最高可达6倍。有一些ACIS失败的例子。该实现于2004年12月作为开放源码在计算几何算法库(CGAL)3.1版中发布。(C)2007 Elsevier B.V.保留所有权利。
Nef polyhedra in d-dimensional space are the closure of half-spaces under boolean set operations. In consequence, they can represent non-manifold situations, open and closed sets, mixed-dimensional complexes, and they are closed under all boolean and topological operations, such as complement and boundary. They were introduced by W. Nef in his seminal 1978 book on polyhedra. The generality of Nef complexes is essential for some applications.In this paper, we present a new data structure for the boundary representation of three-dimensional Nef polyhedra and efficient algorithms for boolean operations. We use exact arithmetic to avoid well-known problems with floating-point arithmetic and handle all degeneracies. Furthermore, we present important optimizations for the algorithms, and evaluate this optimized implementation with extensive experiments. The experiments supplement the theoretical runtime analysis and illustrate the effectiveness of our optimizations. We compare our implementation with the ACIS CAD kernel. ACIS is mostly faster, by a factor up to six. There are examples on which ACIS fails.The implementation was released as Open Source in the Computational Geometry Algorithm Library (CGAL) release 3.1 in December 2004. (c) 2007 Elsevier B.V. All rights reserved.