FR2920899A1 - Structure de donnees en tranches et procede de chargement d'une simulation basee sur des particules utilisant une structure de donnees en tranches dans un gpu, etc - Google Patents

Abstract

La structure de données en tranches utilisée pour une simulation basée sur des particules ou analogue utilisant un GPU (12) ou un processeur en continu est une structure de données pour un espace de calcul. L'espace est un espace de calcul tridimensionnel construit à partir d'un grand nombre de voxels ; une pluralité de tranches perpendiculaires à l'axe Y sont formées ; un grand nombre de voxels sont divisés par une pluralité de tranches bidimensionnelles ; les coordonnées de début respectives des voxels maximum et minimum sont calculées pour une plage de voxels dans laquelle des particules sont présentes dans chaque tranche d'une pluralité de tranches bidimensionnelles ; la plage de voxels est déterminée comme une boîte de délimitation entourée par une forme rectangulaire ; et une mémoire (13B) est prévue pour les voxels contenus dans les boîtes de délimitation de chaque tranche de la pluralité de tranches bidimensionnelles.

Description

STRUCTURE DE DONNÉES EN TRANCHES ET PROCÉDÉ DE CHARGEMENT D'UNE SIMULATION BASÉE SUR DES PARTICULES UTILISANT UNE STRUCTURE DE DONNÉES EN TRANCHES DANS UN GPU, ETC.

ARRIÈRE-PLAN DE L'INVENTION 1. Domaine de l'invention La présente invention concerne une structure de données en tranches et son application à une simulation basée sur des particules, basée sur un procédé de calcul de fluide utilisant par exemple des particules, améliorant le rendement de la mémoire pour un procédé utilisant une grille de calcul utilisée dans une recherche de proximité, et améliorant le rendement d'une recherche de particule proche et un procédé de chargement d'une simulation basée sur des particules utilisant une structure de données en tranches dans un GPU, etc. 2. Description de la technique associée Le terme simulation basée sur des particules se réfère à un procédé de simulation pour effectuer des calculs dans lesquels l'objet physique constituant l'objet de simulation est considéré comme une collection (agrégation) d'un grand nombre de particules et des calculs sont effectués en notant le comportement individuel du grand nombre de particules. Dans les calculs effectués par un ordinateur, on utilise habituellement pour les particules mentionnées ci-dessus, des sphères ayant un diamètre fixe. Dans le cas où on exprime la forme de l'objet physique par une agrégation de sphères, le degré d'approximation ou degré de résolution spatiale de l'objet physique varie selon le procédé utilisé pour déterminer la taille (diamètre) de ces sphères. De plus, en faisant varier le diamètre des sphères ou en faisant varier le degré de résolution spatiale, on peut contrôler le degré de précision du calcul et la vitesse de calcul dans les calculs de simulation effectués par un ordinateur. Au cours de ces dernières années, on a effectué le calcul du comportement de fluides et analogue en utilisant la simulation basée sur des particules mentionnée ci-dessus et on a effectué des recherches sur les simulations de fluides et analogue sur les écrans de dispositifs d'affichage d'ordinateur. Les documents dans lesquels cette recherche est décrite comportent : Development of a rigid body calculation method

using a particie method, and application to computer graphics de Masayuki Tanaka et al., Japan Society of Mechanical Engineers , collection d'articles présentés à la 19th Computational Mechanics Conference , pp. 701-702, 2006. La recherche sur les techniques de simulation basées sur des particules est importante en tant que technologie fondamentale de l'infographie (CG). Les procédés de simulation de fluide utilisant le procédé de particules comportent les procédés MPS (méthode serai-implicite de particule mobile) et SPH (hydrodynamique de particules lissée). Dans le procédé MPS, on calcule un écoulement non compressé en résolvant des équations de Poisson dérivées d'équations simultanées ; dans SPH, on calcule un écoulement quasi-non compressé sans établir de conditions non compressées. En conséquence, le procédé MPS présente des coûts de calcul supérieurs à SPH. En conséquence, les procédés SPH constituent le courant majoritaire dans le domaine de l'infographie. Dans la recherche sur la simulation basée sur des particules, on a principalement utilisé largement dans le passé un procédé dans lequel on a préparé un algorithme de calcul en utilisant un CPU. Toutefois, au cours de ces dernières années, une recherche est également en cours concernant des simulations basées sur des particules utilisant un GPU (unité de traitement graphique : généralement un processeur en continu). Un GPU a une construction dans laquelle le traitement de calcul est effectué en parallèle de manière interne par une pluralité de processeurs pour réaliser une adaptation spéciale pour le traitement graphique. En conséquence, dans le cas du traitement de la conversion de coordonnées de sommets et analogue, un GPU peut effectuer un traitement à une vitesse beaucoup plus rapide qu'un CPU. De plus, un GPU peut commander le traitement en écrivant un programme appelé nuanceur ; en conséquence, on peut également utiliser un GPU dans divers types de traitements autres que graphiques. En conséquence, on a également tenté d'accroître la vitesse des calculs utilisés dans des simulations basées sur des particules utilisant un GPU. Les inventeurs ont par exemple mis au point un procédé dans lequel on utilise un GPU pour exécuter toutes les simulations de SPH. Des documents décrivant ce procédé comportent Real-time Fluid Simulation Coupled with Cloth de T. Harada, S. Koshizuka et Y. Kawaguchi, dans Proc. Of Theory and Practice of

Computer Graphics, 2007 et Smoothed Particle Hydrodynamics on GPUs de T. Harada, S. Koshizuka et Y. Kawaguchi dans Proc. Of Computer Graphics International , pages 63 à 70, 2007. Dans le procédé mentionné ci-dessus proposé par le présent inventeur, on a utilisé une grille fixe dans l'espace pour rechercher des particules proches dans des simulations basées sur des particules ; on a rencontré en conséquence les problèmes suivants : à savoir, le rendement de la mémoire était médiocre et des limitations étaient générées concernant le domaine de calcul.

