Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



ID: 279193.0, MPI für Informatik / Algorithms and Complexity Group
Boolean Operations on 3D Selective Nef Complexes: Optimized Implementation and Experiments
Authors:Hachenberger, Peter; Kettner, Lutz
Editors:Kobbelt, Leif; Shapiro, Vadim
Language:English
Publisher:ACM
Place of Publication:New York, USA
Date of Publication (YYYY-MM-DD):2005
Title of Proceedings:ACM Symposium on Solid and Physical Modeling (SPM 2005)
Start Page:163
End Page:174
Place of Conference/Meeting:Cambridge, MA, USA
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2005-06-13
Audience:Experts Only
Intended Educational Use:No
Abstract / Description:Nef polyhedra in $d$-dimensional space are the closure of
half-spaces under boolean set operation. 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.

We presented in previous work a new data structure for the boundary
representation of three-dimensional Nef polyhedra with
efficient algorithms for boolean operations. These algorithms were
designed for correctness and can handle all cases, in particular all
\emph{degeneracies}. To this extent we rely on exact
arithmetic to avoid well known problems with floating-point
arithmetic.

In this paper, we present important optimizations for the
algorithms. We describe the chosen implementations for the
point-location and the intersection-finding subroutines, a kd-tree
and a fast box-intersection algorithm, respectively. We evaluate
this optimized implementation with extensive experiments that
supplement the runtime analysis from our previous paper and that
illustrate the effectiveness of our optimizations. We compare our
implementation with the \textsc{Acis} CAD kernel and demonstrate the power and
cost of the exact arithmetic in near-degenerate situations.

The implementation was released as Open Source in the
\textsc{Cgal} release 3.1 in December 2004.
Last Change of the Resource (YYYY-MM-DD):2006-01-13
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-6DBA4898294F9C69C1256FC50081FC75-...
ISBN:1-59593-015-9
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.