Brevet FR2919087A1 — publié le 20090123

PROCÉDÉ DE CONSTRUCTION D'UNE SIRtUCTURE DE DONNÉES UTILISÉE POUR LA RECHERCHE DE PARTICULE PROCHE, PROGRAMME CORRESPONDANT ET SUPPORT DE STOCKAGE POUR STOCKER LE PROGRAMME ARRIÈRE-PLAN DE L'INVENTION 1. Domaine de l'invention La présente invention concerne un procédé de construction d'une structure de données utilisée pour la recherche de particule proche, telle qu'on obtient un procédé pour accélérer une recherche de particule proche en exécutant jusqu'au bout une simulation basée sur des particules en utilisant un GPU ou un autre processeur en continu et on peut effectuer par exemple en temps réel un calcul de collision ou analogue d'un grand nombre de corps rigides ; un programme du procédé de construction d'une structure de données ; et un support de stockage pour stocker le programme. 2. Description de la technique associée Une simulation basée sur des particules est un procédé de simulation pour effectuer des calculs concernant le comportement de chaque particule d'un grand nombre de particules dans lequel l'objet de la simulation est un groupe (agrégation) d'un grand nombre de particules. Pour le calcul par un ordinateur, on utilise habituellement comme particules des sphères ayant un diamètre constant. Lorsqu'on exprime la forme de l'objet par une agrégation de sphères, le degré d'approximation ou la résolution spatiale varie selon le procédé de détermination de la taille (diamètre) des sphères. En faisant varier le diamètre des sphères et en faisant varier la résolution spatiale, on permet de contrôler la précision du calcul et la vitesse de calcul dans le calcul de simulation par ordinateur. Au cours de ces dernières années, on a utilisé la simulation basée sur des particules mentionnée ci-dessus pour calculer les collisions d'un grand nombre de corps rigides et pour calculer le comportement de fluides, de corps particulaires et analogue, et pour des simulations de recherche de collision, écoulement et analogue, sur l'écran d'un dispositif d'affichage d'ordinateur. Les résultats de cette recherche sont décrits dans Development of a rigid body calculation method using a particle method, and application thereof to computer graphics de M. Tanaka et al., Japan Society of Mechanical Engineers , Actes de la 19t" Computational Mechanics Conference , pp. 701-702, 2006. La recherche sur ces techniques de simulation est importante pour la technologie qui constitue les fondements de l'infographie (CG). Dans la recherche sur la simulation basée sur des particules décrite ci-dessus, on a utilisé dans le passé un grand nombre de procédés pour utiliser un CPU pour créer un algorithme de calcul. Toutefois, peu de recherches ont été menées concernant des simulations basées sur des particules dans lesquelles on utilise activement un GPU (unité de traitement graphique) ou un autre processeur en continu. Dans une telle recherche antérieure utilisant un GPU, on a effectué par exemple une recherche de particule proche au moyen d'un CPU et on a transféré à un GPU pour traitement d'image les données de recherche obtenues par le CPU. Selon cette technique, on utilise le CPU comme unité d'exécution de calcul primaire, l'algorithme de calcul de la recherche de particule proche est exécuté par le CPU et le GPU, comme unité d'exécution de calculs auxiliaires, exécute seulement un algorithme de calcul pour le traitement de l'affichage d'image. En conséquence, la technique de calcul classique n'a pas été configurée de façon que les algorithmes de calcul de la recherche de particule proche et du traitement d'image de la simulation basée sur des particules soient achevés et exécutés uniquement à l'intérieur du GPU. Puisque dans le calcul classique de simulation basée sur des particules, on n'adopte pas une configuration dans laquelle l'ensemble du calcul (traitement d'image, construction de la structure de données utilisée dans la recherche de particule proche et analogue) n'est achevé que par le GPU, le rendement du calcul est insatisfaisant, la capacité de traitement d'image inhérente au GPU ne peut pas être prouvée de manière adéquate et il est impossible d'effectuer un calcul de collision d'un grand nombre de corps rigides et d'autres simulations en temps réel de corps rigides, simulations de fluide et analogue. Il existe en conséquence un besoin pour mettre au point un procédé pour utiliser jusqu'au bout un GPU ou un autre processeur en continu pour effectuer la construction d'une structure de données utilisée dans une recherche de particule proche par le GPU ou analogue et pour démontrer la capacité de traitement d'image maximale du GPU. RÉSUMÉ DE L'INVENTION Considérant les problèmes mentionnés ci-dessus, un objectif de la présente invention est de fournir un procédé de construction d'une structure de données utilisée dans une recherche de particule proche, tel qu'un GPU ou un autre processeur en continu peut achever la construction de la structure de données utilisée dans la recherche de particule proche d'une simulation basée sur des particules, on peut utiliser efficacement le GPU ou analogue, on peut prouver la capacité maximale de traitement (d'image) du GPU, on peut activer une vitesse de calcul élevée et on peut effectuer un traitement de calcul/traitement d'affichage, par exemple, pour une simulation d'un corps rigide en temps réel, une simulation d'un corps fluide ou analogue, et fournir un programme pour le procédé de construction de structure de données et un support de stockage pour stocker le programme. Pour atteindre les objectifs mentionnés ci-dessus, le procédé de construction d'une structure de données utilisé dans une recherche de particule proche, son programme et le support de stockage pour stocker le programme selon la présente invention, sont constitués comme décrit ci-dessous. Le procédé de construction d'une structure de données est utilisé par un procédé exécuté par un processeur de calcul graphique tel qu'un GPU ou analogue pour calculer une simulation d'un objet physique en convertissant des données d'images numériques tridimensionnelles construites à partir de données d'images créées dans une mémoire vidéo en données d'images numériques bidimensionnelles, caractérisé en ce que l'objet physique est indiqué sous la forme d'un grand nombre de particules et on utilise un procédé pour déterminer l'état d'existence de l'objet physique en se basant sur une relation de position de stockage parmi le grand nombre de particules dans une structure de données d'images tridimensionnelles de la mémoire vidéo. Une texture de compartiment incluse dans la structure de données d'images tridimensionnelles est constituée d'un compartiment dans lequel est divisé un espace mémoire créé conformément à un espace dans lequel l'objet physique apparaît et un numéro de particule affecté au grand nombre de particules est stocké dans chacun des nombreux compartiments ; et une étape d'écriture est prévue dans laquelle les coordonnées de particule et le numéro de particule de la particule stockée dans le compartiment sont lus et écrits dans un espace d'images bidimensionnel par le processeur de calcul graphique en utilisant un nuanceur de sommet. Dans l'étape d'écriture, le numéro de particule et les coordonnées de particules de chaque particule de la pluralité de particules sont écrits un par un lors d'un rendu d'une pluralité de cycles de traitement lors d'un intervalle unique d'une simulation lorsqu'une pluralité de particules sont présentes dans le compartiment. Dans le procédé mentionné ci-dessus pour construire une structure de données, lorsqu'on utilise un GPU en tant que processeur de calcul graphique, la sélection d'un pixel écrit et d'un numéro de particule de la particule écrite dans chaque rendu pendant la pluralité de cycles de traitement, et la sélection d'un canal dans le pixel écrit, sont effectuées en utilisant des fonctions d'un test pochoir, un masque de couleur et un test de profondeur qui sont préparées par le GPU. Lorsqu'on utilise un processeur en continu incluant un GPU ou analogue, on peut également effectuer la sélection du numéro de particule et de l'emplacement mémoire des particules écrits à chaque étape d'une pluralité de cycles d'un cycle de traitement, et la sélection de l'emplacement mémoire en mémoire qui est alloué à un voxel, en utilisant les fonctions d'une pluralité de compteurs préparés par le processeur en continu. De façon spécifique, le procédé est destiné à construire une structure de données utilisée dans une recherche de particule proche, qui est utilisé dans un procédé exécuté par un processeur en continu, pour calculer une simulation d'un objet physique en convertissant des données d'images numériques tridimensionnelles construites à partir d'une matrice de données créée dans la mémoire en données d'images numériques bidimensionnelles. On utilise un procédé dans lequel l'objet physique est indiqué par un grand nombre de particules et l'état d'existence de l'objet physique est déterminé en se basant sur la relation de position de stockage parmi le grand nombre de particules dans les données d'image tridimensionnelle située dans la mémoire. Une matrice de compartiment incluse dans les données d'images tridimensionnelles est constituée de compartiments pour allouer des espaces mémoire qui sont créés de façon à correspondre à des espaces dans lesquels apparaît l'objet physique et les numéros de particules affectées au grand nombre de particules sont respectivement stockés pour un grand nombre de compartiments. Le procédé comporte une étape d'écriture dans laquelle le numéro de particule et les coordonnées de particule d'une particule stockée dans un compartiment sont lus par le processeur en continu et écrits dans une matrice de la mémoire en utilisant une opération de dispersion du processeur en continu et lorsqu'une pluralité de particules sont présentes dans un compartiment à l'étape d'écriture, les numéros de particules et les coordonnées de particules de la pluralité de particules sont divisés dans un noyau pendant une pluralité de cycles de traitement et lus un par un dans un intervalle unique de la simulation. Dans le procédé mentionné ci-dessus pour construire une structure de données, on stocke en séquence un numéro de particule à partir des numéros de particules qui sont en ordre ascendant ou en ordre descendant, séparément pour chacun des quatre canaux ou analogue, constitués de RGBA d'un pixel ou analogue pour lequel le numéro de particule est écrit lorsque quatre des particules sont présentes dans le compartiment. Le procédé mentionné ci-dessus pour construire une structure de données comprend de façon plus spécifique les étapes décrites ci-dessous lorsqu'on utilise un GPU en tant que processeur de calcul graphique. Le procédé comprend l'écriture d'un numéro de particule iba dans le canal R et l'exécution d'un rendu par un premier sous-programme en initialisant un tampon de profondeur à une valeur maximale et en acceptant des éléments ayant une faible valeur en utilisant un test de profondeur lors de l'écriture du pixel durant un premier passage ; l'écriture d'un numéro de particule ibl dans le canal G et l'exécution d'un rendu par un deuxième sous-programme en utilisant un masque de couleur pour interdire l'écriture dans le canal R et en utilisant un test pochoir lors de l'écriture dans le pixel durant un deuxième passage ; l'écriture d'un numéro de particule ib2 dans le canal B et l'exécution d'un rendu par un troisième sous-programme en utilisant un masque de couleur pour interdire l'écriture dans les canaux R et G, et en utilisant un test pochoir lors de l'écriture dans le pixel durant un troisième passage ; et l'écriture d'un numéro de particule ib3 dans le canal A et l'exécution d'un rendu par un quatrième sous-programme en utilisant un masque de couleur pour interdire l'écriture dans les canaux R, G et B et en utilisant un test pochoir lors de l'écriture dans le pixel durant un troisième passage ; les numéros de particules des quatre particules étant ibo, ibi, ib2 et ib3 (où ibO ib1 > ib2 > ib3 dans le cas de l'ordre descendant). Lorsqu'on utilise un processeur en continu, on utilise généralement la mémoire allouée à un voxel à la place du pixel mentionné ci-dessus (pixel écrit), on utilise un emplacement mémoire dans la mémoire allouée à un voie! à la place du canal mentionné ci-dessus et on utilise des fonctions de compteur correspondantes à la place des fonctions du test de profondeur, du masque de couleur et du test pochoir mentionnées ci-dessus, préparées par le GPU. De façon spécifique, le procédé comprend l'écriture du numéro de particule ibo au premier emplacement mémoire et l'exécution d'un noyau par un premier sous-programme en initialisant le compteur à a et en acceptant la première écriture au premier emplacement mémoire lors de l'écriture dans la mémoire allouée au voxel durant un premier passage ; l'écriture du numéro de particule ibi au deuxième emplacement mémoire et l'exécution d'un noyau par un deuxième sous-programme en utilisant le compteur pour interdire l'écriture au premier emplacement mémoire, et l'écriture de la valeur suivante au deuxième emplacement mémoire lors de l'écriture dans la mémoire allouée au voxel durant un deuxième passage ; l'écriture du numéro de particule ib2 au troisième emplacement mémoire et l'exécution d'un noyau dans un troisième sous-programme en utilisant le compteur pour interdire l'écriture aux premier et deuxième emplacements mémoire, et l'écriture de la valeur suivante au troisième emplacement mémoire lors de l'écriture dans la mémoire allouée au voxel durant un troisième passage ; et l'écriture du numéro de particule ib3 au quatrième emplacement mémoire et l'exécution d'un noyau dans un quatrième sous-programme en utilisant le compteur pour interdire l'écriture aux premier, deuxième et troisième emplacements mémoire, et l'écriture de la valeur suivante au quatrième emplacement mémoire lors de l'écriture dans la mémoire allouée au voxel durant un quatrième passage ; les numéros de particule des quatre particules étant ibo, ibi, ib2 et ibi (où Ibp ibi > ib2 > ib3 dans le cas de l'ordre descendant). Dans le procédé de construction d'une structure de données mentionné ci-dessus, l'objet physique est constitué d'un grand nombre de corps rigides et on exécute le calcul d'une simulation basée sur le calcul de collision du grand nombre de corps rigides. Dans le procédé de construction d'une structure de données mentionné ci-dessus, le GPU mentionné ci-dessus comme exemple de processeur en continu est un processeur de calcul graphique. Le programme de construction d'une structure de données utilisé dans la recherche de particule proche décrite précédemment selon la présente invention est un programme pour exécuter les sous-programme et analogue constituant le procédé de recherche de particule proche décrit ci-dessus par un processeur en continu qui comporte un GPU ou analogue. La présente invention permet d'obtenir les effets suivants. Dans un procédé de simulation d'un phénomène physique sur un ordinateur en appliquant une simulation basée sur des particules pour effectuer l'approximation d'un corps rigide, un corps fluide, un corps particulaire ou analogue et en mettant en oeuvre un procédé de construction d'une structure de données utilisée dans une recherche de particule proche, on adopte une configuration dans laquelle les sous-programmes pour exécuter des calculs pour construire la structure de données utilisée dans la recherche de particule proche sont entièrement exécutés par un GPU ou autre processeur en continu, on utilise efficacement le GPU ou analogue, on peut prouver la capacité maximale de traitement de calcul d'image du GPU et on peut effectuer un calcul à grande vitesse, de sorte qu'on peut par exemple effectuer en temps réel, une simulation de corps rigide, une simulation de corps fluide ou analogue. On peut également utiliser la présente invention comme technologie élémentaire importante optimale pour un jeu ou analogue dans lequel on exprime de l'eau qui s'écoule et d'autres objets naturels en utilisant en tant que simulation de CG, une simulation de corps rigides, une simulation de corps fluide ou analogue dans un dispositif d'affichage d'image. BRÈVE DESCRIPTION DES DESSINS Ces objectifs et caractéristiques de la présente invention ainsi que d'autres deviendront plus clairs d'après la description qui suit des modes de réalisation préférés, fournie en référence aux dessins annexés, dans lesquels : la figure 1 est un schéma de structure de système représentant la structure de base du système informatique pour mettre en oeuvre le procédé de construction d'une structure de données utilisée dans une recherche de particule proche selon la présente invention ; la figure 2 est un schéma par blocs montrant la structure de base de l'intérieur du GPU installé dans le système informatique ; la figure 3 est un schéma montrant une image d'effet (CG) basée sur une simulation de corps rigides concernant le phénomène physique de chute/collision de 10 922 tores ; la figure 4 est un schéma montrant une image d'effet (CG) basée sur une simulation de corps rigides concernant le phénomène physique de chute/collision de 16 384 pièces d'échecs ; la figure 5 est un organigramme représentant l'algorithme de calcul de l'accélération d'une simulation de corps rigides en utilisant le GPU ; la figure 6 est un organigramme représentant les détails spécifiques des sous-programmes de traitement de construction de 25 compartiments ; la figure 7 est un organigramme montrant un exemple modifié de l'algorithme de calcul d'accélération d'une simulation de corps rigides utilisant le GPU ; la figure 8 est un schéma montrant une image d'effet (CG) 30 basée sur une simulation de corps fluide concernant le phénomène physique lorsqu'une pluralité de corps fluides sphériques tombent dans un corps fluide ; et la figure 9 est un schéma montrant une image d'effet (CG) basée sur une simulation de corps particulaire lorsqu'un corps particulaire 35 contenu dans un récipient en forme d'entonnoir s'écoule vers le bas, tombe à l'extérieur d'une ouverture à l'extrémité inférieure du récipient et est contenu dans un récipient positionné au-dessous de l'ouverture. DESCRIPTION DES MODES DE RÉALISATION PRÉFÉRÉS Des modes de réalisation préférés de la présente invention vont être décrits ci-après en se basant sur les dessins annexés. La figure 1 montre la structure de base du système informatique pour mettre en oeuvre le procédé de construction d'une structure de données utilisée dans une recherche de particule proche selon la présente invention. Dans la description du présent mode de réalisation, un exemple dans lequel on utilise par exemple un GPU en tant que processeur de calcul graphique va être décrit en tant que mode de réalisation principal. Le système informatique 10 est configuré en utilisant par exemple un PC (ordinateur personnel) et il est muni d'un CPU 11 et d'un GPU 12 en tant que processeurs de calcul. Le système informatique 10 est également muni d'une mémoire principale 13A et d'une mémoire vidéo (VRAM) 13B en tant que dispositifs de stockage et il est muni d'au moins un dispositif d'entrée 14 et d'un dispositif d'affichage 15 en tant que dispositifs périphériques. Le CPU 11, le GPU 12, la mémoire principale 13A, le dispositif d'entrée 14 et le dispositif d'affichage 15 sont connectés entre eux par l'intermédiaire d'un bus 16. Le dispositif d'entrée 14 est connecté au bus 16 par l'intermédiaire d'une interface d'entrée 17 et le dispositif d'affichage 15 est connecté au bus 16 par l'intermédiaire d'une interface de sortie 18. La mémoire vidéo 13B est directement connectée au GPU 12. Des données sont échangées avec la mémoire vidéo 13B par l'intermédiaire du GPU 12. Le CPU (dispositif central de traitement de calcul) 11 est par exemple un processeur de calcul courant installé dans un PC ou analogue. Le GPU (unité de traitement graphique) 12 est un processeur de calcul graphique et il exécute un traitement de calcul d'image. On utilise le GPU 12 en tant que dispositif de calcul parallèle constitué d'une pluralité de processeurs contenus à l'intérieur. On utilise par exemple en tant que GPU 12 un GeForce 7900GTX de Nvidia. Le produit utilisé en tant que GPU 12 n'est pas limité à celui-ci et on peut également utiliser un processeur ou un autre processeur en continu pour traitement d'image ayant une structure/des fonctions similaires. Le GPU 12 exécute un programme de recherche de particule proche 13A-1 stocké dans la mémoire principale 13A et met en oeuvre un calcul de recherche de particule proche dans une simulation basée sur des particules. Le programme de recherche de particule proche 13A-1 exécute la construction d'une structure de données utilisée dans une recherche de particule proche. Le GPU 12 exécute également un programme de traitement d'image courant 13A-2 stocké dans la mémoire principale 13A, met en oeuvre un traitement d'images en utilisant des données d'images stockées dans des pixels, qui sont obtenues par calcul de la recherche de particule proche, et utilise les données d'images créées pour le dessin (rendu pour affichage) sur l'écran du dispositif d'affichage 15. Une image de CG est affichée sur l'écran du dispositif d'affichage 15 en se basant sur les calculs de simulation basée sur des particules. Dans la description du présent mode de réalisation fournie ci-après, le calcul d'une simulation en temps réel d'un corps rigide est décrit, basé sur l'exécution de calculs de collision d'un grand nombre de corps rigides sur la base d'une simulation basée sur des particules. Dans le calcul de cette simulation, le GPU 12 uniquement exécute le procédé de construction de structure de données destiné à être utilisé dans la recherche de particule proche. La structure de base des parties appropriées de l'intérieur du GPU 12 mentionné ci-dessus est représentée schématiquement sur la figure 2. Le GPU 12 est muni d'une pluralité de processeurs 21 agencés d'une façon en parallèle et le rendu d'affichage (dessin) est exécuté en se basant sur le traitement de calcul parallèle par les processeurs. Selon le procédé de construction (construction des compartiments) de la structure de données utilisée dans une recherche de particule proche selon le présent mode de réalisation en particulier, lorsque par exemple quatre particules sont présentes dans un compartiment unique, les numéros de particules et les coordonnés de particule des quatre particules sont écrits dans chacun des canaux RGBA d'un pixel unique lors de quatre rendus de traitement répétés. Le traitement de calcul d'image est accéléré par l'intermédiaire du traitement de construction des compartiments dans le GPU 12. De façon plus spécifique, lorsque le GPU 12 est un GeForce 7900GTX , le GPU 12 comporte huit nuanceurs de sommet (VS) 22 agencés en parallèle dans un premier étage et 24 nuanceurs de fragment (FS) 23 agencés en parallèle dans un étage qui suit. Le programme exécuté par les processeurs de sommet 21 est un nuanceur de sommet 22 et le programme exécuté par les processeurs de fragment 21 est un nuanceur de fragment 23. Dans la description ci-dessus, les processeurs de sommet sont des processeurs agencés en parallèle et sont des processeurs qui sont spécialisés pour traiter simultanément une conversion de coordonnées (conversion de coordonnées de sommet d'entrée en coordonnées dans l'espace de l'image rendue) d'un grand nombre de sommets. Le GPU 12 peut calculer une conversion de coordonnées de sommets à grande vitesse par comparaison avec un CPU. Le fonctionnement d'un processeur de sommet est spécifié par un nuanceur de sommet. Le GPU 12 est muni de plus d'une unité de fonction de test de profondeur 24, d'une unité de fonction de masque de couleur 25 et d'une unité de fonction de test pochoir 26. Le bloc 27 est une unité de distribution de commande de nuanceur. Le programme de recherche de particule proche 13A-1 pour exécuter le procédé de construction d'une structure de données utilisée dans une recherche de particule proche selon la présente invention est exécuté jusqu'au bout uniquement par le GPU 12 en utilisant la structure interne du GPU 12 mentionnée ci-dessus. Un mode de réalisation de la simulation de corps rigides des collisions d'un grand nombre de corps rigides va ensuite être décrit. Les détails du procédé de construction d'une structure de données utilisée dans une recherche de particule proche mise en oeuvre en se basant sur l'exécution du programme de recherche de particule proche 13A-1 apparaîtront dans la description de la simulation de corps rigides. Des exemples du grand nombre de corps rigides comportent un grand nombre d'éléments de tores ou un grand nombre de pièces d'échec. Des exemples du CG obtenus en tant que résultats de la simulation de corps rigides du présent mode de réalisation sont représentés sur les figures 3 et 4. La figure 3 représente une image d'effet (CG) basée sur un calcul de collision d'une simulation de corps rigides concernant le phénomène physique de chute/collisions de 10 922 tores ; et la figure 4 représente une image d'effet (CG) basée sur un calcul de collision d'une simulation de corps rigides concernant le phénomène physique de chute/collisions de 16 384 pièces d'échecs. Dans les calculs de collision du grand nombre de corps rigides décrits ci-dessus, les formes du grand nombre de corps rigides sont toutes exprimées et traitées d'une façon approximative comme des agrégations de sphères de même taille (particules) en appliquant un procédé basé sur les particules (simulation basée sur les particules). On effectue l'approximation des formes des corps rigides basées sur des sphères en se basant sur un modèle de polygone des corps rigides et elles sont générées en utilisant un procédé de voxelisation utilisant un GPU ( Fast solid voxelisation using graphics hardware , Actes du JSCES, p. 20060023, 2006) ayant été proposé par les présents inventeurs et d'autres, par exemple. On détermine la taille des sphères utilisées (résolution spatiale) de manière appropriée en prenant en considération la précision de calcul et la vitesse de calcul. Dans le calcul de collision du grand nombre de corps rigides dans lequel les corps rigides sont exprimés approximativement comme une agrégation de sphères, on exécute (1) le calcul de chaque corps rigide, (2) le traitement de détection (calcul de la distance entre les sphères qui constituent les corps rigides) des collisions entre les corps rigides, et (3) le traitement de réponse (calcul de la force et du couple agissant sur la sphère) basé sur la collision. Les concepts de ces calculs sont décrits ci-dessous. (1) Calcul du corps rigide : Les quantités physiques nécessaires pour le calcul d'un corps rigide sont : les coordonnées (x) du centre de gravité, la vitesse de translation (v), un quaternion (q) indiquant l'importance de la rotation, et la vitesse angulaire (w) et le tenseur d'inertie (I). Le calcul du mouvement des corps rigides est divisé en calcul du mouvement de translation et calcul du mouvement de rotation. Les détails de calcul du mouvement de translation sont représentés par les équations 1 à 3 et les détails de calcul du mouvement de rotation sont représentés par les équations 4 à 10. La force F agissant sur un corps rigide se décompose en une force Fc apparaissant en raison de la collision et l'autre force externe Fe, comme représenté dans l'équation (1). F=Fc+Fe (1) La dérivée par rapport autemps de la quantité de mouvement de translation P d'un corps rigide est calculée comme représenté dans l'équation (2) en utilisant la force F agissant sur le corps rigide, dP/dt = F (2) La vitesse v du centre de gravité est calculée d'après P = Mv (où M et la masse du corps rigide) en utilisant la quantité de mouvement de translation P. Lorsqu'on utilise la vitesse v du centre de gravité, la dérivée par rapport au temps de la position du centre de gravité x du corps rigide est indiquée par l'équation (3). dx/dt = v (3) La force F agissant sur un corps rigide provoque un mouvement de rotation du corps rigide et modifie la quantité de mouvement angulaire L. La dérivée par rapport au temps de la quantité de mouvement angulaire L est indiquée par l'équation (4). F est le vecteur allant du centre de gravité du corps rigide jusqu'au point d'action de la force. dL/dt = r x F (4) La vitesse angulaire w est calculée par l'équation (5) en utilisant la quantité de mouvement angulaire L. w = I(t)"1L (5) Dans l'équation (5), I(t)-1 est la matrice inverse du tenseur d'inertie à l'instant t. La matrice inverse 1(t)-1 est calculée par l'équation (6) en utilisant la matrice inverse I(o)-1 du tenseur d'inertie I(o) du corps rigide dans l'état initial. I(t)-1 = R(t)I(o)-1R(t)T (6) Dans l'équation (6), R(t) et R(t)T sont la matrice de rotation et la matrice transposée à l'instant t. Le quaternion q est mis à jour en utilisant la vitesse angulaire w calculée par l'équation (5). L'importance de la variation dq du quaternion est calculée d'après la vitesse angulaire w par l'équation (7). dq = [cos(9/2), asin(e/2)] (7) L'axe de rotation a et l'angle de rotation 0 sont ici calculés par 5 les équations (8) et (9). a = w/Iwl (8) e = lwdtl (9) Le quaternion q(t+dt) après dt est calculé par l'équation (10) en utilisant q(t) au temps t et dq de l'équation (7). 10 q(t + dt) = dq x q(t) (10) (2) Traitement de détection de collision : On calcule la distance entre les sphères qui constituent des corps rigides pour détecter une collision d'un corps rigide. On considère que deux sphères entrent en collision lorsque la distance entre les sphères 15 est inférieure au diamètre des sphères. Dans la détection de collisions entre un grand nombre de corps rigides, on doit exécuter le calcul de distance mentionné ci-dessus en relation avec les sphères qui constituent tous les corps rigides. L'importance du calcul est proportionnelle au carré du nombre de sphères et à mesure que le nombre de corps rigides 20 augmente, le nombre de sphères augmente et l'importance du calcul augmente également. En conséquence, pour diminuer l'importance du calcul dans la configuration du traitement de détection de collision selon le présent mode de réalisation, un espace imaginaire (espace de stockage de données tridimensionnelles dans la mémoire) dans lequel le grand nombre 25 de corps rigides existent est divisé dans une grille (grille d'espace tridimensionnel) appelé compartiment (ou grille) et le grand nombre de sphères qui indiquent respectivement le grand nombre de corps rigides, sont stockés dans les compartiments. Un simple compartiment forme un simple cube et dans le cas où l'on utilise une structure 30 tridimensionnelle dans laquelle la longueur d'un côté du compartiment est la même longueur que le diamètre d'une sphère, les sphères pouvant potentiellement entrer en collision avec une certaine sphère i sont limitées aux sphères qui sont stockées dans les 33 compartiments adjacents au compartiment dans lequel est stockée la sphère i. Une détection de 35 collision est effectuée en se basant sur la construction des compartiments comme décrit ci-dessus, de sorte que l'importance du calcul est réduite et le coût du calcul peut être notablement réduit. Les détails de la construction des compartiments selon le présent mode de réalisation sont décrits ci-après. (3) Réponse basée sur la collision Dans une réponse de collision, on calcule la force appliquée à la sphère qui constitue un corps rigide unique. Dans le calcul de la force de collision, on utilise un ressort linéaire et un amortisseur dans un procédé par éléments distincts en relation avec deux sphères en contact entre elles, Les détails du calcul de la force de collision sont présentés dans les équations 11 à 16. Une force de répulsion proportionnelle à l'importance du décalage et une force d'amortissement proportionnelle à la vitesse relative agissent sur les sphères en collision, où x est le coefficient de ressort et n est le coefficient d'amortissement. Lorsque deux sphères i et j sont présentes et que leur diamètre est d, une collision se produit lorsque la distance Irijl entre les deux sphères est plus petite que d, et que la force fs due à l'élasticité selon l'équation (11) et la force d'amortissement fd due à l'amortissement selon l'équation (12) agissent sur les sphères. fs = - x(d - Irijl)rij/Irijl (11) fd = - ri(vj - vi) (12) Selon les équations (11) et (12), rij = rj - ri et ri et rj sont les vecteurs de position des sphères i, j. La force de frottement ft dans le sens du cisaillement est calculée par l'équation (13) comme une force proportionnelle à la vitesse vt dans le sens du cisaillement. ft = xtvt (13) La force fi agissant sur la sphère i est calculée par l'équation (14). fi=fs+fd+ft (14) La force Fc et le couple Tc agissant sur le corps rigide dus à la collision sont respectivement calculés par les équations (15) et (16), en utilisant la force fi agissant sur la sphère i. Fc= >fi (15) iecorpsrigidc Tc= Er'ix fi (16) ie rorp..rigide Dans l'équation (16), r'i est le vecteur de position relative d'une sphère par rapport au centre de gravité d'un corps rigide. L'accélération du procédé de construction d'une structure de données ou l'utilisation dans la recherche de particule proche sur la base de l'utilisation seule du GPU 12 va ensuite être décrite. Selon le présent mode de réalisation, les calculs mentionnés ci-dessus concernant les collisions du grand nombre de corps rigides sont tous exécutés par le GPU 12. La vitesse des calculs mentionnés ci-dessus peut ainsi être accrue. L'algorithme de calcul basé sur le programme de recherche de particule proche 13A-1 dans le GPU 12 va être décrit. La structure de données préparée pour l'algorithme de calcul mentionné ci-dessus va d'abord être décrite. Lorsque les calculs décrits ci-dessus sont exécutés par le GPU 12, les quantités physiques mentionnées ci-dessus sont stockées et conservées sous la forme d'une pluralité de textures 13B-1 (représentées sur la figure 1) incluses dans la mémoire vidéo 13B. De façon spécifique, on utilise deux textures 13B-1 stockées dans la mémoire vidéo 13B pour chacun parmi les coordonnées du centre de gravité, le quaternion, l'importance du mouvement de translation, et l'importance du mouvement angulaire de chaque corps rigide pour exécuter le calcul de corps rigide. On utilise une texture unique 13B-1 stockée dans la mémoire vidéo 13B pour chacun parmi les coordonnées du centre, la vitesse, le compartiment, la force agissant sur chaque sphère et le couple agissant sur chaque sphère pour chaque sphère pour exécuter le calcul de collision. Dans le cas du présent mode de réalisation, on suppose un espace tridimensionnel et une grille d'espace tridimensionnel, c'est-à-dire un compartiment, dans lequel est divisé l'espace tridimensionnel comme décrit ci-dessus, est préparé dans le calcul de collision du grand nombre de corps rigides basé sur la simulation basée sur des particules. Toutefois, un GPU 12 pouvant actuellement être utilisé ne peut pas écrire une texture tridimensionnelle. En conséquence, dans le présent mode de réalisation, on exprime un compartiment tridimensionnel constitué d'un nombre de (L x L x L) grilles en utilisant une texture bidimensionnelle unique formée en superposant (D x D) du nombre nécessaire de grilles bidimensionnelles. Dans ce cas, lorsque les indices sur le compartiment tridimensionnel sont (i, j, k) et que les indices sur la texture bidimensionnelle sont (s, t), les relations indiquées par les équations (17) et (18) sont formées entre les deux types d'indices. s = i + L (k - D[k/D]) (17) t = j + Lf[k/D] (18) Dans les équations, i, j, k et s, t sont respectivement les valeurs incluses dans les plages [0, L-1] et [0, D x L-1]. L'algorithme de calcul de l'accélération utilisant le GPU 12 va ensuite être décrit en référence à l'organigramme de la figure 5. Lorsque l'unité de temps pour exécuter un cycle de calcul (simulation) pour dessiner sur l'écran d'affichage du dispositif d'affichage 15 est un intervalle unique, le calcul dans l'intervalle unique est exécuté dans les huit niveaux représentés ci-dessous. Niveau 1 : Calcul des quantités physiques des sphères (étape S11) Niveau 2 : Construction des compartiments (étape 512) Niveau 3 : Détection de collision (étape S13) Niveau 4 : Réponse de collision (calcul de la force et du couple agissant sur les sphères) (étape S14) Niveau 5 : Calcul de la quantité de mouvement de translation des corps rigides (étape S15) Niveau 6 : Calcul de la quantité de mouvement angulaire des corps rigides (étape S16) Niveau 7 : Calcul des coordonnées du centre de gravité des corps rigides (étape S17) Niveau 8 : Calcul du quaternion des corps rigides (étape 518) Le traitement de rendu pour l'affichage est exécuté en utilisant les coordonnées du centre de gravité et le quaternion du corps rigide qui sont finalement obtenus par les calculs mentionnés ci-dessus (simulation) et l'image résultante de la simulation est dessinée (étape 519). On détermine lors d'une étape de détermination qui suit S20 s'il faut continuer la simulation et lorsque le résultat est OUI, le processus retourne à l'étape S11 et les étapes S11 à S19 sont répétées. Lorsque le résultat est NON, la simulation se termine. Comme décrit ci-dessus, les huit niveaux des étapes de calcul S11 à S18 sont exécutés dans le temps d'un intervalle unique pour le traitement de rendu (étape S19) pendant un cycle d'affichage. Dans la description ci-dessus, le calcul de traitement de la recherche proche est effectué dans les calculs de la construction des compartiments exécutés à l'étape S12. Ce calcul est entièrement exécuté uniquement par le GPU 12, de sorte que le calcul peut être accéléré. Une description détaillée de la construction des compartiments est fournie ci-dessous. Les détails des calculs des étapes S11 à S19 sont décrits ci-10 dessous. Étape S11 : Calcul des quantités physiques d'une sphère Les coordonnées du centre de gravité et les vitesses des sphères constituant les corps rigides sont calculées de manière à effectuer un calcul de collision du grand nombre de corps rigides par le procédé de 15 particules. Les détails du calcul concernant la vitesse et les coordonnées du centre de gravité d'une sphère sont comme représenté dans les équations 19-21. Les coordonnées du centre de gravité, le quaternion, la vitesse et la vitesse angulaire du corps rigide j sont respectivement Xj, Qj, Vj et 20 Wj. Lorsque ri est le vecteur de position relative du centre de la sphère i par rapport au centre de gravité du corps rigide dans un état sans rotation, la position relative et le vecteur r'i dans un état de rotation par le quaternion Qj sont calculés par l'équation (19). 25 r'i = QjriQjT (19) Lorsque xi, vi sont les coordonnées du centre et la vitesse de la sphère i constituant le corps rigide j, xi et vi sont calculés par les équations (20) et (21). 30 Étape S12 : Construction du compartiment Le terme construction du compartiment se réfère au traitement pour stocker tous les numéros du grand nombre de sphères (particules) préparées pour exprimer chacun des nombreux corps rigides 35 dans des grilles d'espace tridimensionnel, c'est-à-dire des compartiments, xi = Xj + r'i (20) vi = Vj + Wj x r'i (21) préparés sous la forme d'éléments dans lesquels l'espace est divisé en tant que structure de données dans la mémoire vidéo 13B, comme décrit précédemment. De façon spécifique, la construction des compartiments est le traitement de stockage d'un numéro affecté à chacune des nombreuses sphères dans chacun des nombreux compartiments, et constitue le traitement pour disperser les données concernant chacune des nombreuses sphères. On utilise une fonction d'écriture (rendu pour le traitement) par un nuanceur de sommet (sommet) dans le traitement mentionné ci-dessus concernant la construction des compartiments. La fonction d'écriture est une fonction telle qu'un sommet peut être écrit dans des coordonnées désignées comme entrée. En d'autres termes, un nuanceur de sommet possède une fonction appelée récupération de texture de sommet (VTF) pour accéder à une texture de la mémoire vidéo 13B et on peut référencer les coordonnées d'une sphère en utilisant cette fonction du nuanceur de sommet, Le traitement de dispersion de données décrit ci-dessus peut être exécuté dans le GPU 12 en plaçant un sommet aux coordonnées du compartiment qui correspond aux coordonnées de la sphère. Lorsque le nombre de sphères est n (k, ii, ..., in-1), on prépare le même nombre n (po, pi, ..., pr-1) de sommets que le nombre de sphères. Une sphère unique est corrélée avec chaque sommet. Les numéros des sphères qui correspondent aux sommets po, pi, ,.., pn-1 sont io, ..., Les numéros des sphères sont agencés par exemple dans l'ordre (ordre ascendant) io Dans les nuanceurs de fragment (FS) 23, le numéro de la sphère est écrit en tant que couleur ou profondeur . Les détails de traitement de la construction des compartiments S12 vont être décrits de façon spécifique en référence à la figure 6. L'étape de construction des compartiments S12 est constituée des étapes 5101 à S104 de quatre passages qui sont effectués en séquence. La première écriture (étape S101) dans un simple pixel lors du premier passage est une étape d'écriture du numéro de la sphère ibo dans le canal R. Le numéro de la sphère ibo possède le plus petit numéro parmi les quatre sphères. De façon spécifique, ce numéro de sphère est écrit en tant que pixel ayant la plus petite profondeur et on exécute le rendu pour le premier traitement. Dans le cas de l'écriture de ce numéro de sphère ibo, on détermine d'abord un masque de couleur pour sélectionner le canal R (étape S31), on détermine un test de profondeur (étape S32), on initialise ensuite le tampon de profondeur à la valeur maximale (étape 533), on utilise le test de profondeur ainsi déterminé pour accepter les éléments ayant la plus petite valeur et on active l'écriture (rendu de sommet S34). L'écriture (étape S102) dans le même pixel lors du deuxième passage est une étape d'écriture du numéro de sphère ibi dans le canal G de sorte que la valeur écrite dans le canal R n'est pas écrasée. Lors de cette écriture, on interdit l'écriture dans les canaux RBA en utilisant un masque de couleur pour sélectionner le canal G (étape S41). On utilise le même tampon de profondeur que celui qui est utilisé lors du premier passage et le test de profondeur est déterminé de façon à accepter des éléments ayant une valeur élevée (étape S42). Toutefois, puisque le numéro de sphère le plus grand ib3 est ainsi écrit dans le canal G du pixel mentionné ci-dessus, on utilise un test pochoir pour empêcher cette écriture (étape S43). Lors du test pochoir, on initialise le tampon de pochoir à zéro (étape S44) et on effectue une détermination telle que la valeur est accrue par le test pochoir. Lorsque la valeur est de 1 ou plus dans le test pochoir, on effectue une détermination telle que l'écriture échoue (étape 543). On empêche ainsi un numéro de sphère pour lequel l'écriture a échoué d'être écrit dans le pixel après avoir effectué une fois le traitement d'écriture pour le pixel. On écrit ainsi le numéro de sphère ibl dans le canal G (étape S45) lors du deuxième passage d'écriture pour le même pixel. On effectue ensuite le même traitement que celui décrit ci-dessus dans le cas de l'écriture du numéro de pixel ibz dans le canal B du troisième passage (étape S103) et l'écriture du numéro de sphère ib3 du quatrième passage (étape 5104) dans le même pixel et on écrit respectivement le numéro de sphère ibz et le numéro de sphère ib3 dans le canal B et le canal A. L'étape S103 du troisième passage comporte les étapes S51 à S53, respectivement de détermination d'un masque de couleur pour sélectionner le canal B, effacement du tampon de pochoir et rendu de sommet (écriture). L'étape 5104 du quatrième passage comporte les étapes S61 à S63, respectivement de détermination d'un masque de couleur pour sélectionner le canal A, effacement du tampon de pochoir et rendu de sommet (écriture). Comme décrit ci-dessus lors de la construction de la structure de données utilisée dans la recherche de particule proche dans laquelle on utilise le GPU 12, c'est-à-dire dans la construction des compartiments, dans le cas ou une pluralité (par exemple quatre) de sphères sont présentes dans un compartiment, le stockage dans le compartiment (écriture des numéros de sphères dans les canaux RGBA du pixel) est divisé en rendu d'une pluralité d'instances de traitement (par exemple quatre) lorsque les numéros des sphères sont stockés dans un simple compartiment et corrélés avec un pixel. Lors du rendu pour une instance unique de traitement, le numéro d'une simple sphère est écrit dans un simple canal du pixel selon la règle mentionnée ci-dessus. On détermine la règle mentionnée ci-dessus concernant la sélection des canaux d'écriture et l'ordre d'écriture des numéros de sphère dans chaque rendu en utilisant le test de profondeur, le masque de couleur et le test pochoir, qui sont des fonctions du GPU 12. Étape S13 : Calcul de collision Dans ce calcul de collision, on effectue une recherche d'une sphère présente au voisinage lorsqu'il existe une possibilité de collision avec une certaine sphère i. Dans cette recherche, on désigne comme entrée une texture de compartiment générée en tant que texture de coordonnées de la sphère et on effectue un traitement en utilisant un nuanceur de fragment. À l'aide de ce traitement, un compartiment est référencé, tel que l'on obtient les numéros des sphères stockées dans les 33 compartiments entourant le compartiment dans lequel la certaine sphère est stockée et on utilise les numéros pour référencer la texture pour laquelle les coordonnées de la sphère sont stockées, de sorte à obtenir les coordonnées de la sphère (coordonnées du centre de la sphère). On calcule les distances entre les sphères et la sphère i en utilisant les coordonnées de sphère de chaque sphère et on exécute le calcul de collision. Étape S14 : Réponse de collision (calcul de la force et du couple agissant sur les sphères) Pour deux sphères qui sont déterminées comme en collision, on peut calculer d'après l'équation (12) les forces agissant sur les sphères et les couples exercés par les forces sur les corps rigides, en utilisant les coordonnées (vecteurs de position) des deux sphères, les vitesses (vecteurs de vitesse) des deux sphères et les vecteurs de position relative par rapport aux centres de gravité des corps rigides. Étapes S15, S16 : Calcul des quantités de mouvement de translation et de mouvement angulaire des corps rigides. Lors de l'étape S14, puisqu'on calcule les forces agissant sur les sphères et les couples exercés par les forces sur les corps rigides, on combine ces valeurs en utilisant les équations (15) et (16) mentionnées ci- dessus et on calcule les forces agissant sur les corps rigides. On met ensuite à jour les quantités de mouvement de translation et de mouvement angulaire des corps rigides en utilisant les équations (2) et (4) mentionnées ci-dessus. Étapes S17, S18 : Calcul des coordonnées du centre de gravité et des quaternions des corps rigides. On calcule les coordonnées du centre de gravité d'un corps rigide en utilisant l'équation (3) mentionnée ci-dessus. Dans le présent mode de réalisation, on effectue une sortie vers une autre texture de coordonnées de centre de gravité de corps rigide en utilisant comme entrée les coordonnées du centre de gravité et la texture de vitesse de centre de gravité du corps rigide. On calcule la mise à jour des quaternions des corps rigides en utilisant l'équation (10) mentionnée ci-dessus. Dans le présent mode de réalisation, la valeur à laquelle la texture de quaternion de l'autre corps rigide est mise à jour est, de plus, écrite en utilisant comme entrée les quaternions et les textures de vitesse angulaire des corps rigides. Étape S19 : Traitement de rendu (rendu pour l'affichage). On effectue le rendu pour dessiner l'affichage sur l'écran du dispositif d'affichage 15 en se basant sur le calcul présenté dans les équations 22 et 23 ci-dessous en utilisant les coordonnées du centre de gravité et les quaternions des corps rigides calculés comme décrit ci-dessus. Lorsqu'on fait initialement tourner le vecteur de position relative ri depuis le centre du corps rigide lorsque le sommet i ne tourne pas, de la valeur de rotation courante du corps rigide en utilisant le quaternion Q, et 10 qu'on le déplace ensuite des coordonnées du centre de gravité X du corps rigide, on calcule le vecteur de position relative courante r' du sommet i à l'aide de l'équation (22). r'i = X + QriQT (22) On utilise ensuite la matrice de projection de vue de modèle M 15 pour convertir les coordonnées r" dans le système de coordonnées en cours de rendu, en se basant sur l'équation (23). r" = Mr'i (23) Dans le calcul exécuté dans le GPU 12, on répète fondamentalement les huit étapes d'algorithmes décrites ci-dessus, de 20 sorte qu'on peut afficher sur l'écran d'affichage du dispositif d'affichage 15 une image en temps réel d'une simulation de collision des nombreux corps rigides. La figure 7 représente un exemple modifié de l'algorithme de calcul d'accélération de la simulation de corps rigides représentée sur la 25 figure 5. Dans le déroulement du traitement représenté sur la figure 7, on utilise les mêmes symboles de référence pour indiquer des étapes qui sont sensiblement les mêmes que les étapes représentées sur la figure 5. Selon l'algorithme de calcul représenté sur la figure 7, on peut adopter une configuration dans laquelle le calcul S15 de la quantité de mouvement de 30 translation des corps rigides, le calcul S16 des coordonnées du centre de gravité des corps rigides, le calcul S17 de la quantité de mouvement angulaire des corps rigides et le calcul S18 des quaternions des corps rigides sont exécutés simultanément par un traitement parallèle. On utilise ici un traitement parallèle dans le GPU 12. Le déroulement du reste du 35 traitement est le même que celui qui est représenté sur la figure 5. Au moyen de cette configuration, on peut encore réduire le temps d'un intervalle unique de l'algorithme de calcul de la simulation du corps rigide et on peut obtenir encore une accélération supplémentaire. Dans la simulation de corps rigides de chute/collisions de 10 922 tores représentée sur la figure 3, le temps nécessaire pour un intervalle unique était de 16,6 millisecondes et le rapport de trame durant le rendu était de 23 FPS. Dans la simulation de corps rigides de chute/collisions de 16 384 pièces d'échecs représentée sur la figure 4, le temps nécessaire pour un intervalle unique était de 12,8 millisecondes et le rapport de trame durant le rendu était de 21,2 FPS. On a utilisé la quantité physique à laquelle on fait référence par le terme quaternion pour indiquer l'orientation d'un corps rigide dans la description du mode de réalisation fournie ci-dessus, mais on peut également utiliser pour le calcul une matrice de rotation à la place d'un quaternion. Un quaternion et une matrice de rotation sont tous deux des quantités physiques qui indiquent l'orientation d'un objet . On a appliqué le procédé de construction d'une structure de données utilisé dans la recherche de particule proche d'une simulation basée sur des particules du mode de réalisation décrit précédemment à une simulation de corps rigides concernant des collisions d'un grand nombre de corps rigides, mais le procédé de construction d'une structure de données selon la présente invention n'est pas ainsi limité et on peut également l'appliquer pour exprimer le mouvement de fluide d'un corps fluide ou d'un corps particulaire ou d'un autre objet naturel, comme représenté sur les figures 8 et 9. La figure 8 est un schéma représentant une image d'effet d'une simulation montrant l'état de variation d'un corps fluide lorsqu'unepluralité de corps fluides sphériques (gouttes) tombent dans l'eau ou dans un autre corps fluide. La figure 9 est un schéma représentant une image d'effet d'une simulation montrant le changement d'état lorsqu'un corps particulaire contenu dans un récipient en forme d'entonnoir s'écoule vers le bas, tombe à l'extérieur par une ouverture à l'extrémité inférieure du récipient et est contenu dans un récipient positionné au-dessous de l'ouverture. Le procédé décrit précédemment de construction d'une structure de données utilisé dans une recherche de particule proche est mis en oeuvre par l'exécution du programme de recherche de particule proche 13A-1 représenté sur la figure 1 par le GPU 12. Le programme de recherche de particule proche 13A-1 concernant le procédé de construction d'une structure de données utilisée dans une recherche de particule proche est stocké tel quel sur un CD-ROM ou sur un autre support de stockage et il peut être configuré comme un programme autonome. Dans la description du mode de réalisation, un exemple a été décrit dans lequel on a utilisé un nuanceur (nuanceur) dans le montage du programme par le GPU. Ceci était un exemple de l'utilisation d'un modèle de programme spécialisé pour les fonctions graphiques d'un GPU. Toutefois, la présente invention n'est pas limitée à cette configuration. On peut utiliser le processeur en continu courant mentionné ci-dessus incluant un GPU en tant que processeur de calcul graphique et on peut effectuer un montage en utilisant un modèle de programmation courant en tant que modèle de programmation. On peut généralement monter le programme en utilisant CUDA, CTM, Brook ou un autre modèle de programmation outre le nuanceur mentionné ci-dessus dans le processeur en continu incluant le GPU 12. Lors du montage du nuanceur dans le GPU selon le mode de réalisation décrit précédemment, on a stocké en tant que textures 13B-1 dans la mémoire vidéo 13B des tranches, des voxels et des données concernant les particules dans l'espace de calcul. On utilise généralement des matrices à la place des textures lorsqu'on utilise CUDA ou analogue en tant que montage de programme. Comme décrit précédemment, lorsqu'on utilise un GPU en tant que processeur de calcul graphique dans le procédé de construction d'une structure de données, on effectue une sélection des coordonnées de particule et du numéro de particule de la particule écrite dans chaque rendu pendant la pluralité de cycles de traitement, et une sélection d'un canal dans le pixel écrit, en utilisant les fonctions d'un test pochoir, d'un masque de couleur et d'un test de profondeur, qui sont préparées par le processeur de calcul graphique. À titre de variante, lorsqu'on utilise un processeur en continu en tant que processeur de calcul graphique, on utilise un emplacement mémoire à la place du pixel mentionné ci-dessus (pixel écrit), on utilise un emplacement mémoire dans la mémoire pour un voxel à la place du canal mentionné ci-dessus et on utilise des fonctions de compteur préparées par le processeur en continu à la place des fonctions du test de profondeur, du masque de couleur et du test pochoir mentionnées ci-dessus, préparées par le GPU. On utilise la fonction de compteur à la place du test de profondeur, du masque de couleur et du test pochoir mentionnés ci-dessus. En conséquence, lorsqu'on utilise un processeur en continu en tant que processeur de calcul graphique, on effectue la sélection du numéro de particule et de l'emplacement mémoire des particules écrites lors des étapes d'une pluralité de cycles de traitement et la sélection de l'emplacement mémoire dans la mémoire pour le voxel, en utilisant les fonctions de compteur préparées par le processeur en continu. Comme décrit précédemment, le procédé de construction d'une structure de données, c'est-à-dire l'étape de construction de paquets S12 représentée sur la figure 6, comprend les étapes décrites ci-dessous lorsque le programme est monté en utilisant le GPU 12 en tant que processeur de calcul graphique. Le procédé comprend une étape (5101) d'écriture d'un numéro de particule Ibo dans le canal R et d'exécution d'un rendu par un premier sous-programme en initialisant un tampon de profondeur à une valeur maximale et d'acceptation des éléments ayant une faible valeur en utilisant un test de profondeur lors de l'écriture dans le pixel durant un premier passage ; une étape (5102) d'écriture d'un numéro de particule ib1 dans le canal G et d'exécution de rendu par un deuxième sous-programme en utilisant un masque de couleur pour interdire l'écriture dans le canal R et en utilisant un test pochoir ou analogue lors de l'écriture dans le pixel durant un deuxième passage ; une étape (S103) d'écriture d'un numéro de particule ib2 dans le canal B et d'exécution d'un rendu par un troisième sous-programme en utilisant un masque de couleur pour interdire l'écriture dans les canaux R et G et en utilisant un test pochoir lors de l'écriture dans le pixel durant un troisième passage ; et une étape (S104) d'écriture d'un numéro de particule ib3 dans le canal A et d'exécution d'un rendu par un quatrième sous-programme en utilisant un masque de couleur pour interdire l'écriture dans les canaux R, G et B et en utilisant un test pochoir lors de l'écriture dans le pixel durant un quatrième passage ; les numéros de particules des quatre particules étant ibo, iBl, ib2 et ib3 (ou Ibo De plus, outre le traitement pour écrire le numéro de particule dans la mémoire destination d'écriture des données en une étape , les compteurs sont également mis à jour. La mise à jour des compteurs se réfère à l'incrémentation des compteurs une seule fois. Comme décrit ci-dessus, lorsqu'on utilise un GPU ou un autre processeur en continu et que CUDA est monté en tant que modèle de programmation, on utilise des matrices créées dans la mémoire vidéo à la place des textures. Une texture est un concept inclus dans des matrices créées dans une mémoire vidéo . Les matrices créées dans une mémoire vidéo peuvent généralement être interprétées comme des matrices créées dans une mémoire dédiée . Dans un GPU ou un autre processeur en continu, lorsque le programme est monté en utilisant CUDA à la place des nuanceurs en tant que modèle de programmation, on utilise un emplacement mémoire à la place d'un pixel (pixel écrit), on utilise un emplacement mémoire dans la mémoire pour un voxel à la place d'un canal et on utilise des fonctions de compteur correspondantes à la place des fonctions du test de profondeur, du masque de couleur et du test pochoir. REVENDICATIONS 1. Procédé de construction d'une structure de données utilisée dans une recherche de particule proche utilisée par un procédé exécuté par un GPU (Unité de traitement graphique) pour calculer une simulation d'un objet physique en convertissant des données d'images numériques tridimensionnelles construites à partir de données d'images créées dans une mémoire vidéo en données d'images numériques bidimensionnelles, caractérisé en ce que on utilise une technique pour indiquer l'objet physique sous la forme d'un grand nombre de particules et pour déterminer l'état d'existence de l'objet physique en se basant sur une relation de position de stockage parmi le grand nombre de particules dans une structure de données d'images tridimensionnelles de la mémoire vidéo ; une texture de compartiment incluse dans la structure de données d'images tridimensionnelles est constituée d'un compartiment dans lequel est divisé un espace mémoire créé conformément à un espace dans lequel l'objet physique apparaît et un numéro de particule affecté au grand nombre de particules est stocké dans chacun des nombreux compartiments ; une étape d'écriture est prévue dans laquelle les coordonnées de particule et le numéro de particule de la particule stockée dans le compartiment sont lus et écrits dans des pixels d'un espace d'images bidimensionnel, le GPU utilisant un nuanceur de sommet du GPU ; et le numéro de particule et les coordonnées de particules de chaque particule de la pluralité de particules sont écrits dans un canal sélectionné d'un pixel sélectionné dans les pixels un par un lors d'un rendu d'une pluralité de cycles de traitement lors d'une étape unique d'une simulation lorsqu'une pluralité de particules sont présentes dans le compartiment durant l'étape d'écriture. 2. Procédé selon la revendication 1, caractérisé en ce que la sélection du pixel écrit et d'un numéro de particule de la particule écrite dans chaque rendu pendant la pluralité de cycles de traitement, et la sélection du canal dans le pixel écrit, sont effectuées en utilisant des fonctions d'un test pochoir, un masque de couleur et un test de profondeur qui sont préparés par le GPU. 3. Procédé selon la revendication 2, caractérisé en ce qu'on stocke en séquence un numéro de particule à partir des particules pour lesquelles les numéros de particules sont en ordre ascendant ou en ordre descendant, séparément pour chacun des quatre canaux ou analogue, constitués de RGBA d'un pixel pour lequel le numéro de particule est écrit lorsque quatre des particules sont présentes dans le compartiment. 4. Procédé selon la revendication 3, comprenant : l'écriture d'un numéro de particule ibo dans le canal R et l'exécution d'un rendu par un premier sous-programme en initialisant un tampon de profondeur à une valeur maximale et en acceptant des éléments ayant une faible valeur en utilisant un test de profondeur lors de l'écriture du pixel durant un premier passage ; l'écriture d'un numéro de particule ibi dans le canal G et l'exécution d'un rendu par un deuxième sous-programme en utilisant un masque de couleur pour interdire l'écriture dans le canal R et en utilisant un test pochoir lors de l'écriture dans le pixel durant un deuxième passage ; l'écriture d'un numéro de particule ib2 dans le canal B et l'exécution d'un rendu par un troisième sous-programme en utilisant un masque de couleur pour interdire l'écriture dans les canaux R et G, et en utilisant un test pochoir lors de l'écriture dans le pixel durant un troisième passage ; et l'écriture d'un numéro de particule ibi dans le canal A et l'exécution d'un rendu par un quatrième sous-programme en utilisant un masque de couleur pour interdire l'écriture dans les canaux R, G et B et en utilisant un test pochoir lors de l'écriture dans le pixel durant un quatrième passage ; les numéros de particules des quatre particules étant ibo, ibi, ib2 et ibi (où ibo ibi > ib2 > ib3 dans le cas de l'ordre descendant). 5. Procédé selon la revendication 1, caractérisé en ce que l'objet physique est constitué d'un grand nombre de corps rigides et on exécute le calcul d'une simulation basée sur le calcul de collision du grand nombre de corps rigides. 6. Programme de construction d'une structure de données utilisée dans une recherche de particule proche utilisée par un programmeexécuté par un GPU (Unité de traitement graphique) pour calculer une simulation d'un objet physique en convertissant des données d'images numériques tridimensionnelles construites à partir de données d'images créées dans une mémoire vidéo en données d'images numériques bidimensionnelles, caractérisé en ce que le programme fait exécuter par le GPU les sous-programmes comprenant : l'indication de l'objet physique sous la forme d'un grand nombre de particules et la détermination de l'état d'existence de l'objet physique en se basant sur une relation de position de stockage parmi le grand nombre de particules dans une structure de données d'images tridimensionnelles de la mémoire vidéo ; la constitution d'une texture de compartiment incluse dans la structure de données d'images tridimensionnelles par un compartiment dans lequel est divisé un espace mémoire créé conformément à un espace dans lequel l'objet physique apparaît et un numéro de particule affecté au grand nombre de particules stocké dans chacun des nombreux compartiments ; l'exécution d'un sous-programme d'écriture utilisant un nuanceur de sommet pour lire les coordonnées de particule et un numéro de particule de la particule stockée dans le compartiment et écrire les coordonnées de particule et le numéro de particule dans des pixels d'un espace d'images bidimensionnel ; et l'écriture du numéro de particule et des coordonnées de particules de chaque particule de la pluralité de particules dans un canal sélectionné d'un pixel sélectionné dans les pixels un par un lors d'un rendu d'une pluralité de cycles de traitement lors d'une étape unique d'une simulation lorsqu'une pluralité des particules sont présentes dans le compartiment durant l'étape d'écriture du sous-programme d'écriture. 7. Programme selon la revendication 6, caractérisé en ce que la sélection du pixel écrit et d'un numéro de particule de la particule écrite dans chaque rendu pendant la pluralité de cycles de traitement, et la sélection du canal dans le pixel écrit, sont effectuées en utilisant des fonctions d'un test pochoir, un masque de couleur et un test de profondeur qui sont préparés par le GPU. 8. Programme selon la revendication 7, caractérisé en ce qu'on fait exécuter par le GPU un sous-programme de stockage en séquenced'un numéro de particule à partir des particules pour lesquelles les numéros de particules sont en ordre ascendant ou en ordre descendant, séparément pour chacun des quatre canaux constitués de RGBA d'un pixel pour lequel le numéro de particule est écrit lorsque quatre des particules sont présentes dans le compartiment. 9. Programme selon la revendication 8, caractérisé en ce qu'on fait exécuter par le GPU des sous-programmes comprenant : l'écriture d'un numéro de particule bo dans le canal R et l'exécution d'un rendu par un premier sous-programme en initialisant un tampon de profondeur à une valeur maximale et en acceptant des éléments ayant une faible valeur en utilisant un test de profondeur lors de l'écriture du pixel durant un premier passage ; l'écriture d'un numéro de particule lb' dans le canal G et l'exécution d'un rendu par un deuxième sous-programme en utilisant un masque de couleur pour interdire l'écriture dans le canal R et en utilisant un test pochoir lors de l'écriture dans le pixel durant un deuxième passage ; l'écriture d'un numéro de particule b2 dans le canal B et l'exécution d'un rendu par un troisième sous-programme en utilisant un masque de couleur pour interdire l'écriture dans les canaux R et G, et en utilisant un test pochoir lors de l'écriture dans le pixel durant un troisième passage ; et l'écriture d'un numéro de particule b3 dans le canal A et l'exécution d'un rendu par un quatrième sous-programme en utilisant un masque de couleur pour interdire l'écriture dans les canaux R, G et B et en utilisant un test pochoir lors de l'écriture dans le pixel durant un troisième passage ; les numéros de particules des quatre particules étant ibo, ibi, ib2 et ib3 (où ibO ibl > ib2 > ib3 dans le cas de l'ordre descendant). 10. Programme de construction d'une structure de données utilisée dans une recherche de particule proche selon la revendication 6, caractérisé en ce que l'objet physique est constitué d'un grand nombre de corps rigides, et le calcul d'une simulation basée sur un calcul de collision 35 du grand nombre de corps rigides est exécuté par le GPU. 11. Support lisible par un ordinateur pour stocker le programme de construction d'une structure de données utilisée dans une recherche de particule proche selon l'une quelconque des revendications 6 à 10. 12. Procédé de construction d'une structure de données utilisée dans une recherche de particule proche utilisée par un procédé exécuté par un processeur en continu pour calculer une simulation d'un objet physique en convertissant des données d'images numériques tridimensionnelles construites à partir d'une matrice de données créée en mémoire en données d'images numériques bidimensionnelles, caractérisé en ce que on utilise une technique pour indiquer l'objet physique sous la forme d'un grand nombre de particules et pour déterminer l'état d'existence de l'objet physique en se basant sur une relation de position de stockage parmi le grand nombre de particules dans une structure de données d'images tridimensionnelles de la mémoire ; une matrice de compartiment incluse dans la structure de données d'images tridimensionnelles est constituée d'un compartiment dans lequel est divisé un espace mémoire créé conformément à un espace dans lequel l'objet physique apparaît et un numéro de particule affecté au grand nombre de particules est stocké dans chacun des nombreux compartiments ; une étape d'écriture est prévue dans laquelle les coordonnées de particule et le numéro de particule de la particule stockée dans le compartiment sont lus et écrits dans une matrice de la mémoire en utilisant une opération de dispersion du processeur en continu par le processeur en continu ; et le numéro de particule et les coordonnées de particules de chaque particule de la pluralité de particules sont écrits un par un dans un noyau pendant une pluralité de cycles de traitement lors d'une étape unique d'une simulation lorsqu'une pluralité des particules sont présentes dans le compartiment durant l'étape d'écriture. 13. Procédé selon la revendication 12, caractérisé en ce que la sélection de données écrites et d'un numéro de particule de la particule écrite dans chaque étape pendant la pluralité de cycles de traitement, et la sélection d'une pluralité d'emplacements mémoire dans la mémoireallouée pour un voxel sont effectuées en utilisant des fonctions de compteur préparées par le processeur en continu. 14. Procédé selon la revendication 13, caractérisé en ce qu'on stocke en séquence un numéro de particule à partir de particules pour lesquelles les numéros de particules sont en ordre ascendant ou en ordre descendant, séparément pour chacun du premier au quatrième emplacement mémoire pour lequel le numéro de particule est écrit lorsque quatre des particules sont présentes dans le compartiment. 15. Procédé selon la revendication 14, comprenant : l'écriture d'un numéro de particule ibo au premier emplacement mémoire et l'exécution d'un noyau par un premier sous-programme en initialisant le compteur à zéro et l'acceptation de l'écriture initiale au premier emplacement mémoire lors de l'écriture dans la mémoire allouée au voxel lors d'un premier passage ; l'écriture d'un numéro de particule ib1 au deuxième emplacement mémoire et l'exécution d'un noyau par un deuxième sous-programme en utilisant le compteur pour interdire l'écriture au premier emplacement mémoire et l'écriture d'une valeur suivante au deuxième emplacement mémoire lors de l'écriture dans la mémoire allouée au voxel lors d'un deuxième passage ; l'écriture d'un numéro de particule ib2 au troisième emplacement mémoire et l'exécution d'un noyau pour un troisième sous-programme en utilisant le compteur pour interdire l'écriture aux premier et deuxième emplacements mémoire et l'écriture d'une valeur suivante au troisième emplacement mémoire lors de l'écriture dans la mémoire allouée au voxel lors d'un troisième passage ; et l'écriture d'un numéro de particule ib3 au quatrième emplacement mémoire et l'exécution d'un noyau pour un quatrième sous-programme en utilisant le compteur pour interdire l'écriture aux premier, deuxième et troisième emplacement mémoire et l'écriture d'une valeur suivante au quatrième emplacement mémoire lors de l'écriture dans la mémoire allouée au voxel lors d'un quatrième passage ; les numéros de particules des quatre particules étant ibo, ibi, ib2 et ib3 (où Ibo ibl > ib2 > ib3 dans le cas de l'ordre descendant). 16. Procédé selon la revendication 12, caractérisé en ce que l'objet physique est constitué d'un grand nombre de corps rigides, et le calcul d'une simulation basée sur un calcul de collision du grand nombre de corps rigides est exécuté. 17. Programme de construction d'une structure de données utilisée dans une recherche de particule proche utilisée par un programme exécuté par un processeur en continu pour calculer une simulation d'un objet physique en convertissant des données d'images numériques tridimensionnelles construites à partir d'une matrice de données créée en mémoire en données d'images numériques bidimensionnelles, caractérisé en ce que le programme fait exécuter par le processeur en continu les sous-programmes comprenant : l'indication de l'objet physique sous la forme d'un grand nombre de particules et la détermination de l'état d'existence de l'objet physique en se basant sur une relation de position de stockage parmi le grand nombre de particules dans une structure de données d'images tridimensionnelles dans la mémoire ; la constitution d'une matrice de compartiments incluse dans la structure de données d'images tridimensionnelles d'un compartiment dans lequel est divisé un espace mémoire créé conformément à un espace dans lequel l'objet physique apparaît et un numéro de particule affecté au grand nombre de particules stocké dans chacun des nombreux compartiments ; l'exécution d'un sous-programme d'écriture utilisant une opération de dispersion du processeur en continu pour lire les coordonnées de particule et le numéro de particule de la particule stockée dans le compartiment et écrire les coordonnées de particule et le numéro de particule dans une matrice de la mémoire par le processeur en continu ; et l'écriture du numéro de particule et des coordonnées de particules de chaque particule de la pluralité de particules un par un dans un noyau pendant une pluralité de cycles de traitement lors d'une étape unique d'une simulation lorsqu'une pluralité des particules sont présentes dans le compartiment durant l'étape d'écriture du sous-programme d'écriture. 18. Programme selon la revendication 17, caractérisé en ce que la sélection de données écrites et d'un numéro de particule de la particule écrite à chaque étape pendant la pluralité de cycles de traitement, et la sélection d'une pluralité d'emplacements mémoire dans une mémoire allouée pour un voxel sont effectuées en utilisant des fonctions de compteur préparées par le processeur en continu. 19. Programme selon la revendication 18, caractérisé en ce qu'on stocke en séquence un numéro de particule à partir des particules pour lesquelles les numéros de particules sont en ordre ascendant ou en ordre descendant, séparément pour chacun du premier au quatrième emplacement mémoire pour lequel le numéro de particule est écrit lorsque quatre des particules sont présentes dans le compartiment. 20. Programme selon la revendication 19, caractérisé en ce que le programme fait exécuter par le processeur en continu les sous-15 programmes comprenant : l'écriture d'un numéro de particule ibo au premier emplacement mémoire et l'exécution d'un noyau par un premier sous-programme en initialisant le compteur à zéro et l'acceptation de l'écriture initiale dans la première mémoire lors de l'écriture au premier emplacement mémoire 20 dans la mémoire allouée au voxel lors d'un premier passage ; l'écriture d'un numéro de particule ibl au deuxième emplacement mémoire et l'exécution d'un noyau par un deuxième sous-programme en utilisant le compteur pour interdire l'écriture au premier emplacement mémoire et l'écriture d'une valeur suivante au deuxième 25 emplacement mémoire lors de l'écriture dans la mémoire allouée au voxel lors d'un deuxième passage ; l'écriture d'un numéro de particule ib2 au troisième emplacement mémoire et l'exécution d'un noyau pour un troisième sous-programme en utilisant le compteur pour interdire l'écriture aux premier et 30 deuxième emplacement mémoire et l'écriture d'une valeur suivante au troisième emplacement mémoire lors de l'écriture dans la mémoire allouée au voxel lors d'un troisième passage ; et l'écriture d'un numéro de particule ib3 au quatrième emplacement mémoire et l'exécution d'un noyau pour un quatrième sous- 35 programme en utilisant le compteur pour interdire l'écriture aux premier, deuxième et troisième emplacement mémoire et l'écriture d'une valeursuivante au quatrième emplacement mémoire lors de l'écriture dans la mémoire allouée au voxel lors d'un quatrième passage ; les numéros de particules des quatre particules étant ibo, ibi, ib2 et ibi (où ibo ibi > ib2 > ib3 dans le cas de l'ordre descendant). 21. Programme selon la revendication 20, caractérisé en ce que l'objet physique est constitué d'un grand nombre de corps rigides, et on exécute le calcul d'une simulation basée sur un calcul de collision d'un grand nombre de corps rigides. 22. Support de stockage lisible par un ordinateur pour stocker le programme pour construire une structure de données utilisée dans une recherche de particule proche selon l'une quelconque des revendications 17 à 21.