Je travaille en chimie théorique sur un cluster à haute performance, souvent avec des simulations de dynamique moléculaire. L'un des problèmes que j'aborde concerne un champ statique d'hyper-sphères à N dimensions (typiquement N = 2-5), avec lequel une particule test peut entrer en collision. Je cherche à optimiser (lire : réviser) la structure de données que j'utilise pour représenter le champ de sphères afin de pouvoir effectuer une détection rapide des collisions. Actuellement, j'utilise un simple tableau de pointeurs vers une structure à N membres (des doubles pour chaque coordonnée du centre) et une liste des plus proches voisins. J'ai entendu parler des arbres oct- et quad- mais je n'ai pas trouvé d'explication claire sur leur fonctionnement, sur la façon d'en implémenter un efficacement, ou sur la façon de faire une détection rapide des collisions avec un arbre oct- et quad-. Compte tenu de la taille de mes simulations, la mémoire n'est (presque) pas un problème, mais les cycles le sont.
Réponses
Trop de publicités?
La meilleure façon d'aborder ce problème dépend de plusieurs facteurs que vous n'avez pas décrits : - Le même arrangement d'hypersphères sera-t-il utilisé pour de nombreux calculs de collision de particules ? - Les hypersphères sont-elles de taille uniforme ? - Quel est le mouvement de la particule (par exemple, ligne droite/courbe) et ce mouvement est-il affecté par les sphères ? - Considérez-vous que la particule a un volume nul ?
Je suppose que la particule ne se déplace pas simplement en ligne droite, car il s'agirait d'un calcul relativement rapide consistant à trouver le point le plus proche entre une ligne et un point, ce qui serait probablement aussi rapide que de trouver la boîte avec laquelle la ligne se croise (pour déterminer l'endroit de l'arbre n à examiner).
Si les positions de l'hypersphère sont fixes pour un grand nombre de collisions de particules, le calcul de la valeur de l'hypersphère peut s'avérer utile. décomposition de voronoï/tessellation de Dirichlet vous permettrait de trouver rapidement la sphère la plus proche de votre particule pour un point donné de l'espace.
Cependant, pour répondre à votre question initiale sur les octrees/quadtrees/2^n-trees, en n dimensions, vous commencez par un (hyper)-cube qui contient la zone de l'espace qui vous intéresse. Ce cube sera subdivisé en 2^n hypercubes si vous estimez que son contenu est trop compliqué. Cette opération se poursuit de manière récursive jusqu'à ce que vous n'ayez plus que des éléments simples (par exemple, un centroïde d'hypersphère) dans les nœuds feuilles. Maintenant que l'arbre n est construit, vous l'utilisez pour la détection des collisions en prenant la trajectoire de votre particule et en l'intersectant avec l'hypercube extérieur. La position de l'intersection vous indiquera quel hypercube du niveau suivant de l'arbre visiter ensuite, et vous déterminerez la position de l'intersection avec tous les 2^n hypercubes à ce niveau, en suivant vers le bas jusqu'à ce que vous atteigniez un nœud feuille. Une fois que vous avez atteint la feuille, vous pouvez examiner les interactions entre la trajectoire de votre particule et l'hypersphère stockée à cette feuille. En cas de collision, vous avez terminé, sinon vous devez trouver le point de sortie de la trajectoire de la particule de la feuille de l'hypercube actuel et déterminer l'hypercube vers lequel elle se déplace ensuite. Continuez jusqu'à ce que vous trouviez une collision ou que vous quittiez entièrement l'hypercube délimité.
La recherche efficace de l'hypercube voisin lors de la sortie d'un hypercube est l'une des parties les plus difficiles de cette approche. Pour 2^n arbres, les approches de Samet {1, 2} peuvent être adaptées. Pour les kd-arbres (arbres binaires), une approche est proposée dans {3} section 4.3.3.
Une mise en œuvre efficace peut être aussi simple que le stockage d'une liste de 8 pointeurs de chaque hypercube vers ses hypercubes enfants, et le marquage de l'hypercube d'une manière spéciale s'il s'agit d'une feuille (par exemple, rendre tous les pointeurs NULL).
Une description de la division de l'espace pour créer un quadri-arbre (que vous pouvez généraliser à un n-arbre) peut être trouvée dans Klinger & Dyer {4}.
Comme d'autres l'ont mentionné, les arbres kd peuvent être plus adaptés que les arbres 2^n, car l'extension à un nombre arbitraire de dimensions est plus simple, mais l'arbre sera plus profond. Il est également plus facile d'adapter les positions de division à la géométrie de vos hypersphères avec un arbre kd. hypersphères avec un arbre kd. La description ci-dessus de la détection des collisions dans un arbre 2^n s'applique également à un arbre kd.
{4} Experiments in picture representation using regular decomposition, Klinger, A., et Dyer, C.R. E, Comptr. Graphics and Image Processing 5 (1976), 68-105.
Un arbre quadruple est un arbre à deux dimensions dans lequel, à chaque niveau, un nœud a quatre enfants, chacun d'entre eux couvrant 1/4 de la surface du nœud parent.
Un arbre Oct est un arbre tridimensionnel dans lequel, à chaque niveau, un nœud a 8 enfants, chacun d'entre eux contenant 1/8e du volume du nœud parent. Voici une image pour vous aider à le visualiser : http://en.wikipedia.org/wiki/Octree
Si vous effectuez des tests d'intersection à N dimensions, vous pouvez généraliser cela à un arbre à N dimensions.
Les algorithmes d'intersection commencent au sommet de l'arbre et parcourent de manière récursive tous les nœuds enfants qui croisent l'objet testé. À un moment donné, on atteint les nœuds feuilles, qui contiennent les objets réels.
Un octree fonctionne tant que vous pouvez spécifier les sphères par leur centre - il classe hiérarchiquement les points dans des régions cubiques à huit enfants. Pour déterminer les voisins d'une structure de données octree, vous devrez effectuer des calculs sphère-intersection-cube (dans une certaine mesure plus faciles qu'il n'y paraît) afin de déterminer quelles régions cubiques d'un octree se trouvent à l'intérieur de la sphère.
Pour trouver les voisins les plus proches, il faut remonter l'arbre jusqu'à ce qu'un nœud ait plus d'un enfant peuplé et que tous les nœuds environnants soient inclus (ce qui permet à la requête de prendre en compte tous les côtés).
De mémoire, il s'agit de l'algorithme de base (quelque peu naïf) pour l'intersection sphère-cube :
i. Le centre est-il à l'intérieur du cube (ce qui donne la situation éponyme) ?
ii. L'un des coins du cube se trouve-t-il dans le rayon r du centre (coins à l'intérieur de la sphère) ?
iii. Pour chaque surface du cube (vous pouvez éliminer certaines surfaces en déterminant sur quel côté de la surface se trouve le centre), calculez (c'est de l'arithmétique vectorielle de première année) :
a. Une normale de la surface qui va au centre de la sphère
b. La distance entre le centre de la sphère et l'intersection de la normale avec le plan de la surface (la corde intersecte le plan de la surface du cube).
c. L'intersection du plan se trouve à l'intérieur du côté du cube (une condition de l'intersection de la corde avec le cube).
iv. Calculer la taille de la corde (Sin de Cos^-1 du rapport entre la longueur normale et le rayon de la sphère)
v. Si le point le plus proche de la ligne est inférieur à la distance de la corde et que ce point se trouve entre les extrémités de la ligne, la corde coupe l'une des arêtes du cube (la corde coupe la surface du cube quelque part le long de l'une des arêtes).
Je me souviens un peu moins bien, mais c'est quelque chose que j'ai fait pour une situation impliquant des régions sphériques en utilisant une structure de données octee (il y a de nombreuses années). Vous pouvez également consulter les KD-trees, comme le suggèrent les autres affiches, mais votre question initiale semble très similaire à ce que j'ai fait.
