+

WO2006003268A1 - 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. - Google Patents

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. Download PDF

Info

Publication number
WO2006003268A1
WO2006003268A1 PCT/FR2004/001371 FR2004001371W WO2006003268A1 WO 2006003268 A1 WO2006003268 A1 WO 2006003268A1 FR 2004001371 W FR2004001371 W FR 2004001371W WO 2006003268 A1 WO2006003268 A1 WO 2006003268A1
Authority
WO
WIPO (PCT)
Prior art keywords
objects
terrain
visible
height
faces
Prior art date
Application number
PCT/FR2004/001371
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/001371 priority Critical patent/WO2006003268A1/fr
Publication of WO2006003268A1 publication Critical patent/WO2006003268A1/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
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
    • G06T17/05—Geographic models
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2210/00—Indexing scheme for image generation or computer graphics
    • G06T2210/12—Bounding box

Definitions

  • the present invention relates to the general technical field of synthetic imaging, and more particularly 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 3D scenes of very large sizes representing virtual cities of variable altitudes.
  • the role of visibility calculus is to determine which objects of a 3D scene are visible from a point and an observation direction.
  • This pretreatment is a method of calculating visibility. It provides a list of objects in the scene that will be visible in a given view. Only objects in 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 named in the LOPV suite.
  • the list of visible objects is included in the list of potentially visible objects.
  • a first visibility calculation method for establishing lists of potentially visible objects 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 observation direction [1, 4, 8, 9, 13, 16].
  • a second method of calculating visibility for establishing lists of potentially visible objects is based on the technique using the pyramid of view. This technique starts from the observation that all the objects located outside this pyramid at a given instant are rejected during the rendering phase.
  • a third method of calculating visibility starts from the following property: to test the occultation of each polygon being too slow, it is more efficient to use techniques based on the use of hierarchical structures of the scene and bounding volumes [9 ].
  • the three processes that have just been presented make it possible to reject part of the scene of the 3D rendering phase.
  • the method of the present invention is usable in various 3D applications, but is particularly suitable for applications proposing a ground-level 3D navigation in a 3D scene representing a virtual city.
  • the most important property is that at a given observation position, only a very small part of the buildings constituting the 3D scene is visible because of inter-building occultations.
  • a first method of calculating visibility using the inter-object occultation principle is the Coord and Teller process [5, 6]. This process is based on the use of large convex blackout objects.
  • This method determines occultation planes valid relative to a certain displacement of the observer.
  • plans are defined with respect to a set of observation points. There are several evolutions of this process based on different structuring of the 3D scene.
  • Other visibility calculation methods implementing the principle of inter-object occultation have also been proposed. These methods are based on the property of the occultation volumes (shadow volume) [2, 11] generated by a point of observation and the outline of some objects that obscure the rest of the scene. Indeed, at a given point of observation, we can define a shadow volume centered on the point of observation and based on the outline of occulting objects guaranteeing that any object included in this shadow volume will be not visible from the observer.
  • Several processes mixing scene structuring and this property have been proposed. Concerning the choice of occulting objects, several dynamic or static strategies have also been proposed.
  • Another approach in the visibility calculation is to make a partition of the 3D navigation space and for each element of the partition, called the view cell, of. calculate the list of potentially visible objects.
  • this visibility calculation is performed for areas, or cells of view, of the 3D space.
  • this type of visibility calculation method for determining lists of potentially visible objects by region (that is to say by view cell).
  • the 2D 1/4 model of a building includes an altitude (null by default), a footprint defined by a list of points, and a height. From this information (footprint E, altitude A, height H), it is possible, as illustrated in FIG. 1, to draw a 3D building by extruding a prism 24 at altitude A, the base of the prism 24 corresponding to the impression E and the height of the prism being equal to the height H of the building.
  • Peter Wonka's process consists of different stages: - a first step is to make a partition of the navigable space into a view cell,
  • a second step consists in calculating visible minimum heights in order to determine a map of the minimum heights visible with respect to each view cell, and a third step is to test the visibility of the objects of the scene with respect to each view cell. according to the map of the minimum visible heights of the view cell.
  • the calculation of the map of visible minimum 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 the minimum visible height Hmin (r) in all the rectangle with respect to the cell of view.
  • the calculation of the map of the visible minimum heights uses the resources of the 3D graphics cards and links the dimension of the 2D zone for calculating the visible minimum heights with the number of pixels of the 3D graphics card and the surface covered by a pixel.
  • a 2D area for calculating the minimum visible heights of 1024 * 768 square meters is obtained. So the map of the minimum visible heights will cover 1024 * 768 square meters of the 3D urban scene.
  • the method When calculating the map of the visible minimum heights, the method imposes to reduce the occulting objects of an erosion value denoted "e" in order to limit the errors related to the method used to calculate the visible minimum heights of said map. Due to modeling
  • the erosion operation is performed on the footprint of the buildings.
  • the erosion value e (corresponding to the erosion amplitude) is related to the recovery value (corresponding to the size of a pixel) denoted k by the following relation: e> k / + Jl.
  • the erosion value In practice to take into account the occultation phenomena, the erosion value must be low.
  • the visibility test on the objects of the 3D scene is as follows.
  • the visibility test is done by comparing the height of an enclosing box of the object and the minimum visible heights of the pixels having an intersection with the footprint. on the ground of the object. For objects that are outside the area covered by the map of the minimum visible heights, the visibility test is shown in Figure 2. Wonka proposes the following modification of his process: the boundaries of the map of the minimum visible heights 1 make it possible to define a horizon of visibility 4. This skyline 4 assures us that every object
  • Peter Wonka's method therefore does not deal with the inter-building concealment that is outside the overlap area, ie outside the area covered by the map of the minimum visible heights. .
  • the Wonka process has the following disadvantages: i.
  • the process does not take into account field data
  • the terrain is very often in relief.
  • some parts of the field may obscure areas of the scene. For example, a user in front of a hill does not see what is behind the hill.
  • some areas of the scene may be visible from some parts of the terrain. For example, the number of buildings visible to a user at the top of a hill will be greater than the number of visible buildings for a user who is at the bottom of a hole. ii. The process does not take into account buildings of different altitudes.
  • e is generally equal to one meter, which requires that the recovery value of a pixel (k) is less than or equal to ⁇ ⁇ meter.
  • the values k and e are linked by the relation e ⁇ k / y / 2. So if we assume an erosion value e equal to one meter and a graphic card of 1280 * 1024 pixels, then the map of the minimum visible heights will cover a maximum of 1817 * 1454 square meters, and in real cases, the cities are of the order 8km * 8km.
  • the inter-building concealment is not taken into account outside the area covered by the map of the minimum visible heights. vi.
  • the erosion operation generates visibility.
  • one of the disadvantages of the erosion operation is that this mathematical operation generates visibility between the buildings having at least one stop in common, even if this visibility does not exist in the initial database.
  • an object 6 which is situated, with respect to the current view cell, behind two buildings 7 and 8 having a stop 9 in common, and which is not visible before the erosion operation.
  • the inter-building concealment is not taken into account outside the area covered by the map of the minimum visible heights.
  • any object 3 located outside the area covered by the map 1, and whose projection 5 on the horizon of visibility 4 has a height greater than the minimum visible heights will be considered potentially visible. However, it can be hidden by another building located outside the area covered by map 1.
  • building 12 (5 meters) closest to the viewpoint will be considered hidden, and the following three buildings 13, 14, 15 (25, 20 and 10 meters) will be considered as potentially visible, their projections on the visibility horizon 17 having heights greater than the height of the horizon of visibility 17 (6 meters).
  • An object of the present invention is to provide a general method for determining a list of potentially visible objects by region for 3D scenes of very large sizes representing virtual cities of varying altitudes to overcome most of the aforementioned drawbacks.
  • the invention relates to a method for determining lists of potentially visible objects in a 3D scene comprising objects on a terrain of variable altitude and in which a user is able to move virtually on a displacement zone corresponding to the whole. areas of the ground not covered by the objects, characterized in that it comprises the steps of:
  • the present invention thus makes it possible to treat the cases of real urban environments for which the effect of the natural relief is far from being negligible.
  • the creation of paving stones makes it possible to take into account the occultation generated by the relief of the terrain.
  • the present invention makes it possible to take into account complementary urban data (street furniture, vegetation, signage and field data) in visibility.
  • the method of the present invention is completely independent of the memory resources with respect to the size of the bases since the size of the rectangles of the grid is adapted according to the available memory resources for the calculation of the map of the visible minimum heights.
  • Some methods of calculating visibility 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 that must be in RAM is the visibility matrix (or map of the minimum visible heights) whose size is fixed in advance, independently of the size of the urban environment to be treated.
  • this data structure is stored in the memory of the graphics card and not in the central memory of the computer.
  • the method further comprises a step of:
  • the step of creating terrain objects comprises the substeps of: - Make a grid in M rectangles of the plane Pmin on all the surface of the ground,
  • the step of partitioning the user's moving area into an array of view cells comprises the substeps of:
  • the scene comprises generic objects defined by a footprint, an altitude and a height
  • the method further comprises a step of transforming the generic objects, and field objects into modeled 2D 1/2 occulting objects by: - extending vertically the faces of the generic objects up to the altitude zmin, each occulting object thus obtained being defined by a fingerprint corresponding to the projection of the generic object on the plane Pmin, an altitude equal to zmin and a height equal to the sum the altitude and height of the generic object, - vertically extending the bases of the terrain objects to the altitude zmin, each occulting object thus obtained being defined by an imprint corresponding to the projection of the terrain object on the Pmin plane, an altitude zmin and a height equal to the altitude of the terrain object of which
  • the transformation of generic objects, field objects and bounding volumes into 2D 1/4 extended objects said transformation consisting in extending the faces of generic objects, field objects and bounding volumes to the Pmin plane, each extended object thus obtained being defined by a footprint equal to the projection on the Pmin plane of the generic object, of the terrain object or of the enclosing volume associated with it, by an altitude equal to zmin and a height equal to the sum of the altitude and height of the generic object, the terrain object, or the enclosing volume associated with it;
  • the step of determining, for each view cell, a list of potentially visible objects comprises the substeps of:
  • calculating a first map of visible minimum heights said map being obtained by: o carrying out a grid in N rectangles of the plane Pmin, the area occupied by each rectangle being a function of a recovery value k1 chosen so that the grid covers all the surface of the ground, o selecting occulting faces, in particular among the faces of the occulting objects, and by eroding the occulting faces selected by an erosion value e1 proportional to the recovery value k1, o calculating for each rectangle the minimum height visible from the view cell, - determining a temporary list of potentially visible objects by comparing, for each object of the scene and each field object, the height of the associated extended object and the minimum heights of the first map of the rectangles intersecting with the imprint of the extended object, - calculating a second map of the visible minimum heights, said map being obtained by: o carrying out a grid in N rectangles of the plane Pmin on part of the terrain, said part including the base of the view cell and the area occupied by each rectangle being a
  • the method further comprises a step of merging related blackout objects to obtain related sets, said merging step being performed prior to the step of selecting the blackout faces, and consisting of: - to determine groups of occulting objects satisfying conditions of connectivity,
  • the recovery value k1 is calculated using the relation: k1 ⁇ max ( ⁇ x / Nx, ⁇ y / Ny). Or :
  • Nx, Ny are the number of rectangles usable in row and in column for the map of the visible minimum heights, so that k1 is greater than or equal to the maximum between the ratio of the width of the land by the number of rectangles usable in line, and the ratio of the length of the land by the number of rectangles usable in column, and in that the erosion value e1 is deduced from the preceding calculation by using the relation relating the erosion value el to the recovery value k1: el ⁇ k1 / ⁇ 2; the erosion value e2 is chosen to be substantially equal to 1 meter, and in that the recovery value k2 is deduced from the value of e2 chosen by using the relation linking the erosion value e2 to the recovery value k2: a >k2 ⁇ ; the step consisting in selecting occulting faces, in particular among the faces of the occulting objects (300, 301), consists of:
  • the step of eroding the blackout faces with an erosion value e consists in eroding the footprints of the blackout objects and sets of obscuring objects related to the erosion value e;
  • 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 likely to move virtually on a displacement zone corresponding to all the zones. land not covered by the objects, characterized in that it comprises:
  • means capable of determining, for each cell of view, a list of objects potentially visible by the user from the view cell, said list being determined by testing the visibility of the objects of the scene and the created terrain objects.
  • FIG. 1 is a perspective view of a model object 2OV 2 ;
  • FIG. 2 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 the minimum visible heights;
  • FIG. 3 is a front view of three objects before and after an erosion operation;
  • FIG. 4 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 the minimum visible heights;
  • FIG. 5 is a perspective view of a scene on which a user is located, said scene comprising an occulting face of an occulting object, a visible object and a non-visible object;
  • FIG. 6 is a perspective view of a scene comprising objects on a terrain of variable altitude
  • FIG. 7 is a front view of a scene comprising objects on a terrain of variable altitude
  • FIG. 8 is an illustration of a triangulation step and comprises top views of a scene before and after triangulation, and a perspective view of a view cell obtained by extruding a prism on a triangular partition obtained by triangulation;
  • FIG. 9 is a perspective view of a view cell that overlaps two terrain objects;
  • FIG. 10a is a front view of modeled blackout objects
  • FIG. 10b is a front view of 2DVz modeled extended objects obtained from the objects of the scene and the field objects;
  • FIG. 11 is a first illustration of the step of fusing related blackout objects and comprises a view from above of three footprints of related blackout objects, and a top view of a fingerprint resulting from the fusion of the fingerprints of the three related blackout objects;
  • FIG. 12 is a second illustration of the step of fusing related blackout objects and comprises a front view of three related blackout objects, and a front view of the object resulting from the fusion of the three related blackout objects;
  • FIG. 13 is a top view of a scene on which there is a user and two blackout faces of occulting objects;
  • FIG. 14 is a flowchart illustrating the various steps of the method.
  • An object of the present invention is to provide a general method for determining a list of potentially visible objects by region for very large 3D scenes representing virtual cities of varying altitudes.
  • the visibility calculation method presented below makes it possible to determine lists of objects that are potentially visible in urban scenes of real size of the order of 8km * 8km including objects, particularly representing buildings, on a parcel of land. variable altitude.
  • this method takes into account the effects of the terrain for occultation and visibility calculations.
  • the process incorporates for all visibility tests all types of objects (street furniture, vegetation ).
  • the inventors started from the observation that at ground level very few objects of a scene like street furniture are visible because of the inter-object occultation.
  • a large volume 22 of the 3D scene is not visible from the point of view. observation 20.
  • an object 23 included strictly in this shadow volume 22 will not be visible from the observation point 20. Therefore, during a ground navigation in an urban scene representing a virtual city, very few objects 19 will be visible from an observation point 20.
  • the determination of a minimal subset of potentially visible objects per region in a scene is a complex problem that can not be solved without hypothesis.
  • hypotheses of the method are as follows: the objects of the scene (buildings, signage, tree, ...) are
  • the set of objects of a scene is composed of: o generic objects 100, that is to say objects represented by a 2D / 4 model (namely a footprint, an altitude and a height), these generic objects 100 are buildings; Moreover, the imprints of objects
  • each generic object 100 may be associated with a roof 102 modeled by assembling polygons
  • the objects of the scene are included in a box of dimension ( ⁇ x, ⁇ y); the number of pixels that can be used for the map of the visible minimum heights is equal to (Nx, Ny);
  • the visibility calculation method makes it possible to process digital data.
  • digital data are characteristic of virtual objects, for example buildings, bus shelters, or terrain.
  • a mobile or fixed terminal is used as a work station, said terminal comprising memory means for storing a database comprising these digital data.
  • the numeric data associated with it includes this information.
  • These digital data are stored in the workstation database, along with other information about the polygon such as its texture for example.
  • the processing means of the central unit are able to calculate the position of all the points of the polygon to be displayed.
  • a representation of the terrain is obtained.
  • we will present the visibility calculation process by referring to the objects (land, buildings, street furniture) rather than referring to the associated numerical data on which the treatments are carried out.
  • the first step of the method consists in calculating the minimum altitude of the terrain of the stage. In the following, this minimum altitude will be called altitude zmin.
  • the second step of the method consists in defining a plane Pmin 103 at the altitude zmin. This plan will be used in some of the following steps of the process.
  • the third step of the method consists in calculating the field 104 modeled 2D A 1
  • These field objects objects are calculated in particular to take into account the concealment of objects generated by the field.
  • a 2D regular grid of the Pmin plane 103 is defined.
  • a 3D block is associated, of which: the lower base is the rectangle itself, the minimum altitude 105 is equal to the minimum altitude of the terrain surface having a nonzero intersection with this tile, the height 106 is equal to the maximum altitude of the terrain surface having a non-zero intersection with this tile.
  • the fourth step of the method consists of partitioning the near-ground observation space into regions called view cells. Indeed, the exact calculation of visible objects from a 3D volume is very difficult and very expensive in terms of calculation time and material resources.
  • the space 25 in which the virtual observer can move is equal to the complement of the union of all the objects 26, 27, 28, 29 of the scene.
  • the partition of the user's moving area is obtained very simply as follows. We translate the terrain and the objects of the scene in the plane Pmin 103. Then, we carry out a 2D triangulation of the complementary
  • This triangulation consists of sharing the user's zone of displacement in 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 are called view cells 31.
  • the altitude 108 of a cell 107 is equal to at least 109 of the altitudes of the lower bases 109, 110 of the terrain objects 111, 112 having an intersection with the view cell 107, and the height of the a view cell 107 is equal to a reference height 113 (between 0 and 2 meters at the city scale) to which is added the maximum value 114 of the heights 114, 115 of the field objects having an intersection with the cell .
  • the fifth step of the method consists of transforming the generic objects 100 and the field objects 104 of the scene into occulting objects 300, 301 of the same altitude zmin.
  • These occulting objects are modeled 2D 1 A Indeed, the model 2D 1/4 simplifies the calculations of visibility.
  • These occulting objects 300, 301 will be used when calculating maps of the minimum visible heights.
  • the imprint of an occulting object 301 corresponds to the projection on the plane Pmin of the generic object of which it is the extension. All these occulting objects 301 have the same altitude zmin. The height of an occulting object
  • 301 is equal to the sum of the altitude and the height of the object 100 associated with it.
  • the prints of the terrain objects 104 are vertically extended in the plane Pmin 103. Prisms are then obtained modeling the extended field objects. These prisms are called occulting objects 300.
  • the footprint of an occulting object 301 is equal to the footprint of the terrain object 104 translated at the altitude zmin, the altitude is equal to zmin, and the height is equal to the altitude of the terrain object 104.
  • LOPV list of the potentially visible objects
  • a first phase effectively resolves the far-end inter-object occultation and calculates, for each view cell, a temporary list of potentially visible objects using a first map of minimum heights. visible.
  • This map is obtained by carrying out a grid in the plane Pmin of the surface of the ground, the dimensions (length, width) of this first map being a function of a recovery value k1.
  • a second phase makes it possible to effectively take into account the close inter-object occultation, and calculates, for each view cell, the list of potentially visible objects using a second map of the visible minimum heights.
  • This map is obtained in the same way as before.
  • the dimensions (length, width) of this second card are a function of a recovery value k2.
  • the visibility tests are done only on the objects of the temporary list calculated in the first phase.
  • the first step in the first phase of calculating the list of potentially visible objects is to choose the recovery value k1.
  • This recovery value is chosen according to the area occupied by the terrain. The area occupied by a pixel depends on this recovery value k1.
  • the recovery value k1 In order to be able to take into account all the phenomena of inter-object occultations, one chooses the recovery value k1 so that the first map of the visible minimum heights covers the whole city. For this, the recovery value k1 must be such that: k1> max ( ⁇ x / Nx, ⁇ y / Ny). Or :
  • Ny are the number of pixels usable in line and in column for the calculation of the maps of the visible minimum heights.
  • the second step in the first phase of calculating the list of potentially visible objects is to choose blackout faces.
  • all the faces of the occulting objects 300, 301 that is to say the faces of the extended generic objects and extended field objects, will be selected as the blackout faces.
  • groups of merged obscuration objects the fusion method described below is used. "Let a set B of objects modeled 2DA 1 , then one can realize a partition (in the sense ensemblist), of all the objects, by the criterion of connectivity of the footprints on the ground following:
  • Bi and Bj be two objects of set B, then Bi and Bj are said to be related if their footprints on the ground have at least two consecutive vertices in common.
  • B ⁇ Uj Bci for i ranging from 1 to N ⁇ Bci is therefore one of the subsets of related occulting objects, that is to say in which any two objects taken in the same subset Bci necessarily belong to at least one connected component of Bci.
  • BICs will be called "related sets”.
  • the step of selecting the occulting faces consists in selecting all the faces of the occulting objects 300, 301, and the faces of the related sets.
  • 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.
  • erosion by e1 is done on the footprint of the blackout objects and related sets.
  • the fourth step in the first phase of calculating the list of potentially visible objects is to calculate the first map of the minimum visible heights for the current view cell. Since the calculation of a map of the visible minimum heights is a difficult and time-consuming problem, a minimal approximation of this calculation is proposed. This approximation consists in sampling with points the edges of the upper face of the current view cell and calculating a map of the minimum heights visible at each of these points.
  • the calculation of the map associated with the current view cell is then simply deduced from the maps associated with the sampling points of the current view cell.
  • Shadow volume 22 the truncated pyramid defined by the four half-lines passing through observation point 20 and the four peaks of face 21.
  • This shadow volume 22 ensures that any object 23 entirely contained in this 3D volume is not visible from the observation point 43.
  • the map Hp (r) of the minimum heights visible with respect to the observation point p 43 is deduced from the shadow volumes 45, 48 by orthogonal projection on a matrix 46 of pixels of the volumes of shadows 45, 48 generated by the occulting faces 44, 47.
  • the procedure is as follows.
  • the set of maps Hp is determined, where o (r) takes into account only one occulting face o of the set FO of the occulting faces with respect to the observation point p.
  • the map Hp (r) is calculated.
  • map Hp (r) associated with the set of maps Hp, o (r) of all the occulting faces o is given by the formula:
  • Hp (r) max ⁇ Hp, o (r), where ⁇ FO ⁇ , where:
  • 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 visible minimum height of a pixel r with respect to the observation point p and taking into account only the occulting face o,
  • - FO represents the set of blackout faces.
  • the maps Hp, o (r) are calculated by orthogonal projections of the shadow volumes on the pixel matrix 46 located in the plane Pmin.
  • the map Hmin (r) associated with the current view cell is determined.
  • Hmin (r) min ⁇ Hp (r), PE ⁇ , where: 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 faces.
  • the fifth step of the first phase of calculating the list of objects. potentially visible is to determine the temporary list of potentially visible objects in relation to each view cell.
  • the faces of the generic objects 100, the enclosing volumes, and the terrain objects 104 are prolonged in the minimum altitude plane Pmin 103 zmin. Prisms are then obtained modeling the generic objects 100, the enclosing volumes, and the field objects 104.
  • the imprint of an extended object 305 corresponds to the projection on the plane Pmin of the generic object 100, the field object 104 or the enclosing volume of which it is the extension.
  • the altitude of an extended object 305 is equal to zmin.
  • the height of an extended object 305 is equal to the sum of the altitude and the height of the object (generic object, field object or enclosing volume) associated with it.
  • the set of extended objects 305 is obtained as illustrated in FIG. 10b. 305.
  • this visibility test is done by comparing the height of the extended object 305 and the minimum visible heights of the first map of the minimum visible heights of the pixels. intersecting with the footprint of the object.
  • a list of the potentially visible extended objects 305 is then obtained. Since each extended object 305 in the list is associated with an object of the scene or a field object, the temporary list of potentially visible objects is deduced.
  • the second phase of calculating the list of potentially visible objects includes a first step of choosing an erosion value e2.
  • This erosion value e2 is chosen low (in practice less than 1 meter) in order to reduce as much as possible the phenomenon of reduction of the occulting faces.
  • the recovery value k2 corresponding to the size of the pixels is deduced from the erosion value e2 by the formula connecting e and k: e ⁇ VJ-JZ.
  • the second visible minimum height map only covers part of the terrain. This part covered by the second card includes the current cell
  • the second step of the second phase consists in choosing the blackout faces.
  • the occulting objects determined during the fifth step of the method are used here.
  • the faces of the occulting objects and the faces of the pairs of related occulting objects are selected as occulting faces.
  • the merger of pairs of occulting objects is a special case of the fusion of groups of related occulting objects.
  • Let there be a pair of related occulting objects then we define their fusion as being the connected set defined by: - its footprint on the ground which is equal to the merging of the footprints, with deletion of the edges in common of the two related occulting objects - its height which equals at least the heights of the two related blackout objects.
  • the third step of the method consists in eroding the blackout faces by 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 is to compute the map of the minimum heights visible to the current view cell. This calculation is done in the same way as in the fourth step of the first phase. In this way, for each view cell, the second map of the visible minimum heights is obtained.
  • the fifth step of the second phase is to test the visibility of the objects in the scene to determine the list of potentially visible objects. This test is performed with respect to each view cell as a function of the second map of the visible minimum heights (associated with said cell). This test is performed on the objects of the temporary list of potentially visible objects and is a function of the distance of the objects relative to the area covered by the second map of the minimum visible heights.
  • the object is said to be potentially visible if the maximum height of the object
  • the associated prolonged 305 is greater than one of the pixel heights of the second map intersecting with the object's footprint. If the extended object 305 associated with the object under test does not intersect with the second map of the visible minimum heights, an encompassing volume of the extended object 305 is projected (see FIG. 2) over a visibility horizon. If the projection of the object is above the horizon of visibility 4, the tested object (generic object, field or specific) is said potentially visible.
  • the visibility calculation method for determining lists of potentially visible objects by region for very large 3D scenes representing virtual cities includes the following steps: a) calculating the minimum height of the urban scene : zmin, and the definition of a plane Pmin at the altitude zmin (step 70 of figure 14), b) the creation of terrain objects (step 71 of figure 14):
  • For each grid rectangle we associate a 3D block whose: • the lower base is the rectangle itself, the minimum altitude is equal to the minimum altitude of the terrain surface having a non-zero intersection with this block, the height is equal to the maximum elevation of the terrain surface having a non-zero intersection with this tile. This altitude is therefore also that of the upper base of the pavement, c)
  • the partition of the user's moving area (step 72 of FIG. 14):
  • the altitude of a cell is equal to the minimum of the minimum altitudes of terrain objects intersecting with the view cell, and the height of a view cell is equal to the reference height to which the maximum value of the objects is added. pit heights intersecting the cell, d) selecting a view cell (step 73 of Fig. 14):
  • k1 is calculated so that the first map of visible minimum heights covers the entire city.
  • the erosion value e1 is deduced from the recovery value k1, f)
  • the selection and erosion of the occulting faces (step 75 of FIG. 14):
  • the faces of the occulting objects are chosen as the occulting faces and the faces of the related sets resulting from the merging of the groups of related occulting objects are added thereto. g) Calculation of the first map of visible minimum heights
  • Hmin1 (r) associated with the current view cell (step 76 of FIG. 14): The computation is done by the operation of union and intersection of the shadow volumes generated by the occulting faces and the sampled points of the cell of view. The calculation is done using the hard-wired functions of the 3D graphics cards accessible by the OpenGL graphic library. To calculate the first map of the minimum heights, a grid is made in N rectangles (pixels) of the plane Pmin, the area occupied by each rectangle being a function of the recovery value k1, then for each rectangle the minimum height visible from the view cell (31, 107), h) determining the temporary list of potentially visible objects (step 77 of Fig. 14):
  • the visibility test of the extended objects is as follows: an object is said to be potentially visible if its maximum height is greater than one of the heights of the pixels of the card having an intersection with the footprint of the object.
  • the selected faces are the faces of the occulting objects and the faces of the fusions of all the pairs of related occulting objects.
  • k) The calculation of the second map of the visible minimum heights Hmin2 (r) associated with the current view cell (step 80 of FIG. 14): The calculation is done in the same way as in step g). The length and the width of the second card are a function of the recovery value k2.
  • a visibility test is carried out using the second map of the minimum visible heights.
  • the visibility test is only performed on the extended objects associated with objects in the temporary list of potentially visible objects according to the distance of the objects relative to the area covered by the map of the minimum visible heights. Indeed, if an object has an intersection with the area covered by the second map, then the object is said to be potentially visible if the maximum height of the extended object associated with it is greater than one of the heights of the second map of the minimum visible heights of the pixels having an intersection with the footprint of the object.
  • the enclosing volume of the object is projected on the horizon of visibility. If the projection of the object is above the horizon of visibility, the object is said to be potentially visible.
  • the method presented above can be implemented in a system for performing 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 a 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 forwards them online for example to a remote personal computer that 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)
  • Software Systems (AREA)
  • Remote Sensing (AREA)
  • Processing Or Creating Images (AREA)

