Breaking the 64 spatialized sources barrier

Nicolas Tsingos, Emmanuel Gallo and George Drettakis REVES / INRIA-Sophia Antipolis http://www-sop.inria.fr/reves Spatialized soundtracks and sound-effects are standard elements of today's video games. However, although 3D audio modeling and content creation tools (e.g., Creative Lab's EAGLE [START_REF]Creative Labs[END_REF]) provide some help to game audio designers, the number of available 3D audio hardware channels remains limited, usually ranging from 16 to 64 in the best case. While one can wonder whether more hardware channels are actually required, it is clear that large numbers of spatialized sources might be needed to render a realistic environment. This problem becomes even more significant if extended sound sources are to be simulated: think of a train for instance, which is far too long to represented as a point source. Since current hardware and APIs implement only point-source models or limited extended source models [START_REF]Direct X homepage[END_REF][START_REF]EAX © Creative Labs[END_REF][START_REF] Zoomfx | [END_REF], a large number of such sources would be required to achieve a realistic effect (view Example1). Finally, 3D-audio channels might also be used for restitution-independent representation of surround music tracks, leaving the generation of the final mix to the audio rendering API but requiring the programmer to assign some of the precious 3D channels to the soundtrack. Also, dynamic allocation schemes currently available in game APIs (e.g. Direct Sound 3D [START_REF]Direct X homepage[END_REF]) remain very basic. As a result, game audio designers and developers have to spend a lot of effort to best-map the potentially large number of sources to the limited number of channels. In this paper, we provide some answers to this problem by reviewing and introducing several automatic techniques to achieve efficient hardware mapping of complex dynamic audio scenes in the context of currently available hardware resources. We show that clustering strategies, some of them relying on perceptual information, can be used to map a larger number of sources to a limited number of channels with little impact to the perceived audio quality. The required pre-mixing operations can be implemented very efficiently on the CPU and/or the GPU (graphics processing unit), out-performing current 3D audio boards with little overhead. These algorithms simplify the task of the audio designer and audio programmer by removing the limitation on the number of spatialized sources. They permit rendering of extended sources or discrete sound reflections, beyond current hardware capabilities. Finally, they integrate well with existing APIs and can be used to drive automatic resource allocation and level-of-detail schemes for audio rendering.

In the first section, we present an overview of clustering strategies to group several sources for processing through a single hardware channel. We will call such clusters of sources auditory impostors. In the second section, we describe recent techniques developed in our research group that incorporate perceptual criteria in hardware channel allocation and clustering strategies. The third section is devoted to the actual audio rendering of auditory impostors. In particular, we present techniques maximizing the use of all available resources including the CPU, APU (audio processing unit) and even the GPU which we turn into an efficient audio processor for a number of operations. Finally, we demonstrate the described concepts on several examples featuring a large number of dynamic sound sources 1 .

Clustering sound sources

The process of clustering sound sources is very similar in spirit to the level-of-detail (LOD) or impostor concept introduced in computer graphics [START_REF] Luebke | Level of Detail for 3D Graphics[END_REF]. Such approaches render complex geometries using a smaller number of textured primitives and can scale or degrade to fit specific hardware or processing power constraints whilst limiting visible artefacts. Similarly, sound-source clustering techniques (Figure 2) aim at replacing large sets of point-sources with a limited number of representative point-sources, possibly with more complex characteristics (e.g. impulse response). Such impostor sound-sources can then be mapped to audio hardware to benefit from dedicated (and otherwise costly) positional audio or reverberation effects (see Figure 3). Clustering schemes can be divided into two main categories: fixed clustering, which uses a predefined set of clusters, and adaptive clustering which attempts to construct the best clusters on-the-fly.

Two main problems in a clustering approach are the choice of a good clustering criteria and a good cluster representative. The answers to these questions largely depend on the available audio spatialization and rendering back-end and whether the necessary software operations can be performed efficiently. Ideally, the clustering and rendering pipeline should work together to produce the best result at the ears of the listener. Indeed, audio clustering is linked to human perception of multiple simultaneous sound sources, a complex problem that has received a lot of attention in the acoustics community [START_REF] Blauert | Spatial Hearing : The Psychophysics of Human Sound Localization[END_REF] . This problem is also 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]. However, ASA attempts to solve the dual and more complex problem of segregating a complex sound mixture into discrete, perceptually relevant components.

Fixed-grid clustering

The first instance of source clustering was introduced by Herder [START_REF] Herder | Optimization of sound spatialization resource management through clustering[END_REF][START_REF] Herder | Visualization of a clustering algorithm of sound sources based on localization errors[END_REF] in 1991 who grouped sound sources by cones in direction space around the listener, the size of which was chosen relying upon available psycho-acoustic data on the spatial resolution of human 3D hearing. He also discussed the possibility of grouping the sources by distance or relative-speed to the listener. However, it is unclear that relative speed, which might vary a lot from source to source is a good clustering criteria. One drawback of fixed grid clustering approaches is that they cannot be targeted to fit a specified number of (non-empty) clusters. Hence, they can end-up being sub-optimal (e.g., all sources fall into the same cluster while sufficient resources are available to process all of them independently) or might provide too many non-empty clusters for the system to render any further (see Figure 5).

It is however possible to design a fixed grid clustering approach that works pretty well by using direction-space clustering and more specifically "virtual surround". Virtual surround renders the audio from a virtual rig of loudspeakers (see Figure 4). Each loudspeaker can be mapped to a dedicated hardware audio buffer and spatialized according to its 3D location. This technique is widely used for headphone rendering of 5.1 surround film soundtracks (e.g., in software DVD players), simulating a planar array of speakers. Extended to 3D, it shares some similarities with directional sound-field decomposition techniques such as Ambisonics [34]. However, not relying on complex mathematical foundations, it is less accurate but does not require any specific audio encoding/decoding and fits well with existing consumer audio hardware. Common techniques (e.g. amplitude panning [START_REF] Pulkki | Virtual Sound Source Positioning using vector Base amplitude panning[END_REF]) can be used to compute the gains that must be applied to the audio signals feeding the virtual loudspeakers in order to get smooth transitions between neighboring directions. The main advantage for such an approach is its simplicity. It can be very easily implemented in an API such as DirectSound 3D (DS3D). The main application is responsible for the pre-mixing of signals and panning calculations while the actual 3D sound restitution is left to DS3D. Although there is no way to enforce perfect synchronization between DS3D buffers, the method appears to work very well in practice. Example 2 and Example 3 feature a binaural rendering of up to 180 sources using two different virtual speaker rigs (respectively an octahedron and an icosahedron around the listener) mapped to 6 and 18 DS3D channels. One drawback of a direction-space approach is that reverberation-based cues for distance rendering, e.g., in EAX [START_REF]EAX © Creative Labs[END_REF] which implements automatic reverberation tuning based on source-tolistener distance, can no longer be used directly. One work-around this issue is to use several virtual speaker rigs located at different distances from the listener, at the expense of more 3D channels.

Adaptive positional clustering

In contrast to fixed-grid methods, adaptive clustering aims at grouping sound sources based on their current 3D location (including incoming direction and distance to the listener) in an "optimal" way. Adaptive clustering has several advantages: 1) it can produce a requested number of non-empty clusters, 2) it will automatically refine the subdivision where needed, 3) it can be controlled by a variety of error metrics. Several clustering approaches exist and can be used for this purpose [START_REF] Fränti | On the splitting method for vector quantization codebook generation[END_REF][START_REF] Fränti | Randomised local search algorithm for the clustering problem[END_REF][START_REF] Likas | The global k-means clustering algorithm[END_REF]. For instance, global k-means techniques [START_REF] Likas | The global k-means clustering algorithm[END_REF] start with a single cluster and progressively subdivide it until a specified error criteria or number of clusters has been met. This approach constructs a subdivision of space that is locally optimal according to the chosen error metric. Example 4 shows the result of such an approach applied to a simple example where three spatially-extended sources are modeled as a set of 84 point-sources. Note the progressive de-refinement when the number of clusters is reduced and the adaptive refinement when the listener is moving closer or away from the large "line-source". In this case, the error metric was a combination of distance and incident direction onto the listener. Cluster representatives were constructed as the centroid in polar coordinates of all sources in the cluster.

