F De Sorbier De Pougnadoresse

P Bouvier
email: bouvier@univmlv.fr

A Herubel
email: herubel@univmlv.fr

V Biri
email: biri@univmlv.fr

From Research on the virtual reality installation

This article presents a new virtual reality installation inspired by the CAVE system but non expensive (7000€) and transportable. Moreover, we espe cially focus on the feeling of presence. This means user should be able to feel his selfpresence in the virtual environment and the presence of the virtual objects and entities. Keeping in mind to increase the feeling of presence, we finally propose a dedicated game based on an immersive environment, consistent interactions and emotions.

Introduction

Virtual reality (VR) aims at plunging one or more users at the heart of an artifi cial environment where they are able to feel and interact in real time thanks to sen sorimotor interfaces. The keypoint of a VR experiment is that users respond through real actions and emotions to stimuli which materialize the virtual environ ment (VE) and the virtual events.

VR is a leading area which is mainly exploited in highend fields like simula tors, scientific research, army and industry. Reasons why VR is not more general ized are mainly the cost of the system, the large room needed and the skills re quired. However, there is a growing demand for the use of VR in fields like games, artistic installations and education. That's why we design a nonexpensive (7000€) CAVElike system [START_REF] Cruz-Nera | The CAVE: audio visual experience automatic virtual environment[END_REF] which is also easily transportable in order to be de ployed in school or during show.

Our system use four screens of size 3mx3m, a 3D sound rendering with head phones and various interaction tools like the Nintendo Wiimote or a 3mx3m home made sensitive carpet. After an overview of the concepts related to presence, we will describe our VR installation. Finally, we will outline the results of the evalua tion of the system.

2 Virtual reality and presence 2.1 The role of presence VR experience makers often intend to create the conditions required to make users feel presence. This feeling of presence could be seen shortly as a strong feel ing to exist in the VE. This means, user's being in the VE has to be the most natu ral as possible in the sense without the awareness of the virtuality of the situa tion [START_REF] Ijsselsteijn | Elements of a multi-level theory of presence: Phenomenology, mental processing and neural correlates[END_REF]. Even if it has not been yet strongly established that presence improve the efficiency of the experiment [START_REF] Welch | How Can We Determine if the Sense of Presence Affects Task Performance?[END_REF][START_REF] Bormann | Subjective performance[END_REF], presence remains an important aims to tend to ward in that it motivates the researches on several levels: new interaction devices, new algorithms etc.

The feeling of presence can be seen from three angles [START_REF] Lee | Presence, explicated[END_REF]. Firstly the spatial presence or being there [START_REF] Minsky | Telepresence[END_REF] which is to feel like at a different place. Selfpresence, here it's not being there but just being, that is projection of user's ego in the role he is supposed to incarnate in the VR application. Social presence is the being with, it relates to the presence of other intelligences.

One understands that to tend toward such unstable psychological state, it is cru cial that users accept to get caught up in the experiment. Then, our work is to pro vide an experiment sufficiently credible but not necessarily realistic in order to delude user's sense and critical thinking. For this purpose we identified five inter related technical and psychological pillars on which we can lean on: human cogni tion knowledge as a foundation, immersion, interaction, consistency of the sen sorimotor loop and emotions. These pillars, which are inclined to be sufficiently generic to fit with any kind of application field, have to be seen as guidelines for VR designers. We point the fact that there is no hierarchy between the pillars, some are technical, others are more human side. Sometimes they work on their own, sometimes they work in conjunction, the aim still remains to arouse presence in a synergistic manner.

The pillars of presence