Abstract

L'invention concerne un procédé de détermination de listes d'objets potentiellement visibles dans une scène 3D comprenant des objets (100) sur un terrain (101) d'altitude variable 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 (100), caractérisé en ce qu'il comprend les étapes consistant à créer des objets terrain (104) correspondant chacun à une partie du terrain, partitionner la zone de déplacement de l'utilisateur en un réseau de cellules de vue, déterminer, pour chaque cellule de vue, une liste d'objets potentiellement visibles par l'utilisateur depuis la cellule de vue, ladite liste étant déterminée en testant la visibilité des objets (100) de la scène et des objets terrain (104) créés.

Description

Procédé général 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 d'altitudes variables
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 d'altitudes variables. En imagerie de synthèse, Ie 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 la 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 englobants [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 une scène 3D représentant une ville virtuelle.
Dans ce type d'applications, 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 le 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 objets qui occultent le reste de la 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é est utilisable par exemple sur des bases de données urbaines, c'est-à-dire des scènes 3D représentant des villes virtuelles. Ces scènes comprennent des objets qui sont des bâtiments sur un terrain.
Ce procédé suppose que la base de données urbaine est plane, c'est- à-dire que le terrain sur lequel reposent les bâtiments est plat. Ce procédé suppose également que chaque bâtiment est représenté par un modèle 2D1A
Le modèle 2D1/4 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 1 , 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é 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 la 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/2 des bâtiments, l'opération d'érosion est réalisée sur l'empreinte au sol des bâtiments. La valeur d'érosion e (correspondant à l'amplitude d'érosion) est liée à la valeur de recouvrement (correspondant à la taille d'un pixel) notée k par la relation suivante : e >k / +Jl. 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. Pour chaque cellule de vue, le test de visibilité sur les objets de Ia scène 3D est le suivant.
Pour les objets contenus dans la zone recouverte par la carte des hauteurs minimales visibles, le test de visibilité se fait par comparaison entre la hauteur d'une 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 de la zone recouverte par la carte des hauteurs minimales visibles, le test de la visibilité est illustré à la figure 2. Wonka propose la modification suivante de son procédé : les frontières de la carte des hauteurs minimales visibles 1 permettent de définir une 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. Le procédé ne prend pas en compte les données terrain
En effet, le procédé de Peter Wonka suppose que le terrain est plat. Ceci implique que le procédé de Peter wonka ne prend en compte les données terrain ni pour les phénomènes d'occultation, ni pour les tests de visibilité.
Or en pratique, le terrain est très souvent en relief. Ainsi, certaines parties du terrain peuvent occulter des zones de la scène. Par exemple, un utilisateur qui se trouve devant une colline ne voit pas ce qui se trouve derrière la colline.
Par ailleurs, certaines zones de la scène peuvent être visibles depuis certaines parties en relief du terrain. Par exemple, le nombre de bâtiments visibles pour un utilisateur qui se trouve au sommet d'une colline sera plus important que le nombre de bâtiments visibles pour un utilisateur qui se trouve au fond d'un trou. ii. Le procédé ne prend pas en compte les bâtiments d'altitudes différentes.
En effet, comme précédemment décrit, le procédé de Peter Wonka suppose que le terrain est plat, et donc que les bâtiments sont tous à la même altitude. iii. Le procédé ne prend pas en compte les données de type mobilier urbain, la végétation, les panneaux de signalisation et les bâtiments spécifiques.
En effet, le procédé de Peter Wonka ne prend en compte que les bâtiments représentés avec un modèle 2D1A Ainsi, il ne prend pas en compte les objets de type mobilier urbain comme les abris de bus, les bancs, les panneaux publicitaires ou les panneaux de signalisation. Il ne prend pas non plus en compte la végétation comme les arbres, ou les bosquets. Pour plus de réalisme une base de donnée urbaine devrait prendre en compte toutes ces données.
Le procédé de Peter Wonka ne prend pas non plus en compte les bâtiments spécifiques, c'est-à-dire des bâtiments modélisés à l'aide d'autres modèles que le modèle 2D1A En effet, pour des types de bâtiments comme des églises ou des monuments, le modèle 2 D/4 n'est pas adapté pour la visualisation. Pour représenter tous ces bâtiments spécifiques, on utilise par exemple un modèle facette 3D.
Pour plus de réalisme il faudrait prendre en compte ces bâtiments spécifiques pour les tests de visibilité. iv. La zone de recouyrement de la carte des hauteurs minimales visibles ne couyre qu'une partie de la ville.
En effet, pour ne pas trop réduire les faces 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 à ^β mètre. En effet, les valeurs k et e sont liées par la relation e ≥k/ y/2. 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 à
Figure imgf000011_0001
e doit être supérieure ou égale à 2 mètres. Dès lors, plus la valeur de e est grande et plus les faces occultantes seront réduites et donc moins le phénomène d'occultation sera pris en en compte. Par exemple, une amplitude d'érosion de 2 mètres enlève 4 mètres par face de bâtiment. v. Le procédé de Wonka ne prend pas en compte l'occultation inter¬ bâtiment sur toute la base de données 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. vi. 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 3, 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). vii. 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 Ia 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 4, 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ètre é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é général 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 d'altitudes variables permettant de pallier la plupart des inconvénients précités.
PRESENTATION DE L1INVENTION
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 d'altitude variable 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 à :
- créer des objets terrain correspondant chacun à une partie du terrain, - partitionner la zone de déplacement de l'utilisateur en un réseau de cellules de vue, - déterminer, pour chaque cellule de vue, une liste d'objets potentiellement visibles par l'utilisateur depuis la cellule de vue, ladite liste étant déterminée en testant la visibilité des objets de la scène et des objets terrain créés. La présente invention permet ainsi de traiter les cas d'environnements urbains réels pour lesquels l'effet du relief naturel est loin d'être négligeable. La création de pavés terrain permet de prendre en compte l'occultation engendrée par le relief du terrain. La présente invention permet de prendre en compte des données urbaines complémentaires (mobilier urbain, végétation, signalisation et donnée terrain) dans la visibilité. Le procédé de la présente invention est totalement indépendant des ressources mémoire par rapport à la taille des bases puisque la taille des rectangles du quadrillage est adaptée 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 selon l'invention sont les suivants : le procédé comprend en outre une étape consistant à :
- calculer une altitude minimale zmin du terrain afin de définir un plan Pmin à l'altitude minimale zmin ; l'étape consistant à créer des objets terrain comprend les sous étapes consistant à : - effectuer un quadrillage en M rectangles du plan Pmin sur toute la surface du terrain,
- associer un prisme appelé objet terrain à chaque rectangle du quadrillage, le prisme étant défini par une base, jαne altitude et une hauteur, la base du prisme étant le rectangle, l'altitude du prisme étant égale à l'altitude minimale de la surface du terrain ayant une intersection non nulle avec le prisme, et la hauteur du prisme étant égale à l'altitude maximale de la surface du terrain ayant une intersection non nulle avec le prisme ; l'étape consistant à partitionner la zone de déplacement de l'utilisateur en un réseau de cellules de vue comprend les sous étapes consistant à :
- translater dans le plan Pmin la zone de déplacement de l'utilisateur, - partager le translaté de la zone de déplacement en un réseau de triangle,
- extruder un prisme représentant la cellule de vue sur chaque triangle, la hauteur de la cellule de vue étant égale à une hauteur de référence à laquelle on ajoute la valeur maximale des hauteurs des objets terrain ayant une intersection non nulle avec le prisme ; la scène comprend des objets génériques définis par une empreinte, une altitude et une hauteur, et en ce que le procédé comprend en outre une étape de transformation des objets génériques, et des objets terrain en objets occultants modélisés 2D1/2 en : - prolongeant verticalement les faces des objets génériques jusqu'à l'altitude zmin, chaque objet occultant ainsi obtenu étant défini par une empreinte correspondant à la projection de l'objet générique sur le plan Pmin, une altitude égale à zmin et une hauteur égale à la somme de l'altitude et de la hauteur de l'objet générique, - prolongeant verticalement les bases des objets terrain jusqu'à l'altitude zmin, chaque objet occultant ainsi obtenu étant défini par une empreinte correspondant à la projection de l'objet terrain sur le plan Pmin, une altitude zmin et une hauteur égale à l'altitude de l'objet terrain dont il est le prolongement ; la scène comprend des objets spécifiques modélisés par un assemblage de polygones, et en ce que le procédé comprend en outre une étape consistant à transformer les objets spécifiques, les objets génériques et les objets terrain en objets prolongés modélisés 2D1/2, ladite étape comprenant :
- la définition d'un volume englobant pour chaque objet spécifique de la scène,
- la transformation des objets génériques, des objets terrain et des volumes englobants en objets prolongés modélisés 2D1/4, ladite transformation consistant à prolonger les faces des objets génériques, des objets terrain et des volumes englobants jusqu'au plan Pmin, chaque objet prolongé ainsi obtenu étant défini par une empreinte égale à la projection sur le plan Pmin de l'objet générique, de l'objet terrain ou du volume englobant qui lui est associé, par une altitude égale à zmin et une hauteur égale à la somme de l'altitude et de la hauteur de l'objet générique, de l'objet terrain ou du volume englobant qui lui est associé ; l'étape consistant à déterminer, pour chaque cellule de vue, une liste d'objets potentiellement visibles comprend les sous étapes consistant à :
- calculer une première carte de hauteurs minimales visibles, ladite carte étant obtenue en : o effectuant un quadrillage en N rectangles du plan Pmin, la surface occupée par chaque rectangle étant fonction d'une valeur de recouvrement k1 choisie de sorte que le quadrillage recouvre toute la surface du terrain, o sélectionnant des faces occultantes, notamment parmi les faces des 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 la cellule de vue, - déterminer une liste temporaire d'objets potentiellement visibles en comparant, pour chaque objet de la scène et chaque objet terrain, la hauteur de l'objet prolongé associé et les hauteurs minimales de la première carte des rectangles ayant une intersection avec l'empreinte de l'objet prolongé, - calculer une deuxième carte des hauteurs minimales visibles, ladite carte étant obtenue en : o effectuant un quadrillage en N rectangles du plan Pmin sur une partie du terrain, ladite partie incluant la base de la cellule de vue 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, notamment parmi les faces 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 la cellule de vue,
- déterminer la liste des objets potentiellement visibles en comparant, pour chaque objet de la liste temporaire d'objets potentiellement visibles, la hauteur de l'objet prolongé associé et les hauteurs minimales de la deuxième carte des rectangles ayant une intersection avec l'empreinte de l'objet prolongé ; le procédé comprend en outre une étape de fusion d'objets occultants connexes afin d'obtenir des ensembles connexes, ladite étape de fusion étant réalisée préalablement à l'étape de sélection des faces occultantes, et consistant à : - déterminer des groupes d'objets occultants vérifiant des conditions de connexité,
Puis pour chaque groupe d'objets occultants connexes, déterminer un ensemble connexe en : - supprimant des empreintes des objets les arrêtes qu'elles ont en commun afin d'obtenir une empreinte unique qui est assignée à l'ensemble connexe,
- déterminer, parmi les objets du groupe, celui dont la hauteur est la plus petite et assigner sa hauteur à l'ensemble connexes ; - les conditions de connexité à vérifier par un ensemble d'objets 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 : 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 k1 est supérieure ou égale au maximum entre le rapport de la largeur du terrain par le nombre de rectangles utilisables en ligne, et le rapport de longueur du terrain par 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 : el ≥k1/\2 ; 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 de e2 choisie en utilisant la relation liant la valeur d'érosion e2 à la valeur de recouvrement k2 : a >k2Λβ ; l'étape consistant à sélectionner des faces occultantes, notamment parmi les faces des objets occultants (300, 301 ), consiste à :
- sélectionner l'ensemble des faces des objets occultants (300, 301), - sélectionner l'ensemble des faces des ensembles d'objets occultants connexes ; l'étape consistant à éroder les faces occultantes par une valeur d'érosion e consiste à éroder les empreintes au sol des objets occultants et des ensembles d'objets occultants connexes par la valeur d'érosion e ;
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 à créer des objets terrain correspondant chacun à une partie du terrain,
- des moyens aptes à partitionner la zone de déplacement de l'utilisateur en un réseau de cellules de vue,
- des moyens aptes à déterminer, pour chaque cellule de vue, une liste d'objets potentiellement visibles par l'utilisateur depuis la cellule de vue, ladite liste étant déterminée en testant la visibilité des objets de la scène et des objets terrain créés.
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 d'un objet modélisé 2OV2 ; - la figure 2 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 3 est une vue de face de trois objets avant et après une opération d'érosion ;
- la figure 4 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 5 est une vue en perspective d'une scène sur laquelle se trouve un utilisateur, ladite scène comprenant une face occultante d'un objet occultant, un objet visible et un objet non visible ;
- la figure 6 est une vue en perspective d'une scène comprenant des objets sur un terrain d'altitude variable ;
- Ia figure 7 est une vue de face d'une scène comprenant des objets sur un terrain d'altitude variable ;
- la figure 8 est une illustration d'une é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 partition triangulaire obtenue par triangulation ;
- la figure 9 est une vue en perspective d'une cellule de vue chevauchant deux objets terrain ; - la figure 10a est une vue de face d'objets occultants modélisés
2DY2 obtenus à partir d'objets génériques de la scène et des objets terrain ;
- la figure 10b est une vue de face d'objets prolongés modélisés 2DVz obtenus à partir des objets de la scène et des objets terrain ; - la figure 11 est une première illustration de l'étape de fusion d'objets occultants connexes et comprend une vue de dessus de trois empreintes d'objets occultants connexes, et une vue de dessus d'une empreinte résultant de la fusion des empreintes des trois objets occultants connexes ;
- la figure 12 est une seconde illustration de l'étape de fusion d'objets occultants connexes et comprend une vue de face de trois objets occultants connexes, et une vue de face de l'objet résultant de la fusion des trois objets occultants connexes ;
- la figure 13 est une vue de dessus d'une scène sur laquelle se trouve un utilisateur et deux faces occultantes d'objets occultants ; - la figure 14 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é général 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 d'altitudes variables.
Ainsi, le procédé de calcul de visibilité présenté ci-après permet de déterminer des listes d'objets potentiellement visibles dans des scènes urbaines de taille réelle de l'ordre de 8km*8km comprenant des objets, représentant notamment des bâtiments, sur un terrain d'altitude variable. De plus ce procédé prend en compte les effets du terrain pour les calculs d'occultations et de visibilité. Enfin le procédé intègre pour les tests de visibilité tout type d'objet (mobilier urbain, végétation ...).
Pour cela, les inventeurs sont partis de la constatation qu'au niveau du sol très peu d'objets d'une scène comme du mobilier urbain sont visibles en raison de l'occultation inter-objet.
En effet, comme représenté à la figure 5, en un point d'observation 20 situé proche d'une face 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 représentant une ville 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 dans une scène est un problème complexe que l'on ne peut résoudre sans hypothèse.
En référence à la figure 6, les hypothèses du procédé sont les suivantes : - les objets de la scène (bâtiments, signalisation, arbre, ...) sont
représentés dans un repère orthonormée directe (O, X, y, Z) ;
- l'ensemble des objets d'une scène, est composé : o d'objets génériques 100, c'est-à-dire d'objets représentés par un modèle 2D/4 (à savoir une empreinte au sol, une altitude et une hauteur), ces objets génériques 100 sont des bâtiments ; par ailleurs, les empreintes des objets
— > — » génériques sont parallèles au plan (O1-X y) et leur altitude est variable ; o d'objets spécifiques, c'est-à-dire d'objets modélisés par assemblage de polygones (modèle facettes 3D), ces objets spécifiques sont des bâtiments spécifiques (églises, monuments ...), du mobilier urbain (abris de bus, bancs, feux, stops ...), et de la végétation (arbres) ; o d'un terrain 101 (relief numérisé) modélisé par assemblage de polygones ;
- chaque objet générique 100 peut être associé à un toit 102 modélisé par assemblage de polygones ;
- les objets de la scène sont inclus dans une boite de dimension (Δx, Δy) ; - le nombre de pixels utilisable pour la carte des hauteurs minimales visibles est égal à (Nx, Ny) ;
Comme l'homme de l'art l'aura compris, le procédé de calcul de visibilité permet de traiter des données numériques. Ces données numériques sont caractéristiques d'objets virtuels, par exemple des bâtiments, des abris bus, ou un terrain.
Pour représenter virtuellement une ville en 3D, on utilise un terminal mobile ou fixe comme une station de travail, ledit terminal comprenant des moyens mémoire pour stocker une base de données comprenant ces données numériques.
Par exemple, en ce qui concerne le terrain, celui-ci est modélisé par assemblage de polygones. Pour définir un polygone, il est nécessaire de connaître certaines informations. Ces informations peuvent par exemple être
les coordonnées dans le repère (O, X, y, Z) de trois points caractéristiques du polygone.
Pour chaque polygone, les données numériques associées à celui-ci comprennent ces informations. Ces données numériques sont stockées dans Ia base de données de la station de travail, avec d'autres informations concernant le polygone comme sa texture par exemple. A partir de ces données numériques, les moyens de traitement de l'unité centrale sont capables de calculer la position de l'ensemble des points du polygone à afficher. En affichant l'ensemble des points de l'ensemble des polygones sur des moyens d'affichage de la station de travail, on obtient une représentation du terrain. Dans la suite, on présentera le procédé de calcul de visibilité en faisant référence aux objets (terrain, bâtiments, mobilier urbain) plutôt qu'en faisant référence aux données numériques associées sur lesquelles sont effectués les traitements. En référence à la figure 7, la première étape du procédé consiste à calculer l'altitude minimale du terrain de la scène. Dans la suite, cette altitude minimale sera appelée altitude zmin.
La deuxième étape du procédé consiste à définir un plan Pmin 103 à l'altitude zmin. Ce plan sera utilisé dans certaines des étapes suivantes du procédé.
La troisième étape du procédé consiste à calculer des objets terrain 104 modélisés 2D1A Ces objets terrain sont calculés afin notamment de prendre en compte l'occultation d'objets engendrée par le terrain. Pour créer ces objets terrain 104, on définit un quadrillage régulier 2D du plan Pmin 103. A chaque rectangle de la grille, on associe un pavé 3D dont : la base inférieure est le rectangle lui-même, l'altitude minimale 105 est égale à l'altitude minimale de Ia surface du terrain ayant une intersection non nulle avec ce pavé, la hauteur 106 est égale à l'altitude maximale de la surface du terrain ayant une intersection non nulle avec ce pavé.
Ces pavés 3D sont appelés objets terrain et seront ensuite utilisés dans le procédé de calcul de visibilité. La quatrième étape du procédé consiste à réaliser une partition de l'espace d'observation proche du sol en régions appelées celluies 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 8, dans une application de visualisation d'environnements urbains, l'espace 25 dans lequel l'observateur virtuel peut se déplacer est égal au complémentaire de l'union de tous les objets 26, 27, 28, 29 de la scène.
La partition de la zone de déplacement de l'utilisateur est obtenue très simplement comme suit. On translate le terrain et les objets de la scène dans le plan Pmin 103. Puis, on effectue une triangulation 2D du complémentaire
(translaté à l'altitude z = zmin) des empreintes au sol des objets de la scène. 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 sont appelés cellules de vue 31.
Comme illustré à Ia figure 9, l'altitude 108 d'une cellule 107 est égale au minimum 109 des altitudes des bases inférieures 109, 110 des objets terrain 111 , 112 ayant une intersection avec la cellule de vue 107, et la hauteur d'une cellule de vue 107 est égale à une hauteur de référence 113 (comprise entre 0 et 2 mètre à l'échelle de la ville) à laquelle on ajoute la valeur maximale 114 des hauteurs 114, 115 des objets terrain ayant une intersection avec la cellule.
En référence à la figure 10a, la cinquième étape du procédé consiste à transformer les objets génériques 100 et les objets terrain 104 de la scène en objets occultants 300, 301 de même altitude zmin. Ces objets occultants sont modélisés 2D1A En effet, le modèle 2D1/4 simplifie les calculs de visibilité. Ces objets occultants 300, 301 seront utilisés lors du calcul de cartes des hauteurs minimales visibles.
Pour transformer les objets génériques 100 en objets occultants 301 , on prolonge les faces des objets génériques 100 dans le plan Pmin 103 d'altitude zmin. On obtient alors des prismes modélisant les objets génériques prolongés. Ces prismes sont appelés objets occultants 301.
L'empreinte d'un objet occultant 301 correspond à la projection sur le plan Pmin de l'objet générique dont il est le prolongement. Tous ces objets occultants 301 ont la même altitude zmin. La hauteur d'un objet occultant
301 est égale à la somme de l'altitude et de la hauteur du objet 100 qui lui est associé.
Pour transformer les objets terrain 104 en objets occultants 300, on prolonge verticalement les empreintes des objets terrain 104 dans le plan Pmin 103. On obtient alors des prismes modélisant les objets terrain prolongés. Ces prismes sont appelés objets occultants 300. L'empreinte d'un objet occultant 301 est égale à l'empreinte de l'objet terrain 104 translatée à l'altitude zmin, l'altitude est égale à zmin, et la hauteur est égale à l'altitude de l'objet terrain 104.
On obtient alors l'ensemble d'objets occultants 300, 301 tel qu'illustré à la figure 10a.
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 (objets de la scène et objets terrain) 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-objet lointaine et calcule, pour chaque cellule de vue, une liste temporaire d'objets potentiellement visibles à l'aide d'une première carte des hauteurs minimales visibles. Cette carte est obtenue en effectuant un quadrillage dans le plan Pmin de la surface du terrain, les dimensions (longueur, largeur) de cette première carte étant fonction d'une valeur de recouvrement k1.
Ensuite une deuxième phase permet de prendre en compte de façon efficace l'occultation inter-objet proche, et calcule, pour chaque cellule de vue, la liste des objets potentiellement visibles à l'aide d'une deuxième carte des hauteurs minimales visibles. Cette carte est obtenue de la même manière que précédemment. Les dimensions (longueur, largeur) de cette deuxième carte sont fonction d'une valeur de recouvrement k2. Dans cette deuxième phase, les tests de visibilité se font uniquement sur les objets de la liste temporaire calculée 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. Cette valeur de recouvrement est choisie en fonction de la surface occupée par le terrain. La surface occupée par un pixel dépend de cette valeur de recouvrement k1. Afin de pouvoir prendre en compte tous les phénomènes d'occultations inter-objet, on choisit la valeur de recouvrement k1 de telle sorte que la première carte des hauteurs minimales visibles recouvre toute la ville. Pour cela la valeur de recouvrement k1 doit être tel que : k1 >max(Δx/Nx, Δy/Ny). Où :
- Δx et Δy sont les largeur et longueur du terrain,
- Nx, Ny sont le nombre de pixels utilisable en ligne et en colonne pour le calcul des cartes des hauteurs minimales visibles.
Connaissant la valeur de recouvrement k1 , on en déduit la valeur d'érosion el qui doit être supérieure ou égale à YΛIsJl. En effet, la valeur de recouvrement k1 et la valeur d'érosion el sont liées par la relation: el ≥k1Λ£. On remarque, que la valeur de l'érosion à appliquer sera grande. Par exemple, si on suppose une ville de dimension 8km*8km, et si on suppose que l'on dispose d'un moyen de traitement graphique 3D nous permettant d'utiliser 1280*1024 pixels pour le calcul de la première carte des hauteurs minimales visibles. Alors les valeurs de k1 et el deviennent : k1 = max(8000/1280, 8000/1024) = 6.25 mètres el = 6.25/^ = 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 faces occultantes.
Dans son procédé, Peter Wonka prend comme faces occultantes toutes les faces des objets génériques.
Dans le présent procédé, on choisira comme faces occultantes toutes les faces des objets occultants 300, 301 , c'est-à-dire les faces des objets génériques prolongés et des objets terrain prolongés. A cet ensemble, on ajoute également les faces de groupes d'objets occultants fusionnés. Pour obtenir des groupes d'objets occultants fusionnés, on utilise la méthode de fusion décrite ci après. « Soit un ensemble B d'objets modélisés 2DA1 , alors on peut réaliser une partition (au sens ensembliste), de tous les objets, 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 dit 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 d'objets occultants 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 d'objets occultants tel que défini précédemment. Alors le résultat de la fusion de tous les objets occultants connexes est un ensemble connexe défini de la façon suivante :
- son empreinte au sol est le résultat de la fusion des empreintes des objets occultants obtenue par suppression des arrêtes en communs,
- sa hauteur est égale au minimum des hauteurs de toutes les hauteurs de tous les objets occultants.
En effet, comme représenté à la figure 11 , trois objets occultants 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 de l'ensemble connexe. Par ailleurs, comme représenté à la figure 12, trois objets occultants
38, 39, 40 ayant des faces 41 , 42 en commun vont être fusionnés par suppression de leurs faces en commun 41 , 42. La hauteur de l'ensemble connexe 141 obtenue par fusion des objets occultants 38, 39, 40 sera égale à la hauteur de l'objet occultant 38 qui est le moins haut des trois objets occultants 38, 39, 40. Ainsi, l'étape de sélection des faces occultantes consiste à sélectionner toutes les faces des objets occultants 300, 301 , et les faces des ensembles 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 faces occultantes. Ceci permet de corriger des 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 2D1/4 des objets occultants et des ensembles connexes, l'érosion par e1 se fait sur l'empreinte au sol des objets occultants et des ensembles connexes.
La quatrième étape de la première phase du calcul de Ia liste des objets potentiellement visibles consiste à calculer la première carte des hauteurs minimales visibles pour la cellule de vue courante. Le calcul d'une 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. Cette approximation consiste à échantillonner par des points les arrêtes de la face supérieure de la cellule de vue courante et à calculer une 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.
Pour calculer une carte des hauteurs minimales visibles Hp(r) depuis un point d'observation p donné, on définit la notion de volume d'ombre comme suit : « Soit un point d'observation 20 (cf. figure 5) et soit une face 21 d'un objet occultant modélisée par un rectangle perpendiculaire au sol, alors on appelle volume d'ombre 22 la pyramide tronquée définie par les quatre demi- droites passant par le point d'observation 20 et les quatre sommets de la face 21. »
Ce volume d'ombre 22 garantit que tout objet 23 entièrement contenu dans ce volume 3D n'est pas visible depuis le point d'observation 43.
Dès lors la carte Hp(r) des hauteurs minimales visibles par rapport au point d'observation p 43 (cf. figure 13) se déduit des volumes d'ombres 45, 48 par projection orthogonale sur une matrice 46 de pixels des volumes d'ombres 45, 48 engendrés par les faces occultantes 44, 47.
Pour calculer la carte Hp(r) prenant en compte l'ensemble des faces occultantes par rapport au point d'observation p, on procède de la manière suivante. On détermine l'ensemble des cartes Hp,o(r) ne prenant en compte qu'une face occultante o parmi l'ensemble FO des faces occultantes par rapport au point d'observation p. Ensuite, on calcule la carte Hp(r).
En effet, la carte Hp(r) associée à l'ensemble des cartes Hp,o(r) de toutes les faces occultantes o est donnée par la formule :
Hp(r) = max {Hp,o(r), o ε FO}, Où :
- Hp(r) est Ia 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 minimum visible d'un pixel r par rapport au point d'observation p et en ne prenant en compte que la face occultante o,
- FO représente l'ensemble des faces occultantes.
Les cartes Hp,o(r) sont calculées par projections orthogonales des volumes d'ombres sur la matrice de pixels 46 située dans le plan Pmin.
Or la discrétisation sur une grille de pixels engendre des erreurs. C'est Ia raison pour laquelle on effectue l'opération d'érosion mathématique préalablement au calcul dθ la première carte des hauteurs minimales 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 faces occultantes. La cinquième étape de la première phase du calcul de la liste des objets . potentiellement visibles consiste à déterminer la liste temporaire des objets potentiellement visibles par rapport à chaque cellule de vue.
Dans un premier temps, on commence par transformer les objets génériques (bâtiments 100), les objets spécifiques, et les objets terrain en objets prolongés modélisés 2D1A
Pour cela, on détermine pour chaque objet spécifique modélisé par assemblage de polygone, un volume englobant.
Ensuite, et comme illustré à la figure 10b, on prolonge les faces des objets génériques 100, des volumes englobants, et des objets terrain 104 dans le plan Pmin 103 d'altitude minimum zmin. On obtient alors des prismes modélisant les objets génériques 100, les volumes englobant, et les objets terrain 104.
Ces prismes sont appelés objets prolongés 305. L'empreinte d'un objet prolongé 305 correspond à la projection sur le plan Pmin de l'objet générique 100, de l'objet terrain 104 ou du volume englobant dont il est le prolongement. L'altitude d'un objet prolongé 305 est égale à zmin. La hauteur d'un objet prolongé 305 est égale à la somme de l'altitude et de la hauteur de l'objet (objet générique, objet terrain ou volume englobant) qui lui est associé.
Ainsi, contrairement à l'étape de détermination de la première carte des hauteurs minimales visibles où c'était l'altitude de l'objet terrain qui était prise en compte dans les phénomènes d'occultation, ici c'est la hauteur de l'objet terrain qui est prise en compte pour les tests de visibilité.
On obtient l'ensemble d'objets prolongés 305 tel qu'illustré à la figure 10b. On effectue ensuite un test de visibilité des objets prolongés 305. Pour chaque objet prolongé 305, ce test de visibilité se fait par comparaison entre la hauteur de l'objet prolongé 305 et les hauteurs minimales visibles de la première carte des hauteurs minimales visibles des pixels ayant une intersection avec l'empreinte au sol de l'objet. Pour chaque cellule de vue, on obtient alors une liste des objets prolongés 305 potentiellement visibles. Comme chaque objets prolongés 305 de la liste est associé à un objet de la scène ou à un objet terrain, on déduit la liste temporaire d'objets potentiellement visibles.
A la fin de la première phase, on obtient donc pour chaque cellule de vue une liste temporaire des objets potentiellement visibles qui est un sur¬ ensemble de la liste minimale puisque calculée avec un e1 grand. Ainsi, lors de la deuxième phase, on ne testera que la visibilité des objets appartenant à la liste temporaire des objets potentiellement visibles obtenue à la 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 faces occultantes. La valeur de recouvrement k2 correspondant à la taille des pixels se déduit de la valeur d'érosion e2 par la formule reliant e et k : e ≥VJ-JZ. Comme la valeur d'érosion e2 est faible, alors la valeur de recouvrement k2 est faible (inférieur à k1 ). Par conséquent, la deuxième carte des hauteurs minimales visibles ne couvre plus qu'une partie du terrain. Cette partie couverte par la deuxième carte comprend la cellule courante La deuxième étape de la deuxième phase consiste à choisir les faces occultantes.
On utilise ici les objets occultants déterminés lors de la cinquième étape du procédé.
On sélectionne comme faces occultantes les faces des objets occultants et les faces des couples d'objets occultants connexes.
La fusion de couples d'objets occultants est un cas particulier de la fusion de groupes d'objets occultants connexes. Soit un couple d'objets occultants connexes, alors on définit leur fusion comme étant l'ensemble connexe défini par : - son empreinte au sol qui est égale à la fusion des empreintes au sol, avec suppression des arrêtes en commun des deux objets occultants connexes, - sa hauteur qui égale au minimum des hauteurs des deux objets occultants 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, pour chaque cellule de vue, la deuxième carte des hauteurs minimales visibles.
La cinquième étape de la deuxième phase consiste à tester la visibilité des objets de la scène afin de déterminer la liste des objets potentiellement visibles. Ce test est réalisé par rapport à chaque cellule de vue en fonction de la deuxième carte des hauteurs minimales visibles (associée à ladite cellule). Ce test est réalisé sur les objets de la liste temporaire d'objets potentiellement visibles et est fonction de la distance des objets par rapport à la zone recouverte par la deuxième carte des hauteurs minimales visibles.
En effet si l'objet prolongé 305 associé à l'objet (objet générique, spécifique ou terrain) testé a une intersection avec la deuxième carte des hauteurs minimales visibles, alors l'objet est dit potentiellement visible si la hauteur maximale de l'objet prolongé 305 qui lui est associé est supérieure à l'une des hauteurs des pixels de la deuxième carte ayant une intersection avec l'empreinte au sol de l'objet. Si l'objet prolongé 305 associé à l'objet testé n'a pas d'intersection avec la deuxième carte des hauteurs minimales visibles, un volume englobant de l'objet prolongé 305 est projeté (voir figure 2) sur une horizon de visibilité 4. Si la projection de l'objet se trouve au-dessus de l'horizon de visibilité 4, l'objet testé (objet générique, terrain ou spécifique) est dit potentiellement visible.
En résumé, 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) le calcul de la hauteur minimale de la scène urbaine : zmin, et la définition d'un plan Pmin à l'altitude zmin (étape 70 de la figure 14), b) la création d'objets terrain (étape 71 de la figure 14) : Les objets terrain sont obtenus par quadrillage du plan z= zmin. A chaque rectangle du quadrillage, on associe un pavé 3D dont : • la base inférieure est le rectangle lui-même, l'altitude minimale est égale à l'altitude minimale de la surface du terrain ayant une intersection non nulle avec ce pavé, la hauteur est égale à l'altitude maximale de la surface du terrain ayant une intersection non nulle avec ce pavé. Cette altitude est donc aussi celle de la base supérieure du pavé, c) La partition de la zone de déplacement de l'utilisateur (étape 72 de la figure 14) :
La partition en cellules de vue est obtenue par extrusion de prismes sur les triangles résultant de la triangulation de la zone de déplacement de l'utilisateur translatée à l'altitude z = zmin. L'altitude d'une cellule est égale au minimum des altitudes minimales des objets terrain ayant une intersection avec la cellule de vue, et la hauteur d'une cellule de vue est égale à la hauteur de référence à laquelle on ajoute la valeur maximale des hauteurs des pavés ayant une intersection avec la cellule, d) La sélection d'une cellule de vue (étape 73 de la figure 14) :
On échantillonne par e l'arrête supérieure de la cellule de vue courante, e) Le calcul de la taille d'un pixel (k1 ) et de la valeur d'érosion (e1) associée (étape 74 de la figure 14) : k1 est calculée de telle sorte que la première carte des hauteurs minimales visibles recouvre toute la ville. La valeur d'érosion e1 se déduit de Ia valeur de recouvrement k1 , f) La sélection et l'érosion des faces occultantes (étape 75 de la figure 14) :
Pour cela, on transforme les objets générique et les objets terrain en objets occultants modélisés 2D1A
Ensuite, on sélectionne les faces occultantes. On choisit comme faces occultantes toutes les faces des objets occultants et on y ajoute les faces des ensembles connexes issus de la fusion des groupes d'objets occultants connexes. g) Le calcul de la première carte des hauteurs minimales visibles
Hmin1 (r) associée à la cellule de vue courante (étape 76 de la figure 14) : Le calcul se fait par l'opération d'union et d'intersection des volumes d'ombres générés par les faces 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. Pour calculer la première carte des hauteurs minimales, on effectue un quadrillage en N rectangles (pixels) du plan Pmin, la surface occupée par chaque rectangle étant fonction de la valeur de recouvrement k1 , puis on calcule pour chaque rectangle la hauteur minimale visible depuis la cellule de vue (31 , 107), h) La détermination de la liste temporaire d'objets potentiellement visible (étape 77 de la figure 14) :
Pour déterminer cette liste, on effectue un test de visibilité des objets prolongés (transformé 2D Vz des objets terrain, des volumes englobants et des objets spécifique et générique) à l'aide de la première carte des hauteur minimales visibles.
Le test de visibilité des objets prolongés est le suivant : un objet est dit potentiellement visible si sa hauteur maximale est supérieure à l'une des hauteurs des pixels de Ia carte ayant une intersection avec l'empreinte au sol de l'objet.
Si un objet terrain est potentiellement visible alors, toute la surface du sol contenue dans cet objet terrain sera considérée comme potentiellement visible.
En ce qui concerne les objets génériques rehaussés avec un toit, le test se fait sur le volume englobant de l'union de l'objet et du toit. i) Le choix d'une valeur faible d'érosion e2 et la déduction de la taille d'un pixel k2 (étape 78 de la figure 14) : En pratique Ia valeur d'érosion e2 est inférieure à 1 mètre. j) La sélection et l'érosion des faces occultantes (étape 79 de la figure 14) :
Les faces sélectionnées sont les faces des objets occultants et les faces des fusions de tous les couples d'objets occultants connexes. k) Le calcul de la deuxième carte des hauteurs minimales visibles Hmin2(r) associée à la cellule de vue courante (étape 80 de la figure 14) : Le calcul se fait de la même manière qu'à l'étape g). La longueur et la largeur de la deuxième carte sont fonction de la valeur de recouvrement k2. I) La détermination de la liste des objets potentiellement visibles (étape 81 de la figure 14) :
Pour cela, on effectue un test de visibilité à l'aide de la deuxième carte des hauteurs minimales visibles. Le test de visibilité ne se fait que sur les objets prolongés associés aux objets de la liste temporaire d'objet potentiellement visibles 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 couverte par la deuxième carte, alors l'objet est dit potentiellement visible si la hauteur maximale de l'objet prolongé qui lui est associé est supérieure à l'une des hauteurs de la deuxième carte des hauteurs minimales visibles 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 d) à I) 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 comprenant des objets (100) sur un terrain (101) d'altitude variable et dans laquelle un utilisateur est susceptible de se déplacer virtuellement sur une zone de déplacement (25) correspondant à l'ensemble des zones du terrain non recouvertes par les objets (100), caractérisé en ce qu'il comprend les étapes consistant à : - créer des objets terrain (104) correspondant chacun à une partie du terrain,
- partitionner la zone de déplacement (25) de l'utilisateur en un réseau de cellules de vue (31 , 107),
- déterminer, pour chaque cellule de vue (31 , 107), une liste d'objets potentiellement visibles par l'utilisateur depuis la cellule de vue, ladite liste étant déterminée en testant la visibilité des objets de la scène et des objets terrain créés.
2. Procédé selon la revendication 1 , caractérisé en ce qu'il comprend en outre une étape consistant à :
- calculer une altitude minimale zmin du terrain (101 ) afin de définir un plan Pmin à l'altitude minimale zmin.
3. Procédé selon la revendication 2, caractérisé en ce que l'étape consistant à créer des objets terrain (104) comprend les sous étapes consistant à :
- effectuer un quadrillage en M rectangles du plan Pmin sur toute la surface du terrain (101),
- associer un prisme appelé objet terrain (104) à chaque rectangle du quadrillage, le prisme étant défini par une base, une altitude et une hauteur, la base (105) du prisme étant le rectangle, l'altitude du prisme étant égale à l'altitude minimale de la surface du terrain ayant une intersection non nulle avec le prisme, et la hauteur du prisme étant égale à l'altitude maximale de la surface du terrain ayant une intersection non nulle avec le prisme.
4. Procédé selon la revendication 2 ou 3, caractérisé en ce que l'étape consistant à partitionner la zone de déplacement (25) de l'utilisateur en un réseau de cellules de vue (31 , 107) comprend les sous étapes consistant à : - translater dans le plan Pmin la zone de déplacement (25) de l'utilisateur,
- partager le translaté de la zone de déplacement en un réseau de triangles,
- extruder un prisme représentant la cellule de vue (31 , 107) sur chaque triangle, la hauteur de la cellule de vue (31 , 107) étant égale à une hauteur de référence à laquelle on ajoute la valeur maximale des hauteurs des objets terrain ayant une intersection non nulle avec le prisme.
5. Procédé selon l'une quelconque des revendications 2 à 4, caractérisé en ce que la scène comprend des objets génériques (100) définis par une empreinte, une altitude et une hauteur, et en ce que le procédé comprend en outre une étape de transformation des objets génériques (100), et des objets terrain (104) en objets occultants (300,301) modélisés 2D1/2 en :
- prolongeant verticalement les faces des objets génériques (100) jusqu'à l'altitude zmin, chaque objet occultant (301 ) ainsi obtenu étant défini par une empreinte correspondant à la projection de l'objet générique (100) sur le plan Pmin, une altitude égale à zmin et une hauteur égale à la somme de l'altitude et de la hauteur de l'objet générique ; - prolongeant verticalement les bases (105) des objets terrain (104) jusqu'à l'altitude zmin, chaque objet occultant (300) ainsi obtenu étant défini par une empreinte correspondant à la projection de l'objet terrain (104) sur le plan Pmin, une altitude zmin et une hauteur égale à l'altitude de l'objet terrain dont il est le prolongement.
6. Procédé selon l'une quelconque des revendications 2 à 5, caractérisé en ce que la scène comprend des objets spécifiques modélisés par un assemblage de polygones, et en ce que le procédé comprend en outre une étape consistant à transformer les objets spécifiques, les objets génériques et les objets terrain en objets prolongés (305) modélisés 2D1/2, ladite étape comprenant :
- la définition d'un volume englobant pour chaque objet spécifique de la scène,
- la transformation des objets génériques (100), des objets terrain (104) et des volumes englobants en objets, prolongés (305) modélisés 2DÎ4, ladite transformation ' consistant à prolonger les faces des objets génériques, des objets terrain (104) et des volumes englobants jusqu'au plan Pmin, chaque objet prolongé
(305) ainsi obtenu étant défini par une empreinte égale à la projection sur le plan Pmin de l'objet générique, de l'objet terrain ou du volume englobant qui lui est associé, par une altitude égale à zmin et une hauteur égale à la somme de l'altitude et de la hauteur de l'objet générique, de l'objet terrain ou du volume englobant qui lui est associé.
7. Procédé selon les revendications 5 et 6, caractérisé en ce que l'étape consistant à déterminer, pour chaque cellule de vue (31 , 107), une liste d'objets potentiellement visibles comprend les sous étapes consistant à : - calculer une première carte de hauteurs minimales visibles, ladite carte étant obtenue en : o effectuant un quadrillage en N rectangles du plan Pmin, la surface occupée par chaque rectangle étant fonction d'une valeur de recouvrement k1 choisie de sorte que le quadrillage recouvre toute la surface du terrain (101), o sélectionnant des faces occultantes (21 ), notamment parmi les faces des objets occultants (300, 301), 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 la cellule de vue (31 , 107),
- déterminer une liste temporaire d'objets potentiellement visibles en comparant, pour chaque objet de la scène et chaque objet terrain, la hauteur de l'objet prolongé (305) associé et les hauteurs minimales de la première carte des rectangles ayant une intersection avec l'empreinte de l'objet prolongé,
- calculer une deuxième carte des hauteurs minimales visibles, ladite carte étant obtenue en : o effectuant un quadrillage en N rectangles du plan Pmin sur une partie du terrain (101 ), ladite partie incluant la base de la cellule de vue 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 (21 ), notamment parmi les faces des objets occultants (300, 301), et en érodant les faces occultantes (21 ) 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 la cellule de vue (31 , 107), - déterminer la liste des objets potentiellement visibles en comparant, pour chaque objet de la liste temporaire d'objets potentiellement visibles, la hauteur de l'objet prolongé associé et les hauteurs minimales de la deuxième carte des rectangles ayant une intersection avec l'empreinte de l'objet prolongé.
8. Procédé selon la revendication précédente, caractérisé en ce qu'il comprend en outre une étape de fusion d'objets occultants connexes (38, 39, 40) afin d'obtenir des ensembles connexes, ladite étape de fusion étant réalisée préalablement à l'étape de sélection des faces occultantes, et consistant à : - déterminer des groupes d'objets occultants (38, 39, 40) vérifiant des conditions de connexité,
Puis pour chaque groupe d'objets occultants connexes, déterminer un ensemble connexe en :
- supprimant 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) qui est assignée à l'ensemble connexe (141 ),
- déterminer, parmi les objets (38, 39, 40) du groupe, celui dont la hauteur est la plus petite et assigner sa hauteur à l'ensemble connexes (141).
9. Procédé selon la revendication 8, caractérisé en ce que les conditions de connexité à vérifier par un ensemble d'objets (38, 39, 40) sont que leurs empreintes (32, 33, 34) aient au moins deux sommets consécutifs en commun.
10. Procédé selon l'une des revendications 7 à 9, 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 k1 est supérieure ou égale au maximum entre le rapport de la largeur du terrain (101) par le nombre de rectangles utilisables 5 en ligne, et le rapport de longueur du terrain (101 ) par 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 : el ≥k1/-v2. 0
11. Procédé selon l'une des revendications 7 à 10, 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 choisie en utilisant la relation liant la valeur d'érosion e2 à la valeur 5 de recouvrement k2 : e2 ≥Yliφ..
12. Procédé selon l'une des revendications 7 à 11 , caractérisée en ce que l'étape consistant à sélectionner des faces occultantes, notamment 0 parmi les faces des objets occultants (300, 301 ), consiste à :
- sélectionner l'ensemble des faces des objets occultants (300, 301 ),
- sélectionner l'ensemble des faces des ensembles d'objets occultants connexes. 5
13. Procédé selon l'une des revendications 7 à 12, caractérisé en ce que l'étape consistant à éroder les faces occultantes par une valeur d'érosion e consiste à éroder les empreintes au sol des objets occultants et des ensembles d'objets occultants connexes par la e 0 valeur d'érosion e.
14. Système apte à déterminer des listes d'objets potentiellement visibles dans une scène 3D comprenant des objets (100) sur un terrain (101) et dans laquelle un utilisateur est susceptible de se déplacer virtuellement sur une zone de déplacement (25) correspondant à l'ensemble des zones du terrain (101) non recouvertes par les objets
(100), caractérisé en ce qu'il comprend :
- des moyens aptes à créer des objets terrain (104) correspondant chacun à une partie du terrain, - des moyens aptes à partitionner la zone de déplacement (25) de l'utilisateur en un réseau de cellules de vue (31 , 107),
- des moyens aptes à déterminer, pour chaque cellule de vue (31 , 107), une liste d'objets potentiellement visibles par l'utilisateur depuis la cellule de vue, ladite liste étant déterminée en testant la visibilité des objets de la scène et des objets terrain créés.
PCT/FR2004/001371 2004-06-03 2004-06-03 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. WO2006003268A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
PCT/FR2004/001371 WO2006003268A1 (fr) 2004-06-03 2004-06-03 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.

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/FR2004/001371 WO2006003268A1 (fr) 2004-06-03 2004-06-03 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.