Par exemple, dans les procédés de calcul de fluide utilisant des particules, à la différence des procédés de calcul de fluide utilisant une grille, on n'utilise généralement pas de grille de calcul ; en conséquence, on obtient les avantages suivants : à savoir, qu'on peut facilement calculer des petites gouttelettes et analogue et qu'on peut exprimer le comportement réel du fluide. D'autre part, dans les procédés de calcul de fluides utilisant des grilles, on modifie la disposition des particules de façon dynamique sans aucune relation entre les particules calculées ; en conséquence, un traitement qui recherche des particules présentes au voisinage de certaines coordonnées est nécessaire dans des intervalles de temps respectifs pour calculer les quantités physiques à ces coordonnées. Pour effectuer une recherche de particule proche d'une manière efficace, on peut obtenir une amélioration de l'efficacité en disposant une grille dans le domaine de calcul (grille de calcul) et en enregistrant les numéros de certaines particules dans des voxels (appelés également compartiments ou grilles) contenant ces particules. Les grilles de calcul sont généralement préparées de sorte que le domaine de calcul est enveloppé. Lorsque une grille de calcul est fixe et préparée durant l'opération ci-dessus, il existe généralement un grand nombre de voxels dans lesquels les particules ne sont pas présentes dans le cas où la répartition des particules varie dans le domaine de calcul d'un fluide et le rendement d'utilisation de la mémoire est médiocre. Il existe des limites à la taille des mémoires dans lesquelles on peut utiliser des programmes de simulation ; en conséquence, à mesure que la taille de la mémoire utilisée dans la grille de calcul est réduite, la mémoire pouvant être utilisée pour des particules exprimant le fluide augmente et on peut effectuer une simulation de fluides à plus grande échelle. En raison des problèmes mentionnés ci-dessus, il existe une demande pour augmenter le rendement de mémoire de la grille de calcul utilisée dans la recherche de particules proches dans des simulations basées sur des particules. RÉSUMÉ DE L'INVENTION À la lumière des problèmes ci-dessus, un objectif de la présente invention est de fournir une structure de données en tranches pour un procédé de calcul de fluide utilisant des particules, améliorant le rendement d'utilisation de la mémoire pour un procédé utilisant une grille de calcul utilisée dans une recherche de particule proche et pouvant améliorer le rendement d'une recherche de particule proche. Un autre objectif de la présente invention est de fournir un procédé pour charger dans un GPU, etc., une simulation basée sur des particules utilisant une structure de données en tranches permettant le chargement aisé dans un GPU, etc., de la structure de données en tranches, pouvant améliorer le rendement d'utilisation de la mémoire. Pour atteindre les objectifs décrit ci-dessus, la structure de données en tranches fournie par la présente invention est construite comme suit : La structure de données en tranches pour une simulation basée sur des particules est une structure de données pour un espace utilisé dans le calcul d'une simulation basée sur des particules utilisant un CPU, un processeur en continu et un GPU ou analogue. L'espace est un espace de calcul tridimensionnel construit à partir d'un grand nombre de voxels. Le grand nombre de voxels (une grille) sont divisés en une pluralité de domaines en tranches bidimensionnels et en formant une pluralité de domaines en tranches bidimensionnels (tranches) perpendiculaires à un axe arbitraire unique dans un espace de calcul tridimensionnel. Dans la pluralité de domaines en tranches bidimensionnels, on calcule les coordonnées de début des voxels maximum et minimum pour des plages de voxels dans lesquelles les particules sont présentes, de façon à déterminer des plages rectangulaires (boîtes de délimitation) destinées à enfermer les domaines dans lesquels des particules sont présentes en utilisant une forme rectangulaire. Une mémoire est prévue pour les voxels

contenus dans les plages rectangulaires de chaque domaine de la pluralité de domaines en tranches bidimensionnels. Dans la structure de données en tranches, on enregistre les valeurs qui spécifient les particules (par exemple, les numéros de particules ou analogue) dans des éléments d'enregistrement de la mémoire prévue pour les voxels dans lesquels les particules sont présentes dans la construction décrite ci-dessus. Dans la structure de données en tranches, le calcul des numéros de voxels v(x, y, z) des voxels dans lesquelles certains points (x, y, z) dans les plages rectangulaires de chaque domaine de la pluralité de domaines en tranches bidimensionnels sont présents dans la configuration ci-dessus, est effectué en utilisant une valeur qui définit les plages rectangulaires de chacune des domaines en tranches bidimensionnels, une valeur qui détermine les numéros des tranches ou un numéro d'en-tête. Dans la structure de données en tranches pour une simulation basée sur des particules, par exemple prévue par la présente invention, le calcul de la simulation basée sur des particules est un calcul d'une recherche de particule proche et l'espace de calcul tridimensionnel est divisé par les domaines en tranches bidimensionnels pour rendre plus efficace le calcul de la recherche de particule proche dans la construction décrite ci-dessus. Dans la construction de données en tranches pour une simulation basée sur des particules on utilise par exemple un GPU ou un processeur en continu pour effectuer le calcul dans lequel l'espace de calcul tridimensionnel est divisé par les domaines en tranches bidimensionnels pour le calcul de la simulation basée sur des particules, dans la construction décrite ci-dessus. Le procédé de chargement d'une simulation basée sur des particules utilisant une structure de données en tranches dans un GPU ou un processeur en continu est un procédé pour construire une structure de données utilisée pour accroître le rendement de calcul d'une recherche de particule proche dans la simulation basée sur des particules, enregistrer des données, qui sont nécessaires pour effectuer une recherche de particule proche sur un GPU utilisant cette structure de données, dans une mémoire vidéo en tant que matrice, et charger la matrice dans le GPU. Ce procédé comprend les étapes consistant à former une pluralité de domaines en tranches bidimensionnels perpendiculaires à un axe arbitraire unique dans un espace de calcul tridimensionnel construit en utilisant un grand nombre de voxels, et diviser le grand nombre de voxels par la pluralité de domaines en tranches bidimensionnels ; calculer les coordonnées de début respectives des voxels maximum et minimum sur une plage de voxels dans laquelle des particules sont présentes dans chaque domaine de la pluralité de domaines en tranches bidimensionnels, et déterminer ainsi une plage rectangulaire destinée à enfermer la plage de voxels en utilisant une forme rectangulaire ; préparer au moins une matrice bidimensionnelle ; enregistrer dans les éléments (GPU canaux RGBA) de la matrice, quatre valeurs qui sont nécessaires au minimum pour définir chaque domaine de la pluralité de domaines en tranches bidimensionnels ; préparer une autre matrice d'au moins une dimension ; et enregistrer un numéro de particule des particules dans cette autre matrice. Dans ce procédé de chargement dans un GPU ou analogue, on utilise une texture comme matrice lorsqu'on utilise un nuanceur dans le chargement du programme dans le GPU.

