CGAL Projects for the Google Summer of Code 2011

As in 2010 the CGAL Project is a mentoring organization of the Google Summer of Code. On this page we present some project ideas as well the information applicants have to provide us. GSoC applicants are welcome to propose other ideas and check if a mentor is interested in supervising it.

Summary

1. Enhancing Some Packages via Multi-Processing
   1. Adapting Arrangement to the Parallel Boost Graph Library
   2. Parallelizing Divide-And-Conquer
2. Replacing some basic non-geometric tools in CGAL by Boost/TR1/C++0x functionality
3. Switching from CGAL::HalfedgeGraph to boost::PlanarEmbedding
4. Supporting Minkowski Sum of Degenerate and Generalized Polygons
5. Add an Interface for the Eigen Library
6. Integrate As-Rigid-As-Possible Surface Modeling in CGAL
7. Enhancing the 2D Arrangement package
   1. Enhancing the Arrangement-with-History component and Polygon Repairing
   2. Enhancing the Plane-Sweep Framework for Arrangements
   3. Enhancing the Point Location
8. Local Operators in 3D Triangulations

Enhancing Some Packages via Multi-Processing

Mentor: Ophir Setter from the Applied Computational Geometry Lab, Tel Aviv University

Though the CGAL code is designed to be efficient, as multi-core processors become ubiquitous, the demand for multi-threaded data-structures rises. The idea of the project is to enable multi-threading in some of the CGAL packages. This enhancement is expected to contribute a significant performance boost in real-world multi-core scenarios. Some of the tasks should be tested and benchmarked on real-world data.

1. Adapting Arrangement to the Parallel Boost Graph Library

   Project Description

   The Arrangement data-structure is already adapted to the Boost Graph Library [SLL02] (BGL) which enables the user to run BGL algorithms on the arrangement data-structure. The task includes adapting the arrangement data-structure to the Parallel Boost Graph Library (PBGL) to enable users to run parallel graph algorithms on the Arrangement data-structure out-of-the-box. This requires implementing additional concepts imposed by PBGL.

   [SLL02]

   J. G. Siek, L.-Q. Lee, and A. Lumsdaine. The Boost Graph Library. Addison-Wesley, Boston, MA, USA, 2002.

2. Parallelizing Divide-And-Conquer

   Project Description

   Some of the algorithms in the 2D Arrangement package and related packages use a divide-and-conquer approach. This approach enables the immediate improvement by multi-threading. The following components are candidates for such an enhancement:

   1. Boolean set-operations --- The algorithms in the 2D Regularized Boolean Set-Operations package can use both a D&C approach and a sweep-line approach. This task also includes the investigation of the trade off between the two approaches.
   2. Envelope algorithms.
   3. Minkowski sum using convex decomposition.

Required skills: C++ and Multithreading in C++.

Replacing some Basic Non-Geometric Tools in CGAL by Boost/TR1/C++0x Functionality

Mentor: Sebastien Loriot from GeometryFactory

Project Description

The CGAL project started in 1996, before the first C++ standard was released, and before the Boost project was launched. CGAL has accumulated a number of geometry-independent tools which these days offer duplicate functionality with what is (a) in TR1, (b) planned for the next C++ standard C++0x, and/or (c) are in Boost. Doing the replacement would help in the long-term by easing maintenance: (a) less code to maintain, and (b) new people are more likely to know about a standard tool, and it will be more useful to them to learn about them, rather than something which is only in CGAL and with no geometric or scientific flavor.

The goal of this project would be to "cleanup" CGAL by replacing as many of these as possible. Of course, depending on the case, there can be constraints in terms of efficiency, API compatibility, deprecation paths, etc. So, the task is not trivial, but there are pieces easier than others. It should be a nice way to learn about various standard tools in CGAL, Boost and C++0x.

Some examples of things to be considered:

    Filter_iterator        ->  boost::filter_iterator
    Object                 ->  boost::any/variant
    Triple/Quadruple       ->  TR1::tuple/array
    Unique_hash_map        ->  TR1::unordered_map/set
    copy_n                 ->  C++0x::copy_n
    iterator ranges        ->  Boost.Range
    Timers                 ->  Boost.Timers
    Integer8/16/32         ->  int32_t...
    min_max_element        ->  C++0x (or TR1 ?)
    predecessor/successor  ->  prev/next (C++0x/TR1)
    

Required skills:boost, advanced C++.

Switching from CGAL::HalfedgeGraph to boost::PlanarEmbedding

