WO2006003267A1

WO2006003267A1 - Method for determining a list of elements potentially visible by region for ultra large 3d scenes of virtual cities

Info

Publication number: WO2006003267A1
Application number: PCT/FR2004/001370
Authority: WO
Inventors: Loïc BOUGET; Christian Bouville; Alexandre Cotarmanac'h
Original assignee: France Telecom
Priority date: 2004-06-03
Filing date: 2004-06-03
Publication date: 2006-01-12

Abstract

The invention relates to a method and an associated system for determining lists of objects potentially visible in a 3D scene (201) which comprises objects (200) and in which a user can virtually move. The inventive method consists in partitioning a user displacement area (250) into an array of partition prisms (202), in calculating a first map of minimum visible heights Hmin1 (R), wherein the dimensions of said map correspond to an overlapping value k1 selected in such a way that the map covers the entire surface occupied by the scene (201), in determining a first list of potentially visible objects by testing the visibility of the scene (201) objects (200) with the aid of the first map Hmin1 (R), in calculating a second map of minimum visible heights Hmin2 (R), wherein the dimensions of said map correspond to an overlapping value k2 which is less than k1 and in determining the potentially visible objects by testing the visibility of the first list objects with the aid of the second map Hmin2(R).

Description

Method for determining a list of potentially visible elements by region for very large 3D scenes representing virtual cities

The present invention relates to the general technical field of synthetic imaging, and more particularly to the field of 3D scene representation.

GENERAL PRESENTATION OF PRIOR ART

The general object of the invention is to propose a visibility calculation method making it possible to determine lists of potentially visible objects by region for very large 3D scenes representing virtual cities. In synthetic imagery, the role of visibility calculation is to determine which objects in a 3D scene are visible from a point and an observation direction.

Historically, visibility calculation has always played a crucial role for reasons of display performance of 3D scenes. Indeed, when a 3D scene is displayed, some parts are ^'not visible: the parts outside the field of view, for example, or the objects that are hidden by opaque objects in front.

In order to speed up the display of a 3D scene, we must therefore avoid unnecessary drawing of these "hidden" parts. Thus, it is necessary to eliminate as soon as possible these parts of the processing methods which will generate (draw) the 3D scene.

This is why we often apply a preprocessing to the scene to determine what will ultimately be visible in a given view of it. This preprocessing is a visibility calculation method. It makes it possible to obtain a list of the objects of the scene which will be visible in a given view. Only the objects of this list will be drawn by the means processing and displayed on the display means, which is faster than drawing all the objects of a scene.

Many visibility calculation methods allowing the elimination of non-visible objects were thus proposed in the 1970s, in particular the most famous and the most used is the z-buffer method [3]. This particularly efficient process is implemented on all modern 3D accelerator cards.

In recent years, these visibility methods have regained interest due to the growth in the complexity of 3D databases which makes it impossible to use conventional z-buffer type methods.

Therefore, in a client-server real-time perspective, it becomes necessary to use processes (off or on-line) allowing, depending on a point or an observation area, to reject part of the scene before to use the conventional z-buffer type methods for calculating the synthetic image.

In the visibility calculation methods, a distinction is made between work on exact visibility and work on conservative visibility.

An exact visibility calculation method aims to determine at an observation position and direction the exact list of visible objects. This technique generally uses a structure called an aspect graph.

A conservative visibility calculation method searches at a position or an observation area for the smallest list of potentially visible objects that will be called LOPV below. The list of visible objects is included in the list of potentially visible objects.

In the following, we will focus on processes dealing with conservative visibility that are better suited to navigation in large urban-type environments. Indeed, calculating the exact visibility of a view cell is very complex, and therefore cumbersome to implement. We also differentiate the work on visibility that takes place in the 3D object space of the scene, from that which takes place in the 2D discretized image space obtained by projections of 3D objects of the scene on the image plane. For performance reasons, we will only be interested in the first category.

A number of methods have already been proposed for establishing lists of potentially visible objects in order to eliminate non-visible objects. A first visibility calculation method allowing lists of potentially visible objects to be established is based on the technique of eliminating hidden faces. This technique consists in rejecting the faces of objects whose normal has an angle between [-Pi / 2; Pi / 2] with a given direction of observation [1, 4, 8, 9, 13, 16]. A second visibility calculation method for establishing lists of potentially visible objects is based on the technique using the view pyramid. This technique starts from the observation that all the objects located outside this pyramid at a given time are rejected during the rendering phase. Several methods using hierarchical structures of the scene have been coupled to this method.

A third visibility calculation method starts from the following property: since the screening of each polygon is too slow, it is more efficient to use techniques based on the use of hierarchical structures of the scene and of encompassing volumes [9 ]. The three processes which have just been presented allow to reject part of the scene from the 3D rendering phase.

However, for performance reasons, these methods are not applicable to real time use for overly complex databases. The method of the present invention can be used in different 3D applications, but is particularly suitable for applications offering 3D navigation at ground level.

In the case of urban navigation applications at ground level, 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 due to inter-building occultations.

In the following, we will be particularly interested in the different processes implementing the inter-object occultation principle. A first visibility calculation method implementing the inter-object occultation principle is the Coord and Teller method [5, 6]. This process is based on the use of large convex blackout objects. This process determines valid occultation plans in relation to a certain displacement of the observer. Several planes are defined in relation to a set of observation points. There are several evolutions of this process based on different structuring of the 3D scene.