Publications (1)

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

Family

ID=34958400

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2004/001371 WO2006003268A1 (fr) 2004-06-03 2004-06-03 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.

Country Status (1)

Country Link
WO (1) WO2006003268A1 (fr)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2452300A (en) * 2007-08-30 2009-03-04 Imagination Tech Ltd Predicated Geometry Processing in a Tile Based Rendering System
US20090167759A1 (en) * 2007-12-26 2009-07-02 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
CN106355636A (zh) * 2016-08-30 2017-01-25 北京像素软件科技股份有限公司 虚拟现实三维水体渲染中水体网格的处理方法
US11465633B2 (en) * 2018-11-14 2022-10-11 Huawei Technologies Co., Ltd. Method and system for generating predicted occupancy grid maps

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020113805A1 (en) * 2001-01-02 2002-08-22 Jiang Li Image-based walkthrough system and process employing spatial video streaming

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020113805A1 (en) * 2001-01-02 2002-08-22 Jiang Li Image-based walkthrough system and process employing spatial video streaming

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
F. DURAND ET AL.: "Conservative visibility preprocessing using extended projections", PROCEEDINGS OF THE 27TH ANNUAL CONFERENCE ON COMPUTER GRAPHIS AND INTERACTIVE TECHNIQUES, 23 July 2000 (2000-07-23), ACM PRESS, NEW YORK, US, pages 239 - 248, XP002302701 *
L. DOWNS ET AL.: "Occlusion horizons for driving through urban scenery", PROCEEDINGS OF THE 2001 SYMPOSIUM ON INTERACTIVE 3D GRAPHICS, 2001, ACM PRESS, NEW YORK, US, pages 121 - 125, XP002302699 *
SCHAUFLER ET AL.: "Conservative Volumetric with Occluder Fusion", PROCEEDINGS OF SIGGRAPH 2000, 23 July 2000 (2000-07-23), ACM PRESS, NEW YORK, US, pages 229 - 238, XP002302700 *

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2452300A (en) * 2007-08-30 2009-03-04 Imagination Tech Ltd Predicated Geometry Processing in a Tile Based Rendering System
GB2452300B (en) * 2007-08-30 2009-11-04 Imagination Tech Ltd Predicated geometry processing in a tile based rendering system
US20090167759A1 (en) * 2007-12-26 2009-07-02 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
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
CN106355636A (zh) * 2016-08-30 2017-01-25 北京像素软件科技股份有限公司 虚拟现实三维水体渲染中水体网格的处理方法
CN106355636B (zh) * 2016-08-30 2019-05-14 北京像素软件科技股份有限公司 虚拟现实三维水体渲染中水体网格的处理方法
US11465633B2 (en) * 2018-11-14 2022-10-11 Huawei Technologies Co., Ltd. Method and system for generating predicted occupancy grid maps