As we already said human must be at the heart of a VR system that's why it is central to understand how we perceive our environment and other humans, how we construct a mental representation of the environment etc. Moreover this may also permit to understand "the mental and neural processes that may underlie pres ence" [START_REF] Ijsselsteijn | Elements of a multi-level theory of presence: Phenomenology, mental processing and neural correlates[END_REF]. That's why we consider human cognition knowledge as a root for other pillars. We could lean on the headways in neuropsychology, social cognition, psy chology of emotions etc. This knowledge may guide the VR system design (how to delude user's senses?) but also the experiment itself (scenario, atmosphere).

The second pillar is immersion. It is achieved through the stimulation of user's senses in order to generate sensations which enable, sometimes thanks to an illu sion, the perception of the virtual environment. From this perception will ensue a proper comprehension of the virtual environment and consequently its appropria tion. At the stage of immersion there is absolutely no reference to presence or be ing there. The immersion is measurable: does the system provide a stereoscopic display? a 3D sound spatialization? use a sensory substitution? show aesthetic highdefined textures etc. It is obvious that immersion will be more complete [START_REF] Stein | The Merging of the Senses[END_REF] if several senses are stimulated in coherence. Last point, most of the time the vir tual environment is rendered as it would be if no user were there. We forget that, if someone is plunging in a virtual environment, by his simple inactive presence he has an effect on this environment. So we claim that immersion must be bidi rectional, this will improve the credibility of the environment.

The third pillar, interaction has to fulfill two tasks : to acquire information (for example via a tactile system) and to communicate information (for example to point out or manipulate an object, to modify the environment, to navigate etc. ). Moreover, by inducing that user and virtual entities exist in the VE because they interact, interactions possibilities will help to improve the feeling of presence. If we refer to the concept of "perceptual illusion of non mediation" from [START_REF] Lombard | At the heart of it all: The concept of presence[END_REF] we un derstand that interaction devices must be as transparent and natural as possible un til being forgotten. Moreover, direct body interactions could improve presence be cause these latter enable to match virtual actions with real or at least expected pro prioceptive and kinesthetic feedback. It could be the case if a virtual movement corresponds to a real movement like walking for example. Finally, until now we only emphasized communication between user and the environment but of course that can include a communication with autonomous agents or other human.

The fourth pillar consists in maintaining an actionperception or sensorimotor loop consistent. It will be necessary to respect two main points. Firstly, we will have to take care not to break the causality link between user's actions and the sys tem's feedback. That means we have to implement realtime algorithms and pro vide high frequency displays. Secondly, we must maintain the time and place con sistency between various sensory stimulations associated with the same event or virtual object. This fourth pillar constitutes a link between the last two ones but can also include some works related to synesthesia, crossmodal illusion [START_REF] Ijsselsteijn | Is This My Hand I See Before Me? The Rubber Hand Illusion. In Reality, Virtual Reality, and Mixed Reality[END_REF][START_REF] Biocca | Visual cues and virtual touch: Role of visual stimuli and intersensory integration in cross-modal haptic illusions and the sense of presence[END_REF], multimodality [START_REF] Västfjäll | Travelling without moving: Auditory scene cues for translational selfmotion[END_REF].

Even by providing some high quality immersion and interaction which respect the consistency of the actionperception loop, it will probably remain a distance between users and the role they are suppose to incarnate in the experiment. This distance which links user to reality may have several causes: the system's short comings, the real world distractions [START_REF] Wang | Evaluating the Effect of Real World Distraction on User Performance in Virtual Environments[END_REF] or just because the experiment is not mo tivating. We argue that technology can not, on its own, create the feeling of pres ence [START_REF] Banos | Sense of presence in emotional virtual environments[END_REF][START_REF] Riva | Affective interactions using virtual reality: the link between presence and emotions[END_REF]. Here is the role of the emotion pillar. By introducing emotion in the experiment we want to cancel this distance and encourage users to forget these disturbances and accept to get caught up and stay focused on the experiment. Fi nally, we think that emotions and presence self support themselves in a virtuous circle: firstly, emotion enables to reach presence more easily and then presence permits to feel more intensely emotions [START_REF] Riva | Affective interactions using virtual reality: the link between presence and emotions[END_REF].

In section 3 we will explain how we put some of these ideas in concrete form through different choices.

Virtual reality installations

Head mounted displays [START_REF] Sutherland | A head-mounted three dimensional display[END_REF] (HMD) are often associated with the concept of virtual reality because they seem to be wellsuited for immersive purposes. That kind of device which is quite intrusive because of weight, is composed of two screens allowing stereoscopic display. A strength and a weakness of a HMD is that users are roughly and completely cut off from the real environment. There fore, the loose of fixed points contributes to faze user who will be unable to keep a motionless position. Moreover, its cost will restrain its use to single user's applica tions. Finally, it is necessary to operate a tracking of user's position to maintain the consistency between the virtual content and the orientation of the viewpoint. For these reasons, we prefer to concentrate on screenbased installations.

The CAVEsystem [START_REF] Cruz-Nera | The CAVE: audio visual experience automatic virtual environment[END_REF] relies on large screens to increase the feeling of pres ence, placing user at the center of a cube. Each face is a screen on which stereo scopic images are backprojected. That way, user is visually plunged into the vir tual world (and drawbacks of HMD's are almost removed). However, like star cave [START_REF] Defanti | TheStarCAVE, a Third-Generation CAVE and Virtual Reality OptIPortal[END_REF], SAS, bluec [START_REF] Spagno | Construction of a Three-sided Immersive Telecollaboration System[END_REF] or Allosphere [START_REF] Hollerer | The Allosphere: A Large-Scale Immersive Surround-View Instrument[END_REF], a CAVElike system requires large space to ensure a correct display area. Furthermore, such an installation is hardly transportable due to its size and meticulous settings that are required. Finally, this system may be expensive because of devices used, maintenance cost and frame work needed.

These limits have led to propose some alternatives. The area taken up by the VR installation can be reduced by replacing the projective devices with well adapted ones. For example, The Varrier [START_REF] Peterka | Personal varrier: autostereoscopic virtual reality display for distributed scientific visualization[END_REF] suggests to use walls of autostereo scopic screens instead of the backprojected screens but this solution is very ex pensive. Trying to ease the displacement of an installation, MiniVR [START_REF] Fairen | MiniVR: a portable virtual reality system[END_REF] and Cy berdome [START_REF] Shibano | Cyberdome: Pc clustered hemi spherical immersive projection display[END_REF] suggest solutions based on a small screen or a curved screen.

To cut prices, [START_REF] Ohno | Development of a portable of a portable virtual reality system for disaster education[END_REF][START_REF] Grimes | A transportable and easily configurable multi-projector display system for distributed virtual reality applications[END_REF] and HIVE [START_REF] Cliburn | The HIVE: Hanover immersive virtual environment[END_REF] have followed a selfmade approach with consumer grade components. In addition, these installations are easily trans portable because they are light and simple to assemble. Concretely, these VR in stallations bring flexibility and control of the system.

3 About our virtual reality installation

Outlook

Here are the constraints we identified in order to create a VR system less ex pensive and easily transportable. Software has to be homemade or free open source, bulk of our system has to be designed with consumer grade components and if no lowcost solution exists for a device we create it. Moreover, the frame work has to be as light as possible, easy to assemble, a medium room like a class room must contain it and the whole system has to be transportable in a commer cial vehicle.

Despite these constraints we still want to provide an experiment which enables to feel presence. So, we will have to take care of several points according to each pillars. For immersion : the quality of the videoprojector (luminosity, resolution, frequency, size of the projection plane), multisensorial rendering (sound, tactile). For interactions, we provide natural devices which are not too much intrusive but offer a good precision (Wiimote, sensitive carpet for the management of user's moves). For the consistency of the sensorimotor loop : low latency system based on a clientserver architecture. And finally, to find some subterfuges in the appli cation to make user forget the shortcomings of the installation.

Description of the installation

The screens

To visually immerse the user we choose to use a CAVElike display system but using only the four vertical faces of the cube. The upper face is not used because the installation is designed to be used in rooms with classical height (roughly 3.50m). Each screen is handmade using tracing paper which is resistant and al lows backprojection. A videoprojector is placed behind each screen and is cali brated as for the image perfectly matches its surface. This layout prevents user to cast his shadow when working close to the screen.

Currently, the visual installation is monoscopic but can easily evolved to stereoscopic display. The installation can be upgraded with twice more videopro jectors and special screens which support a polarized projection system [START_REF] Bouvier | Immersive visual and audio world in 3D[END_REF]. However the number of required devices does not allow us to experiment stereo scopic projection yet. Active devices could also be used but need to be synchro nized and are still expensive.

Sound spatialization

To render the virtual acoustic environment two kinds of devices can be used: headphones or loudspeakers each having their advantages and shortcomings. Headphones are generally considered as more intrusive than loudspeakers what hinders the immersion. But headphones have the significant advantage of isolating the listener from external sounds (spectators, other installations etc.). As our in stallation is transportable, it can be installed in halls where the acoustic cannot be controlled and thus phenomenon of reverberation could appear and perturb the lis tener's perception. That is why we decide to use headphones as auditory display and a simple implementation of the HRTF associated to a spherical head model [START_REF] Cheng | Introduction to head related transfer functions (HRTFs): Representation of hrtfs in time, frequency and space[END_REF].

Interaction devices

One way to interact with the virtual environment is to capture user's position and head's orientation. Keeping in mind the cost constraint, two devices have been created.

The first device is a multizonal sensitive carpet used to capture user's position. User's weight enables the contact of two aluminum sheets isolated by perforated foam (Fig. 2 right). The floor area of the carpet is 9m² and contains 64 square zones meaning that the precision of the device is 14cm². Data transmission be tween the carpet and the server is provided by a MIDI interface. The multizonal sensitive carpet transmits the approximate user's feet position and some actions can be detected like user's jump or when user is hitting the ground with one of his feet. User's average posture can be deduced when these latter information are cou pled with the compass data.

The second device is indeed an electronic compass that gives user's head orien tation. The lightness of the sensor allows placing it on a cap worn by user so its impact on the feeling of presence is small. The device is depicted on Fig. 2. A Nintendo Wiimote is used to let the user directly interacts with the content of the virtual environment. The benefits are its low price and the capacities of that device to increase immersion. Moreover, some actions can be triggered according to user's position captured by the sensitive carpet.

Software architecture

Achieving realtime is a key point for an immersive installation and software architecture is the corner stone of this accomplishment. Such installation runs nu merous processing threads sometimes very complex like sound processing, captor acquisitions and 3D rendering on multiple displays. Those processes are mostly independent from each other except for synchronization data. Such characteristics call for a distributed architecture over network. Assigning processes between sev eral machines reduces per machine computational overhead and assures that every process gets the needed level of preemption. However this solution does have structural problems, so we stated that different processes need synchronization data. As an example, sound processing needs to be synchronized with user's posi tion. Network accesses, despite being nearly as fast as hard disk accesses, are sig nificantly slower than RAM and carrying data between each machine can be a huge bottleneck. The lack of hard realtime virtual reality platforms is another problem. Hard realtime ensures that two machines A and B receiving a signal from a machine C will act exactly the same at the same time. To address this prob lem A and B should share a clock signal to synchronize their reactions to an event.

Our implementation uses a client/server architecture pattern with a double logi cal network topology. Our server hosts several processes and handles the central control of the installation. An operator can diagnose problems and possibly stop or restart the experiment. In order to avoid multiple synchronizations between cap tors, we centralized their acquisitions on the server. The server hosts the sound processing and runs threads as well. Sound data should not be carried through the network since it may significantly decrease net work performances. Then, only sound controls are carried over the network through the sound thread, which may process and play a locally stored sound as a consequence. Our server is a completely homemade C++ program using the Qt li brary for inputs/outputs and the GUI. In our installation, the most resource inten sive process is the multiple screen 3D rendering. Each 3D rendering process is a client to our server and is hosted on a separate machine. In our installation a dis play client is a Ogre3D application, but most of 3D engines such as OpenScene Graph could be used as a display client. Each client is able to render on one screen and can be informed of captors data. It can order the server to play or stop a par ticular sound. Synchronizing this events with the server is achieved using a star logical network. Signals from the server are broadcasted to each client while clients orders directly reach the server. We stated that when receiving the same signal, clients can act slightly differently due to the lack of hard realtime. We re solve this problem with a full mesh logical network topology which connects ev ery client. Each client broadcast a clock signal on the network to other clients. The clock is a signal count. If a client detects that another one has received more sig nals it will wait to receive the same signal before triggering more events. Else, if a client detects that the others didn't receive a signal, it will wait for them. This sim ple mechanism avoids desynchronization between clients.

Importance of the content

As described previously, one of the pillars concerns emotions. Most of virtual reality installations include computing units and others devices which lead to cre ate visual and audio discomforts. More the user feels involved in the world pre sented to him more he forgets these imperfections. Generating emotions helps captivating user to focus his attention on the virtual environment rather than the material. To that purpose, we create a scenario taking advantage of the emotion's pillar to involve users.

Several video games studies [START_REF] Grimshaw | Sound and Immersion in the First-Person Shooter[END_REF][START_REF] Schneider | Death with a story: How story impacts emotional, motivational, and physiological responses to first-person shooter video games[END_REF] have shown the importance of integrating emotions in content to increase presence feeling. For example, fear and anxiety are widely used for stimulating user's emotions in video games implementing dark atmosphere or dangerous place. Considering the scenario, it should be an help for the generation of emotions [START_REF] Aylett | Towards a narrative theory of virtual reality[END_REF].

For these reasons, our VR installation has been developed considering using emotions within a scenario. We created a story for first person game taking place in a prison. The user is playing the role of a prisoner who is trying to escape with a fellow prisoner (NPC) who gives some advice. That scenario has several advan tages. First it allows user to evolve in the installation as he is moving in the virtual environment (for example the floor area fit with the jail area). Secondly, the at mosphere of prison is associated with strong feelings of stress and fear. These two latter points contribute to induce the feeling of presence, by generating emotions that involve user in the virtual world, and by increasing immersion thanks to simi larities between real and virtual spaces.

Bidirectional aspect of immersion is also increased by displaying user's shadow and his image on reflective surfaces like mirrors. This point is important for selfpresence as user has to feel existing in the virtual world. For that purpose, we use a technique named visual hulls [START_REF] Laurentini | The Visual Hull Concept for Silhouette-Based Image Understanding[END_REF] which allows to reconstruct the geom etry of an object according to a set of images captured from calibrated cameras. For each image, the silhouette of the object is computed and unprojected in the form of a cone centered on the related camera. The intersection of the cones pro duces an envelope approximating the body of the object. In the same way, we use visual hulls to create an avatar similar to the user which will be used to compute shadow or reflections in a mirror as in figure 4.

Financial details

As previously explained, the main disadvantage of most VR installations is their cost. Especially, CAVElike systems are expensive (from 23,000€ to 300,000€). These reasons led us to propose a lowcost installation made with con sumer grade components. The manufacturing cost of our installation is around 7,500€ divided as follows :

• Display (4 screens and 4 videoprojectors) : 3,800€

• Computer hardware (5 PCs with Linux and network) : 3,300€

• Small equipments (carpet, electronic compass and headphones) : 420€

Evaluation

We have initiated an evaluation procedure of the efficiency of the installation concerning the feeling of presence and to validate several of our choices detailed in section 3. Our study had 30 participants who are all graduates students in com puter sciences. Most of them regularly play video games. For this evaluation we use postexposure questionnaire using a seven point Likert item. We firstly evalu ate the perceived feeling of presence through its different angles (cf. section 2.1). Question 1 about spatial presence : "During the game, how much did you feel like you were really there in the virtual environment ?" (1=there, 7=not there at all). Question 2 about selfpresence : "During the game, how much did you feel you re ally be the prisoner ?" (1=was, 7=was not me at all). Question 3 about environ ment presence : "During the game, how much did you feel that the virtual environ ment was a real place ?" (1=real, 7=not real at all). Question 4 about social pres ence : "During the game, how much did you feel that other prisoners were existing person ?" (1=existing, 7=not existing at all). Here are the results (average of the quote) for these 4 questions : Q1: 3.5, Q2: 3.9, Q3: 4.1, Q4: 5.1. The results were quite conformed to our expectation, but we estimate them too unfinished to draw conclusions.

We also evaluate the relevance of our interaction tools choices. Question 5 : "Does the video game you just played provide high quality play control ?"(1=high quality, 7=low quality). We had a quite surprising bad result for this question which may show that people expect more from a VR game than an interaction tool like Wiimote.

In a future experiment we will evaluate the impact of each pillars on presence, independently and in conjunction. We will test if selfpresence decrease without the virtual shadow or the reflect in the mirror. We will also do a comparative study between playing the game in front of a PC or in our installation.

Conclusions

We have presented a lowcost (~7000€) and transportable version of a CAVE like virtual reality installation. We also take care to keep enough quality to arouse feeling of presence. We have described the different parts of the installation which are screens, sound, interaction devices and software architecture. We have also ar gued the importance of the content of the application to maintain the feeling of presence. Finally, we have briefly presented the results of our studies based on a questionnaire which were aimed at checking if user feel to be present in the virtual world.

These latter evaluations have pointed out the lack of efficiency concerning the pillar of interaction. So we are thinking to more natural solutions of interactions by using nonintrusive devices. One of our goals is to propose a direct interaction thanks to the tracking of user's hands. We would like to establish some eye contact during the experiment which will signify that you are existing for someone else and then will increase your feeling of self-and co-presence. We also would like to add several fans in the installation to simulate air displacement to increase immersion. Finally, we want evaluate the impact of our four screens display on the feeling of presence by comparing it with a standard PC display.

Fig. 1 .

 1 Fig. 1. Different views of our virtual reality installation

Fig. 2 .

 2 Fig. 2. The electronic compass (left) and a cross section of the sensitive carpet (right)

Fig. 3 .

 3 Fig. 3. Software architecture

Fig. 4 .

 4 Fig. 4. Using a visual hulls of the user increase self presence


Adrien Herubel
email: aherubel@quintaindustries.com

Venceslas Biri
email: biri@univ-mlv.fr

Stephane Deverly
email: sdeverly@quintaindustries.com

MORPHOLOGICAL ANTIALIASING AND TOPOLOGICAL RECONSTRUCTION

Keywords: antialiasing, mlaa, topology, realtime, gpu

Morphological antialiasing is a post-processing approach which does note require additional samples computation. This algorithm acts as a non-linear filter, ill-suited to massively parallel hardware architectures. We redesigned the initial method using multiple passes with, in particular, a new approach to line length computation. We also introduce in the method the notion of topological reconstruction to correct the weaknesses of postprocessing antialiasing techniques. Our method runs as a pure post-process filter providing full-image antialiasing at high framerates, competing with traditional MSAA.

INTRODUCTION

In computer graphics, rendering consists in sampling the color of a virtual scene. The mathematical properties of the sampling operation imply that rendering is inherently bond to aliasing artifacts. Therefore, the subject of antialiasing techniques has been actively explored for the past forty years [START_REF] Catmull | A hidden-surface algorithm with antialiasing[END_REF].

Traditional approaches to handle aliasing involve computing multiple samples for each final sample. However antialiasing by supersampling and its refinements for exemple MultiSamplge AntiAliasing (MSAA), can be prohibitively costly notably in terms of memory. Due to the popularity of deferred rendering approaches in recent real-time rendering engines, a number of filter-based antialiasing techniques appeared. Morphological Antialiasing [START_REF] Reshetov | Morphological antialiasing[END_REF] (MLAA) is a relatively recent technique which enables full image antialiasing as a post-process. Figure 1 compares two images corrected by respectively MSAA and MLAA with similar results. However MLAA has its own caveats. As a pure imagebased techniques it can not handle subpixel geometry aliasing. Moreover, as a non-linear filter, the technique uses proficiently deep branching and imagewise knowledge thus is a poor candidate to a naive GPU implementation.

We present in this paper both a practical real-time implementation of the MLAA on the GPU and a image-based technique to simulate subpixel geometry antialiasing. Our GPU MLAA implementation is a complete redesign of the original algorithm and takes full advantage of hardware acceleration. We improve results of MLAA on undersampled small scale geometric details. Our algorithm is able to locally reconstruct subpixel missing data. Our method runs as a pure post-process filter providing full-image antialiasing at high framerates.

ANTIALIASING TECHNIQUES

Supersampling

Antialiasing is a widely studied topic in computer graphics from the very start [START_REF] Catmull | A hidden-surface algorithm with antialiasing[END_REF]). Antialiasing is built in most graphics hardware [START_REF] Akeley | Reality engine graphics[END_REF][START_REF] Schilling | A new simple and efficient antialiasing with subpixel masks[END_REF] thanks to refinements of the supersampling technique. In this technique, named SSAA for Supersampling AntiAliasing, rendering is done at higher resolution then undersampled to produce the final image. Though this technique gives good results, it can be particularly costly in terms of rasterization, shading and memory. Framerates can decrease rapidly in case of complex shading or ray- The most common hardware supersampling approach is multisampling or MSAA [START_REF] Akeley | Reality engine graphics[END_REF][START_REF] Schilling | A new simple and efficient antialiasing with subpixel masks[END_REF]. In the naive supersampling, each sample is shaded, therefore a pixel is shaded multiple times. MSAA decreases the cost by decoupling fragment shading and sampling. For each sample in a pixel, the covering triangle is stored, shading is then performed once for each covering triangle then pixel color is extrapolated. CSAA or Coverage Sampling Antialiasing reduces even more the number of shaded samples by handling separately primitive coverage, depth, stencil and color. Amortized Supersampling [START_REF] Yang | Amortized supersampling[END_REF] uses temporal coherence between frames to reduce computed samples but is limited to procedural shading.

Multisampling techniques are still tightly coupled to fixed parts of the graphic pipeline, but fixed functions tend to disappear. A recent technique by [START_REF] Iourcha | A directionally adaptive edge anti-aliasing filter[END_REF] takes advantage of new hardware MSAA capabilities to acquire more accurate coverage values using neighbors of samples.

In deferred shading [START_REF] Koone | An efficient low-cost antialiasing method based on adaptive postfiltering[END_REF], the shading stage is performed in image-space on G-Buffers. Therefore using hardware multisampling with deferred shading is usually considered challenging (Engel, 2009).

Image-based antialiasing

In order to totally remove the dependency to geometry, it is possible to directly filter the final image. Full-image filtering offers the advantage of handling triangle coverage aliasing as well as shadows or textures indifferently. With the recent gain in popularity of deferred shading techniques and the limited MSAA capabilities of the current generation of game console these approaches flourished. The combination of edge detection and blur is a common and inexpensive tech- nique [START_REF] Shishkovtsov | Deferred shading in stalker[END_REF], however the results contain lots of false positive resulting generally in overblurring. In [START_REF] Koone | An efficient low-cost antialiasing method based on adaptive postfiltering[END_REF], 5x5 masks are used to detects patterns to blend.

MLAA [START_REF] Reshetov | Morphological antialiasing[END_REF]) is an image-based algorithm providing full-image antialiasing independently of the rendering pipeline. Therefore it can be used in rasterization as well as in raytracing. Moreover it is perfectly adapted to deferred rendering techniques. The initial algorithm is CPU based and was successfully ported to SPU for the PS3 console [START_REF] Hoffman | Morphological Antialiasing in God of War III[END_REF] with results comparable to MSAA4x.

The algorithm can be coarsely divided in two passes. First we detect discontinuity segments along lines and columns of the image. Crossing segments are then detected and form L shapes of varying orientations and sizes. Then the pixels of the frame are blended with their opposite neighbor along theses shapes (cf. figure 2). Concerned samples are those contained in the L, they are covered by a trapeze which is a sub-part of the triangle formed by the L. Blending weight depends of the trapeze area.

Though this algorithm is naively parallelizable it is ill-suited to massively parallel architectures such as GPU. Indeed L shapes detection imply deep dynamic branching and quasi-random access patterns in the frame which cripples cache efficiency [START_REF] Nvidia | Compute Unified Device Architecture Programming Guide[END_REF]. Moreover, as a post-processing technique, MLAA is unable to handle small scale geometry aliasing, and as a relatively local filter can suffer from poor temporal coherence, which induces flickering artifacts in animation. Finally, using luminance for discontinuity computation can lead to poor quality on RGB rendering.

3 MLAA ON THE GPU The initial algorithm was entirely redesigned to fit with a GPU GLSL implementation thus allowing direct usage in any rendering engine. GPU detection and storage of L shapes can be avoided since the main objective is to compute the area of the covering trapeze on each pixel along discontinuity lines. This area can be computed using the pixel position on the L shape. Our algorithm will therefore detect discontinuity segments, determine relative positions of pixels along these segments, compute covering trapeze areas and then do the final blending. The figure 3 shows an overview of the algorithm and samples for each of these stages. Complete source code, including shaders, can be found [START_REF] Biri | Source code of TMLAA[END_REF].

Discontinuities detection

In this stage, we seek color discontinuities between two neighboring pixels. For greyscale images, we detect discontinuity presence if the difference between greyscale values exceeds a user defined value called the discontinuity factor, chosen between 0. and 1. For color images we could use this factor as a threshold in the luminance of the pixels. However in RGB, red and blue share the same luminance leading to aliasing artifacts on textures. Therefore we switch to CIELAB color space where we are able to compute a color difference directly based on human perception [START_REF] Kang | Computational color technology[END_REF]. This discontinuity detection pass creates a texture containing, for each pixel, the existence of a discontinuity at its bottom and its right border. These two booleans are stored in two different texture channels.

We also use this first stage to initialize the texture storing discontinuity line lengths. We simply write 1 to the left and right distance of any pixel belonging to horizontal lines and 1 to up and down distance to the ones belonging to vertical lines. This is done simply using MRT.

Distance propagation

In this stage, we want to compute the distance in number of pixel, from any pixel along discontinuity lines to their two extremities. In fact, we will propagate distance from the extremities. This is done in left and right direction for horizontal lines and on up and down directions for vertical ones. Adding these two lengths also gives us the total length of the horizontal (resp vertical) discontinuity line minus one. And of course, it gives us the position of the pixel relatively to this line which will be useful in the next step. All lengths will be computed in pixel distance.

To propagate the distance to the extremities of lines, we will use a modification of the recursive doubling approach [START_REF] Dubois | Analysis of the recursive doubling algorithm[END_REF][START_REF] Hensley | Fast summed-area table generation and its applications[END_REF]. The computation will be done in up to four steps. The first one will compute length distance up to four pixels, the second one up to 16, the third one up to 64 and the final one, up to 256. At each step, for a given pixel X, we look at its distance d(X) (for instance for left direction), fetch distance of the texel at d(X) distance (at left) and add it to the current distance d(X). Updating the distance is given by :

d(X) := d(X) + d(X.x -d(X).x, X.y) (1)
We do the same for right, up and down direction. We also do that three times at each step. Figure 4 illustrates computation of left distance for the two first steps of this stage. The reason we split the computation in several step is that, you can check, for each step and pixel, if the pixel's distance is below the maximum length we can obtain from the previous step. If so, the pixel distance is already computed and can be discarded. Since distance will be stored in 8-bit precision, we will restrict ourselves to 255 line length (in pixel). The interest is that the four distance can be stored in a regular RGBA texture. You need two such textures in order to update distance, one texture for reading (in the shader), and one for writing. 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 2 3 4 4 0 1 2 Example here shows the computation of the relative distance to the left horizontal end line. In the first step, pixel A checks its three closest neighbor, each one making him "jump" to the left. Pixel B checks its closest left neighbor then its left pixel which does not belong to a discontinuity line (distance is zero then). So the computation will add 0 for the two last times. In the second step, pixel B has a distance lesser than 4, so it is discarded as all pixels marked in red. Pixel A will check the fourth -its distance -left neighbor, add one, check the left neighbor and stop here.

Computing blending factors

To this point we have computed the discontinuity segments, their lengths and the relative position of any pixel along these lines. Therefore, for each pixel bordering a discontinuity segment, we need to identify which type of L shape it belongs to. Each pixel can belong to up to four L shapes and will be blended accordingly. For an identified L shape, the area of the trapeze A can be precomputed and depends from segment length L in pixels, and from the relative position p of the pixel in the segment. Trapeze area can be computed by the formula :

A = 1 2 1 - 2 * p + 1 L (2)
This equation is true if p < L/2, else we have a triangle. If L is odd, the area of this triangle is 1/(2L), else it is 1/(8L). Therefore, given the relative position computed in previous step, and the length of the L shape, we can fetch the blending factor in a precomputed 2D texture. Given that a pixel may belong to up to for L shapes, four blending factors are stored, one for each neighbor, on a RGBA texture which is used in the final step.

Blending

At the end of the previous step, each pixel of the textures contains blending factors with its four neighbors. Therefore the blending consists in using them as local convolution kernels.

TOPOLOGICAL RECONSTRUCTION

An inherent problem to image based antialiasing algorithm are their incapacity to "regenerate" geometry in case of wrong sampling as in figure 5. We present in this section a reconstruction technique for this geometry, particularly in simple but frequent cases where only one sample is missing. We use discrete geometry and topology approaches to compute, for each pixel, its connexity number [START_REF] Kong | Digital topology: introduction and survey[END_REF]) and a characterization of its neighborhood. Using these properties it is possible to determine whether a pixel could reconnect two homogeneous areas and then "reconstruct" missing geometry.