Other visibility calculation methods implementing the inter-object concealment principle have also been proposed. These processes are based on the property of the occultation volumes (shadow volume) [2, 11] generated by an observation point and the outline of certain buildings obscuring the rest of the scene.

Indeed, at a given observation point, one can define a volume of shadow centered on the observation point and based on the outline of blackout objects guaranteeing that any object included in this volume of shadow will not not visible from the observer. Several methods mixing scene structuring and this property have been proposed. Regarding the choice of blackout objects, several dynamic or static strategies have also been proposed.

The above methods presented calculate the visibility relative to an observation point. This requires, when moving the user in the 3D world, to recalculate the visibility at each new position. These methods are therefore cumbersome to implement and are not applicable to real-time use for databases that are too complex.

Another approach in calculating visibility consists in making a partition of the 3D navigation space and for each element of the partition, called view cell, calculating the list of potentially visible objects.

Thus, rather than performing a visibility calculation at each position of the user, this visibility calculation is carried out for areas, or view cells, of the 3D space. In the following, we will be particularly interested in this type of visibility calculation method making it possible to determine lists of potentially visible objects by region (that is to say by view cell).

As in the Coord and Teller method there are methods for selecting large convex blackout objects [15] relative to the view cell.

However, the strong constraint on the choice of blackout objects taken into account means that these methods are not the most interesting in real cases.

Another method is proposed by Durand et Al. This method [7, 10, 14, 19] tests the non-visibility of objects by projecting blackout objects and objects on a 2D plane and by checking the inclusion of the objects projected on projections of blackout objects.

However, this process is difficult to implement because of the importance of the choice of projection planes and blackout objects taken into account.

We can also cite a method [12] dynamically calculating virtual blackout objects. The advantage of this type of process is to take into account the fusion of shadow volumes of blackout objects.

Recently Peter Wonka [17, 18] proposed a very promising visibility calculation method which uses the characteristics of the wired z-buffer of modern cards. This process assumes that the urban database is flat and that each building is represented by a 2DVa model, namely a footprint, an altitude and a height. The 3D building is deduced from the 2DYz model by elevation of a prism on the footprint. Peter Wonka's process includes different stages:

- a first step consists in making a partition of the navigable space into a view cell,

a second step consists in calculating minimum visible heights in order to determine a map of the minimum visible heights with respect to each view cell, and

a third step consists in testing the visibility of the objects of the scene with respect to each view cell as a function of the map of the minimum heights visible from the view cell.

Calculating the map of minimum visible heights ensures that an object will not be visible from a view cell if its height is less than the minimum visible heights of the region where it is located. This map is obtained by a grid of the surface occupied by the urban environment and containing for each rectangle r Ia minimum visible height Hmin (r) throughout the rectangle relative to the view cell. An object entirely included in a rectangle r and of height less than

Hmin (r) will therefore not be seen from the view cell. This map is represented using a 2D matrix and is called the visibility matrix. In the following, the rectangles will be called pixels because of the use of 3D graphic imaging techniques to speed up the processing. The calculation of the minimum visible height map uses the resources of 3D graphic cards and links the dimension of the 2D area for calculating the minimum visible height to the number of pixels of the 3D graphic card and to the surface covered by a pixel.

For example for a graphics card of [1024, 768] pixels and an overlap value of 1 meter, we obtain a 2D area for calculating the minimum visible heights of 1024 * 768 square meters. So the map of minimum visible heights will cover 1024 * 768 square meters of the 3D urban scene.

When calculating the map of minimum visible heights, the method requires reducing the blackout objects with an erosion value denoted “e” in order to limit the errors linked to the method used to calculate the minimum visible heights of said map. Due to modeling

2D ^1/4 of buildings, the erosion operation is carried out on the buildings' footprint. The value of erosion e (corresponding to the amplitude of erosion) is linked to the value of overlap (corresponding to the maximum size of a pixel) noted k by the following relation: e ≥k / "J2.

In practice to take into account the occultation phenomena, the erosion value must be low.

Indeed, if the erosion value is high, the blackout objects will be too eroded or reduced, and therefore the occultation phenomena will not be taken into account.

The test of the visibility of the objects of the scene with respect to each view cell is illustrated in FIG. 1. This test is carried out according to the map of the minimum visible heights 1 of the view cell 2.

For the objects contained in the zone covered by the map of the minimum visible heights 1, the visibility test is carried out by comparison between the height of the bounding box of the object and the minimum visible heights of the pixels having an intersection with the imprint on the ground of the object.

For the objects which are outside the zone covered by the map of visible minimum heights, Wonka proposes the following modification of its process: the borders of the map of visible minimum heights make it possible to define the horizon of visibility 4. This line d horizon 4 assures us that any object 3 outside the region covered by the map of the minimum visible heights 1 and whose projection 5 is below the horizon line 4 is not seen from the view cell. Peter Wonka's process therefore does not manage the inter-building concealment which is located outside the overlap area, that is to say outside the area covered by the map of the minimum visible heights. .

The Wonka process has the following disadvantages: i. The overlap area of the minimum visible height map covers only part of the city.

