Cyril Crassin

Fabrice Neyret

Sylvain Lefebvre

Miguel Sainz

Elmar Eisemann

Beyond Triangles : GigaVoxels Effects In Video Games

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Beyond Triangles : Gigavoxels Effects In Video Games

Overview

Voxel representations are commonly used for scientific data visualization, but also for many special effects involving complex or fuzzy data (e.g., clouds, smoke, foam). Since voxel rendering permits better and easier filtering than triangle-based representations it is also an efficient high-quality choice for complex meshes (with several triangles per pixel) and detailed geometric data (e.g., boats in Pirates of the Caribbean).

We have shown in [START_REF] Crassin | Gigavoxels : Ray-guided streaming for efficient and detailed voxel rendering[END_REF]] that highly detailed voxel data can be rendered in high quality at real-time rates. The work foreshadows the use of very large volumetric data sets in the context of video-games. Our system, based on ray-casting of a generalized sparse octree structure on GPU, achieves high rendering performance for billions of voxels.

To further underline the usefulness in the context of video games, this sketch introduces new features of our system, namely free object instantiation and the mixing with existing triangle scenes. We also demonstrate how to render complex visual effects like depthof-fields or approximated soft shadows in very efficient ways, exploiting intrinsic properties of our multi-resolution scheme.

GigaVoxels rendering

In GigaVoxels, voxel data is efficiently managed by structuring small voxel volumes, so-called bricks, in form of an octree. In such a way, hardware-based tri-linear interpolation is combined with a fast traversal, even for semi-transparent volumes. One key feature of our method is hybrid update/ray-casting process. During the traversal of the hierarchical volume, rays record information about the traversed octree nodes. Consequently, a ray's return value is not only a color value. E.g., if visited nodes were not present at the correct resolution a subdivision requests is returned. Because the marching is terminated when the volume becomes opaque, intravolume occlusion is taken into account and only visible data is loaded at the needed resolution and involving minimum CPU intervention. This out-of-core scheme drives a volume cache that manages the octree structure as well as the brick storage on the GPU in a unified manner.

Volume scene instancing

We extended GigaVoxels to allow scene-graph like instancing in order to create and render large scenes composed of millions of octree-based volumetric objects. To allow many semi-transparent objects, our method relies on a BVH acceleration structure. To maintain compatibility with our out-of-core update scheme, this structure is integrated in our ray-tracing process during the rendering. A new screen space structure allows us to efficiently disambiguate overlapping instances of semi-transparent volumes.

Soft shadows and depth-of-field effects

In [START_REF] Crassin | Gigavoxels : Ray-guided streaming for efficient and detailed voxel rendering[END_REF], we demonstrated that multisampling techniques can be efficiently approximated by preintegrated 3D mipmapping. Quadrilinear filtering during ray casting was enabled by maintaining a sparse octree with mipmapped bricks.

Soft shadows are usually approximated by integrating visibility over the surface of the light source. This relates to the amount of light that reaches a given point on an object. For a volumetric source, the rays towards the source form a bundle that we represent with a single cone. The blocking contribution of the object inside this cone is estimated by accumulating opacity. This is done in the same way as for eye rays, involving the mipmapping mechanism to approximate the cone integration. The resulting opacity value represents the amount of occlusion. This approach provides cheap, but plausible soft shadows while avoiding the classical multisampling.

Similarly, the mipmapping mechanism can be used to approximate a depth-of-field effect. The aperture of real cameras causes only points on a focal plane to project to a single point on the image, whereas all others produce a circle of confusion. During the eye-ray traversal, it is possible to compute this projection size and use it to determine a corresponding mipmap level for each sample lookup. The technique results in a cheap depth-of-field effect. As a side effect, the use of blurred data even accelerates the rendering, which is a powerful property.

In conclusion, GigaVoxels can be used to render many effects efficiently. Our ray-based update mechanism ensures to upload only the data that is actually needed for the image production which limits bandwidth consumption as well as pressure on the voxel cache.

Figure 1 :

 1 Figure 1: Our technique renders complex scenes consisting of billions of voxels in real time and supports soft shadows, instancing, high-quality filtering, and depth-of-field effects.


Elmar Eisemann

Xavier Décoret

Preprint: Visibility Sampling on GPU and Applications

In this paper, we show how recent GPUs can be used to very efficiently and conveniently sample the visibility between two surfaces, given a set of occluding triangles. We use bitwise arithmetics to evaluate, encode, and combine the samples blocked by each triangle. In particular, the number of operations is almost independent of the number of samples. Our method requires no CPU/GPU transfers, is fully implemented as geometric, vertex and fragment shaders, and thus does not impose to modify the way the geometry is sent to the graphics card. We finally present applications to soft shadows, and visibility analysis for level design.

