Master level project proposal: Robust Predicates for Mesh Generation - Symbolic Perturbation

Contact: Bruno Lévy and This e-mail address is being protected from spambots. You need JavaScript enabled to view it (joint project between ALICE and VEGAS)

General presentation

This project takes place in the frame of the ERC starting grant GOODSHAPE, on optimal sampling and mesh generation. Given a 3D shape, the optimal sampling problem consists in positioning a set of points inside the shape in a way that minimizes the so-called quantization noise power [DFG99]. In the frame of project GOODSHAPE, we proved the continuity of the objective function and proposed several generalizations [LY10].Minimizing the quantization noise power requires to accurately construct some geometric structures (restricted Voronoi diagram and clipped Voronoi diagram, depicted in the figure). The computation of these structures depends on some elementary functions, called geometric predicates, that analyse the relative locations of some points. In order to ensure that the combinatorics are consistent, these functions need to be resistant to degeneracies, such as a point that is exactly located on a plane. The goal of this research project is to define a symbolic perturbation scheme, that will consistently handle these degeneracies [EM90].The overall idea is to perturb each point’s coordinate with a function, and study the sign of the first non-zero coefficients of the Taylor expansion.

Goals of the training period

The main goal of this project is to define the predicates involved in the computation of the Restricted Voronoi Diagram together with a symbolic perturbation scheme that will ensure that all degeneracies are properly handled. The project

is articulated into the following phases:

• Study the definition of the Restricted Voronoi Diagram, the algorithm to compute it, and the predicate involved in this algorithm [LY10]. The predicate corresponds to the position of a point p relative to a plane Π. The plane Π is the bisector of two points, and the point p is defined as the intersection between three planes ;

• Study the definition of symbolic perturbations, as introduced in [EM90]. In the initial paper, symbolic perturbations can be applied to determinants. In our case, a richer algebra needs to be introduced, in order to be able to process a point p that is not directly given (but defined as an intersection) ;

• (Optional) implement the three forms of the predicate in C++, and test it on degenerate cases.

Requires skills

Taste for both mathematics and programming. Enthusiasm is a must!

Possible continuation

There are several possibilities for continuing this work as a Ph.D., in the frame of project GOODSHAPE.

References

[EM90] Herbert Edelsbrunner and Ernst Peter Mucke. Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithms, ACM Transactions on Graphics, 1990.

[DFG99] Qiang Du, Vance Faber and Max Gunzburger. Centroidal Voronoi Tesselations: Applications and Algorithms SIAM review, 1999

[LY10] Bruno Lévy and Yang Liu. Lp Centroidal Voronoi Tesselation and its Applications, ACM Transactions on Graphics - SIGGRAPH conf. proc., 2010.

Link: Geometry processing in ALICE

Link: The proposal in PDF