Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Boolean Operations on 3D Selective Nef Complexes: Optimized Implementation and Experiments

Hachenberger, P., & Kettner, L. (2005). Boolean Operations on 3D Selective Nef Complexes: Optimized Implementation and Experiments. In ACM Symposium on Solid and Physical Modeling (SPM 2005) (pp. 163-174). New York, USA: ACM.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Hachenberger, Peter1, Autor           
Kettner, Lutz1, Autor           
Kobbelt, Leif, Herausgeber
Shapiro, Vadim, Herausgeber
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2006-01-132005
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: New York, USA : ACM
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 279193
Anderer: Local-ID: C1256428004B93B8-6DBA4898294F9C69C1256FC50081FC75-HachenbergerKettner2005Nef
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Cambridge, MA, USA
Start-/Enddatum: 2005-06-13

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: ACM Symposium on Solid and Physical Modeling (SPM 2005)
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: New York, USA : ACM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 163 - 174 Identifikator: ISBN: 1-59593-015-9