Sphère englobante

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Sphère englobante de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Sphere englobante — 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… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • LIBERTÉ — La question de la liberté peut être abordée à trois niveaux différents, dont chacun fait appel à un type propre de discours. À un premier niveau, celui du langage ordinaire, « libre » est un adjectif qui caractérise certaines actions humaines… …   Encyclopédie Universelle

  • Histoire du mouvement keplerien — La description du mouvement des planètes par Johannes Kepler à partir des tables établies par son maître Tycho Brahe est un tournant dans l histoire des sciences qui prit naissance au début du XVIIe siècle. Malgré le retentissant procès de… …   Wikipédia en Français

  • Religion — La religion a été définie pour la première fois par Cicéron comme « le fait de s occuper d une nature supérieure que l on appelle divine et de lui rendre un culte »[1]. Dans les langues où le terme est issu du latin religio, la religion …   Wikipédia en Français

  • MYTHE - L’interprétation philosophique — Traitant ici uniquement des problèmes qui concernent la philosophie, c’est à dire des problèmes de sens et de vérité, on laissera de côté les discussions contemporaines sur le mythe en anthropologie et en histoire comparée des religions, ainsi… …   Encyclopédie Universelle

  • Histoire du mobilier francais — Histoire du mobilier français Sommaire 1 Le style Moyen Age 2 Le style Renaissance 3 Le style Louis XIII 4 Le style Louis XIV …   Wikipédia en Français

  • Histoire du mobilier français — L histoire du mobilier français est relativement riche, du fait des influences étrangères et des modes locales qui l ont modelée. Sommaire 1 Le style Moyen Age 2 Le style Renaissance 3 Le style Louis XIII 4 …   Wikipédia en Français

  • Lexique Sur L'Histoire Du Mobilier Français — Histoire du mobilier français Sommaire 1 Le style Moyen Age 2 Le style Renaissance 3 Le style Louis XIII 4 Le style Louis XIV …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”