CGAL homepage   ACG at TAU  
TAU Members   People   Projects  

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

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.
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.

Links

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://www.cs.tau.ac.il/~danha 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

[Projects Page] [Top]
Site is maintained by Efi Fogel. Last modified: July 19 2007.