Personal tools
You are here: Home Courses Computational Geometry Spring 2010 2D Maps in CGAL and Applications
« December 2019 »
December
SuMoTuWeThFrSa
1234567
891011121314
15161718192021
22232425262728
293031
Log in


Forgot your password?
 

2D Maps in CGAL and Applications

CGAL

General

  • The goal: make the large body of geometric algorithms developed in the field of computational geometry available for industrial applications.
    • Reliable.
    • Flexible.
    • Efficient.
    • Easy to use.
  • Developed in C++ and follows the Generic Programming paradigm.
  • Developed by a consortium consisting of a few institutions in Europe and Israel.
    • Active institutions: (i) ETH (ii) Inria (iii) MPI (iv) TAU (v) Utrecht

History

  • Development started at 1995.
  • First release appeared in June 1997.
  • Work continued after the end of European support in 1999.
  • Editorial Board created in 2001.
  • Geometry Factory founded in January 2003.
    • An INRIA startup.
    • Sells commercial licenses, support, geometry ized development.
  • Version 3.5.1 released in December 2009.
  • Version 3.6 Beta release February 2010.

Numbers

900,000 lines of C++ code
10,000 downloads per year not including Linux distributions
3,500 pages manual
3,000 subscribers to cgal-announce list
1,000 subscribers to cgal-discuss list
120 packages
60 commercial users
25 active developers
7 Google’s page rank for www.cgal.org
6 months release cycle
2 licenses: Open Source and commercial

Customers

Customers

 

Reliability

  • Addresses robustness problems
    • Explicit degeneracy handling.
    • Exact Geometric Computation.

Flexibility

  • Open library
  • Modular structure. Separation between to geometry and topology.
  • Adaptable to user code.
  • Extensible, e.g., data structures can be extended.

Ease of Use

  • Didactic and exhaustive Manuals
  • Follows standard concepts (e.g., C++ and STL)
  • Smooth learning-curve

Efficiency

  • Follows the generic-programming paradigm.
  • Polymorphism is resolved at compile time
    • Has no run-time overhead cost.
    • Large code footprint and long compilation processes.

Architecture

  • Geometric Kernel
    • Constant-size geometric objects (e.g., points, lines, and planes).
    • Predicates and constructors of objects of these types.
  • Basic Library
    • Data structure and algorithms (e.g., Triangulations, Polyhedrons, and Arrangements).
  • Support Library
    • Number types.
    • Geometric-object generators.
    • Input/Output.
    • Visualization.
    • More none geometric types (e.g., Circulators).

Geometric Kernel Classification

  • Dimension - 2, 3, arbitrary
  • Number types:
    • Ring: +,-,*
    • Euclidean ring (adds integer division and gcd) (e.g., CGAL::Gmpz).
    • Field: - +,-,*,\  (e.g., CGAL::Quotient(CGAL::Gmpz)).
    • Exact sign evaluation for expressions with roots (Field_with_sqr).
  • Coordinate representation
    • Cartesian - requires a field number type or Euclidean ring if no constructions are performed.
    • Homogeneous - requires Euclidean ring.
  • Reference Counting.

The Trouble with Double 

[KMSY04]

p = (0.5 + x.u, 0.5 + y.u),
0 ≤ x, y < 256,
u = 2−53,
q = (12, 12)
r = (24, 24)
orientation(p, q, r) evaluated with double
256 x 256 pixel image
RED > 0 YELLOW = 0 BLUE < 0
imprecision

→ Inconsistencies in predicate evaluations.

Orientation in Theory

orientation(p, q, r) = sign(det[
px py
1
qx
qy
1
rx ry
1
])
  = sign((qx − px )(ry − py ) − (qy − py )(rx − px))

ccw(s, q, r) ∩ ccw(s, r , p) ∩ ccw(s, p, q) ⇒ ccw(p, q, r)

ccw

Exact Geometric Computation