Neighborhood and connexity

In the case of binary images, we remind some elements of digital topology [START_REF] Kong | Digital topology: introduction and survey[END_REF]. A point A ∈ Z 2 is defined as (A 1 , A 2 ). We consider neighborhood relationships N 4 and N 8 defined by, for each point A ∈ Z 2 :

N 4 (A) = B ∈ Z 2 ; |B1 -A1| + |B2 -A2| ≤ 1 N 8 (A) = B ∈ Z 2 ; max(|B1 -A1|, |B2 -A2|) ≤ 1 (3) Let α ∈ {4, 8}, we define N * α (A) = N α (A) A . A point B will be α-adjacent at point A if B ∈ N * α (A). An α-path is a sequence of points A 0 ...A k so that A i is adjacent to A i-1 for i = 1...k.
Let X ⊆ Z 2 , two points A, B of X are α-connected in X if an α-path exists in X between these two points. This defines an equivalence relation. Equivalency classes for this relationship are α-connected components of X. A subset X of Z 2 is said α-connected if it is constituted by exactly one α-connected component. The set constituted by all α-connected components of X is noted C α (X). A subset Y of Z 2 is said α-adjacent to a point A ∈ Z 2 if it exists a point B ∈ Y adjacent to A. The set of α-connected components of X α-adjacent to point A is noted C A α (X). Formally, the connexity number for a point A in a subset X of Z 2 are defined by : T

