+

WO2006003267A1 - Procede de determination de liste d’elements potentiellement visibles par region pour des scenes 3d de tres grandes tailles representant des villes virtuelles - Google Patents

Procede de determination de liste d’elements potentiellement visibles par region pour des scenes 3d de tres grandes tailles representant des villes virtuelles Download PDF

Info

Publication number
WO2006003267A1
WO2006003267A1 PCT/FR2004/001370 FR2004001370W WO2006003267A1 WO 2006003267 A1 WO2006003267 A1 WO 2006003267A1 FR 2004001370 W FR2004001370 W FR 2004001370W WO 2006003267 A1 WO2006003267 A1 WO 2006003267A1
Authority
WO
WIPO (PCT)
Prior art keywords
objects
visible
blackout
map
value
Prior art date
Application number
PCT/FR2004/001370
Other languages
English (en)
Inventor
Loïc BOUGET
Christian Bouville
Alexandre Cotarmanac'h
Original Assignee
France Telecom
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by France Telecom filed Critical France Telecom
Priority to PCT/FR2004/001370 priority Critical patent/WO2006003267A1/fr
Publication of WO2006003267A1 publication Critical patent/WO2006003267A1/fr

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T15/00—3D [Three Dimensional] image rendering
    • G06T15/10—Geometric effects
    • G06T15/40—Hidden part removal