Perceptually-driven source prioritization and resource allocation

So far, very few approaches have attempted to include psycho-acoustic knowledge in the audio rendering pipeline. Most of the effort has been dedicated to speeding up signal processing cost for spatialization purposes, e.g. spatial sampling of HRTF or filtering operations for headphone rendering [START_REF] Begault | 3D Sound for Virtual Reality and Multimedia[END_REF][START_REF] Martens | Principal Components Analysis and Resynthesis of Spectral Cues to Perceived Direction[END_REF]. However, existing approaches never consider the characteristics of the input signal. On the other hand, important advances in audio compression, such as MPEG-1 layer 3 (mp3), have shown that exploiting both input signal characteristics and our perception of sound could provide unprecedented quality vs. compression ratios [START_REF] Brandenburg | MP3 and AAC explained[END_REF][START_REF] Painter | A review of algorithms for perceptual coding of digital audio signals[END_REF][START_REF] Rangachar | Analysis and improvement of the MPEG-1 audio layer III algorithm at low bit-rates[END_REF]. Thus, taking into consideration signal characteristics in audio rendering might help to design better prioritization and resource allocation schemes, perform dynamic sound source culling and improve the construction of clusters. However, contrary to most perceptual audio coding (PAC) applications, that encode once to be played repeatedly, the soundscape in a video game is highly dynamic and perceptual criteria have to be recomputed at each processing frame for a possibly large number of sources. We propose a perceptually-driven audio rendering pipeline with clustering, illustrated in Figure 6.

Prioritizing sound sources

Assigning priorities to sound sources is a fundamental aspect of resource allocation schemes. Currently, APIs such as DS3D use basic schemes based on distance to the listener for on-the-fly allocation of hardware channels. Obviously, such schemes would benefit from the ability to sort sources by perceptual importance or "emergence" criteria. As we already mentioned, this is a complex problem, related to the segregation of complex sound mixtures as studied in the ASA field. We experimented with a simple, loudness-based model that appears to give good results in practice, at least in our test examples. Our model uses power spectrum density information pre-computed on the input waveforms (for instance, using short time Fast Fourier Transform) for several frequency bands. This information does not represent a significant overhead in terms of memory or storage space. In real-time, we access this information, modify it to account for distance attenuation, directivity of the source, etc., and map the value to perceptual loudness space using available loudness contour data [START_REF] Zwicker | Psychoacoustics: Facts and Models[END_REF][START_REF] Moore | A Model for the Prediction of Thresholds, Loudness and Partial Loudness[END_REF]. We use this loudness value as a priority criterion for further processing of sound sources.

Dynamic sound source culling

Sound source culling aims at reducing the set of sound sources to process by identifying and discarding inaudible sources. A basic culling scheme determines whether the source amplitude is below the absolute threshold of hearing (or below a 1-bit amplitude threshold). Using dynamic loudness evaluation for each source, as described in the previous section, makes this process much more accurate and effective. Perceptual culling is a further refinement aiming at discarding sources that are perceptually masked by others. Such techniques have been recently used to speed-up modal/additive synthesis [START_REF] Van Den Doel | Measurements of Perceptual Quality of Contact Sound Models[END_REF][START_REF] Lagrange | Real-time Additive Synthesis of Sound by Taking Advantage of Psychoacoustics[END_REF], e.g., for contact-sound simulation. To exploit them for sampled sound signals, we pre-compute another characteristics of the input waveform, the tonality. Based on PAC techniques, an estimate of the tonality in several sub-bands can be calculated using short-time FFT. This tonality index [START_REF] Rangachar | Analysis and improvement of the MPEG-1 audio layer III algorithm at low bit-rates[END_REF] estimates whether the signal in each sub-band is closer to a noise or a tone. Masking thresholds, which typically depend on such information, can then be dynamically evaluated. Our perceptual culling algorithm sorts the sources by perceptual importance, based on their loudness and tonality, and progressively inserts them into the current mix. The process stops when the sum of remaining sources is masked by the sum of already inserted sources. In a clustering pipeline, sound source culling could be used either before or after clusters are formed. Both solutions have their own advantages and drawbacks. Performing culling first reduces the load of the entire subsequent pipeline. However, culling in this case must be conservative or take into account more complex effects, such as spatial unmasking, i.e., sources we can still hear distinctly because of our spatial audio cues, although one would mask the other if both were at the same location [START_REF] Hirsh | The influence of interaural phase on interaural summation and inhibition[END_REF]. Unfortunately, little data is available to quantify this phenomenon. Performing culling on a per-cluster basis reduces this problem since sources within a cluster are likely to be close to each other. However, the culling process will be less efficient since it will not consider the entire scene. In the following train-station example, we experimented with the first approach, without spatial unmasking, using standard mp3 masking calculations [START_REF] Rangachar | Analysis and improvement of the MPEG-1 audio layer III algorithm at low bit-rates[END_REF].

Perceptually weighted clustering

The adaptive clustering scheme presented in the previous section can also benefit from psycho-acoustic metrics. For instance, dynamic loudness estimation can be used to weight the error metric in the clustering process so that clusters containing louder sources get refined first. It can also be used to provide a better estimate for the representative of the cluster as a loudness-weighted average of the location of all sources in the cluster.

Rendering auditory impostors

The second step of the pipeline is to render the groups of sound sources resulting from the clustering process. Although we can replace a group of sound sources by a single representative for localization purposes, a number of operations still have to be performed individually for each source. Such "pre-mixing" operations, usually available in 3D audio APIs, include variable delay lines, resampling and filtering (e.g., occlusions, directivity functions and distance attenuation). For a clustering-based rendering pipeline to remain efficient, these operations must be kept simple and implemented very efficiently since they can quickly become the bottleneck of the approach. Another reason why one would want to keep as much per-source processing as possible is to avoid sparseness in the impulse response and comb-filtering effects that would result from using a single delay and attenuation for each cluster (see Figure 7).

Efficient pre-mixing using CPU and GPU

Pre-mixing operations can be efficiently implemented on the CPU and even on the GPU. For instance, premixing for Examples 3 and 4 consists of a linear interpolation for Doppler shifting and resampling (which works well, especially if the input signals are over-sampled beforehand [START_REF] Wenzel | A software-based system for interactive spatial sound synthesis[END_REF]), and three additions and multiplications per sample for gain control and panning on the triplet of virtual speakers closest to the sound's incoming direction. We implemented all operations in assembly language using 32 bit floating-point arithmetic. In our examples, we used audio processing frames of 1024 samples at 44.1KHz. Pre-mixing 180 sound sources required 38% of the audio frame in CPU time on a Pentium4 mobility 1.8GHz, 70% on a Pentium3 1GHz.

For the train-station application presented in the next section, pre-mixing consisted of a variable delay line implemented using linear interpolation plus 3-band equalization (input signals were pre-filtered) and accumulation. Equalization was used to reproduce frequency-dependent effects such as source directivity and distance attenuation. For this application we experimented with GPU audio premixing. By loading audio data into texture memory (see Figure 8), it is possible to use standard graphics rendering pipelines and APIs to perform premixing operations. Signals pre-filtered in multiple frequency sub-bands are loaded into multiple color components of texture data. Audio premixing is achieved by blending several textured line segments and reading back the final image. Reequalization can be achieved through color modulation. Texture resampling hardware allows resampling of audio data and the inclusion of Doppler shift effects (Figure 9). Our test implementation currently only supports 8-bit mixing due to limitations of frame buffer depth and blending operations on the hardware at our disposal. However, recent GPUs support extended resolution frame-buffers and accumulation could be performed using 32-bit floating-point arithmetic using pixel shaders. With performance comparable to optimized (and often non-portable) software implementations, GPU pre-mixing can be implemented using multi-platform 3D graphics APIs. When possible, using the GPU for audio processing will reduce the load on the main CPU and help balance the load between CPU, GPU and APU.