Similar Documents

Publication Publication Date Title
Wrenninge et al. Synscapes: A photorealistic synthetic dataset for street scene parsing
Zhang et al. A progressive morphological filter for removing nonground measurements from airborne LIDAR data
EP1982310B1 (fr) Procede de synthese d'une image virtuelle par lancer de faisceaux
Rutzinger et al. Tree modelling from mobile laser scanning data‐sets
McLaren et al. Visualisation of digital terrain models: techniques and applications
US20100085360A1 (en) Rendering in scattering media
Guan et al. DEM generation from lidar data in wooded mountain areas by cross-section-plane analysis
Lichti Spectral filtering and classification of terrestrial laser scanner point clouds
Ruzickova et al. A new GIS-compatible methodology for visibility analysis in digital surface models of earth sites
Skinner et al. High-fidelity simulation for evaluating robotic vision performance
FR2771201A1 (fr) Mappage de texture anisotrope utilisant l'analyse de silhouette ou d'empreinte dans un systeme informatique de generation d'images
Iwasaki et al. An efficient method for rendering underwater optical effects using graphics hardware
EP3729327A1 (fr) Methode de reconnaissance d'objets dans une scene observee en trois dimensions
Naylor A priori based techniques for determining visibility priority for 3-d scenes
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
Kennie et al. Modelling for digital terrain and landscape visualisation
EP2266101B1 (fr) Procede et dispositif de simulation de contact par images a plan de profondeur
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
Chapell et al. NeRF-based 3D reconstruction and orthographic novel view synthesis experiments using City-scale aerial images
Dam et al. Terrain generation based on real world locations for military training and simulation
Dietrich et al. Terrain guided multi-level instancing of highly complex plant populations
Nunes Procedural generation of synthetic forest environments to train machine learning algorithms
Hamid-Lakzaeian et al. An integrated octree-RANSAC technique for automated LiDAR building data segmentation for decorative buildings
Vallet et al. Fast and accurate visibility computation in urban scenes

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

121 Ep: the epo has been informed by wipo that ep was designated in this application
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浏览器服务，不要输入任何密码和下载