Definitions

  • the present invention relates to the general technical field of synthetic imaging, and more particularly to the field of 3D scene representation.
  • the general object of the invention is to propose a visibility calculation method making it possible to determine lists of potentially visible objects by region for very large 3D scenes representing virtual cities.
  • the role of visibility calculation is to determine which objects in a 3D scene are visible from a point and an observation direction.
  • This preprocessing is a visibility calculation method. It makes it possible to obtain a list of the objects of the scene which will be visible in a given view. Only the objects of this list will be drawn by the means processing and displayed on the display means, which is faster than drawing all the objects of a scene.
  • An exact visibility calculation method aims to determine at an observation position and direction the exact list of visible objects. This technique generally uses a structure called an aspect graph.
  • a conservative visibility calculation method searches at a position or an observation area for the smallest list of potentially visible objects that will be called LOPV below.
  • the list of visible objects is included in the list of potentially visible objects.
  • a number of methods have already been proposed for establishing lists of potentially visible objects in order to eliminate non-visible objects.
  • a first visibility calculation method allowing lists of potentially visible objects to be established is based on the technique of eliminating hidden faces. This technique consists in rejecting the faces of objects whose normal has an angle between [-Pi / 2; Pi / 2] with a given direction of observation [1, 4, 8, 9, 13, 16].
  • a second visibility calculation method for establishing lists of potentially visible objects is based on the technique using the view pyramid. This technique starts from the observation that all the objects located outside this pyramid at a given time are rejected during the rendering phase.
  • Several methods using hierarchical structures of the scene have been coupled to this method.
  • a third visibility calculation method starts from the following property: since the screening of each polygon is too slow, it is more efficient to use techniques based on the use of hierarchical structures of the scene and of encompassing volumes [9 ]. The three processes which have just been presented allow to reject part of the scene from the 3D rendering phase.
  • the method of the present invention can be used in different 3D applications, but is particularly suitable for applications offering 3D navigation at ground level.
  • a first visibility calculation method implementing the inter-object occultation principle is the Coord and Teller method [5, 6]. This process is based on the use of large convex blackout objects. This process determines valid occultation plans in relation to a certain displacement of the observer. Several planes are defined in relation to a set of observation points. There are several evolutions of this process based on different structuring of the 3D scene.
  • Another approach in calculating visibility consists in making a partition of the 3D navigation space and for each element of the partition, called view cell, calculating the list of potentially visible objects.
  • this visibility calculation is carried out for areas, or view cells, of the 3D space.
  • this type of visibility calculation method making it possible to determine lists of potentially visible objects by region (that is to say by view cell).
  • Peter Wonka [17, 18] proposed a very promising visibility calculation method which uses the characteristics of the wired z-buffer of modern cards. This process assumes that the urban database is flat and that each building is represented by a 2DVa model, namely a footprint, an altitude and a height. The 3D building is deduced from the 2DYz model by elevation of a prism on the footprint. Peter Wonka's process includes different stages:
  • a first step consists in making a partition of the navigable space into a view cell
  • a second step consists in calculating minimum visible heights in order to determine a map of the minimum visible heights with respect to each view cell, and
  • a third step consists in testing the visibility of the objects of the scene with respect to each view cell as a function of the map of the minimum heights visible from the view cell.
  • Calculating the map of minimum visible heights ensures that an object will not be visible from a view cell if its height is less than the minimum visible heights of the region where it is located.
  • This map is obtained by a grid of the surface occupied by the urban environment and containing for each rectangle r Ia minimum visible height Hmin (r) throughout the rectangle relative to the view cell.
  • Hmin (r) will therefore not be seen from the view cell.
  • This map is represented using a 2D matrix and is called the visibility matrix.
  • the rectangles will be called pixels because of the use of 3D graphic imaging techniques to speed up the processing.
  • the calculation of the minimum visible height map uses the resources of 3D graphic cards and links the dimension of the 2D area for calculating the minimum visible height to the number of pixels of the 3D graphic card and to the surface covered by a pixel.
  • the method When calculating the map of minimum visible heights, the method requires reducing the blackout objects with an erosion value denoted “e” in order to limit the errors linked to the method used to calculate the minimum visible heights of said map. Due to modeling
  • the erosion operation is carried out on the buildings' footprint.
  • the value of erosion e (corresponding to the amplitude of erosion) is linked to the value of overlap (corresponding to the maximum size of a pixel) noted k by the following relation: e ⁇ k / "J2.
  • the erosion value In practice to take into account the occultation phenomena, the erosion value must be low.
  • FIG. 1 The test of the visibility of the objects of the scene with respect to each view cell is illustrated in FIG. 1. This test is carried out according to the map of the minimum visible heights 1 of the view cell 2.
  • the visibility test is carried out by comparison between the height of the bounding box of the object and the minimum visible heights of the pixels having an intersection with the imprint on the ground of the object.
  • Wonka proposes the following modification of its process: the borders of the map of visible minimum heights make it possible to define the horizon of visibility 4.
  • This line d horizon 4 assures us that any object 3 outside the region covered by the map of the minimum visible heights 1 and whose projection 5 is below the horizon line 4 is not seen from the view cell.
  • Peter Wonka's process therefore does not manage the inter-building concealment which is located outside the overlap area, that is to say outside the area covered by the map of the minimum visible heights. .
  • the Wonka process has the following disadvantages: i.
  • the overlap area of the minimum visible height map covers only part of the city.
  • e is generally equal to one meter, which means that the recovery value of a pixel (k) must be less than or equal to y ⁇ meter.
  • the values k and e are linked by the relation e> k I s ⁇ .
  • inter-building concealment is not taken into account outside the area covered by the map of the minimum visible heights, iii.
  • the erosion operation generates visibility.
  • one of the drawbacks of the erosion operation is that this mathematical operation generates visibility between buildings having at least one edge in common, even if this visibility does not exist in the initial database.
  • an object 6 which is situated, relative to the current sight cell, behind two buildings 7 and 8 having a stop 9 in common, and which is not visible before the erosion operation (step 10) will become visible after the erosion operation (step 11).
  • the size of the list of potentially visible objects increases exponentially by taking urban databases of increasing size.
  • any object 3 located outside the area covered by the map 1, and whose projection 5 on the visibility horizon 4 has a height greater than the minimum visible heights will be considered as potentially visible. However, it can be hidden by another building located outside the area covered by the card 1. For example, if we assume, as illustrated in Figure 3, four buildings 12, 13, 14, 15 of same width and an observation point 18 aligned in an observation direction, the heights of the buildings 12, 13, 14, 15 being respectively 5, 25, 20 and 10 meters from the closest to the furthest from the observation point 18. If it is also assumed that these four buildings 12, 13, 14, 15 are located outside the area 16 covered by the map 1, and that the height of the visibility horizon 17 is 6 meters.
  • building 12 (5 meters) closest to the point of view will be considered hidden, and the following three buildings 13, 14, 15 (25, 20 and 10 meters) will be considered potentially visible, their projections on the visibility horizon 17 having heights greater than the height of visibility horizon 17 (6 meters).
  • An object of the present invention is to provide a method for determining a list of potentially visible objects by region for very large 3D scenes representing virtual cities which makes it possible to overcome most of the above-mentioned drawbacks.
  • the invention relates to a method for determining lists of potentially visible objects in a 3D scene comprising objects on a terrain, and in which a user is able to move virtually over a displacement zone corresponding to all of the zones of the land not covered by the objects, characterized in that it comprises the stages consisting in:
  • the present invention thus makes it possible to efficiently process real-size urban databases.
  • the second phase of the new method takes into account more closely the occultation phenomena between buildings close to the observer.
  • the method of the present invention is completely independent of the memory resources (of the system on which it is implemented) with respect to the size of the bases since the size of the rectangles of the grid is adapted (via the value depending on the memory resources available for calculating the map of the minimum visible heights.
  • Certain visibility calculation methods can be very effective, but they require storage in local memory of a data structure describing the entire scene. This is not the case of the method of the present invention since the only data structure which must be in random access memory is the visibility matrix (or map of the minimum visible heights) whose size is fixed in advance, regardless of the size of the urban environment treat.
  • this data structure is stored in the memory of the graphics card and not in the main memory of the computer.
  • the objects of the scene are represented by a 2D 1/4 model, and are defined by an altitude, a height, and a footprint comprising a set of points; the method further comprises a step of merging related objects in order to obtain sets of related objects in order to obtain sets of related objects, said merging step being carried out prior to the step of selecting the blackout faces;
  • the step of merging related objects includes the steps of:
  • Ny are the number of rectangles that can be used online and in column for the map of the minimum visible heights
  • the erosion value e2 is chosen to be substantially equal to 1 meter, the overlap value k2 being deducted from the value of the value
  • the step of partitioning the user movement area into a network of partition prisms includes the sub steps
  • an erosion value e consists in eroding the footprints of objects on the ground by the erosion value e; ' . . the step of selecting the blackout faces of the blackout objects includes selecting the blackout faces of the blackout objects as well as selecting the blackout faces of sets of related objects), said objects and sets of related objects constituting the blackout objects; the visibility test on each object of the scene consists in comparing the height of a bounding box of the object and the minimum visible heights of the rectangles of the map of the minimum visible heights having an intersection with the footprint of the object;
  • the invention also relates to a system capable of determining lists of potentially visible objects in a 3D scene comprising objects on a terrain and in which a user is able to move virtually over a displacement zone corresponding to all of the zones. land not covered by the objects, characterized in that it comprises:
  • means suitable for calculating a first map of visible minimum heights said means comprising: o means suitable for making a grid of the terrain in N rectangles, the dimensions of the rectangles being a function of an overlap value k1 chosen so that the grid covers all the surface occupied by the scene, o means able to select blackout faces of blackout objects and means able to erode the blackout faces selected by an erosion value e1 proportional to the cover value k1, o means capable of calculating for each rectangle the minimum height visible from the partition prism, - means capable of determining a first list of potentially visible objects by carrying out a visibility test of the objects of the scene using the first visible minimum height map,
  • means suitable for calculating a second map of the minimum visible heights said means comprising: o means suitable for making a grid, in N rectangles, of part of the ground, said part including the base of the partition prism and the dimensions rectangles being a function of an overlap value k2 less than k1, o means able to select the blackout faces of the blackout objects and means able to erode the blackout faces selected by an erosion value ei proportional to the value of overlap k2, o means capable of calculating for each rectangle the minimum height visible from the partition prism, - means capable of determining a second list of potentially visible objects by carrying out a visibility test of the objects in the first list of potentially visible objects using the second map of minimum visible heights.
  • This system further comprises means capable of implementing the method described above.
  • - Figure 1 is a perspective view illustrating a visibility test of the method of Peter Wonka applied to an object of a scene, the object being located outside the area covered by the map of minimum visible heights;
  • - Figure 2 is a front view of three buildings before and after an erosion operation;
  • FIG. 3 is a front view illustrating the visibility test of the method of Peter Wonka applied to four objects of a 3D scene, the four objects being located outside the area covered by the map of minimum visible heights;
  • FIG. 4 is a perspective view of a stage on which is located a user, said scene comprising an occulting facade of a concealing object, a visible object and a non-visible object;
  • FIG. 5 is a perspective view of a modeled object 2O ⁇ ⁇ ;
  • FIG. 6 is an illustration of the triangulation step and includes top views of a scene before and after triangulation, and a perspective view of a view cell obtained by extruding a prism on one of the triangular partitions obtained by triangulation;
  • FIG. 7 is a first illustration of the building merger step and includes a top view of three footprints of related buildings, and a top view of the footprint of the building resulting from the merger of the three related buildings;
  • - Figure 8 is a second illustration of the building merging step and includes a front view of three connected buildings, and a front view of the building resulting from the merger of the three connected buildings;
  • - Figure 9 is a top view of a scene on which is a user and two blackout facades of blackout buildings;
  • FIG. 10 is a perspective view of a 3D scene on which is implemented the method according to the present invention.
  • - Figure 11 is a flowchart illustrating the different steps of the method. DESCRIPTION OF THE INVENTION
  • An object of the present invention is to provide a visibility calculation method making it possible to determine precise lists of potentially visible objects by region for very large 3D scenes representing virtual cities.
  • the scene represents a virtual city and the objects of the scene are buildings.
  • An object of the present invention is therefore that the visibility calculation method makes it possible to effectively process urban data of real size of the order of 8 km * 8 km, and also makes it possible to obtain much more precise results.
  • the inventors started from the observation that at ground level very few buildings are visible due to the inter-building occlusion. In fact, as shown in FIG. 4, at an observation point 20 located near a facade 21, a large volume 22 of the 3D scene, called the shadow volume, is not visible from the point of observation 20.
  • Determining a minimum subset of potentially visible objects by region is a complex problem that cannot be solved without a restrictive assumption.
  • the process assumptions are as follows:
  • the urban database is made up of buildings of the same altitude and represented using a 2 D Vz model
  • the number of pixels usable for the map of the minimum visible heights is equal to (Nx, Ny);
  • the 2D 1/2 model of a building includes an altitude (zero by default), a footprint defined by a list of points, and a height.
  • the first step of the process consists in dividing the observation space close to the ground into view cells. Indeed, the exact calculation of objects visible from a 3D volume is very difficult and very costly in terms of calculation time and material resources.
  • the 3D space 25 in which the virtual observer can move is equal to the complement of the union of all the buildings
  • the partition of the user's displacement zone is very simply obtained by 2D triangulation of the complementary footprints on the buildings. This triangulation consists in dividing the area 25 of movement of the user into a network of triangles 30.
  • the 3D partition is deduced from the triangulation by extruding a prism on each triangle previously obtained.
  • the prisms thus created constitute the view cells 31.
  • the list of potentially visible objects LOPV is calculated. This list results from a minimalist evaluation of all the objects visible from at least one of the points of the current view cell.
  • a first phase makes it possible to effectively resolve the occultation between distant buildings and calculates a first list of objects potentially visible for the current view cell.
  • the first step of the first phase of calculating the list of potentially visible objects consists in choosing the covering value k1 of a pixel as a function of the dimensions of the scene.
  • the covering value k1 (defining the size of a pixel) is chosen so that the map of minimum visible heights covers the whole city.
  • the recovery value k must be such that: k> max ( ⁇ x / Nx, ⁇ y / Ny). Or :
  • - ⁇ x and ⁇ y are the dimensions of the box in which the surface occupied by the stage is included
  • Ny are the number of pixels that can be used online and in column for the map of the minimum visible heights.
  • the second step of the first phase of calculating the list of potentially visible objects consists in choosing blackout facades of blackout objects.
  • Peter Wonka considers that the set of blackout objects consists of all the buildings on the scene, and chooses as blackout facades all the facades of the buildings on the scene.
  • the set of blackout objects consists of all the buildings on the scene and a set of merged buildings.
  • the step consisting in choosing the blackout facades consists in taking the facades of all the buildings and the facades of merged buildings. To obtain sets of merged buildings, the building fusion method described below is used.
  • Bci is therefore one of the subsets of connected buildings, that is to say in which any two objects taken from the same subset Bci necessarily belong to at least one connected component of Bci.
  • Bci related sets
  • a connected set of buildings as defined above. Then the result of the merger of all related buildings is a building defined as follows:
  • the step consisting in choosing the blackout facades consists in taking the facades of all the buildings and the facades of the sets of related objects.
  • an erasing of the blackout facades is carried out. This makes it possible to correct the errors linked to the method used to calculate the maps of the minimum visible heights.
  • a mathematical erosion operation is defined by the following property:
  • a ' is said to be eroded from A by e if A' is included in A and if for any pair of points (a, a ') such that"a'"belongs to A 'and” a "belongs to A, the distance from "a '" to "a” is greater than or equal to e. »Due to 2D14 modeling of buildings, erosion by e1 occurs on the footprint of objects. This erosion operation will be carried out on all the blackout facades of blackout objects, that is to say on the facades of buildings, but also on the facades of related sets resulting from the merger of related buildings.
  • the fourth step of the first phase of calculating the list of potentially visible objects consists in calculating the map of the minimum heights visible for the current view cell.
  • a first sub-step when calculating the Hmin (r) map of the minimum visible heights with respect to a view cell therefore consists in calculating Hp (r) maps of the minimum visible heights at different sampling points "p" of said cell.
  • Hp (r) maps of the minimum visible heights at different sampling points "p" of said cell.
  • the shadow volume 45 is called the truncated pyramid defined by the four half-lines passing through the observation point 43 and the four vertices of the facade 44.
  • This shadow volume 45 guarantees that any object entirely contained in this 3D volume is not visible from the observation point 43.
  • the facade 44 is called the facade blackout.
  • Hp (r) map taking into account all of the blackout facades with respect to an observation point p, on. determines the set of Hp maps, o (r) taking into account only one blackout facade o among the set FO of blackout facades relative to the observation point p. We deduce the Hp (r) card.
  • Hp (r) max ⁇ Hp, o (r), oe FO ⁇
  • Hp (r) is the function representing the minimum visible height of a pixel r with respect to the observation point p
  • o (r) is the function representing the minimum visible height of a pixel r relative to the observation point p and taking into account only the blackout facade o,
  • Hp, o (r) are calculated by orthogonal projections of the volumes of shadows on the pixel matrix 46.
  • discretization on a grid of pixels generates errors. This is the reason why the mathematical erosion operation is carried out before calculating the map of visible heights.
  • the Hmin (r) map associated with the current view cell is determined.
  • Hmin (r) min ⁇ Hp (r), pe PE ⁇ ,
  • PE represents the set of sampling points taken on the edges of the upper face of the view cell. The condition for this calculation to be valid is that the sampling interval is less than or equal to the erosion amplitude e of the blackout facades.
  • the visibility test of an object consists of a comparison between the height of a bounding box of the object and the Hmin (r) of the pixels having an intersection with the footprint on the ground of the object.
  • the second phase of calculating the list of potentially visible objects includes a first step consisting in choosing an erosion value e2.
  • This erosion value e2 is chosen to be low (in practice less than 1 meter) in order to minimize the phenomenon of reduction of blackout facades.
  • a value k2 of overlap corresponding to the size of the pixels is deduced from the value of erosion e2 by the formula connecting e and k: e ⁇ VJsl ⁇ .
  • the second stage of the second phase consists in choosing the blackout facades.
  • Peter Wonka takes as blackout facades all the facades of buildings.
  • the present method adds the facades of the pairs of connected buildings.
  • the third step of the method consists in eroding the blackout faces with the erosion value e2.
  • the method used to erode the faces is identical to that used in the first phase
  • the fourth step of the second phase consists in calculating the map of the minimum heights visible for the current view cell. This calculation is performed in the same way as in the fourth step of the first phase. This gives the map of the minimum heights visible for each view cell.
  • the fifth step of the second phase consists in testing the visibility on the objects of the scene in order to determine a second list of potentially visible objects. This test is carried out with respect to each view cell according to the second map of the minimum visible heights associated with said cell. This test is performed on the objects in the first list of potentially visible objects and is a function of the distance of the objects from the area covered by the map of the minimum visible heights.
  • the object tested has an intersection with the map of the minimum visible heights, then the object is said to be potentially visible if its maximum height is greater than one of the heights of the pixels of the map having an intersection with the footprint. on the ground of the object. Otherwise the surrounding volume of the object is projected (see Figure 1) on the horizon of visibility. If the projection of the object is above the visibility horizon, the object is said to be potentially visible.
  • K1 is calculated so that the map of the minimum visible heights covers the whole city.
  • the erosion value e1 is deduced from the size of a pixel.
  • d) The selection and erosion of blackout facades (203, 204, 205, 206) (step 73 of Figure 11). To the facades of all the buildings, we add the facades of the mergers of all the related buildings.
  • e) The computation of the map of the minimum visible heights Hmin1 (r) associated with the current view cell (step 74 of FIG. 11).
  • the calculation is done by the operation of union and intersection of the volumes of shadows generated by the blackout facades and the sampled points of the view cell 202. The calculation is done using the wired functions of the graphics cards 3D accessible by the OpenGL graphics library. f) The search for potentially visible objects (step 75 in Figure 11).
  • the visibility test for objects 200 is as follows: an object 200 is said to be potentially visible if its maximum height is greater than one of the heights of the map of the minimum visible heights of the pixels having an intersection with the footprint of the 'object.
  • erosion value e1 is less than 1 meter h
  • the visibility test is only carried out on the objects obtained in step f) as a function of the distance of the objects from the area covered by the map of the minimum visible heights. Indeed, if an object has an intersection with the area of the map, then the object is said to be potentially visible if its maximum height is greater than one of the heights of the visibility matrix of the pixels having an intersection with the footprint. on the ground of the object. Otherwise the encompassing volume of the object is projected onto the visibility horizon. If the projection of the object is above the visibility horizon, the object is said to be potentially visible.
  • the method presented above can be implemented in a system making it possible to carry out visibility calculations.
  • This system is for example a personal computer comprising memory means (RAM, ROM) connected to processing means such as a processor, display means such as a display screen and input means such as a keyboard and mouse.
  • This system can also be an Internet server. In this case, the server makes it possible to determine the lists of potentially visible objects, and transmits them online for example to a remote personal computer which will display the 3D scene.

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • Geometry (AREA)
  • Computer Graphics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Processing Or Creating Images (AREA)

