As in 2010, 2011 and 2012, 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.

Previous project ideas of the CGAL project for the **Google Summer of Code** can be found on the following pages:
2010, 2011,
2012.

**Before sending an email to anybody, please carefully read this section.**

First section to read: Information Candidates Should Supply

- Adding a Concept Checking Framework in CGAL
- Adding the ideas of the Screened Poisson Surface Reconstruction algorithm into CGAL
- New Package: 2D Shape Reconstruction from Unorganized Cross-section
- Finalization of the implementation of a 2D Reconstruction and Simplification Algorithm from Point Set
- 2D AABB Tree
- Enhancing the Arrangement-with-History component
- Implement a model of the concept ArrangementDcel using the Combinatorial Map data structure
- Introduce modularity into CGAL
- More point generators in CGAL
- Interface CGAL and Sage
- Adding a Curve-Skeletonization Algorithm into CGAL
- Improved design and new features for the Mesh_2 package
- Visibility Polygon Implementation

CGAL is a C++ template library which heavily relies on concepts. In order to increase the quality of the library we would like to introduce a mechanism to check that all the requirements of a concept are exactly those needed (a concept might be missing some requirements and might also ask requirements that are not used). A solution might be using the Boost Concept Checking Library. This task does not require any particular notion of computational geometry.

CGAL provides a variant of the Poisson algorithm. Main differences are that it uses a tetrahedrization instead of an octree, and performs two passes to avoid artifacts where the algorithm has to fill big gaps. We would like to incorporated the new ideas of Misha Kazhdan's last paper into CGAL. These improvements would allow to explicitly incorporate the points as interpolation constraints, and would reduce time complexity.

This project consists in implementing the following paper of Pooran Memari and Jean-Daniel Boissonnat:

- Provably Good 2D Shape Reconstruction from Unorganized Cross Sections, 2008 Computer Graphics Forum, Vol.27, No. 5, 1403-1410

This algorithm is able to reconstruct a 2D shape described by a set of segments, each representing the intersection of the shape with a line. The implementation will be based on existing components from the CGAL library (2D Constrained Delaunay Triangulation, Voronoi diagram of segments, Intersection primitives, ...). The motivation for implementing this algorithm is to use it as a preprocessing step in the 3D generalization currently under development.

This project consists in going to the submission of a new package to CGAL. The student will start from the prototype code of the following paper by De Goes and Cohen-Steiner and Alliez and Desbrun:

- An optimal transport approach to robust reconstruction and simplification of 2D shapes, in Computer Graphics Forum (proceedings of EUROGRAPHICS Symposium on Geometry Processing), 30, 5, 1593-1602, 2011

The purpose of this project is to understand the code written for this research paper, propose a suitable API and update the code accordingly, write a demo, write the documentation into CGAL style, and submit the package to the Editorial Board for review. Of course, the student is invited to perform an extra optimization of the code and to propose new ideas to improve the algorithm. This project is particularly interesting to show what we usually call ''the extra mile'' to turn a code written for a research paper into a documented and publicly distributable code.

The purpose of this project is to provide the same functionalities as the ones provided by the 3D AABB package but in 2D. Instead of duplicating of the code, the student will have to devise a solution that shares as much as possible source code from the 3D implementation, without breaking backward compatibility. Once completed, a testsuite carefully checking the correctness and performances of the implementation must be devised. The performance of such a core component being important, code profiling and optimization is a key aspect of the project.

Time permitting, the student will propose a solution to the point-inside-polygon test using the 2D AABB-tree and will to participate to the ACM GISCUP 2013.

When you construct an arrangement induced by a set A of arbitrary planar curves, you end up with a collection C of x-monotone subcurves of A that
are pairwise disjoint in their interior. These subcurves are associated with the arrangement edges (more precisely, with pairs of DCEL halfedges).
The `Arrangement_with_history_2<Traits,Dcel>`

class-template offered by the
2D Arrangement
package extends the `Arrangement_2<Traits,Dcel>`

class template with an additional layer that represents A and a cross mapping
between the curves of A and the arrangement edges they induce. Let B denote the set of maximal x-monotone subcurves of the curves in A.
In this project you are asked to augment the `Arrangement_with_history_2`

class-template with an additional layer that represents B,
and cross mappings between the curves of the three layers, i.e., A, B, and C. If time permits, 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.

An object of the class template `Arrangement_2<Traits,Dcel>`

offered by the
2D Arrangement package represents
the planar subdivision induced by a set of x-monotone curves and isolated points into maximally connected cells. The arrangement is
represented as a doubly-connected edge-list (Dcel) such that each Dcel vertex is associated with a point of the plane and each edge is
associated with an x-monotone curve whose interior is disjoint from all other edges and vertices. The Dcel template parameter must be substituted
by a model of the concept ArrangementDcel. The 2D Arrangement
package offers a model of this concept called `Arr_dcel_base<V,H,F>`

.
In this project you are asked to develop another model of this concept using the Combinatorial Map data structure offered by the
Combinatorial Maps package.