Mentor: Andreas Fabri from GeometryFactory

Project Description

Inspired by the Boost Graph Library (BGL), we extended the Graph concept by introducing the HalfedgeGraph. This concept imposes an order on the edges incident to a vertex. It leads to the notion of edges cycles and hence faces. Currently, the CGAL Surface Mesh Simplification package operates on polyhedral surfaces using this API.

Starting with boost Rel 1.35, the BGL added the notion of PlanarEmbeddings.

The goal of this project is to investigate how we can switch to this PlanarEmbedding concept, and if it still needs further extensions for our purposes. The next step is to make the necessary changes in the Surface Mesh Simplification package. If there still remains time, the student could start to rewrite the CGAL Surface Mesh Parametrisation package, which took another approach to make an abstraction of a polyhedral surface.

Required skills:BGL, advanced C++.

Supporting Minkowski Sum of Degenerate and Generalized Polygons

Mentors: Efi Fogel and Michael Hemmer from the Applied Computational Geometry Lab, Tel Aviv University

Project Description

Given two sets A, B ∈ R², their Minkowski sum, denoted as A ⊕ B, is their point-wise sum, namely the set:

Minkowski sums are used in many applications, such as motion planning and computer-aided design and manufacturing.

The 2D Minkowski Sums package of CGAL contains the function minkowski_sum_2() that computes the planar Minkowski sums of two simple polygons (see the manual for the precise definition of a simple polygon). The function is overloaded with two variants; one implements the decomposition method and the other implements the convolution method. Both summands are restricted to simple polygons that do not contain holes. (Resulting sums may contain holes though.)

The 2D Minkowski Sums package, like the 2D Regularized Boolean Set-Operations package, is implemented on top of the arrangement infrastructure. The two packages are integrated well to allow mixed operations. However, while the latter supports operations on polygons the boundaries of which comprise x-monotone curves that are not necessarily line segments, the former is restricted to linear polygons only.

You are asked to enhance the implementations of the package to support the following:

1. Minkowski sums of degenerate polygons, where any summand reduces to a line segment or to a point using both decomposition and convolution methods.
2. Minkowski sums of generalized polygons the boundaries of which comprise circular arcs or line segments using the convolution method.
3. Minkowski sum of polygons with holes using the decomposition method. This implies introducing a decompisition operation that decomposes polygons with holes.

Required skills: C++, templates, Minkowski sum.

Add an Interface for the Eigen Library

Mentors: Sebastien Loriot from GeometryFactory and Gael Guennebaud from LaBRI Bordeaux.

Project Description

Several CGAL packages need to solve sparse linear systems. As CGAL has a clear focus on geometry, we use a third party library for this purpose: Taucs. The main drawback of Taucs is that it has no active developer community maintaining it and making it evolve.

The goal of this project is to interface CGAL with the Eigen library. This project is about interfacing software, hence beyond C++ programming one has to care about the build system, cross-platform aspects. Depending on the progress of this project, an additional task would be to work on out-of-core functionalily.

This project will be co-mentored by Gael Guennebaud for the Eigen library and by Sebastien Loriot for CGAL

Required skills: C++, templates, cmake, solvers.

Integrate As-Rigid-As-Possible Surface Modeling in CGAL

Mentors: Andreas Fabri from GeometryFactory, and Olga Sorkine from ETH Zurich.

Project Description

In their SGP 2007 paper entitled As-Rigid-As-Possible Surface Modeling Olga Sorkine and Marc Alexa present a new algorithm for deforming a polyhedral surface, when a zone and some handles on the surface are selected and the user moves the handles in space. A video captured with a prototype implementation can be watched here or on YouTube.

As evaluators of the prototype implementation were satisfied, we plan to reimplement the algorithm in CGAL, so that it operates on CGAL polyhedral surfaces, and uses the solver APIs of CGAL that allow to easily exchange the underlying solver.

This project will be co-mentored by Olga Sorkine as far as the algorithm itself is concerned and by Andreas Fabri as far as CGAL and software design questions are concerned.

Required skills: geometry processing, numerical solvers, C++, templates.

Enhancing the 2D Arrangement Package

Mentors: Efi Fogel and Michael Hemmer from the Applied Computational Geometry Lab, Tel Aviv University

The 2D Arrangement package of CGAL has a long history. Like many other packages, it is the result of a long development process. Over the years this package has evolved. The code went through small and large modifications in form of bug fixes, extensions, restructuring, and re-design. Through the years we have also collected a modest number of features that we haven't implemented yet. Three of these missing features are listed below. Each item is considered as a separate project. You many need to refer to the user manual to understand what the project is about.