Abstract

L'invention concerne un procédé, et un système associé, permettant de déterminer des listes d'objets potentiellement visibles dans une scène 3D (201) comprenant des objets (200) et dans laquelle un utilisateur est susceptible de se déplacer virtuellement, le procédé comprenant les étapes consistant à partitionner la zone de déplacement (250) de l'utilisateur en un réseau de prismes de partition (202), calculer une première carte de hauteurs minimales visibles Hmin1 (R), les dimensions de ladite carte étant fonction d'une valeur de recouvrement k1 choisie de sorte que la carte recouvre toute la surface occupée par la scène (201), déterminer une première liste d'objets potentiellement visibles en effectuant un test de visibilité des objets (200) de la scène (201) à l'aide de la première carte Hmin1 (R), calculer une deuxième carte des hauteurs minimales visibles Hmin2(R), les dimensions de ladite carte étant fonction d'une valeur de recouvrement k2 inférieure à k1, déterminer une deuxième liste d'objets potentiellement visibles en effectuant un test de visibilité des objets de la première liste à l'aide de la deuxième carte Hmin2(R).

Description

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

Claims

REVENDICATIONS
1. Procédé de détermination de listes d'objets potentiellement visibles dans une scène 3D (201) comprenant des objets (200) sur un terrain, et dans laquelle un utilisateur est susceptible de se déplacer virtuellement sur une zone de déplacement (250) correspondant à l'ensemble des zones du terrain non recouvertes par les objets (200), caractérisé en ce qu'il comprend les étapes consistant à :
- partitionner la zone de déplacement (250) de l'utilisateur en un réseau de prismes de partition (202),
Puis pour chaque prisme de partition (202) :
- 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 (203, 204, 205, 206) d'objets occultants et en érodant les faces occultantes (203, 204, 205, 206) 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 (202),
. - déterminer une première liste d'objets potentiellement visibles en effectuant un test de visibilité des objets (200) 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 (202) 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 (203, 204, 205, 206) des objets occultants et en érodant les faces occultantes (203, 204, 205, 206) 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.
2. Procédé selon la revendication 1 , caractérisé en ce que les objets (200) de la scène (201 ) 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.
3. Procédé selon la revendication 1 ou 2, caractérisé en ce qu'il comprend en outre une étape de fusion d'objets (38, 39, 40) connexes afin d'obtenir des ensembles d'objets connexes (141 ), ladite étape de fusion étant réalisée préalablement à l'étape de sélection des faces occultantes (203, 204, 205, 206).
4. Procédé selon les revendications 2 et 3, caractérisé en ce que l'étape de fusion des objets (38, 39, 40) connexes comprend les étapes consistant à :
- déterminer des ensembles d'objets (38, 39, 40) vérifiant des conditions de connexité, Puis pour chaque ensemble d'objets connexes : - supprimer des empreintes (32, 33, 34) des objets (38, 39, 40) les arrêtes (35, 36) qu'elles ont en commun afin d'obtenir une empreinte unique (37) 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 (141).
5. Procédé selon la revendication 4, caractérisé en ce que 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.
6. Procédé selon l'une des revendications précédentes, caractérisé en ce que la valeur de recouvrement k1 est calculée en utilisant la relation : 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, 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, et en ce que la valeur d'érosion e1 est déduite du calcul précédent en utilisant la relation liant la valeur d'érosion el à la valeur de recouvrement k1 : cl >k1/v2.
7. Procédé selon l'une des revendications précédentes, caractérisé en ce que la valeur d'érosion e2 est choisie sensiblement égale à 1 mètre, et en ce que la valeur de recouvrement k2 est déduite de la valeur d'érosion e2 en utilisant la relation liant la valeur d'érosion e2 à la valeur de recouvrement k2 : a >k2Λ/2.
8. Procédé selon l'une des revendications précédentes, caractérisé en ce que l'étape consistant à partitionner la zone de déplacement (250) de l'utilisateur en un réseau de prismes de partition (202) comprend les sous étapes consistant à : .
- partager la zone de déplacement (250) de l'utilisateur en un réseau de triangles,
- extruder un prisme sur chaque triangle obtenu précédemment.
9. Procédé selon la revendication 2 en combinaison avec l'une quelconque des revendications 1 , 3, 4, 5, 6, 7 ou 8, caractérisé en ce . que l'étape consistant à éroder les faces occultantes (203, 204, 205,
206) des objets occultants par une valeur d'érosion e consiste à éroder les empreintes des objets occultants par la valeur d'érosion ε.
10. Procédé selon l'une des revendications précédentes caractérisée en ce que l'étape consistant à sélectionner les faces occultantes (203,
204, 205, 206) des objets occultants comprend la sélection des faces des objets ainsi que la sélection des faces des ensembles d'objets connexes (141), lesdits objets et ensembles d'objets connexes constituant les objets occultants. • '
11. Procédé selon l'une des revendications précédentes, caractérisé en ce que le test de visibilité sur chaque objet (200) 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
(200). 12. Système apte à déterminer des listes d'objets potentiellement visibles dans une scène 3D comprenant des objets (200) sur un terrain et dans laquelle un utilisateur est susceptible de se déplacer virtuellement sur une zone de déplacement (250) 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 (250) 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 (202),
- des moyens aptes à déterminer une première liste d'objets potentiellement visibles en effectuant un test de visibilité des objets (200) 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 (202) 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 e2 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.
13. Système selon la revendication 12, caractérisé en ce qu'il comprend en outre des moyens aptes à mettre en œuvre le procédé selon les revendications 2 à 11.
PCT/FR2004/001370 2004-06-03 2004-06-03 Procede de determination de liste d’elements potentiellement visibles par region pour des scenes 3d de tres grandes tailles representant des villes virtuelles WO2006003267A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
PCT/FR2004/001370 WO2006003267A1 (fr) 2004-06-03 2004-06-03 Procede de determination de liste d’elements potentiellement visibles par region pour des scenes 3d de tres grandes tailles representant des villes virtuelles

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/FR2004/001370 WO2006003267A1 (fr) 2004-06-03 2004-06-03 Procede de determination de liste d’elements potentiellement visibles par region pour des scenes 3d de tres grandes tailles representant des villes virtuelles