α (A, X) = C A α [N * 8 (A) ∩ X]
(4) Using the number of connexities we can measure efficiently the number of connected components adjacent to a given pixel.

Image reconstruction

Our objective is to work on the particular case of a single pixel missing for small scale geometry as shown in Figure 6. In this case, post-processing techniques due to missing data can not handle this artifact. Nevertheless, local image structure can indicate the probable presence of a missing element.

We work locally on each image pixel on a 3x3 mask. On each mask we identify potential shapes which are cut in two connected component by the current pixel. We focus on pixels linking the two connected components. The shape is constituted by pixels sharing the same color and different from the current pixel color. Reciprocally, the complement of the reconstructed shape has to be a unique connected component, thus sharing the same color as the current pixel, in order to avoid removing straight lines. If X is the shape to be reconstructed, we select pixels A so T 8 (A, X) = 2 and T 8 (A, X) = 1. Therefore we can replace their color by the color of the shape. Figure 6 gives an overview of the results.

Integration

The correction takes place before discontinuity lines detection. On the whole image, we compute the connexity number for each pixel. In order to do this, we compare the color in CIELAB space with its 8 neighbors. Each neighbor with a different color than the current pixel color is marked as belonging to X, the others are marked as belonging to the set X. Using the gathered data, the number of connexities is fetched using a lookup-table. If the number of connexities T 8 (A, X) = 2 and T 8 (A, X) = 1, the pixel is then replaced by the mean color of X pixels.

