Mon projet de recherche doctoral

Je suis A.T.E.R. dans l'équipe Informatique Géométrique et Graphique du Laboratoire des Sciences de l'Image, de l'Informatique et de la Télédétection.

Accès direct: mon mémoire

Résumé

Le sujet de mon projet de recherche doctoral était « Décomposition et paramétrisation de systèmes de contraintes géométriques sous-contraints ».

L'axe de recherche était une extension des travaux de Pascal Schreck et Pascal Mathis, qui concernent la généralisation de la notion de « bonne constriction » par la considération de groupes de transformations géométriques qui sont des composés d'une translation, d'une rotation et d'une homothétie.

Mes travaux ont eu pour objectif de permettre la mise au point de logiciels de modélisation par contrainte accessibles à des utilisateurs non experts. Ils ont pour cela visé à établir une paramétrisation d'un système de contraintes géométriques en fournissant une liste des éléments géométriques à fixer, combinée à une décomposition du système en une liste de sous-systèmes associés aux différentes parties de la paramétrisation. Ainsi, l'utilisateur peut obtenir un retour visuel intuitif sur le degré de déformabilité de l'objet qu'il a décrit.

Contexte des travaux

Système de contraintes géométriques

La résolution d'un système de contraintes géométriques consiste à trouver toutes les figures (solutions) satisfaisant des contraintes (e.g. distances entre points, angles entre droites, tangences) données par l'utilisateur. Les solutions sont décrites soit par les coordonnées des entités géométriques (points, droites, cercles, etc.) les composant, soit par un plan de construction des figures qui permettra de retrouver les coordonnées. Les principaux domaines d'application sont d'une part la Conception Assistée par Ordinateur (CAO), où les systèmes de contraintes sont données sous la forme de dessins côtés et d'autre part les Environnements Interactifs d'Apprentissage avec Ordinateur (EIAO), où ces systèmes sont décrits par un énoncé textuel.

Exemple d'esquisse côtée Exemple de figure solution

Exemple d'esquisse côtée (les valeurs des paramètres ne sont pas affichées) et une figure solution

Formellement, un système de contraintes géométriques (angl. GCS: Geometric Constraint System) dans un univers géométrique U est un triplet S = (C, X, A) avec

Une solution d'un système est une valuation des inconnues, c'est-à-dire une application de X vers U, telle que les interprétations de tous les termes de C dans U sont valides. On appelle espace des solutions l'ensemble des solutions d'un GCS.

Le problème de la sous-constriction

L'un des principaux problèmes de la résolution de GCS vient de la possibilité que le système soit mal contraint. On considère généralement trois degrés de constriction:

La plupart des solveurs de contraintes géométriques considèrent des systèmes de contraintes bien contraints et de nombreuses propriétés importantes de ces solveurs ne sont démontrées que sous l'hypothèse de la bonne constriction du système à résoudre. La détermination du degré de constriction d'un GCS est donc un thème de recherche important.
Dans le cas des systèmes sur-contraints, les recherches déjà effectuées visent généralement la détection du plus petit sous-système inconsistant afin que l'utilisateur voie rapidement pourquoi son système est sur-contraint.

Exemple de système structurellement sur-contraint

Exemple de système structurellement sur-contraint: selon les valeurs des contraintes, il peut n'y avoir aucune solution

Dans le cas des systèmes sous-contraints, on distingue principalement deux approches: la première consiste simplement à détecter la sous-constriction, pour ensuite laisser l'utilisateur résoudre le problème. La seconde consiste à ajouter des contraintes paramétrées qui permettent de revenir à la bonne constriction du système, et à laisser l'utilisateur choisir la valeur du paramètre.

Le problème de la première approche est évident: on demande à un utilisateur d'étudier son système manuellement afin de trouver l'erreur. Or l'utilisateur est souvent un architecte ou un concepteur mécanicien, pas un spécialiste de la résolution de contraintes. Le problème de la deuxième approche est double: d'une part, la contrainte paramétrée qu'on a ajoutée n'a pas forcément un «sens» pour l'utilisateur (pourquoi cette contrainte et pas une autre ?) ce qui lui rendra parfois la tâche difficile quand il devra donner une valeur au paramètre. D'autre part, il n'existe pas à l'heure actuelle de méthode complète pour trouver quelle contrainte ajouter.

Exemple de système sous-contraint

Exemple de système sous-contraint: l'angle entre les deux «barres» peut varier, il y a une infinité de solutions

La définition de la sous-constriction donnée plus haut pose un problème supplémentaire: prenons le cas d'un triangle dont les longueurs des trois côtés sont connues. Du point de vue de l'utilisateur, il n'y a que deux solutions, symétriques l'une de l'autre.
Toutefois, formellement, puisqu'une solution est donnée par les coordonnées des entités et dans la mesure où les contraintes de distance ne positionnent pas la figure par rapport au repère considéré, il y a une infinité de solutions. Le système, bien que rigide, est donc sous-contraint !

Trois solutions d'un système rigide

Trois solutions parmi l'infinité des solutions d'un système représentant un triangle rigide

Approche multi-groupes

