As in 2010, the CGAL Project was a mentoring organization of the Google Summer of Code in 2011. Successful projects can be found here.
On this page we presented some project ideas.
Previous project ideas of the CGAL project for the Google Summer of Code can be found on the following pages: 2010.
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.
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. |
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:
Required skills: C++ and Multithreading in C++.
Mentor: Sebastien Loriot from GeometryFactory
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++.
Mentor: Andreas Fabri from GeometryFactory
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++.
Mentors: Efi Fogel and Michael Hemmer from the Applied Computational Geometry Lab, Tel Aviv University
Given two sets A, B ∈ R2, their Minkowski sum, denoted as A ⊕ B, is their point-wise sum, namely the set:
| A ⊕ B = {a + b | a ∈ A, b ∈ B}. |
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:
Required skills: C++, templates, Minkowski sum.
Mentors: Sebastien Loriot from GeometryFactory and Gael Guennebaud from LaBRI Bordeaux.
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 functionality.
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.
Mentors: Andreas Fabri from GeometryFactory, and Olga Sorkine from ETH Zurich.
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.
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.
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):
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.
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:
<s2,s3,s1>.
If we specify the equation x = x0 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.
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.
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.
Mentor: Pierre Alliez from INRIA Sophia Antipolis
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:
Required skills:computational geometry, C++.
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
This anchor is a mailto: with a mail body containg the above items.
