CGAL Projects for Google Summer of Code 2012

Accepted Projects

As in 2010 and 2011, the CGAL Project was a mentoring organization of the Google Summer of Code in 2012. Successful projects can be found here.

Project Ideas

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

• Switch current demo to a non-flash version;
• Add interface to input surfaces and to output a triangulation in 3D (using some TDS from CGAL) - TDS is chosen to support pick'n'highlight for ''vertices''/''edges''/shells/''volumes'';
• Construct triangulation from surface analysis output;
• Provide refinement operator for zooming;

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:

• Demonstrate all geometric traits classes.
• Demonstrate arrangements of unbounded curves (with several unbounded faces).
• Demonstrate the overlay operation.

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:

• Filling holes in meshes, Liepa, P., Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 200-205, 2003

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:

• Consistent mesh partitioning and skeletonisation using the shape diameter function, Shapira, L. and Shamir, A. and Cohen-Or, D., The Visual Computer, 24,4,p. 249-259, 2008, Springer

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:

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

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:

• intersections with batched queries (set of primitives as queries).
• distance with batched point queries and exploit spatial coherencies of point set query.
• sphere range query (returns all primitive within distance from point query or batched point queries).
• intersection with tree query to find all intersecting primitives.
• add possibility to use boost::apply_visitor or other call back frunction when an intersection occurs (traversal functor exists but a visitor may be easier to customize).
• add possibilities to dynamically activate or disactivate some primitives of the tree.
• perform accelerations through profiling, reduction of cache misses.

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.

• extend the existing plug-in interfaces and support library to be more convenient for users and more tailored to CGAL use-cases
  • reusable selection mechanisms for primitives
  • specialized rendering for geometric objects (feature highlighting)
• smooth out the user interface
• write and improve essential demos
  • Polyhedron package
  • Mesh_3 package
• improve the capabilities to interactively inspect geometric objects for debugging

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:

• Implement 3D planar arrangements, using the 2D arrangement package.
• Implement an oracle for the 3D mesh generation package which creates a mesh from the data given on the planes.

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.