Dans le procédé de chargement décrit ci-dessus, les quatre valeurs minimales sont le numéro p; du voxel de tête dans un domaine en tranches bidimensionnel arbitraire (i), les coordonnées de début bx;,m;n et bzi, min du voxel minimum et le nombre de voxels nx, dans une direction axiale spécifiée.

Dans la présente invention, on n'utilise pas de grille fixe ; en remplacement, on divise l'espace de calcul tridimensionnel en domaines en tranches bidimensionnels perpendiculaires à une direction axiale unique et les voxels enregistrés dans la mémoire sont limités en utilisant l'approche de plages rectangulaires spécifiées, c'est-à-dire des boites de délimitation. En conséquence, on peut utiliser une mémoire vidéo telle qu'un GPU ou analogue avec un bon rendement, on peut améliorer le rendement de la mémoire de voxels (grille) utilisée dans la recherche de particule proche d'une simulation de particule en utilisant un GPU ou analogue et on peut rendre plus efficace la recherche de particule proche.

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 détaillée qui suit des modes de réalisation préférés de la présente invention, effectuée en référence aux dessins annexés, dans lesquels : la figure 1 est un schéma de construction de système représentant la construction de base d'un système informatique dans lequel la simulation basée sur des particules de la présente invention est exécutée; la figure 2 est un schéma par blocs représentant la construction 10 de base de l'unité interne d'un GPU monté dans le système informatique ; la figure 3 est une vue en perspective représentant l'espace de calcul tridimensionnel ; la figure 4 est un schéma explicatif montrant une comparaison entre une grille fixe classique (A) et le procédé (B) utilisé pour déterminer 15 la grille (voxels) utilisée dans le présent mode de réalisation ; la figure 5 est un organigramme montrant la procédure utilisée pour charger dans un GPU le procédé de calcul selon la structure de données en tranches ; la figure 6 est un organigramme montrant une procédure plus 20 concrète pour l'étape d'élaboration de la structure de données ; la figure 7 est un organigramme montrant une procédure plus concrète pour l'étape de détermination de la boîte de délimitation ; la figure 8 est un schéma montrant l'approche du calcul de numéro d'en- tête de la tranche ; et 25 la figure 9 est un organigramme montrant une procédure plus concrète pour l'étape de lecture des valeurs. DESCRIPTION DES MODES DE RÉALISATION PRÉFÉRÉS Des modes de réalisation appropriés de la présente invention vont être décrits ci-dessous en référence aux dessins annexés. 30 La figure 1 montre la construction d'un système informatique utilisé dans une structure de données en tranches dans le calcul d'une recherche de particule proche dans une simulation basée sur des particules utilisant un GPU, dans lequel on exécute un procédé de simulation construit en utilisant cette structure de données en tranches. 35 Le système informatique 10 est construit par exemple en utilisant un PC (ordinateur personnel) et il comprend un CPU 11 pour

exécuter le traitement de calcul d'un ordinateur classique comme unité de traitement de calcul, et un GPU 12 pour exécuter un traitement de calcul spécifiquement adapté au traitement d'image. De plus, le système informatique 10 comprend une mémoire principale 13A et une mémoire vidéo (VRAM) 13B, en tant que dispositifs mémoire, et il comprend au moins un dispositif d'entrée 14 et 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 les uns aux autres 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. De plus, la mémoire vidéo 13B est directement connectée au GPU 12. L'échange de données avec la mémoire vidéo 13B s'effectue par l'intermédiaire du GPU 12.

De plus, dans le présent mode de réalisation, le procédé de programmation utilisé par le GPU 12 a une construction utilisant un nuanceur. Le CPU (unité de traitement de calcul central) Il est par exemple une unité de traitement de calcul classique montée dans un PC ou analogue. De plus, le GPU 12 est une unité de traitement graphique et il effectue un traitement de calcul d'image. On utilise par exemple comme CPU un Core X6800 . Le GPU 12 contient une pluralité de processeurs et il est utilisé dans un calculateur parallèle. On utilise par exemple comme GPU 12 un GeForce 8800GTX fabriqué par NVIDIA Co. De plus, le produit utilisé en tant que GPU 12 n'y est pas limité ; on peut également utiliser un autre processeur en continu ayant une structure et un fonctionnement similaires. Ce GPU 12 exécute un programme de recherche de particule proche 13A-1 enregistré dans la mémoire principale 13A et il effectue des calculs de recherche de particule proche dans la simulation basée sur des particules. Le programme de recherche de particule proche 13A-1 construit une structure de données utilisée dans la recherche de particule proche. Le procédé utilisé pour construire la structure de données ayant la structure caractéristique de la présente invention va être décrit en détail ultérieurement.

