Complexe cellulaire régulier 3D et diagrammes de Voronoï dans CGAL

3D regular cellular complex and Voronoi diagrams in CGAL

Contact : Monique Teillaud, <Monique(dot)Teillaud(at)sophia.inria.fr>

La bibliothèque CGAL (Computational Geometry Algorithms Library) propose deux types de structures combinatoires permettant de représenter une subdivision du plan: une structure pour les subdivisions triangulaires ainsi qu'une structure plus générale du type DCEL (doubly connected edge list, ou encore "arêtes ailées"). Cette deuxième structure est codée sous la forme d'une structure en demi-arêtes. En dimension 3, CGAL n'offre qu'une structure de subdivision tétraédrique de l'espace, et pas de structure permettant de stocker une subdivision polyédrique générale. L'objectif du stage est la réalisation d'un module CGAL offrant une telle structure. Un premier stage (2 mois, Master 1) a eu lieu en 2007. Ce stage a abouti à la programmation d'une structure de subdivision spatiale en 3D, réutilisant et généralisant la structure Halfedge Data Structures de CGAL. Seules les ``couches basses'' de cette structure ont pu être mises en place (et documentées). Ce travail a été présenté au 24th European Workshop on Computational Geometry en mars 2008: Antoine Bru and Monique Teillaud, Generic implementation of a data structure for 3D regular complexes. Ce stage consistera à : - concevoir les spécifications de la couche supérieure constituant l'interface de cette structure, - coder cette couche, - la documenter, - approfondir l'état de l'art (voir article ci-dessus), - si le temps le permet, coder, en suivant cette même interface, une classe pour les diagrammes de Voronoï 3d, basée sur le module de Triangulations 3D de CGAL, sur le modèle du module diagramme de Voronoï 2D. La gestion des cas dégénérés (points cosphériques) sera particulièrement intéressante et utile.

The Computational Geometry Algorithms Library CGAL proposes two types of combinatorial structures to represent a planar subdivision: a structure for triangular subdivisions and a more general DCEL structure DCEL (doubly connected edge list), ou encore "arêtes ailées"), coded as a halfedge data structure. In 3D, CGAL offers only a structure for tetrahedral subdivision. The goal of the work is to realize a CGAL package for more general polyhedral subdivision. A first prototype is already available, reusing and extending the CGAL Halfedge Data Structure. But only its low layers have been coded and documented: Antoine Bru and Monique Teillaud, Generic implementation of a data structure for 3D regular complexes, European workshop on computational geometry, EuroCG, march 2008. More precisely, the work will consist in: - working on the state-of-the-art, - designing the specifications of the higher layer, that will be the user interface of the structure, - coding this higher layer, - documenting it, - following the same interface, code a class for 3D Voronoï diagram, based on the CGAL 3D Triangulations. Handling degenerate cases (cospherical points) will be particularly useful and interesting, in a similar ay as done in the CGAL 2D Voronoi diagrams.

Pour en savoir plus sur :
Site du Projet Open Source
Transparents d'Introduction

Quelques références :
Antoine Bru and Monique Teillaud, Generic implementation of a data structure for 3D regular complexes, EuroCG'08
L. Kettner. Using generic programming for designing a data structure for polyhedral surfaces, Comput. Geom. Theory Appl., 13:65-90, 1999
F. Preparata and M. Shamos, Computational geometry: An Introduction, Springer-verlag, 1995
E. Brisson, Representing Geometric Structures in d Dimensions: Topology and Order, Discrete Comput. Geom., vol 9, pp 387--426, 1993
P. Lienhardt, N-Dimensional Generalized Combinatorial Maps and Cellular Quasi-Manifolds, Internat. J. Comput. Geom. Appl., vol 4, pp 275--324, 1994
Y. Bertrand and J.-F. Dufourd, Algebraic specification of a 3D-Modeler Based on Hypermaps, CVGIP: Graph. Models Image Process., vol 56, pp 29--60, 1994
B. Lévy, G. Caumon, S. Conreaux and X. Cavin, Circular Incident Edge Lists: a Data Structure for Rendering Complex Unstructured Grids, IEEE Visualization, 2001

Prérequis :
- très bon niveau en C++,
- bonnes connaissances d'algorithmique de base,
- goût pour le code de bonne qualité,
- goût pour les aspects mathématiques, et la combinatoire et la géométrie en particulier.