Bonne structure d'accélération pour les tests de sphères de rayon avec des sphères qui se déplacent

Question

Je cherche la structure d'accélération appropriée pour faire des tests d'intersection de sphère de rayon (dans un jeu). les conditions suivantes:

sont arround 100 -Il y sphères et 100 rayons pour tester les uns contre les autres par image

-les sphères se déplacent dans chaque trame, de même les rayons

peuvent être des rayons -Il y/sphères ajoutés/supprimés dans chaque trame (mais la plupart d'entre eux sera le même entre deux cadres, juste déplacé légèrement)

chose -whole est en 3D

un KD-Tree est très bon pour intersection Ray tests, mais depuis les sphères déplacer, je devrais reconstruire le KD-Tree dans chaque image, ce qui est coûteux

un Oct-tree est plus facile à maintenir, mais très inefficace pour les tests d'intersection de rayons.

100 rayons contre 100 sphères ne semble pas beaucoup, mais je suis le codage des ressources très faibles, donc je suis à la recherche d'une accélération pour que

quelqu'un peut me donner quelques conseils à ce sujet?

Answer 1

100x100 = 10k, une force brute optimisée ne semble pas incohérente, en particulier que le test d'intersection rayon/sphère implique seulement ajouter/multiplier. Vous pouvez toujours précalculer tout vecteur de rayon normalisé avant la boucle principale. Si vous faites l'hypothèse que vous vivez dans un univers borné et que la densité spatiale des sphères et des rayons est relativement uniforme, vous pouvez utiliser une grille spatiale fixe (oct-tree fixe) - quelque chose comme une grille de cellules 16x16x16, ou plus-- et:

• Précalculer pour chaque cellule intersection sphère (facile à calculer, ne concernent que quelques ajouts et des comparaisons), magasin dans chaque cellule la liste des sphères qui se croisent,
• pour chaque rayon, en une boucle:
  • calculer la liste des cellules le ra y traverse (une méthode basée sur un algorithme de Bresenham pourrait faire l'affaire)
  • faire le test d'intersection pour toutes les sphères dans cette liste de cellules.

De cette façon, vous ne devez pas stocker tout rayon dans un arbre, que les sphères. L'efficacité de cette méthode dépend du rapport taille de la cellule/taille de la sphère, si vous n'avez pas trop de dispersion sur la taille de la sphère, cela peut être un bon indice.

Si les sphères ne se croisent et la taille sphère ont un minimum, vous pouvez même lié la liste sphère dans la liste des cellules (nombre approprié est laissé en exercice au lecteur ...)

HTH