De plus, le GPU 12 exécute un programme de traitement d'image classique 13A-2 enregistré dans la mémoire principale 13A, il effectue un traitement d'image en utilisant des données d'image obtenues par le calcul de la recherche de particule proche et enregistrées dans la texture et il effectue un dessin (rendu pour affichage) sur l'écran du dispositif d'affichage 15 en utilisant les données d'image préparées. Une image CG est affichée sur l'écran du dispositif d'affichage 15 en se basant sur le calcul de la simulation basée sur des particules. Dans la description qui suit du présent mode de réalisation, on décrit par exemple un exemple du calcul d'une simulation de fluide basée sur une simulation basée sur des particules. Dans le calcul de cette simulation de fluide, on exécute un procédé utilisé pour construire une structure de données utilisée dans la recherche de particule proche en utilisant principalement la structure et les fonctions internes caractéristiques du GPU 12. Comme indiqué ultérieurement, la structure de données décrite dans le présent mode de réalisation est appelée structure de données en tranches (ou structure de données basée sur des tranches) . De plus, celui-ci peut également être exécuté en utilisant un CPU.

La structure de base des unités essentielles à l'intérieur du GPU 12 va ensuite être décrite en référence à la figure 2. La figure 2 est un schéma par blocs qui représente sous forme schématique la structure interne du GPU 12 . Le GPU 12 comprend une pluralité de processeurs 21 disposés en parallèle ; le rendu pour l'affichage (dessin des images) est effectué en se basant sur un traitement de calcul parallèle par ces processeurs. En particulier, dans le procédé utilisé pour la construction de la structure de données (construction de voxels (ou compartiments)) utilisée dans la recherche de particule proche du présent mode de réalisation, dans le cas où quatre particules sont présentes dans un voxel, les numéros de particule des quatre particules sont respectivement écrits dans les canaux RGBA du voxel unique. On obtient une augmentation de la vitesse du traitement de calcul d'images par le traitement de la construction de ces voxels dans le GPU 12. Par exemple, le GPU 12 possède habituellement huit nuanceurs de sommet (VS) 22, disposés en parallèle dans l'étage avant et 24 nuanceur de fragment (FS) 23, disposés en parallèle dans l'étage arrière.

Les programmes exécutés par chaque processeur de la pluralité de processeurs de sommet (21A) sont les nuanceurs de sommet 22 et les programmes exécutés par chacun des processeurs de fragment (21B) sont les nuanceurs de fragment 23.