Indeed, in order not to reduce the facades of blackout buildings too much, e is generally equal to one meter, which means that the recovery value of a pixel (k) must be less than or equal to yβ meter. Indeed, the values k and e are linked by the relation e> k I sβ.

So if we assume an erosion value e equal to one meter and a graphics card of 1280 * 1024 pixels, then the map of the minimum visible heights will cover at most 1817 * 1454 square meters, or in real cases, the cities are the order 8km * 8km. To cover a larger area, the value of k must be increased, which implies an increase in the erosion amplitude. For example, for k equal to 21 ^ fI, e must be greater than or equal to 2 meters.

Consequently, the greater the value of e, the more the blackout facades will be reduced and therefore the less the blackout phenomenon will be taken into account. For example, an erosion amplitude of 2 meters removes 4 meters per building facade. ii. Wonka's method does not take into account inter-building concealment on the entire urban database.

Indeed, as previously described, inter-building concealment is not taken into account outside the area covered by the map of the minimum visible heights, iii. The erosion operation generates visibility.

Indeed, one of the drawbacks of the erosion operation is that this mathematical operation generates visibility between buildings having at least one edge in common, even if this visibility does not exist in the initial database. Thus, as shown in FIG. 2, an object 6 which is situated, relative to the current sight cell, behind two buildings 7 and 8 having a stop 9 in common, and which is not visible before the erosion operation (step 10) will become visible after the erosion operation (step 11). iv. The size of the list of potentially visible objects increases exponentially by taking urban databases of increasing size.

Indeed, inter-building concealment is not taken into account outside the area covered by the map of the minimum visible heights. Thus, any object 3 located outside the area covered by the map 1, and whose projection 5 on the visibility horizon 4 has a height greater than the minimum visible heights will be considered as potentially visible. However, it can be hidden by another building located outside the area covered by the card 1. For example, if we assume, as illustrated in Figure 3, four buildings 12, 13, 14, 15 of same width and an observation point 18 aligned in an observation direction, the heights of the buildings 12, 13, 14, 15 being respectively 5, 25, 20 and 10 meters from the closest to the furthest from the observation point 18. If it is also assumed that these four buildings 12, 13, 14, 15 are located outside the area 16 covered by the map 1, and that the height of the visibility horizon 17 is 6 meters.

Then building 12 (5 meters) closest to the point of view will be considered hidden, and the following three buildings 13, 14, 15 (25, 20 and 10 meters) will be considered potentially visible, their projections on the visibility horizon 17 having heights greater than the height of visibility horizon 17 (6 meters).

These three buildings 13, 14, 15 will therefore be part of the list of potentially visible objects although two of them are not visible (buildings 14, 15 of 20 and 10 meters being hidden by building 13 of 25 meters) . An object of the present invention is to provide a method for determining a list of potentially visible objects by region for very large 3D scenes representing virtual cities which makes it possible to overcome most of the above-mentioned drawbacks.

PRESENTATION OF THE INVENTION

The invention relates to a method for determining lists of potentially visible objects in a 3D scene comprising objects on a terrain, and in which a user is able to move virtually over a displacement zone corresponding to all of the zones of the land not covered by the objects, characterized in that it comprises the stages consisting in:

- partition the user's movement area into a network of partition prisms,

Then for each partition prism:

compute a first map of minimum visible heights, said map being obtained by: terrain, o selecting blackout faces from blackout objects and eroding the blackout faces selected by an erosion value e1 proportional to the covering value k1, o calculating, for each rectangle, the minimum height visible from the partition prism,

- determine a first list of potentially visible objects by carrying out a visibility test of the objects on the scene using the first map of the minimum visible heights, - calculate a second map of the minimum visible heights, said map being obtained by: o making a grid in N rectangles of part of the ground, said part including the base of the partition prism and the surface occupied by each rectangle being a function of a covering value k2 less than k1, o selecting the blackout faces of the blackout objects and eroding the blackout faces selected by an erosion value e2 proportional to the covering value k2, o calculating for each rectangle the minimum height visible from the partition prism,

- determine a second list of potentially visible objects by carrying out a visibility test of the objects in the first list of potentially visible objects using the second map of the minimum visible heights.

The present invention thus makes it possible to efficiently process real-size urban databases.

It breaks down into two phases. During the first phase, the use of the map of minimum heights visible over the entire city makes it possible to take into account inter-building occultation phenomena across the entire urban database. The second phase of the new method takes into account more closely the occultation phenomena between buildings close to the observer.

