Largeur locale (local feature size) d'un ensemble de contraintes

Lieu :

INRIA , Unité de Sophia Antipolis
Projet PRISME
BP 93
06902 Sophia Antipolis
FRANCE

Information:

Mariette Yvinec - Chargée de recherche Projet Prisme Tel : +33 4 92 38 77 49 e-mail: <Mariette.Yvinec@sophia.inria.fr>

Description:

Le travail proposé s'inscrit dans le cadre général du problème de la génération automatique de triangulations et de maillages. Dans ce contexte, les données sont constituées par un complexe linéaire par morceaux ( PLC ou piecewise linear complex) c'est à dire un ensemble de faces (facettes, d'arêtes et sommets) qui constituent les contraintes. Le but est alors de construire une partition simpliciale de l'espace qui respecte les contraintes. Les contraintes sont considérées comme respectées lorsque chacune d'entre elle apparait comme une union de faces de la partition. La partition construite s'appelle un maillage ou une triangulation selon que l'on impose ou non des conditions additionnelles sur la forme et la taille des éléments.

En dimension 3, un PLC ne peut généralement pas être triangulé sans ajouter de sommets aux sommets des contraintes et le but est d'en ajouter le moins possible. Une solution consiste à construire une triangulation conforme c'est à dire un ensemble de points dont la triangulation de Delaunay respecte les contraintes. Une autre solution consiste à construire un ensemble de points plus restreint dont la triangulation de Delaunay respecte seulement les arêtes des contraintes ce qui garantit l'existence d'une triangulation (Delaunay contrainte mais pas nécessairement Delaunay) respectant les contraintes.

Les algorithmes les plus efficaces proposés récemment pour résoudre les problèmes de triangulation conforme s'adaptent à la géométrie locale des contraintes. Ils reposent sur la notion de largeur locale (local feature size) d'un ensemble de contraintes et la possibilité de pouvoir évaluer efficacement ce paramètre en divers point de l'espace. Etant donné un PLC décrivant les contraintes et un point x de l'espace, situé ou non sur une face du PLC, on appelle largeur locale en x et on note lfs(x) (pour least feature size) le rayon de la boule minimale centrée en x intersectant deux faces non incidentes du PLC.

Largeur locale : examples en 2d

Le travail proposé dans ce stage consiste à proposer, implanter et comparer diverses structures de données permettant d'évaluer efficacement la largeur locale d'un ensemble de contraintes en divers points de l'espace. L'une des structures que l'on peut envisager consiste à utiliser la triangulation de Delaunay des sommets de contraintes qui doit être calculée de toute façon. Les portions de contraintes qui ne sont pas présentes dans cette triangulation pourront être stockées dans les cellules qu'elles traversent. Une autre solution consiste à utiliser des structures plus généralistes de type octree.

Mots clefs :

Géométrie Algorithmique, Triangulations, Triangulation conformes, Triangulations contraintes, Maillages, local feature size,

Outils :

Stations de travail SUN Solaris ou PC Linux,
langage C++,
Bibliothèque géométrique CGAL

Bibliographie :

• A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation, J. Ruppert, J. Algorithms, 18, 548--598, 1995.
• Conforming {Delaunay} Triangulations in 3D, David Cohen-Steiner, Eric Colin de Verdière et Mariette Yvinec Proc. 18th Annu. ACM Sympos. Comput. Geom, 2002