CGAL is a C++ library of algorithm and library providing various modules (packages) that do not necessarily depend on each other. A criticism that we often hear about CGAL is that it's a too large library, people would be happy to have only a small portion of the library to use only what they need. The purpose of this project is to find the best approach to achieve this goal. Internally, CGAL is already decomposed into packages and the release tarball consists in a flatten view of this structure. This project implies to detect the real dependencies amongst packages (that is headers included and used), encode this dependencies at the level of cmake, identifies core component that are required by all the packages, find a way for users to download the modules they are interested in, etc.

If time allows it, the student will try to find a way to reduce the size of the core component, make optional the compilation of the lib, etc.

CGAL is a high quality generic C++ library on Computational Geometry. Amongst its features, CGAL offers random point generators in disks, squares, balls, cubes, hypercubes, to mention a few. Point generation is quite useful for several things, e.g., testing algorithms, obtaining initial values for optimization schemes, and more. In this work, we will concentrate efforts on implementing new point generators. Some of the useful point generators that are missing in CGAL include random points inside a triangle, simplex, triangulation, on a surface mesh, on a pure complex, ...

Sage is one of the leading and fastest growing open source mathematics software systems. It combines the features of nearly a hundred open source projects and provides a clean high-level Python-based shell and programming environment to easily access their functionality. In particular, Sage offers a wide range of symbolical and algebraic computations. However, Sage currently lacks advanced algorithms for geometric computing. Vice versa, the development of geometric-algebraic algorithms in CGAL can be tedious, and while CGAL provides highly efficient filtered algebraic predicates for its current use cases, more complicated applications would benefit from the large range of algebraic operations accessible via Sage.

The goal of this project is to provide a clean way to call CGAL functions from Sage. The existing CGAL bindings for Python can serve as a guide, but have to be extended by interfaces supporting arbitrary precision number types. For efficiency reasons, it seems that Cython is the method of choice and should be preferred over SWIG or Boost wrappers.

If time allows, a second goal is to access Sage functionality within CGAL.

This project consists in implementing a curve-skeletonization algorithm for a watertight surface mesh. The algorithm consists of two main phases. In the first step, a mass-spring system is solved, resulting in a progressive contraction of the model into a skeleton. In the final step, the watertight surface is converted into a network of curves by shortest-edge collapse. The basic algorithm can also be extended to guarantee that the curves are centered within the object.

A visual demo of the algorithm is available here and the algorithm is explained in the following paper (a reference implementation is also available at this page):

- Tagliasacchi, A., Alhashim, I., Olson, M., and Zhang, H. 2012. Mean Curvature Skeletons. Computer Graphics Forum (Proceedings of the Symposium on Geometry Processing) 31, 5, 1735-1744.

The Mesh_2 package implements a 2D isotropic triangle mesh generator. Currently, the domain to be meshed is defined by some constrained edges and a set of seed points. The constrained edges divide the plane into several connected components. The mesh domain is either the union of the bounded connected components including at least one seed, or the union of the bounded connected components that do no contain any seed. The project can be split into three phases:

- Improve the C++ interface of the package, in order to unify the API with the Mesh_3 package (3D mesher).
- Add some mesh optimization methods, to improve the quality of the output meshes.
- Develop an "oracle" abstraction layer (as devised for Mesh_3) so that the mesher can take different types of input: implicit functions, polygonal domains, 2D images... and on the way, add the ability to manage multi-domain inputs.

or additionnal details, here is the documentation of the current Mesh_2 package and of the Mesh_3 package.

Given a planar polygonal domain (which can be given as a polygon or as an arrangement) and a query point, compute the polygon of all points that can see the query point. Efficient algorithm implementations for this problem are still missing in CGAL. This project will therefore join forces with people at TU Braunschweig, with the purpose of developing a new package for visibility. Together we will work on implementing several different algorithm types (with vs. without preprocesing) for different problem inputs (simple polygons vs. polygons with holes vs. arrangements); including limited vision ranges would be a welcome extra.

Specifically, the project consists of the following steps:

- Familiarize with the interfaces and shape them together with the mentor team
- Select at least one visibility algorithm and implement it
- Join in developing a test suite and instances to validate correctness of all the algorithms

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

- 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.
- Provide a proposal of a technical solution with your envisioned methodology. The more detailed the better.
- Explain how the solution will be available to the user, in which form. Do not forget the documentation, unitary tests and cross-platform aspects.
- 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.
- Provide a formal commitment that you will be involved full time on the GSoC. This is absolutely mandatory.

- First name, last name, affiliation and geographical location.
- A brief list of the main studies and programming courses attended, with ranking.
- List of the most important software projects contributed and success.
- Which are your best skills in terms of programming and scientific computing?
- In general what is your taste in terms of programming? language, methodology, team work, etc.
- Is there anything that prevents you from working full time on the project during the program period?
- 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?
- Are you more interested in the theory/scientific aspect of CGAL, or do you feel more like a hacker?
- What are your long-term wishes in terms of job?

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