Nicolas Tsingos
email: nicolas.tsingos@sophia.inria.fr

Emmanuel Gallo

George Drettakis

Perceptual Audio Rendering of Complex Virtual Environments

Keywords: Virtual Environments, Spatialized Sound, Spatial Hearing Models, Perceptual Rendering, Audio Hardware

Figure 1: Left, an overview of a test virtual environment, containing 174 sound sources. All vehicles are moving. Mid-left, the magenta dots indicate the locations of the sound sources while the red sphere represents the listener. Notice that the train and the river are extended sources modeled by collections of point sources. Mid-right, ray-paths from the sources to the listener. Paths in red correspond to the perceptually masked sound sources. Right, the blue boxes are clusters of sound sources with the representatives of each cluster in grey. Combination of auditory culling and spatial clustering allows us to render such complex audio-visual scenes in real-time.

Introduction

Including spatialized audio is a key aspect in producing realistic virtual environments. Recent studies have shown that the combination of auditory and visual cues enhances the sense of immersion (e.g., [START_REF] Larsson | Better presence and performance in virtual environments by improved binaural sound rendering[END_REF]). Unfortunately, high-quality spatialized audio rendering based on pre-recorded audio samples requires heavy signal processing, even for a small number of sound sources. Such processing typically includes rendering of source directivity patterns [START_REF] Savioja | Creating interactive virtual acoustic environments[END_REF]], 3D positional audio [START_REF] Begault | 3D Sound for Virtual Reality and Multimedia[END_REF]] and artificial reverberation [START_REF] Gardner | Reverberation algorithms[END_REF][START_REF] Savioja | Creating interactive virtual acoustic environments[END_REF].

Despite advances in commodity audio hardware (e.g., [Sound-Blaster 2004]), only a small number of processing channels (16 to 64) are usually available, corresponding to the number of sources that can be simultaneously rendered.

Although point-sources can be used to simulate direct and loworder indirect contributions interactively using geometric techniques [START_REF] Funkhouser | Real-time acoustic modeling for distributed virtual environments[END_REF], a large number of secondary "images-sources" are required if further indirect contributions are to be added [START_REF] Borish | Extension of the image model to arbitrary polyhedra[END_REF]]. In addition, many real-world sources such as a train (see Figure 1) are extended sound sources; one solution allowing their improved, if not correct, representation is to simulate them with a collection of point sources, as proposed in [START_REF] Sensaura | ZoomFX, MacroFX, Sensaura c[END_REF]]. This further increases the number of sources to render. This also applies to more specific effects, such as rendering of aerodynamic sounds [START_REF] Dobashi | Realtime rendering of aerodynamic sound using sound textures based on computational fluid dynamics[END_REF], that also require processing collections of point sources.

For all the reasons presented above, current state-of-the-art solutions [START_REF] Tsingos | Modeling acoustics in virtual environments using the uniform theory of diffraction[END_REF][START_REF] Fouad | An extensible toolkit for creating virtual sonic environments[END_REF][START_REF] Wenzel | A softwarebased system for interactive spatial sound synthesis[END_REF][START_REF] Savioja | Creating interactive virtual acoustic environments[END_REF], still cannot provide high-quality audio renderings for complex virtual environments which respect the mandatory real-time constraints, since the number of sources required is not supported by hardware, and software processing would be overwhelming.

To address this shortcoming, we propose novel algorithms permitting high-quality spatial audio rendering for complex virtual environments, such as that shown in Figure 1. Our work is based on the observation that audio rendering operations (see Figure 2) are usually performed for every sound source while there is significant psycho-acoustic evidence that this might not be necessary due to limits in our auditory perception and localization accuracy [START_REF] Moore | An introduction to the psychology of hearing[END_REF][START_REF] Blauert | Spatial Hearing : The Psychophysics of Human Sound Localization[END_REF].

Similar to the occlusion culling and level of detail algorithms widely used in computer graphics [START_REF] Funkhouser | Adaptive display algorithms for interactive frame rates during visualization of complex virtual environments[END_REF], we introduce a dynamic sorting and culling algorithm and a spatial clustering technique for 3D sound sources that allows for 1) significantly reducing the number of sources to render, 2) amortizing costly spatial audio processing over groups of sources and 3) leveraging current commodity audio hardware for complex auditory simulations. Contrary to prior work in audio rendering, we exploit a priori knowledge of the spectral characteristics of the input sound signals to optimize rendering. From this information, we interactively estimate the perceptual saliency of each sound source present in the environment. This saliency metric drives both our culling and clustering algorithms.

We have implemented a system combining these approaches. The results of our tests show that our solution can render highly dynamic audio-visual virtual environments comprising hundreds of point-sound sources. It adapts well to a variety of applications including simulation of extended sound sources and indoor acoustics simulation using image-sources to model sound reflections.

We also present the results of a pilot user study providing a first validation of our choices. In particular, it shows that our algorithms have little impact on the perceived audio quality and spatial audio localization cues when compared to reference renderings.

Traditional pipeline

Audio hardware (APU) pre-mixing positional audio

Figure 2: A traditional hardware-accelerated audio rendering pipeline. Pre-mixing can usually be implemented with few operations while positional audio and reverberation rendering require heavier processing.

Related Work

Our approach builds upon prior work in the fields of perceptual audio coding and audio rendering. The following sections give a short overview of the background most relevant to our problem.

Perceptual audio coding and sound masking

When a large number of sources are present in the environment, it is very unlikely that all will be audible due to masking occurring in the human auditory system [START_REF] Moore | An introduction to the psychology of hearing[END_REF]]. This masking mechanism has been successfully exploited in perceptual audio coding (PAC), such as the well known MPEG I Layer 3 (mp3) standard [START_REF] Painter | A review of algorithms for perceptual coding of digital audio signals[END_REF][START_REF] Brandenburg | mp3 and AAC explained[END_REF]. Note that contrary to PAC, our primary goal is to detect masking occurring between several sounds in a dense sound mixture rather than "intra-sound" masking. Since our scenes are highly dynamic, masking thresholds have to be continuously updated. This requires an efficient evaluation of the necessary information.

Interactive masking evaluation has also already been used for efficient modal synthesis [START_REF] Lagrange | Real-time additive synthesis of sound by taking advantage of psychoacoustics[END_REF][START_REF] Van Den Doel | Measurements of perceptual quality of contact sound models[END_REF][START_REF] Van Den Doel | Interactive simulation of complex audio-visual scenes[END_REF]] but, to our knowledge, no solution to date has been proposed to dynamically evaluate masking for mixtures of general digitally recorded sounds. Such techniques could nevertheless complement our approach for real-time synthesized sounds effects.

In the context of spatialized audio, binaural masking (i.e., taking into account the signals reaching both ears) is of primary importance. Although mp3 allows for joint-stereo coding, very few PAC approaches aim at encoding spatial audio and include the necessary binaural masking evaluation. This is quite a complex task since binaural masking thresholds are not entirely based on the spatial location of the sources but also depend on the relative phase of the signals at each ear [START_REF] Moore | An introduction to the psychology of hearing[END_REF]]. Finally, in the context of room acoustics simulation, several perceptual studies aimed at evaluating masking thresholds of individual reflections were conducted using simple image-sources simulations [START_REF] Begault | Early reflection thresholds for virtual sound sources[END_REF]]. Unfortunately, no general purpose thresholds were derived from this work.

Spatial audio rendering

Few solutions to date have been proposed which reduce the overall cost of an audio rendering pipeline. Most of them specifically target the filtering operations involved in spatial audio rendering. Martens and Chen et al. [1987;[START_REF] Chen | A spatial feature extraction and regularization model for the head-related transfer function[END_REF] proposed the use of principal component analysis of Head Related Transfer Functions (HRTFs) to speed up the signal processing operations. One approach, however, optimizes HRTF filtering by avoiding the processing of psycho-acoustically insignificant spectral components of the input signal [START_REF] Filipanits | Design and implementation of an auralization system with a spectrum-based temporal processing optimization[END_REF]]. [START_REF] Fouad | Perceptually based scheduling algorithms for real-time synthesis of complex sonic environments[END_REF] propose a level-of-detail rendering approach for spatialized audio where the sound samples are progressively generated based on a perceptual metric in order to respect a budget computing time. When the budget processing time is reached, missing samples are interpolated from the calculated ones. Since full processing still has to be performed on a per source basis, the approach might result in significant degradation for large numbers of sources. Despite these advances, high-quality rendering of complex auditory scenes still requires dedicated multi-processor systems or distributed audio servers [START_REF] Chen | Experiences with scalability of display walls[END_REF][START_REF] Fouad | An extensible toolkit for creating virtual sonic environments[END_REF]].

An alternative to software rendering is to use additional resources such as high-end DSP systems (Tucker Davis, Lake DSP, etc.) or commodity audio hardware (e.g., Sound Blaster [Sound-Blaster 2004]). The former are usually high audio fidelity systems but are not widely available and usually support ad-hoc APIs. The latter provide hardware support for game-oriented APIs (e.g., Direct Sound 3D [Direct Sound 3D 2004], and its extensions such as EAX [START_REF] Eax | Environmental audio extensions 4.0, Creative c[END_REF]). Contrary to high-end systems, they are widely available, inexpensive and tend to become de facto standards. Both classes of systems provide specialized 3D audio processing for a variety of listening setups and additional effects such as reverberation processing. In both cases, however, only a small number of sources (typically 16 to 64) can be rendered using hardware channels. Automatic adaptation to resources is available in Direct Sound but is based on distance-culling (far-away sources are simply not rendered) which can lead to discontinuities in the generated audio signal. Moreover, this solution would fail when many sources are close to the listener.