Publications (1)

Publication Number Publication Date
WO2006003267A1 true WO2006003267A1 (fr) 2006-01-12

Family

ID=34958396

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2004/001370 WO2006003267A1 (fr) 2004-06-03 2004-06-03 Procede de determination de liste d’elements potentiellement visibles par region pour des scenes 3d de tres grandes tailles representant des villes virtuelles

Country Status (1)

Country Link
WO (1) WO2006003267A1 (fr)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2075762A3 (fr) * 2007-12-26 2011-08-10 Aisin Aw Co., Ltd. Dispositif de traitement de données tridimensionnelles, dispositif de génération d'image tridimensionnelle, dispositif de navigation, et programme de traitement de données tridimensionnelles
WO2017179025A1 (fr) 2016-04-15 2017-10-19 Alk-Abelló A/S Polypeptides épitopiques d'allergènes de pollen d'ambroisie

Non-Patent Citations (4)

* Cited by examiner, † Cited by third party
Title
BATAGELO H C ET AL: "Dynamic scene occlusion culling using a regular grid", COMPUTER GRAPHICS AND IMAGE PROCESSING, 2002. PROCEEDINGS. XV BRAZILIAN SYMPOSIUM ON FORTALEZA-CE, BRAZIL 7-10 OCT. 2002, LOS ALAMITOS, CA, USA,IEEE COMPUT. SOC, US, 7 October 2002 (2002-10-07), pages 43 - 50, XP010624490, ISBN: 0-7695-1846-X *
DECORET X; DEBUNNE G; SILLION F: "Erosion based visibility preprocessing", 14TH EUROGRAPHICS WORKSHOP ON RENDERING, 25 June 2003 (2003-06-25) - 27 June 2003 (2003-06-27), 2003 ACM NEW YORK, NY, USA, pages 281 - 288, XP002322894 *
WONKA P ET AL: "OCCLUDER SHADOWS FOR FAST WALKTROUGHS OF URBAN ENVIRONMENTS", COMPUTER GRAPHICS FORUM, AMSTERDAM, NL, vol. 18, no. 3, 7 September 1999 (1999-09-07), pages C51 - C60,C400, XP001034491, ISSN: 0167-7055 *
WONKA P; WIMMER M; SCHMALSTIEG D: "Visibility preprocessing with occluder fusion for urban walkthroughs", RENDERING TECHNIQUES 2000. PROCEEDINGS OF THE EUROGRAPHICS WORKSHOP, 26 June 2000 (2000-06-26), WIEN, AUSTRIA, pages 1 - 11, XP002322893 *

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2075762A3 (fr) * 2007-12-26 2011-08-10 Aisin Aw Co., Ltd. Dispositif de traitement de données tridimensionnelles, dispositif de génération d'image tridimensionnelle, dispositif de navigation, et programme de traitement de données tridimensionnelles
US8441479B2 (en) 2007-12-26 2013-05-14 Aisin Aw Co., Ltd. Three dimensional data processing device and method, three dimensional image generating device, navigation device, and computer-readable medium containing three-dimensional data processing program
WO2017179025A1 (fr) 2016-04-15 2017-10-19 Alk-Abelló A/S Polypeptides épitopiques d'allergènes de pollen d'ambroisie

