Comment trouver la valeur de hachage d'un vecteur 3D?

Question

J'essaye d'effectuer la détection de collision de phase large avec une approche de taille de grille fixe. Ainsi, pour la position de chaque entité: (x, y, z) (chacun de type float), j'ai besoin de trouver dans quelle cellule se trouve l'entité. J'ai alors l'intention de stocker toutes les cellules dans une table de hachage. signaler des collisions (le cas échéant). Voici ce que je fais: Position de la cellule de grille: (type int) (Gx, Gy, Gz) => (x/M, y/M, z/M) où M est la taille de la grille.

Une fois, j'ai une cellule, je voudrais l'ajouter à une table de hachage avec sa clé étant un hachage unique basé sur (Gx, Gy, Gz) et la valeur étant la cellule elle-même. Maintenant, je ne peux pas penser à une bonne fonction de hachage et j'ai besoin d'aide avec ça. Est-ce que quelqu'un peut me suggérer une bonne fonction de hachage?

Merci

Answer 1

Si quelqu'un est toujours intéressé par cela, je cernées une solution qui fonctionne ici:

http://www.gamedev.net/community/forums/topic.asp?topic_id=567378

Answer 2

L'approche de la grille va avoir des problèmes près des limites de la grille des boites. Pourquoi ne pas utiliser les arbres BSP à la place?

Answer 3

Ma fonction de hachage préférée pour ce type de vecteur est de faire tourner les bits de chaque composant par une constante différente et de les rapprocher ensemble.

C'est très rapide, et les rotations de bits sont utiles pour réduire les collisions et assurer que l'espace clé est utilisé autant que possible.

Answer 4

Voici quelques références que vous pourriez consulter. Les papiers de Warren discutent de l'algorithme de hachage en détail:

A parallel hashed Oct-Tree N-body algorithm

A portable parallel particle program