MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
Downloading URL:
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:
Note, Abstract, ©
(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},
 ADDRESS = {Cambridge, MA, USA},
 MONTH = {June},
 ISBN = {1-59593-015-9},
}

Entry last modified by Lutz Kettner, 01/13/2006
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Lutz Kettner		Created
03/16/2005 00:39:47
Revisions
5.
4.
3.
2.
1.		Editor(s)
Lutz Kettner
Lutz Kettner
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
01/13/2006 10:35:48 AM
01/12/2006 09:21:21 PM
16.11.2005 15:28:25
31.10.2005 15:06:54
04/06/2005 06:30:48 PM