CGAL Projects page for the Google Summer of Code 2014

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

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

Summary:

First section to read: Information Candidates Should Supply

1. Use Embree for Ray Shooting
2. Adding Better I/O for the CGAL Library
3. Fixes to the 2D Arrangements Package
4. Support for Qt5
5. Adding a Parallel Version of the Edge Simplification Algorithm
6. Enhancing the Upcoming Visibility Package
7. Implementing a Shortest Path on Polyhedron Algorithm
8. Intersection of Half-Spaces and Computation of the Voronoi-covariance Measure of a Point Set
9. Finalization of the Implementation of a 2D Reconstruction and Simplification Algorithm from Point Set
10. BGL for Combinatorial Maps and Linear Cell Complex
11. Enhancing the Plane-Sweep Framework for Arrangements
12. Adding a package for constructing exact Yao graphs to CGAL

Use Embree for Ray Shooting

Mentor(s): from GeometryFactory

Project description:

The Embree project has a low level API for ray shooting queries. First benchmarks show that Embree is faster than the CGAL AABB Tree. This is partially due to the use of vector operations. The goal of this GSoC project is twofold. First, we want to allow to use Embree, for example in the mesh generator. Second the student should introduce vector operations in the AABB Tree.

Required Skills: parallel vector operations, C++ templates

Adding Better I/O for the CGAL Library

Mentor(s): from GeometryFactory

Project description:

The goal of this project is to add some wrapper to allow CGAL to read/write different classical input files.

The obvious things we see that is missing are:

• vtk data structures (unstructured grids, poly data, ...)
• MRI file formats for the meshing algorithms: Nifti (.nifti), Gis (.img, .hdr), vtk
• GIS file formats (WKT, GML, GeoJSON, ...)

The goal is not necessarily to re-implement these readers/writers but rely on existing software with a license compatible with CGAL

Required Skills: vtk, C++ templates, cmake

Fixes to the 2D Arrangements Package

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

Project description:

Fix and enhance various small features in the 2D Arrangements package:

• Implement Naive Ray Shooting.
• Fix all point location strategies to work with all traits class.
• Fix the demo to support polylines and enhance it to support the algebraic traits.
• Replace CGAL::Object with boost::variant
• Augment the polyline traits.

Required Skills: Qt4, C++ templates

Support for Qt5

Mentor(s): from GeometryFactory and from (CNRS/Université de Lyon)

Project description:

In short: Add support for Qt5 and keep the support for Qt4 in CGAL demos.

CGAL has a support for Qt4, and all its demos are written using Qt4 (without the Qt3Support module). Now that Qt5 is released (and even at version 5.2), it is time to support that new version. The objective of this project is to design the code of the CGAL Graphics View package, and CGAL demos, so that they can be compiled both with Qt4 and Qt5. The CMake scripts will also have to be adapted so that they can use either Qt4 or Qt5.

Required Skills: C++, Qt4, Qt5, CMake

Adding a Parallel Version of the Edge Simplification Algorithm

Mentor(s): from GeometryFactory and from Inria Sophia-Antipolis

Project description:

CGAL has a triangulated surface mesh edge simplification package based on the paper

The goal of this project is to use a modified version of this algorithm to allow edges of a mesh to be simplified using parallel threads.

Required Skills: C++, Intel TBB

Enhancing the Upcoming Visibility Package

Mentor(s): from TU Braunschweig

Project description:

During GSoC 2013 we started a package for visibility computation within 2D polygons. The goal of this project is to enhance the currently implemented algorithms (see Efficient Computation of Visibility Polygons; EuroCG'14; Francisc Bungiu, Michael Hemmer, John Hershberger, Kan Huang and Alexander Kröller. Specifically, the triangular expansion algorithm should be parallelized.

Required Skills: C++, Intel TBB

Implementing a Shortest Path on Polyhedron Algorithm

Mentor(s): from GeometryFactory and Éric Colin de Verdière from ENS

Project description:

The goal of this project is to implement the following shortest path algorithm into CGAL:

The implementation can be limited to manifold surface and must use the Boost Graph Library extension of CGAL. If time allows an extension of this work could be the implementation of the intrinsic Voronoi diagram.

Required Skills: Computational Geometry, C++, Template programming

Intersection of Half-Spaces and Computation of the Voronoi-covariance Measure of a Point Set

Mentor(s): from CNRS/University of Grenoble and from GeometryFactory

Project description:

The first goal of this project is to implement a robust intersection of a set of half-space. Several methods might be implemented as efficiency is very important.

The second goal is to use this primitive to implement the Voronoi-covariance measure of a point set, which can be used for robust estimation of geometric quantities from point clouds (eg. normal, sharp features, etc.).
More details are provided in the following paper:

Required Skills: Notions of Computational Geometry, C++, Generic Programming

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

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:

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

BGL for Combinatorial Maps and Linear Cell Complex

Mentor(s): from (CNRS/Université de Lyon) and from GeometryFactory

Project description:

This project consists in developing the traits class allowing to use Combinatorial map and Linear cell complex data structures as model of Boost Graph Concept.

The new traits class will be developed by taking the similar existing class for Halfedge_data_structure and Polyhedron_3 (which are very similar than Combinatorial map and Linear cell complex of dimension 2). Validation of the class will be done through tests using existing geometrical algorithms in CGAL defined on the Boost Graph Concept, such as the Triangulated Surface Mesh Simplification package for example.

Required Skills: Generic Programming, C++, Boost.

Enhancing the Plane-Sweep Framework for Arrangements

Mentor(s): from the Applied Computational Geometry Lab, Tel Aviv University and from TU Braunschweig

Project description:

Expose the plane-sweep class-template of the 2D Arrangements package to the public, so that other users can implement their own concrete algorithms. This requires revisiting the visitor concept, improving the code so that there is a clear distinction between code that requires exact construction and code that does not, implementing tests, developing additional examples, and writing the appropriate documentation.

Required Skills: Generic Programming, C++, Sweep-line framework.

Adding a package for constructing exact Yao graphs to CGAL

Mentor(s): from TU Braunschweig and from University of Western Sydney

Project description:

The goal of this project is to add a package for constructing exact Yao graphs to CGAL. The definition of the Yao graph is simple: given a set of points S on the plane and an integer k, each point in S divides the plane into k equally-angled cones of angle 2Pi/k and establishes an edge to its closest neighbor in each cone. The algorithm used to construct Yao graph in this project will be a sweep-line algorithm similar to the famous Fortune's algorithm for constructing Voronoi Diagrams. The challenging part is that the code should be written such that it is optional whether the constructed graph is the exact one, that is, without mistakes due to rounding errors. This is not trivial since the rays subdividing the cones are defined over algebraic extension fields what depend on the chosen k.

Required Skills: Generic Programming, C++, Sweep-line framework.

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 containing the above items.