A solution to the problem of rendering many sources using limited software or hardware resources has been presented by Herder [1999a;1999b] and is based on a clustering strategy. Similar approaches have also been proposed in computer graphics for off-line rendering of scenes with many lights [START_REF] Paquette | A light hierarchy for fast rendering of scenes with many lights[END_REF]]. In Herder [1999a;1999b], a potentially large number of pointsound sources can be down-sampled to a limited number of representatives which are then used as actual sources for rendering. In theory, such a framework is general and can accommodate primary sound sources and image-sources. Herder's clustering scheme is based on fixed clusters, corresponding to a non-uniform spatial subdivision, which cannot be easily adapted to fit a pre-defined budget. Hence, the algorithm cannot be used as is for resource management purposes. Second, the choice of the cluster representative (the Cartesian centroid of all sources in the cluster) is not optimal in the psycho-acoustical sense since it does not account for the characteristics of the input audio signals.

Overview of our contributions

We propose a novel spatial audio rendering pipeline for sampled sound signals. Our approach can be decomposed into four steps (see Figure 3) repeated for each audio processing frame through time (typically every 20 to 30 milliseconds):

• First, we evaluate the perceptual saliency of all sources in the scene. After sorting all sources based on their binaural loudness, we cull perceptually inaudible sources by progressively inserting sources into the mix until their combination masks all remaining ones. This stage requires the pre-computation of some spectral information for each input sound signal.

• We then group the remaining sound sources into a predefined budget number of clusters. We use a dynamic clustering algorithm based on the Hochbaum-Shmoys heuristic [START_REF] Hochbaum | A best possible heuristic for the k-center problem[END_REF], taking into account the loudness of each source. A representative point source is constructed for each non-empty cluster.

• Then, an equivalent source signal is generated for each cluster in order to feed the available audio hardware channels. This phase involves a number of operations on the original audio data (filtering, re-sampling, mixing, etc.) which are different for each source.

• Finally, the pre-mixed signals for each cluster together with their representative point location can be used to feed audio rendering hardware through standard APIs (e.g., Direct Sound 3D), or can be rendered in software.

Sections 4 to 7 detail each of these steps. We have also conducted a pilot perceptual study with 20 listeners showing that our approach has very limited impact on audio quality and localization abilities.

The results of this study are discussed in Section 8.

Perceptual saliency of sound sources

The first step of our algorithm aims at evaluating the perceptual saliency of every source. Saliency should reflect the perceptual importance of each source relative to the global soundscape.

Perception of multiple simultaneous sources is a complex problem which is actively studied in the community of auditory scene analysis (ASA) [START_REF] Bregman | Auditory Scene Analysis, The perceptual organization of sound[END_REF][START_REF] Ellis | A perceptual representation of audio[END_REF] where perceptual organization of the auditory world follows the principles of Gestalt psychology. However, computational ASA usually attempts to solve the inverse and more complex problem of segregating a complex sound mixture into discrete, perceptually relevant auditory events. This requires heavy processing in order to segment pitch, timbre and loudness patterns out of the original mixture and remains applicable only to very limited cases.

In our case, we chose the binaural loudness as a possible saliency metric. Due to sound masking occurring in our hearing process, some of the sounds in the environment might not be audible. Our saliency estimation accounts for this phenomenon by dynamically evaluating masked sound sources.

Pre-processing the audio data

In this paper, we focus on applications where the input audio samples are known in advance (i.e., do not come from a real-time input and are not synthesized in real-time). Based on this assumption, we can pre-compute spectral features of our input signals throughout their duration and dynamically access them at runtime. Specifically, for each input signal, we generate instantaneous short-time power spectrum distribution (PSD) and tonality index for a number of frequency sub-bands. Such features are widely used in perceptual audio coding [START_REF] Painter | A review of algorithms for perceptual coding of digital audio signals[END_REF].

The PSD measures the energy present in each frequency band, while the tonality index is an indication of the signal noisiness: low indices indicate a noisier component. This index will be used for interactive estimation of masking thresholds.

Our input sound signals were sampled at 44100 Hz. In order to retain efficiency, we use four frequency bands f corresponding to 0-500 Hz, 500-2000 Hz, 2000-8000 Hz and 8000-22050 Hz. Although this is far less than the 25 critical bands used in audio coding, we found it worked well in practice for our application while limiting computational overhead.

We derive our spectral cues from a short time fast Fourier transform (FFT) [START_REF] Steiglitz | A DSP Primer with applications to digital audio and computer music[END_REF]]. We used 1024 sample long Hanningwindowed frames with 50% overlap. We store for each band f its instantaneous power spectrum distribution (i.e., the integral of the square of the modulus of the Fourier transform), PSD t ( f ), for each frame t.

From the PSD, we estimate a log-scale spectral flatness measure of the signal as:

SFM t ( f )=10 log10 µ g (PSD t ( f )) µ a (PSD t ( f )) ,
where µ g and µ a are respectively the geometric and arithmetic mean of the PSD over all FFT bins contained in band f . We then estimate the tonality index, T t ( f ), as:

T t (f )=min( SFM t (f ) -60 , 1). Note that, as a result, T t ( f ) ∈ [0, 1].
This information is quite compact (8 floating-point values per frame, i.e., 1.4 kbyte per second of input audio data at CD quality) and does not result in significant memory overhead.

This pre-processing can be done off-line or when the application is started but can also be performed in real-time for a small number of input signals since our unoptimized implementation runs about six times faster than real-time.

Binaural loudness estimation

At any given time-frame t of our audio rendering simulation, each source S k is characterized by : 1) its distance to the listener r,2)the corresponding propagation delay δ = r/c, where c is the speed of sound, and 3) a frequency-dependent attenuation A which consists in a scalar factor for each frequency band. A is derived from the octave band attenuation values of the various filters used to alter the source signal, such as occlusion, scattering and directivity filters. For additional information on these filters see [START_REF] Pierce | Acoustics. An introduction to its physical principles and applications[END_REF][START_REF] Ansi | American national standard method for the calculation of the absorption of sound by the atmosphere[END_REF][START_REF] Tsingos | Soundtracks for computer animation: sound rendering in dynamic environments with occlusions[END_REF][START_REF] Savioja | Creating interactive virtual acoustic environments[END_REF]]. For instance, in the case of a direct, unoccluded contribution from the source to the receiver, A will simply be the attenuation in each frequency band due to atmospheric scattering effects. If the sound is further reflected or occluded, A will be obtained as the product of all scalar attenuation factors along the propagation path.

Our saliency estimation first computes the perceptual loudness at time t, of each sound source k, using an estimate of the sound pressure level in each frequency band. This estimate pressure level is computed at each ear as:

P k t ( f )=Spat(S k ) × PSD k t-δ ( f ) × A k t ( f )/r, (1)
where Spat(S k ) returns a direction and frequency dependent attenuation due to the spatial rendering (e.g., HRTF processing). In our case, we estimated this function using measurements of the output level of band-passed noise stimuli rendered with Direct Sound 3D on our audio board. As a result, Equation 1 must be evaluated twice since the Spat(S k ) values will be different for the left and right ear.

The loudness values at both ears Lleft k t and Lright k t , are then obtained from the sound pressure levels at each ear using the model of [START_REF] Moore | A model for the prediction of thresholds, loudness and partial loudness[END_REF]]. Loudness, expressed in phons, is a measure of the subjective intensity of a sound referenced to a 1kHz tone1 . Based on Moore's model, we pre-compute a loudness table for each of our four frequency sub-bands assuming the original signal is a white noise. We use these tables to directly obtain a loudness value per frequency band given the value of P k t ( f ) at both ears. Going back to linear scale, a scalar binaural loudness criterion L k t is computed as:

L k t = ||10 Lleft k t /20 || 2 + ||10 Lright k t /20 || 2 . (2)
Finally, we normalize this estimate and average it over a number of audio frames to obtain smoothly varying values (we typically average over 0.1-0.3 sec. i.e., 4-12 frames).

Binaural masking and perceptual culling

We evaluate masking in a conservative manner by first sorting the sources by decreasing order according to their normalized loudness L k t and progressively inserting them into the current mix until they mask the remaining ones.

We start by computing the total power level of our scene

P TOT = ∑ k P k t ( f ).
At each frame, we maintain the sum of the power of all sources to be added to the mix, P toGo , which is initially equal to P TOT .

We then progressively add sources to the mix, maintaining the current tonality T mix , masking threshold M mix , as well as the current power P mix of the mix. We assume that sound power adds up which is a crude approximation but works reasonably well with real-world signals, which are typically noisy and uncorrelated.

To perform the perceptual culling, we apply the following algorithm, where ATH is the absolute threshold of hearing (corresponding to 2 phons) [START_REF] Moore | An introduction to the psychology of hearing[END_REF]]:

M mix = -200 P mix = 0 T = 0 P toGo = P TOT while (dB(P toGo ) > dB(P mix ) -M mix ) and (P toGo > AT H ) do add source S k to the mix

P toGo -= P k P mix +=P k T +=P k * T k T mix = T/P mix M mix =(14.5 + Bark(f max )) * T mix + 5.5 * (1 -T mix ) k++ end
Similar to prior audio coding work [START_REF] Painter | A review of algorithms for perceptual coding of digital audio signals[END_REF], we estimate the masking threshold, M mix ( f ) as:

