Personal tools
You are here: Home Projects Internal Projects Arrangements on Surfaces
« April 2017 »
April
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
30
Log in


Forgot your password?
 

A general framework for processing a set of curves defined on a continuous two-dimensional parametric surface

Arrangement on Surfaces picture
An arrangement induced by 23 ellipsoids in
degenerate position on a base ellipsoid.

Abstract

We introduce a general framework for processing a set of curves defined on a continuous two-dimensional parametric surface, while sweeping the parameter space. We can handle planes, cylinders, spheres, tori, and surfaces homeomorphic to them. A major goal of our work is to maximize code reuse by generalizing the prevalent sweep-line paradigm and its implementation so that it can be employed on a large class of surfaces and curves embedded on them. We have realized our approach as a prototypical CGAL package. We present experimental results for two concrete adaptations of the framework for: (i) arrangements of arcs of great circles embedded on a sphere, and (ii) arrangements of intersection curves between quadric surfaces embedded on a quadric.

The Topology-Traits Concept

In previous CGAL versions, planar arrangements used to be represented by the Arrangement_2 class template. This template has two parameters: the first is a geometry-traits class, which must be a model of the geometry-traits model, and the other is a class that represents a DCEL structure.

We now introduce a class template named Arrangement_on_surface_2, which represents an arrangement on an arbitrary surface. For backward compatibility, the geometry-traits class maintains the same interface. However, its predicates related to x and y should interpreted in the two-dimensional parameter space that defines the surface. The second template parameter is a topology-traits class, which defines the specific manner the arrangement is represented as a DCEL structure. We next give a more detailed description on the requirements from the topology-traits class.

First, the topology-traits class must define a nested Dcel type, which corresponds to the DCEL class used to represent the arrangement. In addition it must define visitors that perform certain tasks. The most important visitors are:

Construction sweep-line visitor
A sweep-line visitor class that can construct the arrangement of a set of curves from scratch.
Insertion sweep-line visitor
A sweep-line visitor class that can insert a set of curves into a non-empty arrangement.
Overlay sweep-line visitor
A sweep-line visitor class that constructs a new arrangement corresponding to the overlay of two input arrangements.
Insertion zone visitor
Used to insert a single curve into an existing arrangement by computing its zone. Like the sweep-line algorithm, the zone-computation algorithm is also implemented in a generic fashion and its output is determined by a visitor class.
The fact that the visitor classes are defined by the topology-traits classes makes it possible to support generic functions that operate on the Arrangement_on_surface_2 class. For example, the function insert_curves(arr, begin, end) accepts an arrangement instance arr and a range of curves defined by [begin, end). If the arrangement is empty, it uses the construction sweep-line visitor to sweep over the input curves and construct their arrangement. Otherwise, it uses the insertion sweep-line visitor to insert them into the existing arrangement.

There are usually several alternatives for the actual DCEL representation of an arrangement on a specific surface.

Unbounded Topology
Different DCEL representations for the same arrangement

 

The topology-traits class encapsulates the actual DCEL representation of the arrangement. It provides access to the DCEL class, such that the Arrangement_on_surface_2 class can directly update DCEL records with no boundary conditions (i.e., all vertices and edges related to points and curves in the augmented parameter space). The topology-traits class is however responsible for handling the DCEL records that represents the surface boundaries: infinity, curves of discontinuity (identification), and singularity (contraction) points. To do so, it provides the following functionality:

Initialize
Construct a DCEL structure that represents an empty arrangement.
Place boundary vertex
Locate the DCEL vertex to which a given curve object with a boundary condition will be assigned, if existing. Otherwise it returns NULL.
Notify on boundary vertex creation
This function is used to notify the topological traits that a new DCEL vertex has been created which carries a boundary condition. This way it is possible to keep the internal objects of the topological traits up-to-date.
Locate around boundary vertex
For a given DCEL vertex, this functions returns the predecessor half-edge which identifies where to insert a given curve with a boundary condition. If may return NULL, if there is no such.
Is redundant
Determine whether a given vertex with a boundary condition becomes redundant. For example, a vertex that lie on a fictitious halfedge becomes redundant after one of its non-fictitious incident halfedges is deleted (typically it is only incident to two fictitious halfedges), or consider the case where a vertex representing a contraction point becomes isolated.
Remove redundant vertex
Remove a redundant vertex from the DCEL structure.
Is perimetric path
Determine whether a sequence of halfedges (given by first and last halfedge) forms a perimetric path, i.e., crosses an existing curve of identification an odd number of times.
Boundaries of same face
Check whether two given perimetric loops (each indicated by an halfedge) form outer boundaries of the same incident face.