Furthermore, the method of the present invention is completely independent of the memory resources (of the system on which it is implemented) with respect to the size of the bases since the size of the rectangles of the grid is adapted (via the value depending on the memory resources available for calculating the map of the minimum visible heights. Certain visibility calculation methods can be very effective, but they require storage in local memory of a data structure describing the entire scene. This is not the case of the method of the present invention since the only data structure which must be in random access memory is the visibility matrix (or map of the minimum visible heights) whose size is fixed in advance, regardless of the size of the urban environment treat. In addition, this data structure is stored in the memory of the graphics card and not in the main memory of the computer.

Preferred, but not limiting, aspects of the visibility calculation method according to the invention are as follows: the objects of the scene are represented by a 2D ^1/4 model, and are defined by an altitude, a height, and a footprint comprising a set of points; the method further comprises a step of merging related objects in order to obtain sets of related objects in order to obtain sets of related objects, said merging step being carried out prior to the step of selecting the blackout faces;

The visibility generated by the erosion of blackout facades is here compensated by the erosion of the merged buildings, which makes it possible to reduce the size of the lists of potentially visible objects and therefore to be more precise. - the step of merging related objects includes the steps of:

- determine sets of objects verifying connection conditions,

Then for each set of related objects: - delete from the footprints of the objects the edges they have in common in order to obtain a unique footprint representing the set of related objects,

- determine, among the objects of the set, the one whose height is the smallest and assign its height to the set of related objects; the conditions of connectedness to be checked by two objects so that they are connected are that their footprints have at least two consecutive vertices in common; the recovery value k1 is calculated using the relation: 5 k1 ≥max (Δx / Nx, Δy / Ny).

Or :

- Δx and Δy are the width and the length of the terrain,

- Nx, Ny are the number of rectangles that can be used online and in column for the map of the minimum visible heights,

10 so that the overlap value k1 is greater than or equal to the maximum between the ratio of the width of the terrain to the number of

- rectangles that can be used online, and the ratio of the length of the terrain to the number of rectangles that can be used in column, the erosion value e1 being deduced from the previous calculation using the relation linking the value

15 of erosion el at the recovery value k1: el> k1 / v2.

the erosion value e2 is chosen to be substantially equal to 1 meter, the overlap value k2 being deducted from the value of the value

20 of erosion e2 using the relation linking the value of erosion e2 to the value of recovery k2: e2.≥k2Λ £. the step of partitioning the user movement area into a network of partition prisms includes the sub steps

25 consisting of:

- share the user's movement area in a network of triangles,

- extrude a prism on each triangle obtained previously; the step of eroding the blackout faces of the blackout objects

30. by an erosion value e consists in eroding the footprints of objects on the ground by the erosion value e; ^' . . the step of selecting the blackout faces of the blackout objects includes selecting the blackout faces of the blackout objects as well as selecting the blackout faces of sets of related objects), said objects and sets of related objects constituting the blackout objects; the visibility test on each object of the scene consists in comparing the height of a bounding box of the object and the minimum visible heights of the rectangles of the map of the minimum visible heights having an intersection with the footprint of the object; The invention also relates to a system capable of determining lists of potentially visible objects in a 3D scene comprising objects on a terrain and in which a user is able to move virtually over a displacement zone corresponding to all of the zones. land not covered by the objects, characterized in that it comprises:

means capable of partitioning the movement area of the user into a network of partition prisms,

means suitable for calculating a first map of visible minimum heights, said means comprising: o means suitable for making a grid of the terrain in N rectangles, the dimensions of the rectangles being a function of an overlap value k1 chosen so that the grid covers all the surface occupied by the scene, o means able to select blackout faces of blackout objects and means able to erode the blackout faces selected by an erosion value e1 proportional to the cover value k1, o means capable of calculating for each rectangle the minimum height visible from the partition prism, - means capable of determining a first list of potentially visible objects by carrying out a visibility test of the objects of the scene using the first visible minimum height map,

means suitable for calculating a second map of the minimum visible heights, said means comprising: o means suitable for making a grid, in N rectangles, of part of the ground, said part including the base of the partition prism and the dimensions rectangles being a function of an overlap value k2 less than k1, o means able to select the blackout faces of the blackout objects and means able to erode the blackout faces selected by an erosion value ei proportional to the value of overlap k2, o means capable of calculating for each rectangle the minimum height visible from the partition prism, - means capable of determining a second list of potentially visible objects by carrying out a visibility test of the objects in the first list of potentially visible objects using the second map of minimum visible heights. This system further comprises means capable of implementing the method described above.

PRESENTATION OF THE FIGURES

Other characteristics, aims and advantages of the present invention will emerge from the following description, which is purely illustrative and not limiting and should be read with reference to the appended drawings, in which:

- Figure 1 is a perspective view illustrating a visibility test of the method of Peter Wonka applied to an object of a scene, the object being located outside the area covered by the map of minimum visible heights; - Figure 2 is a front view of three buildings before and after an erosion operation;

- Figure 3 is a front view illustrating the visibility test of the method of Peter Wonka applied to four objects of a 3D scene, the four objects being located outside the area covered by the map of minimum visible heights;

- Figure 4 is a perspective view of a stage on which is located ^a user, said scene comprising an occulting facade of a concealing object, a visible object and a non-visible object;

- Figure 5 is a perspective view of a modeled object 2O ^Λ Λ;

- Figure 6 is an illustration of the triangulation step and includes top views of a scene before and after triangulation, and a perspective view of a view cell obtained by extruding a prism on one of the triangular partitions obtained by triangulation;

- Figure 7 is a first illustration of the building merger step and includes a top view of three footprints of related buildings, and a top view of the footprint of the building resulting from the merger of the three related buildings;

- Figure 8 is a second illustration of the building merging step and includes a front view of three connected buildings, and a front view of the building resulting from the merger of the three connected buildings; - Figure 9 is a top view of a scene on which is a user and two blackout facades of blackout buildings;

- Figure 10 is a perspective view of a 3D scene on which is implemented the method according to the present invention. - Figure 11 is a flowchart illustrating the different steps of the method. DESCRIPTION OF THE INVENTION

An object of the present invention is to provide a visibility calculation method making it possible to determine precise lists of potentially visible objects by region for very large 3D scenes representing virtual cities.

Thus, the scene represents a virtual city and the objects of the scene are buildings. An object of the present invention is therefore that the visibility calculation method makes it possible to effectively process urban data of real size of the order of 8 km * 8 km, and also makes it possible to obtain much more precise results.

For this, the inventors started from the observation that at ground level very few buildings are visible due to the inter-building occlusion. In fact, as shown in FIG. 4, at an observation point 20 located near a facade 21, a large volume 22 of the 3D scene, called the shadow volume, is not visible from the point of observation 20.

Thus, an object 23 strictly included in this shadow volume 22 will not be visible from the observation point 20. Consequently, when navigating on the ground in a virtual urban scene, very few objects 19 will be visible from an observation point 20.

Determining a minimum subset of potentially visible objects by region is a complex problem that cannot be solved without a restrictive assumption. The process assumptions are as follows:

- The urban database is made up of buildings of the same altitude and represented using a 2 D Vz model,

- Urban data are included in a dimension box (Δx,

Δy); - The number of pixels usable for the map of the minimum visible heights is equal to (Nx, Ny); The 2D ^1/2 model of a building includes an altitude (zero by default), a footprint defined by a list of points, and a height.

From this information (footprint E, altitude A, height H), it is possible, as illustrated in FIG. 5, to draw a 3D building by extruding a prism 24 at altitude A, the base of the prism 24 corresponding to the footprint E and the height of the prism being equal to the height H of the building. The process presented here is therefore based on the fact that most buildings in a 3D scene can be modeled by prisms.

The first step of the process consists in dividing the observation space close to the ground into view cells. Indeed, the exact calculation of objects visible from a 3D volume is very difficult and very costly in terms of calculation time and material resources.

As illustrated in FIG. 6, in an application for visualizing urban environments, the 3D space 25 in which the virtual observer can move is equal to the complement of the union of all the buildings

26, 27, 28, 29.

Due to the modeling used for the scene buildings

(2D modeling ¹ Λ), the partition of the user's displacement zone is very simply obtained by 2D triangulation of the complementary footprints on the buildings. This triangulation consists in dividing the area 25 of movement of the user into a network of triangles 30.

, The 3D partition is deduced from the triangulation by extruding a prism on each triangle previously obtained. The prisms thus created constitute the view cells 31. Next, for each view cell, the list of potentially visible objects (LOPV) is calculated. This list results from a minimalist evaluation of all the objects visible from at least one of the points of the current view cell.

The calculation of the list of potentially visible objects is broken down into two phases. First, a first phase makes it possible to effectively resolve the occultation between distant buildings and calculates a first list of objects potentially visible for the current view cell.

Then a second phase makes it possible to take into account effectively the inter-building concealment close to the current view cell.

In this second phase, the visibility tests are done only on the list of potentially visible objects calculated for the current view cell in the first phase.

The first step of the first phase of calculating the list of potentially visible objects consists in choosing the covering value k1 of a pixel as a function of the dimensions of the scene.

In order to be able to take into account all the inter-building occultation phenomena, the covering value k1 (defining the size of a pixel) is chosen so that the map of minimum visible heights covers the whole city.

For this, the recovery value k must be such that: k> max (Δx / Nx, Δy / Ny). Or :

- Δx and Δy are the dimensions of the box in which the surface occupied by the stage is included,

- Nx, Ny are the number of pixels that can be used online and in column for the map of the minimum visible heights.

Knowing the size of a pixel (covering value k1), we deduce the erosion value el, which must be greater than or equal to k1Λ / -î. Indeed, k and e are linked by the relation: e> k / v2.

Note that the value of the erosion to be applied will be large. For example, if we suppose a city of dimension 8km * 8km, and if we suppose that we have a 3D graphic processing means allowing us to use 1280 * 1024 pixels for the calculation of a map of minimum visible heights. Then the values of k and e become: K = max (8000/1280, 8000/1024) = 6.25 meters e = 6.25 / v2 = 4.42 meters.

The second step of the first phase of calculating the list of potentially visible objects consists in choosing blackout facades of blackout objects.

In his process, Peter Wonka considers that the set of blackout objects consists of all the buildings on the scene, and chooses as blackout facades all the facades of the buildings on the scene.

Unlike Peter Wonka's process, we consider here that the set of blackout objects consists of all the buildings on the scene and a set of merged buildings.

Thus, with the present method, the step consisting in choosing the blackout facades consists in taking the facades of all the buildings and the facades of merged buildings. To obtain sets of merged buildings, the building fusion method described below is used.

"Let the set B of all the buildings, then we can achieve a partition (in the set sense) of all the buildings by the criterion of connected footprints on the ground: Let Bi and Bj be two objects of the set B, then Bi and Bj are said to be related if their footprints have at least two consecutive vertices in common. "

From this definition we deduce a partition of the set B by related subsets: B = {Uj Bci for i ranging from 1 to N}

Bci is therefore one of the subsets of connected buildings, that is to say in which any two objects taken from the same subset Bci necessarily belong to at least one connected component of Bci. We will call the Bci "related sets". Or a connected set of buildings as defined above. Then the result of the merger of all related buildings is a building defined as follows:

- its footprint on the ground is the result of the merger of the footprints on the ground obtained by removing edges in common,

- its height is equal to the minimum of the heights of all the heights of all the related buildings.

Indeed, as shown in FIG. 7, three buildings whose footprints 32, 33, 34 have edges 35, 36 in common will be merged by deleting their edges 35, 36 in common in order to obtain the footprint on the ground 37 of a related assembly B1.

Furthermore, as shown in FIG. 8, three buildings 38, 39, 40 having common facades 41, 42 will be merged by removing their common facades 41, 42. The height of the connected assembly obtained by merging the buildings 38, 39, 40 will be equal to the height of building 38 which is the lowest of the three buildings 38, 39, 40.

Thus, with the present method, the step consisting in choosing the blackout facades consists in taking the facades of all the buildings and the facades of the sets of related objects. In the third step of the first phase of calculating the list of objects potentially visible for the current view cell, an erasing of the blackout facades is carried out. This makes it possible to correct the errors linked to the method used to calculate the maps of the minimum visible heights. A mathematical erosion operation is defined by the following property:

"A 'is said to be eroded from A by e if A' is included in A and if for any pair of points (a, a ') such that"a'"belongs to A 'and" a "belongs to A, the distance from "a '" to "a" is greater than or equal to e. »Due to 2D14 modeling of buildings, erosion by e1 occurs on the footprint of objects. This erosion operation will be carried out on all the blackout facades of blackout objects, that is to say on the facades of buildings, but also on the facades of related sets resulting from the merger of related buildings. The fourth step of the first phase of calculating the list of potentially visible objects consists in calculating the map of the minimum heights visible for the current view cell.

The computation of the map of the visible minimum heights being a difficult problem and costly in computation time, one proposes a minimalist approximation of this computation by sampling by points the edges of the upper face of the current view cell and by calculating the map minimum heights visible at each of these points. The calculation of the map associated with the current view cell is then deduced simply from the maps associated with the sampling points of the current view cell.

A first sub-step when calculating the Hmin (r) map of the minimum visible heights with respect to a view cell therefore consists in calculating Hp (r) maps of the minimum visible heights at different sampling points "p" of said cell. To calculate the map of the minimum visible heights Hp (r) from a given observation point, the concept of shadow volume is defined as follows:

Either an observation point 43 (see Figure 9) and a facade 44 of a building modeled by a rectangle perpendicular to the ground, then the shadow volume 45 is called the truncated pyramid defined by the four half-lines passing through the observation point 43 and the four vertices of the facade 44. This shadow volume 45 guarantees that any object entirely contained in this 3D volume is not visible from the observation point 43. The facade 44 is called the facade blackout. Soon _. during the Hp (r) map of the minimum heights visible with respect to an observation point "p" is deduced from the shadow volumes 45, 48 by orthogonal projection on the matrix 46 of pixels of the volumes of shadows 45, 48 generated by the blackout facades 44, 47.

To determine the Hp (r) map taking into account all of the blackout facades with respect to an observation point p, on. determines the set of Hp maps, o (r) taking into account only one blackout facade o among the set FO of blackout facades relative to the observation point p. We deduce the Hp (r) card.

Indeed, the function Hp (r) associated with the set of functions Hp, o (r) of all blackout facades o is given by the formula: Hp (r) = max {Hp, o (r), oe FO },

Or :

- Hp (r) is the function representing the minimum visible height of a pixel r with respect to the observation point p,

- Hp, o (r) is the function representing the minimum visible height of a pixel r relative to the observation point p and taking into account only the blackout facade o,

- FO represents all the blackout facades.

The functions Hp, o (r) are calculated by orthogonal projections of the volumes of shadows on the pixel matrix 46. However, discretization on a grid of pixels generates errors. This is the reason why the mathematical erosion operation is carried out before calculating the map of visible heights.

Once all the Hp (r) maps of all the sampling points have been calculated, the Hmin (r) map associated with the current view cell is determined.

The function Hmin (r) giving the minimum visible heights associated with a view cell knowing the functions Hp (r) of all the sampling points p is given by the following formula:

Hmin (r) = min {Hp (r), pe 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 facades.

When the Hmin (r) map of the minimum visible heights associated with the current view cell has been obtained, a visibility test is performed on the objects of the 3D scene in order to determine a first list of the objects potentially visible with respect to said cell.

The visibility test of an object consists of a comparison between the height of a bounding box of the object and the Hmin (r) of the pixels having an intersection with the footprint on the ground of the object.

At the end of the first phase, we obtain for each view cell a list of potentially visible objects which is a superset of the minimum list since it is calculated with a large e1. During the second phase, only the visibility of the objects belonging to the visibility list obtained in the first phase will be tested.

The second phase of calculating the list of potentially visible objects includes a first step consisting in choosing an erosion value e2. This erosion value e2 is chosen to be low (in practice less than 1 meter) in order to minimize the phenomenon of reduction of blackout facades. A value k2 of overlap corresponding to the size of the pixels is deduced from the value of erosion e2 by the formula connecting e and k: e ≥VJsl≥.

The second stage of the second phase consists in choosing the blackout facades. In his process, Peter Wonka takes as blackout facades all the facades of buildings. To this set, the present method adds the facades of the pairs of connected buildings.

This is a special case of merging related sets. Let be a couple of connected buildings, then we define their fusion as being the building defined by: - its footprint on the ground which is equal to the fusion of the footprints on the ground, with the removal of joint edges of the two connected buildings,

- its height which is equal to the minimum height of the two connected buildings.

The third step of the method consists in eroding the blackout faces with the erosion value e2. The method used to erode the faces is identical to that used in the first phase

The fourth step of the second phase consists in calculating the map of the minimum heights visible for the current view cell. This calculation is performed in the same way as in the fourth step of the first phase. This gives the map of the minimum heights visible for each view cell.

The fifth step of the second phase consists in testing the visibility on the objects of the scene in order to determine a second list of potentially visible objects. This test is carried out with respect to each view cell according to the second map of the minimum visible heights associated with said cell. This test is performed on the objects in the first list of potentially visible objects and is a function of the distance of the objects from the area covered by the map of the minimum visible heights.

Indeed if the object tested has an intersection with the map of the minimum visible heights, then the object is said to be potentially visible if its maximum height is greater than one of the heights of the pixels of the map having an intersection with the footprint. on the ground of the object. Otherwise the surrounding volume of the object is projected (see Figure 1) on the horizon of visibility. If the projection of the object is above the visibility horizon, the object is said to be potentially visible.

For each view cell, the second list of potentially visible objects associated with said cell is therefore obtained at the output of the method. In summary, and with reference to FIGS. 10 and 11, the visibility calculation method making it possible to determine lists of potentially objects visible by region for very large 3D scenes representing virtual cities comprises the following steps: a) The partitioning of the displacement zone 250 of the user (step 70 of FIG. 11). This partition is obtained by elevating prisms on each triangle produced by triangulation of the complementary footprints on the ground of buildings. b) The selection of a view cell 202 (step 71 of FIG. 11). c) The calculation of the size of a pixel (k1) and of the erosion value (e1) (step 72 of FIG. 11).

