- Sphère englobante
-
La technique de la Bounding Sphere ou sphère englobante est un algorithme utilisé dans le calcul 3D. Il permet d'optimiser la projection d'un point sur une surface en 3D. En effet, au lieu de parcourir tous les points de la surface et chercher le minimum des distances avec le point de départ, cette technique permet de borner l'espace de recherche.
Considérons la surface en 3D comme une matrice avec les lignes représentant l'axe X, les colonnes l'axe Y, et la hauteur est la valeur dans la case Mat[x][y] = z , notons le point que l'on veut projeter Pt(X,Y,Z), et la sphère de rayon R centrée en le point précédent.
La principale optimisation en temps se fait à la première étape, en bornant la recherche en X et en Y. On parcourt seulement de X-R a X+R et de Y-R a Y+R , cependant il faut faire attention à ces valeurs, si la valeur est négative, on prendra zéro à la place, et si la valeur est supérieure à la dimension de la surface 3D, on gardera cette dimension. On obtient ainsi un espace de recherche de la forme d'un parallélépipède.
Maintenant, dans cet espace réduit, on regarde s'il existe un point dont la distance avec le centre de la sphère (le point considéré) est inférieure ou égale au rayon choisi. S'il n'y en a pas, on recommence l'opération en augmentant le rayon de la sphère. S'il y en a au moins un, on choisira le minimum des distances.
Algorithme
En voici l'algorithme (en pseudo-code):
pas_trouvé = true; R = 0; min = -1; Tant que pas_trouvé :R = R + 1 /* ou R = R * 2 */ :Pour i de X-R a X+R ::Pour j de Y-R a Y+R :::Si ((dist = Dist(Pt, Mat[i][j])) <= R) and (min < 0 or dist < min) /* Mat[i][j] point en x=i, y=j */ :::Alors ::::pas_trouvé = false; ::::min = dist; :::FinSi ::FinPour :FinPour FinTantque
Liens externes
Catégorie :- Algorithme géométrique
Wikimedia Foundation. 2010.
