Arbres BSP

Qu’est-ce qu’est un arbre BSP?

Un "Binary Space Partitioning Tree" (ou "BSP Tree" ou "Arbre binaire pour le partitionnement de l’espace") est une structure de données qu’on utilise pour organiser des objets dans un espace de dimension n. Dans le domaine de l’informatique graphique, ce concept a notament de nombreuses applications dans l’élimination des parties cachées et dans le lancer (ou tracé) de rayons. Un arbre BSP est une division récursive de l’espace qui considère chaque polytope (segment en 2d ou polygone en 3d) comme un hyperplan (droite en 2d ou plan en 3d) de coupe qu’il utilise pour classer tous les objets qui restent dans l’espace comme soit devant, soit derrière cet hyperplan. Autrement dit, quand on insère un segment dans l’arbre, on le classe relativement à chaque noeud fils approprié. Pour plus de renseignements sur les arbres BSP, lisez: BSP Tree FAQ.


Je regrette que votre navigateur ne soit pas capable d’afficher les appliquett es Java.

Comment utiliser cette Appliquette

Vous pouvez dessiner des segments dans la première fenêtre (le premier segment, quand il est dessiné, a pour effet d’initialiser des processus Java, ainsi l’appliquette prend plus de temps pour dessiner les segments saisis postérieurement). Les segments sont nommés dans l’ordre numérique de leur saisie, et l’arbre est construit par insertion de chaque segment dans cet ordre. S’il faut partager une partition, les noms pour les composantes "devant" et "derrière" recevoient un "f" et un "b" accolé au numéro d’ordre, respectivement. Par exemple, si la partition 1 croise le plan de coupe créé par la partition 0: la composante de la partition 1 qui est devant la partition 0 va s’appeller "1f", et la composante qui est derrière va s’appeler "1b".

Vous pouvez modifier le point de vue (en couleur magenta) directement avec la souris. Ainsi, le petit carré peut etre transporté là ou vous le désirez dans la scène pour placer l’observateur, et l’extrémité de la flèche permet de positionner la direction de vue. La pseudo-vue 3d est alors raffraichie.

Si le temps de réponse est trop élevé quand vous bougez des segments, mettez le bouton "interactive" en position non enfoncée pour annuler la nature interactive de l’appliquette. En mode non-interactif, l’arbre BSP est reconstruit seulement après qu’un segment soit déplacé vers un nouvel emplacement et que le bouton de la souris soit inactif.

Si le dessin de l’arbre devient trop grand pour sa fenêtre, utilisez la souris dans la fenêtre pour le déplacer.

Plus d’information à propos des arbres BSP

Probablement le meilleur site pour trouver des informations sur les arbres BSP est BSP Tree FAQ, qui fait le point sur les questions les plus fréquemment posées.

La traduction a été légèrement révisée par Jean-Marc FERRARI, élève doctorant en informatique graphique de l’Université de Bordeaux, France. Remarque: la traduction de applet en appliquette n’est pas officielle mais souvent employée. Certains prefèrent le terme applelette ou utilisent directement la terminologie anglaise.