K1 is calculated so that the map of the minimum visible heights covers the whole city. The erosion value e1 is deduced from the size of a pixel. d) The selection and erosion of blackout facades (203, 204, 205, 206) (step 73 of Figure 11). To the facades of all the buildings, we add the facades of the mergers of all the related buildings. e) The computation of the map of the minimum visible heights Hmin1 (r) associated with the current view cell (step 74 of FIG. 11).

The calculation is done by the operation of union and intersection of the volumes of shadows generated by the blackout facades and the sampled points of the view cell 202. The calculation is done using the wired functions of the graphics cards 3D accessible by the OpenGL graphics library. f) The search for potentially visible objects (step 75 in Figure 11). The visibility test for objects 200 is as follows: an object 200 is said to be potentially visible if its maximum height is greater than one of the heights of the map of the minimum visible heights of the pixels having an intersection with the footprint of the 'object.

^• g) The choice of a low erosion value e2 and inferring the size of a pixel k2 (step 76 of FIG 11).

In practice the erosion value e1 is less than 1 meter h) The selection and erosion of blackout facades (step 77 in Figure 11).

To the facades of all buildings, we add the facades resulting from the merging of pairs of related buildings. i) The computation of the map of the minimum visible heights Hmin2 (r) associated with the current view cell 202 (step 78 of FIG. 11). The calculation is done by the operation of union and intersection of the volumes of shadows generated by the blackout facades and the sampled points of the view cell. The calculation is done using the wired functions of the 3D graphics cards accessible by the OpenGL graphics library. j) The search for potentially visible objects (step 79 in Figure 11).

