Brevet FR2906388A1 — publié le 20080328

La présente invention a pour objet un procédé et un dispositif de détection de collision et de construction et de visualisation d'informations géométriques de contact, et plus généralement de proximité entre un nombre fini d'objets simulés numériquement, c'est-à-dire d'objets virtuels. On a déjà proposé dans le brevet US 6 862 026 (document [9]) un procédé de détection de collision entre objets virtuels basé sur la construction de boîtes comprenant les objets à considérer, en fonction du déplacement souhaité. Ce procédé de l'art antérieur consiste à vérifier la superposition des boîtes contenant les deux objets, et le cas échéant à subdiviser chaque boîte en deux boîtes plus petites. Une optimisation est effectuée en utilisant des boîtes dont les axes sont alignés sur les axes de l'un des objets. Ce procédé n'utilise pas de distance entre objets. On connaît par ailleurs par le document de référence [1] un procédé de détermination de distances minimales locales entre des objets polyédriques volumiques représentés par une triangulation de leur frontière en dimension 3, mais ce procédé est explicité en relation avec certaines applications particulières et implique des calculs relativement longs qui ne sont pas adaptés au cas de la simulation en temps réel. La présente invention vise à remédier aux inconvénients précités et à permettre de réaliser plus facilement la détection des collisions ou la construction des informations géométriques de contact ou de proximité entre un nombre fini d'objets simulés numériquement, en optimisant la vitesse de traitement et en fournissant des solutions très robustes vis-à-vis des déplacements et des rotations des objets virtuels, afin notamment de ne pas déstabiliser le rendu graphique ou haptique par suite d'une interaction avec l'utilisateur qui est par nature peu prévisible. Ces buts sont atteints grâce à un procédé de détection de collision et de construction d'informations géométriques de contact et de proximité entre au moins un premier objet polyédrique simulé numériquement et au moins un deuxième objet polyédrique simulé numériquement, 2906388 2 caractérisé en ce que l'on représente les premier et deuxième objets polyédriques simulés numériquement sous la forme de complexes simpliciaux dans Rn, où Rn désigne le produit cartésien du corps des réels n fois par lui-même, avec n égal à 2 ou à 3, 5 en ce que l'on effectue une étape de prétraitement pour chaque complexe simplicial dont les coordonnées des sommets sont données dans un système de coordonnées fixé, en ce que ce prétraitement consiste au moins à calculer pour chaque face de chaque complexe simplicial une description géométrique 10 du cône polyédrique correspondant aux normales au sens fort associées à cette face, à déterminer le label de la classe de contact à laquelle appartient cette face et à déterminer pour chaque complexe simplicial un arbre de volumes englobants de l'objet du complexe simplicial à partir à la fois de la position des faces du complexe simplicial et des ensembles de 15 normales au sens fort associées, et en ce que, à partir des informations obtenues à l'issue de l'étape de prétraitement, on procède à un calcul de distances minimales locales et de quasi-distances minimales locales, ces dernières correspondant chacune à un couple de points appartenant respectivement 20 à des objets distincts et qui définiraient une distance minimale locale si la position d'un objet par rapport à l'autre subissait une rotation d'un angle faible inférieur à un seuil donné. Ce procédé est applicable au cas d'objets polyédriques simulés numériquement qui peuvent être aussi bien rigides que déformables. 25 Les étapes de prétraitement et de calcul des distances minimales locales (LMD) et des quasi-distances minimales locales (quasi LMD) peuvent être effectuées en temps réel. L'invention concerne également un dispositif de détection de collision et de construction d'informations géométriques de contact et de 30 proximité entre au moins un premier objet polyédrique simulé numériquement et au moins un deuxième objet polyédrique simulé numériquement, caractérisé en ce qu'il comprend des moyens pour représenter les premier et deuxième objets polyédriques simulés numériquement (10, 35 20) sous la forme de complexes simpliciaux dans Rn, où Rn désigne le 2906388 3 produit cartésien du corps des réels n fois par lui-même, avec n égal à 2 ou à 3, en ce qu'il comprend des moyens de prétraitement pour chaque complexe simplicial dont les coordonnées des sommets sont données dans 5 un système de coordonnées fixé, en ce que ces moyens de prétraitement comprennent au moins des moyens de calcul pour chaque face de chaque complexe simplicial d'une description géométrique du cône polyédrique correspondant aux normales au sens fort associées à cette face, des moyens de 10 détermination du label de la classe de contact à laquelle appartient cette face et des moyens de détermination pour chaque complexe simplicial d'un arbre de volumes englobants de l'objet du complexe simplicial à partir à la fois de la position des faces du complexe simplicial et des ensembles de normales au sens fort associées, 15 et en ce qu'il comprend des moyens de calcul associés aux moyens de prétraitement, pour procéder à un calcul de distances minimales locales et de quasi-distances minimales locales, ces dernières correspondant chacune à un couple de points appartenant respectivement à des objets distincts et qui définiraient une distance minimale locale si la 20 position d'un objet par rapport à l'autre subissait une rotation d'un angle faible inférieur à un seuil donné. Le dispositif peut être couplé à un solveur mécanique. L'ensemble du dispositif et du solveur mécanique peut être couplé à au moins un périphérique parmi les périphériques comprenant 25 notamment une interface graphique utilisateur, une souris, un périphérique de capture de mouvement, une interface à retour d'effort, une interface tactile, une interface sonore. L'invention permet en particulier une simulation stable de comportement mécanique (sans oscillations parasites), et le choix d'une 30 grande raideur du rendu haptique qui procure un ressenti fidèle à la situation représentée. Cette solution permet d'identifier les zones de contact, avec une solution régularisée vis-à-vis des translations et des rotations de l'objet. C'est-à-dire que l'on peut anticiper ce qui va se passer. Le traitement du 35 problème des contacts peut ainsi obtenir une solution stable sans avoir recours à une approche événementielle qui nécessiterait le calcul des 2906388 4 instants de contact et l'adaptation des pas de temps de l'intégrateur numérique en fonction des dates de ces instants. L'avantage de la solution proposée est non seulement de fournir une solution très stable au cours des déplacements en temps réel d'objets 5 virtuels, mais aussi de résoudre les situations difficiles à simuler telles que - recherche de contacts conformants entre objets sans collision ni traversée des objets (par exemple positionnement d'un objet plan sur un autre objet plan, détection de contacts plans entre deux objets) ; 10 -recherche d'une trajectoire de montage/démontage d'une pièce en évitant les zones de contact et/ou de blocage ; mise en évidence des zones de contact pour des objets notamment concaves, avec solution stable lors de mouvements de faible amplitude angulaire ou de déplacement au voisinage d'une position. 15 L'invention ne se limite pas à la détection de contacts ponctuels, mais elle permet aussi la détection de contacts conformants pour différentes topologies : contacts linéiques ou contacts surfaciques entre deux objets. Elle permet également de détecter des intersections et, dans certaines conditions, des profondeurs d'interpénétration. 20 D'autres caractéristiques et avantages de l'invention ressortiront de la description suivante de modes particuliers de réalisation,, donnés à titre d'exemples, en référence aux dessins annexés, sur lesquels : - la Figure 1 est un diagramme explicatif d'un aspect du procédé selon l'invention montrant un exemple en dimension 2 du choix ou du 25 rejet sélectif de différentes distances minimales locales (LMD) entre deux objets virtuels, - la Figure 2 montre un exemple d'arbre orienté pouvant être utilisé dans une étape du procédé selon l'invention, - les Figures 3 à 7 montrent diverses positions relatives entre un 30 premier objet cubique et un deuxième objet plan simulés numériquement, qui peuvent être visualisés selon l'invention, et - la Figure 8 est un schéma bloc d'un exemple de dispositif selon l'invention. Avant de décrire en détail le procédé et le dispositif selon 35 l'invention, on donnera ci-dessous un certain nombre de définitions utiles, soit classiques, c'est-à-dire recouvrant des concepts généraux largement 2906388 5 acceptés par la communauté scientifique et technique, et pour lesquels une terminologie suffisamment unifiée existe dans la littérature scientifique et technique, soit plus spécifiques, dans la mesure où bien qu'il s'agisse de définitions de concepts relativement généraux, la 5 terminologie peut varier selon les auteurs. On donnera également quelques définitions propres à l'invention et au domaine d'application du procédé. I û Définitions classiques Dans la suite, Rn désigne le produit cartésien du corps des réels 10 n fois par lui-même, où n est un entier strictement positif. Cet espace est considéré muni de sa structure euclidienne naturelle. La sphère unité de Rn est notée Sn-` . Intérieur et bord relatifs 15 Notion topologique. Soit A une partie de W . L'intérieur relatif de A est l'intérieur de A dans la topologie naturelle (i.e. celle qui découle de la structure euclidienne) du sous-espace affine de Rn engendré par A. L'intérieur relatif de A est noté Ri(A) . De même, le bord relatif (ou frontière relative) de A est le bord 20 de A dans la topologie naturelle du sous-espace affine de Rn engendré par A. Simplexe Notion géométrique. Soit d un entier positif ou nul. Un simplexe 25 (ou d -simplexe, ou encore simplexe de dimension d) de W est défini comme l'enveloppe convexe de d+1 points de Rn affinement indépendants. On remarque que la dimension topologique d'un cfsimplexe est égale à d. 30 Face d'un simplexe Soit S un cf-simplexe défini comme l'enveloppe convexe de l'ensemble de points de Rn affinement indépendants {po, ..., pd}. Les simplexes définis comme les enveloppes convexes de sous-ensembles de 35 {po, ..., pd} sont appelés les faces du simplexe S. 2906388 6 Le simplexe S est une face particulière de S. Les faces d'un simplexe S différentes de lui-même sont appelées les faces propres de S. Leur union est appelée le bord simplicial (ou frontière simpliciale) de S, noté Bd S. L'intérieur simplicial de S est défini comme le complémentaire 5 de Bd Sdans S: IntS=SùBdS. L'intérieur simplicial et le bord simplicial d'un simplexe coïncident avec respectivement l'intérieur relatif et le bord relatif de ce simplexe. 10 Complexe simplicial Un complexe simplicial Kdans 11 n est un ensemble de simplexes de W tel que les deux conditions suivantes soient vérifiées : û toute face d'un élément de Kest aussi dans K; 15 û l'intersection de deux simplexes quelconques de Kest une face de chacun d'eux. Les éléments d'un complexe simplicial sont appelés les faces de ce complexe. La dimension d'un complexe simplicial est définie comme la dimension maximale de ses faces. 20 L'union des faces d'un complexe simplicial K s'appelle le corps du complexe K, noté IKI. Il est facile de montrer que les intérieurs relatifs des faces d'un complexe simplicial forment une partition du corps de ce complexe. On peut se référer également à cet égard à la page 7 du 25 document [2]. Polytope Définition issue de la topologie algébrique. Soit Kun complexe simplicial dans Rn. En supposant que chaque face o- de K est munie de 30 sa topologie naturelle (i.e. de la topologie induite sur o- par la topologie naturelle de W ), on peut munir le corps de Kd'une topologie définie de la manière suivante : un sous-ensemble A de IKI sera considéré comme fermé dans KI si et seulement si Ana est fermé dans a, pour toute face o- de K L'espace topologique ainsi défini sera toujours noté IKI et 35 est appelé l'espace topologique sous-jacent à K,, ou encore le polytope de K 2906388 7 Polyèdre Définition issue de la topologie algébrique. Un espace topologique qui est le polytope d'un complexe simplicial fini sera appelé un polyèdre. Cône Définition issue de l'analyse convexe. Toute partie C d'un espace vectoriel sur le corps des réels stable par multiplication par les réels strictement positifs est appelée cône. On dit qu'un cône est pointé lorsqu'il 10 contient l'origine. Remarque : Un cône de Rn n'est pas nécessairement de révolution, ni convexe, ni fermé. Cône polaire 15 Définition issue de l'analyse convexe. Soit A une partie de Rn. L'ensemble noté A* et défini de la manière suivante : A'={yERn / b'xEA,(y,x)0} est appelé le cône polaire de A, ou encore simplement le polaire de A. C'est un cône convexe, car c'est l'intersection de demi-espaces 20 fermés. On note également que le polaire de A, le polaire de l'enveloppe convexe de A, ainsi que le polaire du cône convexe engendré par A, coïncident. Cône tangent 25 Définition issue de l'analyse convexe. Soit A une partie de Rn et x un élément de A. Un vecteur y de Rn est dit tangent à A au point x si l'une des deux conditions suivante est remplie : • y est le vecteur nul ; • y est non nul et il existe une suite de Rn (xk )kEN.' à valeurs dans 30 A\{x}, telle que : o hmxk=x ; kxk -x y o lim = k--Ilxk-xl IyII L'ensemble des vecteurs tangents à A en x est appelé le cône 35 tangent à A en x et noté TA(x) . C'est un cône fermé, non nécessairement convexe. 5 2906388 8 Pour plus de détails sur les cônes tangents et une définition rigoureuse des cônes normaux, on peut se référer par exemple au document [3]. 5 Dilatation Notion issue du domaine de la morphologie mathématique. Soit E un espace métrique muni d'une distance d. L'opération de dilatation de rayons, aussi appelée s-dilatation, associe à toute partie A de E, la partie de E, appelée e -dilaté de A, constituée de l'union des boules de rayon e 10 ayant pour centre un élément de A. Partition Terme ensembliste. Soit E un ensemble. Un ensemble P de parties de E est une partition de E s'il vérifie les trois conditions 15 suivantes : • les éléments de Psont des parties non-vides de E; • les éléments de P sont deux à deux disjoints ; • l'union des éléments de Pest égale à E 20 Recouvrement Terme ensembliste. Soit Eun ensemble. Un recouvrement d'une partie A de E est une collection de partie de E telle que l'union de ces parties contienne A. Toute partition d'un ensemble E est aussi un recouvrement de 25 E Hiérarchie Terme ensembliste. Soit E un ensemble fini. Une hiérarchie sur E est un ensemble H de parties de E qui vérifie les trois conditions 30 suivantes : • H contient les singletons de E; • H contient E; • Si A et B sont deux éléments de H et que ce sont des parties non-disjointes de E, alors A contient Bou B contient A. 35 2906388 9 Arbre orienté Notion issue de la théorie des graphes. Un arbre orienté est un graphe orienté connexe sans circuit dans lequel tout sommet a un degré entrant (nombre d'arêtes ayant ce sommet comme extrémité) inférieur ou 5 égal à 1. Un arbre orienté possède un et un seul sommet dont le degré entrant est 0, alors que tous les autres sommets sont de degré entrant 1. Ce sommet est appelé la racine de l'arbre. Un exemple d'arbre orienté (dont les noeuds sont munis de 10 labels) est donné sur la Figure 2. La longueur maximale d'un chemin dans un arbre orienté est appelée la profondeur de l'arbre. Pour chaque noeud, il existe un unique chemin partant de la racine et arrivant en ce noeud. La longueur de ce chemin est appelée la 15 profondeur du noeud dans l'arbre. La profondeur de la racine est donc 0. Dans l'exemple de la Figure 2, le noeud 8 est de profondeur 2, tandis que le noeud 4 est de profondeur 3. Les noeuds dont le degré partant est nul sont appelés les feuilles de l'arbre. Dans l'exemple de la Figure 2, les feuilles de l'arbre sont les 20 noeuds 3, 4, 5, 7,8et9. Soit a un noeud d'un arbre orienté. Les noeuds auxquels arrivent les arêtes partantes de a sont appelés les enfants du noeud a. Une feuille est donc un noeud qui n'a pas d'enfants. Le nombre maximal d'enfants d'un noeud dans un arbre orienté 25 est appelé l'arité de l'arbre. Remarque : les arbres les plus utilisés dans le domaine de la détection de collision sont des arbres de faible arité, par exemple des arbres binaires (d'arité 2), ternaires (d'arité 3) ou quaternaires (d'arité 4). 30 2 ù Définitions spécifiques Objet polyédrique Un objet polyédrique est un corps physique pour lequel une représentation géométrique possible est un polyèdre, au sens défini plus 35 haut. Ceci est valable aussi bien dans un espace physique de référence de 2906388 10 dimension 2 que dans un espace de dimension 3, le polyèdre associé étant respectivement un polyèdre de R2 ou de R3. Vecteur unitaire orthogonal à une face d'un simplexe Soient Sun d-simplexe de R" avec d > O, ci une face de S de 5 dimension dû1 et v le sommet de S opposé à (F. Soit a le projeté orthogonal de v sur le sous-espace affine de W engendré par a-. Les points a et v sont distincts. Le vecteur unitaire aùv est appelé le laùv11 vecteur unitaire orthogonal à la face o- du simplexe Set noté u,, (Q) . Trace d'un cône sur la sphère unité 10 Soit C un cône de Rn. La trace de C sur la sphère unité est l'intersection de C avec Sn-'. Si C contient l'origine, alors le cône pointé engendré par la trace de C sur la sphère unité est égal à C. Vecteurs normaux au sens fort Soit A une partie de W . Un vecteur W est dit normal au sens 15 fort à A au point x s'il appartient au polaire de TA(x). L'ensemble des vecteurs normaux au sens fort à A au point x est donc le cône convexe TA(x)* , qui sera appelé le cône normal au sens fort à A au point x et noté nA(x). Soit B une sous-partie de A. Un vecteur y de R" est dit normal 20 au sens fort à A associé à B s'il existe un point x de B tel que y appartienne à TA(x)* . L'ensemble des vecteurs normaux au sens fort à A associés à B sera noté nA (B) . On a donc: nA(B) = U nA(x) xeB 25 Interpénétration (ou interférence) Notion géométrique. Soit A et B deux compacts de Rn . On dira que A et B sont en interpénétration (ou encore en interférence) si leurs intérieurs ne sont pas disjoints. 2906388 11 Contact ponctuel Domaine de la modélisation des phénomènes mécaniques de contact. La définition proposée ici est une formalisation mathématique de la notion géométrique de contact ponctuel. 5 Soit A et B deux compacts de W . Un contact ponctuel entre A et Best défini comme un point isolé de l'intersection de A et B. Contact conformant Domaine de la modélisation des phénomènes mécaniques de contact. La définition proposée ici est une formalisation mathématique de 10 la notion géométrique de contact conformant. Soit A et B deux compacts de W . Un contact conformant entre A et B est défini comme une composante connexe par arcs, d'intérieur vide et non réduite à un point, de l'intersection de A et B. Distance minimale locale 15 Soit E un espace métrique muni d'une distance d Soit A et B deux parties de E Une distance minimale locale entre A et B, notée en abrégé LMD dans la suite, est définie comme un minimum local de la restriction de la fonction d, définie sur le produit cartésien de E par lui-même, au produit cartésien de A et B. Un couple de points (a, b) E AxB 20 réalisant un tel minimum local est appelé le support de la distance minimale locale considérée, tandis que le réel positif d(a,b) est appelé la valeur de la LMD. Interstice Domaine de la modélisation des phénomènes mécaniques de 25 contact. La définition proposée ici est une formalisation mathématique de la notion géométrique d'interstice, généralisée au cas des corps non nécessairement convexes. Soit A et B deux compacts de Iii" . Les interstices entre A et B sont par définition les valeurs des LMD entre A et B. 30 Sous-arbre orienté ou branche Théorie des graphes. Un sousgraphe d'un arbre orienté T qui est encore un arbre orienté est appelé un sous-arbre orienté de T ou encore une branche de T 2906388 12 Volume englobant Notion issue du domaine de la détection de collisions. Il est donné ici une formalisation mathématique. Un volume englobant est un élément d'un recouvrement d'une 5 partie de W . Il sera également employé, bien que ce ne soit pas habituel dans le domaine de la détection de collisions, pour désigner un élément d'un recouvrement d'une partie de Sn-' ou de W xSn-' . Hiérarchie de volumes englobants Notion issue du domaine de la détection de collisions. Soit A une 10 partie de E, où Edésigne R", Sn-', ou R' xS"-'. On appellera hiérarchie de volumes englobants de A toute famille finie H = (V1, ..., VN) de parties de E, dits volumes englobants, associée à un arbre orienté T, dit arbre de volumes englobants, dont les noeuds sont en bijection avec les éléments de H et qui vérifie la propriété suivante : pour tout sous-arbre orienté T' 15 de Tayant même racine que T, les éléments de Hassociés aux feuilles de T'forment un recouvrement de A. Cette définition a pour conséquence que les volumes englobants associés aux feuilles de l'arbre T forment un recouvrement de A. De même, le volume englobant associé à la racine de Trecouvre A à lui seul. 20 Un moyen simple de construire une hiérarchie de volumes englobants d'une partie A de E est de commencer par construire une hiérarchie H'sur une partition de A au sens ensembliste. Les méthodes usuelles pour cela sont la subdivision successive à partir de A tout entier et l'agrégation successive à partir d'une partition de A. On peut ensuite 25 construire une hiérarchie de volumes englobants de A à partir de H'en recouvrant la réunion des éléments de chaque élément de H' par un élément de H, la structure d'arbre orienté associée à H découlant directement de la structure hiérarchique de H: On introduira maintenant trois notions qui sont propres à 30 l'invention. Sous-partie d'une partie deRn munie des vecteurs normaux au sens fort associés Etant donnée une partie A de Ibn et B une sous-partie de A, on dira que l'on munit B des normales au sens fort à A associées (sous- 2906388 13 entendu à B) lorsque l'on désignera la partie de Rn xW formée par le produit cartésien de B et de nA(B). On peut remarquer que cet ensemble est vide dès que nA(B) l'est. Classe de contact 5 Soit K un complexe simplicial. On classifie, en classes dites classes de contact et labellisées de 0 à 7, les faces de K, en Fonction de leur dimension topologique, de la dimension topologique de l'intersection avec la sphère unité des ensembles de vecteurs normaux au sens fort au corps de Kassociés à leur intérieur relatif, et éventuellement la géométrie 10 de l'intersection de leur étoile dans Ket de la frontière (dans W) du corps de K, selon le tableau 1 ci-dessous pour n = 3. Tableau 1 Dimension Dimension Géométrie de Label de topologique de la topologique de l'intersection de la classe de face o- (Int a-) n Sn-' l'étoile de o- dans contact de o- K et de la frontière du corps de K 0 2 quelconque 0 0 1 quelconque 1 1 1 quelconque 2 0 0 non plane 3 0 0 plane 4 1 0 quelconque 5 2 0 quelconque 6 quelconque (0, 1, -1 quelconque 7 2 ou 3) Pour n = 2, on utilise le tableau 2 ci-dessous : 15 2906388 14 Tableau 2 Dimension Dimension Géométrie de Label de topologique de la topologique de l'intersection de la classe de face a- nKI (Int 6) n Sn-' l'étoile de a dans contact de 6 K et de la frontière du corps de K 0 1 quelconque 0 0 0 quelconque 1 1 0 quelconque 2 quelconque (0, 1, -1 quelconque 7 ou 2) On rappelle que la dimension topologique de l'ensemble vide est -1 par 5 convention. Quasi-distance minimale locale (régularisée vis-à-vis des rotatiorni Extension de la notion de distance minimale locale entre les dilatés de deux complexes simpliciaux non interférents Cette définition sera précisée plus loin, lorsque les éléments nécessaires à sa formulation 10 auront été mis en place. On explicitera maintenant de façon détaillée le procédé selon l'invention. De manière hiérarchique, on peut distinguer deux étapes, temporellement disjointes, du procédé de l'invention, ces deux étapes 15 pouvant à leur tour être décomposées en sous-étapes. Ces deux étapes sont 1. Etape de pré-calcul : cette étape est réalisée lors de la préparation de la simulation proprement dite. Elle consiste à calculer des données nécessaires à l'efficacité (i.e. la rapidité) des traitements 20 effectués dans la deuxième étape. 2. Etape de calcul de distances minimales locales : cette étape tire parti des informations pré-calculées pour accélérer les calculs nécessaires au procédé et atteindre un niveau de performance compatible avec une simulation en temps réel. 2906388 15 Afin de faciliter la compréhension du fonctionnement du procédé, on commencera par présenter ci-dessous des résultats qui établissent un lien entre la notion de distance minimale locale entre deux complexe simpliciaux et la notion d'ensemble de vecteurs normaux (au 5 sens fort) associés à un point ou une partie d'un complexe sirnplicial. On poursuivra ensuite la description du procédé proprement dit. L'invention prend en compte les résultats importants suivants. Soient K, et K2 deux complexes simpliciaux dans Rn . Soient x, 10 et x2 deux points des corps de K, et K2 respectivement. Le couple (x,,x2) est le support d'une LMD entre les corps de K, et K2 si et seulement si les deux conditions suivantes sont vérifiées : x2ûx,E1K,, l); x,-x2E (x2). 15 Soit Kun complexe simplicial dans R . Soit x un point du corps de K Soit cx l'unique face de Kdont l'intérieur relatif contient x • Le cône tangent au corps de K au point x est égal au cône engendré par StQx ûx . 20 • Le cône tangent au corps de K au point x est égal à Il8" dès que x appartient à l'intérieur de IKI dans W . 1 # • 1KI(x)_(DirAffcr n{ua(a-), oEStKQx, dimo'=dimax+1} . Par conséquent : 25 • Si x et y sont deux points du corps de K contenus dans l'intérieur relatif de la même face 6 de K, alors les cônes tangents au corps de Ken xet ysont égaux ; • IKI (x) = u1 K~ (Int o-x) . • KI(Into-x) est un cône polyédrique. 30 On peut énoncer un corollaire de ce résultat. Supposons de plus que les corps de K, et K2 sont disjoints. Le couple (x,,x2) est le support d'une LMD entre les corps de K, et K2 si et seulement si les deux conditions suivantes sont vérifiées : lx2 ûxI appartient a 1K,I(x1) ; x2-x, 2906388 16 x, -x2 appartient à 1KZ1(x2) I1x, ùx21 On en déduit en particulier que les couples de points (x,,x2) supports de distances minimales locales entre les corps de K, et K2 sont 5 tels que 1K,I(x,) et nK21(x2) ne sont pas réduits à {O} . Soient K, et K2 deux complexes simpliciaux dans W , de corps disjoints. Soient A, et A2 des parties des corps de K, et K2 respectivement. S'il existe (au moins) un couple de points (x,,x2) dans 10 A, xA2 support d'une LMD entre les corps de K, et K2, alors les trois conditions suivantes sont vérifiées : 1. P,(A,,A2) : l'intersection de IK'I(A,) et ùIK21(A2) n'est pas réduite à {o} ; 2. P2(A,,A2) : l'intersection de l K'I(A,) et du cône engendré par A2 ùA, 15 n'est pas réduite à {0} ; 3. P3(A,,A,) : l'intersection de -1K21(A2) et du cône engendré par A2 ù A, n'est pas réduite à {o} . On peut ici expliciter les aspects principaux du procédé selon 20 l'invention. Le procédé de l'invention est applicable aux objets polyédriques rigides et aux objets polyédriques déformables à condition que les déformations correspondent àdes déplacements des sommets des complexes simpliciaux sous-jacents. 25 L'invention améliore et étend le procédé proposé dans le document [1] qui permet le calcul des distances minimales locales entre des objets polyédriques volumiques représentés par une triangulation de leur frontière en dimension 3. L'invention corrige et clarifie la définition des normales (au sens 30 fort) associées à un point de la frontière d'un tel polyèdre en s'appuyant sur le cadre théorique bien établi de l'analyse convexe. L'invention permet d'étendre la méthode proposée par le document [1] au cas général des complexes simpliciaux (éventuellement dilatés) en dimension 2 et 3, ce qui comprend notamment les cas 35 suivants : 2906388 17 objets polyédriques surfaciques (plaques, coques, tôles, etc) objets polyédriques linéiques (câbles, poutres, etc) ; objets polyédriques à topologie hybrides (squelettes, etc) ; nuages de points (unions de boules, etc). 5 L'introduction des dilatations augmente le potentiel de représentation du modèle géométrique que constitue la notion de complexe polyédrique. La dilation d'un complexe polyédrique purement surfacique pourra donc représenter la demi-épaisseur d'une coque, celle d'un complexe purement linéique le rayon moyen d'un câble, etc. 10 Une généralisation de l'invention aux représentations par axe médian est possible. Les résultats importants mentionnés plus haut permettent de restreindre la recherche calculatoire de distances minimales locales entre les corps de deux complexes simpliciaux K, et K2, de corps disjoints, aux 15 seuls couples de points (x,,x2) des corps de K, et K2tels que 1K,I(x,) et nlK2 (x2) ne soient pas réduits à {01. Néanmoins ceci peut représenter une infinité de couples de points à tester, et il n'est donc pas possible de baser un procédé de calcul des LMD entre deux complexes simpliciaux sur une exploration exhaustive de ces couples candidats. 20 Le dernier résultat présenté plus haut est un élément supplémentaire important pour le fonctionnement du procédé, car il fournit une condition nécessaire qui va pouvoir être utilisée pour la localisation de distances minimales locales entre les corps de K, et K2. Supposons en effet que l'on dispose de partitions finies P, et P2 25 des corps de K, et K2 respectivement. Une méthode permettant par le calcul de restreindre les lieux possibles de couples de points supports de LMD entre les corps de K, et K2 consiste à évaluer les prédicats PI, P2 et P3 qui correspondent aux conditions 1 à 3 décrite plus haut pour chaque couple (AI,A2)e P, xP2 . Le nombre de couples à tester est égal au produit 30 des cardinaux de P et P2. Supposons maintenant que les complexes K, et K. sont finis (i.e. possèdent un nombre fini de faces). Alors un choix possible pour la partition P, (resp. P2) est l'ensemble des intérieurs simpliciaux des faces de K, (resp. K2). Les couples à tester sont alors les (Int Q, , Int 62) , 35 appartenant à K, et (72 à K2. De plus, comme le prédicat P,(Int6,,Int62)est faux dès que 1 KI(Intal) ou 1 K,l(Intol) est réduit à {o}, 2906388 18 on peut restreindre les tests à effectuer aux seuls couples (I:nt o',, Int o'2 ) tels que 1K I (Int o',) et 1K I (Int o',) ne sont pas réduits à {O} . En vue d'accélérer ce parcours de couples de faces, le procédé de l'invention utilise une hiérarchie de volumes englobants qui sera décrite plus loin. 5 On s'intéressera d'abord au cas d'un couple de faces (o,,o-2)E K, xK2 . On peut montrer qu'un couple de points (x,,x2)E (Into',,Inta-2) est le support d'une LMD entre FK1I et IK2I si et seulement si les deux conditions suivantes sont vérifiées : (x,, x2) est le support d'une LMD entre Int Q, et Int o'2 ; 10 x2 ù x, E IKil (Int ) ; x, ù x2 E YGKZI (Int o"2) . D'après les résultats précédents, on peut aussi montrer qu'un couple de points (x,, x2) E Int o', x Int o'2 est le support d'une LMD entre Int et Into'2 Si et seulement si le vecteur x2-x, appartient à 15 (DirAff Q, )1 n (Dir Aff 62 )1. Par conséquent, un tel couple de points est aussi une LMD entre Aff o, et Aff 62 . Plus précisément, un couple de points (x,, x2) E Aff xAff a•2 est une LMD entre Int Q, et Int o'2 Si et seulement si (x,,x2) appartient à Into',xInto2et x2ùx, à (Dir Aff )l n(DirAff o-2)'. 20 Les résultats énoncés dans les deux paragraphes précédents permettent de construire un procédé pratique de calcul des couples de points (x,,x2)E Int cri xlnto2 qui sont des LMD entre K,I et IK2I : Calculer le lieu des points (x,,x2)E Aff Q, xAff a-2 tels que x2 ùx, appartient à (Dir Aff 61 )1 n (Dir Aff 62 )1. 25 Calculer l'intersection de ce lieu avec Int o', x Int o'2 . Parmi les éléments (x,,x2) de l'ensemble ainsi obtenu, ne retenir que ceux qui vérifient x2 ùx, E 1 Kii(Into-1) et x, ùx2 E nlK2I(Inta-2) . On obtient ainsi exactement les couples de points (x,,x2)E Int xInto'2 qui sont des LMD entre IKII et IK2I. 30 On notera que les ensembles de couples de points successivement calculés dans le procédé précédent peuvent être infinis, ce qui correspond au cas de contacts conformants entre des objets polyédriques dilatés. Il est possible de donner une description géométrique simple de ces ensembles de couples de points (ce sont des 35 ensembles polyédriques) dans les cas de R3 et R2, mais le caractère infini du nombre de LMD obtenues finalement rend impossible la prise en 2906388 19 compte explicite de chacune de ces LMD sous forme d'interstice dans une méthode numérique visant à simuler les phénomènes de contact entre solides polyédriques. Cependant, il est possible de montrer, par des arguments simples d'analyse convexe, que la prise en compte de chacune 5 de ces LMD n'est pas nécessaire pour assurer le respect des contraintes unilatérales de non-interpénétration des objets. C'est pourquoi ces cas, qui ne correspondent géométriquement qu'à des cas de parallélisme entre Aff 6, et Aff 62 , sont ignorés dans le procédé lié à l'invention. Les tableaux 3 et 4 ci-dessous donnent, pour les cas de IR3 et 10 11 2 , les nombres possibles de LMD entre Int 6, et Int 62 . dim 62 dimc 0 1 2 3 0 O ou l O ou 1 O ou l 0 1 0 ou 1 ou 0 ou une infinité 0 une infinité 2 , 0 ou une infinité 0 3 0 Tableau 3 : Nombre de distances minimales locales entre Int cri et Int o2 lorsque o-, et 62 sont des simplexes disjoints de I 2906388 20 dim o-2 dim 6, 0 1 2 0 Oou1 Oou1 0 1 0 ou une infinité 0 2 0 Tableau 4 : Nombre de distances minimales locales entre Into-, et Into-2 lorsque Q, et (72 sont des simplexes disjoints de 1182 5 Le détail des calculs pratiques associés au traitement de chacun des cas soulevés par les tableaux précédents sera exposé plus loin. Il convient toutefois d'abord de faire deux remarques essentielles : Dans certains cas particuliers où le nombre de LMD entre 1K11 et IK21 dont le support est sur Into1 xlnto-2 est pourtant un ensemble fini, 10 ces LMD peuvent en fait être ignorés dans le cadre de la construction d'un ensemble de points de contacts entre solides rigides en l'absence de frottement sec au contact. L'élimination de ces LMD permet de réduire le nombre de points de contact utilisés (et donc le temps de calcul des méthodes numériques utilisées au sein d'un solveur numérique traitant le 15 contact) sans pour autant engendrer des erreurs qui pourraient aboutir à l'interpénétration des solides rigides. Les cas particuliers en question correspondent en fait à des LMD qui passent par l'intérieur relatif de contacts conformants entre les solides polyédriques dilatés. Leur élimination correspond donc à ne conserver que les LMD qui soit sont en 20 intersection avec le bord relatif de l'enveloppe convexe d'un contact conformant entre les solides polyédriques dilatés, soit passent par un contact ponctuel entre ces solides. La figure 1 fournit un exemple typique des cas finalement retenus en dimension 2. Entre les représentations 210, 220 de deux objets, on a 25 visualisé quatre LMD référencés 231 à 234. Dans l'exemple considéré, on a retenu les LMD 231, 232, 234 (en tirets épais) et on a rejeté la LMD inutile 232 (en pointillés fins). 2906388 21 Les algorithmes de résolution de problème d'évolution impliquant le contact peuvent être classifiés en deux groupes principaux : les algorithmes de type événementiel (qui calculent exactement les instants de transition entre séparation et contact) et les algorithmes de 5 type time-stepping (à pas de temps) qui utilisent un pas de temps d'intégration fixé à l'avance. Ces derniers sont les seuls capables d'être exécutés à ce jour en temps réel pour le cas d'un grand nombre de contact ou d'une accumulation infinie (le fameux effet 2:eno , qui correspond à une infinité de transitions au cours d'un intervalle de temps 10 fini, comme dans le cas d'une balle rigide soumise à la gravité qui rebondit sur un plan avec un coefficient de restitution en vitesse compris strictement entre 0 et 1). Dans le cas d'un algorithme de type time-stepping , il peut s'avérer difficile de stabiliser un objet polyédrique représenté par un 15 simple cube posé sur plan et soumis à la gravité si les seuls points de contact considérés sont issus de LMD entre le cube et le plan. En effet, le seul cas permettant la stabilisation du cube correspond à l'existence simultanée de strictement plus d'une LMD entre le cube et le plan, ce qui correspond au cas du parallélisme entre une face du cube et le plan. Dans 20 ce cas, il existe une infinité de LMD entre le cube et le plan (leur support sur le cube correspond à toute une face de celui-ci). D'après la remarque précédente, le fait de retenir seulement les quatre LMD qui correspondraient aux quatre coins du cube posés sur le plan pour déterminer un ensemble fini de points de contact serait suffisant. Or, non 25 seulement le cas de parallélisme est difficile à caractériser numériquement car il implique d'évaluer de manière exacte (ou suffisamment bien gérée) des prédicats d'égalité entre des nombres réels représentés en machine, mais encore force est de constater que la stabilisation du cube sur le plan implique de pouvoir passer de façon stable au cours de la simulation par 30 des états où aucune face du cube n'est parallèle au plan, mais où des rotations de faible amplitude entraînent un passage (au cours du pas de temps) par un tel état. Une face du cube est alors presque parallèle au plan, et il suffit d'une rotation de faible amplitude pour les quatre LMD recherchées existent (éventuellement de manière complètement isolée 35 dans le temps). C'est pourquoi l'invention introduit la notion de quasi-LMD, qui correspond à un couple de points qui serait le support d'une LMD si la 2906388 22 position d'un corps par rapport à l'autre subissait une rotation d'un angle faible, dont la mesure maximum est un paramètre du procédé. L'élimination d'une LMD inutile pour le problème de contact ou la prise en compte d'une quasi-LMD est systématisable en fonction de 5 simples critères locaux que formalisent les classes de contact accompagnées d'un tableau synthétique de compatibilité et de régularisation angulaire qui sera présenté plus loin (Tableau 5). On notera que, outre le fait que le procédé selon l'invention est généraliste, il présente des avantages fondamentaux qui découlent de la 10 mise en oeuvre de quasi-LMD et de la possibilité d'éliminer une LMD inutile pour le problème de contact. D'autre part, les ensembles 1 KI(Inta) sont des cônes polyédriques qui peuvent être pré-calculés dans le cas d'un corps rigide. Enfin, l'invention prend en compte le fait que l'examen de toutes 15 les paires (Q,,0,)E K,xK, est inutile et peut être accéléré grâce à l'utilisation de hiérarchie de volumes englobants de IK, et respectivement muni des normales au sens fort associées. Dans le cas rigide, ces hiérarchies de volumes englobants peuvent être entièrement pré-calculées. Dans le cas d'un corps déformable représenté par un 20 complexe simplicial fini K, la solution suivante est applicable : -utiliser une hiérarchie H' sur la partition de IKI pour former les intérieurs simpliciaux des faces de K pour construire une hiérarchie de volumes englobants H pour un état de déformation de référence ; conserver entre deux états déformés de la même structure une 25 hiérarchie de volumes englobants basée sur H'et simplement remettre à jour la géométrie de chaque volume englobant afin de s'adapter aux déformations des faces de K L'utilisation de hiérarchie de volumes englobants est une technique classique dans le domaine de la détection de collision. 30 L'invention utilise une méthode qui améliore celle proposée par le document [1]. On décrira maintenant de façon détaillée l'étape de pré-calcul du procédé selon l'invention. Dans toute la suite, on suppose que n est un entier fixé, égal à 35 2ouà3. 2906388 23 Les données d'entrée sont construites par une famille finie de complexes simpliciaux de W . Les données de sortie comprennent : Pour chaque face ade chaque complexe simplicial K: 5 û une description géométrique du cône polyédrique ,P KI(Int a) ; û le label de la classe de contact à laquelle appartient la face. Pour chaque complexe simplicial d'entrée K : un arbre de volumes englobants du corps du complexe simplicial muni des normales au sens fort associées. Les volumes englobants sont donc des parties deRn xRn. 10 Dans l'invention, chaque volume englobant utilisé est le produit cartésien d'une boule de Rn et d'un cône Rn. Dans le cas de R3, les cônes considérés sont des cônes de révolution, simples ou doubles, d'ouverture éventuellement nulle (demi-droite ou droite complète). Dans le cas de R', les cônes considérés s'obtiennent à partir du cas tridimensionnel par 15 intersection des cônes avec un plan contenant leur axe de révolution. A chaque noeud feuille de l'arbre sont associées une ou plusieurs faces de K Une face de Kest associée à au plus une feuille de l'arbre. Les faces de K associées aux feuilles de l'arbre sont exactement les faces dont l'ensemble des normales au corps de K au sens fort 20 associées est non vide. Le volume englobant associé à un noeud feuille recouvre la partie du corps de K, munie des normales associées, formée par l'union des intérieurs simpliciaux des faces de K associées à cette feuille. A chaque noeud de l'arbre (qu'il soit un noeud feuille ou non), 25 sont associés : un volume englobant qui recouvre la partie du corps de K, munie des normales associées, formée par l'union des intérieurs simpliciaux des faces de K associées aux feuilles de la branche de l'arbre engendrée par ce noeud ; 30 pour chaque classe de contact de label i (de 0 à 7), une valeur booléenne égale à l'évaluation du prédicat suivant:: il existe, parmi les feuilles de la branche de l'arbre engendrée par ce noeud, au moins une feuille à laquelle est associée au moins une face de K dont le label de la classe est i. 2906388 24 On décrira maintenant les traitements effectués pour chaque complexe simplicial K donné en entrée. On suppose que les coordonnées des sommets de K sont données dans un système de coordonnées fixé. Dans le cas d'un corps rigide, il est naturel et commode de choisir un 5 repère lié à ce corps. Dans le cas d'un corps déformable, on pourra par exemple choisir un repère de référence pour fixer les coordonnées des sommets de Kdans un état de déformation qui sera dit de référence (par exemple, l'état de repos pour un corps dont la loi de comportement est de type élastique). 10 Une première étape du prétraitement selon le procédé conforme à l'invention consiste en le calcul des normales au sens fort et des classes de contact. Il s'agit, pour chaque face Ede /Ç de calculer une description géométrique de 1KI(Int 6) . On rappelle le résultat suivant : 15 1KI (o-) = (DirAff o-)1 n{u,(Q), où E StKQ, dim6 =dimo+l} . Plusieurs choix sont possibles pour représenter en machine un tel cône polyédrique. Compte tenu du fait que dans les calculs qui seront nécessaires lors de la phase de recherche des LMD, le sous-espace vectoriel (DirAff o-)1 n'a pas besoin d'être représenté en machine. Une 20 représentation du cône convexe {u,,(6), Q E i K o-, dimo-'= dim6+1} suffit. Dans le cas d'un corps rigide, on aura intérêt à travailler dans un système de coordonnées lié au corps et à utiliser une représentation polaire de {u,.(o-), o -'e StK6, dim6 =dima+1}, ce qui revient à 25 représenter le cône convexe engendré o -'E St K 6, dim 6 = dim Q + 1} par ses arêtes, c'est-à-dire par un sous-ensemble minimal de {u,,(Q), a- E St K o-, dim a' = dim o-+ 1} qui engendre le même cône convexe. 30 Dans le cas d'un corps déformable, le sous-ensemble des vecteurs qui dirigent les arêtes du cône convexe engendré par {ua,(6), 6'E StKo-, dimd=dimo+1} peut varier, donc il est plus rentable de conserver tous les ua,(a-) dans la représentation polaire. A titre d'exemple, on peut examiner une face o- qui est un 35 sommet d'un complexe polyédrique dans R3. On a alors : (DirAff o)' = R3 , 2906388 d'où 9KI (6) _ {uQ (6), 6 E St K Q, dim a' = l} Il s'agit maintenant de calculer les uQ (6), puis d'en extraire un sous-ensemble minimal qui engendre le même cône convexe. Ceci peut se 5 faire facilement en recherchant les plans qui composent les faces du cône convexe polyédrique engendré par {ua,(Q), o -'E St K o-, dim a' _: l}, ce qui revient à éliminer successivement les ua,(6) qui ne sont pas des vecteurs directeurs d'une arête de ce cône. Ces plans sont engendrés par des couples de vecteurs indépendants pris parmi les u, (Q), et sont tels que 10 tous les autres u, (6) sont du même côté de ces plans. Il y a plusieurs cas possibles. 1. { u,,(6), a' E St K dim o-' =1} est vide, donc 1 KI (6) _ IR3 . La classe de contact de o. est donc la classe de label 0. 2. {u,,(6), crie StKQ, dim6 =1} ne possèdent pas de vecteurs 15 indépendants. Deux sous-cas se présentent : a. Tous les u,,(6) sont de même sens. Dans ce cas ill suffit d'en retenir un seul et le label de la classe de contact de o- est 0. b. Il existe des u,,(6) de sens opposé. Alors le cône engendré par les ua (o-) est une droite vectorielle et la classe de 20 contact de 6 est de label 1. 3. Il existe un plan engendré par une paire de vecteurs uc,(Q) indépendants qui permet de mettre tous les autres uoi(cr) dans un même demi-espace ouvert. On peut alors montrer que le cône convexe engendré par les u,,(6) ne contient aucune droite 25 vectorielle. Il faut alors chercher les autres couples vecteurs u,,(6) qui engendrent des plans satisfaisant à la même propriété. Les vecteurs concernés peuvent être ordonnés de manière circulaire, les autres sont dans l'intérieur du cône et ne font pas partie de la représentation minimale recherchée. La classe de contact de 6 est 30 de label 0. 4. Il existe un plan engendré par une paire de vecteurs u,,(6) indépendants qui permet de mettre tous les autres uQ (cr) dans un même demi-espace fermé, mais pas dans un même demi-espace ouvert. Dans ce plan se trouvent alors au moins trois uc.,(o-) . Trois 35 cas se présentent : 25 2906388 26 a. les u,,(o) contenus dans ce plan engendrent un cône convexe qui est égal à ce plan. Alors deux cas se présentent à nouveau : i. Il existe des ua,(o-) qui ne sont pas dans ce plan. Le 5 cône convexe recherché est en fait un demi-espace délimité par le plan trouvé et la classe de contact de a est de label 3. ii. Tous les ua (6) sont dans le plan trouvé. Le cône convexe recherché est égal à ce plan et la classe de 10 contact de Q est de label 4. b. les u,,(6) contenus dans ce plan engendrent un cône convexe qui est égal à un demi-plan fermé. Alors deux cas se présentent à nouveau : i. Il existe des u,,(6) qui ne sont pas dans ce plan. 15 Alors le cône convexe engendré par les u,,(6) a exactement deux faces, et il reste un plan exactement à trouver. La classe de contact de o- est de label 1. ii. Tous les ua,(o-) sont dans ce plan. Le cône convexe recherché est exactement égal au demi-plan fermé 20 rencontré et la classe de contact de o- est de label 1. c. les ua,(o-) contenus dans ce plan engendrent un cône convexe qui est un secteur angulaire plan strictement inclus dans un demi-plan. Alors seuls les vecteurs arêtes de ce secteur sont à retenir, et on se ramène au cas 3. 25 5. Aucun plan engendré par les paires de u,,(o-) ne permet de mettre tous les u,,(Q) dans un même demi-espace. Alors les u,,(6) engendrent un cône convexe qui est en fait tout R3, et on a u1K~ (Q) = 0 . La classe de contact de o- est de label 7. 30 On décrira maintenant une deuxième étape du prétraitement selon le procédé conforme à l'invention. Cette deuxième étape concerne la construction de la hiérarchie de volumes englobants. Plusieurs approches sont possibles pour la construction de la hiérarchie de volumes englobants. Principalement, on distingue 35 classiquement les approches par subdivision successive (ou top-down ) et par agrégation (ou bottom-up ). On notera que le document [1] 2906388 27 s'appuie sur la librairie PQP (voir les documents [4] et [5]) pour réaliser cette tâche. Or PQP ne s'appuie que sur la position des primitives géométriques (points, arêtes, triangles) pour la construction d'une hiérarchie, et n'utilise pas les normales associées. 5 L'invention propose d'utiliser à la fois la position des faces a du complexe simplicial et les ensembles de normales nlKl(6) associés. Pour cela, il peut être utile de calculer préalablement un cône de révolution englobant pour chaque nlKl(o), ce qui n'implique que des calculs géométrique élémentaires et ne pose pas de difficultés particulières à 10 l'homme de l'art. L'invention propose les étapes qui suivent, qui ont pour but la construction d'une hiérarchie (au sens ensembliste) de la partition du corps de K formée par les intérieurs simpliciaux de ses faces. C'est un procédé top-down , qui agit récursivement par subdivision d'ensembles 15 d'éléments de cette partition, en partant de l'ensemble de tous les éléments de la partition qui sera donc associé à la racine de l'arbre. Le critère d'arrêt des itérations correspond au traitement des ensembles d'éléments de la partition de cardinal 1 (les singletons, c'est-à-dire un seul Int Q) qui se retrouvent associés aux feuilles de l'arbre. 20 Le procédé de subdivision prend la forme suivante : alternativement (ou selon une heuristique qui dépend du contexte d'utilisation) au sens de la position et de l'orientation, on réalise des subdivisions selon le critère classique de la médiane selon l'axe de plus grande inertie (voir par exemple le document [1]). Au sens de la 25 position doit être compris comme l'utilisation des barycentres des o' . Au sens de l'orientation doit être compris comme l'utilisation des axes des cônes des révolution qui englobent les 1,1(a). Expérimentalement, une heuristique efficace est de réaliser les 3 ou 4 premières subdivisions selon la position, puis d'alterner entre position 30 et orientation (stratégie de subdivision dite splitting ). Une fois la hiérarchie construite, il suffit de calculer des volumes englobants pour chaque noeud de la hiérarchie. En ce qui concerne les sphères qui englobent les positions des faces associées à un noeud, deux stratégies sont possibles : 35 1. Calculer la sphère de rayon minimal qui englobe les faces; associées à chaque noeud. 2906388 28 2. Calculer des sphères minimales pour les feuilles de l'arbre, puis remonter successivement dans l'arbre par inclusion hiérarchique des sphères englobantes. Dans les deux cas de figure, des méthodes classiques existent 5 et sont disponibles dans la littérature. Dans le cas rigide, la solution 1 est plus efficace. Dans le cas déformable, la recherche d'efficacité dans la remise à jour de la hiérarchie de volume englobant privilégie une solution hybride : utiliser la solution 1 pour le bas de l'arbre, la solution 2 pour le haut . La distinction entre le haut et le bas de l'arbre peut se faire 10 sur un critère de profondeur des noeuds, avec un seuil de profondeur à régler expérimentalement. En ce qui concerne les cônes de révolution qui doivent englober les ensembles de normales des faces qui sont associées aux noeuds, une solution analogue à la solution 2 pour les solutions a l'avantage de la 15 simplicité d'implémentation (il suffit de calculer des cônes qui englobent simplement des paires de cône). Sur le plan de l'efficacité, il est également intéressant de remonter dans la hiérarchie de volumes englobants l'information d'appartenance de faces aux différentes classes de contact, comme 20 annoncé plus haut. Cette remontée d'information permet de durcir les tests noeud à noeud qui seront décrits ci-dessous, et donc de rendre les descentes de hiérarchies plus sélectives, donc plus rapides. Cette remontée ne pose pas de problème particulier. Il suffit d'associer à chaque noeud une collection de huit valeurs booléennes qui indiquent, pour 25 chacune des huit classes, l'existence parmi les faces associées au noeud d'au moins une face appartenant à la classe. On remarque enfin que, dans le cas rigide uniquement, la classe de chaque face est définitivement déterminée à l'initialisation. Par conséquent, comme cela sera expliqué ci-dessous, les faces appartenant à 30 la classe de label 7 peuvent être omises car elles ne peuvent être le support d'une LMD, ni même d'une quasi-LMD. On décrira maintenant une étape du procédé selon l'invention qui suit le prétraitement et consiste en l'étape de calcul des (quasi)-ILMD. On introduit ici deux paramètres de la méthode qui peuvent être 35 modifiés au besoin entre deux requêtes et dont la modification n'invalide pas l'étape de pré-calcul précédente. 2906388 29 Le premier paramètre, noté y., est une valeur angulaire positive ou nulle qui permet de définir la notion de quasi-LMD (toute LMD est une quasi-LMD). Le deuxième paramètre, noté d,nat, est un seuil de distance (positive ou nulle, éventuellement infinie) qui permet de 5 restreindre le calcul des quasi-LMD aux seules quasi-LMD dont la valeur est inférieure à ce seuil. On considère dans la suite deux complexes simpliciaux K, et K2. L'opération qui est décrite ici pour une paire de complexes doit être appliquée à chaque paire de complexes distincts parmi les complexes 10 donnés en entrée. Cette étape de l'invention est analogue à celle de la méthode proposée dans le document [1] mais introduit les extensions suivantes : • Les tests noeud à noeud prennent en compte les dilations éventuelles appliquées aux complexes K, et K2, de valeurs 15 respectives e, et e2. Le test sur la position relative des noeud consiste donc à vérifier que les centres des sphères englobantes associées sont distants d'au plus R, +R2 +e, +e2 +d,,,, où R, et R2 sont les rayons des sphères. En revanche, le cône dual (selon le document [1]) se base sur les sphères non dilatées. 20 • Les tests noeud à noeud prennent en compte la tolérance au désalignement yn . Par conséquent, dans les tests d'intersection des différents cônes, les cônes de révolution qui englobent les normales doivent être remplacés par des cônes de même axe dont la demi-ouverture au sommet est augmentée de yr, . 25 • Les tests noeud à noeud comportent un test supplémentaire basé sur les classes de contact. Supposons que les deux noeuds à tester comportent des vecteurs de booléens d'appartenance de leurs faces aux classes de contact notés c, et c2. La rème composante d'un tel vecteur est un booléen qui indique s'il existe parmi les faces 30 associées au noeud au moins une face appartenant à la classe de label i. Le test consiste à évaluer le booléen c,TCc2, où C est la matrice symétrique booléenne suivante, appelée matrice de compatibilité entre classes de contact : 2906388 30 '1 1 1 1 1 1 1 0\ 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 C= 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0, • le test étant validé si et seulement si la valeur booléenne résultante 5 est 1. • Les tests feuille à feuilleprennent en compte les dilatations des complexes et la tolérance au désalignement yä, . Le principe pour réaliser ces tests est de calculer d'abord l'unique LMD entre les espaces affines engendrés par les deux faces testées (comme 10 expliqué plus haut, les cas de parallélisme sont rejetés sans préjudice), puis de vérifier que son support se situe sur le produit des intérieurs simpliciaux des faces. Ceci correspond à des calculs géométriques élémentaires que l'homme de l'art maîtrise et qui sont détaillés dans par exemple le document [6]. Si une LMD 15 (x,,x2)E Inter, xInt62 entre les intérieurs simpliciaux des faces est trouvée, il reste à vérifier, comme expliqué plus haut, que celle-ci est compatible avec les cônes de normales au sens fort associées aux intérieurs simpliciaux des faces, i.e. de tester si x2 -x, appartient à 1K,I(Int6,)et si x, ùx2 appartient à? K,I(Int6. ). Ce test 20 est facile à réaliser car l'étape de pré-calcul a permis d'obtenir une représentation de lK,i (Int or,) et de 1IK21(Int U2) sous la forme du polaire d'un ensemble fini de vecteurs du type uQ (cs) . La contrainte d'appartenance à ce cône polaire doit être assouplie pour tenir compte d'un désalignement maximal de y,ä, ce qui peut être 25 approché de manière simple en considérant non pas le cône polaire aux vecteurs u,,(6) (i.e. l'ensemble des vecteurs qui forment un angle d'au moins 2 avec chaque u~ (o) ), mais l'ensemble des vecteurs qui forment un angle d'au moins - --y,. avec chaque ua (6) . Cet assouplissement ne doit pas être fait dans tous les cas, 30 mais doit obéir aux règles fixées par le tableau 5 suivant. 2906388 31 Tableau 5 Label 0 1 2 3 4 5 6 7 de la classe de contact de 62 Label de la classe de contact de o-, 0 (0, 0) (0, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) 0 1 (0, 0) (1, 1) (1, 1) (1, 0) 0 0 0 0 2 (0, 1) (1, 1) (1, 1) (1, 0) 0 0 0 0 3 (0, 1) (0, 1) (0,1) 0 0 0 0 0 4 (0,1) 0 0 0 0 0 0 0 5 (0, 1) 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 5 Le Tableau 5 montre les règles de régularisation angulaires permettant de définir les quasi-LMD. Le tableau doit être utilisé comme un tableau à double entrée. Dans chaque case du tableau se trouvent soit un couple de valeurs booléennes, soit le symbole 0. Si un couple de valeurs booléennes est présent dans une case, la première valeur (resp. la 10 deuxième valeur) indique si le cône polaire aux vecteurs uQ (6) associé à la face o, (resp. Q2) doit être remplacé par l'ensemble décrit plus haut et 2906388 32 paramétré par la valeur de ',mar. Le symbole 0 identifie les cas qui doivent être rejetés (cas inutiles évoqués plus haut). Dans le cas des corps déformables, la géométrie des volumes englobants (sphères et cônes de révolution) doit être remise à jour après 5 modification de l'état de déformation, ce qui n'ajoute pas de difficulté car les méthodes classiques de remise à jour s'appliquent directement. Selon une variante de l'invention, on calcule non seulement les distances entre objets, pour mettre en évidence les zones de proximité, mais également les vitesses de déplacement relatifs, ce qui permet 10 d'adapter automatiquement et localement les seuils de distance. Selon une autre variante de l'invention, les calculs sont parallélisés pour exploiter au mieux une architecture parallèle, par exemple à base de processeurs mufti-coeurs, afin d'accélérer les simulations temps réel. 15 Selon une autre variante de l'invention, le procédé est généralisé aux objets représentés par un axe médian polyédrique (voir par exemple les documents [7] et [8]. Un avantage du procédé selon l'invention utilisant des quasi-LMD est d'être régularisé vis-à-vis des translations et des rotations, ce qui 20 conduit à des solutions très robustes vis-à-vis des déplacements et des rotations des objets virtuels. Le rendu graphique et/ou haptique n'est donc pas déstabilisé par l'interaction avec l'utilisateur qui est par nature peu prévisible. Un autre avantage du procédé est de permettre des calculs 25 rapides, et donc de pouvoir être intégré dans un simulateur temps réel. L'invention permet ainsi une simulation stable du comportement mécanique, sans oscillations parasites. Un exemple de réalisation du procédé selon l'invention sera présenté en référence aux Figures 3 à 7. 30 Ces Figures montrent les images de deux objets 10, 20 simulés numériquement, à savoir un cube 10 et un plan 20, mais l'invention est naturellement applicable à des objets de formes très variées. Les Figures 3 à 7 montrent diverses visualisations des zones de contact ou de proximité entre les deux objets virtuels, lorsqu'il existe un 35 mouvement relatif entre ces objets. 2906388 33 Sur les Figures 3 à 7, on a représenté un repère XYZ associé à l'objet cubique 10. Dans l'exemple considéré, on a considéré que le plan 20 est fixe et que les mouvements relatifs entre les deux objets 10 et 20 ne sont déterminés que par les déplacements (rotations ou translations) 5 de l'objet cubique 10. L'objet cubique 10 comprend une face qui présente des coins ABCD. Lorsqu'un coin A du cube 10 s'approche du plan 20 (Figure 3), on visualise la zone de contact et/ou le contact le plus proche situé dans le 10 coin A du cube 10 le plus proche du plan 20. Sur la Figure 3, ceci est matérialisé par une grande flèche FA. Lors d'une rotation du cube 10 (Figure 4), un autre coin B s'approche de la surface du plan 20. Ceci est matérialisé par une petite flèche FB. 15 On passe ensuite par une étape intermédiaire où une arête (Figure 5) (ou le cas échéant une face) du cube 10 est parallèle au plan 20. Ainsi, sur la Figure 5, tous les points de l'arête situés entre les coins A et B présentent la même distance par rapport au plan 20. Ceci est matérialisé par les grandes flèches FA, FB aux coins A et B. Le système 20 visualise alors l'arête entière (ou la face) du cube 10 qui est parallèle au plan 20. Si la rotation du cube 10 se poursuit (Figure 6), on repasse à une situation symétrique à celle du début, par exemple les coins C et D du cube 10 se rapprochent du plan 20 alors que les coins A et B restent à une 25 certaine distance du plan 20. Les petites flèches fc et fc symbolisent le rapprochement des coins C et D vers le plan 20. A la fin de cette rotation (Figure 7), dans l'exemple donné, on a la face du cube 10 délimitée par les coins A, B, C, D qui est parallèle au plan 20. Cette même distance est matérialisée par de grandes flèches FA, FB, Fc, FD aux coins A, B, C, D. 30 Selon l'art antérieur, on serait passé de manière discontinue d'un coin du cube à l'autre, avec une forte instabilité en fonction d'une petite variation angulaire du cube. Selon l'invention, on passe au contraire de manière continue d'un point A du cube 10 à l'arête AB, puis à l'autre coin B, puis à une face 35 A, B, C, D, de manière non seulement continue, mais régularisée vis-à-vis 2906388 34 de petites rotations angulaires de l'objet, et vis-à-vis de petites translations. Cet exemple permet d'illustrer l'efficacité de la solution de l'invention. En effet, dans le cas dans le cas de contact entre un objet 5 concave et un autre objet, les solutions antérieures présentent des instabilités qui se traduisent par exemple par une oscillation entre différents points de contact (cas du tabouret incliné dont le point de contact passe d'un pied à l'autre, ou du cube sur un plan). Au contraire selon l'invention, les zones de proximité sont identifiées avant et/ou après 10 un contact, ce qui supprime les instabilités liées à la détection limitée aux contacts ponctuels. On a représenté sur la Figure 8 un exemple de dispositif 100 permettant de mettre en oeuvre le procédé selon l'invention. Le dispositif comprend un module 101 permettant de 15 représenter sous une forme numérique des objets qui peuvent être définis sous la forme de complexes simpliciaux K1, K2 dans Rn où n est égal à 2 ou à 3. Le dispositif 100 de détection de collision et de construction d'informations géométriques de contact ou de proximité entre un nombre 20 fini d'objets virtuels comprend un module 110 de prétraitement et un module 120 de traitement proprement dit. Le module de prétraitement 110 pour chaque complexe simplicial K, dont les coordonnées des sommets sont données dans un système de coordonnées fixé, comprend des moyens de calcul 111, pour 25 chaque face 6 de chaque complexe simplicial K, d'une description géométrique du cône polyédrique correspondant aux normales au sens fort (Int a) associées à cette face, des moyens 112 de détermination du label de la classe de contact à laquelle appartient cette face (a) et des moyens 113 de détermination pour chaque complexe simplicial K d'un 30 arbre de volumes englobants de l'objet du complexe simplicial K à partir à la fois de la position des faces a du complexe simplicial K et des ensembles de normales au sens fort associées (a). Le module de traitement 120 comprend des moyens de calcul utilisant les résultats du module de prétraitement 110 et permet de 35 procéder à un calcul de distances minimales locales (LMD) et de quasi-distances minimales locales (quasi-LMD) de la façon exposée plus haut. 2906388 35 L'ensemble des modules 101, 110, 120 est avantageusement couplé à un solveur mécanique 130. L'ensemble des modules 101, 110, 120 et du solveur mécanique 130 est préférentiellement couplé à un périphérique 110 constitué par une 5 interface graphique utilisateur et/ou à un ou plusieurs autres périphériques 140 tels que par exemple : souris 2D classique, souris 3D à six degrés de liberté, périphérique de capture de mouvements, périphérique de réalité virtuelle, interface à retour d'effort,, interface tactile, interface sonore. 10 En effectuant une évaluation de quasi-distances minimales locales entre les objets virtuels, l'invention permet la construction d'un espace de contact régularisé entre les objets, les objets virtuels modélisant des corps solides qui peuvent être rigides ou déformables, et définis dans un espace tridimensionnel ou bidimensionnel. 15 Le problème de la détection de collisions entre des corps C1 et C22 possède plusieurs formulations, chacune d'elles correspondant à "type de requête". Les types de requête les plus fréquemment rencontrés sont les suivants : - requête d'interférence : évaluation du prédicat C1nC2 ≠ 0. 20 calcul d'interférence : détermination du compact C1nC2. Lorsque C1 et C2 sont disjoints : requête de proximité globale ou calcul de distance de séparation (ou distance minimale globale) : rechercher les couples de points (a,b)E C1xC2 qui réalisent min d(a,b). (a,b)EC1xC2 25 requête de proximité globale ou calcul des distances minimales locales : recherche de tous les minima locaux de la fonction CIxC2ù R dc, c2 (a, b) H d(a, b) Lorsque C1 et C2 sont de dimension topologique n et en 30 interférence : - Calcul de profondeur d'interpénétration globale : recherche d'un vecteur de norme minimal tel que l'image de C1 par la translation selon ce vecteur est disjointe de C2. 2906388 36 Calcul de profondeur d'interpénétration locale : même calcul, en remplaçant C1 (resp. C2) par l'intersection de C1 (resp. C2) avec un voisinage d'une composante connexe de C1nC2. Lorsque C1 et C2 sont disjoints : 5 Calcul de la date d'impact : en supposant que C1 est en mouvement par rapport à C2 selon une trajectoire paramétrée par le temps et supposant que C1 et C2 sont initialement disjoints, calculer, s'il existe, la date de l'instant le plus précoce où C1 etC2 entrent en interférence. Calcul du point d'impact : déterminer le compact C1nC2 à la date de 10 l'impact. L'invention permet de prendre en compte ces diverses requêtes et concerne plus particulièrement le calcul des distances minimales locales entre deux ensembles de primitives élémentaires : - en dimension deux, les primitives élémentaires sont le point et le 15 segment de droite (appelé arête). - en dimension deux, les primitives élémentaires sont le point, lle segment de droite (appelé arête) et le triangle. Dans le cas où l'application visée est la construction d'un espace de contact entre solides rigides ou déformables géométriquement 20 représentés par de tels ensembles, l'invention prend également en compte les problèmes : - de la régularisation de l'espace de contact construit à partir des distances minimales locales ; - de la minimisation de la dimension de cet espace dans le cas de contacts 25 glissants entre corps rigides. Si l'espace de contact n'est pas régularisé et qu'une méthode de résolution du problème de contact de type "time stepping" est utilisée, alors des instabilités peuvent être observées, notamment dans le cas de contacts conformants. La présente invention permet de résoudre ce 30 problème et de traiter le cas des contacts conformants. Dans le cas où le modèle de contact entre corps est glissant et que les corps sont rigides, la dimension de l'espace de contact peut être réduite sans changer le problème de contact. Le procédé selon l'invention permet d'apporter des 35 améliorations par rapport à l'art antérieur sous plusieurs aspects. En particulier, 2906388 37 - on calcule de manière bien définie et rigoureuse le domaine de valuation du champ de normales sur chaque primitive élémentaire ; les primitives considérées dans toute la méthode sont les points, les arêtes (privées de leurs extrémités) et les triangles (privés de leurs 5 arêtes), un volume englobant feuille ne contient qu'une seule primitive ; la construction de l'arbre de volumes englobants est réalisée de haut en bas, par division successive, basée non seulement sur la position des primitives mais aussi sur leur orientation ; les volumes englobants au sens de l'orientation sont des cônes de 10 révolution simples ou doubles ; les cas traités comprennent notamment le cas des surfaces polyédriques à bord libre en dimension trois, et le cas des courbes polygonales en dimension deux ; on peut aussi traiter le cas, en dimension trois, des volumes représentés 15 par leur enveloppe polyédrique et le cas, en dimension deux,, des aires représentées par leur contour polygonal ; - en remplaçant la condition d'intersection des cônes primaux et duaux par une condition de proximité dépendante du type de domaine, on régularise vis-à-vis des rotations les espaces de contact construits à 20 partir des distances minimales locales. Celles-ci sont alors remplacées par des quasi-distances minimales locales par rapport aux rotations. Cette notion de régularisation est l'analogue de la régularisation que constituent les distances minimales locales des contacts stricts vis-à-vis des translations ; 25 Dans le cas des corps rigides en contact glissant : en ne retenant que les quasi-distances minimales locales qui s'appuient sur des couples de primitives relativement strictement convexes, on réduit la dimension des espaces de contacts régularisés basés sur les quasi-distances minimales locales. Cette suppression est réalisée grâce à une classification des 30 primitives élémentaires selon leur nature et selon la dimension topologique de leur domaine de valuation. Une condition de compatibilité est établie entre classes de primitives. L'information de présence dans un noeud de l'arbre de primitives de chaque classe est calculée et un test de compatibilité est ajouté aux tests de proximité 35 entre noeuds lors de la descente des arbres. 2906388 Documents de référence D. Johnson and E. Cohen. Spatializecl Normal Cone Hierarchies. In Proc. 2001 ACM Symposium on Interactive 3D Graphics, Research Triangle Park, NC, March 19-21, 2001. pp. 129-134. J. R. Munkres. Elements of Algebraic Topology, Advanced Book Program, Perseus Publishing, Cambridge, Massachusetts, 1984. D. P. Bertsekas. Convex Analysis and Optimization, Athena Scientific, Belmont, Massachussetts, 2003. E. Larsen, S. Gottschalk, M. Lin, and D. Manocha. Fast Proximity Queries with Swept Sphere Volumes, Technical report TR99-018, Department of Computer Science, University of N. Carolina, Chapel Hill. [5] http://www.cs.unc.edu/NgeomjSSV/ [6] C. Ericson. Real Time Collision Detection. Elsevier, MK Press, 2005. 38 [1] [2] [3] [4] [7] [8] [9] 2906388 39 Nina Amenta, Sunghee Choi and Ravi Kolluri The Power Crust Sixth ACM Symposium on Solid Modeling and Applications 2001, pages 249-260. Nina Amenta, Sunghee Choi and Ravi Kolluri The Power Crust, unions of balls, and the medial axis transform Computation Geometry: Theory and Applications, 2001, 19(2-3), pages 127-153, (special issue on surface reconstruction). G. Zachmann, Process and device for collision detection of objects. United States Patent, No. US 6,862,026 B2, Mar. 1, 2005. REVENDICATIONS 1. Procédé de détection de collision et de construction d'informations géométriques de contact et de proximité entre au moins un premier objet polyédrique simulé numériquement (10) et au moins un deuxième objet polyédrique simulé numériquement (20), caractérisé en ce que l'on représente les premier et deuxième objets polyédriques simulés numériquement (10, 20) sous la forme de complexes simpliciaux (KI, K2) dans Rn, où Rn désigne le produit cartésien du corps des réels n fois par lui-même, avec n égal à 2 ou à 3, en ce que l'on effectue une étape de prétraitement pour chaque complexe simplicial (K) dont les coordonnées des sommets sont données dans un système de coordonnées fixé, en ce que ce prétraitement consiste au moins à calculer pour chaque face (a) de chaque complexe simplicial (K) une description géométrique du cône polyédrique correspondant aux normales au sens fort (niK1 (Int a)) associées à cette face (a), à déterminer le label de la classe de contact à laquelle appartient cette face (a) et à déterminer pour chaque complexe simplicial (K) un arbre de volumes englobants de l'objet du complexe simplicial (K) à partir à la fois de la position des faces (a) du complexe simplicial (K) et des ensembles de normales au sens fort associées (nIKI (a)), et en ce que, à partir des informations obtenues à l'issue de l'étape de prétraitement, on procède à un calcul de distances minimales locales (LMD) et de quasi-distances minimales locales (quasi-LMD), ces dernières correspondant chacune à un couple de points appartenant respectivement à des objets distincts et qui définiraient une distance minimale locale (LMD) si la position d'un objet par rapport à l'autre subissait une rotation d'un angle faible (ymax) inférieur à un seuil donné. 2. Procédé selon la revendication 1, caractérisé en ce que au moins l'un des objets polyédriques simulés numériquement (10) est rigide. 3. Procédé selon la revendication 1, caractérisé en ce que au 35 moins l'un des objets polyédriques simulés numériquement (10) est déformable. 2906388 41 4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que les étapes de prétraitement et de calcul des distances minimales locales (LMD) et des quasi-distances minimales 5 locales (quasi-LMD) sont effectuées en temps réel. 5. Système de détection de collision et de construction d'informations géométriques de contact et de proximité entre au moins un premier objet polyédrique simulé numériquement (10) et au moins un 10 deuxième objet polyédrique simulé numériquement (20), caractérisé en ce qu'il comprend des moyens (:L01) pour représenter les premier et deuxième objets polyédriques simulés numériquement (10, 20) sous la forme de complexes simpliciaux (K1, K2) dans Rn, où Rn désigne le produit cartésien du corps des réels n fois par 15 lui-même, avec n égal à 2 ou à 3, en ce qu'il comprend des moyens de prétraitement (110) pour chaque complexe simplicial (K) dont les coordonnées des sommets sont données dans un système de coordonnées fixé, en ce que ces moyens de prétraitement (110) comprennent au 20 moins des moyens de calcul (111) pour chaque face (a) de chaque complexe simplicial (K) d'une description géométrique du cône polyédrique correspondant aux normales au sens fort (niKi (Int a)) associées à cette face (a), des moyens (112) de détermination du label de la classe de contact à laquelle appartient cette face (a) et des moyens (113) de 25 détermination pour chaque complexe simplicial (K) d'un arbre de volumes englobants de l'objet du complexe simplicial (K) à partir à la fois de la position des faces (a) du complexe simplicial (K) et des ensembles de normales au sens fort associées (nIKI (a)), et en ce qu'il comprend des moyens de calcul (120) associés 30 aux moyens de prétraitement (110), pour procéder à un calcul de distances minimales locales (LMD) et de quasi-distances minimales locales (quasi-LMD), ces dernières correspondant chacune à un couple de points appartenant respectivement à des objets distincts et qui définiraient une distance minimale locale (LMD) si la position d'un objet par rapport à l'autre subissait une rotation d'un angle faible (ymax) inférieur à un seuil donné. 2906388 42 6. Système selon la revendication 5, caractérisé en ce qu'il est couplé à un solveur mécanique (130). 5 7. Système selon la revendication 6, caractérisé en ce qu'il est couplé à au moins un périphérique (140) comprenant une interface graphique utilisateur, une souris, un périphérique de capture de mouvement, une interface à retour d'effort, une interface tactile, une interface sonore.