Brevet FR2927184A1 — publié le 20090807

-1- " Procédé et dispositif de simulation de contact par images à plan de profondeur." La présente invention concerne un procédé de simulation d'un contact entre au moins deux objets volumiques délimités par des surfaces triangulaires. Elle trouve une application particulièrement intéressante dans le domaine de simulation physique en temps réel pour jeu vidéo ou io simulateurs chirurgicaux. Mais elle est d'un cadre plus large puisqu'elle peut s'appliquer à toute simulation impliquant des objets en contact avec une géométrie non triviale. Une simulation d'objets mécaniques peut être schématiquement décomposée en quatre processus principaux : la détection de collision, le 15 calcul des forces de contact, le calcul des forces internes, et l'intégration du temps. La détection de collisions est souvent l'opération de traitement la plus intense et a largement fait l'objet d'études approfondies pendant de nombreuses années. Ce traitement est important puisque la crédibilité de la simulation en dépend. 20 Des tests géométriques précis et des calculs d'intersection en profondeur sont nécessaires pour déterminer des forces d'interaction entre des surfaces de contact. Les objets sont généralement décomposés en primitives de contact telles que des sphères ou des triangles. Cependant, les primitives sphériques conduisent à des approximations peu 25 convaincantes de la surface de contact et entraînent malheureusement des artefacts importants. Les primitives à base de triangles sont plus efficaces mais nécessitent plus de calculs géométriques que les sphères. De toute manière, les calculs des forces de répulsion sont complexes à mettre en oeuvre et des fonctions discontinues de l'espace peuvent apparaître. Pour 30 des objets rigides, il est possible de réaliser des calculs préalables afin d'éviter ces fonctions discontinues, mais cela est difficilement envisageable pour des objets déformables. La détection de collisions et le calcul de forces de contact restent donc des tâches extrêmement difficiles à mettre en oeuvre. 35 -2 - Dans l'art antérieur, on connaît le document Teschner et al., � Collision detection for deformable objects. � Computer Graphics Forum 24, 1 (March 2005), 61-81, dans lequel on décrit la détection de collision et des techniques de réponse. Ce document décrit des techniques de création de hiérarchies de volumes englobants pour palier la complexité quadratique inhérente à la détection de collision. Ce document met en oeuvre la technique des champs de distance pour obtenir des détections de collision robustes. Dans cette technique, pour tout point de l'espace, on stocke la "caractéristique la plus proche" (closest feature) qui est l'élément de la io surface le plus proche à ce point, de façon à permettre des intersections en profondeur. En pratique, cette technique n'est utilisée que pour des objets rigides car elle nécessite des calculs préalables (prétraitement) de champ de distance lors de l'initialisation de la simulation. Il subsiste également des problèmes de discontinuité de l'application d'un espace 3D vers une 15 surface, ce qui peut générer des réponses instables. D'une façon générale, les systèmes informatiques actuels tels que les ordinateurs personnels intègrent une carte graphique qui a pour fonction de gérer le traitement et l'affichage de composants graphiques de plus en plus 20 complexes. Cette carte graphique permet notamment d'accélérer l'affichage 3D. Pour ce faire, elle comporte une unité de traitement graphique GPU (Graphics Processing Unit en langue anglaise) qui est un processeur optimisé pour la 3D. Récemment, pour exploiter la puissance de calcul des GPU et leur capacité 25 à échantillonner efficacement les polygones, des méthodes basées-image ont été introduites. Pour des géométries de maillage données, ces méthodes génèrent des paires de primitives géométriques, qui sont ensuite traitées par la CPU pour calculer les forces de contact. Comme elles n'utilisent pas de structures de données volumiques, elles peuvent être 30 efficacement appliquées à des objets rigides et des objets déformables. Les paires de contacts peuvent être composées de triangles ou de points dans des volumes. Après détection, des calculs supplémentaires de la CPU sont nécessaires pour modéliser les intersections et les forces de contact. On connaît le document Heidelberger et al. � Real-time volumetric 35 intersections of deforming objects �. In Proceedings of Vision, Modeling, Visualization (VMV), Munich, Germany, November 19-21, 2003, qui décrit -3 - un algorithme des � Images à plan de profondeurs � LDI (Layered Depth Images en langue anglaise). Cet algorithme permet de représenter de façon compacte plusieurs couches de la géométrie d'une intersection d'objets à partir d'un point de vue donné. Cet algorithme permet de construire des modèles géométriques du volume d'intersection. Selon cet algorithme, on calcule des boîtes englobants les objets. Puis, pour chaque paire d'objets potentiellement en collision, un axe de visualisation est choisi et l'ensemble de la surface de chaque objet est rendu dans une variété de textures (LDI). On visualise les surfaces contenues dans l'intersection des io boîtes englobantes, une visualisation étendue selon la direction de visualisation de façon à inclure toutes les couches de surface. La détection de collision est ensuite effectuée compte tenu des paires de texels (texture pixel) consécutifs, ou triplets pour l'auto-collision, le long de l'axe de visualisation. Cette méthode simple et rapide évite des opérations de 15 prétraitement. Cependant, ce document traite uniquement de la détection de collision et reste muet quant au calcul des forces de contact. La présente invention a pour but de remédier aux inconvénients précités en limitant notamment les calculs géométriques complexes. 20 Un autre but de l'invention est une méthode permettant de calculer rapidement les forces de contact des objets simulés rigides et déformables, sans faire appel à des pré-traitements géométriques. On atteint au moins l'un des objectifs précités avec un procédé de 25 simulation interactive d'une intersection entre au moins deux objets volumiques modélisés au moyen de primitives géométriques, notamment des surfaces triangulaires. Ce procédé comprend les étapes suivantes : a) on détermine un polyèdre englobant un volume d'intersection entre les deux objets, 30 b) pour un axe de visualisation donné du polyèdre, on applique un algorithme des � Images à plan de profondeurs � LDI de façon à déterminer un ensemble de pixels de contact ; ces pixels étant des éléments de la surface du volume d'intersection des objets simulés. Selon l'invention, on réalise en outre les étapes suivantes : 35 c) on calcule la taille (en mètres cubes) du volume d'intersection à partir des pixels de contact, -4 - d) à chaque sommet des primitives géométriques dans le polyèdre, on calcule une dérivée partielle de la taille du volume d'intersection V par rapport à sa coordonnée selon l'axe de visualisation, e) on répète au moins les étapes b) et d) pour deux autres axes de visualisation orthogonaux de façon à déterminer des dérivées partielles selon trois axes orthogonaux, on obtient alors un vecteur gradient, et f) à chaque sommet des primitives géométriques des objets, on associe une force f calculée à partir desdites dérivées partielles. io Ces étapes sont exécutées en statique, il n'y a pas d'intégration temporelle. Les deux objets peuvent être deux parties d'une même entité, ce qui permet de traiter l'auto-collision. Avec le procédé selon l'invention on modélise par algorithme LDI les 15 surfaces de contact sous forme de champs de hauteurs échantillonnés selon trois directions orthogonales. Des forces de pression agissant sur la surface de contact peuvent alors être calculées d'après les dérivées partielles du volume d'intersection dans les trois directions. Aucun document de l'art antérieur ne décrit la réalisation de l'algorithme LDI sur 20 trois axes orthogonaux et le calcul de la force à partir des dérivées partielles du volume d'intersection. Ces dérivées partielles peuvent être avantageusement calculées à partir d'images crées au sein d'une carte graphique. Par conséquent, on peut utiliser un matériel graphique standard tel qu'une carte graphique d'ordinateur personnel pour calculer les forces 25 de contact entre objets simulés. La présente invention est une méthode à base d'images qui est capable de directement calculer les composants des forces de contact qui sont appliquées au niveau des sommets de triangles. Plus précisément, on étend l'algorithme LDI en élaborant un nouveau modèle géométrique basé 30 sur les pixels. Non seulement on modélise le volume d'intersection, mais on modélise également sa dérivée par rapport aux coordonnées des sommets. On peut alors efficacement prendre en compte des intersections profondes tout en évitant des calculs géométriques complexes. 35 Par ailleurs, le polyèdre est défini comme étant un volume issu de l'intersection entre deux boîtes englobant respectivement les deux objets. -5 - De préférence, il s'agit d'un parallélépipède rectangle, les trois axes de visualisation étant trois axes orthogonaux de ce parallélépipède rectangle. Le calcul des forces est indépendant des dynamiques internes des objets et les surfaces peuvent être attachées à divers modèles physiques. Selon l'invention, à l'étape b) on peut associer à chaque pixel de contact : - une valeur de hauteur, io - un identifiant de la primitive géométrique associée à ce pixel, - un identifiant de l'objet auquel appartient ce pixel, - une orientation de la normale à la primitive géométrique associée à ce pixel, et des coordonnées barycentriques sur la primitive géométrique associée à 15 ce pixel. Le volume d'intersection V peut être calculé de différentes manières. Un exemple de réalisation est de modéliser par des rectangles la surface définie par le volume d'intersection vu selon l'axe de visualisation (cela 20 correspond à une vue en coupe du volume d'intersection). Dans ce cas, à l'étape c), on calcule le volume d'intersection V à partir de l'équation suivante : V =a L (ù1)d zi , � a � étant l'aire d'un pixel ; � C � un ensemble 25 d'indices de pixels qui couvrent la surface du volume d'intersection ; z;,; la hauteur des pixels de contact ; � d � étant égale à 2 ou à 1 selon qu'il s'agisse d'un pixel supérieur ou d'un pixel inférieur, cette notion de pixel supérieur ou inférieur est définie dans l'algorithme LDI. En effet, dans la représentation en champs de hauteur, une collision fait intervenir une paire 30 de pixels, un pixel supérieur et un pixel inférieur ; � d � est égale à 2 pour le pixel supérieur, � d � est égale à 1 pour le pixel inférieur. Selon l'invention, pour calculer la force on suppose que les forces de répulsion ont tendance à minimiser le volume d'intersection. On définit donc une énergie potentielle E associée au volume d'intersection V. -6 - Avantageusement, à l'étape f), la force peut être définie par l'équation suivante : aE f=-- ax , x étant un vecteur de coordonnées de sommets. Avantageusement, cette énergie E est une fonction croissante du volume d'intersection V. La force correspondante est donc proportionnelle au gradient du volume. On peut par exemple définir l'énergie potentielle E par l'équation suivante : E=1kV2 f=ùkVV io 2 , et obtenir ax , k étant un nombre positif. Les forces de répulsions sont parallèles à la normale aux triangles et proportionnelles à leur aire puisque le gradient de volume (dérivée partielle du volume) indique la direction de variation maximum du volume. Les forces peuvent être interprétées comme étant la somme des forces de 15 pression intégrées sur la surface du volume d'intersection. Selon une caractéristique avantageuse de l'invention, la dérivée partielle du volume d'intersection par rapport à la coordonnée z d'un sommet A l'axe de la LDI est définie par l'équation suivante : aV = a L (ù1)d az1'J az~,j 20 On peut noter que le terme az correspond en fait au coefficient d'ombrage (barycentrique) de Gouraud, généralement utilisé pour interpoler la hauteur et la couleur d'un pixel (i, j). Selon un mode de mise en oeuvre avantageux de l'invention, à l'étape e) on répète également l'étape c), le volume d'intersection V à 25 considérer pour les étapes suivantes étant 1/3 d'une valeur obtenue en sommant le volume d'intersection calculée à chaque répétition. Cette technique permet d'approcher la valeur exacte du volume d'intersection par sa valeur moyenne sur les trois axes de visualisation. Avantageusement, le dispositif peut comprendre en outre au moins 30 un registre de volume pour stocker des valeurs de volume d'intersection calculées, et un registre de gradient consistant en un vecteur contenant -7 - trois valeurs scalaires par sommet, chacune associée à un axe de visualisation. Selon un mode de mise en oeuvre de l'invention, pour une simulation interactive dynamique, on peut utiliser une matrice de raideur pour encoder la variation des forces en réponse à la variation des positions des vertices. Cette matrice de raideur peut être déterminée en calculant un différentiel de la force f, et approximée selon la formule suivante si l'on part d'une équation précédente : af __aVkaVT ax ax ax Selon un autre aspect de l'invention, il est proposé un dispositif de simulation interactive d'une intersection entre au moins deux objets volumiques modélisés au moyen de primitives géométriques. Selon l'invention, ce dispositif comporte une unité de traitement graphique GPU mettant en oeuvre un procédé tel que décrit précédemment de façon à calculer des forces de contact. Le dispositif peut être une machine globale longeant l'unité de traitement graphique GPU ainsi qu'une unité centrale de traitement CPU (Central Processing Unit) apte à récupérer des images calculées par l'unité de traitement graphique et à en déduire les forces à appliquer sur les deux objets. D'autres avantages et caractéristiques de l'invention apparaîtront à l'examen de la description détaillée d'un mode de mise en oeuvre nullement limitatif, et des dessins annexés, sur lesquels : La figure 1 est une vue générale simplifiée d'une unité de traitement graphique en communication avec une CPU, Les figures 2 et 3 illustrent des étapes de mise en oeuvre de l'algorithme LDI, et Les figures 4 à 7 sont des vues simplifiées en deux dimensions de deux objets en intersection à différentes stades du procédé selon l'invention pour le calcul des forces de contact. -8 - A titre d'exemple non limitatif, la présente invention peut être mise en oeuvre au sein d'un processeur graphique GPU destiné à créer des pixels à partir de surfaces triangulaires. Sur la figure 1 on voit de façon très schématique une carte graphique 1 communiquant avec un processeur CPU 2. La carte graphique est dotée notamment d'un processeur graphique GPU 3, d'une zone mémoire 4 et de connecteurs 5, 6 pour communiquer avec la CPU 2 et un moyen d'affichage non représenté. Dans cette zone mémoire 4 on distingue en particulier un registre de volume 7 pour stocker des valeurs de volume d'intersection calculées et un registre de gradient 8 pour stocker io un vecteur contenant les dérivées partielles par rapport à chaque sommet d'une surface triangulaire conformément à l'invention. Ces registres 7, 8 peuvent également se trouver dans une mémoire RAM du côté CPU. De préférence, la carte graphique exécute l'algorithme LDI dont les données de sortie sont récupérées puis traitées par le processeur CPU pour 15 le reste des opérations selon l'invention. De même, l'ensemble du processus selon l'invention peut également s'exécuter sur le processeur CPU directement. On va maintenant décrire en référence aux figures 2 et 3 la 20 technique LDI appliquée à deux objets en intersection. On commence par définir une boîte englobante 9, 10 autour de chaque objet 11, 12. On identifie ensuite un parallélépipède rectangle 13 qui est l'intersection entre les deux boîtes englobantes 9 et 10. Ce parallélépipède rectangle 13 contient le volume d'intersection qui est le volume rempli par une partie de 25 l'objet 11 et une partie de l'objet 12. Le volume d'intersection 14 est représenté en pointillé sur la figure 2. A l'origine, les objets 11 et 12 sont simulés en trois dimensions. Mais sur cette figure 2, on a choisi un axe de visualisation de sorte que les objets 11 et 12 sont représentés en deux dimensions. Dans le 30 parallélépipède rectangle 13, les surfaces de contact sont représentées par les traits délimitant les objets 11 et 12. Ensuite, on échantillonne ces surfaces contenues dans le plan de la figure 2. Sur la figure 3 on voit un tel échantillonnage : il s'agit d'un échantillonnage régulier, chaque échantillon ou pixel étant déterminé comme point de croisement entre une droite 35 horizontale et un trait (ou surface) contenu dans le parallélépipède rectangle 13. Sur la figure 3 on voit une pluralité de ces droites -9 - horizontales 15 qui croisent les traits délimitant les objets 11 et 12 en des échantillons ou pixels 16a-16d. Ensuite, on réalise une projection de ces pixels 16a-16d selon une direction horizontale. Les surfaces sont alors représentées comme des champs de hauteurs. Comme plusieurs surfaces peuvent se projeter en un même point, on utilise plusieurs couches. La première couche cl est constituée d'échantillons 16a de premier ordre : c'est-à-dire des échantillons issus d'un premier croisement entre chaque droite horizontale 15 et un trait dans le parallélépipède rectangle 13. La couche c2 contient les échantillons 16b de second ordre correspondant au io deuxième croisement entre chaque droite horizontale 15 et les traits à l'intérieur du parallélépipède rectangle 13. Il en est de même pour la couche c3 contenant les échantillons 16c et la couche c4 contenant l'unique échantillon 16d (issu d'une seule ligne 15 qui croise pour la quatrième fois une surface dans le parallélépipède rectangle 13). Les pixels de contact 15 sont les échantillons délimitant le volume d'intersection 14. Chaque échantillon contient sa hauteur, un identifiant de la primitive géométrique associée, un identifiant de l'objet auquel il appartient, une orientation de la normale à la primitive géométrique associée, et des coordonnées barycentriques sur la primitive géométrique associée. 20 Sur les figures suivantes on va voir un peu plus détails la façon de calculer et d'appliquer les forces de contact. Sur les figures 4 à 7 on voit un autre exemple d'intersection entre deux objets 17 et 18. L'objet 17 est presque entièrement contenu dans l'objet 18. Chaque objet est modélisé selon des primitives triangulaires et 25 on distingue des sommets A à m qui sont en fait les sommets des polygones représentant les objets 17 et 18 sur les figures 4 à 7. Le volume d'intersection 19 est illustré par un polygone en pointillé 23 majoritairement délimité par la surface de l'objet 17 et par une arête de l'objet 18. Ce pointillé 23 représente les surfaces de contact entre les deux objets. Les 30 zones 20 et 21 illustrent les forces de contact. La zone 20 représente la force de contact appliquée par l'objet 18. Les zones 21 représentent les forces de contact appliquées par l'objet 17. Conformément à la présente invention on va appliquer l'algorithme LDI à l'intersection des objets 17 et 18 selon trois axes de visualisation ou axes de projection orthogonaux. 35 Pour simplifier l'exposé, les figures 5 et 6 illustrent uniquement les -10 ù projections selon deux axes orthogonaux : horizontal sur la figure 5, vertical sur la figure 6. Sur la figure 5, on voit un échantillonnage des surfaces dans la direction verticale. Chaque trait est un pixel. L'échantillonnage est réalisé selon des couloirs horizontaux. Le cadre 22 est une représentation en champs de hauteurs c'est-à-dire sous forme de couches de pixels échantillonnés sur les surfaces des deux objets 17 et 18. Les signes � + � et � - � dans le cadre 22 correspondent au sens de la pression de répulsion sur le pixel correspondant. Le cadre 22 aide à identifier les intersections io entre objets et à identifier les pixels de contact, c'est-à-dire les pixels des surfaces de contact. Sur les figure 5 et 6, les pixels de contact portent chacune une flèche représentant la pression de répulsion. La figure 6 illustre une projection verticale. De la même manière que sur la figure 5, les pixels obtenus après échantillonnage sont représentés par des petits 15 tirés, mais qui sont horizontaux cette fois-ci. Les pixels de contact portent également des flèches représentant des pressions de répulsion. Le calcul des forces de contact au niveau de chaque sommet A à m passe par un calcul du volume d'intersection 19 selon les trois axes de visualisation. On va voir ce calcul uniquement pour la projection verticale 20 de la figure 6. Le calcul est identique pour les autres axes de visualisation. Selon l'invention, le volume est calculé selon la formule suivante : V =a L (ù1)d zi (i,i c Pratiquement, � a � est l'aire de chaque pixel de contact. i,j 25 permettent d'identifier chaque pixel de contact de la figure 6. Pour le pixel de contact 24 (situé sur une arête de l'objet 17) par exemple, la hauteur z; liée à ce pixel est sa hauteur dans le repère z tel que représenté sur la figure 6 (axe des ordonnées parallèle à l'axe de projection) ; � d � est égale à 1. Par contre pour le pixel de contact 25 (situé sur une arête de 30 l'objet 18), la hauteur z;,; liée à ce pixel est sa hauteur dans le repère z tel que représenté sur la figure 6 ; � d � est égale à 2. Avec les pixels de contact 24 et 25, on comprend que le calcul du volume d'intersection revient à calculer le volume de la partie hachurée sur la figure 6. 24 est un pixel de contact inférieur. 25 est un pixel de contact supérieur. 15 20 -11 - Le volume d'intersection est calculé selon un seul axe de visualisation ou bien pour chaque axe de visualisation, dans ce dernier cas, on prendra la moyenne des trois valeurs de volume d'intersection calculées. Une fois le volume calculé, on calcule pour chaque axe de visualisation et au niveau de chaque sommet A-M, la dérivée partielle du volume par rapport à la hauteur, dans l'exemple de la figure 6 c'est par rapport à l'axe z qui est l'axe de projection. Pour ce faire, on utilise avantageusement l'équation : aV = a (_l)d az~'1 On applique cette formule donc pour chaque sommet selon les trois axes de visualisation. On obtient ainsi un vecteur gradient de la forme : aV (aV aV aV aV ax axg ' ayg ' azg ' axB , ... Selon l'invention, si l'on définit une énergie potentielle par : E=1kV2 2 Alors la force de contact est : f =-kV aV , k étant un nombre positif. En fait, il suffit de récupérer le vecteur gradient calculé précédemment et de multiplier par -kV. 25 La présente invention permet donc de calculer des forces de contact dans une simulation d'objets mécaniques. Les objets simulés sont munis de surfaces de contact qui interagissent quand les objets s'intersectent. L'invention consiste à modéliser les surfaces de contact sous forme de champs de hauteurs échantillonnés selon trois directions orthogonales, puis 30 à calculer les dérivées du volume d'intersection par rapport aux coordonnées des sommets des triangles selon chaque direction de l'espace, en utilisant trois LDI dans des directions orthogonales. La force de pression -12 - agissant sur une surface de contact peut alors être calculée d'après ces dérivées partielles. Bien sûr, l'invention n'est pas limitée aux exemples qui viennent 5 d'être décrits et de nombreux aménagements peuvent être apportés à ces exemples sans sortir du cadre de l'invention. REVENDICATIONS 1. Procédé de simulation interactive d'une intersection entre au moins deux objets volumiques modélisés au moyen de primitives géométriques ; procédé dans lequel : a) on détermine un polyèdre englobant un volume d'intersection V entre les deux objets, b) pour un axe de visualisation du polyèdre, on applique un algorithme des � Images à plan de profondeurs � LDI de façon à déterminer un ensemble de io pixels de contact, caractérisé en ce qu'on réalise en outre les étapes suivantes : c) on calcule la taille du volume d'intersection V à partir des pixels de contact, d) à chaque sommet des primitives géométriques dans le polyèdre, on calcule une dérivée partielle de la taille du volume d'intersection V par rapport à la 15 coordonnée du sommet selon l'axe de visualisation, e) on répète au moins les étapes b) et d) pour deux autres axes orthogonaux de façon à déterminer des dérivées partielles selon trois axes orthogonaux, et f) à chaque sommet des primitives géométriques des objets, on associe une 20 force f calculée à partir desdites dérivées partielles. 2. Procédé selon la revendication 1, caractérisé en ce que la dérivée partielle du volume d'intersection pour un sommet A selon un axe de visualisation z est définie par l'équation suivante : aV ù=a (_1)d az~,~ 25 aZ (i>>)Ec aZ , � a � étant l'aire d'un pixel, � C � un ensemble d'indices de fragments qui couvrent la surface du volume d'intersection, z;,; la hauteur des pixels de contact, � d � étant égale à 2 ou à 1 pour respectivement un pixel supérieur ou un pixel inférieur dans la projection selon l'algorithme LDI. 30 3. Procédé selon la revendication 1 ou 2, caractérisé en ce qu'à l'étape f), la force est définie par l'équation suivante :-14 - f =--, ox E étant une énergie potentielle qui est une fonction croissante du volume d'intersection V, et x un vecteur de coordonnées de sommets. 4. Procédé selon la revendication 3, caractérisé en ce que l'énergie potentielle E est définie par l'équation suivante : E=1kV2 f=-kVaV 2 , soit ax , k étant un nombre positif 5. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'à l'étape c), on calcule le volume d'intersection V à partir de l'équation suivante : V =a L (ù1)d zi (i,j c � a � étant l'aire d'un pixel, � C � un ensemble d'indices de fragments qui couvrent la surface du volume d'intersection, z;,; la hauteur des pixels de contact, � d � étant égale à 2 ou à 1 pour respectivement un pixel supérieur ou un pixel inférieur dans la projection selon l'algorithme LDI. 6. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'à l'étape e) on répète également l'étape c), le volume d'intersection à considérer pour les étapes suivantes étant 1/3 d'une valeur obtenue en sommant le volume d'intersection calculée à chaque répétition. 7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'à l'étape b) on associe à chaque pixel de contact : -une valeur de hauteur, - un identifiant de la primitive géométrique associée à ce pixel de contact, - un identifiant de l'objet auquel appartient ce pixel de contact, - une orientation de la normale à la primitive géométrique associée à ce pixel de contact, et - des coordonnées barycentriques sur la primitive géométrique associée à ce pixel de contact. 8. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que les primitives géométriques sont des surfaces triangulaires. 5-15 - 9. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le polyèdre est défini comme étant un volume issu de l'intersection entre deux boîtes englobant respectivement les deux objets. 10. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que pour une simulation interactive dynamique, on utilise une matrice de raideur pour encoder la variation des forces en réponse à la variation des positions des sommets. i0 11. Procédé selon la revendication 10, caractérisé en ce que la matrice de raideur est déterminée en calculant un différentiel de la force f. 12. Dispositif de simulation interactive d'une intersection entre au moins deux 15 objets volumiques modélisés au moyen de primitives géométriques ; caractérisé en ce que ce dispositif comporte une unité de traitement graphique GPU mettant en oeuvre un procédé selon l'une quelconque des revendications précédentes de façon à calculer des forces de contact. 20 13. Dispositif selon la revendication 12, caractérisé en ce qu'il comprend en outre au moins un registre de volume pour stocker des valeurs de volume d'intersection calculées, et un registre de gradient consistant en un vecteur contenant trois valeurs scalaires par sommet, chacune associée à un axe de visualisation. 25 14. Dispositif selon la revendication 12 ou 13, caractérisé en ce qu'il comprend en outre une unité centrale de traitement CPU apte à récupérer des images calculées par l'unité de traitement graphique et à en déduire les forces à appliquer sur les deux objets. 30