The visibility test is only carried out on the objects obtained in step f) as a function of the distance of the objects from the area covered by the map of the minimum visible heights. Indeed, if an object has an intersection with the area of the map, then the object is said to be potentially visible if its maximum height is greater than one of the heights of the visibility matrix of the pixels having an intersection with the footprint. on the ground of the object. Otherwise the encompassing volume of the object is projected onto the visibility horizon. If the projection of the object is above the visibility horizon, the object is said to be potentially visible.

Note that operations b) to j) are iterated for all view cells.

The method presented above can be implemented in a system making it possible to carry out visibility calculations.

This system is for example a personal computer comprising memory means (RAM, ROM) connected to processing means such as a processor, display means such as a display screen and input means such as a keyboard and mouse. This system can also be an Internet server. In this case, the server makes it possible to determine the lists of potentially visible objects, and transmits them online for example to a remote personal computer which will display the 3D scene.

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 geometry models for visible surface algorithms

[5] Satyan Coorg and Seth Teller. Temporally consistent 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 representation

[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 scenes [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 environments

[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

1. Method for determining lists of potentially visible objects in a 3D scene (201) comprising objects (200) on a terrain, and in which a user is able to move virtually over a displacement zone (250) corresponding to all the areas of the ground not covered by the objects (200), characterized in that it comprises the stages consisting in:

- partitioning the movement area (250) of the user into a network of partition prisms (202),

Then for each partition prism (202):

- calculate a first map of minimum visible heights, said map being obtained by: o performing a grid of the terrain in N rectangles, the area occupied by each rectangle being a function of an overlap value k1 chosen so that the grid covers all of the terrain, o selecting blackout faces (203, 204, 205, 206) of blackout objects and eroding the blackout faces (203, 204, 205, 206) selected by an erosion value e1 proportional to the overlap value k1 , o calculating, for each rectangle, the minimum height visible from the partition prism (202),

. - determining a first list of potentially visible objects by carrying out a visibility test of the objects (200) of the scene using the first map of the minimum visible heights,

- calculate a second map of the minimum visible heights, said map being obtained by: o performing a grid in N rectangles of part of the. ground, said part including the base of the partition prism (202) and the surface occupied by each rectangle being a function of an overlap value k2 less than k1, o selecting the blackout faces (203, 204, 205, 206) of the blackout objects and eroding the blackout faces (203, 204 , 205, 206) selected by an erosion value e2 proportional to the overlap value k2, o calculating for each rectangle the minimum height visible from the partition prism,

2. Method according to claim 1, characterized in that the objects (200) of the scene (201) are represented by a 2D ^1/4 model, and are defined by an altitude, a height, and an imprint comprising a set of points.

3. Method according to claim 1 or 2, characterized in that it further comprises a step of merging related objects (38, 39, 40) in order to obtain sets of related objects (141), said step being carried out prior to the step of selecting the blackout faces (203, 204, 205, 206).

4. Method according to claims 2 and 3, characterized in that the step of merging related objects (38, 39, 40) comprises the steps consisting in:

- determine sets of objects (38, 39, 40) verifying conditions of connectedness, Then for each set of connected objects: - removing fingerprints (32, 33, 34) from objects (38, 39, 40) the edges (35, 36) that they have in common in order to obtain a single imprint (37) representing the set of objects related,

- determine, among the objects in the set, the one whose height is the smallest and assign its height to the set of related objects (141).

5. Method according to claim 4, characterized in that the conditions of connectedness to be checked by two objects so that they are connected are that their fingerprints have at least two consecutive vertices in common.

6. Method according to one of the preceding claims, characterized in that the recovery value k1 is calculated using the relation: k1 ≥max (Δx / Nx, Δy / Ny). Or :

- Δx and Δy are the width and the length of the terrain,

- Nx, Ny are the number of rectangles that can be used in line and in column for the map of minimum visible heights, so that the overlap value k1 is greater than or equal to the maximum between the ratio of the width of the terrain to the number of rectangles usable online, and the ratio of the length of the land to the number of rectangles usable in column, and in that the erosion value e1 is deduced from the previous calculation using the relation linking the erosion value el to the value of overlap k1: cl> k1 / v2.

7. Method according to one of the preceding claims, characterized in that the erosion value e2 is chosen to be substantially equal to 1 meter, and in that the recovery value k2 is deduced from the erosion value e2 using the relationship between the erosion value e2 and the recovery value k2: a> k2Λ / 2.

8. Method according to one of the preceding claims, characterized in that the step consisting in partitioning the displacement zone (250) of the user into a network of partition prisms (202) comprises the sub-steps consisting in:.

- share the movement area (250) of the user in a network of triangles,

- extrude a prism on each triangle obtained previously.

9. Method according to claim 2 in combination with any one of claims 1, 3, 4, 5, 6, 7 or 8, characterized in that. that the step of eroding the blackout faces (203, 204, 205,

206) blackout objects with an erosion value e consists in eroding the fingerprints of blackout objects with the erosion value ε.

10. Method according to one of the preceding claims, characterized in that the step consisting in selecting the blackout faces (203,

204, 205, 206) of the blackout objects includes the selection of the faces of the objects as well as the selection of the faces of the sets of related objects (141), said objects and sets of related objects constituting the blackout objects. ^{• '}

11. Method according to one of the preceding claims, characterized in that the visibility test on each object (200) of the scene consists in comparing the height of a bounding box of the object and the minimum visible heights of the rectangles of the. height map ^of minimum visible having an intersection with the imprint of the object

(200). 12. System capable of determining lists of potentially visible objects in a 3D scene comprising objects (200) on a terrain and in which a user is able to move virtually over a displacement zone (250) corresponding to the set areas of the ground not covered by the objects, characterized in that it comprises:

- means suitable for partitioning the movement area (250) of the user into a network of partition prisms, - means suitable for calculating a first map of minimum visible heights, said means comprising: o means suitable for performing a grid of the terrain in N rectangles, the dimensions of the rectangles being a function of an overlap value k1 chosen so that the grid covers the entire area occupied by the scene, o means capable of selecting blackout faces of blackout objects and means capable of eroding the blackout faces selected by an erosion value e1 proportional to the covering value k1, o means capable of calculating for each rectangle the minimum height visible from the partition prism (202),

means capable of determining a first list of potentially visible objects by carrying out a visibility test of the objects (200) of the scene using the first map of the minimum visible heights,

- Means able to calculate a second map of the minimum visible heights, said means comprising: o Means capable of making a grid, in N rectangles, of part of the ground, said part including the base of the partition prism (202) and the dimensions of the rectangles being a function of an overlap value k2 less than k1, o means able to select the blackout faces of the blackout objects and means able to erode the blackout faces selected by an erosion value e2 proportional to the overlap value k2, o means able to calculate for each rectangle the minimum visible height from the partition prism,

- Means capable of determining a second list of potentially visible objects by carrying out a visibility test of the objects of the first list of potentially visible objects using the second map of the minimum visible heights.

13. System according to claim 12, characterized in that it further comprises means capable of implementing the method according to claims 2 to 11.