intersection rapide de sphère-grille

Question

étant donné une grille 3D, un point 3d comme centre de sphère et un rayon, je voudrais calculer rapidement toutes les cellules contenues ou recoupées par la sphère.

Actuellement, je prends le cadre de délimitation (gridéigned) de la sphère et calcule les deux cellules pour le point max min anx de cette boundingbox. Ensuite, pour chaque cellule entre ces deux cellules, je fais un test d'intersection boîte-sphère.

serait génial s'il y avait quelque chose de plus efficace

merci!

Answer 1

Il existe une version de l'algorithme de Bresenham pour dessiner des cercles. Considérons l'endroit bidimensionnel à z = 0 (supposons que la sphère est à 0,0,0 pour l'instant), et regardons seulement le plan x-y des points de la grille. En partant de x = R, y = 0, suivez l'algorithme de Bresenham jusqu'à y = y_R, x = 0, sauf qu'au lieu de dessiner, vous utilisez simplement le résultat pour savoir que tous les points de la grille avec les coordonnées x inférieures sont à l'intérieur du cercle. à x = x_center. Mettez-les dans une liste, comptez-les ou prenez note de. Quand cela est fait avec un problème bidimensionnel, répétez avec z variable et en utilisant un rayon réduit R (z) = sqrt (R^2-z^2) à la place de R, jusqu'à z = R. Si le centre de la sphère est en effet situé sur un point de la grille, vous savez que chaque point de la grille à l'intérieur ou à l'extérieur de la moitié droite de la sphère a un partenaire miroir sur le côté gauche, et vous pouvez faire la moitié du comptage/listing par dimension. Vous pouvez également gagner du temps en exécutant Bresenham uniquement sur la ligne à 45 degrés, car tout point x, y relatif au centre a un partenaire y, x. Si la sphère peut être n'importe où, vous devrez calculer les résultats pour chaque octant.

Answer 2

Peu importe l'efficacité avec laquelle vous calculez une cellule individuelle à l'intérieur ou à l'extérieur de la sphère, votre algorithme sera toujours O (rayon^3) car vous devez marquer autant de cellules. La suggestion de DarenW de l'algorithme de cercle du milieu (aka Bresenham) pourrait donner une accélération constante du facteur, tout comme tester simplement l'intersection en utilisant le rayon au carré pour éviter l'appel de sqrt().

Si vous voulez améliorer les performances de O (r^3), vous pouvez utiliser un octree au lieu d'un quadrillage. Chaque nœud de l'arbre peut être marqué comme étant entièrement à l'intérieur, entièrement à l'extérieur ou partiellement à l'intérieur de la sphère. Pour les nœuds partiellement internes, vous recyclez l'arbre jusqu'à ce que vous arriviez aux cellules les plus fines. Cela nécessitera toujours de marquer O (r^2 log r) nœuds [O (r^2) nœuds sur la limite, O (log r) parcourt l'arbre pour arriver à chacun d'entre eux], donc cela ne vaut peut-être pas la peine problème dans votre application.