Dans ce qui précède, les processeurs de sommet sont des processeurs qui sont disposés en parallèle et qui sont particulièrement adaptés au traitement du grand nombre de conversions de coordonnées de sommet (conversion des coordonnées de sommet d'entrée en coordonnées dans l'espace de l'image rendue) en même temps. Le GPU 12 peut calculer la conversion de coordonnées de sommet à une vitesse supérieure à celle du CPU. Le dispositif désignant le fonctionnement des processeurs de sommet est un nuanceur de sommet. De plus, le GPU 12 comprend une unité de fonction de test de profondeur 24, une unité de fonction de masque de couleur 25 et une unité de fonction de test pochoir 26. De plus, le bloc 27 est une unité de répartition de commande de nuanceur. Le concept de base de la structure de données en tranches en tant que structure de données du présent mode de réalisation utilisé dans une simulation basée sur des particules utilisant les GPU 12 va être décrit. Dans le calcul de fluide basé sur le procédé de particule, on détermine un espace (ou domaine) utilisé dans le calcul de la recherche de particule proche exécuté à des étapes temporelles respectives. Cet espace est appelé espace de calcul . Comme représenté sur la figure 3, cet espace de calcul est un espace tridimensionnel 31 qui est défini par trois axes, à savoir, l'axe X, l'axe Y et l'axe Z, qui sont perpendiculaires entre eux. Un grand nombre de grilles 32 sont préparées dans l'espace de calcul 31. Le grand nombre de grilles 32 est constitué de petits corps cubiques qui constituent l'espace de calcul 31 et qui sont d sur une face. Dans la description du présent mode de réalisation, ces grilles 32 sont appelées voxels . Ces voxels peuvent également être appelés compartiments ou grilles . Le grand nombre de grilles, c'est-à-dire les voxels 32, ont une étendue infinie et la disposition des grilles dans l'espace de calcul 31 n'est pas modifiée durant les calculs. Dans le procédé de calcul du présent mode de réalisation, seuls les voxels nécessaires parmi le grand nombre de voxels 32 constituant l'espace de calcul 31 sont contenus dans la mémoire vidéo 13B, comme il va être décrit ultérieurement. De plus, dans le cas où on utilise une grille fixe comme dans les procédés de calcul classiques, on fixe une boîte de délimitation en tant que domaine de calcul dans l'espace de calcul, et une mémoire est prévue pour les voxels à l'intérieur de cette boîte de délimitation, indépendamment de la présence ou de l'absence de particules. En d'autres termes, une mémoire est prévue même pour les voxels dans lesquels aucune particule n'est présente. D'autre part, dans le procédé de calcul du présent mode de réalisation, une mémoire est prévue en règle générale pour les voxels dans lesquels des particules sont présentes. Dans le procédé de calcul de la présente invention, une pluralité de tranches 31a perpendiculaires à un axe unique sont d'abord formées dans l'espace de calcul 31, et le grand nombre de voxels 32 préparés dans l'espace de calcul 31 est divisé de sorte à être contenu dans chaque tranche de la pluralité de tranches 31a. Les tranches respectives 31a sont bidimensionnelles, ce qui est une dimension de moins que les dimensions de l'espace de calcul 31 (trois dimensions). La dimension correspondant à l'épaisseur des tranches respectives 31a est sensiblement égale à une face (d) des voxels 32. En d'autres termes, dans la direction de l'axe unique auquel les tranches 31a sont perpendiculaires, seul un simple voxel est présent. Par exemple, on peut choisir comme axe unique un axe arbitraire unique tel que l'axe X, l'axe Y, l'axe Z ou analogue. Lorsque par exemple on choisit l'axe Y comme axe unique , les tranches 31a sont des espaces bidimensionnels s'étendant dans la direction du plan XZ déterminé par les axes X et Z. Un exemple va être décrit ci-dessous dans lequel l'espace de calcul tridimensionnel 31 est divisé en tranches bidimensionnelles 31a perpendiculaires à l'axe Y. Après avoir divisé l'espace de calcul 31 en une pluralité de tranches 31a, des boîtes de délimitation pour les directions axiales X et Z sont définies par les tranches respectives 31a. Ces boîtes de délimitation se réfèrent à des plages éliminées par des limites pour confirmer aussi étroitement que possible l'utilisation de domaines rectangulaires des domaines dans lesquels les particules sont présentes dans une tranche unique 31a. La définition des boîtes de délimitation dans une telle tranche 31a se réfère au calcul des coordonnées de début de voxels maximum et minimum bxi,max, bxi,min, bZi,max, bzi,min, dans les directions axiales X et Z. Ici, i se réfère à un nombre définissant la tranche. Ici, en calculant les coordonnées de début de voxels maximum et minimum bx,,max, bxi,min, bzl,max, bZi,min, dans les directions X et Z, il est possible de déterminer le nombre de voxels contenus dans la boîte de délimitation de la tranche unique 31a, c'est-à-dire les nombres de voxels nx; et nzi dans les directions X et Z contenus dans la tranche 31a, en utilisant les équations (1) et (2) de la formule 1. (Formule 1) Yrx; = bx; max ù 6x; ,n +1 (1) et Y2Z = bzi,nax uzi,min +1 (2) d G En utilisant nxi et nz;, il est possible de déterminer le nombre de voxels ni dans la tranche 31a ayant un numéro i par ni = nxi x nz;. Dans le procédé de calcul du présent mode de réalisation, de la mémoire est prévue pour les voxels du seul domaine situé à l'intérieur de la boîte de délimitation dans chaque tranche. L'espace de calcul 31 est ici divisé en n tranches [Sa, S1, S2, ..., Sn_1]. On calcule le numéro pi du voxel de tête dans la tranche initiale S; en utilisant l'équation (3) de la formule 2 suivante en tant que somme des numéros de voxels dans les tranches So à (Formule 2) >n1 (3) foi La figure 4 montre un exemple (A) de la boite de délimitation utilisée dans le cas où on utilise une structure de grille fixe selon un procédé de calcul classique, et un exemple (B) de la boîte de délimitation utilisée pour déterminer les voxels dans le procédé de calcul du présent mode de réalisation. Sur les figures 4(A) et 4(B), l'axe X, l'axe Y et l'axe Z sont définis comme représenté sur les dessins. Les figures 4(A) et 4(B) représentent ceci sous la forme d'une surface carrée unique (plan )(Y) dans une direction axiale unique XY perpendiculaire à la direction axiale Z. Sur les figures 4(A) et 4(B), les petites formes carrées 41a dans les plages déterminées par les formes carrées 41 indiquent des voxels uniques et les cercles 42 indiquent en outre des particules qui sont présentes à l'intérieur des voxels. En conséquence, les voxels dans lesquels sont présentes des particules 42 et les voxels dans lesquels aucune particule 42 n'est présente sont contenus dans les plages des formes carrées 41. Les unités sous forme de couche indiquées par le numéro 43 qui sont perpendiculaires à la direction axiale Y sur les figures 4(A) et 4(B) correspondent aux tranches 31a mentionnées ci-dessus. Les numéros 41a, 42 et 43 sur la figure 4 n'indiquent pas chaque unité ; les numéros ne sont pas attachés à d'autres unités du même type.

Dans un procédé de calcul classique, puisqu'on utilise une structure de grille fixe, le système est construit de sorte qu'une mémoire est prévue pour tous les voxels contenus dans les domaines carrés 41 (indiqués par des lignes épaisses pleines) indépendamment de la présence ou de l'absence de particules, comme représenté sur la figure 4(A). De façon spécifique, il est nécessaire de prévoir de la mémoire même pour le grand nombre de voxels dans lesquels aucune particule 42 n'est présente. D'autre part, dans le procédé de calcul du présent mode de réalisation, le système est construit de sorte qu'une mémoire est prévue pour les voxels contenus dans les domaines 44 (indiqués par des lignes épaisses pleines) préparés par la synthèse des boites de délimitation définies par les tranches respectives, à savoir, les domaines 44 qui sont construits étroitement de façon à inclure dans la mesure du possible les seuls voxels dans lesquels sont présentes des particules 42. La formation de boîtes de délimitation comme décrit ci-dessus, en utilisant les tranches avec les espaces de calcul 31, permet de calculer comme suit les numéros des voxels dans lesquels certains points (x, y, z) sont présents. En utilisant d'abord les coordonnées de début bymin du voxel minimum dans la direction axiale Y, on calcule le numéro i de la tranche dans laquelle est contenu ce point en utilisant l'équation (4) de la formule 3 qui suit. (Formule 3) r=[yùdy~l (4)

On calcule ensuite le numéro de voxel v(x, y, z) du point (x, y, z) en utilisant l'équation (5) de la formule 4 qui suit. 14 (Formule 4) - 'I z -d + (5) ç- v(x, y, z) = p, + On calcule de cette manière les numéros des voxels dans lesquels est présent le point mentionné ci-dessus (x, y, z). En se référant à l'équation (5) on voit que les valeurs qui sont nécessaires pour calculer les numéros des voxels dans lesquels certains points sont présents sont les valeurs bxi,min, bzi,min et nxi qui définissent les boîtes de délimitation des tranches respectives, la valeur bymin qui détermine le numéro de tranche, les numéros de tête pi des tranches respectives et la longueur d sur une face de chaque voxel. Lorsqu'on utilise la structure de données utilisant des tranches, on peut construire des voxels (grilles) en utilisant la mémoire avec un bon rendement, comme représenté sur la figure 4 (B). On calcule ainsi une structure de données en tranches qui est la structure de données caractéristique du procédé de calcul du présent mode de réalisation. Pour construire réellement la structure de données en tranches mentionnée ci-dessus, on détermine les boîtes de délimitation de chacune des n tranches [So, S1i S2, ..., Sn-1], et on calcule les numéros de tête des tranches respectives d'après les boîtes de délimitation déterminées. De plus, après avoir déterminé les quatre valeurs (pi, bxi,min, bZi,min, nxi) nécessaires pour le calcul des numéros de voxels v(x, y, z), on écrit ces valeurs dans les voxels. Ces quatre valeurs sont les valeurs minimales nécessaires pour la définition des boîtes de délimitation ; ces valeurs ne sont pas limitées à ces seules valeurs. Un système chargé dans le GPU 12 pour pouvoir exécuter le procédé de calcul basé sur la structure de données en tranches mentionnée ci-dessus en utilisant le GPU 12 va ensuite être décrit. Le chargement du procédé de calcul du présent mode de réalisation utilisant le GPU 12 est représenté sur la figure 5. Comme représenté sur la figure 5, celui-ci comprend cinq étapes, à savoir une étape (S11) pour fixer la structure de données dans la mémoire vidéo 13B, une étape (S12) pour fixer les boîtes de délimitation dans chaque tranche du grand nombre de tranches 31a divisant l'espace de calcul 31, une étape (S13) pour calculer les numéros de tête des particules dans chacune des tranches 31a, une étape (S14) pour enregistrer les valeurs et une étape (S15) pour lire les valeurs. De plus, on peut comprendre la structure de données en tranches en termes de la construction de la structure de données en tranches et de l'utilisation de la structure de données en tranches. La construction de la structure de données en tranches met en oeuvre l'élaboration de la structure de données, la détermination des boîtes de délimitation, le calcul des numéros de tête et l'enregistrement des valeurs lors des cinq étapes S11 à S15. De plus, on peut interpréter l'utilisation de la structure de données en tranches comme la lecture des valeurs durant les cinq étapes 511 à S15. Le contenu du traitement durant les cinq étapes S11 à S15 va être décrit ci-dessous dans les cinq étapes S11 à 515. Étape d'élaboration de la structure de données S11 La structure de données permettant le chargement dans le GPU 12 va d'abord être décrite en référence à l'organigramme de traitement représenté sur la figure 6. Pour effectuer les calculs dans le GPU 12, il est nécessaire d'enregistrer des données concernant les tranches, les voxels et les particules dans l'espace de calcul sous la forme d'une texture 13B-1 dans la mémoire vidéo 13B. Comme décrit ci-dessus, l'espace de calcul 31 est divisé en une pluralité de tranches 31a et on prépare en conséquence une texture unidimensionnelle pour recevoir les valeurs nécessaires pour la pluralité de tranches 31a ; à savoir les quatre valeurs pi, bxi,min, bZi,min, nxi (étape 21).

Dans le cas où le nombre de la pluralité de tranches 31a dépasse la valeur maximale de la taille de la texture unidimensionnelle, il est également possible d'utiliser une texture bidimensionnelle. Les quatre valeurs pi, bxi,min, bZi,min et nxi nécessaires pour chaque tranche 31a sont enregistrées dans un simple canal RGBA de la texture unidimensionnelle (étape S22).

L'enregistrement est effectué en utilisant un canal RGBA. Pour cette raison, une simple texture est habituellement suffisante. De plus, on prépare une texture bidimensionnelle pour recevoir les valeurs contenues dans la grille, c'est-à-dire les voxels (étape S23). Dans l'exemple du présent mode de réalisation, les valeurs contenues dans les voxels sont les numéros de particules. On utilise la texture bidimensionnelle et on enregistre les numéros des particules contenues dans les voxels (étape S24). La texture bidimensionnelle qui reçoit les numéros de particules est appelée texture de groupe d'indices . Dans l'exemple du présent mode de réalisation, le système est imaginé de sorte qu'un texel est affecté à un voxel. Dans ce cas, le nombre de texels dans la texture bidimensionnelle est le nombre maximum de texels pouvant être enregistrés dans la texture de groupe d'indices. Étape de détermination de la boîte de délimitation S12 La procédure utilisée pour déterminer la boîte de délimitation va être ensuite décrite en référence à l'organigramme de traitement représenté sur la figure 7. Pour déterminer les boîtes de délimitation dans les tranches 31a, on calcule d'abord les coordonnées de début des voxels maximum et minimum dans chaque tranche (étape S31). Dans le traitement de ce calcul, ceci est réalisé en calculant les numéros des tranches auxquelles appartiennent ces particules d'après la valeur de coordonnée Y des particules et en calculant les valeurs maximales et les valeurs minimales des coordonnées des particules présentes dans les tranches respectives. Puisqu'on utilise le GPU 12, un sommet est affecté à une particule dans ce GPU 12 et l'écriture est effectuée dans la texture unidimensionnelle préparée ci-dessus (étape 532).

Dans le nuanceur de sommet du GPU 12, on calcule les numéros de tranches (i) d'après les valeurs de coordonnées Y des particules en utilisant l'équation (4) mentionnée ci-dessus, c'est-à-dire qu'on calcule les positions d'écriture dans la texture unidimensionnelle (étape S33) et on écrit les sommets dans ces positions calculées (étape S34). Puis, dans le nuanceur de fragment du GPU 12, les valeurs de coordonnées X et les valeurs de coordonnées Y sont délivrées en sortie en tant que couleurs (étape S35). De plus, on peut effectuer le choix des valeurs maximales et des valeurs minimales en utilisant la fonction de mélange alpha du GPU 12. Sur un processeur en continu sur lequel existe une fonction pour comparer des valeurs, telle que le mélange alpha, écrit à partir de plusieurs processeurs, on peut effectuer l'opération en sérialisant l'écriture dans la mémoire. Sur un processeur en continu avec la capacité d'écriture atomique, on peut l'utiliser pour comparer les valeurs écrites par plusieurs processeurs. Étape de calcul des numéros de tête S13 On peut habituellement calculer le nombre de voxels dans une tranche en utilisant la valeur maximale et la valeur minimale des coordonnées XZ de chaque tranche d'une pluralité de ces tranches 31a. Le calcul des numéros de tête nécessite le calcul de l'équation (3) dans chaque tranche. Lorsque le processeur en continu peut calculer un balayage de préfixe (équation (3)), on peut l'utiliser. Il n'est toutefois pas disponible en cas de mise en oeuvre avec un nuanceur sur un GPU, il faut adopter une autre stratégie. Ceci signifie que dans ce traitement, on doit lire et calculer pour chaque tranche i les valeurs allant de no à n1_1. Si l'on suppose que le nombre total de tranches est m, alors si l'on utilise un procédé de calcul classique, un accès mémoire est nécessaire (m(m+1))/2 fois ; en conséquence, la vitesse de traitement est limitée par la vitesse de transfert de mémoire. En conséquence, dans le procédé de calcul du présent mode de réalisation, ceci est exécuté par une fonction utilisant le nuanceur de sommet du GPU 12. De façon spécifique, on lit le nombre n1 de voxels présents dans la tranche i, (i + 1) et on l'ajoute à la matrice de numéro de tête de la mème tranche. De cette manière, on peut calculer les numéros de tête en accédant m fois à la mémoire. Ce traitement est dit opération de dispersion et on peut l'exécuter en utilisant un nuanceur de sommet dans le cas où on utilise un GPU 12. Dans le cas où le nombre de tranches est de m tranches, on exécute ce traitement avec le nombre d'éléments m écrit dans un affichage unidimensionnel. En d'autres termes, dans le cas où on utilise le GPU 12, le traitement est effectué avec l'écriture exécutée dans une texture unidimensionnelle comprenant m texels. Le traitement dans lequel on écrit le nombre de voxels n1 présents dans chaque tranche i dans une matrice de numéros de tête de la (i + 1)-ème à la m-ème tranche peut être effectué en dessinant des segments de ligne du (i + 1)- ème texel au m-ème texel. Si l'on utilise la fonction du GPU 12, le processus délivre en sortie le nombre de voxels dans la tranche dans une couleur conformément au fonctionnement du nuanceur de fragment. De plus, on peut évaluer l'équation (3) en effectuant un traitement d'addition conformément à la fonction de mélange alpha du GPU 12 et on peut calculer les numéros de tête des tranches respectives.

La figure 8 représente une illustration graphique de l'approche du calcul des numéros de tête des tranches. La figure 8 (A) représente le même contenu que celui de la figure 4 (B). La figure 8 (B) représente les numéros des voxels contenus dans les boites de délimitation dans chacune (par exemple) des 10 tranches de bas en haut représentées en (A) comme indiqué par les valeurs numériques aux emplacements correspondants. La figure 8 (C) représente une illustration d'image d'un état où on additionne les numéros de voxels dans les tranches respectives. La figure 8 (D) représente des valeurs cumulées concernant le nombre total de tranches de bas en haut. Étape d'enregistrement des valeurs S14 Les numéros des particules sont enregistrés dans une texture de groupes d'indices en utilisant les numéros de tête de tranche calculés comme décrit ci-dessus et les valeurs définissant les boites de délimitation. Étape de lecture des valeurs S15 Il est maintenant fait référence à l'organigramme représenté sur la figure 9, on calcule les numéros des tranches d'après les valeurs de coordonnées Y des particules (étape S41) et on lit les numéros de tête p; de ces tranches, les valeurs minimales bxi,min et bz;,m;n dans les tranches et les nombres de voxels nx; des tranches dans la direction axiale X (étape S42). On calcule l'équation (5) ci-dessus en utilisant ces valeurs et on calcule les indices des voxels affectés à ces particules (étape S43). On réalise l'écriture des valeurs dans les texels correspondant aux indices calculés en lisant les numéros de particules de ces texels, un sommet étant affecté à une particule (étape S44). On effectue la lecture des valeurs enregistrées dans les voxels dans lesquels certaines coordonnées sont présentes en calculant les indices des voxels de la même manière que dans l'enregistrement des valeurs à partir de ces coordonnées, c'est-à-dire en calculant les adresses mémoire. Le procédé de calcul consistant à utiliser une structure de données en tranches selon le présent mode de réalisation peut être réalisé par la construction d'une structure de données de grille pour enregistrer les numéros de particules et en effectuant le traitement jusqu'à l'enregistrement des numéros de particules en utilisant le GPU 12 ; de cette manière, on peut exécuter toutes les étapes de la simulation basée sur des particules en utilisant le GPU 12. Le procédé de calcul du présent mode de réalisation n'utilise pas de grille fixe et n'est pas soumis aux limitations du domaine de calcul ; en conséquence, on peut facilement exécuter les calculs même dans le cas d'un espace de calcul large et on peut utiliser efficacement la mémoire en excluant les voxels dans lesquels aucune particule n'est présente. De plus, même si l'on augmente le nombre de particules, on peut exécuter une simulation basée sur des particules en utilisant la mémoire utilisée habituellement. Dans le mode de réalisation ci-dessus, on a décrit un cas dans lequel on a utilisé un nuanceur dans le chargement des programmes dans le GPU. La présente invention n'y est toutefois pas limitée ; on peut par exemple effectuer un chargement en utilisant un certain autre modèle de programmation. Hormis le nuanceur, on peut utiliser actuellement un CUDA, CTM, Brook ou analogue dans le chargement des programmes dans le GPU. Ceux-ci sont utilisés en commun dans le sens du langage de programmation dans le cas où on utilise un GPU en tant que processeur en continu. Dans un exemple dans lequel on utilise le nuanceur, on enregistre les données concernant les tranches, voxels et particules, dans l'espace de calcul utilisé pour les calculs dans le GPU 12, dans la mémoire vidéo 13B sous la forme d'une texture 13B-1. Toutefois, dans le cas où on utilise un CUDA ou analogue, à la place d'une texture, on utilise généralement une matrice .

Claims (10)

REVENDICATIONS

1. Système comprenant au moins un processeur (12) et une mémoire (13B) pour mettre en oeuvre un espace de calcul tridimensionnel (31) construit à partir d'un grand nombre de voxels (32) ; une pluralité de domaines en tranches bidimensionnels (31a) perpendiculaires à un axe arbitraire unique, formés dans l'espace de calcul tridimensionnel (31), tels que le grand nombre de voxels (32) sont divisés par la pluralité de domaines en tranches bidimensionnels (31a) ; les coordonnées de début de chacun des voxels maximum et minimum étant calculées pour une plage (44) de voxels dans laquelle des particules (42) sont présentes dans chaque domaine de la pluralité de domaines en tranches bidimensionnels (31a), de sorte que cette plage (44) est déterminée comme une plage rectangulaire entourée par une forme rectangulaire ; et une mémoire (13B) étant prévue pour les voxels contenus dans la plage rectangulaire (44) de chaque domaine de la pluralité de domaines en tranches bidimensionnels (31a).

2. Système selon la revendication 1, dans lequel une valeur qui spécifie les particules est enregistrée dans un élément d'enregistrement de la mémoire (13B) prévue pour les voxels dans laquelle sont présentes les particules (42).

3. Système selon la revendication 1, dans lequel on effectue le calcul des numéros de voxels v(x, y, z) des voxels dans lesquels sont présents certains points (x, y, z) dans les plages rectangulaires (44) de chaque domaine de la pluralité de domaines en tranches bidimensionnels (31a), en utilisant une valeur qui définit les plages rectangulaires (44) de chacun des domaines en tranches bidimensionnels (31a), une valeur qui détermine le numéro de tranche ou un numéro d'en-tête.

4. Système selon la revendication 1, dans lequel le calcul de la simulation basée sur des particules est un calcul de recherche de particule proche et l'espace de calcul tridimensionnel (31) est divisé par les domaines en tranches bidimensionnels (31a) pour rendre plus efficace le calcul de la recherche de particules proches.

5. Système selon l'une quelconque des revendications 1 à 4, dans lequel on utilise un GPU (12) pour effectuer le calcul où l'espace de calcul tridimensionnel (31) est divisé par les domaines en tranchesbidimensionnels (31a) pour le calcul de la simulation basée sur des particules.

6. Procédé de chargement d'une simulation basée sur des particules utilisant une structure de données en tranches dans un processeur en continu (12), qui est un procédé pour construire une structure de données utilisée pour améliorer l'efficacité de calcul d'une recherche de particule proche de la simulation basée sur des particules, enregistrer des données qui sont nécessaires pour effectuer une recherche de particule proche sur le processeur en continu (12) en utilisant cette structure de données, dans une mémoire vidéo (13B) sous la forme d'une matrice, et charger la matrice dans le processeur en continu (12), le procédé comprenant : la formation d'une pluralité de domaines en tranches bidimensionnels (31a) perpendiculaires à un axe arbitraire unique dans un espace de calcul tridimensionnel (31) construit en utilisant un grand nombre de voxels et la division du grand nombre de voxels (32) par la pluralité de domaines en tranches bidimensionnels (31a) ; le calcul des coordonnées de début respectives des voxels maximum et minimum pour une plage de voxels dans laquelle sont présentes des particules dans chaque domaine de la pluralité de domaines en tranches bidimensionnels (31a) et ainsi la détermination d'une plage rectangulaire pour enfermer la plage de voxels en utilisant une forme rectangulaire ; la préparation d'au moins une matrice unidimensionnelle ; l'enregistrement, dans les éléments de ladite matrice, de quatre valeurs qui sont nécessaires au minimum pour définir chaque domaine de la pluralité de domaines en tranches bidimensionnels (31a) ; la préparation d'une autre matrice qui est au moins une matrice unidimensionnelle ; et l'enregistrement d'un numéro de particule des particules dans ladite autre matrice.

7. Procédé selon la revendication 6, dans lequel les quatre valeurs minimales sont le numéro p; du voxel de tête dans un domaine en tranches bidimensionnel arbitraire (i), les coordonnées de début bxi,min et bzi,m;n du voxel minimum et le nombre de voxels nx; dans une direction axiale spécifiée.

8. Procédé selon la revendication 6, caractérisé en ce que ledit processeur en continu est un GPU (12) et lesdits éléments sont des canaux RGBA.

9. Procédé selon la revendication 8, caractérisé en ce qu'on 5 utilise une texture comme dite matrice lorsqu'on utilise un nuanceur dans le chargement du programme dans ledit GPU (12).

10. Système selon la revendication 1, caractérisé en ce que ledit espace est un espace (31) utilisé dans le calcul d'une simulation basée sur des particules.