Brevet FR2873472A1 — publié le 20060127

La présente invention concerne un procédé et un système d'identification de zones de proximité et d'évaluation de distances entre plusieurs objets simulés numériquement. Un objet est ainsi constitué par une géométrie au sein d'un environnement numérique. A titre d'exemple, la simulation interactive du monde réel au sein d'un environnement numérique est dénommée "réalité virtuelle" (RV). Une plate-forme de réalité virtuelle (Figure 1) comprend des interfaces 10 entre l'environnement virtuel et le ou les opérateurs participant à la simulation. Il existe plusieurs types d'interfaces, chacune étant destinée à la stimulation de l'un des sens du ou des opérateurs. On peut ainsi mettre en oeuvre dans une plate-forme RV par exemple des interfaces visuelles 11, auditives 12, haptiques 13. Une plate-forme RV comprend en outre un simulateur dynamique 20 qui a pour fonction de régir en temps réel l'évolution des composantes de l'environnement virtuel selon les lois de la physique, ainsi que leurs interactions. Ces interactions peuvent être bilatérales (liaisons mécaniques) ou unilatérales (collision). Un simulateur dynamique 20 est assimilable à un moteur physique dont le rôle va être de régir l'évolution d'un monde virtuel composé d'objets ayant des propriétés dynamiques et géométriques. Cette tâche est décomposable en deux sous-tâches: la gestion de la dynamique du monde virtuel (moteur dynamique 21) et la gestion des collisions qui ont lieu en son sein (moteur de collisions 22). La gestion de la dynamique du monde virtuel permet de régir l'évolution individuelle des objets contenus dans le monde virtuel selon les lois de la physique. 2873472 2 La Figure 2 illustre le schéma de fonctionnement d'un moteur dynamique 21 dans le cas d'un seul objet. La première étape 211 consiste à faire un bilan des efforts appliqués à l'objet virtuel. Ces efforts auxquels est soumis l'objet peuvent être de plusieurs origines: gravité, contraintes articulaires (également appelées liaisons bilatérales), manipulation de l'opérateur. Leur accumulation va permettre d'obtenir un torseur statique d'effort. Durant la deuxième étape 212 vont être déterminées les accélérations linéaire et angulaire de l'objet par application du principe fondamental de la dynamique (PFD). Les nouvelles position et orientation sont alors directement déterminées par double intégration durant la troisième étape 213. Il paraît intéressant d'observer que le fait d'évoluer en temps discrets impose d'approximer l'intégration. Pour cela, plusieurs méthodes sont envisageables (Euler, Tustin, Runge-Kutta,...). La dernière étape 214 consiste simplement à mettre à jour les position et orientation de l'objet considéré. Le moteur 1 de collisions 22 assure une tâche qui est décomposable en deux phases: détection des collisions et génération des forces de contact. La détection des collisions peut être effectuée selon plusieurs techniques en fonction du type de géométrie utilisée et des performances escomptées. Dans le cadre des méthodes discrètes, qui constituent la grande majorité des techniques utilisées, cette première phase consiste à détecter les interpénétrations entre les différentes paires d'objets à chaque instant. A contrario, les méthodes continues détectent l'instant exact du premier contact entre objets. Quelle que soit la méthode utilisée, cette première phase s'avère la plus lourde des tâches à effectuer par le simulateur dynamique. En effet, la quantité de calculs à effectuer dans le cadre de cette détection est directement liée à la nature des objets évoluant au sein du monde virtuel, particulièrement en termes de complexités géométriques. 2873472 3 Après cette première phase de détection des collisions, il reste à déterminer les efforts résultant des collisions entre les paires de solides concernées. Ces derniers sont généralement décomposés en une force normale de réaction et une force tangentielle de frottement. Il est ainsi nécessaire de modéliser ces collisions. Pour ce faire, trois méthodes sont principalement utilisées: pénalité, impulsion et contrainte. Dans le cadre de simulations dynamiques destinées à fonctionner en temps réel, la gestion des contraintes unilatérales (collisions), que ce soit en termes de détection ou de calcul des forces de contact, engendre une limitation de la complexité géométrique des composants du monde virtuel (nature, nombre et type d'entités élémentaires). On entend par nature de l'objet l'ensemble de ses propriétés de convexité (convexe/concave) et de rigidité (infiniment rigide/déformable). Les entités élémentaires permettant la définition géométrique d'un objet peuvent être de plusieurs types: maillages (triangles, quads), voxels, points, surfaces analytiques. Les principales techniques permettant la détection de collisions entre objets dynamiques sont présentées ci-dessous. La localisation des zones susceptibles d'entrer en collision se retrouve dans les techniques de détection de collisions classiques et, plus particulièrement, dans les optimisations apportées à celle-ci. Ainsi, trois grandes stratégies pouvant répondre à ce besoin émergent de la littérature scientifique: le calcul de la distance minimale entre objets, les hiérarchies de volumes englobants, la considération des volumes balayés durant le mouvement. La première technique va ainsi consister à calculer, à tout moment, la distance minimum entre deux objets E1 et E2 de type polyédrique et ainsi connaître les éléments géométriques el, e2 les plus proches (voir Figure 3). Plusieurs approches ont ainsi été mises en oeuvre afin d'obtenir cette distance minimum ainsi que les éléments géométriques concernés. La plupart de ces techniques considèrent des objets convexes. Ces dernières pourront tout de même s'avérer utilisables dans le cadre de 2873472 4 simulations faisant intervenir des objets concaves par décomposition de ces derniers en éléments convexes. Un premier procédé permettant la détermination de cette distance minimum et des éléments concernés fût introduit par Gilbert, Johnson et Keerthi. Ce procédé, basé sur la différence de Minkowsky et l'optimisation convexe, permet de déterminer la distance entre deux enveloppes convexes de deux ensembles de points El et E2 et a au pire des cas pour complexité o((n+m)2), n et m étant le nombre de points contenus respectivement dans El et E2. Cependant, il est possible d'optimiser ce procédé en se basant sur les résultats obtenus lors des itérations précédentes et ainsi réduire la complexité à 0(n). Ce procédé ne prend pas en compte la nature des objets considérés et l'évolution de leur géométrie. Il est ainsi utilisé au sein de procédés faisant intervenir des objets autres que rigides et convexes. Lin et Canny introduisent un procédé de calcul permettant la détermination, en temps linéaire, des deux points les plus proches de deux maillages non-déformables convexes. Ce procédé est basé sur le concept de cohérence spatiale et temporelle. Le monde virtuel évoluant selon un modèle dynamique, le déplacement d'un objet durant un pas de temps est infinitésimal, ce qui laisse espérer que, à un cycle donné, les points les plus proches appartiennent au voisinage des points les plus proches au cycle précédent. Ce procédé sous-entendant un changement "continu" des zones d'intérêt sur les maillages considérés, il peut être optimisé via une approche multirésolution permettant d'accélérer le "déplacement du calcul" au sein du maillage, telle que celle proposée par Dobkin et Kirkpatrick. Une deuxième approche prenant en compte une hiérarchie de volumes englobant consiste à partitionner les espaces occupés par les objets composant la scène. Ainsi, chaque objet va être approximé par un volume englobant lui-même décomposé en une arborescence de sous- volumes (généralement de topologie similaire au volume englobant "racine"). La stratégie consiste à effectuer une localisation spatiale des zones susceptibles de s'interpénétrer. En pratique, on teste la présence de 2873472 5 chevauchement des volumes englobants d'objets distincts, puis, dans l'hypothèse d'un chevauchement, on effectue un test récursif similaire au niveau des sous-volumes qu'ils contiennent. Cette stratégie permet d'éviter une multitude de tests non-pertinents et se voit très utilisée au sein des moteurs physiques existants. Cependant, ces tests de chevauchement peuvent s'avérer très nombreux dans certains cas (plan/plan par exemple) et ainsi compromettre les performances de la simulation. De plus, la mise à jour de ces volumes (mouvement, déformation) peut s'avérer coûteuse. Plusieurs types de géométries peuvent être utilisés dans le cadre de cette segmentation de l'espace. Les plus communément utilisés sont les sphères 1, les boîtes englobantes isothétiques 2 (AABB) et les boîtes englobantes orientées 3 (OBB) (voir Figures 4a, 4b, 4c). Chacun de ces types de volumes englobants se voit plus ou moins adapté en fonction de la géométrie considérée et du niveau de performance escompté. Ainsi, les sphères englobantes ont pour principal avantage la simplicité des tests de chevauchement. En effet, le test de chevauchement de deux sphères se limite à une comparaison entre la distance séparant leur centre et la somme de leurs rayons respectifs. Cependant, les sphères donnent généralement une approximation moins optimale de la géométrie considérée, en comparaison avec les OBBs par exemple qui, malgré des tests de chevauchement beaucoup plus lourds (théorème des axes séparateurs), limitent l'exécution de tests nonpertinents de par un volume englobé minimal. Architecturalement, les hiérarchies de volumes englobants se présentent sous forme d'arbres, souvent binaires afin d'optimiser leur parcours. On parle également d'Octrees (8 branches / noeud), ou encore de Quadtrees (4 branches / noeud davantage adapté aux géométries 2D). Le volume balayé par un solide en mouvement durant un intervalle de temps correspond à l'union des zones de l'espace qu'il a occupées au cours de cette période. Cet outil géométrique a plusieurs domaines d'application: évaluation d'espace de travail en robotique, modélisation géométrique en CAO. Le volume balayé par une sphère 2873472 6 durant une translation est illustré à titre d'exemple sur les Figures 5a et 5b qui illustrent respectivement les positions initiale 4 et finale 5 de l'objet et le volume balayé correspondant 6. En considérant la cinématique des objets rigides qui évoluent au sein de la simulation à un instant to ainsi que leur géométrie, il est envisageable d'évaluer les volumes qu'ils sont susceptibles de balayer à un horizon tn, n>O, et ainsi anticiper leurs interactions en déterminant les intersections entre leurs volumes balayés respectifs. Plusieurs procédés sont décrits dans la littérature. On peut citer par exemple les nombreux travaux de K. Abdel-Malek et al. Un procédé particulièrement intéressant est également présenté par Y J. Kim et al. Ce dernier permet d'identifier de manière rapide et robuste le volume balayé par un polyèdre de complexité relativement importante (milliers de facettes). En plus d'une algorithmique sophistiquée, il utilise le matériel ce qui lui permet d'atteindre un niveau de performance très élevé et utilisable dans le cadre d'une simulation temps réel. Les voxels sont parfois utilisés afin de définir de manière discrète une géométrie quelconque. Le principe est d'identifier et englober les zones de l'espace occupées par de la matière à l'aide de cubes de tailles variables en fonction du degré de résolution escompté (voir Figure 6). Les techniques présentées ci-dessus de hiérarchie de volumes englobants et de volumes balayés sont également applicables dans le cadre d'optimisation de ce type d'approche voxélique. On peut citer en particulier une technique basée sur une discrétisation hybride utilisant des voxels (ou "voxmap") et l'association de nuage de points (ou "point shell") et de normales. Cette technique est illustrée sur les Figures 7a et 7b. La Figure 7a montre un premier objet original 8 représenté sous forme de voxels 8a et un deuxième objet original 9 représenté sous forme 30 de nuage de points et de normales 9a. La Figure 7b montre le détail d'une interaction entre un voxel 8a d'une surface statique de l'objet 8 et le nuage de points de l'objet 9 avec 2873472 7 le plan tangent 9b à la surface statique et le vecteur force 9a selon la normale au nuage de points de l'objet 9. Cette technique de discrétisation hybride nécessite une phase de précalculs relativement longue mais permet de gérer des données 5 géométriques complexes. Selon une approche analytique, deux autres types de modèles incluent les surfaces implicites et les surfaces paramétriques. Les premières utilisent des fonctions implicites qui définissent des formes dans l'espace. Les surfaces implicites sont l'ensemble des points pour lesquels on a f (x, y, z) = 0, l'intérieur du modèle étant les points pour lesquels f (x, y, z) Pour ces deux méthodes de modélisation, résoudre des problèmes de collision revient donc à manipuler ces fonctions. Ces types de définitions géométriques sont très peu utilisées. Les objets quelconques (non-issus de primitives) et complexes se voient en effet très difficilement représentables de cette manière, particulièrement dans le cas de zones saillantes (discontinuité) très présentes dans les pièces mécaniques par exemple. Une fois les zones d'interpénétration identifiées, il reste à déterminer les forces de contact, soit, en d'autres termes, les efforts de répulsion qui vont permettre de ramener les objets interpénétrés à un simple état de contact. Pour ce faire, trois méthodes émergent de la littérature scientifique: la méthode des contraintes, la méthode d'impulsion et la méthode de pénalité. La méthode des contraintes consiste à prendre explicitement en compte les contraintes de non-interpénétration au niveau des équations du mouvement propres à chacun des objets. Cette contrainte s'exprime comme suit: p(t) = f (force) C(p(t)) 0 2873472 8 où la première équation caractérise le mouvement de chaque objet en fonction des efforts qui lui sont appliqués et la deuxième les contraintes de non-interpénétration. Cette méthode est particulièrement intéressante dans le cas où les collisions ne sont pas très fréquentes (le calcul de collision, soit la détermination de C(p(t), est coûteux) et en l'absence de frottements. Elle a l'avantage de ne pas avoir d'effets néfastes sur la stabilité du système global. La méthode d'impulsion est une approche cinématique qui assimile l'interaction entre deux objets rigides à un impact. La collision est ainsi considérée comme un événement quasi-instantané générant un effort important (dit impulsion) sur les objets concernés. On a ainsi la relation suivante entre les vitesses avant et après impact: vo = e vl où e est appelé coefficient de restitution (e=0: collision élastique, e=1: collision plastique). e est calculable via l'hypothèse de Poisson: P e = r PC Lorsque deux objets sont suffisamment proches, l'impulsion est calculée de manière à les séparer en une seule itération. On pose souvent la condition que les objets concernés ont une trajectoire balistique afin d'optimiser les calculs. La méthode de pénalité permet de gérer les efforts de répulsion entre des objets rigides ou déformables. Elle consiste à appliquer aux objets en collision 14, 15 un effort proportionnel à la profondeur d'interpénétration (on parle de raideur). Le mécanisme de répulsion est ainsi souvent assimilé à un système 16 de type proportionnel dérivé (voir Figure 8). Cette méthode nécessite de connaître le vecteur de pénétration (ce qui peut s'avérer coûteux) et génère bien souvent des instabilités (particulièrement dans les cas de collisions multipoints). 2873472 9 Il ressort de ce qui précède que l'évaluation des distances et l'identification des zones de proximité, et le cas échéant la détection des collisions, entre objets géométriques évoluant au sein d'un environnement numérique, se voit être une étape essentielle dans un grand nombre de disciplines, telles que par exemple la réalité virtuelle ou la scénarisation de déplacements de systèmes robotiques. Toutefois, notamment du fait de leur coût en terme de temps de calcul, les différents procédés utilisés à ce jour se voient souvent inutilisables dans le cadre de simulations faisant intervenir des géométries complexes et nécessitant de hauts niveaux de performances. La présente invention vise à remédier aux inconvénients de l'art antérieur et à permettre de répondre à la plupart des problématiques récurrentes dans l'évaluation des distances ou l'identification des zones de proximité, et notamment dans la détection de collisions en fournissant des solutions avec des temps de calcul réduits compatibles avec des applications en temps réel, avec un haut degré de performances et une simplicité de mise en oeuvre, même lorsque les objets en interaction présentent des géométries complexes ou des natures ou qualités différentes. Ces buts sont atteints, conformément à l'invention, grâce à un procédé d'identification de zones de proximité entre au moins des premier et deuxième objets simulés numériquement, caractérisé en ce qu'il comprend les étapes suivantes: (a) on fournit des données décrivant la géométrie de chacun des premier et deuxième objets simulés numériquement et on stocke ces données en mémoire, (b) on crée une population constituée par un ensemble de N individus appelés pions définis chacun par des premier et second nucléons eux- mêmes définis comme des points appartenant respectivement aux géométries de chacun des premier et deuxième objets, (c) on organise des sessions d'un tournoi au sein des N pions de la population créée, où durant chacune des sessions un pourcentage de 2873472 - 10 - la population est soumis à des combats au cours desquels on évalue pour chaque paire de pions soumis à un combat, en fonction d'une évaluation de la qualité définie à partir d'un critère d'aptitude, lequel a gagné et lequel a perdu et on identifie le gagnant et le perdant par un marquage qui est différent à l'issue de chaque session du tournoi, (d) après le tournoi, on procède à une mutation exploratoire des pions ayant perdu durant une première session, on procède à un remplacement des pions ayant perdu durant une deuxième session, par croisement de pions choisis aléatoirement et on procède à une redéfinition aléatoire des pions ayant perdu durant une troisième session, (e) pour l'exploitation des pions devant servir à déterminer des zones de proximité entre les premier et deuxième objets, on considère uniquement la population des vainqueurs des combats, (f) on exécute à nouveau les étapes (c), (d) et (e) de façon répétitive, et (g) on extrait à la demande des informations géométriques à partir d'une configuration actualisée de la population de pions, durant l'exécution répétitive. Au cours de l'étape d'extraction des informations géométriques, on peut évaluer les distances entre les zones de proximité identifiées. Les données permettant d'identifier des zones de l'espace décrivant la géométrie d'au moins l'un des premier et deuxième objets simulés numériquement peuvent comprendre des représentations polyédriques, des représentations voxéliques, des représentations par surfaces paramétrées ou encore des nuages de points. Selon une caractéristique particulière, le critère d'aptitude permettant d'évaluer la qualité d'un pion est constitué par une mesure de la distance séparant les premier et second nucléons définissant ce pion, la qualité du pion étant d'autant plus grande que la distance mesurée est plus faible. Cette mesure de la distance peut par exemple prendre en compte le carré de la distance séparant les premier et second nucléons définissant le pion. 2873472 - 11 - Le procédé selon l'invention peut en outre comprendre après l'étape (a) de fourniture de données décrivant la géométrie de chacun des premier et deuxième objets simulés numériquement, les étapes suivantes: (a1) on crée une carte de connectivité contenant des informations définissant les propriétés de voisinage entre éléments géométriques au sein des premier et deuxième objets et on stocke en mémoire les informations de cette carte de connectivité, (a2) on crée une carte de proximité contenant des informations définissant les propriétés de proximité au sein des premier et deuxième objets et on stocke en mémoire les informations de cette carte de proximité. Avantageusement, la mutation des pions ayant perdu durant une session du tournoi engendrant des mutations exploratoires pour les pions ayant perdu consiste à déplacer les premier et second nucléons composant un pion sur la surface des premier et deuxième objets auxquels ces premier et second nucléons appartiennent respectivement. Selon un mode de réalisation particulier, lors de la mutation d'un pion ayant perdu durant une session du tournoi, engendrant des mutations exploratoires pour les pions ayant perdu, au moins l'un des premier et second nucléons composant ce pion et appartenant à l'un des premier et deuxième objets représentés sous une forme polyédrique est soumis à une succession de déplacements discrets de centre de facette en centre de facette en considérant les informations définissant les propriétés de voisinage stockées en mémoire. Selon un autre mode de réalisation particulier, lors de la mutation d'un pion vainqueur au cours du tournoi, au moins l'un des premier et second nucléons composant ce pion et appartenant à l'un des premier et deuxième objets représentés sous une forme polyédrique est soumis à un déplacement sur une même facette sur un disque ayant pour centre la position initiale de ce point et pour rayon une amplitude de déplacement 2873472 - 12 maximum qui dépend de l'aire de la facette sur laquelle est effectué le déplacement. Selon encore un autre mode de réalisation particulier, lors de la mutation d'un pion vainqueur au cours du tournoi, au moins l'un des premier et second nucléons composant ce pion et appartenant à l'un des premier et deuxième objets représentés sous une forme polyédrique est soumis à un déplacement sous forme de "trou de vers" d'un sommet d'une facette vers un autre sommet proche d'une autre facette qui n'est pas nécessairement connexe, en considérant les informations définissant les propriétés de proximité stockées en mémoire. Selon encore un autre mode de réalisation particulier, lors de la mutation d'un pion vainqueur au cours du tournoi, les premier et second nucléons composant ce pion et appartenant respectivement aux premier et deuxième objets représentés chacun sous une forme polyédrique avec des facettes triangulaires, sont positionnés de telle sorte qu'ils délimitent un segment définissant la distance minimum entre les deux facettes triangulaires auxquelles ces premier et second nucléons appartiennent respectivement. Avantageusement, lors du remplacement d'un pion ayant perdu durant une session du tournoi engendrant pour les pions ayant perdu des remplacements par croisement de pions choisis aléatoirement, pour définir le nouveau pion résultant du croisement d'un premier et d'un deuxième pions choisis aléatoirement, on considère que le nouveau pion se compose du premier nucléon du premier pion choisi aléatoirement et du second nucléon du deuxième pion choisi aléatoirement. L'invention concerne de façon plus générale un procédé appliqué à un ensemble de P objets simulés numériquement avec P>2, caractérisé en ce qu'il comprend les étapes suivantes: (a) on fournit des données décrivant la géométrie de chacun des P objets 30 simulés graphiquement, (b) on crée une population constituée par un ensemble de N individus appelés pions définis chacun par des premier et second nucléons eux- 2873472 - 13 mêmes définis comme des points appartenant respectivement aux géométries de l'un des P objets et d'un autre des P objets, (c) on organise des sessions d'un tournoi au sein des N pions de la population créée, où durant chacune des sessions un pourcentage de la population est soumis à des combats au cours desquels on évalue pour chaque paire de pions soumis à un combat, en fonction d'une évaluation de la qualité définie à partir d'un critère d'aptitude, lequel a gagné et lequel a perdu et on identifie le gagnant et le perdant par un marquage qui est différent à l'issue de chaque session du tournoi, (d) après le tournoi, on procède à une mutation exploratoire des pions ayant perdu durant une première session, on procède à un remplacement des pions ayant perdu durant une deuxième session, par croisement de pions choisis aléatoirement et on procède à une redéfinition aléatoire des pions ayant perdu durant une troisième session, (e) pour l'exploitation des pions devant servir à déterminer des zones de proximité entre deux des P objets, on considère uniquement la population des vainqueurs des combats, (f) on exécute à nouveau les étapes (c), (d) et (e) de façon répétitive, et (g) on extrait à la demande des informations géométriques à partir d'une configuration actualisée de la population de pions, durant l'exécution répétitive. Dans le cas où les données permettant d'identifier des zones de l'espace décrivant la géométrie des P objets simulés numériquement comprennent des représentations polyédriques, le procédé comprend avantageusement les étapes additionnelles suivantes après l'étape (a) de fourniture de données décrivant la géométrie des P objets simulés numériquement: (ai) on crée une carte de connectivité contenant des informations définissant les propriétés de voisinage entre éléments géométriques au sein de chacun des P objets et on stocke en mémoire les informations de cette carte de connectivité, 2873472 - 14 - (a2) on crée une carte de proximité contenant des informations définissant les propriétés de proximité au sein de chacun des P objets et on stocke en mémoire les informations de cette carte de proximité. L'invention a encore pour objet un système d'identification de zones de proximité entre un nombre P d'objets simulés numériquement avec P>_2, caractérisé en ce qu'il comprend: (a) des premiers moyens de mémoire pour stocker des données décrivant la géométrie de chacun des P objets, (b) un module d'initialisation pour créer une population constituée par un ensemble de N individus appelés pions définis chacun par des premier et second nucléons eux-mêmes définis comme des points appartenant respectivement aux géométries de l'un des P objets et d'un autre des P objets, (c) une unité centrale de traitement comprenant au moins: (cl) des moyens de sélection d'un pourcentage de la population des N pions devant être soumis à des combats par paires au cours d'une session d'un tournoi, (c2) des moyens de comparaison et de calcul pour évaluer au cours d'une session d'un tournoi, pour chaque paire de pions soumis à un combat, la qualité de chacun des pions de la paire de pions à partir d'un critère d'aptitude, (c3) des moyens de marquage, pour identifier à chaque session du tournoi lequel des pions d'une paire de pions soumis à un combat a gagné, et lequel des pions de ladite paire de pions soumis à un combat a perdu, (c4) des moyens d'itération pour produire une évolution des pions qui ont subi au moins un combat, ces moyens d'itération étant associés aumoins à un opérateur de mutation exploratoire des pions ayant perdu pendant une première session du tournoi, à un 2873472 - 15 - opérateur de remplacement des pions ayant perdu durant une deuxième session du tournoi par croisement de pions choisis aléatoirement et à un opérateur de redéfinition des pions ayant perdu durant une troisième session du tournoi, et (c5) un module d'extraction pour ne retenir que les meilleurs pions de la population en fonction du critère d'aptitude, pour la détermination des zones de proximité entre au moins deux des P objets. Le système peut en outre comprendre: (a1) des deuxièmes moyens de mémoire pour stocker des informations représentant une carte de connectivité et définissant les propriétés du voisinage entre éléments géométriques au sein de chacun des P objets, (a2) des troisièmes moyens de mémoire pour stocker des informations représentant une carte de proximité et définissant les propriétés de proximité au sein de chacun des P objets. L'unité centrale de traitement peut comprendre un ensemble d'unités de calcul fonctionnant en parallèle. Le procédé et le système selon l'invention se fondent ainsi sur un 20 processus évolutionnaire basé sur une approche stochastique. Ce processus évolutionnaire traite de populations d'individus définis par des composantes réelles et non simplement de manière binaire. D'autres caractéristiques et avantages de l'invention ressortiront de la description suivante de modes particuliers de réalisation, donnés à 25 titre d'exemples non limitatifs, en référence aux dessins annexés, sur lesquels: - la Figure 1 est un schéma-bloc représentant l'architecture fonctionnelle d'une plate-forme de réalité virtuelle, - la Figure 2 est un organigramme montrant le schéma d'évolution 30 dynamique d'un objet contenu dans le monde virtuel selon les lois de la physique, 2873472 - 16 - - la Figure 3 est un schéma illustrant un procédé connu de calcul de la distance minimale entre deux objets de type polyédrique, - les Figures 4a, 4b et 4c montrent trois exemples d'approximation d'un objet par un volume englobant, - la Figure 5a illustre des positions initiale et finale d'un objet sphérique en translation, - la Figure 5b illustre le volume balayé correspondant à la translation de l'objet de la Figure 5a, - la Figure 6 illustre un exemple de décomposition voxélique d'un objet, - la Figure 7a montre un exemple de représentation hybride d'un objet sous forme de voxels coopérant avec un autre objet représenté sous la forme d'un nuage de points et de normales, - la Figure 7b représente le détail d'une zone d'interaction des 15 deux objets représentés de façon hybride sur la Figure 7a, - la Figure 8 illustre la représentation de deux objets soumis à des efforts de répulsion selon la méthode de pénalité, - la Figure 9 est un schéma illustrant le génotype d'un individu ou pion utilisé dans le cadre de l'invention, - la Figure 10 illustre un exemple de déplacement exploratoire discret d'un point sur un polyèdre, dans le cadre d'une mutation, - la Figure 11 montre un exemple d'opérateur d'exploitation intervenant dans le cadre d'une mutation, - la Figure 12a illustre un processus d'identification des éléments proches dans le cadre d'objets représentés sous une forme polyédrique, - la Figure 12b illustre un exemple de parcours sans trou de vers dans l'objet représenté sur la Figure 12a, - la Figure 12c illustre un exemple de parcours via un trou de vers dans l'objet représenté sur la Figure 12a, - la Figure 13 illustre le principe du croisement de deux pions, - la Figure 14 représente les trois phases principales du procédé selon l'invention, 2873472 - 17 - - les Figures 15a, 15b et 15c illustrent trois exemples de configurations géométriques permettant de matérialiser le segment définissant la distance minimum entre deux triangles de représentations polyédriques d'objets, auxquels appartiennent les deux points composant un pion, - la Figure 16 illustre la projection d'extrémités d'un segment sur un plan contenant un triangle dans le cadre de la détermination du segment définissant la distance minimum entre deux triangles appartenant à des polyèdres représentant deux objets en interaction, - les Figures 17 et 18 illustrent, dans le cas du processus représenté sur la Figure 16, la détermination d'un segment définissant une distance minimum, respectivement dans le cas point-segment et dans le cas segment- segment, - la Figure 19 représente le génotype de plusieurs pions définis entre différents polyèdres représentant différents objets, - la Figure 20 illustre le replacement aléatoire d'un pion dans le cas d'un objet représenté sous forme polyédrique, - la Figure 21 illustre le génotype d'un pion défini entre deux surfaces paramétrées représentant deux objets, - la Figure 22 illustre le génotype d'un pion défini entre deux nuages de points représentant deux objets, - la Figure 23 illustre le génotype d'un pion défini entre deux représentations voxéliques d'objets, - la Figure 24 illustre la fonction d'un opérateur de croisement, - la Figure 25 représente des pions hybrides définis entre des géométries de types différents représentant des objets, et - la Figure 26 est un schéma-bloc montrant les principaux modules constituant un exemple de système selon l'invention. Le procédé et le système selon l'invention, décrits selon un mode de réalisation particulier, permettent à partir d'objets simulés numériquement, ou objets virtuels, d'identifier, tout au long d'une simulation dynamique en temps réel mettant en scène des représentations géométriques des objets, les zones géométriques susceptibles d'entrer en 2873472 - 18 - collision, et cela indépendamment de la complexité géométrique et de la nature (convexité, rigidité) des objets. Pour ce faire, le procédé selon l'invention fait appel à un processus évolutionnaire. D'une façon générale, il applique une stratégie qui consiste à faire évoluer une population d'individus en utilisant des opérateurs de variation (mutation, croisement) destinés à faire converger cette population vers une configuration optimale. L'évaluation de la qualité d'un individu se fait grâce à une fonction nommée "fonction d'objectif' ("fitness") destinée à mesurer un ou plusieurs critères qualitatifs.. Un tel processus évolutionnaire générant de nouveaux individus présente une grande efficacité et une simplicité de mise en oeuvre. Dans un premier temps, le procédé selon l'invention qui applique un processus évolutionnaire à la réalité virtuelle, sera décrit en référence à des objets représentés par des polyèdres, mais l'invention est plus générale et s'applique à des objets quelle que soit leur représentation géométrique. Comme on l'a déjà indiqué, la stratégie de base du procédé selon l'invention consiste à faire évoluer une population d'individus en utilisant des opérateurs de variation (mutation, croisement) destinés à faire converger la population (ensemble d'individus) vers une configuration optimale. La Figure 9 illustre un exemple de définition du génotype 51 d'un individu (qui par la suite sera également appelé "pion") qui est défini comme une paire de nucléons constitués par des points appartenant respectivement à chacun des deux maillages Objet1 et Objet2 représentant les premier et deuxième objets dont on souhaite évaluer la proximité. Le génotype 51 d'un pion peut ainsi s'exprimer comme: 2873472 - 19 - Facel al Ri Face2 a2 R2 où les indices Face (entiers non-signés) représentent les identifiant des faces auxquelles appartiennent respectivement les points définissant le pion,a,et/31 les coordonnées du point appartenant au premier polyèdre dans la base (e,, e2) de la face concernée, et respectivement poura2et/32dans la base(e',,e'2). (0 Le génotype défini ci-dessus est destiné à être utilisé dans le cadre de simulations d'objets de type polyédrique. Il est important de souligner que, de manière plus générique, un pion est simplement défini par deux nucléons appartenant respectivement à deux objets de nature quelconque. Si l'on considère par exemple le cas de surfaces implicites, dans ce cas un pion sera défini par les coordonnées (x,, y,, z,) du premier point et les coordonnées (x2, y2, z2) du deuxième. Dans le cas de géométries de type voxélique, les points pourront être définis par l'indice des voxels concernés. Ainsi, la description d'un pion est directement liée au type de géométrie utilisée. Il est par ailleurs possible de définir un pion entre deux géométries de types différents, les coordonnées des points étant systématiquement exprimées dans l'espace cartésien au moment de l'évaluation. La fonction d'objectif ("fitness") ou critère d'aptitude permettant d'évaluer la qualité d'un pion est constituée par la mesure de la distance séparant les premier et second nucléons définissant ce pion. On peut avantageusement choisir cette mesure comme étant le carré de la distance séparant les deux nucléons qui composent le pion. 2873472 - 20 - Soit (x,, y,, zl) et (x2, y2, z2) les coordonnées cartésiennes respectives des nucléons composant un pion pl projetées dans un même repère. L'expression de la fitness de cet individu est la suivante: fitness(p,) = (x2 xi)2 + (y2 yl)2 + (z2 z, )2 L'utilisation du carré de la norme est avantageuse car la fonction racine carrée est très coûteuse en terme de temps de calcul. On notera que la qualité Qualité (p) d'un individu ou pion p est inversement proportionnelle à sa fonction d'objectif fitness (p). La mutation est un opérateur d'évolution qui est définissable comme une variation plus ou moins importante du patrimoine génétique d'un individu. De façon plus particulière, dans le cadre de la présente invention, faire muter un individu consiste à déplacer les points qui le composent sur la surface des objets auxquels ils appartiennent. Plusieurs heuristiques de déplacement peuvent être définies dans le cadre de simulations faisant intervenir des polyèdres. Ainsi avec un exemple d'opérateur d'exploration illustré sur la Figure 10, les points définissant l'individu concerné vont pouvoir se déplacer sur de grandes distances sur la surface des objets. Cet opérateur génère des déplacements discrets de centres 52 de facettes 53 en centres 52 de facettes 53 en considérant la connexité des objets considérés, obtenue à l'aide de cartes de voisinage des polyèdres pré-calculées. L'amplitude de ces déplacements, qui correspond au nombre de sauts effectués durant la mutation, est déterminée de manière aléatoire. Elle est comprise entre 0 et 6Explor, amplitude de déplacement maximum dépendant de la géométrie de l'objet. La Figure 10 illustre le déplacement exploratoire discret d'un point sur un polyèdre avec une amplitude de huit sauts, mais cette valeur n'est naturellement donnée qu'à titre d'exemple. Un opérateur d'exploitation qui correspond à un autre type de mutation, illustré sur la Figure 11, est destiné à affiner le positionnement 2873472 - 21 - des points qui composent l'individu concerné. Contrairement au cas de la mutation exploratoire, ces déplacements sont définis de manière métrique. Ainsi chaque point va effectuer un déplacement sur un disque de rayon 6E, ploit, amplitude de déplacement maximum, ayant pour centre la position initiale du point. L'amplitude de déplacement maximum (exprimé en mètres) peut être dépendante de l'aire de la face 56 sur laquelle est effectué le déplacement. Ainsi, cette amplitude est calculée durant la phase de pré- calculs pour chaque facette 56. Se déplacer sur les faces 61 d'une représentation polyédrique 60 d'un objet en considérant uniquement la connexité (propriétés de voisinage) peut s'avérer restrictif notamment dans le cas d'objets fins ou fortement courbés. Ainsi, selon un autre aspect de l'invention, il est mis en place une deuxième carte basée sur la proximité des sommets. Durant la phase de pré-calculs, pour chaque sommet 62, 63 est établie une liste des sommets les plus proches 64, 65. Lorsque l'un des points (63) qui composent le pion en mutation se trouve sur un sommet à l'issue d'un déplacement, il a la possibilité (et non l'obligation) de glisser vers un sommet proche (64) pas obligatoirement connexe. Ce type de déplacement peut être dénommé "trous de vers", en référence aux ponts Einstein-Rosen (passages assimilables à des raccourcis liant des zones distantes au sein d'un univers courbé). La Figure 12a illustre la représentation polyédrique 60 d'un objet comportant des faces 61. Selon une carte de proximité, les sommets 64, 65 sont identifiés 25 comme étant les plus proches des sommets 62, 63. La Figure 12b illustre un exemple de parcours 66 sans trou de vers, depuis le sommet 63 jusqu'à un point 67. La Figure 12c illustre un parcours alternatif utilisant l'opérateur de mutation "trou de vers". Dans ce cas, le parcours depuis le sommet 63 jusqu'au point 67 inclut un passage 68 du type "trou de vers" en dehors de la représentation 60 de l'objet, entre les sommets 63 et 64 identifiés comme étant proches. 2873472 - 22 - Des opérateurs de mutation ayant des fonctions similaires à celles des trois opérateurs décrits ci-dessus peuvent être définis dans le cadre de simulation faisant intervenir d'autres types de géométries. L'invention met également en oeuvre un opérateur de variation, dénommé "croisement", qui est destiné à accélérer la convergence de la population (Figure 13). Le principe est de générer un pion (enfant) en couplant deux pions issus de la population (géniteurs). Le nouveau pion possède ainsi des propriétés génétiques propres à ses deux géniteurs. En pratique, cet opérateur peut être utilisé de la manière suivante: le pion "enfant" a pour nucléon 1 celui du premier géniteur et pour nucléon 2 celui du deuxième. Le schéma général du procédé selon l'invention est illustré sur la Figure 14, avec une première phase 71 d'initialisation, une deuxième phase 72 de tournoi et une troisième phase 73 d'évolution. Au cours de la phase 71 d'initialisation, on fournit des données permettant d'identifier des points décrivant la géométrie de chacun des objets simulés graphiquement et on stocke ces données en mémoire. Au cours de cette même phase 71 d'initialisation, on crée également une carte de connectivité contenant des informations définissant les propriétés de voisinage topologique au sein des objets et on stocke en mémoire les informations de cette carte de connectivité. La phase 71 d'initialisation comprend encore l'établissement d'une carte de proximité contenant des informations définissant les propriétés de proximité (trou de vers) au sein des objets et le stockage en mémoire des informations de cette carte de proximité. Enfin, lors de la phase 71 d'initialisation, on crée une population constituée par un ensemble de N individus (que l'on peut appeler pions) définis chacun par des premier et second nucléons constitués par des points appartenant respectivement aux géométries de deux objets distincts préalablement identifiés. La phase 72 de tournoi consiste en l'organisation de combats entre individus. Un combat entre deux individus ou pions consiste à évaluer lequel des deux pions s'avère de meilleure qualité, c'est-à-dire à 2873472 - 23 - déterminer lequel des deux pions présente une fonction d'objectif (ou critère d'aptitude) "fitness" la plus faible. Ainsi, lors de la phase 72 de tournoi, on organise des sessions au sein des N pions de la population créée où, durant chacune des sessions, un pourcentage de la population est soumise à des combats au cours desquels on évalue pour chaque paire de pions soumis à un combat, en fonction d'une évaluation de la qualité définie à partir d'un critère d'aptitude, lequel a gagné et lequel a perdu et on identifie le gagnant et le perdant par un marquage qui est différent à l'issue de chaque session du tournoi. Les différentes sessions de la phase 72 de tournoi peuvent comprendre par exemple une première session Mut% consistant en des combats d'un pourcentage de la population qui engendreront ensuite des mutations, une deuxième session Cross% consistant en des combats d'un pourcentage de la population qui engendreront ensuite des croisements et une troisième session Rand% consistant en des combats d'un pourcentage de la population qui engendreront ensuite des redéfinitions aléatoires. Les première, deuxième et troisième sessions, Mut%, Cross% et Rand% peuvent avoir lieu dans des ordres quelconques. A l'issue de la phase de tournoi 72, les pions gagnants sont identifiés par un marquage qui est différent de celui des pions perdants. Le marquage des pions diffère également en fonction de la session pendant laquelle ils ont subi un ou plusieurs combats. La phase 73 d'évolution consiste à appliquer les opérateurs de variation précédemment définis à la population en fonction des résultats du tournoi et comprend ainsi la mutation des pions ayant perdu durant la première session Mut% du tournoi, le remplacement des pions ayant perdu durant la deuxième session Cross% du tournoi par croisement de pions choisis aléatoirement, et la redéfinition des pions ayant perdu durant la troisième session Rand% du tournoi. L'exploitation des gagnants des combats qui sont supposés être de bons éléments permet de déterminer des zones de proximité entre deux objets. Le processus est itératif et les phases 72 et 73 peuvent se répéter sans arrêt. Il est possible à chaque 2873472 - 24 - instant d'exploiter une configuration améliorée en exploitant les seuls pions alors marqués comme étant gagnants. Le procédé selon l'invention est peu dépendant de la nature géométrique et de la qualité des objets. Il est utilisable dans le cadre de simulations faisant intervenir tous types de géométries (polyèdres, voxels, surfaces paramétrées, etc...) dès lors que les opérateurs de variation adéquats sont définis. De plus, il permet la mixité des géométries, les points qui composent les pions pouvant évoluer de manière totalement différente à la surface des objets auxquels ils appartiennent respectivement. Le procédé n'est pas sensible aux concavités, les mutations exploratoires et les redéfinitions aléatoires assurant la diversité de la population. La qualité des objets (orientation des normales, trous,...) n'affecte nullement le fonctionnement du procédé. Ceci est un avantage considérable (les moteurs physiques actuels sont très sensible à la qualité des objets ce qui affecte souvent considérablement leur bon fonctionnement...). Les durées d'exécution des deuxième et troisième étapes 72, 73 du procédé (tournoi, évolution) ne sont pas dépendantes du nombre d'entités géométriques élémentaires, mais seulement du nombre de pions qui n'est pas dépendant de la complexité géométrique des objets. Dans tous les cas, les pions se voient beaucoup moins nombreux que les entités géométriques élémentaires. Le procédé est donc au total peu dépendant de la complexité géométrique des objets. Comme on l'a déjà indiqué, un individu ou pion d'une population de N individus se compose de deux points que l'on peut également appeler nucléons. Il a été décrit plus haut, plus particulièrement dans le cas d'objets représentés de façon polyédrique, un ensemble d'opérateurs d'évolution ou mutateurs destinés à faire évoluer les pions au sein des polyèdres auxquels ils appartiennent. 2873472 - 25 - Un autre opérateur permet un positionnement optimal des nucléons constituant l'individu concerné sur les triangles qui les contiennent au sein des représentations d'objets de type polyédrique. Cet opérateur de mutation permet de minimiser localement de manière exacte, selon une approche déterministe, la fonction d'objectif (fitness) du pion concerné. Cet opérateur de mutation est destiné à être appliqué à l'élite des individus constituant la population. Il est destiné à accélérer la convergence et augmenter la précision des résultats issus de la mise en oeuvre du procédé. Le but de cet opérateur est de positionner les nucléons qui composent le pion concerné de manière à matérialiser le segment définissant la distance minimum entre les deux triangles auxquels ils appartiennent respectivement. Les Figures 15a, 15b, 15c montrent trois configurations géométriques différentes avec deux triangles 81, 82; 83, 84 et 85, 86 respectivement pour lesquels le segment 87; 88; 89 matérialisant respectivement la distance minimum entre les deux triangles correspond à une interaction sommet/face, sommet/sommet et arête/arête. Ces différents cas peuvent être pris en compte avec le procédé de 20 détermination décrit ci-dessous. Afin de déterminer en un temps réduit le positionnement optimal des nucléons composant le pion concerné, on décompose le cas triangle/triangle en 6 cas segment/triangle comme exprimé ci-dessous, couvrant ainsi l'ensemble des configurations géométriques précédemment définies. (( A,, B,,C,),(A,,Bz,C)) =min {vs,a,(A2, B2, , ([A, , , , , vs,- Gci, B, A2, B,,Cz)), Wsr([A2,B,] (A,,,C,)) vs,([A2,C,],(A,,B,,C,)), vs,([C BZ],(A,,B,,C,)) } Où vST (S,T) et v n. (7,T,) déterminent respectivement les segments matérialisant la distance minimum dans les cas segment/triangle et triangle/triangle. 2873472 - 26 - La détermination du segment minimum dans le cas segment/triangle se décompose elle-même en deux phases: - Identification des configurations géométriques possibles et des éléments concernés (segments, points, face). - Détermination du segment minimum. La première phase consiste à projeter orthogonalement les extrémités du segment sur le plan contenant le triangle. La combinaison des positions de leurs projetés par rapport au triangle va permettre d'identifier les configurations géométriques possibles et les éléments potentiellement concernés. Les positions des projetés par rapport au triangle sont formalisées par leur appartenance à l'une des portions de plan définies par les droites porteuses des côtés du triangle. Par exemple, dans le cas illustré sur la Figure 16, les projetés Pl, QI des extrémités Pet Q du segment appartiennent respectivement aux zones Z2 et Z4 du plan contenant le triangle (A,B,C). Ainsi il existe 49 combinaisons possibles: {(Z;,ZJ),1 [CB]) [PP. ] y'ss ([PQ], [AB]) z, ylss ([PQ], [AB]) Yss ([PQ], [AB]) yJss ([PQ], [AB]) yJss ([PQ], [Ac]) ytss ([PQ], [AC]) YJss ([PQ], [CB]) La deuxième phase va consister à déterminer le pion optimal. Ainsi dans cette partie on définit l'ensemble des fonctions précédemment citées. Le cas point/segment est illustré sur la Figure 17 et correspond à Y PS (M, [PQ]) Le but est de déterminer le coefficient,% tel que: {2e [0,1], VILE [0,1] (2É PQ)M 1, alors on donne à À la valeur 1 Le cas segment/segment est illustré sur la Figure 18 et correspond a-less([PQ,], [1 Q2]) Le but est de déterminer les coefficients 2 et,u tels que: {2E [0,1],,uE [0,1],d(a, f)E [0,1]2, (2- PQ1)(ji É P2Q2) (a PQ,)(fiÉP2Q2) f Après mise en équation: P,M, =2-P,QI P2M2=P2Q2 PQ, É M,M2 = 0 P2Q2ÉM, M2=0 on obtient huit équations pour 8 inconnues: 10 2873472 _2g_ xM xp =/Î.É(xQ1 xp) YM, YP =2'(YQ, Yp) zM, Zp = . (ZQQ zp) xM2 xp2 2 (xQ2 xp2) YM2 YP2 É (YQ2 YP2) ZM2 zP2 =2É(Zaz ZP2) (xQ, xp) (xM2 xM,) + (YQ, YP) (YM2 YMi) + (ZQ, ZP) (ZM2 ZMi) O (xQ2 xp2) (xM2 xM,)+(YQ2 YP2) (YM2 YM,)+(ZQ2 zp2)-(ZM2 ZM)=0 d'où l'on déduit: (XQP XQzP +YQ,P YQ, PZ + ZQp -ZQzP) (XQzP XPP +QzP YPP +ZQzP ZPP) 2 2 (XQ,P XPxP +YQ,P YPxP + ZQiP ZP,P) XQ,P +YQ,P, +ZQ,Pz 2 2 2 (XQP XQx p + YQ P YQzPz + ZQ p ZQ,P) -XQ,P -YQ0P -ZQP + 2 2 2 XQ,PZ + YQ_pz + ZQ_P !, (xQ1P xQ2P2 + YQIP. YQ2P2 + ZQ,P ZQ2P2) (XQ2P XP2P + YQ2P YP2_P + ZQ2P2 ZP,P) d U 2 2 xQ2P2 + YQ2P2 + ZQ2 p afin d'assurer l'appartenance de M, et M2 respectivement à [P,Q,] et [P2Q2], on sature les coefficients) , et,u comme précédemment. Dans le cas de la simulation numérique d'objets faisant intervenir plusieurs objets mobiles les uns par rapport aux autres, il est possible de créer une population de pions pour chaque paire d'objets. Cette approche peut être retenue dans le cas où le nombre n d'objets est relativement petit, mais peut s'avérer coûteuse en temps de calcul si le nombre n d'objets est très supérieur à 2. L'invention peut être mise en oeuvre en utilisant une seule 25 population de N individus ou pions qui s'applique à l'ensemble des géométries représentatives d'objets présentes au sein de la simulation. Dans ce cas, les pions d'une même population peuvent évoluer non plus seulement sur une des paires de géométries contenues dans la simulation, mais sur l'ensemble des paires de géométries (ou maillages) contenues dans la simulation. 2= 2873472 - 30 - Afin de privilégier les combinaisons pertinentes, on ne prend cependant pas en compte les paires d'objets ne pouvant rentrer en contact, c'est-à- dire en particulier les objets liés rigidement ou très distants. Si l'on considère le cas polyédrique, le génotype d'un pion s'exprime de la manière suivante, avec Meshl et Mesh2 qui représentent l'identification des maillages (polyèdres) des objets auxquels appartiennent les deux points (nucléons) composant un pion: Mesh, 10 Face, a, Mesh 2 Face2 a2 où les indices Mesh et Face (entiers non-signés) représentent respectivement les identifiant des polyèdres et faces auxquelles appartiennent les nucléons définissant le pion,a, etf, les coordonnées du point appartenant au premier polyèdre dans la base (e1,e2) de la face concernée, et respectivement pour a2 et f2 dans la base (e',, e'2). Les mutateurs définis précédemment ne sont pas affectés par ce mode de fonctionnement. Les sauts inter-géométries des nucléons sont effectués lors de la phase de replacement aléatoire qui couvre l'ensemble de l'espace à parcourir et non plus seulement l'une des géométries. 20 - 31 - L'application générale du procédé à une population de N pions Pion,. à Pion4 couvrant n représentations géométriques Meshi à Mesh4 d'objets est illustrée sur la Figure 19 pour le cas n = 4 et N = 4. Les génotypes des quatre pions dans l'exemple de la Figure 19 5 sont les suivants: r 1 ( 1 (2l r i 2 1 2 1 0.2 0.2 0.0 0.15 0.25 0.7 0.0 0.85 Pions = 2 Pion2 = 3 Pion3 = 3 Pion, = 4 3 1 4 1 0.3 0.3 0.2 0.25 0.4) \0.2, 0.2) 0.4) L'invention s'applique aussi bien à des simulations faisant intervenir des géométries polyédriques, qui sont couramment utilisées dans un grand nombre de domaines d'application comme la réalité virtuelle ou l'infographie, qu'à des simulations faisant intervenir des géométries non-polyédriques. Les génotypes et opérateurs de mutation adaptés à des géométries polyédriques ont déjà été décrits dans les exemples donnés précédemment. On a simplement représenté sur la Figure 20 un exemple de mutateur procédant au replacement aléatoire d'un nucléon 91, 91' sur les facettes d'une structure polyédrique. On décrira ci-dessous quelques exemples de mise en oeuvre de l'invention faisant intervenir des géométries non polyédriques. La Figure 21 illustre le cas d'objets représentés par des surfaces paramétrées (Bézier, B-Spline,...) appelées "patch". s0 - 32 - Dans ce cas, la définition de chacun des nucléons d'un pion inclut l'identifiant Patch', resp. Patch2 de la surface paramétrée à laquelle il appartient et les coordonnées u1v1 resp u2v2 de ce nucléon au sein de cette surface paramétrée Patchl, resp Patch2 à laquelle il appartient. Le génotype d'un pion est alors le suivant: Patch, Sur la Figure 21, M1 et M2 sont les expressions mathématiques qui 15 définissent respectivement Patch' et Patch2. En ce qui concerne les mutateurs utilisés avec des surfaces paramétrées, on peut noter que l'évolution d'un nucléon sur une surface paramétrée va consister à modifier de manière stochastique ses coordonnées au sein de cette dernière (i.e. (u, v) (u+A,,,v+A) ). Ainsi, le choix des valeurs maximum des coefficients de variations Au et Av conditionnera le type de mutation (exploration ou exploitation). Un repositionnement aléatoire d'un nucléon peut être effectué par un changement aléatoire de ses coordonnées. Le cas d'objets représentés sous forme de nuages de points est 25 illustré sur la Figure 22 avec deux représentations d'objets référencés Nuage' et Nuage2. Dans ce cas, pour déterminer le génotype d'un pion, on définit chacun des nucléons par l'identifiant p' resp P2 du point auquel il appartient, de la façon suivante: - 33 - Nuage, P, Nuage 2 P2 Pour ce qui concerne les opérateurs de mutation, l'évolution d'un nucléon au sein d'un nuage de points va consister à lui faire effectuer des sauts vers les points avoisinant celui auquel il appartient. Pour cela, il est nécessaire afin de limiter les temps de calculs de générer en phase de pré- calcul une carte de proximité similaire à celle utilisée dans le cas polyédrique. La mise en place d'un mutateur de replacement aléatoire est triviale. Elle consiste simplement à mettre à jour de manière aléatoire les paramètres p, et p2. La Figure 23 illustre le cas d'objets représentés par des géométries 15 voxéliques dénommées Géométrie,. et Géométrie2. Pour définir le génotype d'un pion, dans le cas voxélique, chacun des nucléons est défini par l'identifiant v,. resp 1)2 du voxel auquel il appartient comme indiqué ci-dessous: Géométrie 1 vl Géométrie 2 V2 Toutefois, le génotype précédemment défini peut s'avérer 25 inadapté dans certains cas (voxels de tailles différentes ou trop importantes). Il peut alors s'avérer nécessaire d'enrichir ce dernier des coordonnées des nucléons au sein de leur voxel respectif. Dans le cas voxélique, on peut définir des mutateurs de la façon suivante: 2873472 - 34 - Exploration discrète: Le nucléon se déplace de voxel en voxel à l'aide d'une carte de proximité pré-calculée. Exploration continue: Dans le cas où les voxels s'avèrent de taille importante, le nucléon peut se déplacer à la surface du voxel auquel il appartient (variation stochastique de ses coordonnées au sein du voxel). Exploitation stochastique: Exploration continue d'amplitude restreinte. Exploitation déterministe: Le segment "matérialisant" la distance minimum entre deux cubes est trivialement déterminable de manière déterministe. L'exploitation déterministe consiste ainsi à minimiser localement un pion au sein d'une paire de voxels. Replacement aléatoire: Choix aléatoire de nouveaux voxels. On notera que l'opérateur de croisement précédemment défini en référence à des géométries polyédriques s'avère également parfaitement adapté à l'ensemble des génotypes proposés avec des représentations sous la forme de surfaces paramétrées, nuages de points ou voxels. La Figure 24 représente dans sa généralité l'opérateur de croisement pour produire à partir de deux pions Géniteur1 et Géniteur2 un pion Enfant composé du premier nucléon Nucléons du pion Géniteur1 et du deuxième nucléon Nucléon2 du pion Géniteur2. Les génotypes et mutateurs qui viennent d'être définis se présentent comme des formalismes adaptés à la définition et l'évolution de nucléons au sein des différents types de géométries choisis. On peut cependant noter que dans le cadre de la mise en oeuvre du procédé, l'évaluation de la qualité d'un pion se ramène à l'évaluation de la distance euclidienne séparant les nucléons qui le composent. Par suite, il est tout à fait possible de faire intervenir au sein d'une même simulation des géométries de types différents et de prendre en considération des pions hybrides constitués de nucléons de natures différentes, comme illustré sur la Figure 25 où, à titre d'exemple, on voit une représentation polyédrique "Mesh" d'un premier objet, une représentation sous forme de nuage de points "Nuage" d'un second objet, une représentation voxélique "Vox" d'un troisième objet et une représentation sous forme de surface paramétrée "Patch" d'un quatrième objet, avec un premier pion Pionl dont les nucléons appartiennent aux représentations géométriques "Vox" et "Patch", un deuxième pion Pion2 dont les nucléons appartiennent aux représentations géométriques "Patch" et "Nuage" et un troisième pion P3 dont les nucléons appartiennent aux représentations géométriques "Mesh" et "Nuage", ce qui se traduit pour ces trois pions par les génotypes suivants: Pion2 = Pion3 = Patch u Nuage v / \ p2) (Vox v, Pion, =Mesh Face, a, Nuage P i La Figure 26 montre sous forme de schéma-bloc un exemple de système d'identification de zones de proximités entre un nombre P d'objets simulés graphiquement, avec P>2, conformément à l'invention. Ce système comprend une unité de mémoire 110 avec au moins des zones de mémoire 111, 112, 113. Une première zone de mémoire 111 permet de stocker des données décrivant la géométrie de chacun des P objets simulés graphiquement. Une deuxième zone de mémoire 112 permet de stocker des informations représentant une carte de connectivité et définissant les propriétés du voisinage au sein de chacun des P objets. Une troisième zone de mémoire 113 permet de stocker des informations représentant une carte de proximité et définissant les propriétés de proximité au sein de chacun des P objets. 2873472 - 36 - Un module d'initialisation 120 permet de créer une population constituée par un ensemble de N pions définis chacun par des premier et second points ou nucléons appartenant respectivement aux géométries de l'un des P objets et d'un autre des P objets. Un écran de visualisation 130 permet, si on le souhaite, de visualiser les P objets simulés numériquement. Une unité centrale de traitement 140 comprend au moins les sous-ensembles 141 à 145 suivants: - des moyens 141 de sélection d'un pourcentage de la population 10 des N pions devant être soumis à des combats par paires au cours d'une session d'un tournoi, - des moyens de comparaison et de calcul 142 pour évaluer au cours d'une session d'un tournoi, pour chaque paire de pions soumis à un combat, la qualité de chacun des pions de la paire de pions à partir d'un critère d'aptitude, - des moyens de marquage 143, pour identifier à chaque session du tournoi lequel des pions d'une paire de pions soumis à un combat a gagné, et lequel des pions de ladite paire de pions soumis à un combat a perdu, - des moyens d'itération 144 pour produire une évolution des pions qui ont subi au moins un combat, - un module d'extraction 145 pour ne retenir que les meilleurs pions de la population en fonction du critère d'aptitude, pour la détermination des zones de proximité entre au moins deux des P objets. Les moyens d'itération 144 sont associés au moins à un opérateur de mutation exploratoire des pions ayant perdu pendant une première session du tournoi, à un opérateur de remplacement des pions ayant perdu durant une deuxième session du tournoi par croisement de pions choisis aléatoirement et à un opérateur de redéfinition des pions ayant perdu durant une troisième session du tournoi. La référence 150 désigne une interface optionnelle telle qu'une interface haptique permettant d'exploiter les pions sélectionnés et retenus 2873472 - 37 - au cours de l'exécution répétitive des tournois et du processus évolutionnaire. On notera que l'invention évite les phases de tri qui sont coûteuses en temps et, de par l'indépendance du traitement des individus, autorise un processus qui est fortement parallélisable avec une possibilité de répartition des calculs sur plusieurs microprocesseurs ou microcontrôleurs, ainsi que pour chaque nucléon d'un pion la possibilité de passer d'un type de géométrie d'objet à un autre, ce qui donne une grande souplesse de fonctionnement. Les populations d'individus peuvent comprendre par exemple quelques centaines d'individus. REVENDICATIONS 1. Procédé d'identification de zones de proximité entre au moins des premier et deuxième objets simulés numériquement, caractérisé en ce qu'il comprend les étapes suivantes (a) on fournit des données décrivant la géométrie de chacun des premier et deuxième objets simulés numériquement et on stocke ces données en mémoire, (b) on crée une population constituée par un ensemble de N individus appelés pions définis chacun par des premier et second nucléons eux-mêmes définis comme des points appartenant respectivement aux géométries de chacun des premier et deuxième objets, (c) on organise des sessions d'un tournoi au sein des N pions de la population créée, où durant chacune des sessions un pourcentage de la population est soumis à des combats au cours desquels on évalue pour chaque paire de pions soumis à un combat, en fonction d'une évaluation de la qualité définie à partir d'un critère d'aptitude, lequel a gagné et lequel a perdu et on identifie le gagnant et le perdant par un marquage qui est différent à l'issue de chaque session du tournoi, (d) après le tournoi, on procède à une mutation exploratoire des pions ayant perdu durant une première session, on procède à un remplacement des pions ayant perdu durant une deuxième session, par croisement de pions choisis aléatoirement et on procède à une redéfinition aléatoire des pions ayant perdu durant une troisième session, (e) pour l'exploitation des pions devant servir à déterminer des zones de proximité entre les premier et deuxième objets, on considère uniquement la population des vainqueurs des combats, (f) on exécute à nouveau les étapes (c), (d) et (e) de façon répétitive, et (g) on extrait à la demande des informations géométriques à partir d'une configuration actualisée de la population de pions, durant l'exécution répétitive. 2. Procédé selon la revendication 1, caractérisé en ce que au cours de l'étape d'extraction des informations géométriques, on évalue les distances entre les zones de proximité identifiées. 3. Procédé selon la revendication 1 ou la revendication 2, caractérisé en ce que les données permettant d'identifier des zones de l'espace décrivant la géométrie d'au moins l'un des premier et deuxième objets simulés numériquement comprennent des représentations polyédriques. 4. Procédé selon la revendication 1 ou la revendication 2, caractérisé en ce que les données permettant d'identifier des zones de l'espace décrivant la géométrie d'au moins l'un des premier et deuxième objets simulés numériquement comprennent des représentations voxéliques. 5. Procédé selon la revendication 1 ou la revendication 2, caractérisé en ce que les données permettant d'identifier des zones de l'espace décrivant la géométrie d'au moins l'un des premier et deuxième objets simulés numériquement comprennent des représentations par surfaces paramètrées. 6. Procédé selon la revendication 1 ou la revendication 2, caractérisé en ce que les données permettant d'identifier des zones de l'espace décrivant la géométrie d'au moins l'un des premier et deuxième 25 objets simulés numériquement comprennent des nuages de points. 7. Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce que le critère d'aptitude permettant d'évaluer la qualité d'un pion est constitué par une mesure de la distance séparant les premier et second nucléons définissant ce pion, la qualité du pion étant d'autant plus grande que la distance mesurée est plus faible. 2873472 - 40 - 8. Procédé selon la revendication 7, caractérisé en ce que la mesure de la distance constituant le critère d'aptitude permettant d'évaluer la qualité d'un pion prend en compte le carré de la distance séparant les premier et second nucléons définissant ce pion. 9. Procédé selon la revendication 1, caractérisé en ce qu'il comprend en outre après l'étape (a) de fourniture de données décrivant la géométrie de chacun des premier et deuxième objets simulés numériquement, les étapes suivantes: (a1) on crée une carte de connectivité contenant des informations définissant les propriétés de voisinage entre éléments géométriques au sein des premier et deuxième objets et on stocke en mémoire les informations de cette carte de connectivité, (a2) on crée une carte de proximité contenant des informations définissant les propriétés de proximité au sein des premier et deuxième objets et on stocke en mémoire les informations de cette carte de proximité. 10. Procédé selon l'une quelconque des revendications 1 à 9, caractérisé en ce que la mutation des pions ayant perdu durant une session du tournoi engendrant des mutations exploratoires pour les pions ayant perdu, consiste à déplacer les premier et second nucléons composant un pion sur la surface des premier et deuxième objets auxquels ces premier et second nucléons appartiennent respectivement. 11. Procédé selon les revendications 3, 9 et 10, caractérisé en ce que lors de la mutation d'un pion ayant perdu durant une session du tournoi, engendrant des mutations exploratoires pour les pions ayant perdu, au moins l'un des premier et second nucléons composant ce pion et appartenant à l'un des premier et deuxième objets représentés sous une forme polyédrique est soumis à une succession de déplacements discrets de centre de facette en centre de facette en considérant les informations définissant les propriétés de voisinage stockées en mémoire. 2873472 - 41 - 12. Procédé selon les revendications 3, 9 et 10, caractérisé en ce que lors de la mutation d'un pion vainqueur au cours du tournoi, au moins l'un des premier et second nucléons composant ce pion et appartenant à l'un des premier et deuxième objets représentés sous une forme polyédrique est soumis à un déplacement sur une même facette sur un disque ayant pour centre la position initiale de ce point et pour rayon une amplitude de déplacement maximum qui dépend de l'aire de la facette sur laquelle est effectué le déplacement. 13. Procédé selon les revendications 3, 9 et 10, caractérisé en ce que lors de la mutation d'un pion vainqueur au cours du tournoi, au moins l'un des premier et second nucléons composant ce pion et appartenant à l'un des premier et deuxième objets représentés sous une forme polyédrique est soumis à un déplacement sous forme de "trou de vers" d'un sommet d'une facette vers un autre sommet proche d'une autre facette qui n'est pas nécessairement connexe, en considérant les informations définissant les propriétés de proximité stockées en mémoire. 14. Procédé selon les revendications 3, 9 et 10, caractérisé en ce que lors de la mutation d'un pion vainqueur au cours du tournoi, les premier et second nucléons composant ce pion et appartenant respectivement aux premier et deuxième objets représentés chacun sous une forme polyédrique avec des facettes triangulaires, sont positionnés de telle sorte qu'ils délimitent un segment définissant la distance minimum entre les deux facettes triangulaires auxquelles ces premier et second nucléons appartiennent respectivement. 15. Procédé selon la revendication 1, caractérisé en ce que lors du remplacement d'un pion ayant perdu durant une session du tournoi engendrant pour les pions ayant perdu des remplacements par croisement de pions choisis aléatoirement, pour définir le nouveau pion résultant du croisement d'un premier et d'un deuxième pions choisis aléatoirement, on considère que le nouveau pion se compose du premier nucléon du premier pion choisi aléatoirement et du second nucléon du deuxième pion choisi aléatoirement. - 42 - 16. Procédé selon l'une quelconque des revendications 1 à 15, appliqué à un ensemble de P objets simulés numériquement avec P>2, caractérisé en ce qu'il comprend les étapes suivantes: (a) on fournit des données décrivant la géométrie de chacun des P objets simulés graphiquement, (b) on crée une population constituée par un ensemble de N individus appelés pions définis chacun par des premier et second nucléons eux-mêmes définis comme des points appartenant respectivement aux géométries de l'un des P objets et d'un autre des P objets, (c) on organise des sessions d'un tournoi au sein des N pions de la population créée, où durant chacune des sessions un pourcentage de la population est soumis à des combats au cours desquels on évalue pour chaque paire de pions soumis à un combat, en fonction d'une évaluation de la qualité définie à partir d'un critère d'aptitude, lequel a gagné et lequel a perdu et on identifie le gagnant et le perdant par un marquage qui est différent à l'issue de chaque session du tournoi, (d) après le tournoi, on procède à une mutation exploratoire des pions ayant perdu durant une première session, on procède à un remplacement des pions ayant perdu durant une deuxième session, par croisement de pions choisis aléatoirement et on procède à une redéfinition aléatoire des pions ayant perdu durant une troisième session, (e) pour l'exploitation des pions devant servir à déterminer des zones de proximité entre deux des P objets simulés numériquement, on considère uniquement la population des vainqueurs des combats, on exécute à nouveau les étapes (c), (d) et (e) de façon répétitive, et on extrait à la demande des informations géométriques à partir d'une configuration actualisée de la population de pions, durant l'exécution répétitive, (f) (g) 2873472 - 43 - 17. Procédé selon la revendication 16, caractérisé en ce que les données permettant d'identifier des zones de l'espace décrivant la géométrie des P objets simulés numériquement comprennent des représentations polyédriques, et en ce que le procédé comprend en outre, après l'étape (a) de fourniture de données décrivant la géométrie des P objets simulés numériquement, les étapes suivantes (al) on crée une carte de connectivité contenant des informations définissant les propriétés de voisinage entre éléments géométriques au sein de chacun des P objets et on stocke en 10 mémoire les informations de cette carte de connectivité, (a2) on crée une carte de proximité contenant des informations définissant les propriétés de proximité au sein de chacun des P objets et on stocke en mémoire les informations de cette carte de proximité. 18. Système d'identification de zones de proximité entre un nombre P d'objets simulés numériquement avec P__>2, caractérisé en ce qu'il comprend: (a) des premiers moyens de mémoire (111) pour stocker des données décrivant la géométrie de chacun des P objets, (b) un module d'initialisation (120) pour créer une population constituée par un ensemble de N individus appelés pions définis chacun par des premier et second nucléons eux-mêmes définis comme des points appartenant respectivement aux géométries de l'un des P objets et d'un autre des P objets, (c) une unité centrale de traitement (140) comprenant au moins: (cl) des moyens (141) de sélection d'un pourcentage de la population des N pions devant être soumis à des combats par paires au cours d'une session d'un tournoi, (c2) des moyens de comparaison et de calcul (142) pour évaluer au 30 cours d'une session d'un tournoi, pour chaque paire de pions - 44 - soumis à un combat, la qualité de chacun des pions de la paire de pions à partir d'un critère d'aptitude, (c3) des moyens de marquage (143) pour identifier à chaque session du tournoi lequel des pions d'une paire de pions soumis à un combat a gagné, et lequel des pions de ladite paire de pions soumis à un combat a perdu, (c4) des moyens d'itération (144) pour produire une évolution des pions qui ont subi au moins un combat, ces moyens d'itération (144) étant associés au moins à un opérateur de mutation exploratoire des pions ayant perdu pendant une première session du tournoi, à un opérateur de remplacement des pions ayant perdu durant une deuxième session du tournoi par croisement de pions choisis aléatoirement et à un opérateur de redéfinition des pions ayant perdu durant une troisième session du tournoi, et (c5) un module d'extraction (145) pour ne retenir que les meilleurs pions de la population en fonction du critère d'aptitude, pour la détermination des zones de proximité entre au moins deux des P objets. 19. Système selon la revendication 18, caractérisé en ce qu'il 20 comprend en outre (ai) des deuxièmes moyens de mémoire (112) pour stocker des informations représentant une carte de connectivité et définissant les propriétés du voisinage entre éléments géométriques au sein de chacun des P objets, (a2) des troisièmes moyens de mémoire (113) pour stocker des informations représentant une carte de proximité et définissant les propriétés de proximité au sein de chacun des P objets. 20. Système selon l'une quelconque des revendications 18 et 19, caractérisé en ce qu'il comprend en outre un écran de visualisation (130) 30 pour visualiser les objets simulés numériquement. 2873472 - 45 - 21. Système selon la revendication 20, caractérisé en ce qu'il comprend en outre une interface haptique (150). 22. Système selon l'une quelconque des revendications 18 à 21, caractérisé en ce que l'unité centrale de traitement (140) comprend un 5 ensemble d'unités de calcul fonctionnant en parallèle.