Projet Open Source
Introduction à
Contact : Monique Teillaud
<Monique(dot)Teillaud(at)sophia.inria.fr>
La bibliothèque CGAL 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 (voir le chapitre Halfedge
Data Structures du manuel CGAL pour une définition complète).
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.
Ce stage consistera à :
- coder pour CGAL une structure simple de subdivision spatiale en
3D, réutilisant et généralisant la structure Halfedge
Data Structures,
- si le temps le permet, coder, en utilisant cette nouvelle
structure 3d, 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.
Quelques références :
F. Preparata and M. Shamos, Computational geometry: An Introduction,
Springer-verlag, 1995
L. Kettner. Using generic programming for designing a data structure
for polyhedral surfaces, Comput. Geom. Theory Appl.,
13:65-90, 1999
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
Pour en savoir plus sur CGAL :
Projet Open Source
Introduction à
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.