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):

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

URL of the conference:

http://www.cs.sunysb.edu/spm08/

URL for downloading the paper:


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
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)
Eric Berberich
Created
06/24/2008 06:35:06 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
bs-framework-authprep.pdf