Applications

Rendering of complex scenes with extended sound sources using DS3D

The techniques discussed above directly apply to audio rendering of complex, dynamic, 3D scenes containing numerous point sources. They also apply to rendering of extended sources, modeled as a collection of point sources such as the train in Figure 10. In this train station example with 160 sound sources, we were able to render both the visuals (about 70k polygons) and pre-mix the audio on the GPU (ATI Radeon mobility 5700 on a Compaq laptop). Pre-mixing with the CPU (Pentium4 mobility 1.8GHz), using a C++ implementation, resulted in degraded performance (i.e., reduced visual refresh) but improved audio quality. Perceptual criteria used for loudness evaluation, source culling and clustering were pre-computed on the input signals using three sub-bands (0-500 Hz,500-2000 Hz,2000+ Hz) and short audio frames of 1024 samples at 44.1kHz. For more information and technical details, we refer the reader to [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF]. Audio rendering was implemented using DS3D accelerated by the built-in SoundMax chipset (32 3D audio channels). A drawback of the approach is increased bus traffic, since the audio signals for each cluster are premixed outside the APU and must be continuously streamed to the hardware channels. Also, since aggregate signals and representative location for each cluster are continuously updated at each audio frame to best-fit the current soundscape, care must be taken to avoid artefacts when switching the position of the audio channel with DS3D. Switching must happen in-sync with the playback of each new audio frame and can be implemented through the DS3D notification mechanism. On certain hardware platforms, perfect synchronization cannot be achieved but artefacts can be minimized by enforcing spatial coherence of the audio channels from frame to frame (i.e., making sure a channel is used for clusters whose representatives are as close to each other as possible).

View Example 5 : train-station rendered with GPU pre-mixing View Example 6 : train-station rendered with CPU pre-mixing Another application that requires spatialization of numerous sound sources is the simulation of early reflected or diffracted paths from walls and objects in the scene [START_REF] Funkhouser | Real-time acoustic modeling for distributed virtual environments[END_REF][START_REF] Tsingos | Modeling acoustics in virtual environments using the uniform theory of diffraction[END_REF]. Commonly used techniques, based on geometrical acoustics, use ray or beam tracing to model the indirect contributions as a set of virtual image-sources [START_REF] Borish | Extension of the image model to arbitrary polyhedra[END_REF][START_REF] Tsingos | Modeling acoustics in virtual environments using the uniform theory of diffraction[END_REF]. The number of image-sources grows exponentially with the reflection order, limiting such approaches to a few early reflections or diffractions (i.e., reaching the listener first). Obviously, this number further increases with the number of actual sound sources present in the scene, making this problem a perfect candidate for clustering operations.

Spatial audio bridges

Voice communication, as featured on the Xbox Live! system, adds a new dimension to massively multi-player on-line gaming but is currently limited to monaural audio restitution. Next generation on-line games or chatrooms will require dedicated spatial audio servers to handle real-time spatialized voice communication between a large number of participants. The various techniques discussed in this paper can be implemented on a spatial audio server to dynamically build clustered representations of the soundscape for each participant, adapting the resolution of the process to the processing power of each client, server load and network load. In such applications, an adaptive clustering strategy could be used to drive a multi-resolution binaural cue coding scheme [START_REF] Faller | Binaural Cue Coding Applied to Audio Compression with Flexible Rendering[END_REF], compressing the soundscape and including incoming voice signals as a single or a small collection of monaural audio streams and corresponding time-varying 3D positional information. Rendering of the spatialized audio scene could be done either on the client side (if the client supports 3D audio rendering) or on the server side (e.g., if the client is a mobile device with low processing power).

Conclusions

We presented a set of techniques aimed at spatialized audio rendering of large numbers of sound sources with limited hardware resources. This techniques will hopefully simplify the work of the game audio designer and developer by removing limitations imposed by the audio rendering hardware. We believe these techniques can be used to leverage the capabilities of current audio hardware while enabling novel effects, such as the use of extended sources. They could also drive future research in audio hardware and audio rendering API design to allow for better rendering of complex dynamic soundscapes.

Figure 1 -

 1 Figure 1 -A traditional hardware-accelerated audio rendering pipeline. 3D audio channels process the audio data to reproduce distance, directivity, occlusion, Doppler shift and positional audio effects depending on the 3D location of the source and listener. Additionally, a mix of all signals is generated to feed an artificial reverberation or effect engine.

Figure 2

 2 Figure 2-Clustering techniques group sound sources (blue dots) into groups and use a single representative per cluster (colored dots) to render or spatialize the aggregate audio stream.

Figure 3 -

 3 Figure 3 -An audio rendering pipeline with clustering. Sound sources are grouped into clusters which are processed by the APU as standard 3D audio buffers. Constructing the aggregate audio signal for each cluster must currently be done outside the APU, either using the CPU and/or GPU.

Figure 4 -

 4 Figure 4 -"Virtual surround". A virtual set of speakers (here located at the vertices of an icosahedron surrounding the listener) are used to spatialize any number of sources using 18 3D audio channels.

Figure 5 -

 5 Figure 5 -Fixed grid and adaptive clustering illustration in 2D. (a) regular grid clustering (ten non-empty clusters), (b) non-uniform "azimuth-log(1/distance)" grid (six non-empty clusters), (c) adaptive clustering. Contrary to fixed grid clustering, adaptive clustering can « optimally » fit a predefined cluster budget (four in this case).

Figure 6 -

 6 Figure 6 -A perceptually-driven audio rendering pipeline with clustering. Based on pre-computed information on the input signals, the system dynamically evaluates masking thresholds and perceptual importance criteria for each sound source. Inaudible or masked sources are discarded. Remaining sources are clustered. Perceptual importance is used to select better cluster representatives.

Figure 7 -

 7 Figure 7 -Rendering clusters of sound sources and corresponding energy distribution throught time (echograms). Using a single delay/attenuation for each cluster results in sparse impulse response and combfiltering effects (top echogram). Per source pre-mixing solves this problem (bottom echogram).

Figure 8 -

 8 Figure 8 -Audio signals must be pre-processed in order to be pre-mixed by the GPU. They are split into three frequency bands (low, medium, high), shown as the red, green and blue plots on the lower graph, and stored as one-dimensional RGB texture chunks (one pair for the positive and negative parts of the signal).

Figure 9 -

 9 Figure 9 -Pre-mixing audio signals with the GPU. Signals are rendered as textured line segments. Resampling is achieved through texturing operations and re-equalization through color modulation. Signals for all sources in the cluster are rendered with blending turned on, resulting in the desired mix.

Figure 10 -

 10 Figure 10 -(a) An application of the perceptual rendering pipeline to a complex train-station environment. (b) Each pedestrian acts as two sound sources (voice and footsteps). Each wheel of the train is also modeled as a point sound source to get the proper spatial rendering for this extended source. Overall, 160 sound sources must be rendered (magenta dots). (c) Colored lines represent direct sound paths from the sources to the listener. All lines in red represent perceptually masked sound sources while yellow lines represent audible sources. Note how the train noise masks the conversations and footsteps of the pedestrians. (d) Clusters are dynamically constructed to spatialize the audio. Green spheres indicate representative location of the clusters. Blue boxes are bounding boxes of all sources in each cluster.