M mix ( f )=( 14.5 + Bark(f max )) * T mix ( f ) + 5.5 * (1 -T mix ( f )) (dB),
where Bark(f max ) is the value of the maximum frequency in each frequency-band f expressed in Bark scale. The Bark scale is a mapping of the frequencies in Hertz to Bark numbers, corresponding to the 25 critical bands of hearing [START_REF] Zwicker | Psychoacoustics: Facts and Models[END_REF]. In our case we have for our four bands: Bark(500)=5, Bark(2000)= 18, Bark(8000)=24, Bark(22050)=25. The masking threshold represents the limit below which a maskee is going to be masked by the considered signal.

To better account for binaural masking phenomena, we evaluate masking for left and right ears and assume the culling process is over when the remaining power at both ears is below the masking threshold of the current mix.

Since we always maintain an overall estimate for the power of the entire scene, our culling algorithm behaves well even in the case of a scene composed of many low-power sources. This is the case for instance with image-sources resulting from sound reflections. A naive algorithm might have culled all sources while their combination is actually audible.

Dynamic clustering of sound sources

Sources that have not been culled by the previous stage are then grouped by our dynamic clustering algorithm. Each cluster will act as a new point source representing all the sources it contains (i.e., a point source with a complex impulse response). Our goal is to ensure minimal perceptible error between these auditory impostors and the original auditory scene.

Building clusters

Sources are grouped based on a distance metric. In our case, we use the sum of two spatial deviation terms from a source S k to the cluster representative C n : a distance deviation term and an angular deviation term:

d(C n , S k )=L k t βlog 10 (||C n ||/||S k ||)+γ 1 2 (1 -C n .S k ) , (3)
where L k t is the loudness criterion calculated in the previous section (Eq. 2), S k and C n are the positions of source S k and representative C n expressed in a Cartesian coordinate system relative to the listener's position and orientation.

The weighting term L k t ensures that error is minimal for perceptually important sources. In our experiments we used β = 2 and γ = 1, to better balance distance and angle errors. Since human listeners perform poorly at estimating distances, our metric is nonuniform in distance space, resulting in bigger clusters for distant sources.

We use a dynamic clustering strategy based on the Hochbaum-Shmoys heuristic [START_REF] Hochbaum | A best possible heuristic for the k-center problem[END_REF]. In a first pass, this approach selects n potential cluster representatives amongst all k sources by performing a farthest-first traversal of the point set using the metric of Eq. 3. In a second pass, sources are affected to the closest representative, resulting in a disjoint partitioning and clusters are formed. We also experimented with a global kmeans approach (e.g., [START_REF] Likas | The global k-means clustering algorithm[END_REF]), with inferior results in terms of computing time. Both methods, however, gave similar results in terms of overall clustering error (the sum for every source of the distances as defined by Eq. 3).

The representative for the cluster must ensure minimal acoustic distortion when used to spatialize the signal. In particular it must preserve the overall impression of distance and incoming direction on the listener. Thus, a good starting candidate is the centroid of the set of points in (distance, direction) space. Since we are not using a fixed spatial subdivision structure as in [Herder 1999a], the Cartesian centroid would lead to incorrect results for spatially extended clusters. Using the centroid in polar coordinates yields a better representative since it preserves the average distance to the listener.

Moreover, source loudness will affect spatial perception of sound [START_REF] Moore | An introduction to the psychology of hearing[END_REF]]. Hence, we use our loudness criterion to shift the location of the representative once the clusters have been determined. The location of the representative is thus defined, in spherical coordinates relative to the listener's location, as:

ρ C n = ∑ j L j t r j ∑ j L j t , θ C n = θ( ∑ j L j t S j ), φ C n = φ( ∑ j L j t S j ), (4)
where r j is the distance from source S j to the listener (S j 's are the sources contained in the cluster).

Figure 4 illustrates the results of our clustering technique in a simple outdoor environment and an indoor environment with sound reflections modeled as image-sources.

Spatial and temporal coherence

As a result of culling and loudness variations through time, our clustering process might produce different clusters from one frame to another. Since the clusters are mapped one-to-one with audio rendering buffers and the position of a cluster might switch abruptly, audible artefacts might be introduced. To avoid this problem, we perform a consistency check by comparing our current cluster distribution to the one obtained at the previous frame. We shuffle the order of our clusters so that the location of the ith cluster at frame t is as close as possible to the location of the ith cluster at frame t -1. We sort clusters using the summed loudness of all the sources they contain and perform the test greedily, by comparing distances between all pairs of clusters. Shuffling more perceptually relevant clusters first helps minimize possibly remaining artefacts.

Spatial rendering of clusters

The third stage of our pipeline is to compute an aggregate signal (or pre-mix) for an entire cluster based on the signals emitted by each individual sound source it contains. This signal will then be spatialized in the final stage of the pipeline.

Cluster pre-mixing

Computing this pre-mix of all sources involves a number of operations such as filtering (to account for scattering, occlusion, etc.), resampling (to account for the variable propagation delay and Doppler shifting) and 1/r distance attenuation of the input signals.

Filtering depends on the source directivity pattern or material properties in case of image-sources. Hence, it should be performed on each source individually. In our case, we use frequency dependent attenuation to account for all filtering effects. We implemented such filtering as a simple "equalization" over our four sub-bands.

For efficiency reasons, we pre-compute four band-passed copies of the original input signals. The filtered signal is then reconstructed as a sum of the band-passed copies weighted by the vector of attenuation values A (see Section 4.2).

Propagation delay also has to be accounted for on a per source basis. Otherwise, clicking artefacts appear as noticed in [Herder 1999a]. A simple method to account for time-varying non-integer delays is to re-sample the input sound signal. Simple linear interpolation gives good results in practice, especially if the signals are oversampled beforehand [START_REF] Wenzel | A softwarebased system for interactive spatial sound synthesis[END_REF].

For maximum efficiency, we implemented these simple operations using SSE (Intel's Streaming SIMD Extensions) optimized assembly code.

Being able to pre-mix each source individually has several advantages. First, we can preserve the delay and attenuation of each source, ensuring a correct distribution of the energy reaching the listener through time. Doing so will preserve most of the spatial cues associated with the perceived size of the cluster and, more importantly, the timbre of the exact mix which would suffer from "comb-filter" effects if a single delay per cluster was used. This is particularly noticeable for reverberations rendered using imagesources. A second advantage of performing pre-mixing prior to audio hardware rendering is that we can provide additional effects currently not (or poorly) supported in existing audio hardware or APIs (e.g., arbitrary directivity patterns, time delays, etc.).

Spatializing clusters in hardware

The pre-mixed signals for each cluster, along with their representatives, can be used to auralize the audio scene in a standard spatialized audio system.

Each cluster is considered as a point-source located at the position of its representative. Any type of spatial sound reproduction strategy (amplitude panning, binaural processing, etc.) applicable to a point source model can thus be used.

Spatialization can be done in software, limiting the cost of spatial audio processing to the number of clusters. More interestingly, it can be done using standard "game-audio" APIs such as Direct Sound (DS). In this case a hardware 3D audio buffer can be created for each cluster and fed with the pre-mixed signals. The sound buffer is then positioned at the location of the representative (e.g., using DS SetPosition command). We synchronize all positional commands at the beginning of each audio frame using DS notification mechanism. We also use a simple cross-fading scheme by computing a few extra samples at each frame and blending them with the first samples of the next prior to the spatialization. This eliminates artefacts resulting from sources moving in or out of clusters. In our current implementation, we use a 100-sample overlap at 44.1kHz (i.e., 2ms or about a tenth of our audio frame).

Since audio hardware usually performs sampling-rate conversion, it is also possible to assign a different rate to each cluster depending on its importance. We define the importance of a cluster as the sum of the loudness values of all the sources it contains. We sort the clusters by decreasing importance prior to rendering, and map them to a set of hardware buffers whose sampling rate is decreasing, hence requiring less data to be rendered for an equivalent time-step. This is similar in spirit to the approach of [START_REF] Fouad | Perceptually based scheduling algorithms for real-time synthesis of complex sonic environments[END_REF]] but does not require extra software processing and better integrates with current hardware rendering pipelines.

Finally, we can also benefit from additional processing offered by current consumer audio hardware, such as artificial reverberation processing, as demonstrated in the video (see the trainstation and room acoustics sequences).

Applications and performance tests

We evaluated our algorithms on two prototype applications: 1) rendering of one exterior (Highway) and one interior (Trainstation) scene with numerous point sound sources and 2) rendering of an interior scene (Busy office) including modeling of sound reflections.

All tests were conducted on a Pentium 4 3GHz PC with a nVidia GeForce FX5800 ultra graphics accelerator and a CreativeLabs Au-digy2 platinum Ex audio board. Audio was rendered using 1200sample long audio frames at 44.1kHz.

Our first two examples feature extended sound sources resulting in many point sources to render. In our case, extended sources are collections of several point sources playing potentially different signals (e.g., the helicopter has 4 sound sources for rotors, jet exhaust and engine, the river is modeled with 40 point sources, etc.). Each sound source can have its own location, orientation and directivity function (e.g., the directivity of the jet exhaust of the helicopter and voice of the pedestrians in the train station are modeled using frequency dependent cosine lobes).

The train station example contains 60 people, with a sound source for their footsteps and one for their voices, two trains, with a source at each wheel, and a number of other sources (pigeons, etc.). A total of 195 sound sources are included. The highway scene contains 100 vehicles and environmental sound effects resulting in 174 sources. The models used for visual rendering contain respectively about 70000 and 30000 polygons and no visibility optimization was used for display.

