Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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:




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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 12:39:47 AM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section