MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Berberich, Eric
Sagraloff, Michael		dblp
dblp
Editor(s):
Haines, Eric
McGuire, Morgan		dblp
dblp
Not MPII Editor(s):
Haines, Eric
McGuire, Morgan
BibTeX cite key*:
bs-agffgtaas-08
Title, Booktitle
Title*:
A Generic and Flexible Framework for the Geometrical and Topological Analysis of (Algebraic) Surfaces
bs-framework-authprep.pdf (221.77 KB)
Booktitle*:
Proceedings of the 2008 ACM Symposium on Solid and Physical Modeling
Event, URLs
Conference URL::
http://www.cs.sunysb.edu/spm08/
Downloading URL:
Event Address*:
Stony Brook, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
2 June 2008
Event End Date:
4 June 2008
Publisher
Name*:
ACM
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
June
Pages:
171-182
Year*:
2008
VG Wort Pages:
12
ISBN/ISSN:
Sequence Number:
DOI:
10.1145/1364901.1364925
Note, Abstract, ©
(LaTeX) Abstract:
We present a generic framework on a set of surfaces $\calS$ in $\R^3$ that
provides their geometric and topological analysis in order to
support various algorithms and applications in computational geometry.
Our implementation follows the generic programming paradigm, i.e.,
to support a certain family of surfaces, we require a small set of types and
some basic operations on them, all collected in a model of the newly presented
{\sc SurfaceTraits\_3} concept.
The framework obtains geometric and topological information on a
non-empty set of surfaces in two steps.
First, important $0$- and $1$-dimensional features are projected onto the
$xy$-plane, obtaining an arrangement $\calA_\calS$ with certain properties.
Second, for each of its components, a sample point is lifted back to $\R^3$
while detecting intersections with the given surfaces.
This idea is similar to Collins' cylindrical algebraic decomposition (cad).
In contrast, we reduce the number of liftings using \cgal's Arrangement\_2
package as a basic tool. Properly instantiated, the framework provides main
functionality required to support the computation of a
Piano Mover's instance. On the other hand, the complexity of the output is
high, and thus, we particularly regard the framework as key ingredient
for querying information on and constructing geometric objects from a small set
of surfaces. Examples are meshing of single surfaces, the computation of
space-curves defined by two surfaces, to compute lower envelopes of surfaces,
or as a basic step to compute an efficient representation of a
three-dimensional arrangement.

We also inspirit the framework in two steps. First, we show that the well-known
family of algebraic surfaces fulfils the framework's requirements.
As robust implementations on these surfaces are lacking these days, we consider
the framework to be an important step to fill this gap.
Second, we instantiate the framework by a fully-fledged model
for special algebraic surfaces, namely quadrics. This instantiation
already supports main tasks demanded from rotational robot motion
planning~\cite{Latom1993}. How to provide a model for algebraic surfaces
of arbitrary degree, is partly discussed in~\cite{bks-exact-08}.
Keywords:
Surface analysis, geometry, topology, framework, generic programming, meshing, space curves, lower envelopes, algebraic surfaces, quadrics
Copyright Message:
Copyright ACM, 2008
This is the authors' version of the work.
It is posted here by permission of ACM for your personal use.
Not for redistribution. The definitive version was published in the
Proceedings of the ACM Solid and Physical Modelling Symposium (SPM 2008), http://doi.acm.org/10.1145/1364901.1364925
Download
Access Level:
Public

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



BibTeX Entry:

@INPROCEEDINGS{bs-agffgtaas-08,
AUTHOR = {Berberich, Eric and Sagraloff, Michael},
 EDITOR = {Haines, Eric and McGuire, Morgan},
 TITLE = {A Generic and Flexible Framework for the Geometrical and Topological Analysis of (Algebraic) Surfaces},
 BOOKTITLE = {Proceedings of the 2008 ACM Symposium on Solid and Physical Modeling},
 PUBLISHER = {ACM},
 YEAR = {2008},
 PAGES = {171--182},
 ADDRESS = {Stony Brook, USA},
 MONTH = {June},
 DOI = {10.1145/1364901.1364925},
}

Entry last modified by Eric Berberich, 03/03/2009
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)
Eric Berberich		Created
06/24/2008 18:35:06
Revisions
3.
2.
1.
0.
Editor(s)
Eric Berberich
Eric Berberich
Eric Berberich
Eric Berberich
Edit Dates
08/29/2008 09:27:52 PM
06/30/2008 11:32:52 AM
06/24/2008 06:36:03 PM
06/24/2008 06:35:06 PM

File Attachment Icon
bs-framework-authprep.pdf