In the second type of applications we evaluated our rendering pipeline in the context of an interactive room acoustics simulation including the modeling of sound reflection of the walls of the environment. We used a path tracing algorithm to build the imagesources corresponding to sound reflections off the walls of a simple model (a small building floor containing 387 polygons). We simulated all direct paths and first-order reflections to the listener for 60 sound sources resulting in up to 360 image-sources to spatialize. Late reverberation was added to the simulation using the audio hardware's artificial reverberation engine. Note in the video how late reverberation varies as it is driven by the direct and first reflections resulting from our geometrical simulation.

Table 1 summarizes performance results for all sub-parts of our pipeline in the three environments. It also shows averaged video frame rate monitored with and without culling. Performing culling prior to clustering and pre-mixing is a key factor for the efficiency of the algorithm, since the number of sources to process is significantly reduced. In the busy office environment, rendering cannot run in real-time if culling is not applied.

Loudness, however, still has to be computed on a per-source basis so its calculation cost becomes significant as the number of sources increases. However, most of the calculation lies in the averaging process necessary to obtain smoothly varying values for the power and tonality estimates. It was our decision to leave this parameter as a variable but we believe averaging could be directly included in the pre-processing step of our approach.

Pilot validation study

In order to validate our perceptual rendering pipeline, we conducted a series of experiments aimed at evaluating the impact of culling and clustering sound sources on spatial audio rendering, both in terms of perceived audio quality and localization impairment. We also conducted cross-modal rendering tests to evaluate how visuals impact the perception of our spatial audio rendering.

Experimental conditions

We conducted our tests using non-individualized binaural presentation over headphones in a quiet office room. For spatial audio rendering, we used Direct Sound 3D accelerated by a CreativeLabs Audigy2 platinum Ex add-in board on a desktop computer. We used Sennheiser HD600 headphones, calibrated to a reference listening level at eardrum (using a 1kHz sine tone of maximum amplitude).

The age of our 20 test subjects (12 males/8 females) ranged from 13 to 52 (averaging to 31.8). Most of them were computer scientists but very few having any experience in virtual reality or acoustics.

Clustering and localization impairment

Our first set of experiments aimed at evaluating the impact of clustering on the spatial perception of the virtual soundscape. In particular, we wanted to evaluate whether localization impairment arises from the clustering process in a task-based experiment. During this test, sound source masking was disabled.

Our experiment is similar in spirit to [START_REF] Lokki | A case study of auditory navigation in virtual acoustic environments[END_REF]] but uses a different experimental procedure. We asked the test subjects to perform a walkthrough in a 3D environment consisting of many small spheres located every meter on a 2D regular grid at listener's height. Sixteen sound sources corresponding to separate tracks (drums, vocals, guitars, etc.) of a short musical segment were randomly placed at some of these locations. The user was asked to locate an additional reference sound source, emitting a white noise signal, among all the spheres by pointing at it with the mouse and pressing the space bar. Only a single try was allowed. Navigation was done with the mouse, holding the buttons to go forward or backwards. The user could also rotate in place using the arrow-keys of the keyboard.

Each subject performed the test five successive times with a variable number of clusters ranging from small to large. The number of clusters was determined randomly for every test. All subjects underwent a short training period with a reference solution (without clustering) prior to performing the test to learn how to navigate and get accustomed to the 3D audio reproduction.

Subjects performed well in the localization task. Over the 100 runs of the experiment, the source was localized exactly 74% of the time and was found 90% of the time within a 1 meter range of its true location. These results are similar to the ones reported in [START_REF] Lokki | A case study of auditory navigation in virtual acoustic environments[END_REF]]. More than a half of our subjects localized the source with 100% accuracy. Table 2 reports localization time and error (distance of the selected sphere to the actual target sphere) for the five different cluster ranges. As can be seen, the number of clusters did not have a significant impact on localization time or accuracy.

Transparency of clustering and culling

The second set of experiments aimed at evaluating the transparency of the combined clustering and culling algorithms on the perceived sound quality. We used the ITU-R 2 recommended triple stimulus, double blind with hidden reference technique, previously used for quality assessment of low bit-rate audio codecs [START_REF] Grewin | Methods for quality assessment of low bit-rate audio codecs[END_REF]]. Subjects were presented with three stimuli, R, A and B, corresponding to the reference, the test stimulus and a hidden reference stimulus 3 . The reference solution was a rendering with a single source per cluster and masking disabled.

Subjects could switch between the three stimuli at any time during the test by pressing the corresponding keys on the keyboard. The reproduction level could also be slightly adjusted around the calibrated listening level until the subject felt comfortable. Subjects were asked to rate differences between each test stimuli (A and B) and the reference R from "imperceptible" to "very annoying", using a scale from 5.0 to 1.0 (with one decimal) [START_REF] Itu-R | Methods for subjective assessment of small impairments in audio systems including multichannel sound systems[END_REF].

We used two test environments, featuring different stimulus types. In the first environment (Music) the stimulus was a 16-track music signal where each track was rendered from a different location. The locations of the sources were randomized across tests. The second environment (Voice) featured a single source with a speech stimulus but also included the 39 first specular reflections from the walls of the environment (a simple shoebox-shaped room). The location of the primary sound source was also randomized across tests.

As before, each subject performed each test five successive times with a variable number of clusters ranging from small to large. The number of clusters was determined randomly for every test.

On average, 63% of the signals were masked during the simulation for the Music environment and 33% of the sources were masked in the Voice case. Table 3 reports detailed Reference minus Stimulus marks averaged over five cluster ranges. Our algorithm was rated 4.4 on average over all tests, very close to the reference according to our subjects (a mark of 4.0 corresponded to "difference is perceptible but not annoying" on our scale). This result confirms our hypothesis that our approach primarily trades spatial accuracy and number of sources for computing time while maintaining high restitution quality. For very low cluster budgets (typically 1 to 4) however, significant differences were reported, especially in the Music experiment. In such cases cluster locations can vary a lot from frame to frame in an attempt to best-fit the instruments with higher loudness values, resulting in an annoying sensation.

The room acoustics application, while being very well suited to our algorithms, is also very challenging since incorrectly culling image-sources might introduce noticeable changes in the level, timbre or perceived duration of the reverberation. Based on the results of our experiments, our algorithms were found to perform well at 2 International Telecommunication Union 3 i.e., the subjects did do not know which of A or B was the actual test or the reference.

preserving the spatial and timbral characteristics of the reverberation in the Voice experiment. Our other room-acoustic test (busy office, shown in the video) confirms that our algorithm can automatically cull inaudible image-sources while largely preserving the auditory qualities of the reverberation.

Influence of visual rendering

We also attempted to evaluate the influence of possible interaction between image and sound rendering on the quality judgment of our perceptual audio rendering.

We repeated the above quality evaluation test using audio only and audio-visual presentation. Half of our subjects performed the test with visuals and half without. The test environment was a more complex train station environment featuring 120 sources (see video) and we had to limit our maximum number of clusters to 40 to maintain a good visual refresh rate.

Interestingly, the train station example received significantly better marks than the two other examples (see Table 3). This is probably due to its auditory complexity since it contains many simultaneous events, making it harder for the user to focus on a particular problem. For this test-case, the number of subjects was not high enough for a statistical validation of our results. Nonetheless, we note that the obtained marks are lower in the case where visuals were added. This is somewhat counter-intuitive since one could expect that the ventriloquism effect4 would have helped the subjects compensate for any spatial audio rendering discrepancy [START_REF] Vroomen | Perceptual effects of cross-modal stimulation: Ventriloquism and the freezing phenomenon[END_REF]. Actually, addition of graphics may have made it easier for the subjects to focus on discrepancies between the audio and visual rendering quality. In particular, some of our subjects specifically complained about having trouble associating voices with the pedestrians. We believe that our simple visual representation of the pedestrians (limited number of models, no facial animation) failed in this case to provide the necessary visual cues to achieve proper cross-modal integration of the voice and faces which is a situation we are highly sensitive to.

This indicates that a cross-modal importance metric should probably be used, possibly increasing the importance of visible sources (as suggested by [START_REF] Fouad | Perceptually based scheduling algorithms for real-time synthesis of complex sonic environments[END_REF]) and that care should be taken in providing a sufficiently high degree of visual fidelity to avoid disturbing effects in cross-modal experiments.

Limitations of our approach

Based on this preliminary user study, our approach seems very promising although the tests were conducted using nonindividualized binaural rendering. Using the test subjects' own measured HRTFs might reveal significant differences.

Although the method performs very well for a few hundred sound sources, it cannot easily scale to the thousands due to the cost of the clustering and pre-mixing algorithms. Loudness evaluation for every source would also become a significant bottleneck in this case. More efficient alternatives, such as a simple A-weighting of the pressure level could be used and should be evaluated. For such cases, synthesis algorithms might also be used to generate an equivalent signal for the cluster without having to pre-mix all the sources.

Our algorithm currently assumes input sound signals to be nontonal (noise-like) and uncorrelated. However, the results of the preliminary study indicate that it does perform well on a variety of signals (music, voice, natural and mechanical sounds, etc.). Better results might be achieved by computing a finer estimate of the loudness by combining two values computed assuming the signal is closer to a noise or a tone in each frequency band. This would require determining a representative frequency for each frequency band during the pre-computing step (e.g., the spectral centroid) and using an additional pure-tone loudness table. Loudness values obtained under both assumptions could then be combined using the tonality index to yield a better loudness value. A finer estimate of the pressure level of the current mix and global scene would also improve the masking process. However, this is a more difficult problem for which we do not currently have a solution. Although we perform a sort of temporal averaging estimating our criteria, we do not account for fine-grain temporal masking phenomena. This is a very interesting area for future research.

Our system currently uses pre-recorded input signals so that necessary spectral information can be pre-computed. However, we do not believe this is a strong limitation. Equivalent information could be extracted during the synthesis process if synthesized sounds are used. Our pre-processing step can also be performed interactively for a small number of real-time acquired signals (e.g., voice acquired from a microphone for telecommunication applications).