Similar Documents

Publication Publication Date Title
Charron et al. De-noising of lidar point clouds corrupted by snowfall
EP2828834B1 (fr) Modèle et procédé de production de modèles 3d photo-réalistes
WO2006108971A1 (fr) Procede de determination hierarchique d'evenements coherents dans une image sismique
EP1292921A1 (fr) Raffinement d'un maillage triangulaire en trois dimensions
FR3023641A1 (fr)
EP3164743B1 (fr) Procede de determination de caves geologiques
EP3729327A1 (fr) Methode de reconnaissance d'objets dans une scene observee en trois dimensions
EP3679517B1 (fr) Procede de determination des bords saillants d'une cible sur une image
Biasutti et al. Visibility estimation in point clouds with variable density
FR2964775A1 (fr) Procede d'estimation de l'occultation dans un environnement virtuel
FR2966623A1 (fr) Procede d’estimation de l’occultation dans un environnement virtuel
EP2504816B1 (fr) Procede d'estimation de diffusion de la lumiere
WO2006003267A1 (fr) Procede de determination de liste d’elements potentiellement visibles par region pour des scenes 3d de tres grandes tailles representant des villes virtuelles
WO2006003268A1 (fr) Precede general de determination de liste d’elements potentiellement visibles par region pour des scenes 3d de tres grandes tailles representant des villes virtuelles d’altitudes variables.
WO2006027519A2 (fr) Procede de compression de donnees de visibilite, de decompression, decodeur, systeme de compression
FR2948800A1 (fr) Procede d'estimation de diffusion de la lumiere
EP2266101B1 (fr) Procede et dispositif de simulation de contact par images a plan de profondeur
EP3948654A1 (fr) Procédé, programme d'ordinateur et système pour l'identification d'une instance d'objet dans une scène tridimensionnelle
EP3072110B1 (fr) Procédé d'estimation du mouvement d'un objet
BE1026937B1 (fr) Méthode de segmentation d'une image
Sun et al. Generalizable Non-Line-of-Sight Imaging with Learnable Physical Priors
CA2277788C (fr) Methode de detection d'une discontinuite geologique presente dans un milieu par utilisation du flux optique
FR2953050A1 (fr) Procede et dispositif de detection des points de courbure dans une image d'entree
EP2192555B1 (fr) Affichage de données paramétrées
WO2023083577A1 (fr) Procédé pour déterminer des positions optimisées d'un objet pour le suivi d'une trajectoire dans un environnement simulé.

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BW BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE EG ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NA NI NO NZ OM PG PH PL PT RO RU SC SD SE SG SK SL SY TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): BW GH GM KE LS MW MZ NA SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LU MC NL PL PT RO SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

NENP Non-entry into the national phase

Ref country code: DE

WWW Wipo information: withdrawn in national office

Country of ref document: DE

122 Ep: pct application non-entry in european phase
点击 这是indexloc提供的php浏览器服务，不要输入任何密码和下载