Ensure that the control flow in the implementation corresponds to the control flow with exact arithmetic. [Yap]

  • Evaluate predicate instantiated with limited precision.
  • If uncertain ⇒ evaluate predicate instantiated multiple precision.
orientation predicate flow  orientation predicate

Geometric Kernel (easy) Choices

CGAL::Exact_predicates_inexact_constructions_kernel
CGAL::Exact_predicates_exact_constructions_kernel
CGAL::Exact_predicates_exact_constructions_kernel_with_sqrt

Orientation of a triple: Version 1

  • Computing the orientation of 3 points in the plane.
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel  Kernel
typedef Kernel::Point_2                                      Point_2

int main()
{
  Point_2 p(0,0), q(10,3), r(12,19);
  return (CGAL::orientation(q,p,r) == CGAL::LEFT_TURN) ? 0 : 1;
}

Orientation of a triple: Version 2

  • Increasing flexibility.
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel  Kernel
typedef Kernel::Point_2                                      Point_2
typedef Kernel::Orientation_2                                Orientation_2;

int main()
{
  Kernel kernel;
  Orientation_2 orientation = Kernel.orientation_2_object();

  Point_2 p(0,0), q(10,3), r(12,19);
  return (orientation(q,p,r) == CGAL::LEFT_TURN) ? 0 : 1;
}

Basic Library

  • Generic data structures are  parameterized with Traits
    • Separates algorithms and data structures from the geometric kernel.
  • Generic algorithms are parameterized with iterator ranges
    • Decouples the algorithm from the data structure.

Convex Hull

  • A subset Smathbb_Rd is convex if for any two points p and q in the set the line segment with endpoints p and q is contained in S.
  • The convex hull of a set S is the smallest convex set containing S.
  • The convex hull of a set of points P is a convex polygon with vertices in P.

Demonstration of Upper Convex Hull

  • Using Random Access Iterator. [C++]
    • Provides both increment and decrement.
    • Constant-time methods for moving forward and backward in arbitrary-sized steps ('[]' operator).
  • Maintaining the current point separately. [C++]
  • Maintaining an iterator that points to the current point separately. [C++]
  • More generic - can be used for computing the lower hull. [C++]

Miscellaneous

CGAL Arrangements on Surfaces

Two Dimensional Arrangements

Definition: 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
An arrangement of circles in the
plane.
An arrangement of lines in the
plane.
An arrangement of great-circle
arcs on a sphere.

 

The CGAL Arrangement Package

  • Constructs, maintains, modifies, traverses, queries, and presents arrangements on two-dimensional parametric surfaces.
  • Robust and exact.
    • All inputs are handled correctly (including degenerate input).
    • Exact number types are used to achieve exact results.
  • Generic – easy to interface, extend, and adapt
  • Modular – geometric and topological aspects are separated
  • Supports among the others:
    • various point location strategies
    • zone-construction paradigm
    • sweep-line paradigm
    • overlay computation
  • Part of the CGAL basic library

CGAL Arrangements in Numbers

137,080 lines of C++ code (headers)
527 pages of manual
265  files of C++ code (headers)
9 commercial users
7 packages (AOS/SL, BSO, MS, 2D & 3D Env., SR, LER)
AOS - 2D Arrangements on Surfaces
SL - 2D Intersection of Curves (Sweep Line)
BSO - 2D Regularized Boolean Set Operations
MS - 2D Minkowski Sums
SR - SR 2D Snap Rounding
LER - LER 2D Largest Empty Iso Rectangle

Arrangement Data Structure

template <typename GeomTraits, typename TopTraits>
Arrangement_on_surface { ... }

Geometry Traits

  • Is a parameter of the data structures and algorithms.
    • Defines the family of curves that induce the arrangement.
  • Aggregates
    • Geometric types (point, curve).
    • Operations over types (accessors, predicates, constructors).
  • Subdivides input curves into u-monotone subcurves.
    • Most operations involve points and u-monotone curves.