Introduction & previous work

The problem of determining if two region of spaces are mutually visible, given some objects in between, appears in many fields [START_REF] C-O D | A survey of visibility for walkthrough applications[END_REF]. In Computer Graphics, it arises for various tasks such as hidden face removal (finding the first surface visible in a direction), occlusion culling (quickly rejecting parts of a 3D environment that do not contribute to the final image), shadows and more generally illumination computations. The taxonomy of visibility-related algorithms involves different criteria. First, there is the "size" of the regions. Testing the mutual visibility of two points is much easier than testing that of two polygons. What is at stake is the dimensionality of the set of rays joining the two regions. Except for the trivial case of point-point visibility, this set is generally infinite. Typically (e.g. for surface-surface visibility), it has dimension 4 which makes it harder, though not impossible [START_REF] N | Exact fromregion visibility culling[END_REF][START_REF] H | A low dimensional framework for exact polygon-to-polygon occlusion queries[END_REF][START_REF] M | Coherent and exact polygon-to-polygon visibility[END_REF], to manipulate. For that reason, many methods reduce the complexity by sampling the two regions, and solving point-point visibility (e.g. computation of the form factor between two polygons in radiosity). This paper reformulates visibility sampling so that it can benefit of the GPU capabilities.

Of course, sampling yields inaccurate results, fundamen- † X.Décoret is now working at Phoenix Interactive ‡ ARTIS, is part of the LJK research laboratory and of INRIA Rhône-Alpes. LJK is UMR 5524, a joint research laboratory of CNRS, INRIA and Grenoble University.

tally because visibility cannot be interpolated. You may not see the inside of a room from the ends of a corridor, yet fully see it when you stand in the middle, right in front of the open door. Though not exact, such methods can be made conservative -objects are never classified as not seing each other when they actually do -by various means such as erosion [START_REF] D | Erosion based visibility preprocessing[END_REF] or extended projections [START_REF] D | Conservative visibility preprocessing using extended projections[END_REF] for example. One key point here is that exactness is not required in all applications of visibility. As long as the human brain can not perceive or recognize the error, an approximate visibility estimation may be sufficient. Typically soft shadow computations can afford very crude approximations. In occlusion culling, if the pixel error caused by an approximation is small, it can be very beneficial to perform socalled aggressive culling [START_REF] N | Hardware accelerated aggressive visibility preprocessing using adaptive sampling[END_REF]. Of course, the more samples we have, the lower the error and the trade off will be between efficiency (less samples) and accuracy (more samples). The method presented here can treat many samples at once, and can decorrelate the sampling of the two regions, which strongly reduces aliasing.

The classification of visibility algorithms also depends on the type of request. One may either test whether the regions are visible, quantify this value, or even where they are visible. For example, occlusion queries not only return wether an object is hidden by an occlusion map, which can be used for occlusion culling [START_REF] B | Coherent hierarchical culling: Hardware occlusion queries made useful[END_REF], but also indicates how much it is visible, which can be used e.g. for LOD selection [START_REF] A | Integrating occlusion culling with levels of detail through hardly-visible sets[END_REF]. The problem here is to represent which parts of the regions are occluded by a given oc-cluder (i.e. which set of rays it blocks), and then combine these occlusions. It is a difficult task known as penumbrae fusion [START_REF] W | Visibility preprocessing with occluder fusion for urban walkthroughs[END_REF]. Explicitly maintained representations such as [START_REF] M | Coherent and exact polygon-to-polygon visibility[END_REF] are very costly because the space of rays is typically a 4D variety in a 5D space. In [START_REF] H | A low dimensional framework for exact polygon-to-polygon occlusion queries[END_REF], it is used to drive the selection of good occluders. Leyvand et al. [START_REF] L | Ray space factorization for from-region visibility[END_REF] perform ray-space factorisation to alleviate the high dimensionality and benefit from hardware. In guided visibility sampling [WWZ * 06], ray mutations are used to sample visibility where it is most relevant. The method is very fast and uses little memory. In many soft shadow algorithms, percentages of occlusion are combined, instead of the occlusion. Although incorrect in theory -two object that each hide 50% of the light source do not necessarily cover 100% of it -this often yields visually acceptable shadows, and is much easier to compute. In this paper, we show how bitwise arithmetic can be used to encode and combine occlusion correctly, in a GPU-friendly way.