RESULTS

The algorithm was implemented on an Intel Core i7 920 with a NVidia GeForce GTX 295 graphic card. Measurements were done on a Sponza-like scene at resolution of 1920x1080. The Table 1 sums up the results in terms of frames per second on our deferred renderer. In this case MLAA performs well against SSAA both in terms of quality and performance cost. Note that our implementation is currently used on the in-house real-time rendering engine at DuranDuboi Studio notably for asset previewing.

Figure 1 and table 2 compare antialiasing techniques on a forward renderer. In terms of speed and quality, MLAA is equivalent of MSAA4x.

However figure 5 illustrates a pathological case for MLAA. Small scale geometry details lead to holes between samples when the projected geometry is smaller than pixel size. The topological reconstruction does have an additional cost of 0.55ms on our testing configuration and prevent some of these artefacts. Figure 7 presents MLAA filtering with and without correction on the whole image.

CONCLUSION

In this paper, we presented a practical real-time implementation of the MLAA algorithm suited to the GPU. We introduced a new method using topological reconstruction to handle pathological cases for imagebased antialiasing approaches. Our method improves behavior of these algorithms on small scale geometric details.

We intend to continue working on G-Buffer and MLAA integration, particularly how to use additional data in the G-Buffer such as depths and normals to improve general MLAA behavior. We also aim to improve the topological reconstruction to handle bigger gaps and to improve temporal coherence between frames.