Finally, accuracy of the culling and clustering process certainly depends on the number of frequency bands used. Further evaluation is required to find an optimal choice of frequency bands.

Conclusion and future work

We presented an interactive auditory culling and spatial level-ofdetail approach for 3D audio rendering of pre-recorded audio samples. Our approach allows for rendering of complex virtual auditory scenes comprising hundreds of moving sound sources on standard platforms using off-the-shelf tools. It leverages audio hardware capabilities in the context of interactive architectural acoustics/training simulations and can be used as an automatic 3D voice management scheme in video games. Our current pipeline can render more than ten times the number of sources that could be rendered using consumer 3D audio hardware alone. Hence, future audio APIs and hardware could benefit from including such a management scheme at a lower level (e.g., as part of the DirectSound drivers) so that it becomes fully transparent to the user.

We believe our techniques could also be used for dynamic coding and transmission of spatial audio content with flexible rendering, similar to [START_REF] Faller | Binaural cue coding applied to audio compression with flexible rendering[END_REF]. This would be particularly useful for applications such as massively multi-player on-line games that wish to provide a spatialized "chat room" feature to their participants.

A pilot validation study shows that degradation in audio quality as well as localization impairment is very limited and does not seem to significantly vary with the number of used clusters.

We are currently preparing a full-blown follow-up study to provide additional statistical evaluation of the impact of our algorithm. Further experiments also need to be designed in order to evaluate several additional factors such as the pitch, beat or similarity of the signals in the culling and clustering process.

Our results so far suggest that spatial rendering of complex auditory environments can be heavily simplified without noticeable change in the resulting perceived soundfield. This is consistent with the fact that human listeners usually attend to one perceptual stream at a time, which stands out from the background formed by other streams [START_REF] Moore | An introduction to the psychology of hearing[END_REF]].

Figure 3 :

 3 Figure 3: Our novel approach combining a perceptual culling/clustering strategy to reduce the number of sources and amortize costly operations over groups of sound sources.

Figure 4 :

 4 Figure 4: Top row: note how the four clusters (in blue) adapt to the listener's location (shown in red). Bottom row: a clustering example with image-sources in a simple building environment (seen in top view). The audible image-sources, shown in green in the right-hand side image, correspond to the set of reflection paths (shown in white) in the left-hand side image.

Table 1 :

 1 Computing time breakdown for three test environments and corresponding display frame rate (FPS) with and without culling.

	environment	#sources	% culled	#clusters	loudness (ms)	culling (ms)	clustering (ms)	pre-mix (ms)	FPS w/o culling (Hz)	FPS w culling (Hz)
	Trainstation	195	62	20			1.15	0.42	0.61	2.7	19	27
	Highway	174	45	20			1.17	0.42	0.64	2.3	27	33
	Busy office	355	71	20			3.8	0.8	1.14	2.5	< 1	22
		Cluster range					All runs			Successful runs
				localization time (s)	localization error (m) found (%)	localization time (s)
				avg.	min.	max.	avg. min.	max.		avg.	min.	max.
		1to4	90.40 8.32 408.45 0.49 0.00	4.12	85.2	66.08 8.32 272.86
		5to7	52.46 7.74 151.31 0.52 0.00	3.16	88.5	34.16 7.74 113.08
		8to10	66.60 9.18 270.64 0.21 0.00	1.00	100.0	51.98 9.18 127.20
		11 to 13	52.43 6.76 204.51 0.32 0.00	2.24	82.1	49.55 6.76 204.51
		14 to 16	72.11 8.19 320.82 0.27 0.00	1.00	100.0	61.42 8.19 298.76

Table 2 :

 2 Statistics for localization time and error for all tests and successful tests only.

Table 3 :

 3 Statistics for Reference minus Stimulus marks for the Music, Voice and Trainstation environments (negative values correspond to cases where the hidden reference received a lower mark than the actual test stimulus).

		Music				Voice							Trainstation
									cluster rng	with graphics		w/o graphics			both
	cluster rng	avg.	min.	max.	cluster rng	avg.	min.	max.		avg.	min.	max.	avg.	min.	max.	avg.	min.	max.
	1to4	1.625	-2	4	1to8	1.01	-1	3	1to8	0.37	0	2	0.35	-1	3	0.36	-1	3
	5to7	0.433	-1	3	9to16	0.7	0	3	9to16	0.011	-1	1	0.25	0	2	0.189	-1	2
	8to10	0.35	-1	3	17 to 24	0.875	0	2	17 to 24	0.364	-0.1	2	0.1	-1	1	0.281	-1	2
	11 to 13	0.53	-1	3	25 to 32	0.6	-1	3	25 to 32	0.34	-0.1	2	0.5	0	2	0.42	-0.1	2
	14 to 16	0.59	-1	3	33 to 40	0.65	0	3	33 to 40	1.1	-1	4	-0.05	-1	2	0.625	-1	4

by definition phons are equal to the sound pressure level, expressed in decibels, of a 1kHz sine wave.

"presenting synchronous auditory and visual information in slightly separate locations creates the illusion that the location of the sound is shifted in the direction of the visual stimulus"[START_REF] Vroomen | Perceptual effects of cross-modal stimulation: Ventriloquism and the freezing phenomenon[END_REF].

Acknowledgments

This research was supported in part by the CREATE 3-year RTD project funded by the 5th Framework Information Society Technologies (IST) Program of the European Union (IST-2001-34231), http://www.cs.ucl.ac.uk/create/. The authors would like to thank Alexandre Olivier for the modeling and texturing work. The train station environment in the video was designed, modeled and animated by Yannick Bachelart, Frank Quercioli, Paul Tumelaire, Florent Sacré and Jean-Yves Regnault. We thank Alias|wavefront for the generous donation of their Maya software. Finally, the authors would like to thank Mel Slater for advice regarding the pilot validation study, Agata Opalach for thoroughly proof-reading the paper and the anonymous reviewers for their helpful comments.


Marc Stamminger

George Drettakis

Interactive Sampling and Rendering for Complex and Procedural Geometry

We present a new sampling method for procedural and complex geometries, which allows interactive point-based modeling and rendering of such scenes. For a variety of scenes, object-space point sets can be generated rapidly, resulting in a sufficiently dense sampling of the final image. We present an integrated approach that exploits the simplicity of the point primitive. For procedural objects a hierarchical sampling scheme is presented that adapts sample densities locally according to the projected size in the image. Dynamic procedural objects and interactive user manipulation thus become possible. The same scheme is also applied to on-the-fly generation and rendering of terrains, and enables the use of an efficient occlusion culling algorithm. Furthermore, by using points the system enables interactive rendering and simple modification of complex objects (e.g., trees). For display, hardware-accelerated 3-D point rendering is used, but our sampling method can be used by any other point-rendering approach.

Introduction and Motivation

The complexity of virtual environments has grown spectacularly over the recent years, with the advent of high performance, but affordable, graphics hardware. The paradox is that the majority of objects in such scenes often covers only a few, or even fractions of, pixels on the screen. The traditional advantage of polygon-based scan-line coherence is thus lost, while resources are wasted by transforming and clipping geometry which is either invisible, or is smaller than a pixel. This has led to the investigation of alternatives to pure polygon-based rendering in recent research. Several researchers have turned to ray-tracing based approaches (e.g., [START_REF] Parker | Interactive ray tracing[END_REF][START_REF] Walter | Interactive rendering using the Render Cache[END_REF]); An interesting recent alternative is pointbased rendering [START_REF] Grossman | Point sample rendering[END_REF][START_REF] Pfister | Surfels: Surface elements as rendering primitives[END_REF][START_REF] Rusinkiewicz | QSplat: A multiresolution point rendering system for large meshes[END_REF], which is actually an old idea revisited [START_REF] Levoy | The use of points as a display primitive[END_REF].

Point based rendering methods represent the scene's geometry as a set of point samples, that is object space position, surface normal and material data. Usually, the point samples are obtained from images of the scene that include depth and material information, but they are rendered and lit as independent small polygons or oriented disks. It has been shown that such point sample representations are well suited both for fast rendering of extremely complex geometry [START_REF] Rusinkiewicz | QSplat: A multiresolution point rendering system for large meshes[END_REF] and for high-quality visualisation [START_REF] Pfister | Surfels: Surface elements as rendering primitives[END_REF]. These methods however generate samples as a pre-process, thus restricting their use to static, unmodifiable scenes.

In this paper, we focus on points as a primitive well adapted for interactive applications and non-static scenes. We believe that points are particularly well suited for such applications for the following reasons:

Objects can be represented at different levels of details very efficiently, by properly choosing point densities (e.g., [START_REF] Rusinkiewicz | QSplat: A multiresolution point rendering system for large meshes[END_REF]). When we interactively modify procedural objects, sample recomputation is necessary for all levels of detail, at every frame. Most level of detail techniques create coarse levels bottom-up, resulting in computational expense proportional to the object's complexity. In contrast, point samples can be generated top-down, so coarse representations are obtained very quickly. In addition, a coarse representation of an object can be refined incrementally, for example for a closer view, by adding new points. If the object does not change, all old samples remain valid. Rendering procedural and dynamic objects requires adaptive refinement in critical regions. With points this can be easily achieved in a straightforward manner by adding additional points locally. Since point representations do not require the maintenance of topological information, object topology can be trivially changed. Examples are CSG models or geometry modifiers such as the wickerwork or holes modifier used in Fig. 1. In contrast, the use of meshes (e.g., of triangles), to represent dynamically changing procedural objects or non-standard topologies requires intricate book-keeping when adaptively subdividing, and careful processing to avoid cracks and other artifacts. This leads to complex implementations and numerical robustness problems. Points representing a single object or surface are independent, so they can be generated in parallel, in contrast to polygonal meshes. As we shall see, points also lead to simple solutions for visibility culling, and can take advantage of hardware acceleration more easily than for triangles, which require the use of triangle-strips which are non-trivial to generate adaptively.