The soundtrack of the example movies was generated using binaural processing. Please, use headphones for best spatial sound restitution.

Acknowledgements

The author would like to thank Yannick Bachelart, Frank Quercioli, Paul Tumelaire, Florent Sacré and Jean-Yves Regnault for the visual design, modeling and animations of the train-station environment. Christophe Damiano and Alexandre Olivier-Mangon designed and modeled the various elements of the countryside environment. Some of the voice samples in the train-station example were originally recorded by Paul Kaiser for the artwork "TRACE" by Kaiser and Tsingos. This work was partially funded by the 5 th Framework IST EU project "CREATE" IST-2001-34231.


Alex Reche-Martinez

George Drettakis
email: george.drettakis@sophia.inria.fr

View-Dependent Layered Projective Texture Maps

Capturing and rendering of real scenes in an immersive virtual environment is still a challenging task. We present a novel workflow, using high-quality, view-dependent projective texturing at low texture memory cost, while reinforcing artist's control over image quality. Photographs of a real scene are first used to create a 3D model with standard tools. Our method automatically orders geometry into optimized visibility layers for each photograph. These layers are subsequently used to create standard 2D image-editing layers, enabling artists to fill in missing texture using standard techniques such as clone brushing. The result of this preprocess is used by our novel layered projective texture rendering algorithm, which has low texture memory consumption, high interactive image quality and avoids the need for subdividing geometry for visibility. We show results of our implementation on a real-world project.

Introduction

Recent developments in modeling from images and other real-world capture techniques (e.g., laser scanning, stereobased methods), have resulted in an increasing interest in the creation and display of 3D models in realistic computer graphics and virtual environments. The visual quality of such environments can be very high, thanks to the richness of the textures extracted from high-resolution digital photography and the quality of the reconstructed 3D geometry.

The applications are numerous. Urban planning and environmental impact studies, archaeology and education, training, design but also film production or computer games are just a few cases where these highly-realistic virtual environments can be used.

Modeling-from-images approaches have been largely based on pioneering work in Computer Vision [START_REF] Taylor | Structure and motion from line segments in multiple images[END_REF][START_REF] Faugeras | 3-d reconstruction of urban scenes from image sequences[END_REF]. Image-based modelling and rendering methods have also been developed (e.g., [START_REF] Levoy | Light field rendering[END_REF][START_REF] Gortler | The lumigraph[END_REF]), which are an alternative method to capture and display real world scenes. Debevec et al's [START_REF] Debevec | Modeling and rendering architecture from photographs: A hybrid geometry-and image-based approach[END_REF] Facade approach, and the follow-up interactive version [START_REF] Debevec | Efficient view-dependent image-based rendering with projective texture-mapping[END_REF], use a view-dependent rendering algorithm. The textures used in display are blended from multiple views. In the interactive case, projective textures are used, requiring a geometric visibility pre-process (subdivision of polygons).

