CGAL Projects for Google Summer of Code 2013

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.

Summary:

First section to read: Information Candidates Should Supply

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

Adding a Concept Checking Framework in CGAL

Mentor: from GeometryFactory

Project Description

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.

Required skills: C++, Generic programming

Adding the ideas of the Screened Poisson Surface Reconstruction algorithm into CGAL

Mentor: from Inria Sophia-Antipolis and Misha Kazhdan John Hopkins University

Project Description

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.

Required skills: C++, Generic programming, Computational geometry

New Package: 2D Shape Reconstruction from Unorganized Cross-section

Mentor: from GeometryFactory

Project Description

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

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.

Required skills: Computational geometry, C++, CGAL

Finalization of the implementation of a 2D Reconstruction and Simplification Algorithm from Point Set

Mentors: Pierre Alliez from Inria Sophia-Antipolis and from GeometryFactory

Project Description

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:

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.

Required skills: Generic Programming, C++, QT4 (GraphicsView Framework), Computational Geometry is a plus.

2D AABB Tree

Mentor: from Inria Sophia-Antipolis and from GeometryFactory

Project Description

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.

Required skills: Generic Programming, C++, Data Structures and Algorithms

Enhancing the Arrangement-with-History component

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

Project Description

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.

Required skills: C++, Generic Programming, Arrangement

Implement a model of the concept ArrangementDcel using the Combinatorial Map data structure

Mentors: from the Applied Computational Geometry Lab, Tel Aviv University and from LIRIS

Project Description

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.

Required skills: C++, Generic Programming, Arrangement

Introduce modularity into CGAL

Mentor: from GeometryFactory.

Project Description

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.

Required skills: C++, Generic Programming, cmake

More point generators in CGAL

Mentor: from Federal University of Pernambuco.

Project Description

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

Required skills: C++, Generic programming

Interface CGAL and Sage

Mentor: from MPI Saarbruecken, and Burcin Erocal from TU Kaiserslautern, Sage and Pynac projects.

Project Description

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.

Required skills: C++, Python, Cython
Good-to-have Skills: CGAL, Sage

Adding a Curve-Skeletonization Algorithm into CGAL

Mentor: from Ecole Polytechnique Federale de Lausanne, and from GeometryFactory.

Project Description

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):

Required skills: C++, background in geometry processing

Improved design and new features for the Mesh_2 package

Mentor: from GeometryFactory, and from Inria Sophia-Antipolis

Project Description

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:

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

Required skills: Advanced C++, generic programming, background in Computational Geometry or Geometry Processing.

Visibility Polygon Implementation

Mentor: and Alexander Kröller from TU Braunschweig

Project Description

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:

Required skills: C++, some knowledge of Computation Geometry

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.