Campus Event Calendar
Event Entry
What and Who
Nef Polyhedra in 3D Space: Implementation and Optimization
Peter Hachenberger
Ringvorlesung
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 25 November 2004
13:00
-- Not specified --
45
016
Saarbrücken
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.
In the project CGAL we implemented a 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
degeneracies. To this extend we rely on exact
arithmetic to avoid well known problems with floating-point
arithmetic.
In this talk, I present important optimizations for the
algorithms. I describe the chosen implementations for the
point-location and the intersection-finding subroutines, a kd-tree
and a fast box-intersection algorithm, respectively. I evaluate
this optimized implementation with extensive experiments that
supplement our runtime analysis and that
illustrate the effectiveness of our optimizations. Also, I compare our
implementation with the ACIS CAD kernel and demonstrate the power and
cost of the exact arithmetic in near-degenerate situations.
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.
In the project CGAL we implemented a 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
degeneracies. To this extend we rely on exact
arithmetic to avoid well known problems with floating-point
arithmetic.
In this talk, I present important optimizations for the
algorithms. I describe the chosen implementations for the
point-location and the intersection-finding subroutines, a kd-tree
and a fast box-intersection algorithm, respectively. I evaluate
this optimized implementation with extensive experiments that
supplement our runtime analysis and that
illustrate the effectiveness of our optimizations. Also, I compare our
implementation with the ACIS CAD kernel and demonstrate the power and
cost of the exact arithmetic in near-degenerate situations.
Contact
--email hidden
passcode not visible
logged in users only
Bahareh Kadkhodazadeh, 11/22/2004 10:40
Bahareh Kadkhodazadeh, 10/14/2004 12:07 -- Created document.
Bahareh Kadkhodazadeh, 10/14/2004 12:07 -- Created document.