Another concern is the simplicity of a method. To our knowledge, very few of the numerous visibility algorithms are implemented in commercial applications, except for frustum culling and cells and portals [START_REF] A | dpvs: An occlusion culling system for massive dynamic environments[END_REF]. We believe this is because many methods impose high constraints on data representation (e.g. triangles, adjacency information, additional data per triangle, etc.). Our method works fully on the GPU and needs no knowledge about the scene representation. The same rendering code as for display can be used, since everything is implemented as geometry, vertex and fragment shaders. It can handle, static or dynamic scenes.

The remainder of the paper is organized as follows. We first present the principle of our approach, together with considerations on its rationale. Then we present two applications, one to soft shadows, and one to level design in games. We finally use the results obtained in these applications to draw lessons about the proposed method.

Principle

We consider two rectangular patches, a source S and a receiver R. On each are sample points S i , i ∈ [0, s[ and R j , j ∈ [0, r[ respectively. In between are occluding triangles T k , k ∈ [0, t[. For each R j , we want to compute the set:

B j := S i such as ∃k [S i , R j ] ∩ T k ∅ (1)
It is the set of source samples that are not visible from receiver sample R j . If S represents a light source, |B j | gives the amount of blocked light, that is the penumbrae intensity. Computing B j fundamentally requires a triple loop with an inner intersection test. Formally this can be expressed as:

∀i ∀ j ∀k [S i , R j ] ∩ T k ? ∅ (2)
The commutativity of the "for each" operators allows for different ways (6 at most) of organizing the computations. For S i and T k fixed, finding the R j s that pass the intersection test amounts to a projection from S i of T k onto the receiver's plane, and testing which R j falls inside this projection. This can be done using the projection/rasterisation capabilities of graphic cards. In [START_REF] H | Simulating Soft Shadows with Graphics Hardware[END_REF], an off-center perspective view (the projection plane is not perpendicular to the optical axis) of the occluders is rendered from each source sample, to obtain a black and white occlusion mask. These views are accumulated to obtain an image that represents exactly |B j |. This approach has two limitations. First, it only computes the cardinal of the sets, not the sets and is thus limited to shadow-like requests. Second, it requires as many renderings as there are source samples. For 1024 samples, this can drastically impact performance as shown in section 10. Recently, [START_REF] L | Hierarchical penumbra casting[END_REF] showed that, it is most efficient to do all computations involving a particular triangle while it is at hand instead of traversing all triangles again and again. In that spirit, we propose the following approach:

1. traverse all triangles;

2. traverse all receiver samples that are potentially affected by the current triangle, what we called the triangle's influence region;

3. find source samples that are hidden by the current triangle from the current receiver sample;

4. combine with those hidden by previous triangles;

This approach requires a single rendering pass, using geometry, vertex and fragment shaders. Section 3 details how to touch receiving points affected by a triangle. Section 4 shows how to backproject the triangle from these points. Section 5 explains how to deduce hidden light samples of a point on the receiver, and Section 5.1 shows how to combine the hidden samples for all triangles. For the purpose of clarity, we will use a fixed set of 32 light samples. Section 6 will show how to improve the sampling.

Triangle's influence region

The influence region of a triangle is an overestimate of the union of the projections of the triangle from every point on the source. Since the goal is to consider all points potentially influenced, a bounding region suffices. Because source and triangles are convex, the influence region is contained in the convex hull of the projections of the triangle from the corner of the source. Note that it is only contained if one considers a one-sided triangle, as shown on Fig. 1. Instead of computing the convex hull, which is quite involved, we conservatively bound it by an axis-aligned bounding box. It is computed from the triangle using a geometry shader. We pass as uniform parameters the 4 matrices of the projections on the receiving plane from the source's corners. For plane ax + by + cz + d = 0 and corner (u, v, w), the matrix is given by: The geometry shader receives the triangle's vertices, projects them using the matrices, computes an axis-aligned bounding box of the obtained 4 × 3 vertices, and outputs it as a quad.

M := [abcd] × [uvw1] T -(au + bv + cw)I (3)

Backprojections on light source

For each point in the influence region, we find which part of the source is hidden by the triangle by backprojecting it onto the source. This backprojection can be interpolated from the backprojections of the vertices of the triangle's influence region. This is possible because it is a projective application. We compute these in the geometry shader using eq. ( 3) again, and pass them to the fragment shader as three interpolated texture coordinates. Note that this time, the backprojection matrix depends on the triangle, and should therefore be built in the geometry shader, not passed as a uniform. Coordinates of the backprojected triangle are computed in normalized source frame where the source is the square x = ±0.5, y = ±0.5, z = 0. At this stage, summarized on Fig. 2, we produce fragments that correspond to points inside the triangle's influence region and that have access, through three texture coordinates, to the backprojection of the triangle. The next step is to find which source samples fall in these backprojections.

Samples inside backprojection

To encode which samples are inside/outside a backprojection, we use a 32 bit bitmask encoded as RGBA8 color, that is 8 bits per channel. Our fragment shader will then output the sets of blocked samples as the fragment's color.

Computing which samples are inside the backprojection can be done by iterating over the samples, but would be very inefficient. Since the set of samples inside a 2D triangle is the intersection of the set of samples on the left of the supporting line of each (oriented) edge, we can devise a better method based on precomputed textures, in the spirit of [START_REF] K | Hemispherical rasterization for self-shadowing of dynamic objects[END_REF].

An oriented line in the 2D plane of the normalized source frame can be represented by its Hough transform [START_REF] D R | Use of the hough transformation to detect lines and curves in pictures[END_REF], that is an angle θ ∈ [-π, π] and a distance r to the origin. The distance can be negative because we consider oriented lines. However, we need only those lines that intersect the normalized light square so we can restrict ourselves to r ∈ [-

√ 2/2, + √ 2/2].
In a preprocess, we sample this Hough space in a 2D texture called the bitmask texture. For every texel (θ, r), we find the samples located on the left of the corresponding line and encode them as a RGBA8 bitmask (Fig. 3, left).

At run-time, our fragment shader evaluates which samples lie within the backprojection as follows. We first ensure the backprojection is counter-clockwise oriented, reversing its vertices if not. Then the lines supporting the three edges of the backprojection are transformed into their Hough coordinates, normalized so that [-π, π] × [-

√ 2/2, + √ 2/2] maps to [0, 1] × [0, 1]
. These coordinates are used to look-up the three bitmasks encoding which samples lie on the left of each edge. The Hough dual is periodic on θ, thus we use the GL_REPEAT mode for it and GL_CLAMP for r. The latter correctly gives either none or all samples for lines not intersecting the normalized light square. These three bitmasks are AND-ed together to get one bitmask representing the samples inside the backprojection. This result is output as the fragment's color (Fig. 3, right).

Performing a bitwise logical AND between three values in the fragment shader requires integer arithmetic. This feature is part of DirectX10, and is implemented only on very recent graphic cards. However, if not available, it can be emulated [ED06a] using a precomputed 256 3 texture such that:

opMap[i, j, k] = i AND j AND k (4)
Then, to perform the AND between three RGBA8 values obtained from the bitmasks texture, we just do a 3D texture lookup to AND each of the channels together. This approach (c) is general: any logical operation can be evaluated using the appropriate opMap texture.

( 1,1 +1 -1 +1 -1 0,0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1

Combining the occlusion of all triangles

The set output by the fragment shader for a receiver sample R j and a triangle T k can be formally written as :

B j,k ≡ i such as [S i , R j ] ∩ T k ∅ (5)
To compute the B j , we use the fact that B j = k B j,k . With our bitmask representation, the union is straightforward. All we have to do is to OR the colors/bitmasks of each fragment incoming at a same location. This is done automatically by the graphics card by enabling the logical operation blending mode. The resulting image is called hidden-samples map.

Sampling considerations

Our algorithm treats the source and the receiver asymmetrically. The source is explicitly sampled. The samples can be arbitrarily positioned using regular or irregular patterns.

All that is required is to compute the bitmasks texture for the chosen pattern. Conversely, The receiver is implicitly sampled. The rasterization of the influence regions implies that the R j are at the center of the texels of the hidden-samples map. The samples are regularly placed, and their number is given by the texture resolution. Using a 512 × 512 yields about 262k samples, which is much higher than the 32 on the source. Finally, the resulting hidden-samples map indicate which part of the source is not visible from receiver points. To get the opposite information -which part of the receiver a source point sees -it only has to be inverted.

Depending on the context, this asymmetry may not be a problem. It can always be alleviated by performing two passes, switching the source and receiver. In subsequent sections, we discuss how we can improve the number of samples, and the quality of the sampling.

Increasing source samples

We described the algorithm with 32 samples on the source because it is the number of bits available in a typical OpenGL color buffer. Recent cards support buffers and textures with 4 channels of 32 bits each, leading to 128 samples in theory. In practice, when using an integer texture format, only 31 bits can be used because of reserved special values. Thus, we can treat 124 samples.

Of course, the number of samples can be increased using multiple renderings, but the benefit of the single pass nature would be lost. We use Multiple Render Targets (MRT), a feature of modern graphic cards that lets fragment shaders output up to eight fragments to separate buffers. Thus, it is possible to evaluate up to 992 samples in a single rendering pass pass by rendering eight hidden samples maps.

Decorrelating source samples

If there are particular alignments of the scene and the light, or for large sources, a fixed sampling may become visible, even with 128 samples. To alleviate this problem, one can vary the set of samples for each receiving point. We just need to slightly perturb the positions of the backprojections by a random amount based on the position on the receiving plane. We use: random(x, y) = frac (α(sin(βy * x) + γx)) which produces a reasonably white noise if α, β, γ are correctly chosen depending on the texture resolution.

1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 1 0 1 0 2 7 2 6 2 5 2 4 2 3 2 2 2 1 2 0 1 0 1 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 = 5

Backface culling

If the caster is watertight i.e. it encloses a volume, we can ignore every triangle that is front-facing for all points on the light source. Indeed, a ray blocked by such a triangle is necessarily blocked by a non-frontfacing one (it must enter and exit the volume). Culling the front faces is more interesting than culling the back faces, because it yields smaller influence regions. In the geometry shader, we test if the triangle is front-facing by checking if it is front-facing for the four corners of the light source. If yes, it is safe to let the geometry shader discard it. This optimization eliminates roughly half the faces, and thus doubles the framerate.

Application to soft shadows

We can use our method to compute the soft shadows caused by an area light source on a receiving plane. Once we have computed the hidden-sample map, we convert it to a shadow intensity texture. This is done in a second pass, rendering a single quad covering the viewport and activating a fragment shader that does the conversion. The shader fetches the hidden sample bitmask for the fragment, and counts how many bits are at 0. This can be done using a loop over bits, or a precomputed texture [START_REF] E | Fast scene voxelization and applications[END_REF]. We use another method, whose complexity is logarithmic in the number of bits. We duplicate the bitmask, zero-ing odd bits in the first copy, and even bits in the second. We shift the second copy and add it to the first. We repeat the process log 2 (n) times to get the result Figure 4 illustrates the principle. More details can be found in [And].

Finally, we render the receiver texture-mapped with that texture, using linear interpolation and mipmapping. Alternatively, we can do bit counting directly while rendering the receiver. This is particularly interesting if the influence regions were projected from the receiving plane into the current view. In this case no aliasing occurs.

Our approach works correctly for very large sources, where many methods would fail due to the approximation of silhouette edges from the center of the source. An approach like [START_REF] H | Simulating Soft Shadows with Graphics Hardware[END_REF] would require many samples, or aliasing artifacts become noticeable. In our approach, we can decorrelate the sampling (see Section 6.2) and trade aliasing for noise. Figure 5 shows the improvement. Decorrelating sam- pling has also been proposed in a more general framework in [START_REF] S | Non-interleaved deferred shading of interleaved sample patterns[END_REF].

Methods like [AHL * 06] are restricted to rectangular light sources. Our approach can handle any planar light source. We find a bounding rectangle, so we can compute backprojections from its corners, and place the samples where there is light. This can be very handy to compute shadows for neon-like sources where there are typically several long and thin tubes inside a square. It is also possible to use colortextured light sources. We pass to the shader the number of different colors, an array of color values, and an array of bitmasks indicating which samples are associated to each color. Then the shader counts bits in each group as before, multiply by the group color, and sum the result. In our implementation, we organize samples so that the bits inside a texture channel corresponds to samples of the same color, so we do not need to pass group bitmasks. Using 8 MRTS, we can have up to 24 different colors, which is usually sufficient, and incur a negligible extra cost. Fig. 6 shows an example of a colored shadow.

Although we described our algorithm with a planar receiver, it can be adapted to handle a bumpy one. The backprojection of the triangle can be done in the fragment shader (instead of computing it in the geometry shader, and interpolating it for fragments, as described earlier). Thus, we can offset the fragment's world position, for example looking up a height map (this requires that the receiver is a heightfield as seen from at least one point of the source). As a result, we generate accurate soft shadows with high sampling rates for non-planar receivers, which has not been achieved before at interactive rates. Figure 7 shows an example. Some care must be taken though. To assure conservative influence regions the projection from the light's corners (Section 3) has to be performed on a plane lying behind the receiver. A (general) backprojection is a costly operation. Performing it in the fragment -not the vertex -shader can seriously affect the performance. If the receiver and source planes are parallel, which is a natural choice when using a heightfield, the backprojection has a very simple expression.

We first compare with the method by Assarson et al. [START_REF] A | A geometrybased soft shadow volume algorithm using graphics hardware[END_REF][START_REF] A | [END_REF]. Their algorithm has two major shortcomings. First, only edges that are silhouettes for the center of the light are considered. This leads to temporal incoherences, and inaccurate soft shadows as seen on Figure 6. The additive combination of occluders leads to unrealistic umbra regions (in particular, it affects the penumbrae gradient). Figure 8 compares our method in such a situation. Furthermore our result is accurate (up to the sampling), so no temporal artifacts can be observed.

This said, our method has several drawbacks. It separates the caster from the receiver. It computes shadows on a planar (possibly bumpy) receiver, like some recent approaches [AHL * 06]. Consequently, it is probably not suited SSV Our SSV Our

Figure 8: Even for typical game characters, classical approximations (silhouette from the center, additive occlusion) can cause noticeable artifacts. Here, it overestimates the umbra region. In comparison, our algorithm has no such approximation, and produces faithful results. In particular, there are no temporal incoherences when the light moves.

to applications like video games, and would be more interesting for fast previsualisation during the creation of static lightmaps. We insist that not shadow rendering, but visibility sampling, and the possibilities opened up by bitwise arithmetics are in the focus of the paper. Soft shadows just illustrate a possible use. Other tasks also benefit from our method, as demonstrated in the next application.

Application to assisted visibility edition

In video games, it is very important to guarantee that the framerate never drops below a certain threshold. For example, levels are often designed in a way that level-of-detail switches are not visible, or that many complex objects are not seen together from the current viewpoint. Most of this is anticipated during the design phase. Yet, the scene often needs to be modified afterwards. Typically, beta testers report where the game slowed down. Then the artist moves around objects a little, or add some dummy occluders to reduce complexity. It is interesting that some elements of decor are added just to block the player's view.

Visibility is not only a performance concern. It is often imc The Eurographics Association and Blackwell Publishing 2008. portant to enforce that some objects remain invisible, while the player is following a certain path in the game. If guards could be killed from a distance a long time before they are actually supposed to be encountered, the gameplay would be seriously altered. Here again, tools to interactively visualize visibility could help designers preventing such situations.

With our method, it is possible to place two rectangular regions in a scene, and immediately get information concerning their visibility. In particular, unblocked rays are returned (reading back the hidden-samples map). This information can be used to decide where to place objects to obstruct the view between the areas. The algorithm for soft shadows can be used to calculate an importance map indicating most visible regions. Accumulation over time is possible and allows to investigate the impact of moving objects.

We implemented such a system to visualize unblocked rays between two patches (Figure 9). We use 32 × 32 samples on source and receiver, which amounts to 1M rays considered. Yet, it is very fast, even for complex scenes. The apartment model we used has approximately 80.000 triangles, and a complex instantiation structure. A thousand renderings (Heckbert-Herf's approach) takes several seconds. With our method, we achieve about 20 fps, including a naive (inefficient) ray visualisation, which provides interactive feedback to an artist designing a scene. She can edit the scene in realtime, and adapt it to control the desired visibility. Note that our method scales extremely well with geometry in this context. In particular it inherently performs shaft-culling: when a triangle is outside the shaft, the influence region calculated by our geometry shader is outside the NDC range. It is thus clipped and produces no fragments.

The fact that we can consider many rays per second largely compensates the inherent inexactness of sampling. Interestingly, the visualization takes up more GPU resources than the determination of visibility. We compared the amount of rays per second with state-of-the-art ray-tracing approaches. Wald et al. describe a fast method to perform ray-tracing for animated scenes [WIK * 06]. The reported timings (on a dual core Xeon 3,2GHz processor) for intersection tests are 67Hz for a 5K model, 36Hz for a 16K and 16Hz for a 80K model, using a viewport of 1024 2 pixels, which amounts to 1M rays.

Our approach does not perform ray-tracing (intersections are not retrieved), but in term of speed, it achieves very high performance (see section10), is simpler to implement than a complete ray-tracing system and runs on an off-the-shelf graphics cards. Our approach works seamlessly with GPU based animation, skinning or geometric refinement. It is executed completely on the GPU, leaving the CPU available to perform other tasks aside. Finally it would even be possible to combine typical ray-tracing acceleration techniques (e.g. frustum culling) with our approach.

Results & discussion

We made various measurements comparing our method with a multiple rendering approach [HPH97] on a P4 3000MHz.

To allow for a fair comparison, we implemented a modified version of Heckbert and Herf's algorithm. We rasterize directly into a luminance texture using alpha blending and a stencil test (similar to [START_REF] K | Improving shadows and reflections via the stencil buffer[END_REF][START_REF] B | Me and my (fake) shadow[END_REF]) instead of using the accumulation buffer. This requires blending on float textures, which is available on latest cards. This modified implementation is about 10 times faster (for 1000 samples) than the original accumulation buffer version.

Figure 10 shows the light's influence. limited. The larger the source, the larger the influence region and the slower the method becomes. On the contrary, Heckbert's method is independent of the sample's location, hence the size of the source. For a giant source, it would however create aliasing that our method would address (see Figure 5). We have really pushed our algorithm, since we considered very large sources (up to the size of the model), very close to the object. Yet, our method behaves better for sources up to half the scene radius. For the bull model, we activated the watertight optimization (Section 7). This is why the performance drops more strongly than for the palm tree, where it was deactivated. When the source is very large, there are fewer and fewer fully front-facing polygons.

The bottom curves of Figure 10 are surprising at first: our method performs much better than Heckbert and Herf. Because the result is obtained in a single pass, we apply vertex computations (transform, skinning, etc.) once. Real-life scenes, like the office, often contain objects instantiated several times with different transformations. This causes many CPU-GPU transfers of matrices, context switches, etc. that imped the performance when rendering the scene hundreds of time. The mere polygon count is not a sufficient criterion.

There are other factors that influence the performance of our approach, which therefore depends strongly on the type of scene. A small triangle close to a large source has a very large influence region. Since we treat each triangle independently, highly tesselated models incur a high overdraw and a performance drop. A natural solution is to perform mesh simplification on such models, and to use the result, which has less triangles. This is not just natural, it also makes sense.

As pointed in [DHS * 05], high frequencies are lost in the presence of large light sources. The simplified model, even when very coarse, cast shadows that closely matches the exact one, as shown on Figure 11. This improves rendering time, as shown on Figure 12.

Note that it makes sense to compare the polygon count of different versions of the same object. Across models, it is irrelevant: The palm tree scene has 30k polygons but since the leaves are small, they have relatively small influence regions and cause less fillrate than the 4k polygons of the bull model. to the fragment shader (as for the bumpy ground). Alternatively, the geometry shader could retriangulate the intersecting triangles. We want to outline that most results in this paper have been computed with relatively large sources, very close to the caster, which is a worst-case scenario for most other methods. Yet, it works well, even for notably difficult cases such as for the cube in Figure 6.

Conclusion & future work

We presented a fast GPU based visibility algorithm, that samples equivalent to ray-tracing without much CPU work, but is much simpler to implement and faster (512 × 512 × 1000 samples ≈ 260M rays). Of course, ray-tracers are much more general). We believe it demonstrates the benefits of bitwise arithmetic on modern GPUs, whose interest has already been shown in [START_REF] E | Fast scene voxelization and applications[END_REF].

We presented two possible applications illustrating the util-ity of our method. The soft shadow application -although providing accurate real-time shadows on non-planar receivers for the first time -should be seen as a proof of concept. It is probably not suited for games where realism is unnecessary. It can be useful though for fast computation of lightmaps. The visibility edition is a novel application. Its strength is its speed and the ability to provide unblocked rays. It can be implemented easily and does not interfere with any GPU technique (geometry encoding, skinning, etc.). The information read-back is inexpensive, due to the small texture size.

There exist various possibilities for future work. We would like to combine our method with algorithms like [START_REF] N | Hardware accelerated aggressive visibility preprocessing using adaptive sampling[END_REF] to compute PVS. We are also interested in using it to speed up form factor estimation in hierarchical radiosity approaches [START_REF] S | Radiosity and Global Illumination[END_REF]. Finally, we are working on improvements of our soft shadow computations. Inspired by [DHS * 05], we can group triangles based on their distance to the source. The closer groups could be rendered in low resolution textures, and the furthest one in high resolution textures, thus reducing fillrate and improving speed. For globally cast shadows, we can compute shadow intensity on several parallel receivers, and interpolate in between, in the spirit of [START_REF] E | Plausible image based soft shadows using occlusion textures[END_REF].

c

  The Eurographics Association and Blackwell Publishing 2008.

Figure 1 :

 1 Figure1: For a one-sided convex caster (blue triangle) and a convex source (yellow square) the convex hull is not the best overestimate that can be constructed from the vertices.

  e iv e r' s p la n e Source Conservative influence region of T Backprojection of T from P Projection of T from source's corner

Figure 2 :

 2 Figure 2: Overview of how our approach finds the region blocked by a triangle. A geometry shader computes an overestimate of the true influence region. A fragment shader computes the backprojection and hidden samples.

Figure 3 :

 3 Figure 3: (left) Pre-processing the bitmask texture for a set of 32 samples. For every texel (θ, r) we build the line corresponding to this Hough space value (a) and find the samples located on the left of it (b). These samples are encoded as a bitmask (c) that we cast as the RGBA8 color of the texel (d). The sine wave in the resulting textures corresponds to the Hough dual of the sample points. (right) To find the light samples within the backprojection of a triangle (a), we use the bitmask texture. We look-up bitmasks representing the samples lying on the left of each edge (b) and combine them using a bitwise AND (c).

Figure 4 :

 4 Figure 4: Counting bits in logarithmic time.

Figure 5 :

 5 Figure 5: Decorrelating source sampling for each receiver point produces noisier but less aliased shadows. Here, only 32 light samples are used with a 1024 × 1024 texture. The door is slightly above the ground, to better show the shadow.

Figure 6 :

 6 Figure6: (a) An example of shadows using our method (b)Soft shadows caused by a textured light source, using 2 different colors. Notice the complex shadowing effect. The bottom left inset shows the source/receiver/scene configuration (c) A difficult case handled robustly by our method. Approximating shadows based on silhouettes from the center causes incorrect shadows (d). For moving light sources this approximation also causes strong popping.

Figure 7 :

 7 Figure 7: Soft shadows on a non-planar receiver.

Figure 9 :

 9 Figure9: Interactive visibility visualisation: a designer can navigate a scene, place any two patches, and immediately (about 20Hz) see the unblocked rays joining the patches. Here, we show two such shafts (yellow). Closeups emphasize how well our method captures visibility, even for small features like the leaves (2) of the plant. See accompanying video for a demo.

Figure 10 :

 10 Figure 10: Compared influence of light and texture size for Heckbert & Herf(HH) and our method and 992 samples (8 MRT).Top left: palm trees (29 168 polys). Top right: bull (here 4000 tris). Bottom left: office (1700 tris). X-axis indicates light size with respect to scene radius. Y-axis reports rendering time (ms). Bottom right: sampling against computation time for the palm tree scene (top left) with a light/radius ratio of 0.4. For our method, more samples have almost scene independent cost.

Figure 11 :Figure 12 :

 1112 Figure 11: Our method delivers faithful visibility results. One major cost factor is the fillrate. It becomes expensive in the case of big sources due to overdraw. Interestingly these configurations represent exactly those, where a coarse model (left) would provide almost the same shadow. Therefore fillrate can be reduced drastically via simplification.

  Our method is fillrate c The Eurographics Association and Blackwell Publishing 2008.

	400 350 ms		HH 512/8 HH 256/8									90 ms 80	HH 512/8 HH 256/8		Our 512/8 Our 256/8
	300		HH 128/8 HH 64/8									70	HH 64/8 HH 128/8		Our 64/8 Our 128/8
	200 250	Our 64/8 Our 128/8 Our 256/8 Our 512/8									40 50 60
	150											30
	100											20
	50											10
	0	0.1 0.2	0.3	0.4 Light size / scene radius 0.7 0.5 0.6	0.8	0.9	1.0	0.1 0.2 0	0.3	Light size / scene radius 0.4 0.7 0.5 0.6	0.8	0.9	1.0
	700 ms HH 512/8									250 ms	HH 256 Our 256
	600	HH 256/8 HH 128/8									200
	500	HH 64/8
	400	Our 512/8 Our 256/8									150
		Our 128/8
	300	Our 64/8									100
	200
												50
	100
	0											0
	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1.0	1	2		3	4	5	6	7	8
					Light size / scene radius							nb * 124 samples

  One feature of our algorithm is that there are no real degeneracies. It always works, up to the precision of the Hough sampling. Special cases, e.g. if the triangles intersect the receiver, can be solved by transporting the backprojection c The Eurographics Association and Blackwell Publishing 2008. Our

	8000 Polys	8000 Polys
	Ref.	Our

c The Eurographics Association and Blackwell Publishing 2008.

Acknowledgements Special thanks go to U. Assarson for his help with the comparison. We thank Espona & Stanford for the models and L. Boissieux for the studio model. We further acknowledge the reviewers for their insightful comments and H. Bezerra for her help and suggestions.