1. Enhancing the Arrangement-with-History component and Polygon Repairing

   Project Description

   Boolean operations on polygons, referred to as Boolean set-operations, constitute fundamental tasks in computational geometry. These operations are ubiquitous in computer graphics, computer aided design and manufacturing (CAD/CAM), electronic-design automation, and many more domains. Unfortunately, input data of such operations, namely a set of one or more polygons, used in real-world applications is occasionally corrupted, as it originates from measuring devices that are susceptive to noise and physical disturbances. In some other cases, it contains many degeneracies, which either disable computations based on fixed-precision arithmetic, or slow down further computation using multi-precision geometric computation. CGAL offers the package 2D Regularized Boolean Set-Operation, which supports Boolean set-operations on point sets bounded by x-monotone segments in two-dimensional Euclidean space. These operations expect each input point-set to meet a specific set of requirements. Naturally, passing point sets that fail to meet these requirements as input to a Boolean set-operation must be avoided.

   A simple point-set is topologically equivalent to a disc, and has a well-defined interior and exterior. Automatically "fixing" corrupted data, that is, converting invalid point-sets, the interiors and exteriors of which are not well defined to valid ones, is not a simple task. As a matter of fact, it is impossible to come up with a procedure that yields the desired results in all cases. Consider, for example, the self-intersecting polygon depicted on the right. It is uncertain which points are contained in the point set and which ones are not, but including the green small triangle on the right and excluding the red small triangle on the left is a good guess. Winding numbers appear to be useful in such cases. The winding number of a point is the number of counterclockwise cycles the oriented boundary makes around the point. It is common to use one of the following three heuristics (although one could come up with more options):

   • Consider a point included in the point set only if its winding number is non-zero.
   • Consider a point included in the point set only if its winding number is greater than zero.
   • Consider a point included in the point set only if its winding number is odd.

   Computing the winding number of a point set bounded by linear segments can conveniently be done with arrangements supported by the 2D Arrangement package, and in particular with the arrangement-with-history class-template. The 2D Regularized Boolean Set-Operation package supports polygons the boundaries of which comprise x-monotone curves that are not necessarily line segments. Such polygons are referred to as "General Polygons". Computing the winding numbers of general polygons requires an extension of the arrangement-with-history class-template.

   When you construct an arrangement induced by a set C of arbitrary planar curves, you end up with a collection C'' of x-monotone subcurves of C that are pairwise disjoint in their interior. These subcurves are associated with the arrangement edges (more precisely, with pairs of DCEL halfedges). The connection between the original input curves and the arrangement edges is lost during the construction process. This loss might be acceptable for some applications. However, in many practical cases it is important to determine the input curves that give rise to the final subcurves.

   The Arrangement_with_history_2<Traits,Dcel> class-template extends the Arrangement_2<Traits,Dcel> class template with an additional container that represents C and a cross mapping between the curves of C and the arrangement edges they induce.

   The arrangement-with-history class-template is somehow deficient. For example, it is restricted to general curves that do not result with points when subdivided into x-monotone curves, as the interface allows a user to obtain induced edges only. Another deficiency, much more significant, is the lack on an intermediate layer, which represents the x-monotone curves. Let C' denote the set of maximal x-monotone subcurves of the curves in C. Recall that C'' is the set of pairwise disjoint in their interiors subcurves of the curves in C'. You are asked to augment the Arrangement_with_history_2 class-template with an additional container that represents C', and (i) a cross mapping between the curves of C and the curves of C', and (ii) a cross mapping between the curves of C' and the arrangement halfedges they induce.

   As a response to a user request for the curves (and isolated points) induced by a general curve, the range of either edges (and vertices) are returned in arbitrary order. However, as a response to a user request for the edges induced by an x-monotone curve, the range of edges are returned in order from left to right.

   The last part of this project is to develop a generic function that repairs corrupted general polygons exploiting the augmented arrangement-with-history class-template.

   Required skills: C++, templates, Arrangement.
   

