CGAL Projects for Google Summer of Code 2012

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

Summary:

  1. Switching from CGAL::HalfedgeGraph to boost::PlanarEmbedding
  2. Extend the packages Combinatorial maps and Linear cell complex
  3. Webdemo for Visualization of Triangulated Surfaces - aiming at algebraic ones
  4. Porting the 2D-Arrangement demo to Qt 4 and enhancing it
  5. Adding a surface mesh hole filling algorithm into CGAL
  6. Adding a pose independant 3D mesh surface segmentation algorithm into CGAL
  7. Improved design and new features for the Mesh_2 package
  8. New features for the 3D Fast Intersection and Distance Computation (AABB Tree) package
  9. Rework CGAL 3D demo
  10. Surface Reconstruction from Slices
  11. Enhancing the Landmarks point-location strategy for 2D arrangements
  12. External project related to CGAL

Switching from CGAL::HalfedgeGraph to boost::PlanarEmbedding

Mentor: from GeometryFactory

Project Description

Inspired by the Boost Graph Library (BGL), we extended the Graph concept by introducing the HalfedgeGraph concept. 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++

Extend the packages Combinatorial maps and Linear cell complex

Mentor: from LIRIS

Project Description

The two packages Combinatorial maps and Linear cell complex are new in CGAL and thus provide only basic functionalities. The goal of this project is to improve these two packages by adding several new functions. We will start by some basic functions such as copy operator and constructor, inversion method, copy of a part of a combinatorial map... One key point of CGAL packages is the genericity, thus each new function must satisfy this paradigm (for example the copy must be possible between two CMaps having different type of darts or attributes). After this first step, we will develop a new mechanism allowing to associate dynamically some information to a given combinatorial map. Indeed, in the current version, information can only be associated in the compiling step by using template arguments. Lastly, we plan to develop new high level geometrical functions such as the extrusion along a path, the decomposition of a 3D linear cell complex in convex volume... Each new function will be added in the existing Linear cell complex demo.

Required skills:C++, templates

Webdemo for Visualization of Triangulated Surfaces - aiming at algebraic ones

Mentor: from Max-Planck-Institut für Informatik

Project Description

The goal of this project is to provide a webdemo (running in a browser) to visualize the analysis and triangulation of an algebraic surface (or several ones). The project is the next iteration of the webdemo for analyzing and visualizing algebraic curves in 2D (see this page). The iteration is with respect to multiple goals. On one hand it should lift the dimension by one. As for the planar case, there is code available to analyze the algebraic surfaces with its singularities and the theory for triangulating them is also written in a journal submission. However, a certain precision (at least pixel size) must be guaranteed. On the other hand, the new demo should replace the web rendering (currently using Flash) with an more advanced technology.

There are some milestones visible:

Required skills:C++, WebGL or similar technique, some knowledge about triangulations + polynomials in x,y,z

Porting the 2D-Arrangement demo to Qt 4 and enhancing it

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

Project Description

The project consists of two phases. The 2D-Arrangement demo program is currently based on Qt 3. The first phase of the project is to port the demo program to Qt 4. The second phase is to enhance the demo.

A partial list of enhancements follows:

Required skills:C++, Generic Programming

Adding a surface mesh hole filling algorithm into CGAL

Mentor: from GeometryFactory

Project Description

This project consists in implementing a classical hole filling algorithm for surface mesh. The algorithm is described in the following paper:

The algorithm is explained in the Model Repair slides (p. 20) coming with the Polygon Mesh Processing book.

WARNING: An implementation is available under GPL on the web site of the aforementioned book. To prevent any copyright issue and to respect the authors' work, please do not look at that code if you plan to work on this project.

Required skills:C++, Background in Computational Geometry or Geometry Processing.

Adding a pose independant 3D mesh surface segmentation algorithm into CGAL

Mentor: from GeometryFactory

Project Description

This project consists in implementing a segmentation algorithm described in this paper:

The particularity of this algorithm is that it does not rely on local geometric quantities to make the segmentation. It uses a function defined on each point of the mesh (the shape diameter function, SDF) that is a good approximation of the distance to the medial axis of the meshed object. If the project goes well, we can in addition handle the skeleton extraction using the SDF also described in the paper.

Required skills:C++, Background in Computational Geometry or Geometry Processing.

Improved design and new features for the Mesh_2 package

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

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

New features for the 3D Fast Intersection and Distance Computation (AABB Tree) package

Mentors: from INRIA Sophia-Antipolis, and from GeometryFactory

Project Description

The package offers a static data structure and algorithms to perform efficient intersection and distance queries against sets of finite 3D geometric objects. The set of geometric objects stored in the data structure can be queried for intersection detection, intersection computation and distance.

This package turns out useful for a number of atomic geometry processing queries. In this project we propose to add the following features:

Some more advanced changes include designing a dynamic AABB tree through rebalacing, and the possibility to use various primitives as distance queries instead of just point queries.

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

Rework CGAL 3D demo

Mentor: from GeometryFactory

Project Description

CGAL has a large amounts of demos to showcase functionality and ease debugging for authors of packages. Those demos have been written using ad hoc forks of an existing foundation framework. Some work has been done to unify this framework in a plug-in architecture and to integrate OpenSceneGraph as the main means for rendering and scene management.

Required skills:Solid C++, OpenGL

Bonus Skills:Qt, OpenSceneGraph

Surface Reconstruction from Slices

Mentor: from Technische Universität Wien

Project Description

Given a set of arbitrarily aligned planar cross-section of a 3D-object, the target of this project is to reconstruct an interpolating surface, or a 3D multi-labeled mesh. This project will be based on a basic version of the paper Online Reconstruction of 3D Objects from Arbitrary Cross-Sections by Bermano et al., and several other mild variants will be explored (such as the use of different coordinates).
The project will be performed in these two major steps:

Required skills:Strong C++, some knowledge of computational geometry and geometric processing.

Enhancing the Landmarks point-location strategy for 2D arrangements

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

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. The 2D Arrangements package supports different strategies of point location. Here, you are asked to enhance the implementation of a specific strategy called Landmarks.

Required skills:C++, Generic Programming

External project related to CGAL

In case you are looking for more project ideas related to CGAL, here is a link to a CGAL related project from Scilab.



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.