Figure 1 :

 1 Figure 1: Left : Antialiasing with MSAA 4x. Right : with MLAA

Figure 2 :

 2 Figure 2: In MLAA, the bottom red pixel blends with the top red pixel weighted by the area of the yellow trapeze. The technique consists in detecting L shapes in green and blending pixels along the green triangle with pixels opposing the L.

Figure 3 :

 3 Figure 3: Algorithm overview

Figure 4 :

 4 Figure4: Overview of the recursive doubling approach to compute the length of discontinuity lines. Example here shows the computation of the relative distance to the left horizontal end line. In the first step, pixel A checks its three closest neighbor, each one making him "jump" to the left. Pixel B checks its closest left neighbor then its left pixel which does not belong to a discontinuity line (distance is zero then). So the computation will add 0 for the two last times. In the second step, pixel B has a distance lesser than 4, so it is discarded as all pixels marked in red. Pixel A will check the fourth -its distance -left neighbor, add one, check the left neighbor and stop here.

Figure 5 :

 5 Figure 5: Comparison between no antialiasing MLAA (middle) and MSAA8x (right). Missing subpixel data MLAA can't close holes in the electrical lines.

Figure 6 :

 6 Figure 6: Detail of the reconstruction along electric lines. Top left, original image. Top right, MSAA8x. Middle left, MLAA without reconstruction. Middle right, MLAA with topological reconstruction. Bottom line : connexity number for X (left) and X (right), black = 0, red = 1, green = 2, other > 2.

Figure 7 :

 7 Figure 7: Original image (left), Standard MLAA (middle). MLAA with topological reconstruction (right)

Table 1 :

 1 FPS and additional cost of antialiasing techniques on a deferred shading renderer.

	Method	No AA MLAA SSAAx2
	Rendering	17.4	18.3	31.2
	time (ms)
	Add. cost (ms)	0	0.9	13.8

Table 2 :

 2 FPS and additional costs of antialiasing methods in a forward renderer

	Method	no AA MSAA2 MSAA4 MLAA
	Rendering
	time (ms)	10.3	10.9	11.8	11.2
	Add. cost	0	0.6	1.2	0.9


Anthony Giroud
email: agirou01@etudiant.univ-mlv.fr

Venceslas Biri
email: biri@univ-mlv.fr

ILLUMINATING AND RENDERING HETEROGENEOUS PARTICIPATING MEDIA IN REAL TIME USING OPACITY PROPAGATION

Keywords: Real-time rendering, light scattering, participating media, propagation volume, occlusion, radial basis function

We present a new approach to illuminate and render single scattering effects in heterogeneous participating media in real time. The medium's density is modeled as a sum of radial basis functions, and is then sampled into a first volumetric grid. We then integrate the extinction function from each light source to each cell in the volume by a fast cell-to-cell propagation process on the GPU, and store the result in a second volume. We finally render both scattering medium and surfaces using a regular step ray-marching from the observer to the nearest surface. As we traverse the medium, we fetch data from both volumes and approximate a solution to the scattering equation. Our method is real-time, easy to implement and to integrate in a larger pipeline. Figure 1: Left : the original scene.

INTRODUCTION

Participating media are massively used nowadays, both in applications where real-time is required, such the video game industry and in interactive simulations, as well as in domains where visual quality is much more important than user interactions, like cinema and animation.

Rendering natural phenomena such as clouds or fog is absolutely not trivial, but is now compulsory for any rendering engine, since these are the elements in a scene which contribute the most to photorealism.

Considering the latest innovations and performances of modern GPUs, it should be possible to illuminate and render heterogeneous fog or smoke more easily and in real time.

Based on the three-steps algorithm and the idea behind Light Propagation Volumes [START_REF] Kaplanyan | Advances in Real-Time Rendering in 3D Graphics and Games Course[END_REF] where indirect radiance is propagated on surfaces, we introduce a new method to illuminate and render in real time heterogeneous participating media modeled as a sum of gaussians. We focus on single scattering of light within an anisotropic medium, and on shadow effects caused by the medium onto the objects. In this manuscript, we do not handle occlusions by the geometry.

The contribution of this paper is : • Establishing a modular framework to illuminate and render inhomogenous scattering media. • Introducing a new approach for the precomputation of the optical depth between each light source and each point in the scene. • Presenting an efficient implementation of this framework.

PREVIOUS WORK

In this section, we only focus on single scattering techniques. For more details about global illumination techniques, the reader is invited to refer to [START_REF] Cerezo | A survey on participating media rendering techniques[END_REF]. Scattering media rendering techniques are classically divided in three categories : analytic, stochastic and deterministic methods.

We focus on deterministic methods, that seek a good approximation to media rendering equations that can allow fast computation. [START_REF] Max | Efficient Light Propagation for Multiple Anisotropic Volume Scattering[END_REF] and [START_REF] Nishita | A Shading Model for Atmospheric Scattering considering Luminous Distribution of Light Sources[END_REF] worked on an analytic solution for rendering atmospheric scattering, one of the most studied applications by recent works. Later, [START_REF] Stam | Turbulent Wind Fields For Gaseous Phenomena[END_REF]) applied Nishita's model to render turbulent wind fields. More recently, [START_REF] Biri | Real Time Single Scattering Effects[END_REF] presented an analytic reformulation of the single scattering effect of a point light source.

