Coder des tables de hachage spatiales | XPBD

Nous terminons notre discussion sur les tables de hachage spatiales avec un rapide coup d'œil sur la façon de les implémenter avec du code !

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

By Carmen Cincotti  

Ces dernières semaines, nous avons vu plusieurs articles sur le sujet des tables de hachage.

Enfin, nous sommes prêts à voir du code !

Au cours de cet article, nous verrons comment coder une table de hachage spatiale dans le contexte de notre simulation de tissu que nous construisons depuis quelques mois.

Par conséquent, l’implémentation peut être différente si vous avez une application différente !

Construire une table de hachage spatiale

Commençons par voir comment construire une table de hachage spatiale. Imaginons que nous ayons un Float32Array qui est rempli avec les positions des particules qui appartiennent à notre morceau de tissu.

Du dernier article, rappelons que nous avons une fonction pour nous aider, hashPos, qui hache nos positions de particule comme ceci :

hashCoords(xi: number, yi: number, zi: number) { const h = (xi * 92837111) ^ (yi * 689287499) ^ (zi * 283923481); // fantasy function return Math.abs(h) % tableSize; } intCoord(coord: number) { return Math.floor(coord / spacing); } hashPos(pos: Float32Array, nr: number) { return this.hashCoords( intCoord(pos[3 * nr]), intCoord(pos[3 * nr + 1]), intCoord(pos[3 * nr + 2]) ); }

Je vous laisse ce lien pour voir comment ces fonctions ( hashPos, intCoord, et hashCoords) fonctionnent !

Interroger une table de hachage spatiale

Ensuite, nous devons interroger la table. Pendant la simulation, nous pouvons simplement appeler queryAll pendant une image d’animation, qui est responsable d’appeler query pour chaque particule du morceau de tissu.

Lors de la simulation, nous pouvons accéder aux particules qui sont adjacentes les unes aux autres en utilisant son id. Pour ce faire, nous interrogeons firstAdjId par cette fonction utile, getAdjacentParticles :

getAdjacentParticles(id: number) { const start = this.firstAdjId[id]; const end = this.firstAdjId[id + 1]; return this.adjIds.slice(start, end); }

Le code entier de la table de hachage spatiale

Voici le code entier. J’utilise une classe JavaScript que j’ai nommée Hash qui contient toutes les fonctionnalités de la table de hachage spatiale :

L’intégralité du code dans une simulation XPBD avec WebGPU

Enfin, pour voir ce code dans une simulation de tissu, je vous invite à voir ma simulation de tissu avec WebGPU !

Cloth blowing in the wind

Des ressources (en français et anglais)


Comments for Coder 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!