L'approche multi-groupes provient des travaux de Pascal Mathis et Pascal Schreck (voir notamment Schreck, Mathis, Geometrical constraint system decomposition: a multi-group approach, International Journal of Computational Geometry and Applications, 16(5-6):431-442, 2006). Partant du constat exposé ci-dessus, l'approche multi-groupes consiste à généraliser la notion de bonne constriction par l'expression d'un groupe d'invariance. Les groupes de transformations considérés jusqu'à maintenant, les groupes à action locale sont toutes les composées des trois groupes classiques suivants:

On citera notamment les déplacements (translation + rotation) et les similitudes (déplacement + homothétie).

Un système de contraintes géométriques S est dit invariant par un groupe G si pour toute solution s de S et pour toute transformation f de G, f(s) est une solution de S. On appelle orbite de s pour G l'ensemble des solutions s' tels qu'il existe f dans G avec f(s) = s' et s est un représentant de cette orbite.

Quand il existe un nombre fini d'orbites pour G qui forment une partition de l'ensemble des solutions, on dit que le système est bien contraint modulo G. Autrement dit, si à partir d'un nombre fini de solutions, on peut générer n'importe quelle solution en appliquant une transformation de G, le système est dit G-bien-contraint.

L'expression du plus grand groupe d'invariance d'un système généralise la notion de bonne constriction. Le système du triangle ci-dessus est ainsi considéré comme bien contraint modulo les déplacements, puisqu'il suffit de deux solutions, symétriques l'une de l'autre, pour générer tout l'espace des solutions par application des déplacements. Un triangle contraint par deux angles et aucune distance est bien contraint modulo les similitudes.

Deux représentants du triangle contraint par trois distances

Deux représentants des solutions du triangle contraint par trois distances. Les autres peuvent être retrouvées par application des déplacements.

Repères

Si un système est G-bien contraint (i.e. bien contraint modulo le groupe G), on peut se poser la question des contraintes qu'il convient d'ajouter afin qu'il devienne bien contraint modulo l'identité, c'est-à-dire afin qu'il n'aie réellement qu'un nombre fini non nul de solutions.

Cette notion a été formalisée par celle de repères. Un repère pour le groupe G (noté G-repère) est un ensemble d'entités géométriques qui, si elles sont fixées dans l'espace, permettent d'assurer la finitude du nombre de solutions.

Par exemple, dans le cas des déplacements planaires, un D-repère est un point et une direction à partir de ce point. Si ces éléments sont fixés, il n'y a que deux solutions, qui sont symétriques l'une de l'autre. L'adjonction d'une notion d'orientation permet de revenir à une solution unique. Pour les similitudes planaires, un S-repère consiste en deux points.

Deux solutions particulières et les repères correspondants

Deux solutions particulières du triangle contraint par trois distances définies par leur repère (en rouge)

Les travaux de Pascal Mathis et Pascal Schreck ont permis de montrer qu'il y avait bijection entre groupe de bonne constriction et repère: si en fixant un point et une direction dans un système on ne dispose plus que d'un nombre fini non nul de solutions, alors ce système est D-bien contraint.

Assemblage

Les repères jouent un rôle essentiel dans les travaux de l'équipe, car ils permettent de définir une condition nécessaire et suffisante pour que deux système de contraintes soient assemblés: si deux systèmes G-bien contraints partagent un G-repère, alors on est capable de transformer la solution de l'un pour qu'elle soit cohérente avec la solution de l'autre.

Par exemple, si deux triangles contraints par les distances de leurs trois côtés partagent un point et une direction, alors en fixant un repère pour le premier triangle, on fixe les trois points de ce triangle. Le point partagé par le second triangle est donc également fixé, ainsi que la direction qu'ils partagent. Le second triangle a donc d'ores et déjà un point et une direction de fixés, le nombre de solutions est fini non nul.

Comme on l'a vu, la bijection entre repères et groupe de bonne constriction entraîne que le système composé des deux triangles est D-bien contraint: on a fixé un point et une direction et obtenu que l'ensemble du système a un nombre de solutions fini non nul.

Si deux G-systèmes partagent moins qu'un G-repère, ils ne peuvent être assemblés en un unique G-système. S'ils partagent plus qu'un G-repère, il y a sur-contrainte.

Bord

Une notion importante pour la décomposition de systèmes de contraintes géométriques, c'est-à-dire pour le calcul des solutions d'un système par son découpage en sous-systèmes et par assemblage des solutions des sous-systèmes, est celle de bord

Dans un système S, le bord d'un sous-système S1 par rapport à S2 = S - S1 est l'ensemble des informations géométriques que l'on peut calculer dans S1 à propos des éléments géoémétriques communs à S1 et à S2. Ainsi, par exemple, si S1 est un sous-système rigide, il sera possible de calculer:

Des sous-systèmes du bord peuvent permettre de générer le bord. Il est ainsi possible de montrer par exemple que, si un système planaire ne contenant que des points et des droites est bien-contraint modulo les déplacements, la connaissance de l'ensemble des distances entre deux points, des angles entre deux droites et des distances point-droite permet de calculer l'ensemble des autres informations. On appelle base du bord un système minimal permettant de calculer toutes les informations du bord.

Mes travaux

Mes travaux ont abordé trois aspects complémentaires de la résolution de systèmes de contraintes géométriques:

Démonstration du bien-fondé des méthodes de décomposition

Paramétrisation de systèmes de contraintes géométriques sous-contraints

Décomposition de systèmes de contraintes géométriques

Références


Valid XHTML 1.1 Valid CSS!