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.
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.
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.
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é.
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.