We present an integrated system which incorporates the above advantages, and can be used for applications such as interactive procedural modelling for design of outdoors or indoors scenes, or VR/game type interactive viewing and manipulation. To achieve sufficiently rapid generation of point samples in this context, we introduce 5 adaptive sampling. Our new scheme allows us to hierarchically generate new samples locally, in the regions they are required, according to the current viewpoint. We apply this approach to procedural models, including displacement maps and terrains. For complex objects such as trees, we use quasi-random sampling to generate points. The continuous level of detail property of points allows smooth frame rate control. Finally, the use of a hierarchical caching mechanism, parallel computation and an direct mapping to graphics hardware vectors, significantly increases the efficiency of rendering. Examples of our approach are shown in Fig. 1.

Related work

Levoy and Whitted [START_REF] Levoy | The use of points as a display primitive[END_REF], were the first to explicitly investigate the use of points as an alternative to traditional geometry; They treated issues of displacement mapping and texture filtering. In the last few years, there has been significant interest in point-based approaches. Grossman and Dally [START_REF] Grossman | Point sample rendering[END_REF] generated point representations of objects in a preprocess, and presented efficient ways of rendering them. The Surfels approach [START_REF] Pfister | Surfels: Surface elements as rendering primitives[END_REF], concentrates on ways to efficiently render point representations, and presents several reconstruction mechanisms. Points are also used in the Q-splat algorithm [START_REF] Rusinkiewicz | QSplat: A multiresolution point rendering system for large meshes[END_REF], whose goal is to render very large polygonal data sets. The emphasis of this work is the compactness and the flexibility of the data structure and consequent rendering quality to allow treatment of enormous databases, and in particular those that do not fit into main memory. A direct ray-tracing algorithm for point-sets has been developed by Schaufler and Wann Jensen [START_REF] Schaufler | Ray tracing point sampled geometry[END_REF]. The use of particles for modeling, e.g., [START_REF] Szeliski | Surface modeling with oriented particle systems[END_REF], is also related to the use of points. The particle systems of Reeves and Blau [START_REF] Reeves | Approximate and probabilistic algorithms for shading and rendering structured particle systems[END_REF] are in the spirit of our work, however not in an interactive context. In [START_REF] Weber | Creation and rendering of realistic trees[END_REF], an explicit level of detail mechanism is applied in which leaves become points and then disappear, resulting in effects similar to ours for trees, but from a completely different standpoint.

Interactive display using ray-tracing approaches is also related to our work; examples include the Utah interactive ray-tracing environment [START_REF] Parker | Interactive ray tracing[END_REF] and the Render Cache [START_REF] Walter | Interactive rendering using the Render Cache[END_REF]. Image-based rendering techniques share several problems with points based methods, in particular for hole filling. Some of the solutions developed, for example layered depth-images e.g., [START_REF] Shade | Layered depth images[END_REF][START_REF] Lischinski | Image-based rendering for non-diffuse synthetic scenes[END_REF] and the work of Max for trees [START_REF] Max | Rendering tree from precomputed Z-buffer views[END_REF] are in a similar vein to those developed for Surfels for example.

In what follows, we will be using procedural models, often based on the noise function [START_REF] Perlin | An image synthesizer[END_REF]. We have used or been inspired by several models described in [START_REF] Musgrave | The synthesis and rendering of eroded fractal terrains[END_REF][START_REF] Lewis | Algorithms for solid noise synthesis[END_REF]. The procedural and other geometric modifiers we use are inspired by the work of Neyret [START_REF] Neyret | Modeling animating and rendering complex scenes using volumetric textures[END_REF] and Dischler e.g., [START_REF] Dischler | Efficient rendering macro geometric surface structures with bi-directional texture functions[END_REF]. The approach of Meyer and Neyret [START_REF] Meyer | Interactive volumetric textures[END_REF] in particular permits interactive viewing of similar kinds of procedural objects; The generation of slices however requires quite sophisticated hole filling techniques. The initial idea of linebased occlusion culling for which we use for terrains can be found in [START_REF] Lee | An efficient ray tracing method for terrain rendering[END_REF].

The Reyes [START_REF] Cook | The Reyes image rendering architecture[END_REF] rendering architecture is close in spirit to our approach. Objects are tessellated into polygons, until their size is under some predefined threshold. The major differences are that their system stays in the polygonal world, and the emphasis there is high quality rendering rather than interactivity; the choices and tradeoffs are thus very different from our own.

A very recent paper partially covers similar ideas for the rendering of complex static scenes [START_REF] Wand | The randomized z-buffer algorithm: Interactive rendering of highly complex scenes[END_REF], in the context of a walkthrough system.

5-Sampling: adaptive point generation

As mentioned in the introduction, procedural objects like displaced surfaces will require adaptive sampling. The 5-sampling scheme is a hierarchical object-space sampling which allows us to efficiently treat displacement mapped objects, procedural geometry modifiers and terrains. We start with an initial set of samples for each object, with each sample corresponding to a region of surface A ("sample area") on the object (Fig. 2(a)). The union of these regions entirely covers the object. The projection of the region A in image space is A¡ £¢ A cosα d 2 , where α is the angle of the surface normal to the viewing direction, and d is the distance of the surface element to the eye (Fig. 2(a)).

If we were to compute the exact projections A¡ of the sample regions onto the image plane, we would have an image of the object without holes. Since our goal is interactive rendering, we instead project the center of the sample to the image, and draw a simple primitive around it in image space (a hardware accelerated disk in practice). To avoid holes, this primitive should have an image space area which is roughly the size of A¡ . The size of these primitives provides a user-controlled tradeoff between speed and quality. The user defines a threshold A¡ min , which is the desired image size of a projected sample region. For example if A¡ min is 4, a sample will cover 2x2 pixels on average in the image. Thus for larger values of A¡ min , fewer samples will be generated, resulting in faster display. This is similar to the approach used in Q-splat [START_REF] Rusinkiewicz | QSplat: A multiresolution point rendering system for large meshes[END_REF], for controlling display speed.

Clearly, a uniform sample density in object space does not always result in a uniform density in image space, as illustrated in Fig. 2

(b)-(c). Displacement mapping makes this worse.

In what follows, we present a sampling scheme which increases sample density where required for such objects.

The Hierarchical Sampling Scheme

When choosing the initial points, we try to capture all essential object features by choosing a sufficiently dense set of points. For certain classes of procedural objects, we can use a priori information about the frequencies used to generate them. If probable undersampling is detected during evaluation of a point, new samples are created locally in the neighbourhood, which can in turn recursively spawn new samples. Appropriate sampling of a displaced surface, for instance, should increase sample density in steep regions.

To guide the refinement process, we define the undersampling factor F A¡ ¡ A¡ min which is a measure of how well the current set of samples represents the object, given the users choice of sample size A¡ min . If F 1 we meet the user define A¡ min criterion.

If F ¢ 1 too many samples were initially created and finally if F £ 1 more samples are needed, thus spawning additional refinement.

We assume that we have an ¤ u¥ v¦ parameterisation of the object considered. Ini- tially, we create a uniform grid of points in the parameter domain. The grid step size is h; we can consider u 0 §¤ h¥ 0¦ and v 0 ¨¤ 0¥ h¦ to be the initial spawning vectors, Fig. 3(a). When denser sampling is required locally, we refine or subdivide single grid points. To refine an initial grid point, four new points are inserted at relative positions:

