Sébastien TOURNEUX: Analyse morphologique d’objets 3D : identification de propriétés structurantes

De Ensiwiki
Aller à : navigation, rechercher
Cornues.png
Titre du projet Analyse morphologique d’objets 3D : identification de propriétés structurantes
Cadre IRL

Labo LJK [1] / INRIA [2]
Équipe IMAGINE [3]
Encadrants Jean-Claude Léon et Damien Rohmer

Étudiant

Sébastien Tourneux, 2A MMIS.

Problème

Contexte

Lors d'échanges de fichiers décrivant un objet manufacturé (généré par des logiciels de CAO comme Catia ou Solidworks), les informations de construction de l'objet sont perdues. Ainsi, il est impossible à l'utilisateur de corriger des imprécisions de paramétrage, à moins de reconstruire l'objet totalement. C'est pourquoi il est utile d'analyser l'objet pour dégager un graphe de construction [1] qui décrit les différents processus de construction possible d'un objet. Il est alors intéressant d'inclure des répétitions à ce graphe de construction, dans le cas où l'utilisateur voudrait agir sur un paramètre comme le pas de la répétition.

Sujet

On se propose d'étudier les répétitions linéaires ou circulaires d'éléments d'un objet CAO.

Exemple d'objet manufacturé et configurations linéaires (en vert) et circulaires (en rose) à détecter sur la face avant

La détection des répétitions devra être réalisée à la précision du modeleur (un millième de millimètre pour Catia).

Travail préliminaire

On considère qu'une répétition est contenue dans une seule face. Dans le plan de la face, on extrait un nuage de points-clés à partir des éléments de l'objet (l'intersection de l'axe d'un perçage et du plan de la face est un point-clé par exemple). On travaille ensuite à la détection de symétrie sur ce nuage de points.

Approches rejetées

  • Force brute : la combinatoire serait trop grande (la complexité est exponentielle en le nombre de points)
  • Transformée de Hough [4] : cette méthode est utilisée en vision par ordinateur sur des images discrètes pour détecter notamment des droites et des cercles dans l'image. Elle n'est pas applicable à notre problème à cause de la précision recherchée (la méthode nécessiterait une image de taille 10^{12}, impossible à traiter).

Détection par triangulation

Les fonctions des logiciels de CAO qui génèrent des répétitions produisent des éléments qui sont souvent plus proches voisins les un des autres. On propose alors d'utiliser une triangulation de Delaunay qui traduit cette information de proximité entre les points.

Triangulation de Delaunay et diagramme de Voronoï

On peut détecter des alignements en examinant les colinéarités des arêtes de la triangulation.
Une co-circularité est traduite par un site de Voronoï de grand degré (\geq 4).

La triangulation de Delaunay est une triangulation qui évite au maximum de générer des triangles aplatis. Le diagramme de Voronoï est son graphe dual.La cellule de Voronoï d'un point p_i de notre ensemble de point E est l'ensemble des points qui sont les plus proches de p_i que de tous les autres points de l'ensemble E.

Propriété de convexité

La triangulation de Delaunay est un convexe. Si une configuration est détectée sur la limite de la triangulation, alors la configuration est maximale (en terme de nombre de points contenus). On peut alors supprimer les points de la configuration détectée et re-trianguler le nouvel ensemble pour chercher de nouvelles configurations sur la limite.

Algorithme de Bowyer-Watson

Ce algorithme génère une triangulation de Delaunay. Il insère un à un les points à trianguler dans un sous-ensemble de points déjà triangulé. Nous avons modifié l'algorithme pour examiner l'apparition de configuration à chaque insertion :

  • co-circularité : à chaque insertion, l'algorithme originel vérifie la position du point inséré par rapport au cercle circonscrit à chauqe triangle, cela permet de détecter des configurations circulaires.
  • alignements : à chaque insertion, et pour chaque nouvelle arête créée, on parcourt les arêtes déjà existantes en recherchant une colinéarité

La complexité de cet algorithme est quadratique en le nombre de points.

Résultats

Ces méthodes nous permettent de détecter des configurations complexes où des points appartiennent à plusieurs configurations différentes ou dans des configurations à plusieurs direction de répétition.

Perspectives

  • L'intégration des répétitions au graphe de construction pourrait permettre un contrôle plus important à l'utilisateur
  • La transformée de Hough peut être utilisée à faible résolution pour préciser un sous-ensemble de points à étudier
  • On pourrait généraliser cette méthode de détection aux maillages facettisés ("mesh"). Un important travail préliminaire serait alors nécessaire pour dégager les points clés à partir de groupes de facettes.
  • On pourrait étendre la détection à un plus haut niveau : détecter des répétitions de répétitions par exemple


Références

[1] Jean-Claude Léon, Flavien Boussuge, Stefanie Hahmann, Lionel Fine, et al. Décomposition d’un objet numérique 3D sous la forme de primitives et d’un graphe de construction [5], 2013

Annexe