2. Enhancing the Plane-Sweep Framework for Arrangements

   Project Description

   The plane-sweep algorithm is a fundamental concept in Computational Geometry. It plays a central role in the algorithmic study of arrangements. The famous plane-sweep algorithm introduced by Bentley and Ottmann [Ben75] was originally formulated for sets of line segments in the plane. Let S be a set of input line segments in the plane. Consider the vertical line l in the figure to the right. The intersections of the segments in S with l define a one-dimensional arrangement A(S ∩ l) on the line l. It comprises three vertices, and four one-dimensional cells, that is, two half-infinite intervals (rays), and two line segments. We can describe the combinatorial structure of the arrangement A(S ∩ l) by listing the curves that intersect l from bottom to top: <s₂,s₃,s₁>. If we specify the equation x = x₀ of the line l, then we also get the coordinates of the vertices of the one-dimensional arrangement.

   If l does not cross a vertex of the two-dimensional arrangement A(S), and it is slightly (infinitesimally) moved to the right or to the left, the combinatorial structure of the one-dimensional arrangement on l remains intact. This structure changes only when l hits a vertex of the arrangement, either an endpoint of a line segment in S or the intersection point of two (or more) segments in S. Accordingly, we sweep the vertical line l over the collection of curves in the plane from x = -∞ to x = +∞ to discover vertices which are intersection points of curves, and other properties of the arrangement. We stop the sweep at a finite number of points, which we call events. The stopping points are endpoints and intersection points of the segments, since between any consecutive pair of events, the combinatorial structure of the one-dimensional arrangement on l does not change. We maintain two data structures to carry out the sweep efficiently. One structure describes the (dynamically changing) one-dimensional arrangement along the line l; it is called the status structure. The second structure is a queue that keeps track of the events, sorted in increasing xy-lexicographic order; it is called the event queue. Events that are known in advance are inserted into the queue at the beginning of the algorithm. This is the case with events associated with the endpoints of the curves. Other events, namely, intersection points between curves, are discovered as the algorithm proceeds. They are inserted into the queue when discovered.

   Sweeping n curves having k intersections, takes O((n+k)log n) time. In the literature you can find, in addition to a more detailed description of the algorithm, variants that handle degenerate cases and nuances about the time and space complexity of the algorithm. Notice that although the description above applies to line segments, the same procedure works seamlessly for any family of x-monotone curves.

   The 2D Arrangement package offers a generic implementation of the plane-sweep algorithm in form of a class template called Sweep_line_2<Traits, Visitor>. It handles any set of arbitrary x-monotone curves, and serves as the foundation of a family of concrete operations, such as computing all points of intersections of a set of curves, (Strictly speaking this operation is provided by the 2D Intersection of Curves package, which is based on the 2D Arrangements package.) constructing an arrangement induced by a set of curves, aggregately inserting a set of curves into an existing arrangement, and computing the overlay of two arrangements. A concrete algorithm is realized through a plane-sweep visitor, the template parameter of the Sweep_line_2 class-template, which resembles the visitor design-pattern [GHJ+95, Chapter 5]. In our case a visitor defines an operation based on the plane-sweep algorithm to be performed on a set of curves and points. (The BOOST Graph-Library, for example, uses visitors [SLL02, Chapter 12.3] to support user-defined extensions to its fundamental graph-algorithms.)

   Currently, the plane-sweep implementation does not support certain sets of x-monotone curves: The execution may fail if the input set contains a pair of x-monotone curves that overlap in a non-continuous portion. This may occur, for example, with polylines (continuous piecewise linear curves). The first part of this project is to enhance the implementation to support all types of x-monotone curves.

   The second part of the project is to implement the operations listed below through the introduction of suitable visitors.

   1. Computing all points of intersections of a set of x-monotone curves and maintain the association between each intersection point and the two (or more) x-monotone curves that induce the intersection.
   2. Finding the minimum-area triangle defined by a set of points in the plane. You may wonder what is the connection between this problem and the plane-sweep algorithm. To keep this text to minimum at this point, let us just say that one efficient algorithm to solve the problem requires the construction of the arrangement induced by the lines dual to the input points.

   The last part of the project is to expose the plane-sweep class-template to the public, so that other users can implement their own concrete algorithms. This requires implementing tests, developing additional examples, and writing the appropriate documentation.

   [Ben75]	J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509-517, September 1975.
   [GHJ+95]	E. Gamma, R. Helm, R. Johnson, and J. M. Vlissides. Design Patterns --- Elements of Reusable Object-Oriented Software. Addison-Wesley, Boston, MA, USA, 1995.
   [SLL02]	J. G. Siek, L.-Q. Lee, and A. Lumsdaine. The Boost Graph Library. Addison-Wesley, Boston, MA, USA, 2002.

   Required skills: C++, templates, Sweep-line framework.
   

