Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Hachenberger, Peter Kettner, Lutz dblp dblp
 Editor(s): Kobbelt, Leif Shapiro, Vadim dblp dblp Not MPII Editor(s): Kobbelt, Leif Shapiro, Vadim
 BibTeX cite key*: HachenbergerKettner2005Nef

 Title, Booktitle
 Title*: Boolean Operations on 3D Selective Nef Complexes: Optimized Implementation and Experiments Booktitle*: ACM Symposium on Solid and Physical Modeling (SPM 2005)

 Event, URLs
 URL of the conference: URL for downloading the paper: Event Address*: Cambridge, MA, USA Language: English Event Date* (no longer used): Organization: Association for Computing Machinery (ACM) Event Start Date: 13 June 2005 Event End Date: 15 June 2005

 Publisher
 Name*: ACM URL: http://www.acm.org/ Address*: New York, USA Type:

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: June Pages: 163-174 Year*: 2005 VG Wort Pages: 55 ISBN/ISSN: 1-59593-015-9 Sequence Number: DOI:

 (LaTeX) Abstract: 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. URL for the Abstract: http://www.mpi-inf.mpg.de/~kettner/pub/nef_3d_experiments_spm_05_a.html HyperLinks / References / URLs: http://www.mpi-inf.mpg.de/~kettner/proj/Nef/ Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: popular Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{HachenbergerKettner2005Nef,
AUTHOR = {Hachenberger, Peter and Kettner, Lutz},
EDITOR = {Kobbelt, Leif and Shapiro, Vadim},
TITLE = {Boolean Operations on 3D Selective {Nef} Complexes: Optimized Implementation and Experiments},
BOOKTITLE = {ACM Symposium on Solid and Physical Modeling (SPM 2005)},
PUBLISHER = {ACM},
YEAR = {2005},
ORGANIZATION = {Association for Computing Machinery (ACM)},
PAGES = {163--174},