Using particles to model heterogeneous participating media appears much natural, and has also already been intensively used [START_REF] Stam | Stable Fluids[END_REF][START_REF] Fedkiw | Visual Simulation of Smoke[END_REF]. [START_REF] Zhou | Fogshop: Real-time design and rendering of inhomogeneous, single-scattering media[END_REF], propose an hybrid approach to handle single scattering in an heterogeneous participating medium, combining particles (i.e. gaussians) and spherical harmonics. Despite good performances, since all lighting computation depend on the observer's point of view, the whole pipeline has to be processed at each frame. Moreover, it seems not convenient to implement and not easy to integrate in an existing pipeline.

Approaches where the medium is discretized over a 3D grid of voxels start with [START_REF] Kajiya | Ray Tracing Volume Densities[END_REF]. The scattering media is modeled as a set of voxels of varying density. As a first step, the radiance arriving at each voxel from each light source is computed ; then, the main scattering integral is evaluated iteratively between the viewer and the farthest voxel intersected by a ray-tracing. Our method is inspired from this two-step scheme. [START_REF] Kniss | A model for volume lighting and modeling[END_REF] present a technique to illuminate volumetric data based on half angle slicing [START_REF] Wilson | Direct volume rendering via 3d textures[END_REF], handling both a direct and an approximated indirect lighting, but only for a single light source situated outside the medium. [START_REF] Magnor | Reflection nebula visualization[END_REF] introduce a method to visualize reflection nebulae in interactive time. The method uses a three-step algorithm similar to our method, but where the medium's density is kept unchanged, due to the need for lighting precomputations.

Recently, [START_REF] Kaplanyan | Advances in Real-Time Rendering in 3D Graphics and Games Course[END_REF] introduces the concept of Light Propagation Volumes, to scatter indirect lighting. After generating reflective shadow maps and obtaining a set of virtual point lights on reflective surfaces, direct lighting is injected in a radiance volume, which is a simple volumetric grid. In a third step, using graphics hardware, indirect lighting is propagated from cell-to-cell by iteratively solving differen-tial schemes inside the volumetric grid.

Although focusing only on indirect lighting on surfaces, this approach by propagation within a volumetric grid is fast, allow more flexibility and could as well be adapted in the case of direct incoming radiance within a scattering media.

THEORETICAL BACKGROUND

Modeling the participating media using a radial function basis

Because our participating media is not static and can evolve over time, the modeling step must be as simple as possible for the user.

Like [START_REF] Zhou | Fogshop: Real-time design and rendering of inhomogeneous, single-scattering media[END_REF], we choose to model our heterogeneous participating media as a sum of radial basis functions (RBF).

To define the medium's appearance, the user just provides a list of radial particles, which can differ in both amplitude and scale. The particle's density will then be evaluated and injected into a 3D grid.

As the radial function itself, we simply chose the gaussian function, defined on R d :

β(x) = ce -a 2 x-b 2 (1)
where a ∈ R is its amplitude, b ∈ R d its center and c ∈ R its scale.

To evaluate a function defined in a radial function basis, we must sum all basis functions that overlay at the given coordinates.

f (x) = N ∑ i=0 β i (x) ⇐⇒ f (x) = N ∑ i=0 c i e -a 2 i x-b i 2 (2)
where i is the index of the RBF, and N is the total number of RBFs in the basis.

Our illumination model

The appearance of a participating medium is linked to airlight [START_REF] Arvo | Transfer equations in global illumination[END_REF]. When light is emitted from a point light source S, then goes through a participating medium which an extinction function f (see figure 2), the light L S (O) received by the observer at position O, who looks in the direction of point P is given by : where k(α) is the scattering phase function, I S the intensity of light S, and T (A, B) is the optical depth of the medium between points A and B :

L S (O) = P O f (X)k(α(X)) I S S -X 2 e -T (O,X)-T (X,S) dX (3)
T (A, B) = B A K t (t)dt (4)
where K t is the extinction function of the medium.

In our method, we will assume an isotropic scattering involving k(α(X)) = 1 4π . Therefore, our final model is :

L S (O) = P O f (X) 1 4π I S S -X 2 e -T (O,X)-T (X,S) dt
(5)

OUR METHOD

Overview

Our pipeline is composed of three steps :

1. Density injection : The medium's extinction function f is injected into a 3D grid, called the extinction volume (EV).

Opacity propagation :

The optical depth T (S, X) is integrated from each light source S to each cell in another 3D grid called the opacity propagation volume (OPV).

Volume rendering :

The participating medium is rendered, using a simple ray-marching technique, and based on data obtained at the two previous steps.

The following sections describe each step and detail the algorithm. Our application is programmed using C++ and OpenGL, and GLSL for the shaders.

Density injection

Since our medium is composed by a set of RBFs, the final extinction coefficient at a given point within the medium is obtained considering all particles that overlay at this point.

Thanks to the low frequency nature of the scattering medium, we can avoid such costly computation on many points by pre-sampling the extinction coefficients on a 3D grid : the extinction volume.

The EV is implemented as a 3D texture, having the same dimensions as the OPV. Each texel stores only one decimal value, therefore a 16-bit floating point encoding is sufficient. To fill the texture, we perform a plane sweep along the Z-axis (depth). Each plane sweep step fills one texture slice, which is bound to a framebuffer object.

For each RBF contributing to the current slice, we draw its bounding quad facing the camera. The RBF is computed at each point on the quad using equation 2, evaluated in a fragment shader. Since several gaussians may be overlayed on the same slice, we need to activate additive blending.

Opacity propagation

The opacity propagation volume

Now that the medium's density has been discretized into voxels in the EV, we need to compute the optical depth between each light source S and each EV cell X. Contrarily to [START_REF] Magnor | Reflection nebula visualization[END_REF], we allow both the medium and lighting to evolve over time, and must therefore consider repeating this step for each frame for which these conditions have changed. To achieve this in real time, our idea is to use the radiance gathering scheme presented by [START_REF] Kaplanyan | Advances in Real-Time Rendering in 3D Graphics and Games Course[END_REF] for indirect lighting on surfaces, and adapt it to propagate (i.e. integrate) the optical depth between each light source and each voxel in the EV. The resulting values are stored in a separate grid : the opacity propagation volume.

Propagation scheme

When propagating radiance in a discrete neighbouring, it is actually difficult to naturally simulate the quadratic attenuation. When, like in [START_REF] Kaplanyan | Advances in Real-Time Rendering in 3D Graphics and Games Course[END_REF], only cell-to-cell propagation directions are considered, the radiance is distributed among all neighbours and therefore scatters too rapidly around the source, even in scenes without occluding surfaces or media. Because a scattering method is not adapted to an implementation on graphics hardware, we instead use a gathering scheme.

As each cell gathers optical depth from its six neighbours and accounts for its own local density, our solution is to consider both each discrete neighbourto-cell incoming directions and the accurate nondiscrete light-to-cell direction.

We compute a weighted mean of incoming optical depth from all six neighbours, where the six weights are determined by the similarity between the accurate lighting direction SX and the 6-connexity cell-to-cell incoming direction, determined by their dot product.