3. Enhancing the Point Location

   Project Description

   One of the most important query types defined on arrangements is the point-location query: Given a point, find the arrangement cell that contains it. Typically, the result of a point-location query is one of the arrangement faces, but in degenerate situations the query point can be located on an edge or coincide with a vertex. Point-location queries are not only common in many applications, they also play an important role in the global insertion-functions. Therefore, it is crucial to have the ability to answer such queries effectively for any arrangement instance.

   The arrangement package includes several classes (more precisely, class templates parameterised by an arrangement class) that model the ArrangementPointLocation_2 concept. Namely, they all have a member function called locate() that accepts a query point q and returns the face, edge or vertex that contains the query. Each of the various point-location classes employs a different algorithm or strategy for answering queries. One of the most important is the class using Landmarks. The class uses a set of "landmark" points whose location in the arrangement is known. Given a query point, it uses a Kd-tree to find the nearest landmark and then traverses the straight line segment connecting this landmark to the query point.

   It is recommended to use the landmarks point-location strategy when the application frequently issues point-location queries on a rather static arrangement that the changes applied to it are mainly insertions of curves and not deletions of them. However, the current implementation is restricted to bounded arrangements and easy curve types. Fixing the first part is a rather straight forward task since it just means to adjust the existing code to the few special cases caused by unbounded curves. This will probably be a good warm up phase to get more familiar with the code. The second part is slightly more involved, since it is caused by the fact that (depending on the curve type) it is sometimes not easy to provide a "straight line segment" (or x-monotone curve) that connects a landmark point with a query point. Therefore, we would like to implement a different walk strategy that does not require the construction of a connecting segment. This would allow to relax the concept ArrangementLandmarkTraits_2 and would enable point location based on landmarks for a broader set of curve types such as Bézier curves, rational arcs, and algebraic segments.

   Required skills: C++, templates, Arrangement and point location.
   

Local Operators on 3D Triangulations

Mentor: Pierre Alliez from INRIA Sophia Antipolis

Project Description

CGAL provides already a rich set of triangulations in 2D and 3D. In 2D these triangulations come with local operators such as edge flip or edge collapses which are useful a range of algorithms. In 3D the triangulations already provide a rich interface for inserting points, removing vertices, locating, etc. but lack some operators such as edge collapse or edge removal.

The goal of this project is to enhance the implementations of the 3D triangulations by adding the following features:

1. Edge collapse operator in the triangulation data structure (TDS). This requires adding two tests: one to preserve topology (so-called link condition) to be added to the TDS, and one to preserve geometric embedding (a polyhedron kernel test) to be added to the triangulation interface.
2. Edge removal operator in the triangulation data structure (TDS), useful among others to perform 3-2 and 4-4 flips (see paper). This again requires devising topological and geometrical tests.
3. Assess all other operators described in paper and implement them.

Required skills:computational geometry, C++.

Information Candidates Should Supply

The application process has several steps. Before contacting anybody verify that you are eligible, that is that you are enrolled as student, don't get a tuition fee, etc. The next step is to contact the mentor of the project you are interested in. You have to convince him that you are the right person to get the job done. The next step is to work out more details and to contact the mentoring organization by providing the following information by email to gsoc-cgal@lists-sop.inria.fr

Project

1. Select a project in the list and provide your personal and detailed description. If you wish to work on another idea of your own, we are pretty open as long as this serves the goal of consolidating CGAL as a whole.
2. Provide a proposal of a technical solution with your envisioned methodology. The more detailed the better.
3. Explain how the solution will be available to the user, in which form. Do not forget the documentation, unitary tests and cross-platform aspects.
4. Provide a realistic schedule with objectives (one every two weeks for example) and deadlines. Focus on mid-term objectives as well as on the final evaluation.
5. Provide a formal commitment that you will be involved full time on the GSoC. This is absolutely mandatory.

Personal data

1. First name, last name, affiliation and geographical location.
2. A brief list of the main studies and programming courses attended, with ranking.
3. List of the most important software projects contributed and success.
4. Which are your best skills in terms of programming and scientific computing?
5. In general what is your taste in terms of programming? language, methodology, team work, etc.
6. Is there anything that prevents you from working full time on the project during the program period?
7. How do you see your involvement after the program ends? Do you see yourself pushing the project further, or do you see yourself contributing to other CGAL projects?
8. Are you more interested in the theory/scientific aspect of CGAL, or do you feel more like a hacker?
9. What are your long-term wishes in terms of job?

A mailto:

This anchor is a mailto: with a mail body containg the above items.