UP PREC SUIV   HOME

1.2 Partitions dans le plan

Une grande catégorie de prétraitements est basée sur des schémas de découpage du plan dont le but est de subdiviser le plan en régions contenant moins d'objets. Lors d'un calcul de visibilité, une première série de tests de visibilité est effectuée sur les régions issues du découpage. Les régions non visibles, et tous les objets qu'elles contiennent, sont éliminés du calcul. Après ce premier calcul, qui ne doit pas être trop coûteux, le nombre d'objets restant à considérer est en général plus petit que le nombre total d'objets et prend moins de temps à traiter.

1.2.1 Boîtes englobantes

Une première méthode pour découper le plan est de regrouper les objets en groupes, et d'utiliser pour la phase de sélection la boîte englobante de ces groupes objets. Une boîte englobante est une région de l'espace, généralement un polygone, qui contient tous les objets du groupe. Ces boîtes englobantes peuvent avoir des côtés parallèles aux axes, être constituées par l'enveloppe convexe des objets, etc. La première étape d'un calcul de lancer de rayons par exemple, consiste à tester l'intersection entre le rayon et les boîtes englobantes. Ensuite un calcul normal de lancer de rayons est effectué, non pas sur tous les objets de la scène, mais seulement sur ceux contenus dans les boîtes englobantes coupées successivement par le rayon (figure 1.4).

Bloites englobantes
Fig. 1.4 -- Utilisation des boîtes englobantes dans le lancer de rayons.

Les boîtes englobantes sont bien adaptées aux calculs discrets de visibilité. Cependant leur utilité dans des calculs continus est très limitée. De plus, la construction automatique de ces boîtes, ou plus précisément le regroupement optimal des objets en agrégats, n'est pas une tâche facile et fait toujours l'objet de recherches.

1.2.2 Grilles, grilles récursives

D'autres types de méthodes de découpage sont basées sur la subdivision de l'espace en régions et permettent de se déplacer d'une région à une autre sans considérer toute la scène.

La façon la plus simple de découper automatiquement la scène est d'utiliser une grille régulière. À chaque rectangle de la grille est associée la liste des objets qu'il contient. Lors d'un calcul de lancer de rayons, ne sont considérés que les objets contenus dans les rectangles de la grille coupés successivement par le rayon (figure 1.5). La structure de grille permet d'avoir directement les rectangles coupés par le rayon sans avoir à considérer les autres rectangles : il est en effet possible de passer d'un rectangle à un autre rectangle incident en temps constant.

grille
Fig. 1.5 -- Utilisation d'une grille dans le lancer de rayons.

Dans le cas où les objets de la scène ne sont pas uniformément répartis, il est plus utile d'utiliser des grilles adaptatives qui tiennent compte de la répartition des objets et qui évitent le découpage de régions vides. Ces grilles sont souvent définies de façon récursive.

Dans les arbres quadtree par exemple, une région est subdivisée en quatre, et chacune des sous-régions est elle même subdivisée à son tour en quatre... La subdivision s'arrête quand une région devient vide (figure 1.6a). Ces subdivisions sont représentées sous la forme d'un arbre : chaque région est un noeud de l'arbre et a pour fils ses quatre sous-régions (figure 1.6b). De plus, à chaque région est associée la liste des objets qu'elle contient. Plusieurs méthodes peuvent être employées pour effectuer la subdivision : subdivision régulière, subdivision cherchant à répartir uniformément les objets dans les sous-régions... La structure d'arbre peut être utilisée pour rechercher en temps logarithmique les régions traversées par un rayon dans une requête de lancer de rayons.

quadtree
Fig. 1.6 -- Utilisation d'arbre quadtree dans le lancer de rayons. a. Découpage de la scène. b. Arbre correspondant.

Il existe d'autres types de grilles récursives, comme les kd-arbres qui subdivisent les régions en deux sous-régions selon une direction alternativement parallèle à l'axe des abscisses et à l'axe des ordonnées ; cependant le principe général d'utilisation reste le même (pour plus de détails, voir le survol de Samet [Sa84]).

Ces grilles ont l'avantage par rapport aux boîtes englobantes d'introduire une utilisation de la cohérence spatiale grâce à la possibilité de considérer pour une région donnée ses régions incidentes. Les grilles sont utiles dans le cadre de calculs discrets locaux ou dans le cadre de calculs plus globaux (comme déterminer l'ordre d'affichage des objets dans l'algorithme du peintre). En revanche, elles restent peu adaptées aux calculs continus de visibilité car elles permettent difficilement de calculer des limites de visibilité.

1.2.3 Triangulations

Découper la scène en régions ne signifie pas uniquement découper la scène en régions contenant des groupes d'objets. Le découpage de l'espace libre, le plan auquel on a ôté les objets de la scène, permet aussi d'accélérer les calculs. Un des découpages les plus connus est la triangulation, qui consiste à découper l'espace libre d'une scène polygonale en triangles dont les sommets sont les sommets des polygones de la scène (figure 1.7).

triangulation
Fig. 1.7 -- Triangulation d'un polygone.

Les triangulations servent notamment à résoudre des problèmes de visibilité quand l'espace libre est l'intérieur d'un polygone simple, comme par exemple des problèmes de lancer de rayons, de plus courts chemins ou d'illumination par un néon (voir par exemple [GHL+87]).

Bien qu'il existe un algorithme pour trianguler un polygone simple en temps linéaire, celui-ci est assez compliqué. D'autres découpages utilisant des formes polygonales plus grandes et générant moins de régions ont été étudiés pour résoudre ces problèmes, comme par exemple les profils de visibilité structurés d'Heffernan et Mitchel [HM90] ou les décompositions en trapèzes de Chiang, Preparata et Tamassia [CPT96].

Ces découpages introduisent une plus grande utilisation de la cohérence spatiale&nbso;: les frontières des régions découpées s'appuient sur les côtés des objets. Cependant cela ne suffit pas toujours à réduire la complexité des calculs : un rayon peut traverser un nombre important de régions avant de heurter un des côtés du polygone. Pour éviter ces sauts de complexité, les auteurs greffent sur les structures de découpage des structures de recherche purement combinatoire (fractional cascading, BB(alpha )-trees, etc.) et relativement compliquées afin d'obtenir des complexités intéressantes même dans les cas les pires.


Dernière mise à jour : 26 janvier 1997
© Stéphane Rivière
S.Riviere@univ-mulhouse.fr