Curve Family Degree Surface Boundness Arithmetic Author
linear segment 1 plane bounded rational TAU
linear segments, rays, lines 1 plane unbounded rational TAU
piecewise linear curves plane bounded rational TAU
circular arcs, linear segments ≤2 plane bounded rational TAU
Inria
algebraic curves ≤2
n
plane bounded
unbounded
algebraic TAU
MPI
quadric projections ≤2 plane unbounded algebraic MPI
planar Bézier curves n plane unbounded algebraic TAU
univariate polynomials n plane unbounded algebraic Inria
rational function arcs n plane unbounded algebraic TAU
geodesics in sphere
≤2 sphere bounded rational TAU
quadric intersection arcs
≤2 quadric unbounded algebraic MPI
Dupin cyclide intersection arcs
≤2 Dupin cyclide
bounded algebraic MPI

Point Location

Given a subdivision A of the space into cells and a query point q, find the cell of A containing q

point location input point location output
  • Fast query processing.
  • Reasonably fast preprocessing.
  • Small space data structure.
  Naive Walk RIC Landmarks
Preprocessing time none none O(n log n)
O(k log k)
Memory space none none O(n) O(k)
Query time bad reasonable good good
Applicability all limited limited limited

Walk — Walk along a line

RIC — Random Incremental Construction based on trapezoidal decomposition

k — number of landmarks‏

Map Overlay

Definition: The overlay of two planar subdivisions S1 and S2 is a planar subdivision S such that there is a face f in S if and only if there are faces f1 and f2 in S1 and S2 respectively such that f is a maximal connected subset of f1f2.

overlay operand 1  overlay operand 2 overlay result 

The overlay of two subdivisions embedded on a surface in mathbb_R3 is defined similarly.

Map Overlay Implementation

template <typename GeomTraitsA, typename GeomTraitsB, typename GeomTraitsRes, 
          typename TopTraitsA, typename TopTraitsB, typename TopTraitsRes,
          typename OverlayTraits>
void overlay(Arrangement_2<GeomTraitsA, TopTraitsA> arr1,
             Arrangement_2<GeomTraitsB, TopTraitsB> arr2,
             Arrangement_2<GeomTraitsRes, TopTraitsRes>& arr_res,
             OverlayTraits& ovl_tr)

The overlay traits handles the following possible 10 cases:

  1. A new vertex v is induced by coinciding vertices vr and vb.
  2. A new vertex v is induced by a vertex vr that lies on an edge eb.
  3. An analogous case of a vertex b that lies on an edge er.
  4. A new vertex v is induced by a vertex vr that is contained in a face fb.
  5. An analogous case of a vertex vb contained in a face fr.
  6. A new vertex v is induced by the intersection of two edges er and eb.
  7. A new edge e is induced by the overlap of two edges er and eb.
  8. A new edge e is induced by the an edge er that is contained in a face fb.
  9. An analogous case of an edge eb contained in a face fr.
  10. A new face f is induced by the overlap of two faces fr and fb.

Parametric Surfaces

Definition: A parametric surface S of two parameters is a surface defined by parametric equations involving two parameters u

and v:

    fS(u, v) = (x(u, v), y(u, v), z(u, v))

Thus, fS : mathbb_Pmathbb_R3 and S = fS(mathbb_P), where mathbb_P is a continuous and simply connected two-dimensional parameter space.
sphere
cylindercone ellipsoid  torus  parabolid    

We deal with orientable parametric surfaces.

2D Arrangement on Surfaces in 3D

Cylinder
Sphere
Cylinder Boundary
Sphere Boundary
S(u, v) = (r cos u, r sin u, v)
u ∈ [−π,π), vmathbb_R
S(u, v) = (r cos u cos v, r sin u cos v, r sin v)
u ∈ [−π, π), v ∈ [−π/2, π/2]

3D Collision Detection

Minkowski Sums

P and Q are two polyhedra in mathbb_Rd.

M = PQ = {p + q | pP, qQ}.

Minkowski sum in the plane

Collision Detection using Minkowski Sums

P and Q are two polyhedra in mathbb_Rd.