As the light cannot arrive from a direction opposed to source, optical depth incoming with a negative scalar product must be discarded.

In other words, we have :

T n+1 (X, S) = K(X) + ∑ 5 i=0 W S,i (X)T n (X -d i , S) ∑ 5 i=0 W S,i (X) (6
) where T n (X, S) is the portion of the density received from source S by cell X at step n, d i is the incoming density direction from the i th neighbouring cell, and which W S,i is the weight in the sum, given by :

W S,i = (1 -K t (X)) max SX, d i , 0 (

Algorithm

Like to the EV, the OPV is stored as a 3D 16-bit floating point texture with the same dimensions. Each texel stores one optical depth integral for each light source, i.e. one texture is need per group of four lights. Because using a texture for both reading and writing in a shader is not available, the propagation process which is implemented on the GPU requires at least two copies of each texture. They are alternatively used either for reading or writing at each new step.

The integration originates from a single cell containing the light, and advances radially like a wavefront. By marking the visited texels using an additional texture, we can speed up the process in the shader by discarding cells which either have already been computed, or have not been reached yet.

To initialize a new propagation process, the two OPV textures are cleared so that each texel starts with zero, except for the cells which contain a light source, which are initialized with their respective local extinction coefficient.

Each single propagation step involves a plane sweep along the texture slices. The gathering algorithm is implemented in a fragment shader, called on a fullscreen quad.

Algorithm 1 shows the pseudo-code of the fragment shader for the gathering process.

Rendering

Visualizing the medium

Visualizing our participating medium means solving the scattering equation 5, which defines how to obtain the final color of each pixel.

Considering our model, we need to perform an integration along the view ray OP. We have little choice but solving this integration using a conventional raymarching over our grid.

We use a fixed integration step, even if more sophisticated techniques can be used [START_REF] Giroud | Modeling and Rendering Heterogeneous Fog in Real-Time Using B-Spline Wavelets[END_REF].

The entire algorithm is implemented on a fragment shader, and is repeated separately for each light source. We start the integration from the observer and move in the direction of the surface in front of the camera.

Based on precomputations performed in the two previous sections, and considering equation 5, each ray-marching step is straightforward :

1. Fetch f (X), the extinction coefficient corresponding to the local density of our scattering medium, and accumulate it with the values fetched at previous steps. At this point, the density of the medium will decide how much light will locally not pass through and thus be reflected, making the medium visible to the camera.

2. Fetch T (X, S), the optical depth between X and each separate light source S. The radiance from S reaching X is obtained with : e -T (X,S) I S .

3. Compute quadratic attenuation : S -X -2 .

4. Compute this step's contribution, and add the radiance in the integral result :

L S (X) = (1 -K t (X))L S (X) + K t L IN (X) (8)
where L IN (X) is the incoming radiance from the source, given by :

L IN (X) = I S * e -T(X,S) (9)
5. Repeat until the nearest surface is reached.

Rendering surfaces

Last but not least, in order to render the surface in front of the current pixel, we have to use a simple and fast illumination model. In our implementation, we compute a simple Phong illumination, but other models can be used as well.

The final pixel color is finally obtained as the result of an additional integration step, outside the main ray-marching loop : L S (O) = Ph S (P, O)e -T (O,P)-T (P,S) S -X -2 (10)

where Ph S (P, O) is the Phong illumination for light S, at position P on the surface, and as perceived by observer O.

Results

This algorithm has been implemented using GLSL, an Intel Core 2 Quad 2.8Ghz processor and a NVidia GeForce GTX 280 graphics card. Screen resolution is 800x600. Although classic ray-tracing based methods have to perform again the major part of the computations at each frame, our pipeline is very modular.

Which computation phases are or are not performed at each new frame (see table 1) is the parameter which impacts most on the speed at runtime.

In table 2, we can see that computing lighting for between one and up to four sources does not bring significant extra cost. With more than four lights, a second OPV texture is required, which implies more texture fetching and writing operations. In the second column, only the rendering phase is performed.

Table 3 shows that the medium's dimensions almost only affect the density injection phase. After phase 1, the complexity of the medium does not depend on the number of particles anymore, but on the number of cells in the extinction volume.

Conclusion and future work

In this paper, we presented a new method for illuminating and rendering heterogeneous isotropic scattering media in real time. The medium is modeled by providing a simple list of gaussians, which are first sampled over a volumetric grid. Then, the optical depth T (X, S) between each light source and each grid cell is computed by propagating occlusions throughout a second volume using a modified version of Crytek's algorithm. We finally render the medium and surfaces by performing a ray-marching between the camera and the nearest surface. Our method fully achieves real time on conventional hardware, and renders scattering effects such as halos around light sources within the medium with good quality. Using OpenGL and GLSL, we believe that it is easy to implement and most of all, easy to integrate in an existing graphics engine.

We are currently working at several improvements to our method. First, by taking in account occlusions by the geometry. Then, by optimizing the propagation algorithm so that the shader only processes cells sutuated on the propagation wavefront. Finally, we would like to speed-up our ray-marching, by optimizing GPU memory cache management.

Figure 2 :

 2 Figure 2: The integral of T(X, S) is computed during the opacity propagation stage (blue path), between each light S and each position X. The integral of T(O, X) is accumulated at the rendering step.

Figure 3 :

 3 Figure 3: Optical depth gathering : weighting incoming directions. A : Cells already visited by the propagation wavefront are shown in blue, S is the position of the light source and X is the center of the cell for which the gathering process is detailed. B : We compute the dot product between the non-discrete lighting direction SX and each orthogonal cell-to-cell direction. C : Neighbours whose dot product is negative are discarded.

7 )Algorithm 1

 71 Propagation -Pixel shader (GPU) K(X) = Read local density from EV for light source S do /* 1. Gather density from neighbours */ wghtd dens sum = 0 weights sum = 0 for gathering direction d i do W S,i = max(dot( SX, d i ), 0) K(Xd i ) = Read neighbour density wghtd dens sum += W S,i * K(Xd i ) weights sum += W S,i end for /* 2. Result for light S */ pxl channels[S] = K(X) + wghtd dens sum / weights sum pixel color = pxl channels end for

Figure 4 :

 4 Figure 4: Left : Single large particle, one light. Middle : 16 particles, two lights. Right : Multiple lights in a thick fog.

Table 2 :

 2 FPS results with different volume resolutions and lighting conditions. (P) : phases 1 and 2 are precomputed.

	Static elements		Injection Propagation
	Nothing		U		U
	Medium		P		U
	Lighting and medium	P		P
	Table 1: Depending on the type of scene, our method makes
	it possible to precompute (P) the EV density injection and
	the OPV propagation, and only update (U) volumes when
	required.
	Volumes size 1L(P) 1L 2L 4L 8L
	15 3	320	62 62 51 34
	20 3	251	38 37 35 22
	30 3	203	17 17 16	9
	40 3	120	9	9	9	5

Table 3 :

 3 FPS results rendering mediums with different complexities, with dynamic and static scenes, using extinction and occlusion volumes with a 20 3 resolution, in our Cornell box.