Procédé de détermination de liste d'éléments potentiellement visibles par région pour des scènes 3D de très grandes tailles représentant des villes virtuelles
La présente invention concerne le domaine technique général de l'imagerie de synthèse, et plus particulièrement le domaine de la représentation de scène 3D.
PRESENTATION GENERALE DE L'ART ANTERIEUR
Le but général de l'invention est de proposer un procédé de calcul de visibilité permettant de déterminer des listes d'objets potentiellement visibles par région pour des scènes 3D de très grandes tailles représentant des villes virtuelles. En imagerie de synthèse, le rôle du^ calcul de visibilité est de déterminer quels sont les objets d'une scène 3D qui sont visibles depuis un point et une direction d'observation.
Historiquement le calcul de visibilité a toujours joué un rôle crucial pour des raisons de performance d'affichage des scènes 3D. En effet, lorsqu'une scène 3D est affichée, certaines parties ne sont' pas visibles : les parties situées hors du champ de vue par exemple, ou encore les objets, qui sont cachés par des objets opaques situés devant.
Afin d'accélérer l'affichage d'une scène 3D, il faut donc éviter le dessin inutile de ces parties « cachées ». Ainsi, il est nécessaire d'éliminer le plus tôt possible ces parties des procédés de traitement qui vont générer (dessiner) la scène 3D.
C'est la raison pour laquelle on applique souvent à la scène un prétraitement pour déterminer ce qui sera au final visible dans une vue donnée de celle-ci. Ce prétraitement est un procédé de calcul de visibilité. Il permet d'obtenir une liste des objets de la scène qui seront visibles dans une vue donnée. Seuls les objets de cette liste seront dessinés par les moyens
de traitement et affichés sur les moyens d'affichage, ce qui est plus rapide que de dessiner l'ensemble des objets d'une scène.
De nombreux procédés de calcul de visibilité permettant l'élimination d'objets non visibles ont ainsi été proposés dans les années 70, en particulier le plus célèbre et le plus utilisé est le procédé du z-buffer [3]. Ce procédé particulièrement performant se trouve implémenté sur toutes les cartes accélératrices 3D modernes.
Depuis quelques années, ces procédés de visibilité ont repris de l'intérêt en raison de Ia croissance de la complexité des bases de données 3D qui rend impossible l'utilisation des procédés classiques de type z-buffer.
Dès lors, dans une optique client-serveur temps réel, il devient nécessaire d'utiliser des procédés (off ou on-line) permettant en fonction d'un point ou d'une zone d'observation de rejeter une partie de la scène avant d'utiliser les procédés classiques du type z-buffer permettant le calcul de l'image de synthèse.
Dans les procédés de calcul de visibilité, on différencie les travaux sur la visibilité exacte et les travaux sur la visibilité conservative.
Un procédé de calcul de visibilité exacte a pour objectif de déterminer à une position et une direction d'observation la liste exacte des objets visibles. Cette technique utilise en général une structure appelée un graphe d'aspect.
Un procédé de calcul de visibilité conservative recherche à une position ou à une zone d'observation la plus petite liste d'objets potentiellement visibles que l'on nommera dans la suite LOPV. La liste des objets visibles est incluse dans la liste des objets potentiellement visibles.
Dans la suite on s'intéressera particulièrement aux procédés traitant la visibilité conservative mieux adaptés à la navigation dans les grands environnements de type urbain. En effet, le calcul de visibilité exacte d'une cellule de vue est très complexe, et donc lourd à mettre en oeuvre.
On différencie également les travaux sur la visibilité qui s'effectuent dans l'espace objet 3D de la scène, de ceux qui s'effectuent dans l'espace image discrétisé 2D obtenu par projections des objets 3D de la scène sur le plan image. Pour des raisons de performance, on s'intéressera uniquement à la première catégorie.
Il a déjà été proposé un certain nombre de procédés permettant d'établir des listes d'objets potentiellement visibles afin d'éliminer les objets non visibles. Un premier procédé de calcul de visibilité permettant d'établir des listes d'objets potentiellement visibles est basé sur la technique d'élimination des faces cachées. Cette technique consiste à rejeter les faces des objets dont la normale a un angle compris entre [-Pi/2; Pi/2] avec une direction d'observation donnée [1 , 4, 8, 9, 13, 16]. Un second procédé de calcul de visibilité permettant d'établir des listes d'objets potentiellement visibles est basé sur la technique utilisant la pyramide de vue. Cette technique part de la constatation que tous les objets situés à l'extérieur de cette pyramide à un instant donné sont rejetés lors de la phase de rendu. Plusieurs procédés utilisant des structurations hiérarchiques de la scène ont été couplées à ce procédé.
Un troisième procédé de calcul de visibilité part de la propriété suivante : tester l'occultation de chaque polygone étant trop lent, il est plus efficace d'utiliser des techniques basées sur l'utilisation de structures hiérarchiques de la scène et de volumes englobant [9]. Les trois procédés qui viennent d'être présentés permettent de rejeter une partie de la scène de la phase de rendu 3D.
Cependant, pour des raisons de performance, ces procédés ne sont pas applicables à une utilisation temps réel pour des bases de données trop complexes.
Le procédé de la présente invention est utilisable dans différentes applications 3D, mais est particulièrement adapté aux applications proposant une navigation 3D au niveau du sol.
Dans le cas des applications de navigation urbaine au niveau du sol, la propriété la plus importante est qu'à une position d'observation donnée, seule une très faible partie des bâtiments constituant la scène 3D est visible en raison des occultations inter-bâtiments.
Dans la suite on s'intéressera particulièrement aux différents procédés mettant en œuvre le principe d'occultation inter-objets. Un premier procédé de calcul de visibilité mettant en œuvre le principe d'occultation inter-objets est le procédé de Coord et Teller [5, 6]. Ce procédé est basé sur l'utilisation d'objets occultants convexes de grandes dimensions. Ce procédé détermine des plans d'occultation valides par rapport à un certain déplacement de l'observateur. Plusieurs plans sont définis par rapport à un ensemble de points d'observation. Il existe plusieurs évolutions de ce procédé basées sur différentes structurations de la scène 3D.
D'autres procédés de calcul de visibilité mettant en œuvre Ie principe d'occultation inter-objets ont également été proposés. Ces procédés sont basés sur la propriété des volumes d'occultation (volume d'ombre) [2, 11] générés par un point d'observation et le contour de certains bâtiments occultant le reste de Ia scène.
En effet, à un point d'observation donné, on peut définir un volume d'ombre centré sur le point d'observation et s'appuyant sur le contour d'objets occultants garantissant que tout objet inclus dans ce volume d'ombre ne sera pas visible depuis l'observateur. Plusieurs procédés mixant des structurations de scène et cette propriété ont été proposés. Concernant le choix des objets occultants, plusieurs stratégies dynamiques ou statiques ont également été proposées.
Les procédés ci-dessus présentés calculent la visibilité par rapport à un point d'observation. Cela impose, lors du déplacement de l'utilisateur dans le monde 3D, de recalculer la visibilité à chaque nouvelle position.
Ces procédés sont donc lourds à mettre en œuvre et ne sont pas applicables à une utilisation temps réel pour des bases de données trop complexes.
Une autre approche dans le calcul de visibilité consiste à réaliser une partition de l'espace 3D de navigation et pour chaque élément de la partition, appelé cellule de vue, de calculer la liste des objets potentiellement visibles.
Ainsi, plutôt que de réaliser un calcul de visibilité à chaque position de l'utilisateur, ce calcul de visibilité est réalisé pour des zones, ou cellules de vue, de l'espace 3D. Dans la suite on s'intéressera particulièrement à ce type de procédé de calcul de visibilité permettant de déterminer des listes d'objets potentiellement visibles par région (c'est-à-dire par cellule de vue).
Comme dans le procédé de Coord et Teller on trouve des procédés sélectionnant des objets occultants convexes [15] de grande dimension par rapport à la cellule de vue.
Cependant, la contrainte forte sur le choix des objets occultants pris en compte fait que ces procédés ne sont pas des plus intéressants dans les cas réels.
Un autre procédé est proposé par Durand et Al. Ce procédé [7, 10, 14, 19] teste la non visibilité d'objets en projetant les objets occultants et les objets sur un plan 2D et en vérifiant l'inclusion des objets projetés sur les projections des objets occultants.
Cependant, ce procédé est difficile à mettre en œuvre en raison de l'importance du choix des plans de projections et des objets occultants pris en compte.
On peut également citer un procédé [12] calculant dynamiquement des objets occultants virtuels. L'intérêt de ce type de procédé est de prendre en compte la fusion de volumes d'ombre des objets occultants.
Récemment Peter Wonka [17, 18] a proposé un procédé de calcul de visibilité très prometteur qui utilise les caractéristiques du z-buffer câblé des cartes modernes.
Ce procédé suppose que la base de données urbaine est plane et que chaque bâtiment est représenté par un modèle 2DVa, à savoir une empreinte au sol, une altitude et une hauteur. Le bâtiment 3D se déduit du modèle 2DYz par élévation d'un prisme sur l'empreinte au sol. Le procédé de Peter Wonka comprend différentes étapes :
- une première étape consiste à réaliser une partition de l'espace navigable en cellule de vue,
- une seconde étape consiste à calculer des hauteurs minimales visibles afin de déterminer une carte des hauteurs minimales visibles par rapport à chaque cellule de vue, et
- une troisième étape consiste à tester la visibilité des objets de la scène par rapport à chaque cellule de vue en fonction de la carte des hauteurs minimales visibles de la cellule de vue.
Le calcul de la carte des hauteurs minimales visibles garantit qu'un objet ne sera pas visible depuis une cellule de vue si sa hauteur est inférieure aux hauteurs minimales visibles de la région où il se situe. Cette carte est obtenue par un quadrillage de la surface occupée par l'environnement urbain et contenant pour chaque rectangle r Ia hauteur minimale visible Hmin(r)dans tout le rectangle par rapport à la cellule de vue. Un objet entièrement inclus dans un rectangle r et de hauteur inférieure à
Hmin(r) ne sera donc pas vu depuis la cellule de vue. Cette carte est représentée à l'aide d'une matrice 2D et est appelée matrice de visibilité. Dans la suite, les rectangles seront appelés pixels en raison de l'utilisation de techniques d'imagerie graphique 3D pour accélérer le traitement. Le calcul de la carte des hauteurs minimales visibles utilise les ressources des cartes graphiques 3D et lie la dimension de la zone 2D de calcul des hauteurs minimales visibles au nombre de pixels de la carte graphiques 3D et à la surface recouverte par un pixel.
Par exemple pour une carte graphique de [1024, 768] pixels et une valeur de recouvrement de 1 mètre, on obtient une zone 2D de calcul des hauteurs minimales visibles de 1024*768 mètres carrés. Donc la carte des
hauteurs minimales visibles recouvrira 1024*768 mètres carrés de la scène urbaine 3D.
Lors du calcul de la carte des hauteurs minimales visibles, le procédé impose de réduire les objets occultants d'une valeur d'érosion notée « e » afin de limiter les erreurs liées à la méthode utilisée pour calculer les hauteurs minimales visibles de ladite carte. En raison de la modélisation
2D1/4 des bâtiments, l'opération d'érosion est réalisée sur l'empreinte au soi des bâtiments. La valeur d'érosion e (correspondant à l'amplitude d'érosion) est liée à la valeur de recouvrement (correspondant à la taille maximale d'un pixel) notée k par la relation suivante : e ≥k / «J2.
En pratique pour prendre en compte les phénomènes d'occultation, la valeur d'érosion doit être faible.
En effet, si la valeur d'érosion est forte, les objets occultants seront trop érodés ou réduits, et donc les phénomènes d'occultation ne seront pas pris en compte.
Le test de la visibilité des objets de la scène par rapport à chaque cellule de vue est illustré à la figure 1. Ce test est réalisé en fonction de la carte des hauteurs minimales visibles 1 de la cellule de vue 2.
Pour les objets contenus dans la zone recouverte par la carte des hauteurs minimales visibles 1 , le test de visibilité se fait par comparaison entre la hauteur de la boîte englobante de l'objet et les hauteurs minimales visibles des pixels ayant une intersection avec l'empreinte au sol de l'objet.
Pour les objets qui se trouvent en dehors la zone recouverte par la carte des hauteurs minimales visibles, Wonka propose la modification suivante de son procédé : les frontières de la carte des hauteurs minimales visibles permettent de définir l'horizon de visibilité 4. Cette ligne d'horizon 4 nous assure que tout objet 3 extérieur à la région recouverte par la carte des hauteurs minimales visibles 1 et dont la projection 5 est sous la ligne d'horizon 4 n'est pas vu depuis la cellule de vue.
Le procédé de Peter Wonka ne gère donc pas l'occultation inter¬ bâtiment qui se situe à l'extérieur de la zone de recouvrement, c'est-à-dire à l'extérieur de la zone recouverte par la carte des hauteurs minimales visibles.
Le procédé de Wonka présente les inconvénients suivants : i. La zone de recouyrement de la carte des hauteurs minimum visibles ne couyre qu'une partie de la ville.
En effet, pour ne pas trop réduire les façades des bâtiments occultants, e est en général égale à un mètre, ce qui impose que la valeur de recouvrement d'un pixel (k) soit inférieure ou égale à yβ mètre. En effet, les valeurs k et e sont liées par la relation e >k I sβ.
Donc si on suppose une valeur d'érosion e égale à un mètre et une carte graphique de 1280*1024 pixels, alors la carte des hauteurs minimales visibles recouvrira au maximum 1817*1454 mètres carrés, or dans les cas réels, les villes sont de l'ordre 8km*8km. Pour, recouvrir une zone plus grande il faut augmenter la valeur de k, ce qui implique une augmentation de l'amplitude d'érosion. Par exemple pour k égal à 21 ^fI, e doit être supérieure ou égale à 2 mètres.
Dès lors, plus la valeur de e est grande et plus les façades occultantes seront réduites et donc moins le phénomène d'occultation sera pris en compte. Par exemple, une amplitude d'érosion de 2 mètres enlève 4 mètres par façade de bâtiment. ii. Le procédé de Wonka ne prend pas en compte l'occultation inter¬ bâtiment sur toute la base de donnée urbaine.
En effet, comme précédemment décrit, l'occultation inter-bâtiment n'est pas prise en compte en dehors de la zone recouverte par la carte des hauteurs minimales visibles, iii. L'opération d'érosion engendre de la visibilité.
En effet un des inconvénients de l'opération d'érosion est que cette opération mathématique engendre de la visibilité entre les bâtiments ayant au moins une arrête en commun, même si cette visibilité n'existe pas dans la base de donnée initiale.
Ainsi, comme représenté à la figure 2, un objet 6 qui est situé, par rapport à la cellule de vue courante, derrière deux bâtiments 7 et 8 ayant une arrête 9 en commun, et qui est non visible avant l'opération d'érosion (étape 10) deviendra visible après l'opération d'érosion (étape 11 ). iv. La taille de la liste des objets potentiellement visibles augmente de façon exponentielle en prenant des bases de données urbaines de taille croissante.
En effet, l'occultation inter-bâtiment n'est pas prise en compte à l'extérieur de la zone recouverte par la carte des hauteurs minimales visibles. Ainsi, tout objet 3 situé en dehors de la zone recouverte par la carte 1 , et dont la projection 5 sur l'horizon de visibilité 4 a une hauteur supérieure aux hauteurs minimales visibles sera considéré comme potentiellement visible. Or, celui-ci peut être caché par un autre bâtiment situé à l'extérieur de la zone recouverte par la carte 1. Par exemple, si on suppose, comme illustré à la figure 3, quatre bâtiments 12, 13, 14, 15 de même largeur et un point d'observation 18 alignés selon une direction d'observation, les hauteurs des bâtiments 12, 13, 14, 15 étant respectivement de 5, 25, 20 et 10 mètres du plus proche au plus éloigné du point d'observation 18. Si on suppose également que ces quatre bâtiments 12, 13, 14, 15 sont situés à l'extérieur de la zone 16 recouverte par la carte 1 , et que la hauteur de l'horizon de visibilité 17 est de 6 mètres.
Alors le bâtiment 12 (de 5 mètre) le plus proche du point de vue sera considéré comme caché, et les trois bâtiments 13, 14, 15 suivants (de 25, 20 et 10 mètres) seront considérés comme potentiellement visibles, leurs projections sur l'horizon de visibilité 17 ayant des hauteurs supérieures à la hauteur de l'horizon de visibilité 17 (6 mètres).
Ces trois bâtiments 13, 14, 15 feront donc partie de la liste des objets potentiellement visibles bien que deux d'entre eux ne soient pas visibles (les bâtiments 14, 15 de 20 et 10 mètres étant cachés par le bâtiment 13 de 25 mètres).
Un but de la présente invention est de fournir un procédé de détermination de liste d'objets potentiellement visibles par région pour des scènes 3D de très grandes tailles représentant des villes virtuelles permettant de pallier la plupart des inconvénients précités.
PRESENTATION DE L'INVENTION
L'invention concerne un procédé de détermination de listes d'objets potentiellement visibles dans une scène 3D comprenant des objets sur un terrain, et dans laquelle un utilisateur est susceptible de se déplacer virtuellement sur une zone de déplacement correspondant à l'ensemble des zones du terrain non recouvertes par les objets, caractérisé en ce qu'il comprend les étapes consistant à :
- partitionner la zone de déplacement de l'utilisateur en un réseau de prismes de partition,
Puis pour chaque prisme de partition :
- calculer une première carte de hauteurs minimales visibles, ladite carte étant obtenue en : o effectuant un quadrillage du terrain en N rectangles, la surface occupée par chaque rectangle étant fonction d'une valeur de recouvrement k1 choisie de sorte que le quadrillage recouvre tout le terrain, o sélectionnant des faces occultantes d'objets occultants et en érodant les faces occultantes sélectionnées par une valeur d'érosion e1 proportionnelle à la valeur de recouvrement k1 , o calculant, pour chaque rectangle, la hauteur minimale visible depuis le prisme de partition,
- déterminer une première liste d'objets potentiellement visibles en effectuant un test de visibilité des objets de la scène à l'aide de la première carte des hauteurs minimales visibles,
- calculer une deuxième carte des hauteurs minimales visibles, ladite carte étant obtenue en : o effectuant un quadrillage en N rectangles d'une partie du terrain, ladite partie incluant la base du prisme de partition et la surface occupée par chaque rectangle étant fonction d'une valeur de recouvrement k2 inférieure à k1 , o sélectionnant les faces occultantes des objets occultants et en érodant les faces occultantes sélectionnées par une valeur d'érosion e2 proportionnelle à la valeur de recouvrement k2, o calculant pour chaque rectangle la hauteur minimale visible depuis le prisme de partition,
- déterminer une deuxième liste d'objets potentiellement visibles en effectuant un test de visibilité des objets de la première liste d'objets potentiellement visibles à l'aide de la deuxième carte des hauteurs minimales visibles.
La présente invention permet ainsi de traiter de façon efficace les bases de données urbaines de taille réelle.
Elle se décompose en deux phases. Lors de la première phase, l'utilisation de la carte des hauteurs minimales visibles sur toute la ville permet de prendre en compte les phénomènes d'occultation inter-bâtiment sur toute la base de donnée urbaine. La deuxième phase de la nouvelle méthode prend en compte plus finement les phénomènes d'occultation inter¬ bâtiment proche de l'observateur.
Par ailleurs, le procédé de la présente invention est totalement indépendant des ressources mémoire (du système sur lequel il est mis en œuvre) par rapport à la taille des bases puisque la taille des rectangles du quadrillage est adaptée (par l'intermédiaire de la valeur de recouvrement) suivant les ressources mémoire disponible pour le calcul de la carte des hauteurs minimales visibles. Certains procédés de calcul de visibilité peuvent être très efficaces mais ils nécessitent un stockage en mémoire local d'une structure de données décrivant l'intégralité de la scène. Ce n'est pas le cas
du procédé de la présente invention puisque la seule structure de donnée qui doit être en mémoire vive est la matrice de visibilité (ou carte des hauteurs minimales visibles) dont la taille est fixée à l'avance, indépendamment de la taille de l'environnement urbain à traiter. De plus, cette structure de données est stockée dans la mémoire de la carte graphique et non dans la mémoire centrale de l'ordinateur.
Des aspects préférés, mais non limitatifs, du procédé de calcul de visibilité selon l'invention sont les suivants : les objets de la scène sont représentés par un modèle 2D1/4, et sont définis par une altitude, une hauteur, et une empreinte comprenant un ensemble de points ; le procédé comprend en outre une étape de fusion des objets connexes afin d'obtenir des ensembles d'objets connexes afin d'obtenir des ensembles d'objets connexes, ladite étape de fusion étant réalisée préalablement à l'étape de sélection des faces occultantes ;
La visibilité engendrée par l'érosion des façades occultantes est ici compensée par l'érosion des bâtiments fusionnés ce qui permet de réduire la taille des listes d'objets potentiellement visibles et donc d'être plus précis. - l'étape de fusion des objets connexes comprend les étapes consistant à :
- déterminer des ensembles d'objets vérifiant des conditions de connexité,
Puis pour chaque ensemble d'objets connexes : - supprimer des empreintes des objets les arrêtes qu'elles ont en commun afin d'obtenir une empreinte unique représentant l'ensemble d'objets connexes,
- déterminer, parmi les objets de l'ensemble, celui dont la hauteur est la plus petite et assigner sa hauteur à l'ensemble d'objets connexes ;
les conditions de connexité à vérifier par deux objets pour qu'ils soient connexes sont que leurs empreintes aient au moins deux sommets consécutifs en commun ; la valeur de recouvrement k1 est calculée en utilisant la relation : 5 k1 ≥max (Δx/Nx, Δy/Ny).
Où :
- Δx et Δy sont la largeur et la longueur du terrain,
- Nx, Ny sont le nombre de rectangles utilisables en ligne et en colonne pour la carte des hauteurs minimales visibles,
10 de sorte que la valeur de recouvrement k1 est supérieure ou égale au maximum entre le rapport de la largeur du terrain sur le nombre de
- rectangles utilisables en ligne, et le rapport de longueur du terrain sur le nombre de rectangles utilisables en colonne, la valeur d'érosion e1 étant déduite du calcul précédent en utilisant la relation liant la valeur
15 d'érosion el à la valeur de recouvrement k1 : el >k1/v2.
la valeur d'érosion e2 est choisie sensiblement égale à 1 mètre, la valeur de recouvrement k2 étant déduite de la valeur de la valeur
20 d'érosion e2 en utilisant la relation liant la valeur d'érosion e2 à la valeur de recouvrement k2 : e2.≥k2Λ£. l'étape consistant à partitionner la zone de déplacement de l'utilisateur en un réseau de prismes de partition comprend les sous étapes
25 consistant à :
- partager la zone de déplacement de l'utilisateur en un réseau de triangles,
- extruder un prisme sur chaque triangle obtenu précédemment ; l'étape consistant à éroder les faces occultantes des objets occultants
30. par une valeur d'érosion e consiste à éroder les empreintes au sol des objets par la valeur d'érosion e ; ' . .
l'étape consistant à sélectionner les faces occultantes des objets occultants comprend la sélection des faces occultantes des objets occultants ainsi que la sélection des faces occultantes des ensembles d'objets connexes), lesdits objets et ensembles d'objets connexes constituant les objets occultants ; le test de visibilité sur chaque objet de la scène consiste à comparer la hauteur d'une boîte englobante de l'objet et les hauteurs minimales visibles des rectangles de la carte des hauteurs minimales visibles ayant une intersection avec l'empreinte de l'objet ; L'invention concerne également un système apte à déterminer des listes d'objets potentiellement visibles dans une scène 3D comprenant des objets sur un terrain et dans laquelle un utilisateur est susceptible de se déplacer virtuellement sur une zone de déplacement correspondant à l'ensemble des zones du terrain non recouvertes par les objets, caractérisé en ce qu'il comprend :
- des moyens aptes à partitionner la zone de déplacement de l'utilisateur en un réseau de prismes de partition,
- des moyens aptes à calculer une première carte de hauteurs minimales visibles, lesdits moyens comprenant : o des moyens aptes à effectuer un quadrillage du terrain en N rectangles, les dimensions des rectangles étant fonction d'une valeur de recouvrement k1 choisie de sorte que le quadrillage recouvre toute la surface occupée par la scène, o des moyens aptes à sélectionner des faces occultantes d'objets occultants et des moyens aptes à éroder les faces occultantes sélectionnées par une valeur d'érosion e1 proportionnelle à la valeur de recouvrement k1 , o des moyens aptes à calculer pour chaque rectangle la hauteur minimale visible depuis le prisme de partition, - des moyens aptes à déterminer une première liste d'objets potentiellement visibles en effectuant un test de visibilité des objets
de la scène à l'aide de la première carte des hauteurs minimales visibles,
- des moyens aptes à calculer une deuxième carte des hauteurs minimales visibles, lesdits moyens comprenant : o des moyens aptes à effectuer un quadrillage, en N rectangles, d'une partie du terrain, ladite partie incluant la base du prisme de partition et les dimensions des rectangles étant fonction d'une valeur de recouvrement k2 inférieure à k1 , o des moyens aptes à sélectionner les faces occultantes des , objets occultants et des moyens aptes à éroder les faces occultantes sélectionnées par une valeur d'érosion ei proportionnelle à la valeur de recouvrement k2, o des moyens aptes à calculer pour chaque rectangle la hauteur minimale visible depuis le prisme de partition, - des moyens aptes à déterminer une deuxième liste d'objets potentiellement visibles en effectuant un test de visibilité des objets de la première liste d'objets potentiellement visibles à l'aide de la deuxième carte des hauteurs minimales visibles. Ce système comprend en outre des moyens aptes à mettre en oeuvre le procédé décrit ci-dessus.
PRESENTATION DES FIGURES
D'autres caractéristiques, buts et avantages de la présente invention ressortiront encore de la description qui suit, laquelle est purement illustrative et non limitative et doit être lue en regard des dessins annexés, sur lesquels :
- la figure 1 est une vue en perspective illustrant un test de visibilité du procédé de Peter Wonka appliqué à un objet d'une scène, l'objet étant situé à l'extérieur de la zone couverte par la carte des hauteurs minimales visibles ;
- la figure 2 est une vue de face de trois bâtiments avant et après une opération d'érosion ;
- la figure 3 est une vue de face illustrant le test de visibilité du procédé de Peter Wonka appliqué à quatre objets d'une scène 3D, les quatre objets étant situés à l'extérieur de la zone couverte par la carte des hauteurs minimales visibles ;
- la figure 4 est une vue en perspective d'une scène sur laquelle se trouve ' un utilisateur, ladite scène comprenant une façade occultante d'un objet occultant, un objet visible et un objet non visible ;
- la figure 5 est une vue en perspective d'un objet modélisé 2OΛΛ ;
- la figure 6 est une illustration de l'étape de triangulation et comprend des vues de dessus d'une scène avant et après triangulation, et une vue en perspective d'une cellule de vue obtenue en extrudant un prisme sur une des partitions triangulaire obtenue par triangulation ;
- la figure 7 est une première illustration de l'étape de fusion de bâtiments et comprend une vue de dessus de trois empreintes de bâtiments connexes, et une vue de dessus de l'empreinte du bâtiment résultant de la fusion des trois bâtiments connexes ;
- la figure 8 est une seconde illustration de l'étape de fusion de bâtiments et comprend une vue de face de trois bâtiments connexes, et une vue de face du bâtiment résultant de la fusion des trois bâtiments connexes ; - la figure 9 est une vue de dessus d'une scène sur laquelle se trouve un utilisateur et deux façades occultantes de bâtiments occultants ;
- la figure 10 est une vue en perspective d'une scène 3D sur laquelle est mis en oeuvre le procédé selon la présente invention. - la figure 11 est un organigramme illustrant les différentes étapes du procédé.
DESCRIPTION DE L'INVENTION
Un but de la présente invention est de fournir un procédé de calcul de visibilité permettant de déterminer des listes précises d'objets potentiellement visibles par région pour des scènes 3D de très grande taille représentant des villes virtuelles.
Ainsi, la scène représente une ville virtuelle et les objets de la scène sont des bâtiments. Un but de la présente invention est donc que le procédé de calcul de visibilité permette de traiter de façon efficace des données urbaines de taille réelle de l'ordre de 8km*8km, et permette également d'obtenir des résultats beaucoup plus précis.
Pour cela, les inventeurs sont partis de la constatation qu'au niveau du sol très peu de bâtiments sont visibles en raison de l'occlusion inter-bâtiment. En effet, comme représenté à la figure 4, en un point d'observation 20 situé proche d'une façade 21 , un grand volume 22 de la scène 3D, appelé volume d'ombre, n'est pas visible depuis le point d'observation 20.
Ainsi, un objet 23 inclus strictement dans ce volume d'ombre 22 ne sera pas visible depuis le point d'observation 20. Par conséquent, lors d'une navigation au sol dans une scène urbaine virtuelle, très peu d'objets 19 seront visibles depuis un point d'observation 20.
La détermination d'un sous-ensemble minimal d'objets potentiellement visibles par région est un problème complexe que l'on ne peut résoudre sans hypothèse restrictive. Les hypothèses du procédé sont les suivantes :
- La base de donnée urbaine est composée de bâtiments de même altitude et représentés à l'aide d'un modèle 2 D Vz,
- Les données urbaines sont incluses dans une boîte de dimension (Δx,
Δy) ; - Le nombre de pixels utilisables pour la carte des hauteurs minimales visibles est égal à (Nx, Ny) ;
Le modèle 2D1/2 d'un bâtiment comprend une altitude (nulle par défaut), une empreinte au sol définie par une liste de points, et une hauteur.
A partir de ces informations (empreinte E, altitude A, hauteur H), il est possible, comme illustré à la figure 5, de dessiner un bâtiment 3D en extrudant un prisme 24 à l'altitude A, la base du prisme 24 correspondant à l'empreinte E et la hauteur du prisme étant égale à la hauteur H du bâtiment. Le procédé ci présenté s'appuie donc sur le fait que la plupart des bâtiments d'une scène 3D peuvent être modélisés par des prismes.
La première étape du procédé consiste à réaliser une partition de l'espace d'observation proche du sol en cellules de vue. En effet, le calcul exact des objets visibles depuis un volume 3D est très difficile et très coûteux en temps de calcul et ressources matérielles.
Comme illustré à la figure 6, dans une application de visualisation d'environnements urbains, l'espace 3D 25 dans lequel l'observateur virtuel peut se déplacer est égal au complémentaire de l'union de tous les bâtiments
26, 27, 28, 29.
En raison de la modélisation utilisée pour les bâtiments de la scène
(modélisation 2D1Λ), la partition de la zone de déplacement de l'utilisateur est obtenue très simplement par triangulation 2D du complémentaire des empreintes au sol des bâtiments. Cette triangulation consiste à partager la zone 25 de déplacement de l'utilisateur en un réseau de triangles 30.
, La partition 3D se déduit de la triangulation en extrudant un prisme sur chaque triangle précédemment obtenu. Les prismes ainsi créés constituent les cellules de vue 31. Ensuite, pour chaque cellule de vue, on calcule la liste des objets potentiellement visibles (LOPV). Cette liste résulte d'une évaluation minimaliste de tous les objets visibles depuis au moins un des points de la cellule de vue courante.
Le calcul de la liste des objets potentiellement visibles se décompose en deux phases.
Tout d'abord, une première phase permet de résoudre de façon efficace l'occultation inter-bâtiment lointaine et calcule une première liste d'objets potentiellement visibles pour la cellule de vue courante.
Ensuite une deuxième phase permet de prendre en compte de façon efficace l'occultation inter-bâtiment proche de la cellule de vue courante.
Dans cette deuxième phase, les tests de visibilité se font uniquement sur la liste des objets potentiellement visibles calculée pour la cellule de vue courante dans la première phase.
La première étape de la première phase du calcul de la liste des objets potentiellement visibles consiste à choisir la valeur de recouvrement k1 d'un pixel en fonction des dimensions de la scène.
Afin de pouvoir prendre en compte tous les phénomènes d'occultations inter-bâtiments, on choisit la valeur de recouvrement k1 (définissant la taille d'un pixel) de telle sorte que la carte des hauteurs minimales visibles recouvre toute la ville.
Pour cela la valeur de recouvrement k doit être tel que : k >max(Δx/Nx, Δy/Ny). Où :
- Δx et Δy sont les dimensions de la boîte dans laquelle la surface occupée par la scène est incluse,
- Nx, Ny sont le nombre de pixels utilisables en ligne et en colonne pour la carte des hauteurs minimales visibles.
Connaissant la taille d'un pixel (valeur de recouvrement k1 ), on en déduit la valeur d'érosion el, qui doit être supérieure ou égale à k1Λ/-î. En effet, k et e sont liées par la relation: e >k/v2.
On remarque, que la valeur de l'érosion à appliquer sera grande. Par exemple, si l'on suppose une ville de dimension 8km*8km, et si l'on suppose que l'on dispose d'un moyen de traitement graphique 3D nous permettant d'utiliser 1280*1024 pixels pour le calcul d'une carte des hauteurs minimales visibles. Alors les valeurs de k et e deviennent :
K = max(8000/1280, 8000/1024) = 6.25 mètres e = 6.25/v2 = 4.42 mètres.
La deuxième étape de la première phase du calcul de la liste des objets potentiellement visibles consiste à choisir des façades occultantes d'objets occultants.
Dans son procédé, Peter Wonka considère que l'ensemble des objets occultants se compose de tous les bâtiments de la scène, et choisit comme façades occultantes toutes les façades des bâtiments de la scène.
Contrairement au procédé de Peter Wonka, on considère ici que l'ensemble des objets occultants est constitué de l'ensemble des bâtiments de la scène et d'un ensemble de bâtiments fusionnés.
Ainsi, avec le présent procédé, l'étape consistant à choisir les façades occultantes consiste à prendre les façades de tous les bâtiments et des façades de bâtiments fusionnés. Pour obtenir des ensembles de bâtiments fusionnés, on utilise la méthode de fusion de bâtiments décrite ci-après.
« Soit l'ensemble B de tous les bâtiments, alors on peut réaliser une partition (au sens ensembliste) de tous les bâtiments par le critère de connexité des empreintes au sol suivant : Soit Bi et Bj deux objets de l'ensemble B, alors Bi et Bj sont dits connexes si leurs empreintes au sol ont au moins deux sommets consécutifs en communs. »
De cette définition on déduit une partition de l'ensemble B par sous- ensembles connexes : B = { Uj Bci pour i allant de 1 à N}
Bci est donc un des sous-ensembles de bâtiments connexes, c'est-à- dire dans lesquels deux objets quelconques pris dans un même sous- ensemble Bci appartiennent nécessairement à au moins une composante connexe de Bci. On appellera les Bci « ensembles connexes ».
Soit un ensemble connexe de bâtiments tel que défini précédemment. Alors le résultat de la fusion de tous les bâtiments connexes est un bâtiment défini de la façon suivante :
- son empreinte au sol est le résultat de la fusion des empreintes au sol obtenue par suppression des arrêtes en communs,
- sa hauteur est égale au minimum des hauteurs de toutes les hauteurs de l'ensemble des bâtiments connexes.
En effet, comme représenté à la figure 7, trois bâtiments dont les empreintes au sol 32, 33, 34 ont des arrêtes 35, 36 en commun vont être fusionnés par suppression de leurs arrêtes 35, 36 en commun afin d'obtenir l'empreinte au sol 37 d'un ensemble connexe B1.
Par ailleurs, comme représenté à la figure 8, trois bâtiments 38, 39, 40 ayant des façades 41 , 42 en commun vont être fusionnés par suppression de leurs façades en commun 41 , 42. La hauteur de l'ensemble connexe obtenue par fusion des bâtiments 38, 39, 40 sera égale à la hauteur du bâtiment 38 qui est le moins haut des trois bâtiments 38, 39, 40.
Ainsi, avec le présent procédé, l'étape consistant à choisir les façades occultantes consiste à prendre les façades de tous les bâtiments et les façades des ensembles d'objets connexes. Dans la troisième étape de la première phase du calcul de la liste des objets potentiellement visibles pour la cellule de vue courante, on effectue une opération d'érosion des façades occultantes. Ceci permet de corriger les erreurs liées à la méthode utilisée pour calculer les cartes des hauteurs minimales visibles. Une opération d'érosion mathématique est définie par la propriété suivante:
« A' est dit érodé de A par e si A' est inclus dans A et si pour tout couple de points (a, a') tel que « a' » appartient à A' et « a » appartient à A, la distance de « a' » à « a » est supérieure ou égale à e. » En raison de la modélisation 2D14 des bâtiments, l'érosion par e1 se fait sur l'empreinte au sol des objets.
Cette opération d'érosion va être réalisée sur l'ensemble des façades occultantes des objets occultants, c'est-à-dire sur les façades des bâtiments, mais également sur les façades des ensembles connexes résultant de la fusion des bâtiments connexes. La quatrième étape de la première phase du calcul de la liste des objets potentiellement visibles consiste à calculer la carte des hauteurs minimales visibles pour la cellule de vue courante.
Le calcul de la carte des hauteurs minimales visibles étant un problème difficile et coûteux en temps de calcul, on propose une approximation minimaliste de ce calcul en échantillonnant par des points les arrêtes de la face supérieure de la cellule de vue courante et en calculant la carte des hauteurs minimales visibles en chacun de ces points. Le calcul de la carte associée à la cellule de vue courante se déduit ensuite simplement des cartes associées aux points d'échantillonnage de la cellule de vue courante.
Une première sous-étape lors du calcul de la carte Hmin(r) des hauteurs minimales visibles par rapport à une cellule de vue consiste donc à calculer des cartes Hp(r) des hauteurs minimales visibles en différents points d'échantillonnage « p » de ladite cellule. Pour calculer la carte des hauteurs minimales visibles Hp(r) depuis un point d'observation donné, on définit la notion de volume d'ombre comme suit :
Soit un point 43 d'observation (cf. figure 9) et soit une façade 44 d'un bâtiment modélisée par un rectangle perpendiculaire au sol, alors on appelle volume d'ombre 45 la pyramide tronquée définie par les quatre demi-droites passant par le point d'observation 43 et les quatre sommets de la façade 44. Ce volume d'ombre 45 garantit que tout objet entièrement contenu dans ce volume 3D n'est pas visible depuis le point d'observation 43. La façade 44 est appelée façade occultante. Dès. lors la carte Hp(r) des hauteurs minimales visibles par rapport à un point d'observation « p » se déduit des volumes d'ombres 45, 48 par
projection orthogonale sur la matrice 46 de pixels des volumes d'ombres 45, 48 engendrés par les façades occultantes 44, 47.
Pour déterminer la carte Hp(r) prenant en compte l'ensemble des façades occultantes par rapport à un point d'observation p, on. détermine l'ensemble des cartes Hp,o(r) ne prenant en compte qu'une façade occultante o parmi l'ensemble FO des façades occultantes par rapport au point d'observation p. On en déduit la carte Hp(r).
En effet, la fonction Hp(r) associée à l'ensemble des fonctions Hp,o(r) de toutes les façades occultantes o est donnée par la formule : Hp(r) = max {Hp,o(r), o e FO},
Où :
- Hp(r) est la fonction représentant la hauteur minimale visible d'un pixel r par rapport au point d'observation p,
- Hp,o(r) est la fonction représentant la hauteur minimale visible d'un pixel r par rapport au point d'observation p et en ne prenant en compte que la façade occultante o,
- FO représente l'ensemble des façades occultantes.
Les fonctions Hp,o(r) sont calculées par projections orthogonales des volumes d'ombres sur la matrice de pixels 46. Or la discrétisation sur une grille de pixels engendre des erreurs. C'est la raison pour laquelle on effectue l'opération d'érosion mathématique préalablement au calcul de la carte des hauteurs visibles.
Une fois que toutes les cartes Hp(r) de tous les points d'échantillonnage ont été calculées, on détermine la carte Hmin(r) associée à la cellule de vue courante.
La fonction Hmin(r) donnant les hauteurs minimales visibles associée à une cellule de vue connaissant les fonctions Hp(r) de tous les points d'échantillonnage p est donnée par la formule suivante :
Hmin(r) = min{Hp(r), p e PE}, Où : PE représente l'ensemble des points d'échantillonnage pris sur les arrêtes de la face supérieure de la cellule de vue.
La condition pour que ce calcul soit valide est que l'intervalle d'échantillonnage soit inférieur ou égal à l'amplitude d'érosion e des façades occultantes.
Lorsque l'on a obtenu la carte Hmin(r) des hauteurs minimales visibles associée à la cellule de vue courante, on effectue un test de visibilité sur les objets de la scène 3D afin de déterminer une première liste des objets potentiellement visibles par rapport à ladite cellule.
Le test de visibilité d'un objet consiste en une comparaison entre la hauteur d'une boîte englobante de l'objet et les Hmin(r) des pixels ayant une intersection avec l'empreinte au sol de l'objet.
A la fin de la première phase, on obtient pour chaque cellule de vue une liste des objets potentiellement visibles qui est un sur-ensemble de la liste minimale puisque calculée avec un e1 grand. Lors de la deuxième phase, on ne testera que la visibilité des objets appartenant à liste de visibilité obtenue à Ia première phase.
La deuxième phase du calcul de la liste des objets potentiellement visibles comprend une première étape consistant à choisir une valeur d'érosion e2. Cette valeur d'érosion e2 est choisie faible (en pratique inférieure à 1 mètre) afin de réduire le plus possible le phénomène de réduction des façades occultantes. Une valeur k2 de recouvrement correspondant à la taille des pixels se déduit de la valeur d'érosion e2 par la formule reliant e et k : e ≥VJsl≥.
La deuxième étape de la deuxième phase consiste à choisir les façades occultantes. Dans son procédé, Peter Wonka prend comme façades occultantes toutes les façades des bâtiments. A cet ensemble, le présent procédé ajoute les façades des couples de bâtiments connexes.
Cette opération est un cas particulier de la fusion d'ensembles connexes. Soit un couple de bâtiments connexes, alors on définit leur fusion comme étant le bâtiment défini par :
- son empreinte au sol qui est égal à la fusion des empreintes au sol, avec suppression des arrêtes en communs des deux bâtiments connexes,
- sa hauteur qui est égale au minimum des hauteurs des deux bâtiments connexes.
La troisième étape du procédé consiste à réaliser une érosion des faces occultantes par la valeur d'érosion e2. La méthode employée pour éroder les faces est identique à celle employée dans la première phase
La quatrième étape de la deuxième phase consiste à calculer la carte des hauteurs minimales visibles pour la cellule de vue courante. Ce calcul est effectué de la même manière que lors de la quatrième étape de la première phase. On obtient ainsi la carte des hauteurs minimales visibles pour chaque cellule de vue.
La cinquième étape de la deuxième phase consiste à tester la visibilité sur les objets de la scène afin de déterminer une deuxième liste des objets potentiellement visibles. Ce test est réalisé par rapport à chaque cellule de vue en fonction la deuxième carte des hauteurs minimales visibles associée à ladite cellule. Ce test est réalisé sur les objets de la première liste d'objets potentiellement visibles et est fonction de la distance des objets par rapport à la zone recouverte par la carte des hauteurs minimales visibles.
En effet si l'objet testé a une intersection avec la carte des hauteurs minimales visibles, alors l'objet est dit potentiellement visible si sa hauteur maximale est supérieure à l'une des hauteurs des pixels de la carte ayant une intersection avec l'empreinte au sol de l'objet. En cas contraire le volume englobant de l'objet est projeté (voir figure 1 ) sur l'horizon de visibilité. Si la projection de l'objet se trouve au-dessus de l'horizon de visibilité l'objet est dit potentiellement visible.
Pour chaque cellule de vue, on obtient donc en sortie du procédé la deuxième liste d'objets potentiellement visibles associée à ladite cellule. En résumé, et en référence aux figures 10 et 11 , le procédé de calcul de visibilité permettant de déterminer des listes d'objets potentiellement
visibles par région pour des scènes 3D de très grandes tailles représentant des villes virtuelles comprend les étapes suivantes : a) La partition de la zone de déplacement 250 de l'utilisateur (étape 70 de la figure 11 ). Cette partition est obtenue par élévation de prismes sur chaque triangle produits par triangulation du complémentaire des empreintes au sol des bâtiments. b) La sélection d'une cellule de vue 202 (étape 71 de la figure 11 ). c) Le calcul de la taille d'un pixel (k1 ) et de la valeur d'érosion (e1 ) (étape 72 de la figure 11 ).
K1 est calculé de telle sorte que la carte des hauteurs minimales visibles recouvre toute la ville. La valeur d'érosion e1 se déduit de la taille d'un pixel. d) La sélection et l'érosion des façades occultantes (203, 204, 205, 206) (étape 73 de la figure 11 ). Aux façades de tous les bâtiments, on rajoute les façades des fusions de tous les bâtiments connexes. e) Le calcul de la carte des hauteurs minimales visibles Hmin1(r) associée à la cellule de vue courante (étape 74 de la figure 11 ).
Le calcul se fait par l'opération d'union et d'intersection des volumes d'ombres générés par les façades occultantes et les points échantillonnés de la cellule de vue 202. Le calcul se fait à l'aide des fonctions câblées des cartes graphiques 3D accessibles par la bibliothèque graphique OpenGL. f) La recherche des objets potentiellement visibles (étape 75 de la figure 11 ). Le test de visibilité des objets 200 est le suivant : un objet 200 est dit potentiellement visible si sa hauteur maximale est supérieure à l'une des hauteurs de la carte des hauteurs minimales visibles des pixels ayant une intersection avec l'empreinte au sol de l'objet.
• g) Le choix d'une valeur faible d'érosion e2 et la déduction de la taille d'un pixel k2 (étape 76 de la figure 11 ).
En pratique la valeur d'érosion e1 est inférieure à 1 mètre
h) La sélection et érosion des façades occultantes (étape 77 de la figure 11 ).
Aux façades de tous les bâtiments, on rajoute les façades issues des fusions des couples de bâtiments connexes. i) Le calcul de la carte des hauteurs minimales visibles Hmin2(r) associée à la cellule de vue 202 courante (étape 78 de la figure 11). Le calcul se fait par l'opération d'union et d'intersection des volumes d'ombres générés par les façades occultantes et les points échantillonnés de la cellule de vue. Le calcul se fait à l'aide des fonctions câblées des cartes graphiques 3D accessibles par la bibliothèque graphique OpenGL. j) La recherche des objets potentiellement visibles (étape 79 de la figure 11 ).
Le test de visibilité ne se fait que sur les objets obtenus à l'étape f) en fonction de la distance des objets par rapport à la zone recouverte par la carte des hauteurs minimales visibles. En effet, si un objet a une intersection avec la zone de la carte, alors l'objet est dit potentiellement visible si sa hauteur maxi est supérieure à l'une des hauteurs de la matrice de visibilité des pixels ayant une intersection avec l'empreinte au sol de l'objet. En cas contraire le volume englobant de l'objet est projeté sur l'horizon de visibilité. Si la projection de l'objet se trouve au-dessus de l'horizon de visibilité l'objet est dit potentiellement visible.
Il est à noter que les opérations b) à j) sont itérées pour toutes les cellules de vues.
Le procédé présenté ci-dessus peut être mis en œuvre dans un système permettant de réaliser les calculs de visibilité.
Ce système est par exemple un ordinateur personnel comprenant des moyens mémoires (RAM, ROM) connectés à des moyens de traitement tels qu'un processeur, des moyens de visualisation tels qu'un écran d'affichage et des moyens de saisie tels qu'un clavier et une souris. Ce système peut également être un serveur Internet. Dans ce cas, le serveur permet de déterminer les listes d'objets potentiellement visibles, et
les transmet en ligne par exemple sur un ordinateur personnel distant qui affichera la scène 3D.
REFERENCES
[I] UIf Assarsson and Thomas Mller. Optimized view frustum culling algorithms for bounding boxes
[2] J. Bittner, V. Havran, and P. Slavik. Hierarchical visibility culling with occlusion trees. [3] Edwin E. Catmull. A subdivision Algorithm for Computer Display of curved
Surfaces.
[4] J. H. Clark. Hierarchical géométrie models for visible surface algorithms
[5] Satyan Coorg and Seth Teller. Temporally cohérent conservative visibility
[6] Satyan Coorg and Seth Teller. Real-Time occlusion culling for models with large occluders
[7] Frédo Durand, George Drettakis, Joëlle Thollt and Claude Puech.
Conservative visibility preprocessing using extended projections
[8] James D. Foley, Andries van Dam, Steven K. Feiner, and John F.
Hughes. Computer Graphics, Principles'and Pratice Second Edition [9] B. Garlick, D. Baum and J. Winget. Parallel Algorithms and Architectures for 3D Image Gegeration
[10] Ned Greene, M. Kass and Gary Miller. Hierarchical z-buffer visibility
[I I] T. Hudson, D. Manocha, J. Cohen, M. Lin, K. Hoff and H. Zhang. Accelerated occlusion culling using shadow frustra. [12] Vladelen Koltun, Yiorgos Chrysanthou, and Daniel Cohen-Or. Virtual occluders: An efficient pvs représentation
[13] Subodh Kumar, Dinesh Manocha, William Garrett, and Ming Lin.
Hierarchical back-face computation
[14] Hong Lip Lim. Toward a fuzzy hidden surface algorithm. [15] Boaz Nadler, Gadi Fibich, Shuly Lev-Yehudi, and Daniel Cohen-Or. A qualitative and quantitative visibility analysis in urban scènes
[16] M. Slater and Y. Chrysanthou. View volume culling using a probabilistic cashing scheme
[17] Peter Wonka and Dieter Schmalstieg. Occluder shadows for fast walkthroughs of urban environnements
[18] Peter Wonka, Michael Wimmer and Dieter Schmalstieg. Visibility preporecessing with occluder fusion for urban walkthroughs
[19] Hanson Zhang, Dinesh Manocha, Thomas Hudson, and Kenneth E. Hoff
III. Visibility culling using hierachical occlusion maps