PQ ≠ ∅ ⇔ Origin ∈ M = P ⊕ (−Q).

collision detection

Polytope

Definition: A polytope is a bounded convex polyhedron P mathbb_Rd.

Gaussian Maps

Definition: The Gaussian map G(P) of a polytope Pmathbb_R3 is the decomposition of mathbb_S2 into maximal connected regions so that the extremal point is the same for all directions within one region.

G is a set-valued function from ∂P to mathbb_S2.
G(p ∈ ∂P) = the set of outward unit normals to support planes to P at p.
v, e, f — a vertex, an edge, a facet of P.

  • G(f) = outward unit normal to f.
  • G(e) = geodesic segment.
  • G(v) = spherical polygon.

Extended Gaussian Maps

  • G(P) is an arrangement embedded on mathbb_S2, where each face G(v) of the arrangement is extended with v.
  • G(P) is unique ⇒ G−1(G(P)) = P.

Gaussian Maps of Minkowski Sums

The overlay of the Gaussian maps of two polytopes P and Q is the Gaussian map of the Minkowski sum of P and Q.

  • It identifies all the pairs of features of P and Q, respectively, that have common supporting planes.
  • These common features occupy the same space on mathbb_S2.
  • They identify the pairwise features that contribute to ∂(PQ).
cybe  tetrahedron    tetrahedrom cube Minkowski Gaussian map  
 cube Gaussian map  tetrahedron Gaussian map    cube tetrahedrom Minkowski Gaussiam map  
Cube Tetrahedron   Minkowski Sum

2D Motion Planing

Summary

  • Arrangements are versatile.
  • Arrangements are used as foundation for higher level geometric data structures.
  • Arrangements are not bound to the plane.

Literature

Books and Book Chapters

[FWH10] Efi Fogel, Dan Helperin, and Ron Wein.
CGAL Arrangements and Their Applications, A Step-by-Step Guide, to be published.
 
[FHKTWW07] Efi Fogel, Dan Halperin, Lutz Kettner, Monique Teillaud, Ron Wein, and Nicola Wolpert.
Arrangements.
In J.-D. Boissonnat and M. Teillaud, editors, Effective Computational Geometry for Curves and Surfaces, chapter 1, pages 1–66. 2007.
CGCS
[FT07] Efi Fogel and Monique Teillaud.
Generic programming and the CGAL library.
In J.-D. Boissonnat and M. Teillaud, editors, Effective Computational Geometry for Curves and Surfaces, chapter 8, pages 313–320. 2007.

Journal Articles

[FH07] Efi Fogel and Dan Halperin.
Exact and efficient construction of Minkowski sums of convex polyhedra with applications.
Computer-Aided Design, 39(11):929–940, 2007.
 
[WFZH07]
Ron Wein, Efi Fogel, Baruch Zukerman, and Dan Halperin.
Advanced programming techniques applied to CGAL’s arrangement package.
Computational Geometry: Theory and Applications, 38(1–2):37–63, 2007. Special issue on CGAL.
 
[BFHMW10]
Eric Berberich, Efi Fogel, Dan Halperin, Kurt Melhorn, and Ron Wein.
Arrangements on Parametric Surfaces I: General Framework and Infrastructure.
Accepted for publication in Mathematics in Computer Science, 2010. 
 
[BFHKS10]
Eric Berberich, Efi Fogel, Dan Halperin, Michael Kerber, and Ophir Setter,
Arrangements on Parametric Surfaces II: Concretizations and Applications.
Accepted for publication in Mathematics in Computer Science, 2010.
 
[KMSY04] Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee Yap.
Classroom Examples of Robustness Problems in Geometric Computations.
Computational Geometry: Theory and Applications, 40(1):61-78, 2007.

Symposium, Workshop Papers, and Manuscripts

[MFH10] Naama Mayer, Efi Fogel, and Dan Halperin.
Dynamically Maintaining the Exact Minkowski Sums of Rotating Polytopes.
Submitted to Solid and Physical Modeling, 2010.

 

Document Actions