Comment interroger des tables de hachage spatiales | XPBD

Continuons à examiner les tables de hachage spatiales et comment les interroger. Cela sera nécessaire pour implémenter les autocollisions dans notre simulation de tissu XPBD.

Keywords: infographie, tutoriel, structures de données, leetcode, autocollisions

By Carmen Cincotti  

Je voudrais poursuivre notre conversation sur les tables de hachage spatiales dont nous avons commencé à apprendre la semaine dernière.

Les tables de hachage spatiales nous permettront d’implémenter une fonctionnalité très importante des simulations de tissus : les autocollisions.

Qu’est-ce qu’une autocollision de tissu ?

Une autocollision est l’interaction qui se produit lorsque les particules d’un morceau de tissu entrent en collision les unes contre les autres.

Folding cloths

Comment interroger une table de hachage spatiale :

Voyons ensemble comment interroger une table de hachage spatiale afin de détecter des particules proches les unes des autres, tout en gardant une complexité temporelle rapide.

Étape 1 : Créer la table de hachage spatiale et la remplir

Nous avons déjà fait cela lors de l’article précédent. Je vous conseille de le lire avant de continuer !

Avec nos deux tableaux, cellCount et particleMap, nous sommes prêts à rechercher des particules à proximité.

Self collisions 1

Étape 2 : Interroger des carrés adjacents

Notre but dans cette étape est de trouver toutes les particules qui se trouvent dans des carrés adjacents afin de limiter la recherche aux particules proches. Cette méthode est très rapide par rapport à une méthode qui vérifie chaque particule pour voir si elles sont proches ou non.

Pour effectuer une telle requête, on définit une distance de recherche maximale, maxDist. Imaginons que j’ai déjà défini maxDist égal à la longueur d’un carré que je voudrais rechercher des particules proches de la particule 55 :

Grid showing maxDist

Comme vous pouvez le voir, j’ai marqué en violet tous les points que nous finirons par interroger.

Maintenant, nous allons parcourir tous ces points violets afin de voir si les carrés dans lesquels ils résident contiennent des particules. Nous devrons également vérifier le carré dans lequel se trouve la particule 55.

Pour l’instant, voyons un exemple sur la façon de vérifier les particules dans un carré d’intérêt.

Je vais interroger le point violet en haut à gauche. On commence par calculant la coordonnée de la grille, squareCoordinate, dans laquelle ce point se trouve. Pour le faire, on utilise la fonction intCoord :

intCoord(pos: number) { return Math.floor(pos / spacing); } const squareCoordinates = [ intCoord(pos.x), intCoord(pos.y), ]

En utilisant squareCoordinate, nous pouvons indexer dans cellCount pour voir quelles particules s’y trouvent…

Rappelons que nous pouvons utiliser la fonction de hachage hashPos pour calculer le hachage d’une position :

hashCoords(xi: number, yi: number, zi: number) { const hash = (xi * 92837111) ^ (yi * 689287499) ^ (zi * 283923481); return Math.abs(hash); } hashPos(squareCoordinates) { return hashCoords( ...squareCoordinates ); }

Supposons que nous utilisons une fonction de hachage qui, en hachant squareCoordinates, l’indice 44 nous est renvoyé :

Indexing into cellCount, but finding nothing

Pour voir s’il y a des particules dans cet espace, on effectue le calcul suivant :

nparticles=cellCount[i+1]cellCount[i] n_\text{particles} = \text{cellCount[i+1]} - \text{cellCount[i]}

ii est l’indice qu’on vient de calculer.

En poursuivant cet exemple, nous constatons qu’il n’y a rien dans la table à l’index 44 ! :

nparticles=cellCount[5]cellCount[4]nparticles=11=0 n_\text{particles} = \text{cellCount[5]} - \text{cellCount[4]} \\[6pt] n_\text{particles} = 1 - 1 = 0

Voyons maintenant un exemple d’un carré dans lequel résident des particules. Interrogeons la coordonnée située en bas :

Check square where there are particles

En hachant squareCoordinate, nous obtenons l’indice 55. Avec cet indice, nous interrogeons le tableau cellCount pour les particules comme avant :

nparticles=cellCount[6]cellCount[5]nparticles=21=1 n_\text{particles} = \text{cellCount[6]} - \text{cellCount[5]} \\[6pt] n_\text{particles} = 2 - 1 = 1

Cette fois, nous voyons qu’une particule existe dans le carré d’intérêt ! Le nombre à cellCount[i] sert également à indexer dans particleMap, qui dans ce cas est 11.

Par conséquent, en indexant dans particleMap avec l’index 11, nous pouvons voir que la particule 44 se trouve dans le carré d’intérêt.

Pour finir, nous ajoutons la particule 44 dans un tableau appelé queryIds pour l’utiliser plus tard dans l’application :On ajoute la particule 44 dans un tableau qui s’appelle queryIds pour l’utiliser plus tard dans l’application :

Array holding query Ids

Étape 3 : La confirmation de la collision

Avec notre tableau, queryIds, il est temps de confirmer que chaque particule trouvée lors de l’étape précédente se tombe dans la distance de recherche maximale, maxDist, de la particule d’intérêt, dans ce cas la particule 55 :

Particle 4 falls within maxDist

On voit sur l’image ci-dessus que la particule 44 se trouve bien dans ce rayon de recherche. Dans le code, nous devons utiliser une fonction de distance pour confirmer que c’est le cas. Nous pouvons utiliser une fonction de distance typique, comme ceci :

Δp=pipjd=Δpx2+Δpy2 \Delta p = \text{p}_i - \text{p}_j\\[6pt] d = \sqrt{\Delta{p}_x^2 + \Delta{p}_y^2}

Si d<maxDistd < \text{maxDist}, on peut considérer que les deux particules se croisent !

Si d>maxDistd > \text{maxDist}, on remarquerait que les deux particules ne se croisent pas comme représenté sur l’image ci-dessous :

Particle 4 and 5 do not intersect

Bien sûr, nous pouvons éviter ces étapes en utilisant deux boucles pour visiter toutes les particules deux fois afin de déterminer si deux particules se croisent. Une telle opération aurait une complexité temporelle O(n2)O(n^2). Cependant, lors d’une simulation, une telle complexité n’est pas acceptable.

Des ressources (en français et anglais)


Comments for Comment interroger des tables de hachage spatiales | XPBD



Written by Carmen Cincotti, computer graphics enthusiast, language learner, and improv actor currently living in San Francisco, CA.  Follow @CarmenCincotti

Contribute

Interested in contributing to Carmen's Graphics Blog? Click here for details!