Example:

Given a collection C of curves on a surface, the arrangement A(C) is the partition of the surface into vertices, edges and faces  induced by the curves of C.

 
arrangement of circles arrangement of lines
arrangement of arcs on the sphere
This is an Arrangement of Circles
in the plane.
This is an Arrangement of Lines
 in the plane.
This is an Arrangement  of great-circle arcs
 on a sphere

Further Example: Arrangements on ring Dupin Cylides

We provide a geometric and topologic traits class to compute arrangement on (parameterized) ring Dupin Cyclides induced by intersection of the cyclide with algebraic surfaces of any degree D. The family of Dupin cyclides contains as a special case the torus: Such an intersection is represented as real algebraic (plane) curve of bi-degree (2D,2D). CGAL's experimental bivariate algebraic kernel provides the analysis of such curves. We use and extend it by asymptotic information about curves approaching infinity to define a proper geometric traits that reflects specialities when interpreting them with respect to the cylide's parameter space. Our new topological traits provides the demanded opertations to model the particularities of the genus-one reference surface. The implementation does not assume generic position. Our experiments show that the combinatorial overhead of the framework (choice of topology traits: planar versus cyclidean) does not harm the efficiency of the method and that the overall performance is strongly coupled to the efficiency of the implementation for arrangements of algebraic plane curves. Arrangements on tori also support applications, for example, in robot motion planning: The "all space" of a two-link planar robot arm is toroidal.

Arrangement on Torus Arrangement on Dupin Cyclide
Overlay of two Arrangements on Dupin Cyclide
Arrangement on Torus
Arrangement on ring Dupin cyclide
Overlay of two Arrangements on Torus


Movie (Demo)

 

 

Links

  • Eric Berberich, Efi Fogel, Dan Halperin, Kurt Melhorn, and Ron Wein
    Arrangements on Parametric Surfaces I: General Framework and Infrastructure
    Mathematics in Computer Science,  4(1): 45-66, 2010 [link] [bibtex]
  • Eric Berberich, Efi Fogel, Dan Halperin, Michael Kerber, and Ophir Setter
    Arrangements on Parametric Surfaces II: Concretizations and Applications
    Mathematics in Computer Science,  4(1): 67-91, 2010 [link] [bibtex]
  • Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn, and Ron Wein
    Sweeping and Maintaining Two-Dimensional Arrangements on Surfaces
    In Proceedings of the 15th Annual European Symposium on Algorithms (ESA), pages 645-656, 2007 [link] [bibtex]
    In Abstracts of 23rd European Workshop on Computational Geometry (EWCG), pages 223-226, 2007 [pdf] [bibtex]
  • Eric Berberich and Michael Kerber.
    Exact Arrangements on Tori and Dupin Cyclides

    In Proceedings of the ACM Symposium on Solid and Physical Modeling (SPM), pages 59-66, 2008 [Info] [link] [bibtex]

Contact

Eric Berberich http://mpi-inf.mpg.de/~eric eric@mpi-inf.mpg.de
Efi Fogel http://www.cs.tau.ac.il/~efif efif@post.tau.ac.il
Dan Halperin http://acg.cs.tau.ac.il/danhalperin danha@post.tau.ac.il
Kurt Mehlhorn http://mpi-inf.mpg.de/~mehlhorn mehlhorn@mpi-inf.mpg.de
Ron Wein http://www.cs.tau.ac.il/~wein wein@post.tau.ac.il
Michael Kerber http://www.mpi-inf.mpg.de/~mkerber mkerber@mpi-inf.mpg.de
Document Actions