In practice, several commercial modeling-from-images products have been since developed and are used for real world projects 1 . All of these products however have adopted standard, rather than projective texture mapping for display: each polygon has an associated texture, which is extracted from the input photographs by applying inverse camera projection. The output can thus be directly viewed with a traditional rendering system. This choice also allows artists to intervene at various stages of the process, using standard image-editing tools (such as Adobe Photoshop T M (http://www.adobe.com), or GIMP (http://www.gimp.org)), to fill in missing textures or remove undesirable objects etc., or standard modeling tools to edit geometry.

In this paper, we adopt a view-dependent display model, by blending textures taken from different input photographs corresponding to different viewpoints, thus achieving high quality. We strive to stay compatible with standard rendering systems typically in the context of a scene-graph based approach. We develop a new projective texture rendering approach, which does not require subdivision of polygons. We automatically generate image-layers, reducing texture memory requirements compared to texture extraction approaches. The image-layers can be used in a standard image-editing workflow, permitting artists to tightly control final image quality.

We have implemented our system, and we show results from a reconstructed 3D model of a real-world project, which is the construction of the Nice Tramway in France.

A longer technical report describing the details and more results of this work can be found at http://www.inria.fr/reves/publications/data/2003/RD03/.

Related Previous Work

In their original paper [START_REF] Debevec | Modeling and rendering architecture from photographs: A hybrid geometry-and image-based approach[END_REF], Debevec et al. presented the first modeling-from-images system Facade. The idea of view-dependent texture mapping (VDTM) was presented, but the rendering approach is clearly off-line and uses model-based stereo to obtain very impressive visual results. This work was transposed to an interactive rendering context [START_REF] Debevec | Efficient view-dependent image-based rendering with projective texture-mapping[END_REF] in which polygons partially visible in one of the input images are subdivided. This method has the advantage of being completely automatic; the flip side of this is the lack of quality control in a traditional content-creation workflow. In particular, for surfaces which do not receive a projective texture, simple color interpolation is used for hole-filling, producing visual errors. Subdivision of input geometry could also be problematic in some contexts, due to numerical imprecision. The method we will present can be seen as an extension of this approach, by addressing these two issues.

Image-based modeling and rendering solutions have been developed since the mid-nineties. The Lightfield [START_REF] Levoy | Light field rendering[END_REF] and Lumigraph [START_REF] Gortler | The lumigraph[END_REF] algorithms are based on relatively dense sampling of images, so that pure (Lightfield) or geometryassisted (Lumigraph) image interpolation suffices to render an image. The size of the data sets required for these approaches (gigabytes of image data), makes them very hard to use for realistic projects.

View-based rendering [START_REF] Pulli | View-based rendering: Visualizing real objects from scanned range and color data[END_REF] or surface light fields [START_REF] Wood | Surface light fields for 3D photography[END_REF] improve the basic methods. The Unstructured Lumigraph [START_REF] Buehler | Unstructured lumigraph rendering[END_REF], can be seen as a compromise between the lumigraph and VDTM. Blending criteria are more sophisticated than VDTM, and the geometric model can be almost arbitrarily coarse. Another IBMR approach are layered depth images (LDI) [START_REF] Shade | Layered depth images[END_REF], which add depth to a multi-layer image, resulting in high-quality renderings. All of these methods require special-purpose rendering algorithms, and in some cases are hard to integrate in a traditional scene-graph like rendering systems. For LDI's the results are dependent on the quality and availability of depth information.

Our algorithm for layer construction is based on a hardware visibility ordering algorithm by Krishnan et al. [START_REF] Krishnan | A Hardware-Assisted Visibility-Ordering algorithm with applications to volume rendering[END_REF]. A more complete, software solution has been presented by Snyder and Lengyel [START_REF] Snyder | Visibility sorting and compositing without splitting for image layer decompositions[END_REF]. Visibility cycles are resolved in the algorithm by Newell et al. [START_REF] Newell | A solution to the hidden surface problem[END_REF]. Our work is also related to the Tour Into the Picture [START_REF] Horry | Tour into the picture[END_REF], where layers are built manually, and a single view is used. The work of Oh et al. [START_REF] Oh | Image-based modeling and photo editing[END_REF], is also related in what concerns the integration of 3D information and image editing.

Overview

We assume that we have constructed a 3D model from images with calibrated cameras (we use REALVIZ Our goal is to achieve projective texture mapping, without the need to subdivide input geometry. In Fig. 1. the scene has three objects, A, B and C and we consider 3 views, cameras c 1 , c 2 and c 3 . When using the previous projective texture mapping algorithm [START_REF] Debevec | Efficient view-dependent image-based rendering with projective texture-mapping[END_REF], even for such a simple scene, objects A and B must be subdivided. For view c 1 , B will be cut into the B 1 , B 2 (see Fig. 1 second row). When moving from c 1 to c 2 , object B 2 will have the image from c 1 as a projective texture, and then will blend the images from c 1 and c 2 . Object B 1 however, will always be displayed with the image of c 2 , since it is invisible from c 1 .

Instead of doing this, we create layered images, or image layers, by first constructing visibility layers. For a given camera or view, a visibility layer is a set of surfaces for which no pair is mutually occluded. In the example of Fig. 1, and for camera c 1 , there are three layers, the first con-taining A and C, the second containing B, which is partially hidden by A and the third the background. We then create an image layer, corresponding to each geometry layer (Fig. 1 third row). The first layer corresponds to the portions of the image from c 1 covered by the pixels corresponding to A and C, and the second image layer corresponds to object B.

We construct geometric visibility layers by adapting the hardware-based algorithm of [START_REF] Krishnan | A Hardware-Assisted Visibility-Ordering algorithm with applications to volume rendering[END_REF], and then create standard image-editing (i.e., Adobe Photoshop T M or GIMP) layers, which will be used as projective textures.

The artist then edits the image layer, e.g., to fill in missing texture (Fig. 1, 3rd row, right). The corresponding compact image layer are used as projective textures for the appropriate polygons of the reconstructed 3D model, avoiding the need for geometry subdivision. This is shown in the last row of Fig. 1. Because the layers and image-editing have resolved visibility the viewer can move around freely.

Creating Visibility and Image Layers

The first step is to create a set of images with calibrated cameras, and a corresponding coarse 3D model of the scene. We use REALVIZ ImageModeler T M for this step. Our goal is to create a set of layers for each input image of the set, which will be subsequently used as projective textures for display. These layers have the following property: for any object in the first layer, no other object in the scene occludes it; for the second layer, once the objects of the first layer have been removed, the same property applies, and so on for each layer. Once these layers have been created, we can use projective texture mapping without the need to subdivide geometry, since we create a separate projective texture map for each layer.

As mentioned previously, we tightly integrate the creation of these layers with a standard image editing program, so that an artist can fill in the missing parts of a given layer use standard techniques such as clone brushing etc.

To create these image layers, we first perform a visibility sort in 3D, to create what we call visibility layers, which are groups of polygons. We then create what we call image layers, which are true image-editing-programme layers, usable in an image-editing programme such as Adobe Photoshop T M or GIMP.

For the first step, we adapt an existing visibility sorting algorithm to create the visibility layers. The second step is achieved by projecting the visibility layers into the image space to create image-editing 2D layers, that are optimized to minimize the amount of texture wasted, and which then creates standard image-editing 2D layers, so that an artist can subsequently edit the result.

Visibility Layers

To compute the visibility layers we adapt the visibility algorithm of [START_REF] Krishnan | A Hardware-Assisted Visibility-Ordering algorithm with applications to volume rendering[END_REF]. Initially, we render the entire scene into an item buffer, i.e., we use a unique identifier for each object in the scene. We then read this buffer to create an initial working set of potentially visible polygons, which thus contains all objects with at least one visible item buffer pixel containing its id.

The algorithm then iteratively constructs a set of visibility layers. For each iteration, the item-buffer of the working set is rendered into the color and the stencil buffer, and the z-test inverted (GL_LESS). For each pixel with a stencil value greater than 1, the object corresponding to the itembuffer value of the pixel is partially hidden, and thus the object is removed from the working set. The working set is then rendered iteratively, until the stencil buffer contains values less than or equal to 1. The remaining objects are inserted into the current visibility layer, and removed from the working set. The current layer is saved, then set to empty, and the iteration continues.

The output of this algorithm is a set of visibility layers. In each visibility layer we have a set of polygons, which are used to build layered images.

In our implementation we have optimized this process hierarchically thanks to the structure of the scene which is provided by the image modelling programme. In particular, the scene provided by ImageModeler T M is organised into objects which contain a set of faces or polygons. Initially, identifiers are given to objects rather than faces, and the algorithm is performed on objects, rapidly eliminating large objects. When we can no longer proceed with objects, we split them into their constituent polygons. In our examples this is enough to resolve the visibility in the scene. Nonetheless, cycles could occur, even at the level of individual polygons/triangles, and in this case we would need to identify the cycles and cut the geometry using an algorithm such as that of Newell et al. [START_REF] Newell | A solution to the hidden surface problem[END_REF].

Creating Image Layers

To create the image layers, we start with the set of visibility layers. For each visibility layer, we project each constituent polygon into image space, resulting in a 2D contour for each. We then perform a simple clustering algorithm for the set of contours. We use the fact that in OpenGL textures have resolution of a power of 2. For a pair of contours c 1 and c 2 we merge c 1 and c 2 into the same layer, if:

A 12 < A 1 + A 2 ,
where A i is the area of the minimal bounding box with resolution in x and y powers of two, with area greater than the area of the bounding box of the projected contour c i . Thus each layer is potentially split into several layers. This results in an increase of the number of layers, but is required to reduce the texture memory requirements of our projective textures. This is because very distant objects can belong to the same visibility layer, which would result in textures with large areas of empty space, wasting texture memory. The final set of layers is then ready for image editing in the appropriate program. These layers consist of a 2D bounding box in image space for the image being treated.

The layers are then sent to the image-editing program (GIMP in our case), which creates a 2D image layer corresponding to the input image.

Once layers have been created in the editing program, an artist can perform standard operations required to fill in missing texture, remove unwanted objects etc.

Display

After creating the visibility layers and manually editing the texture layers for the objects in the scene we use projective texture mapping for display.

For any viewpoint corresponding to the camera of a photograph, all we need to do is to render the geometry, and for each object assign as a texture the corresponding layer. To allow viewing from other viewpoints, we blend between textures with appropriate blending factors [START_REF] Debevec | Efficient view-dependent image-based rendering with projective texture-mapping[END_REF].

Data Structures

As mentioned previously we have designed our approach to fit into a typical scene-graph based rendering system. We use OpenGL Performer T M [7] in our implementation.

For layered projective texture mapping, the graph is modified to contain a sub-image texture node. In addition to the information of a "standard node" with a projective texture material, this node contains the image coordinates of the sub-image (x i , y i , w i , h i ) that will be used to compute the correct texture projection matrix.

To render the layers, we need to apply a sheared perspective transformation. This can be directly implemented using the OpenGL command glFrustum with parameters: where x min , x max , y min and y max are the values of the frustum for the projection of the original image, w and h are width and height of the original image and x i , y i , w i and h i correspond to the position and size of the layer in the original image.

Rendering Multiple Views

To render multiple views, we need to further modify our scene graph structure. We create a view-dependent projec-tive texture node which contains a list of projective texture nodes, associated with each (unique) geometry.

When encountering such a node during graph traversal, the renderer chooses the blending factors for each appropriate texture [START_REF] Debevec | Efficient view-dependent image-based rendering with projective texture-mapping[END_REF], sets up the texture matrix for the nodes with non-zero blending factors, and renders the associated geometry in as many passes are required.

Results

We show an example which is a reconstructed model of Place Massena in Nice, France. This model has been created in the context of a virtual/augmented environment simulation of the Tramway project in Nice.

We use two input views, using input photos of resolution 2160x1440. In Fig. 2, we show intermediate synthetic views using our method. The algorithm creates a total of between 98 and 160 (optimized) layers for each image, many of which are very small and require no editing. The total texture memory required is 10-12 Megabytes, depending on the image. The algorithm to create the layers takes less than 3 minutes to complete on a Pentium IV, 1.2 Ghz. The entire process of editing and cloning the layers took about two days; using a texture extraction-based approach, with the same scene and the same views, required three weeks.

Discussion and Conclusions

Compared to the initial interactive projective texture mapping approach [START_REF] Debevec | Efficient view-dependent image-based rendering with projective texture-mapping[END_REF], we avoid the need to subdivide geometry for visibility, and we introduce more traditional artist intervention to manually fill in missing textures, rather than depending on interpolation. Thus the advantages of our approach are that we do not increase the polygon count of the scene, and that the approach fits well with traditional workflows, where artist's control over image quality is paramount. The disadvantage is that hole-filling is no longer automatic.

Compared to texture-extraction methods, our approach significantly reduces texture memory requirements and results in better texture quality, since inverse perspective results in large textures and quality loss due to resampling. Informal observation of our system in use has shown that users are less sensitive to parallax errors due to the high quality of the projective textures.

In future work, we will be automating many aspects of the capture and texture editing phases and we plan to integrate this method in a VR setup.

Figure 1 .

 1 Figure 1. Row 1 left: The geometric configuration of the scenes and the cameras. Row 1 right: The input image corresponding to c 1 . Row 2: the corresponding 3D geometry. Row 3 left: Resulting image-layers after geometry sorting. Row 3 right: Image-layers after editing (clone brushing, etc.). Row 4: Visualisation of the layers.

  x min = x min + xi(xmax-xmin) w x max = x min + (xi+wi)(xmax-xmin) w y min = y min + yi(ymax-ymin) h y max = y min + (yi+hi)(ymax-ymin) h

Figure 2 .

 2 Figure 2. Top row: two intermediate (non-input) views, using our new, layered projective texture display. Lower row (right): Closeup of input image; (left) closeup of rendering of our system from a different viewpoint. The quality of the texture in the synthetic view is comparable to the input image.

E.g., www.realviz.com, www.canoma.com, www.photomodeler.com.

Acknowledgements

This research was partially funded by the EU IST project CREATE, IST-2001-34231, http://www.cs.ucl.ac.uk/create. Im-


Alex Reche-Martinez

George Drettakis
email: george.drettakis@sophia.inria.fr

Textures projectives à calques dépendantes du point de vue

La capture et le rendu des scènes réelles dans le contexte des environnements virtuels immersifs sont encore des tâches très difficiles. Nous présentons une nouvelle approche, en utilisant des textures projectives dépendantes du point de vue, de haute qualité et avec un faible coût en mémoire texture. Dans un premier temps, des photographies de la scène réelle sont utilisées pour créer un modèle 3D avec des outils standards. Notre méthode ordonne automatiquement la géométrie en groupes à niveaux de visibilité différents pour chaque point de vue. Ces groupes sont ensuite utilisés pour découper les images en calques, permettant aux artistes le remplissage des textures manquantes, dues à leur non-visibilité, en utilisant des outils comme le tampon de duplication (clone brush). Le résultat de ce processus est utilisé par notre nouvel algorithme de rendu en utilisant des textures projectives à calques, ayant un faible coût d'utilisation de mémoire texture, une haute qualité de rendu et dans le cas de textures projectives dépendantes du point de vue, évite la subdivision de la géométrie engendrée par la visibilité en utilisant des méthodes antérieures.

Introduction

Les développements récents en modélisation à partir d'images et d'autres techniques de capture comme le scanner laser ou les méthodes stéréo, ont eu comme conséquence un intérêt croissant pour la création et l'affichage des modèles 3D dans le domaine du rendu réaliste et les environnements virtuels. La qualité visuelle de tels environnements peut être très bonne, grâce à la richesse des textures extraites à partir de la photographie numérique de haute résolution et la qualité de la géométrie 3D reconstruite.

Les applications de ces méthodes sont nombreuses. Les études de planification urbaine et les études d'impact sur l'environnement, l'archéologie et l'éducation, la formation, la conception, mais aussi la production de films ou les jeux vidéo sont juste à peine quelques cas pour lesquels ces environnements virtuels hautement réalistes peuvent être employés.

Les approches de modélisation à base d'images ont été en grande partie basées sur les travaux pionniers dans la vision par ordinateur [TK95, F + 97]. Des méthodes de modélisation et de rendu à base d'Images (MRBI) ont été également développées par [LH96, G + 96]. Ces approches représentent une alternative pour capturer et afficher de scènes réelles. L'approche de Facade de Debevec et ses collaborateurs [D + 96], et sa version interactive [D + 98], emploient un algorithme de rendu dépendant du point de vue. Les textures utilisées pour l'affichage sont le résultat du mélange de multiples vues. Dans le cas interactif, ils emploient des textures projectives, nécessitant un prétraitement de visibilité géométrique, c'est à dire la subdivision des polygones d'entrée.

Dans la pratique, plusieurs produits commerciaux de modélisation à base d'images ont été développés et sont employés au sein de véritables projets 1 . Cependant tous ces produits ont adopté la méthode standard de texturation pour l'affichage, plutôt que les textures projectives : chaque polygone a une texture associée, qui est extraite à partir des photographies d'entrée en appliquant la projection inverse. Le résultat peut être ainsi directement visualisé avec un système de rendu traditionnel. Ce choix permet également à des artistes d'intervenir à divers moments du processus, à l'aide d'outils standard d'édition d'image (tels qu'Adobe Photoshop T M (http://www.adobe.com), ou GIMP (http://www.gimp.org), afin de remplir les textures manquantes ou pour enlever les objets indésirables, etc., ou à l'aide d'outils de modélisation standard pour éditer la géométrie.

Dans cet article, nous adoptons un modèle d'affichage dépendant du point de vue. Nous développons une nouvelle approche de rendu à base de textures projectives, qui ne nécessite exige pas la subdivision des polygones. Nous 1. E.g., www.realviz.com, www.canoma.com, www.photomodeler.com. générons automatiquement des calques d'image, qui réduisent la quantité de mémoire texture utilisée, comparée aux approches d'extraction de texture. Les calques d'image peuvent être employés dans un programme d'édition d'image standard (comme PhotoShop), permettant aux artistes de contrôler la qualité finale du rendu.

Nous avons implémenté notre système, et nous montrons des résultats d'un modèle 3D utilisé dans un projet réel, qui est la construction du tramway de Nice. Un rapport technique décrivant les détails et plus de résultats de ce travail se trouvent sur http://www.inria.fr/reves/publications/data/2003/RD03/.

Travaux Précédents

Dans leur papier original, Debevec et ses collaborateurs [D + 96] ont présenté le système Facade, qui est le premier logiciel de modélisation à base d'images. Dans cet article ils présentent les textures projectives dépendantes du point de vue (TPDV). Ce travail a été transposé dans un contexte de rendu interactif [D + 98] au sein duquel les polygones partiellement visibles dans une des images d'entrée sont subdivisés. Cette méthode a l'avantage d'être complètement automatique ; par contre, il y manque le contrôle de qualité nécessaire pour la création de contenu. En particulier, pour les surfaces qui ne reçoivent pas une texture projective, l'interpolation simple de couleur est employée pour remplir les trous, produisant des erreurs visibles. La subdivision de la géométrie d'entrée est également problématique selon le contexte, à cause des imprécisions numériques. La méthode que nous présentons ici peut être vue comme une extension de cette approche, en abordant ces deux questions, le remplissage des trous et la subdivision de la géométrie. D'autres méthodes de modélisation et rendu à base d'images ont été développées depuis les années 90. Les algorithmes de Lightfield [START_REF] Levoy | Light field rendering[END_REF] et de Lumigraph [G + 96] sont basés sur la capture relativement dense d'images, de sorte que l'interpolation d'images pure (Lightfield) ou aidée par la géométrie (Lumigraph) suffit pour rendre une image. La taille des données nécessaire pour ces approches (gigaoctets de données d'image) les rend très difficiles à employer dans des projets réels.

Le rendu dépendant du point de vue [P + 97] ou les "surface light fields" [W + 00] améliorent les méthodes de base. L'"Unstructured Lumigraph" [B + 01] peut être vu comme un compromis entre le Lumigraph et le TPDV. Le critère utilisé pour le mélange de textures est plus sophistiqué que dans TPDV, et le modèle géométrique utilisé peut être très approximatif. Une autre approche de l'MRBI utilise les calques d'images avec profondeur (Layered Depth Images, LDI) [S + 98], qui ajoutent la profondeur à une image multicalque. Toutes ces méthodes nécessitent des algorithmes de rendus spécifiques. Dans certains cas ces méthodes sont difficiles à intégrer dans un système traditionnel. Pour les LDI, les résultats dépendent de la qualité et de la disponibilité de l'information de profondeur.

Notre algorithme pour la construction des calques est basé sur un algorithme de tri de la géométrie par visibilité développé par Krishnan et collaborateurs [K + 01]. Une solution plus complète a été présentée par Snyder et Lengyel [START_REF] Snyder | Visibility sorting and compositing without splitting for image layer decompositions[END_REF]. Les cycles de visibilité sont résolus dans l'algorithme développé par Newell et autres [N + 72]. Notre travail est également lié à "Tour Into de Picture" [H + 97], où une seule vue est employée en établissant des calques manuellement. Le travail de Oh et collaborateurs [O + 01], est également lié à notre recherche en ce qui concerne l'utilisation de la 3D pour l'édition d'images.

Vue d'ensemble

Nous supposons que nous avons construit un modèle 3D à partir d'images avec des appareils photo calibrés (nous utilisons REALVIZ ImageModeler T M dans nos exemples pour la calibration et la modélisation à partir d'images). Au lieu de faire ceci, nous subdivisons l'image en calques, issus du tri de la géométrie en calques de visibilité. Pour un point de vue donné, un calque de visibilité est un ensemble de surfaces pour lesquelles aucune paire n'est Nous construisons des calques géométriques de visibilité en adaptant l'algorithme de [K + 01], puis nous créons des calques d'image standard (Adobe Photoshop T M ou GIMP), qui seront employés en tant que textures projectives.

L'artiste édite alors le calque d'image, afin de, par exemple, remplir les morceaux de texture manquants (par exemple fig. 1, 3ème ligne, droite). Les calques des images sont employés en tant que textures projectives pour les polygones du modèle 3D correspondants, évitant ainsi le besoin de subdivision de la géométrie (ceci est montré dans la dernière ligne de la fig. 1) puisque les calques et l'édition d'images ont résolu correctement la visibilité.

Création des calques de visibilité et d'image

La première étape est d'estimer l'ensemble de paramètres intrinsèques et extrinsèques des appareils photo correspondants aux images, et créer un modèle 3D approximatif de la scène. Nous utilisons REALVIZ ImageModeler T M pour cette étape. Notre but est de créer un ensemble de calques pour chaque image d'entrée de l'ensemble, qui sera plus tard employé en tant que textures projectives pour l'affichage. Ces calques ont la propriété suivante : pour n'importe quel objet dans le premier calque, aucun autre objet de la scène ne le cache ; pour les objets du deuxième calque, une fois les objets du premier calque enlevés, la même propriété s'applique, et ainsi de suite pour les calque suivants. Une fois que tous les calques ont été créés, nous pouvons utiliser des textures projectives sans avoir besoin de subdiviser la géométrie, puisque nous avons une texture projective séparée pour chaque calque.

Comme nous l'avons mentionné précédemment, nous intégrons la création de ces calques dans un programme d'édition d'image standard, de sorte qu'un artiste puisse compléter les parties absentes d'un calque donné, en utilisant des techniques standard telles que le tampon de duplication (clone brush), et autres outils d'édition.

Pour créer ces calques d'image, nous trions d'abord la géométrie par ordre de visibilité, pour créer ce que nous appelons les calques de visibilité, qui sont des groupes d'objets ou polygones. Nous créons ensuite ce que nous appelons les calques d'image, qui sont des calques utilisables dans un programme d'édition d'image tel qu'Adobe Photoshop T M ou GIMP.

Pour la première étape, nous adaptons un algorithme de tri par visibilité existant afin de créer les calques de visibilité. La deuxième étape est réalisée en projetant les calques de visibilité dans l'espace image pour créer des calques 2D éditables, optimisés pour réduire la quantité de texture utilisée.

Calques de visibilité

Pour calculer les calques de visibilité nous adaptons l'algorithme de tri par visibilité de [K + 01]. Au début, nous rendons la scène entière dans un Item Buffer, c'est-à-dire, nous donnons un identificateur unique pour chaque objet de la scène. Nous récupérons ensuite cette information pour créer un premier ensemble de polygones potentiellement complètement visibles, contenant ainsi tous les objets avec au moins un pixel dans l'Item Buffer contenant son identificateur. L'algorithme construit itérativement un ensemble de calques de visibilité. Pour chaque itération, l'ensemble d'objets non-classés, qui au début de chaque itération est aussi l'ensemble de candidats pour le calque, est rendu dans l'Item Buffer et le Stencil Buffer avec le test de profondeur inversé (GL_LESS). Pour chaque pixel ayant une valeur supérieure à 1 dans Stencil Buffer, l'objet correspondant au même pixel dans l'Item Buffer est partiellement caché, puisque le test de profondeur est inversé et ce qu'on voit dans les buffers est l'arrière de la scène. L'objet est ensuite enlevé de l'ensemble de candidats pour le calque considéré. L'ensemble de candidats pour le calque est alors rendu itérativement, jusqu'à ce que le Stencil Buffer ne contienne que des valeurs inférieures ou égales à 1. Ces objets sont les objets complètement visibles pour le calque courant. Un dernier test est fait sur ces objets pour résoudre un défaut de l'algorithme de Krishnan [K + 01]. Dans le cas 2D montré dans la Fig. 2 l'algorithme va classer comme objets du premier calque les objets A et C, par contre nous voyons clairement que seul l'objet A est complètement visible. Le test ajouté pour résoudre ce problème consiste simplement en une comparaison entre le premier et dernier rendu de l'itération courante. Tout objet qui apparaît partiellement visible au premier rendu ne peut être considéré comme complètement visible, il est donc éliminé de l'ensemble de candidats pour le calque.

Les objets restants sont insérés dans le calque de visibilité courant. L'ensemble d'objets n'ayant pas encore été classés est utilisé comme ensemble de candidats pour le prochain calque. Le résultat de cet algorithme est un ensemble de calques de visibilité. Dans chaque calque de visibilité, nous avons un ensemble d'objets ou polygones, qui sont ensuite utilisés pour construire les calques d'images.

Dans notre implémentation nous avons optimisé hiérarchiquement le processus grâce à la structure de scène fournie par le programme de modélisation à base d'images utilisé. En particulier, la scène fournie par ImageModeler T M est organisée en objets qui contiennent un ensemble de polygones. Au début, les identificateurs sont donnés aux objets plutôt qu'aux polygones, et l'algorithme est exécuté sur des objets, éliminant rapidement de grands objets. Lorsque nous ne pouvons plus continuer le tri des objets, nous remplaçons les objets par leurs polygones constitutifs. Dans nos exemples, cette démarche est suffisante pour résoudre la visibilité dans la scène. Néanmoins, des cycles pourraient se produire, même au niveau de polygones/triangles (par exemple si deux triangles se coupent), et dans ce cas nous devrions identifier les cycles et découper la géométrie en utilisant un algorithme comme celui de Newell et collaborateurs [N + 72].

Création des calques d'image

Pour créer les calques d'image, nous utilisons l'ensemble de calques de visibilité. Pour chaque calque de visibilité, nous projetons chaque polygone de l'ensemble dans l'espace image, ce qui résulte en un découpage 2D pour chacun. Par contre, étant donné que les objets de chaque calque peuvent être n'importe où dans l'image et que souvent ils sont très séparés, nous sommes obligés d'optimiser le résultat en utilisant un algorithme de clustering. L'algorithme que nous utilisons est très simple. Nous prenons avantage du fait que les textures d'OpenGL soient forcement à résolution puissance de 2 (sauf avec des nouvelles extensions qui ne sont pas disponibles sut toutes les cartes). Pour une paire c 1 et c 2 d'objets projetés nous fusionnons c 1 avec c 2 dans le même calque, si : A 12 < A 1 +A 2 , où A i est l'aire de la boîte englobante de la projection avec côtés

x i = min n (2 n ) > x i et y i = min n (2 n ) > y i où x i et y i sont

Structure de données

Nous avons conçu l'algorithme afin de nous adapter à un système de rendu par scène-graphe. Nous utilisons OpenGL Performer T M [htt] dans notre implementation.

Pour utiliser les textures projectives par calques, nous avons modifié le graphe pour contenir un noeud de texture avec les informations du calque. En plus de l'information d'un noeud de texture standard, ce noeud contient les coordonnées de la sous-image correspondant au calque (x i ,y i ,w i ,h i ) qui sera employé pour calculer la matrice de projection de texture.

Pour rendre les calques, nous devons appliquer une transformation perspective asymétrique. Ceci peut être directement mis en application en utilisant la commande glFrustum d'OpenGL avec les paramètres suivants :

x min = x min + xi(xmax-

Rendu avec multiples textures

Conclusions

Comparé à la méthode interactive des textures projectives dépendantes du point de vue [D + 98], nous évitons la subdivision de la géométrie pour la visibilité, et nous permettons l'interaction de l'artiste pour l'édition des textures manquantes, plutôt qu'utiliser l'interpolation. Les avantages de notre approche sont que nous n'augmentons pas le nombre de polygones de la scène, et que l'approche s'adapte bien au habitudes de travail des artistes, où le contrôle de la qualité d'image est primordial. L'inconvénient est que le remplissage des textures manquantes n'est plus automatique.

Comparé aux méthodes d'extraction de textures classique, notre approche réduit de manière significative l'utilisation de mémoire texture avec des résultats d'une meilleure qualité visuelle, car la projection inverse génère souvent de grandes textures et a pour conséquence une perte de qualité par le re-échantillonnage. L'utilisation de notre système indique que les utilisateurs sont moins sensibles aux erreurs de parallaxe grâce à la qualité élevée des textures projectives.

Pour nos travaux futurs, nous automatiserons beaucoup d'aspects de la capture et de l'édition des textures et nous intégrerons cette méthode dans notre configuration de réalité virtuelle.

  Notre but est d'utiliser des textures projectives, tout en évitant de subdiviser la géométrie d'entrée. Dans la fig. 1 la scène comporte trois objets, A, B et C. Nous considérons 3 vues différentes, c 1 ,c 2 et c 3 . En utilisant la méthode de textures projectives dépendantes du point de vue [D + 98], même dans une scène si simple, les objets A et B doivent être subdivisés. Pour la vue c 1 , B sera coupé en B 1 , B 2 (voir la fig. 1 deuxième ligne). En se déplaçant de c 1 vers c 2 , l'objet B 2 aura l'image de c 1 comme texture projective, et puis mélangera les images de c 1 et c 2 . Par contre, l'objet B 1 sera toujours montré avec la texture projective correspondante à l'image de c 2 , puisqu'il est invisible depuis c 1 .

FIG. 1 -

 1 FIG. 1 -Ligne 1 gauche : Configuration géométrique de la scène et des points de vue de d'entrée. Ligne 1 droite : L'image d'entrée correspondant à c 1 . Rangée 2. : la géométrie 3D correspondante. Ligne 3 gauche : Calques d'image résultat après le tri de la géométrie. Rangée 3 droite : Calques d'image après l'édition (tampon de duplication, etc.). Rangée 4 : Visualisation des calques.

  FIG.2-Illustration de l'algorithme de tri de visibilité.

FIG. 3 -

 3 FIG. 3 -Première ligne : deux nouvelles vues synthétisées, en utilisant notre nouvel affichage avec des textures projectives à calques. Deuxième ligne (droite) : Vue rapprochée d'une image d'entrée ; (gauche) Vue rapprochée dans notre système d'un point de vue différent. La qualité de la texture dans la vue synthétique est comparable à l'image d'entrée.

  les côtés de la vraie boîte englobante de la projection. Ainsi, chaque calque est potentiellement séparé en plusieurs calques. Ceci a comme conséquence une augmentation du nombre de calques, mais ceci est nécessaire pour réduire l'utilisation de mémoire texture. L'ensemble final de calques est alors prêt pour l'édition.Les calques sont envoyés vers le programme d'édition d'image (dans notre cas GIMP) qui va convertir l'ensemble de calques en une image composée qui est visuellement identique à l'image originale. L'artiste peut alors éditer en utilisant tous les outils d'édition disponibles pour remplir toutes les textures manquantes, effacer les objets non désirés, etc.Après avoir créé les calques de visibilité et avoir manuellement édité les calques d'image, nous employons des textures projectives pour l'affichage. Pour tous les points de vue qui correspondent aux points de vue d'entrée tout ce que nous devons faire est rendre la géométrie et pour chaque objet assigner comme texture le calque image correspondant. Pour permettre l'affichage d'autres points de vue, nous mélangeons les textures avec les facteurs de blending appropriés [D + 98].

  où x min , x max , y min et y max sont les valeurs du frustum pour la projection de l'image originale, w et h sont la largeur et la taille de l'image originale et x i , y i , w i et h i correspondent à la position et à la taille du calque dans l'image originale.

		w	xmin)	x max = x min +	(xi+wi)(xmax-xmin) w
	y min = y min +	yi(ymax-ymin) h	y max = y min +	(yi+hi)(ymax-ymin) h

  Pour rendre d'autres points de vue que ceux qui correspondent aux point de vue d'origine, nous utilisons un mélange de plusieurs textures, avec une approche similaire à cellede Debevec [D + 98]. Pour atteindre ce but nous devons modifier notre structure de graphe. Nous créons un noeud dépendant du point de vue qui contient une liste de noeuds de texture projectifs et chacun d'entre eux lié au noeud géométrie unique.Quand la procédure d'affichage parcourt ce noeud, des facteurs de blending sont choisis pour chaque texture correspondante [D + 98]. Ensuite, chaque noeud de texture projectif met à jour la matrice de projection pour sa texture et le facteur de blending que le noeud père a calculé, puis le noeud géométrie associé s'affiche autant de fois que nécessaire, tant que les facteurs de blending sont supérieurs à 0.

	6 Résultats
	Nous montrons comme exemple un modèle reconstruit de la place Massena à Nice. Ce modèle a été créé dans le
	contexte d'une simulation de réalité virtuelle/augmentée du projet de tramway à Nice.
	Nous utilisons deux photos d'entrée à d'une résolution de 2160x1440. Dans la fig. 3, nous montrons des vues

synthétiques intermédiaires en utilisant notre méthode. L'algorithme crée un total d'entre 98 et 160 calques (optimisées) pour chaque image, dont beaucoup sont très petites et n'ont pas besoin d'édition. La mémoire texture nécessaire est de 10-12 méga-octets selon l'image. L'algorithme pour créer les calques prend moins de 3 minutes sur un Pentium IV cadencé à 1,2 Gigahertz. Le processus entier d'édition des calques a pris environ deux jours pour notre artiste. Le même processus en utilisant l'approche d'extraction de textures par objet, avec la même scène et les mêmes vues a pris trois semaines.

Remerciements

Cette recherche a été partiellement effectuée dans le cadre du projet de l'UE IST CREATE, IST-2001-34231, http://www.cs.ucl.ac.uk/create. ImageModeler a été fourni par REALVIZ dans le contexte de CREATE. Merci à A. Olivier-Mangon pour ses idées et pour son aide avec ImageModeler, à F. Durand pour ses commentaires et à M-C. Frasson pour sa relecture et correction de la version française.