u 1 2u 0 ¡ 5 © v 0 ¡ 5¥ v 1 u 0 ¡ 5 © 2v 0 ¡ 5¥ (1)
as well as u 1 and v 1 (see Fig. This refinement procedure can also be applied to the new grid, using offset vectors

u 2 2u 1 ¡ 5 © v 1 ¡ 5, v 2 u 1 ¡ 5 © 2v 1 ¡ 5
, u 2 and v 2 and so forth. The grid at level i has grid size 5¢

i and a rotation angle of iα. Note that this refinement process can be done locally, resulting in increased sample density where needed (see Fig. 3(c)). All descendants of a single grid point form a fractal, Fig. 3(d), which is very similar to the dragon fractal [START_REF] Schroeder | Fractals, Chaos, and Power Laws[END_REF]. The computational effort required for 5 sampling is minimal, since we can precompute vectors u i ¥ v i . In order to subdivide ¤ u¥ v¦ at level i, we simply insert new points at ¤ u¥ v¦ © u i , ¤ u¥ v¦ © v i , ¤ u¥ v¦ u i , ¤ u¥ v¦ v i . The samples form a forest, with one tree per initial sample, which are "root", Fig. 3(d). Each node has 5 children, four with an offset according the level in the tree and a self copy.

Consider the 2x2 grid shown in Figure 3(d), which has been subdivided globally several times. Some regions, shown in white in the figure, are never reached, due to the fractal like nature of our construction. Our solution is to also examine neighbours during subdivision. When subdividing a point p, we always look at its neighbours; if a neighbour p¡ lies outside, but one of its children lies inside, we attach it as a child to p, Fig. 3(e). Note that these neighbours do not exist in the initial grid or its subdivisions. Care has to be taken since other neighbours of p may then have the same children attached. For example, 1¡ and 4¡ are attached to p¡ and also to q in Fig. 3(e). The solution is to attach such "boundary children" of p¡ to a single neighbour of p¡ . We choose the neighbour which is inside the boundary and is closest to the child being considered.

This sampling scheme has nice properties. Due to its uniformity and its lack of randomness new samples are well positioned in between other samples resulting in little overlap. The scheme is purely hierarchical, i.e., every point has exactly one parent in a previous level. Two other schemes with this property are a corresponding 2-subdivision scheme (u 0 v 0 1 ¡ 2) or a 9-subdivision scheme (£

u i ¥ v i ¤ £ 1 ¡ 3¥ 0¥ 1 ¡ 3 ¤ 2 ¥ ¤ 0¥ 0¦
. The former has a very directional nature: when refining a sample, only one new sample is created, and it is always offset in a certain direction. The latter scheme has a large branching factor of 9.

Displacement mapping

Displacement mapping is a way to add very rich visual detail to otherwise simple models. However, the sample density problems mentioned above become worse when displacement mapping is applied.

Define A to be the sample area of the undisplaced surface, and A d the sample area of the displaced surface. Also, A¡ d is the projected area on the image plane of A d , with α the angle between the the undisplaced and the displaced surface normals, and β the angle between the viewing direction and the displaced surface normal, Fig. 4(a). Thus,

A d A cosα ¥ A¡ d A d cosβ d 2 cosβ cosα d 2 A (2)
The geometry of these quantities is illustrated in Fig. 4(a)-(c). We select the number of initial samples n s by assuming that all points have distance d (later on, we will account for the error due to this assumption automatically):

n s A total A¡ min d2 A A¡ min d2 ¥ ( 3
)
where A total is the total area of the object. After displacement we have:

A d A cosα A¡ min d2 cosα ¥ (4)
and after image projection:

A¡ d A d cos β d 2 A¡ min d2 d 2 cosβ cosα A¡ min F¥ (5)
which determines the undersampling factor for displacement.

Procedural Geometry Modifiers

Interpreting scene objects as point sample generators allows for procedural geometry manipulation beyond simple displacement, which can be very complicated with a surface based object representation. We attach a callback function to each object, which processes each sample point created. The function can then modify this point, remove it, or create several new points. An example is the WickerWork-modifier (see Fig. 7). For each point sample the modifier tests whether the sample is (a) in a hole of the wickerwork (¡ remove it), (b) in the region where two strings overlap (¡ create two points, one with positive, one with negative elevation), or (c) it is in the region of a single string, in which case it is just displaced accordingly. For each modified point, a new undersampling factor is computed, using Eq. ( 5). The Wickerwork-modifier returns a value larger than 1 only in case (c). Another example of modifiers are Holes in the sphere of Fig. 1.

Terrains

Terrains are different in that they are infinite, so we cannot start with a uniform sampling. Nevertheless, it is possible and effective to represent them as point sets since their image is finite. Furthermore, their heightfield nature also enables efficient occlusion culling, explained below. In the following we assume the terrain is a heightfield on the z 0 plane. The elevation is positive, with maximum value z max .

Base Plane Sampling. Obviously, it is sufficient to sample a sector of the base plane with the projection of the camera as its apex and an opening angle which is sufficient to contain all visible points. We use a parameterisation that leads to a sufficiently uniform sampling of the sector's projection onto the image plane. We first describe how the sector is computed and then define a mapping of 1¥ 1¡ £¢ 0¥ 1¡ to the sector. The medial axis of the sector is the projection of the camera's viewing direction onto the base plane. Its opening angle is determined such that it contains all visible base plane points. We can parameterise this sector using a normalised medial axis vector ¥m and a perpendicular vector ¥ p. The sector point defined by parameters ¤ u¥ d ¦ is 5(c)). We scale p so that u is in the range 1¥ 1¡ . For d a possibly infinite interval d min ¥ d max ¡ is needed to address the entire visible sector. If the horizon is visible, d max equals infinity (Fig. 5(a)), otherwise it can be obtained from the intersection of the viewing frustum with the base plane (Fig. 5(b),(d)). The value d min can be determined accordingly (Fig. 5(a)-(b)), however it usually has to be decreased further since invisible base plane points are likely to be elevated into the viewing frustum.

¤ ¦¥m © u ¥ p¦ d (Figure
For the parameterisation of the interval d min ,d max ¡ we consider the typical case where the viewing direction is parallel to the base plane. In this case, the y i -coordinate of a projected point is proportional to 1 Another alternative would be to directly parameterise the image plane with ¤ u¥ v¦ and map these to the base plane point visible through this image point. Our parameterisation however fits well with our occlusion culling method described below. Terrain Generation. We generate a set of points on the base plane sector using a uniform grid of valid ¤ u¥ v¦ values. Due to our choice of parameterisation, the image projections of these points on the base plane are approximately uniform. By elevating these points, the sampling on the image plane becomes non-uniform, resulting in the same kind of undersampling as for finite displaced objects.

If ¤ u¥ v¦ are sampled uniformly with step sizes ¤ ∆u¥ ∆v¦ , the base plane area A represented by this sample is approximately (see Fig. 6(c)):

A ¢ ∂p¤ u¥ v¦ ∂u ∂p¤ u¥ v¦ ∂v ∆u∆v ¢ d ¤ v¦ 3 ¤ 1 ¡ d max 1 ¡ d min ¦ ∆u∆v¡ (6)
Elevating this area (A d , Fig. 6(c)-(d)) and projecting it onto the image plane results in

A¡ d ¢ d ¤ v¦ 3 ¤ 1 ¡ d max 1 ¡ d min ¦ cos γ ∆u ∆v cosβ d¡ 2 ¥ (7)
so the undersampling factor F A¡ d ¡ A min . Note that this factor accounts for under-and oversampling due to non-optimal sector sampling as well as due to the displacement.

Occlusion culling.

The sector parameterisation has a nice property for occlusion culling: if we consider base plane lines with constant u, their projection also forms a line in image space. By elevating these points, their image is only moved along this line (see Figure 6(b)). Consequently, a point at ¤ u¥ v¦ can only be hidden by a point ¤ u¥ v¡ ¦ , where v¡ ¢ v. This property is reportedly used in computer games and has been used before e.g., in [START_REF] Lee | An efficient ray tracing method for terrain rendering[END_REF].

As a result, we can render the terrain line by line, where each line has constant u. The line u u l is rendered from front to back, uniformly sampling v in the interval 0¥ 1¡ . The current horizon point is the point on the line that currently has the maximum y-coordinate in the image. A later point at v¡ £ v is hidden if it is below the horizon. We do this occlusion test twice: first we test whether the point would be visible with maximum elevation. If it cannot be rejected trivially, the real elevation z is computed and the test is repeated with z, avoiding many costly elevation computations.

We only perform occlusion culling for initial sample points. Child samples have different u and violate the strict ordering along v. A point only spawns samples if it is not occluded. Nonetheless, an initial point can be occluded, while one of its children is not. We account for this by approximating the maximum elevation of the point and its children by extrapolating the elevation to the children using the terrain gradient at the point. We only discard points if none of its children could be visible, based on this computation.

Complex Geometry

Point based rendering is also a highly efficient means for the rendering of complex geometry, e.g., defined by polygons. Others have investigated this approach very successfully (QSplat [START_REF] Rusinkiewicz | QSplat: A multiresolution point rendering system for large meshes[END_REF], Surfels [START_REF] Pfister | Surfels: Surface elements as rendering primitives[END_REF]), using precomputed samples.

To achieve rapid sample generation for complex geometry, we create a vector of point samples for every object, randomly distributed over the object. There is no spatial order within the vector. We generate this vector by addressing all surface points with ¤ u¥ v¦ -coordinates and sampling the object using quasi random numbers, in our case the first two Halton-sequences [START_REF] Niederreiter | Random Number Generation and Quasi-Monte Carlo Methods[END_REF]. This way, we can create an arbitrarily long vector and, more importantly, we can extend this efficiently when needed.

Due to our construction, any prefix of the vector contains samples which are quite evenly distributed over the object's surface. At each frame, we determine how many samples n s are necessary to obtain adequate image sample density. If the current vector has fewer elements, it is filled to size n s , by using subsequent samples of the Halton sequence. Only the first n s samples are rendered, since the vector may be longer.

To determine n s , we compute the minimum distance d of the object's bounding box to the camera. If the object's surface area is A, we select n s A ¡ d2 A¡ min . Note that this neglects the cosine of the surface normal to the camera, so n s reflects the "worst" case of an object directly facing the viewer.

Our approach provides straightforward level-of-detail (LOD) control. By selecting n s , we have an almost continuous degree of accuracy. Objects with m polygons can be rendered with good quality even with n s ¢ m samples. Since we always render the prefix of a list up to a certain number, the overall appearance of the object will not change quickly from frame to frame, and flickering or popping artifacts are diminished, compared to traditional LOD approaches.

Finally, simple time dependent object modifications can be performed on-the-fly, for example the movement of trees in a turbulent breeze. For each point sample of a tree we precompute the distance to the stem. According to this distance the point is moved in the current wind direction. Wind directions are defined by a turbulence function. We compute the wind direction for each object at its center and use this direction for the entire object. We do not insert additional samples to fill potential resulting holes, as a display speed/computation tradeoff.

System Issues

Sample distance and splat size

Almost continuous and predictable quality control are a major advantage of point based rendering methods. Very fast images can be obtained by rendering few, large points, whereas many small points require more time, but give accurate results. In our implementation the user can steer this tradeoff by defining the desired sample density in the rendered image: the average distance in pixels between samples. Using this size, the point radius is selected automatically, such that holes are almost always avoided.

Alternatively, the user can select a desired frame rate. The time needed for rendering each frame is measured and the sample density parameter is adapted continuously. During motion, the user might see coarse, approximate solutions at high frame rates, which refine quickly as soon as motion stops. This is illustrated in Fig 8, and in the accompanying movie (see the publications page at http://www-sop.inria.fr/reves).

Caching of 5-sampled Points

If we consider the samples obtained by the 5 scheme as a forest, the depth of some trees changes from frame to frame, but the upper parts in the hierarchy remain the same. It is thus natural to store the forest computed in each frame and to reuse it for the next frame. Such a forest is stored per object.

The cached forest can then be traversed top down: for each node the refinement criterion is reevaluated considering the new camera. If a leaf in the cache needs to be refined, new children are computed. If an inner node is classified as a leaf in the new frame, all the children in the cache are skipped. This caching mechanism can significantly reduce the sample computations; the subdivision criterion however has to be evaluated for every sample at every frame.

OpenGL issues

For point rendering we simply use OpenGL GL_POINTS. Evidently, higher quality rendering could be achieved by using ellipsoidal splats as in the Surfels approach [START_REF] Pfister | Surfels: Surface elements as rendering primitives[END_REF]. The current implementation of hardware supported points limits our ability to correctly treat texture and transparency. Use of a Surfels-type rendering method would resolve these problems.

The rendering of unmodified complex geometry is accelerated using OpenGL's glVertexPointer-calls, where an entire array of points can be passed to OpenGL in one call. If the object is composed of different materials, we generate random points on the object, but store these in different vectors, one for each material. Then n s is distributed over the arrays, and each material's sample vector is rendered separately with the according material properties, reducing expensive OpenGL material switches.

Parallelism

Point sample generation is a perfect candidate for parallelisation. No neighbourhood or coherence between samples is considered, so samples can be generated on parallel processors or remote machines. The 5 subdivision scheme leads to a forest of completely independent trees, which can be computed independently on parallel processors.

Results

We have tested our system in three different scenarios. The first is an indoors procedural design test, where we add procedural objects to the scene, and interactively select their parameters. The second is the design of an outdoors world, in which we choose procedural parameters for the terrain. Finally, we have a VR-or game-style scenario, where the user can move around and interact with the scene.

The indoor design example is illustrated in Fig. 7, including an indoor plant moving in the wind of a fan, a procedural wicker work basket and a rock paperweight. The user can move in this scene at 13 frames per second (fps) 1 . Modifications of the procedural objects as shown in the figure can be done at 8 fps for the paperweight, and 4 fps for the basket. During modification of the paperweight object 8% of the time is spent on the base object sample generation, 75% on the displacement computation, and 3.5% on the refinement decisions. When the user moves around the unchanged object, rendering becomes dominant. The time needed for refinement goes up to 30%, whereas the generation of new samples requires limited resources.

For the outdoor design and VR scenarios, we use procedural terrains based on fractal turbulence functions generated by Poisson events [START_REF] Lewis | Algorithms for solid noise synthesis[END_REF]. In order to give higher regions a rougher appearance, we start with only a small number of turbulence octaves (e.g., 3). If the resulting height is above a user-defined threshold, additional octaves are blended in, resulting in smooth valleys and rocky mountains (this effect can also be obtained with multifractals [START_REF] Ebert | Texturing and Modeling: A Procedural Approach[END_REF]). By applying an exponential function, the valleys can be made wider and the mountains steeper. Since we know the area represented by each sample, we stop this evaluation process for detail that is too small to be represented by the sample. This avoids computation for unnecessary or even undesired detail. The model is fast enough for on-the-fly terrain generation but as a more efficient alternative, we can replace it by a tiled, precomputed terrain texture. We also implemented the sky model of [START_REF] Preetham | A practical analytic model for daylight[END_REF], which is precomputed and mapped to a dome around the scene, adding further realism to our outdoors views.

An example of an interactive design session for an outdoors scene in illustrated in Fig. 8, where we add mountains and trees. The center right image is rendered with 280,000 points, 23,000 of which are the online evaluated terrain. Without occlusion culling the number of terrain samples is 40,000. The trees can be moved at 14 fps, if the view point does not change and thus the terrain does not require recomputation. The rightmost image is obtained by increasing sample density, resulting in 3.3 million points, which took 2 seconds. The terrain is always computed by an additional thread on the second processor.

In the VR-or game-like scenario, the user moves around in a coast scene. All terrain points below water level are replaced by lake surface samples, which in turn is displaced according to a procedural wave function (e.g., the ripples in the accompanying video). For the images in Fig. 9 we use a precomputed terrain stored in a texture. Again 1,000 trees were added. The trees are moving in the wind, the user can create ripples in the lake by throwing virtual stones. At 400x400 resolution we obtain about 8 fps.

Conclusion and Discussion

We have presented a novel sampling approach, which generates samples for procedural and complex geometry efficiently. The approach, coupled with caching mechanisms, is fast enough for interactive viewing on todays PC graphics hardware. Our object-space sampling is based on a user-controlled speed/quality threshold A¡ min , namely the desired minimum image space coverage of a sample. This in turns controls the sample density.

For procedural objects, we introduced 5-sampling. Local refinement is controlled by an undersampling factor, defined by the A¡ min threshold. We showed how this factor is computed for displacement maps and other procedural modifiers. For terrains, we introduced a suitable parameterisation, also allowing occlusion culling. Complex unmodified geometries such as trees can also be sampled efficiently with Halton sequences. Samples are stored in vectors which can be efficiently and incrementally updated.

Evidently, there are certain cases where point-based representations are not the best choice. Insufficient point densities or rendering techniques lead to visible holes in continuous surfaces. Our method strives to address this problem by choosing sample densities based on the current viewpoint. Furthermore, coherence over smooth surfaces cannot be exploited. Clearly, polygons are more efficient when they cover many pixels on the screen, but when this is not the case, point representations become the natural choice.

The main limitation of our approach is currently the expense of generating points. Using a hierarchy on very complex objects and a more general occlusion culling approach for all objects would reduce the number of samples generated. Hardware accelerated noise functions would also greatly improve the performance of our method. Better hardware support of point rendering could improve the quality of our images. Other directions include rendering with shadows or more sophisticated illumination models. Fig. 7. Interactive design of an interior environment. To a radiosity solution of an office rendered with polygons, we added a complex tree, a wicker work basket and a paper weight, all displayed with 75,000 points. After turning on the fan, the tree is moving in the wind (center, 13 fps at 400x400). The images on the right show the interactive change of parameters of procedural objects. Top row: changes at 4 fps, bottom row: 8 fps, the last one at 1.5 fps. Fig. 8. Interactive design of an outdoors scene (resolution 400x400). We start with a simple terrain (left: 23,000 points, 6 fps), add 1000 chestnut trees made of 150,000 triangles each and add two clouds (280,000 points, 5 fps). If we increase accuracy, we get the right image using 3,300,000 points after 2 sec. Fig. 9. Two snapshots of an interactive session in a dynamic procedural virtual world. The user navigates at about 8 fps. The trees are moving in the wind and the user "throws rocks" into the lakes. The terrain is precomputed and stored in a texture.

Fig. 1 .

 1 Fig. 1. Examples of our point sample generation algorithm.

Fig. 2 .

 2 Fig. 2. (a) The basic point sample geometry in world and image space. (b) Object curvature results in denser sampling as we approach silhouettes. Projective foreshortening results in denser image space sampling further in the distance. (c) After displacement, holes appear in the steep parts (left). With adaptive insertion of new samples, these holes are filled (right),

Fig. 3 .¡ 2 ¢

 32 Fig. 3. 5 sampling. (a) initial grid with vectors v 0 , u 0 (b) once subdivided and rotated grid spanned by vectors v 1 , u 1 (c) adaptively refined sample set (d) fractal covered by generated samples (e) resolving boundary problems

Fig. 4 .

 4 Fig. 4. Undersampling factor determination.

Fig. 5 .

 5 Fig. 5. Side view: (a) horizon is visible and thus d max ¤ ∞, (b) horizon invisible, d max is finite. Top view: (c) Paramterization of a sector, (d) v parameter.

¡d, 1 ¡ d min v¤ 1 ¡ d max 1 ¡ d min ¦ ¦ ¢ 1 ,

 1111 if the horizon is at y i 0. Consequently, we compute d ¤ v¦ ¤ where v § 0¥ 1¡ . Note that for d max ∞ we can set 1 ¡ d max 0. Thus, we parameterise the sector by p¤ u¥ v¦ ¤ ¦¥m © u ¥ p¦ d ¤ v¦ , where u § 1¥ 1¡ and v § 0¥ 1¡ (Fig. 5(d)).

Fig. 6 (Fig. 6 .

 66 Fig.6(a) shows a uniform ¤ u¥ v¦ grid of this parameterisation, projected to image space. If the viewing direction is parallel to the base plane (Fig.6(a)), the grid remains uniform, if the viewing direction moves up or down (Fig.6(b)), the projected pattern becomes less uniform. However, this is just an initial pattern; if critical undersampling is detected, we automatically insert new samples.

All timings are on a Pentium III PC at 733 Mhz (Sgi 330), with a VR3 (NVidia Quadro) graphics card.

Acknowledgements

Thanks to F. Durand, F. Neyret, and J. Stewart for providing comments on an early draft. The sky model integration was done by M. Weber, based on code of B. Smits. The first author is supported by a Marie-Curie postdoctoral Fellowship. iMAGIS is a joint research project of CNRS/INRIA/UJF/INPG.