Ben Hachmi

Chokri Dhia

Zammali

Hachmi Ben Dhia

Chokri Zammali

LEVEL-SETS AND MIXED APPROACHES FOR DYNAMIC CONTACT PROBLEMS

The Signorini-Moreau contact conditions are set as equations by using unknown Level-Set fields. From this, a mixed weakstrong formulation of dynamic contact problems is derived; the Level-Set fields being the intrinsic contact unknown fields. The problem is then discretized by time, space and collocation schemes and some numerical experimentations are carried out, showing the effectiveness of our global approach. The paper is ended with a prospective use of the local multiscale Arlequin method [1].

INTRODUCTION

Impact problems are nonlinear in essence, but also irregular and multiscales in space and time. Theses evidences are shown by analytical investigations giving explicit solutions of simple model impact problems (see e.g. Gloldsmith [START_REF] Goldsmith | Impact problems[END_REF]). General industrial impact problems have however to be approximated by means of numerical tools. Hughes et al. [START_REF] Hughes | A finite element method for a class of contact-impact problems[END_REF], have designed special numerical schemes since the late seventies and increasing efforts have been since furnished by the computational contact community to address this numerical issue (see e.g. [START_REF] Love | Improved implicit integrators for transient impact problems[END_REF] and the sampling references therein). Very important advances have this way been done and some of the most pertinent schemes are now capitalized in commercial codes. But to our best knowledge and due to the aforementioned intrinsic difficulties of the impact problems (strong nonlinearities and both space and time irregularities and multiscale intrinsic characters), none of the available numerical schemes is yet sufficiently robust, efficient and accurate to address for instance dynamic contact problems such as those involved by vibrating structures under impact. The present work is a contribution to this wide and complex theme. Using the "viability lemma" of J.J. Moreau [START_REF] Moreau | Unilateral Problems in Structural Analysis[END_REF], the unilateral contact laws are written in a first part as equations by using two unknown possibly multivoque Level-Set type fields standing for i) a location of the position of contact surfaces with respect to each other and ii) the Signe of the normal velocity jump on the interface. A weak-strong formulation of dynamic unilateral contact conditions is then derived in a straightforward manner. In a second part, an original continuous weak-strong mixed formulation of a dynamic 3-D contact problem is carried out. The associated discrete nonlinear systems are then derived by using a θ-scheme time discretization, a Galerkin method and a collocation one. The numerical solution strategy used to solve this problem is briefly commented and numerical tests are carried out in a third part. It is particularly shown that the numerical solutions do not exhibit pathologies (due to shocks) such as spurious oscillations of the numerical mechanical fields. The paper is ended with a prospective use of the local multiscale Arlequin method [START_REF] Dhia | Problèmes mécaniques multi-échelles: La méthode Arlequin[END_REF] to superpose to the global (coarse) model local refined ones just in the neighbourhood of impacted zones in order to save human and machine resources. First promising numerical results exemplifying this approach are given.

A DYNAMIC CONTACT MODEL

Let us consider two solids (elastic, for simplicity) which may come into (frictionless, for clarity) contact/impact during their evolution. The classical Signorini contact laws can then be set as flollowing (with rather classical notations) :

d n ≤ 0, λ ≤ 0 and λ d n = 0, on I c × Γ (1)
where , c Γ I ,d n and λ are the potential "slave" contact surface, the time interval, the so-called signed distance and the normal contact pression, respectively. By using the "viability lemma" of J.J. Moreau [START_REF] Moreau | Unilateral Problems in Structural Analysis[END_REF], and by assuming that at the initial time, the conditions (1) are satisfied, these conditions can then be written in an equivalent manner in terms of placements and velocities as follows.

If d n < 0 then a free boundary condition is imposed

[[v n ]] ≤ 0, λ v ≤ 0 and λ v [[v n ]] = 0, otherwise, with [[v n ]
] standing for the normal velocities-jump By using the Signe function introduced in [START_REF] Dhia | Modelling and solution by penalty duality method of unilateral contact problems[END_REF], these Signorini-Moreau inequalities can be transformed to equalities:

( ) ]] [[ n v v d v v h - = λ λ S S
, on

I c × Γ (2) ( ) n d d - = - IR 1 S , ( ) ]] [[ 1 IR n v v v ρ λ - = - S , on I c × Γ (3) with h , 0 ≠ 0 > ρ
and 1 the characteristic function of the semi-negative axis.

-

IR

This new setting of Signorini-Moreau contact conditions is interesting from a numerical point of view since it leads itself "naturally" to a weak formulation, well-suited to numerical approximations.

WEAK-STRONG FORMULATIONS OF THE DYNAMIC CONTACT PROBLEM

By using the Virtual Power Principle VPP (in which a behaviour law is used to express the First Piola-Khirchhoff stress ) and a weak formulation of equation ( 2), keeping equations (3) as local strong ones, the following (original, to our knowledge) weak-strong mixed formulation of the dynamic contact problem is obtained: Find (u i , v i , λ v , S d , S v ) such as for all admissible w i and * λ and for t in

I, 0 ]] [[ ) ( : . 2 1 2 1 0 0 0 = Γ - Ω ∇ + Ω ∫ ∑ ∫ ∑ ∫ Γ = Ω = Ω c i i d w d d n v v d i i i i i i i λ ρ S S w Π w v & τ τ d t t t t i i i ∫ + = 0 ) ( ) ( ) ( 0 v u u ( ) n d d - = - IR 1 S , ( ) ]] [[ 1 IR n v v v ρ λ - = - S on Γ c (4) ( ) [ ] 0 ]] [[ 1 * = Γ - - -∫ Γ c d v h h n v v d v λ λ λ S S
where u i , v i stand for the displacement and velocity fields.

We notice that since the velocity fields may be locally discontinuous with respect to time, the time derivative in the VPP is to be understood in an appropriate sense. We notice also that although the above formulation may recall available lagrangian formulations of frictionless contact problems, it is original to our best knowledge: it is a non augmented, non constrained lagrangian formulation of dynamic contact problems. To be solved, this problem is discretized by means of three numerical tools. A low-order finite time difference scheme of Euler type is used to approximate partial time derivatives. A Galerkin space discretisation method (of the finite element type, or spectral one) is used to approximate the continuous fields u i , v i and λ v , while respecting the compatibility condition (see [START_REF] Dhia | Hybrid frictional contact particles-in elements[END_REF], in the quasistatic case). The Level-Set like fields S d , S v are approximated by means of a collocation method, related intimately in practice to numerical contact integration points. The nonlinear discrete systems will be detailed during the conference.

NUMERICAL SOLUTION STRATEGY AND RESULTS

Our non linear systems are solved, at each time step, by a fixed point strategy on the Level-Set fields S d and S v (actually on their values on the selected finite collocation contact points, for the discrete systems), coupled with classical numerical methods for the solution of the others nonlinearities of the problem. Let us now give a numerical illustration. We consider the very well-known shock of two bars of identical mechanical characteristics and represent the interface mechanical fields obtained by using: i) the Signorini contact conditions (1) and a Newmark scheme, with numerical damping and ii) the suggested approach (figure 1). Other results showing the effectiveness of our global approach of dynamic contact problems, (taking also into account friction phenomena), will be given during the conference.

A PROSPECTIVE USE OF THE ARLEQUIN FRAMEWORK

Our work is ended by showing the use of the local multiscale Arlequin method [START_REF] Dhia | Problèmes mécaniques multi-échelles: La méthode Arlequin[END_REF] to introduce, with great flexibility while saving machine resources, a mechanical and numerical refinement of impact problems in critical zones. The Taylor bar test, treated in the Arlequin framework by superposing a local elastoplastic refined model to a global elastic one, is shown in figure 2.

  15-21 August 2004, Warsaw, Poland

  Figure 2

Figure1

  Figure1


Emmanuel Gallo

Nicolas Tsingos

Extracting and Re-rendering Structured Auditory Scenes from Field Recordings

We present an approach to automatically extract and re-render a structured auditory scene from field recordings obtained with a small set of microphones, freely positioned in the environment. From the recordings and the calibrated position of the microphones, the 3D location of various auditory events can be estimated together with their corresponding content. This structured description is reproduction-setup independent. We propose solutions to classify foreground, well-localized sounds and more diffuse background ambiance and adapt our rendering strategy accordingly. Warping the original recordings during playback allows for simulating smooth changes in the listening point or position of sources. Comparisons to reference binaural and B-format recordings show that our approach achieves good spatial rendering while remaining independent of the reproduction setup and offering extended authoring capabilities.

INTRODUCTION

Current models for interactive 3D audio scene authoring often assume that sounds are emitted by a set of monophonic point sources for which a signal has to be individually generated [START_REF] Savioja | Creating interactive virtual acoustic environments[END_REF][START_REF] Begault | 3D Sound For Virtual Reality and Multimedia[END_REF]. In the general case, source signals cannot be completely synthesized from physics principles and must be individually recorded, which requires enormous time and resources. Although this approach gives the user the freedom to control each source and freely navigate throughout the auditory scene, the overall result remains an approximation. This is due to the complexity of real-world sources, limitations of microphone pick-up patterns and limitations of the simulated sound propagation models. On the opposite end of the spectrum, spatial sound recording techniques which encode directional components of the soundfield [START_REF]SOUNDFIELD[END_REF][START_REF] Streicher | The decca tree -it's not just for stereo anymore[END_REF][START_REF] Merimaa | Applications of a 3D microphone array[END_REF][START_REF] Meyer | Spherical microphone arrays for 3D sound recording, chap. 2 in Audio Signal Processing for next-generation multimedia communication systems[END_REF] can be directly used to acquire and playback real-world auditory environments as a whole. They produce realistic results but offer little control, if any, at the playback end. In particular, they are acquired from a single location in space and only encode directional information, which makes them insufficient for free-walkthrough ap-plications or rendering of large near-field sources. In such spatially-extended cases, correct reproduction requires sampling the soundfield at several locations and encoding the 3D position and not only the incoming direction of the sounds. In practice, the use of such singlepoint recordings is mostly limited to the rendering of an overall surround ambiance that can possibly be rotated around the listener.

We previously developed a novel analysis-synthesis approach which bridges the two previous strategies [START_REF] Gallo | 3D-Audio matting, post-editing and re-rendering from field recordings[END_REF]. Inspired by spatial audio coding [START_REF] Faller | Binaural cue codingpart II: Schemes and applications[END_REF][START_REF] Baumgarte | Binaural cue coding -part I: Psychoacoustic fundamentals and design principles[END_REF][START_REF] Breebaart | MPEG spatial audio coding/MPEG surround: Overview and current status[END_REF][START_REF] Pulkki | Directional audio coding: Filterbank and stft-based design[END_REF][START_REF] Goodwin | Analysis and synthesis for universal spatial audio coding[END_REF] and blind source separation [START_REF] Yilmaz | Blind separation of speech mixtures via time-frequency masking[END_REF][START_REF] Vincent | A tentative typologie of audio source separation tasks[END_REF][START_REF] Radke | Audio interpolation[END_REF], our method builds a higher-level spatial description of the auditory scene from a small set of monophonic recordings. Contrary to previous spatial audio coding work, the recordings are made from widely-spaced locations and sample both content and spatial information for the sound sources present in the scene. Our approach is also mostly dedicated to live recordings since it reconstructs estimates of the 3D locations of the sound sources from physical propagation delays. This information might not be available in studio recordings which rely on non-physical panning strategies. The obtained description can then be used for real-time post-processing and re-rendering of the original recordings, for instance by smoothly varying the listening point inside the environment and editing/moving sound sources. We briefly review key aspects of this approach but refer the reader to [START_REF] Gallo | 3D-Audio matting, post-editing and re-rendering from field recordings[END_REF] for additional details.

We first acquire real-world soundscapes using a small number (e.g., 8) of omnidirectional microphones arbitrarily positioned in the environment. In order to extract correct spatial information from the recordings, it is necessary to retrieve the 3D locations of the microphones. We use an image-based technique from photographs [START_REF] Faugeras | Three-dimensional computer vision: a geometric viewpoint[END_REF] which ensures fast and convenient acquisition on location, not requiring any physical measurements or homing device.

The obtained sparse sampling of the soundfield is analyzed in an off-line pre-processing step in order to segment various auditory components and associate them with the position in space from which they were emitted (Figures 1 and2). To compute this spatial mapping, we split the signal into short time-frames and decompose them onto a set of frequency subbands defined on a Bark scale [START_REF] Traunmüller | Analytical expressions for the tonotopic sensory scale[END_REF] or, alternatively, using a gammatone filter bank [START_REF] Patterson | Auditory filters and excitation patterns as representations of auditory frequency selectivity[END_REF]. Assuming that the sound sources do not overlap in time-frequency domain (W-disjoint orthogonality hypothesis [START_REF] Yilmaz | Blind separation of speech mixtures via time-frequency masking[END_REF]), we then use classical time-difference of arrival techniques (e.g., [START_REF] Knapp | The generalized correlation method for estimation of time delay[END_REF][START_REF] Chen | Time delay estimation in room acoustic environments: An overview[END_REF]) between all pairs of microphones to retrieve a position for each subband at each time-frame. We developed an improved hierarchical source localization technique from the obtained timedifferences, using a quadtree or octree decomposition of space [START_REF] Samet | The Design and Analysis of Spatial Data Structures[END_REF].

Real-time re-rendering is achieved through a frequencydependent warping of the original recordings, based on the estimated positions of each frequency subband. This warping assumes an omnidirectional, anechoic, point source model. For instance, for any desired virtual listener position we first determine the closest microphone and use its signal as a reference. We then warp this reference signal by resampling and equalizing its different subbands. This warping first compensates the original propagation delay and attenuation from each calculated subband location to the location of the reference microphone. It then applies the updated propagation delay and attenuation corresponding to the new position of the virtual listener. Finally, the obtained monophonic signal is enhanced by the spatial cues computed for each subband (e.g., using head-related transfer functions), creating a spatialized rendering. Example re-renderings are available at http://www-sop.inria.fr/reves/projects/audioMatting. However, in the case of live field recordings, this approach suffers from several limitations. First, the underlying hypothesis of time-frequency sparseness for the acquired signals is often not true in practice, especially in the presence of significant background noise [START_REF] Rickard | Sparse sources are separated sources[END_REF]. This results in noisy position estimates and low quality signal reconstruction when virtually moving throughout the environment. Second, our approach uses a limited number of frequency subbands, acting as representative point sources, to model the auditory environment at each timeframe. While point sources might be appropriate to render well-localized events, background ambiance and extended sources (e.g., the sea on a seashore) cannot be convincingly reproduced using this model (Figure 3).

In this paper, we propose a solution to these shortcomings based on an a priori segmentation of foreground sound events and background ambiance which we describe in Section 2.1. We also present an improved rerendering solution specifically adapted to these two components which preserves the independence from the reproduction setup. In particular, we propose to render the foreground sound events using a set of separate point sources while the background component is encoded using a smoother low-order spherical harmonics representation. Details can be found in Sections 2.2 and 2.3. In this paper, we propose to explicitly separate foreground, non-stationary and well localized, sound events from background components that are more stationary and spatially diffuse. Section 3 describes the results of a pilot perceptual evaluation study aimed at assessing the quality of our approach relative to reference binaural and B-format recordings in the case of fixed-listening-point scenarios.

Finally, our approach introduces additional authoring capabilities by allowing separate manipulation of each component, which we briefly outline in Section 4 before concluding.

IMPROVED ANALYSIS AND RE-SYNTHESIS

This section addresses a set of possible improvements to our previous technique. They are based on an a priori segmentation of background and foreground components leading to a two-layer model, similar in spirit to the pairwise/non-directional and direct/diffuse decompositions used in some spatial audio coding approaches [START_REF] Pulkki | Directional audio coding: Filterbank and stft-based design[END_REF][START_REF] Goodwin | Analysis and synthesis for universal spatial audio coding[END_REF][START_REF] Pulkki | Spatial impulse response rendering[END_REF][START_REF] Breebaart | MPEG spatial audio coding/MPEG surround: Overview and current status[END_REF]. However, since we are warping the direct component when re-rendering from different listening points, switching between localized/diffuse models on a per-subband basis would introduce audible artefacts in our case. We chose to perform a finer-grain segmentation of the input recordings as a pre-processing step which does not rely on position estimates. Such an approach was already reported to improve results for blind source separation problems [START_REF] Choi | Real-time binaural blind source separation[END_REF]. We also propose re-rendering strategies tailored to each component.

Background/foreground segmentation

We chose to segment stationary background noise from non-stationary sound events using the technique by Ephraim and Malah [START_REF] Ephraim | Speech enhancement using a-minimum mean-square error short-time spectral amplitude estimator[END_REF], originally developed for denoising of speech signals. This approach assumes that the distributions of Fourier coefficients for signal and noise are statistically independent zero-mean Gaussian random variables. Under this assumption, the spectral amplitude of the denoised signal is estimated using a minimum mean-square error criterion. The background noise signal is then simply obtained by subtracting the denoised signal from the original. We found the algorithm to perform quite well. While not perfect, it leads to a foreground component with limited musical noise. In most cases, this noise is masked when re-combined with the background component at re-rendering time. The extracted foreground component, containing nonstationary sounds is also better suited to our underlying assumption of time-frequency sparseness than the original recordings (see Figure 5). However, several foreground sound sources might still overlap in timefrequency. Background and foreground segmentation is performed independently on the signals from all microphones.

Background "panorama" generation

The separated foreground and background components are both processed using the analysis pipeline described in Section 1 (see also Figure 1). However, in the case of the background component, we obtain noisier position estimates since this component will generally correspond to background noise and sources with low signal-to-noise ratios. In order to produce a smooth spatial background texture, we use the obtained positions to encode the corresponding subband signals on a 1 st -order spherical harmonic basis. No warping is applied to the background component in this case (Figure 4).

As our signals are real-valued, we encode them with real spherical harmonics defined as:

y m l (θ , φ ) =    √ 2K m l cos(mφ )P m l (cosθ ) √ 2K m l cos(-mφ )P -m l (cosθ ) K 0 l P 0 l (cosθ ) m > 0 m < 0 m = 0 (1)
where l is the order, m ∈ [-l; +l], P is the associated Legendre polynomial and K is a scaling factor defined as:

K m l = (2l + 1) 4π (l -|m|)! (l + |m|)! . (2)
For each subband signals, we compute the minimum and maximum elevation and azimuth of the obtained positions over the entire duration of the recording. Then, we uniformly expand the background signal in this area. We choose the background signal to encode from the monophonic recording closest to the center of the acquired scene. Accordingly, the background texture is encoded relative to a fixed reference point, for instance the central point of the scene.

This background panorama can thus be encoded in a preprocessing stage so that only the decoding is performed at run-time, e.g., when freely navigating in the recordings. Several decoding options are available depending on the desired reproduction setup [START_REF] Jot | A comparative study of 3D audio encoding and rendering techniques[END_REF].

Improved foreground re-synthesis

At re-rendering time, we perform a warping of the original foreground recordings in order to generate a signal as consistent as possible with the desired virtual listening position (Figure 4). Assuming an inverse distance attenuation for point emitters, the warped signal R ′ i (t) in subband i is given as:

R ′ i (t) = r i 1 /r i 2 R i (t + (δ i 1 -δ i 2 )), (3)
where r i 1 ,δ i 1 are respectively the distance and propagation delay from the considered time-frequency atom to the reference microphone and r i 2 ,δ i 2 are the distance and propagation delay to the desired listening position. This warping heavily relies on the fact that we consider the subband signals to be re-emitted by anechoic point sources. In real-world environments this model is challenged, due to the strong directionality of some sound sources. As a result, discontinuities can appear when the virtual listener is moving around if the signal from a single reference microphone is used (e.g., the one closest to when the microphones are widely spaced. To further improve the re-rendering quality of the foreground component, we also smooth our position estimates for the subbands using Kalman filtering [START_REF] Kalman | A new approach to linear filtering and prediction problems[END_REF]. This prevents large and fast position changes and limits possible "wobbling" effects due to jittery subband positions.

PILOT SUBJECTIVE EVALUATION

In order to evaluate the quality of a spatial audio reproduction system based on our approach, we compared it to binaural and B-format recordings in the context of various scenarios with fixed listening points.

Test stimuli and procedure

We recorded test scenarios in two different environments: indoors in a moderately reverberant room (RT60 ≈ 0.3 sec. at 1KHz) and outdoors (see Figure 6). For each scenario, we used 8 monophonic recordings made with AudioTechnica 3032 omnidirectional microphones to run our localization and re-rendering approach. A pair of Sennheiser MKE-2 gold microphones was placed inside the ears of a subject to capture reference binaural recordings and we also acquired a B-format version of the scenes using a Soundfield ST250 microphone. Eventually, four recordings (one indoors, three outdoors), each about 50 sec. long, were chosen for quality testing.

We used 8 non-overlapping subbands uniformly distributed on a Bark scale to run our spatial analysis (Figure 1). Then, a binaural rendering from a point of view similar to the binaural and B-format recordings was generated from the monophonic input of the closest omnidirectional microphone and the time-varying locations obtained for the subbands. The signal of the same microphone was used to generate both a binaural rendering of the foreground events and the 1 st -order spherical harmonic background decoded over headphones using a virtual loudspeakers technique. In both cases, we used head related transfer functions (HRTFs) of the LISTEN database (http://recherche.ircam.fr/equipes/salles/listen/) for re-rendering. We also generated a re-rendering without explicit background/foreground segmentation considering the original recording to be entirely foreground. B-format recordings were also converted to binaural using a similar virtual loudspeaker approach.

We used a protocol derived from Multiple Stimuli with Hidden Reference and Anchors procedure (MUSHRA, ITU-R BS.1534) [START_REF]EBU subjective listening tests on internet audio codecs[END_REF][START_REF]EBU subjective listening tests on low-bitrate audio codecs[END_REF][START_REF]Method for the subjective assessment of intermediate quality level of coding systems[END_REF] to evaluate each scenario, using four tests stimuli (binaural reference, Bformat, our approach with foreground only, our approach with background/foreground segmentation) and a hidden reference. We also provided one of our 8 monophonic recordings and the omnidirectional (W) component of the B-format recordings as anchors, resulting in a total of 7 signals to compare. Corresponding test stimuli are available at the following URL: http://www-sop.inria.fr/reves/projects/aes30. Test stimuli were presented over Sennheiser HD600 headphones. Monaural anchor signals were presented at both ears.

Five subjects, aged 23 to 40 and reporting normal hearing, volunteered for this evaluation. They were asked to primarily focus on the spatial aspects of the sounds, paying particular attention to the position of the sources. Since the recordings were made with different microphones, we asked them to avoid specific judgments comparing the general timbre of the recordings. However, the subjects were instructed to keep track of any artefact compromising the quality of the reproduction. Their comments were gathered during a short post-screening interview. Subjects were instructed to rank the signals on a continuous [0,100] quality scale and give the highest possible score to the signal closest to the reference. They were also instructed to give the lowest possible score to the signal with the worst spatial degradation relative to the reference.

Results

Figures 7 and8 summarize the results of this study. The subjects were able to identify the hidden reference and it received a maximal score in all test cases. In most cases, our approach was rated higher than B-format recordings in terms of quality of spatial reproduction. This is particularly true for the foreground-only approach which does not smooth the spatial cues and obtains a very high score. However, the subjects reported artefacts due to subbands whose localization varies rapidly through time, which limits the applicability of the approach in noisier environments. Our approach including background/foreground separation leads to smoother spatial cues since the low order background signal may mask the foreground signal. Hence, it was rated only slightly better than the B-format recordings. Subjects did not report specific artefacts with this approach, showing an improved signal quality. As could be expected, the monophonic anchors received the lowest scores. However, we can note that in some of our test cases, they Fig. 6: Example recording setups. We used 8 omnidirectional microphones (circled in yellow) to capture the auditory scene as well as a Soundfield microphone (highlighted with a light red square) to simultaneously record a B-format version. A binaural recording using microphones placed in the ears of a subject provided a reference recording in each test case.

F O R M A T F O R E G R N D O N L Y F O R E G R N D + B A C K G R N D M O N O A N C H O R M O N O A N C H O R ( W ) R E S T I T U T I O N T E C H N I Q U E M U S H R A S C O R E
Fig. 7: Average MUSHRA scores and 95% confidence intervals for all subjects and all scenarios.

received scores very close to the B-format reproduction. This is probably due to the low spatial resolution of Bformat but could also arise from a non-optimal HRTFbased decoding.

Looking at the various test-cases in more detail, Figure 8 highlights a significantly different behavior for the indoor scenario (TEST#3). In this case, very little background sound was present, hence our approach based on background and foreground separation did not lead to any improvement and, in fact, resulted in a degraded spatial impression. The B-format reproduction, however,

0 2 0 4 0 6 0 8 0 1 0 0 B X F O R M A T F O R E G R N D O N L Y F O R E G R N D + B A C K G R N D M O N O A N C H O R M O N O A N C H O R ( W ) R E S T I T U T I O N T E C H N I Q U E M U S H R A S C O R E T E S T 1 T E S T 2 T E S T 3 T E S T 4
Fig. 8: Average MUSHRA scores and 95% confidence intervals for all subjects in each of our 4 test scenarios.

obtained significantly better scores in this case, probably due to the favorable configuration of the three speakers (one in front, one to the left, and one to the right).

Discussion

In terms of audio quality, feedback from the subjects of the tests shows that our improved algorithm outperforms the previous foreground-only solution. This is of course due to the smoothly varying background and more robust foreground estimates. However, our proposed approach appears less convincing in terms of localization accuracy. Significant parts of the foreground sounds can still be present in the background component and will be spatialized using a different strategy. The resulting We used a small number of frequency subbands in our tests which can challenge our time-frequency orthogonality assumption resulting in noisier position estimates for the foreground component. However, we obtained less convincing results with an increased number of frequency subbands due to less accurate correlation estimates for narrower subbands signals.

We do not currently model sources "at infinity", which may appear in the background but also in the foreground component. Our position estimation can return erroneous position estimates in this case due to the limited extent of our position histogram. This could also explain the perceived degradation of spatial cues compared to the reference. Explicit detection of far-field sources is a component we are planning to add in the near future. Finally, non-individualized HRTF processing could also be a major cause of spatial degradation. Running the test with head-tracking and individualized HRTFs might lead to improved results.

APPLICATIONS

Our approach can lead to spatial audio coding applications for live audio footage in a way similar to [START_REF] Pulkki | Directional audio coding: Filterbank and stft-based design[END_REF][START_REF] Goodwin | Analysis and synthesis for universal spatial audio coding[END_REF][START_REF] Pulkki | Spatial impulse response rendering[END_REF][START_REF] Breebaart | MPEG spatial audio coding/MPEG surround: Overview and current status[END_REF], but it also offers novel decoding/authoring capabilities not available with previous techniques such as free-viewpoint walkthroughs. Figure 10 illustrates the virtual reconstruction of a seashore scene with a pedestrian walking on a pebble beach recorded with the setup shown in Figure 9. A spatial energy map is overlaid, highlighting the location of foreground time-frequency atoms. Note how the position of the footsteps sounds is well reconstructed by our approach. The sound of sea waves hitting the rocks on the shore is mostly captured by the background component (see also Figure 5). Please, visit the web pages mentioned in Sections 1 and 3 for example audio files and videos.

Spatial re-synthesis with free-moving listener

Our approach allows for a "free-viewpoint" spatial audio rendering of the acquired soundscapes. As the virtual listener moves throughout the scene, the foreground component is rendered using a collection of point sources corresponding to each time-frequency atom, as described in section 2.3. The background component is simply rotated based on the current orientation of the listener in order to provide a consistent rendering. Our representation encodes spatial cues in world space and can thus be rendered on a variety of reproduction setups (headphones, multichannel, etc.).

Background/foreground editing

Our two-layer model allows for independent control of the background and foreground components. Their overall level can be adjusted globally or locally, for instance to attenuate foreground sounds with local virtual occluders while preserving the background. The foreground events can also be copied and pasted over a new background ambiance.

Re-rendering with various microphones

Finally, the microphones used for the analysis process can be different from the one used for re-rendering. For instance, it is possible to use any directional microphone to get a combined effect of spatial rendering and beamforming.

CONCLUSION

We presented an approach to convert field recordings into a structured representation suitable for generic 3D audio processing and integration with 2D or 3D visual content. It applies both to outdoor environments or indoor environments with limited reverberation, provides a compact encoding of the spatial auditory cues and captures propagation and reverberation effects which would be very difficult to render with the same level of realism using traditional virtual acoustics simulations.

Perceptual comparisons with reference binaural and Bformat recordings showed that our approach outperforms B-format recordings and can get close to reference binaural recordings when all time-frequency atoms are rendered as foreground point sources. However, artefacts due to background noise lead to reduced signal quality. An alternative solution was proposed based on the explicit segmentation of stationary "background noise" and non-stationary "foreground events". While the signal quality is significantly improved when re-rendering, spatial cues were perceived to be degraded, probably due to non-optimal background separation.

In the future, we would like to improve on our background/foreground segmentation approach, possibly based on auditory saliency models [START_REF] Kayser | Mechanisms for allocating auditory attention: An auditory saliency map[END_REF] or taking advantage of the signals from all microphones. Alternative sparse representations of the signals [START_REF] Mallat | Matching pursuits with time-frequency dictionaries[END_REF][START_REF] Lewicki | Learning overcomplete representations[END_REF] could also be explored in order to improve our approach. Further comparisons to other sound-field acquisition techniques, for instance based on high-order spherical harmonic encoding [START_REF] Abhayapala | Theory and design of high order sound field microphones using spherical microphone array[END_REF][START_REF] Meyer | Spherical microphone arrays for 3d sound recording. chap. 2 in Audio Signal Processing for next-generation multimedia communication systems[END_REF], Fourier-Bessel decomposition [START_REF] Laborie | A new comprehensive approach of surround sound recording[END_REF][START_REF] Laborie | High spatial resolution multi-channel recording[END_REF] or directional audio coding [START_REF] Pulkki | Directional audio coding in spatial sound reproduction and stereo upmixing[END_REF][START_REF] Pulkki | Directional audio coding: Filterbank and stft-based design[END_REF] would also be of primary interest to evaluate the quality vs. flexibility/applicability tradeoffs of the various approaches. We believe our approach opens many novel perspectives for interactive spatial audio rendering or off-line post-production environments, for example to complement image based rendering techniques or freeviewpoint video.

Fig. 1 :

 1 Fig. 1: Overview of our analysis pipeline.

Fig. 2 :

 2 Fig. 2: Construction of a global spatial mapping for the captured sound-field. Based on calculated timedifferences of arrival estimation between all pairs of recordings, we sample all corresponding hyperbolic loci to obtain a position estimate for each considered subband (shown as colored sphere).

Fig. 3 :

 3 Fig.3: Typical components of a real-world auditory scene. In this paper, we propose to explicitly separate foreground, non-stationary and well localized, sound events from background components that are more stationary and spatially diffuse.

Fig. 9 :

 9 Fig. 9: Recording setup used for the seashore recordings.

Fig. 10 :

 10 Fig. 10: Example virtual reconstruction of a seashore with walking pedestrian. Yellow spheres correspond to the locations of the microphones used for recording.

ACKNOWLEDGMENTS

This research was made possible by a grant from the région PACA and was partially funded by the RNTL project OPERA (http://www-sop.inria.fr/reves/OPERA).


Sylvain Lefebvre
email: sylvain.lefebvre@sophia.inria.fr

Carsten Dachsbacher
email: carsten.dachsbacher@sophia.inria.fr

TileTrees

Keywords: texturing, texture mapping, interactive painting

Figure 1: Left: A torus is textured by a TileTree. Middle: The TileTree positions square texture tiles around the surface using an octree. At rendering time, the surface is projected onto the tiles. Right: The tile map holding the set of square tiles.

Introduction

Texture mapping has become one of the fundamental component of computer graphics applications. By separating shape representation from surface appearance it provides a powerful and convenient tool to create, paint and render highly detailed objects and sceneries, at low geometrical cost.

The established approach for texture mapping is to flatten a surface into the 2D domain of a square image. The surface is parameterized into the plane. While some surfaces have a natural planar parameterization (cylinders, cones, more generally all developable surfaces), in most cases this operation is extremely difficult. Thus, the problem of finding good planar parameterizations has attracted lot of research interest and extremely powerful techniques have been devised [START_REF] Floater | Surface Parameterization: a Tutorial and Survey[END_REF]. The challenge is to flatten the surface while keeping a low distortion, which often requires to cut the surface in independently parameterized charts. These charts are later packed into a single texture atlas [START_REF] Maillot | Interactive texture mapping[END_REF]. Providing a tight packing is key to avoid wasting memory.

Nowadays, with the increasing demand for realism and high quality in computer graphics, artists are often required to paint detailed multi-layered texture maps for objects and large parts of the scenery. As a result, memory consumption for texture data increased much faster than available memory. The limitations and inherent difficulties of planar parameterization become less acceptable: Memory is wasted by the impossibility to efficiently pack irregular charts, or by oversampling to compensate for distortion. Most parameterizations are static and assume homogeneous sampling: Once computed they cannot adapt to artist painted content. Chart boundaries produce visible discontinuities in the bilinear interpolation. Finally, most methods encode the mapping as 2D coordinates in the vertices of a triangle mesh, and cannot be used on implicitly defined surfaces.

This lead several researchers toward adaptive and volume approaches. The object is immersed into a volume storing color information only around the surface. Data is stored in a spatial hierarchy, typically an octree. This solves a number of issues: A planar parameterization is no longer necessary, a seamless interpolation can be defined, the hierarchy can be refined in areas of interest. Moreover, the approach does not involve any complex pre-processing. Unfortunately, spatial hierarchies also imply an overhead in access time and space, which limits their use in interactive applications.

Our novel approach combines the advantages of volume approaches and 2D texture mapping. It removes the need for a global parameterization while relying on 2D textures for efficient packing and access. Our key idea is to use an octree to position square texture tiles around the surface. During rendering the surface is projected onto the tiles, and the color is retrieved by a simple 2D texture fetch into a tile map (see Figure 1). Note, however, that we do not seek to define a continuous texture domain: The tiles have different sizes and are packed together in arbitrary order. The square nature of the tiles makes efficient packing easier and let us define a seamless interpolation over the surface. Furthermore, by changing the resolution of the tiles we can locally and dynamically adapt the resolution to artist painted content.

Previous Work

Since its introduction by Catmull [START_REF] Catmull | A Subdivision Algorithm for Computer Display of Curved Surfaces[END_REF]], texturing has spanned a large body of research. In particular, several researchers have focused on overcoming the limitations of texture mapping.

Importance driven parameterization methods have been proposed to allocate more resolution to regions with fine texture detail [START_REF] Sloan | Importance driven texture coordinate optimization[END_REF][START_REF] Sander | Signal-specialized parameterization[END_REF][START_REF] Balmelli | Spaceoptimized texture maps[END_REF]. [START_REF] Carr | Painting detail[END_REF] addressed the issue of dynamically updating the parameterization while the user paints on the surface. The geometry is clustered into charts mapped onto square regions of the texture. The resolution allocated to each chart is dynamically adapted to the user painted content. Our TileTree enables a similar interactive painting approach, but without the need to pre-cluster and dynamically parameterize the triangle mesh.

Several approaches avoid seams by parameterizing the surface onto regular charts [START_REF] Purnomo | Seamless texture atlases[END_REF][START_REF] Carr | Rectangular multi-chart geometry images[END_REF]]. While stored discontinuously, neighboring charts have corresponding samples: A continuous interpolation can be defined along the surface. To avoid splitting the geometry along chart boundaries, Tarini et al. [START_REF] Tarini | Polycubemaps[END_REF]] parameterize surfaces on the faces of a regular polycube: A set of fixed size cubes surrounding the object. Not only does this define a continuous, tileable texture space, but the original mesh does not need to be modified. However, the polycube maps have some drawbacks: The fixed resolution has to be carefully chosen to match the geometric features, the construction requires manual intervention, and finally a triangle mesh is required to encode the parameterization.

To enable texturing of implicit surfaces and avoid explicit parameterization altogether, [START_REF] Benson | Octree textures[END_REF] and [START_REF] Debry | Painting and rendering textures on unparameterized models[END_REF] proposed to encode texture data in an octree surrounding the surface. This provides low distortion and adaptive texturing, at the expense of a space and time overhead: The tree contains many unused entries in its nodes, and accessing the data requires a long chain of indirections. Note that the number of indirections can be reduced at the expense of increased space overhead [START_REF] Lefebvre | Octree Textures on the GPU[END_REF][START_REF] Lefohn | Glift : Generic, efficient random-access gpu data structures[END_REF]]. Instead, Lefebvre and Hoppe [START_REF] Lefebvre | Perfect spatial hashing[END_REF] forgo adaptivity and compactly store fixed-resolution volume color data with a perfect spatial hash. The space overhead is very low and data is accessed with only two memory lookups. Unfortunately, both methods share difficulties inherent to volume approaches when it comes to interpolation. Figure 3: Correct tri-linear interpolation in a volume requires storing the surface as a thick layer. However, the bottom (blue) samples should be sufficient to texture the surface, leading to a 2x saving.

The surface is represented as a thick layer into the volume, thus requiring to store and access 8 samples (see Figure 3). However, interpolating over a surface should only require 4 samples: These approaches always store and access at least twice the data required to texture a given surface. In contrast, our TileTree maps 2D texture tiles onto the surface.

Finally, volume surface trees [START_REF] Boubekeur | Volume-surface trees[END_REF]] are also related to our work. The authors notice that subdividing an octree around a surface until very fine resolution is wasteful: After some level of subdivision the surface is faithfully captured by a simple heightfield. We follow a similar idea and stop subdividing the octree as soon as the surface can be textured by simple square tiles.

TileTrees

Overview

Our approach starts by building an octree around the surface to be textured, similarly to previous octree-based texturing methods. However -and this is the key idea of our work -instead of storing a single color value in the leaves, we map 2D tiles of texture data onto the faces of the leaves (up to six tiles per leaf). The tiles are compactly stored into a regular 2D texture, the tile map. During rendering, each surface point is projected onto one leaf face. This produces texture coordinates then used to access the corresponding texture tile. This idea is illustrated Figure 2.

We only subdivide the octree until no more than one fold exists in each leaf (see Section 3.2). Since with most geometry the texture detail is much finer than the geometric features, the octree leaves tend to be much larger than the texture pixel size: Many neighboring pixels share the same leaf, which guarantees a good access coherence.

The surface is projected onto the faces of the leaves with a simple parallel projection. The face to project onto is locally determined from the surface normal. Note that this projection only requires knowing the surface normal and enclosing leaf. It is performed dynamically at rendering time: Thus our approach does not require to store additional information in vertices. In fact, it does not even require vertices at all: It can be used on implicitly defined surfaces.

The following sections describe each aspect of our approach in more details.

Projection

Each leaf of the octree encloses a piece of surface. Our goal is to project this part of the surface onto one or more faces of the leaf so that each point is uniquely textured. In other words the projection must be injective.

In addition, we want to perform the projection dynamically, at runtime. Therefore, it has to be as simple as possible to compute. However, if the projection fails to handle some surface configurations, we would have to subdivide the octree until reaching pixel resolution. As a compromise, we choose to perform a parallel projection onto the faces of the leaves. The face to project onto is chosen using the major direction of the normal to the surface. While being extremely simple to compute, this projection can handle successfully non trivial cases, including a full sphere. It also handles correctly two-sided thin surfaces, as illustrated Figure 4 -a difficult case with previous volume approaches [START_REF] Benson | Octree textures[END_REF][START_REF] Debry | Painting and rendering textures on unparameterized models[END_REF]. In fact, it can even texture the back and front sides of a triangle differently.

However, it also has a few drawbacks. First, some small amount of distortion is present on steep surfaces. However, it is worth noting that this distortion is no greater than the one produced by an octree texture on faces at an angle. Second, it is not surjective: Some parts of the faces may never be covered by the projected surface. As each face is represented in memory by a square tile, this will result in wasted memory space (see Figure 6, left). We will see in the next section how this issue is addressed.

Building a tight octree

The octree surrounding the surface has to satisfy two constraints. First, we have to make sure to subdivide enough so that an injective projection is possible. Given the projection described in Section 3.2, this implies that no leaf must contain more than one fold in the directions used for projection (see Figure 5). Second, we seek to minimize memory waste. Consider a leaf in which the surface only projects partially onto the faces, leaving some unused pixels in the tiles. By further subdividing we get a better approximation of the surface and we increase pixel usage (see Figure 6). Of course, at the same time we increase the depth of the octree: There is a tradeoff between space efficiency and octree complexity. We therefore expose a coverage threshold to the user. This threshold defines how acceptable it is to waste space to favor access efficiency. We also enforce a maximum tree depth, as this is mandatory for efficient GPU implementation [START_REF] Lefebvre | Octree Textures on the GPU[END_REF].

Before describing the details of the octree construction, we define terms for the leaf configurations that occur. We distinguish two main types of leaves (see Figure 8). A 1-leaf is a leaf where the surface projects onto a single face. A n-leaf is a leaf where the surface projects to more than one face. Now, within the set of 1leaves we distinguish three subtypes. A full-leaf is a 1-leaf with a percentage coverage value of 1 (the tile is entirely used). We call a leaf-stack a set of 1-leaves at same octree level that are neighboring in the direction of the face supporting the tile (see Figure 8). The important property of a leaf-stack is that all the faces in the stack can share a same texture tile without overlapping. A leaf involved in a leaf-stack is named a stacked-leaf. Finally, a boundary-leaf is defined as a 1-leaf which is not involved in any leaf-stack and is not a full-leaf either. Figure 7 shows the various types of leaves on a 3D model.

In order to build the octree, we take the following steps, summarized in Figure 9: 1. Subdivide the octree until leaves contain one fold at most. 2. Enforce coverage constraint on n-leaves.

3. Enforce coverage constraint on boundary-leaves.

4. Split all 1-leaves that could form a stack with a neighbor at a deeper subdivision level. 5. Detect leaf-stacks (all members share a same texture tile).

Our implementation relies on ray-surface intersections for the tree construction, making it suitable for both polygonal meshes and implicit surfaces. Within each leaf we cast axis aligned rays to detect folds and obtain surface normals. The sampling rate must be high enough so that all leaf faces required for proper texturing will be detected, and so that no fold will be missed. Note that nothing precludes the use of more robust detection mechanisms.

Once the octree is created, we allocate tiles for each of the leaf face reached by the surface. The next section describes how tiles are allocated.

1)

3)

2)

4)

Figure 9: The octree construction involves four types of subdivisions. 1) Split until no foldover. 2) and 3) Split to enforce coverage threshold. 4) Split to create leaf-stacks.

Tiles

After octree subdivision, the number of tiles to allocate is:

#full-leaves + #boundary-leaves + #leaf-stacks + ∑ {n-leaf} (n)
where # is the counting operator.

Each tile is mapped onto a leaf face so that the centers of the border samples are aligned with the boundaries of the face. This ensures seamless rendering and enables use of native hardware bilinear filtering. This also implies some sample duplication: Two neighboring tiles encode the same samples along their boundary. Using large tiles reduces this overhead.

To ensure matching samples between leaves at different subdivision levels, the tile size must be equal to 2 k + 1, with k a positive integer (see Figure 10, left). In case of adaptive resolution, this will also ensure that samples of the finer resolution tile are aligned with samples of the coarser resolution tile (see Figure 10, right).

For a simple access during rendering all tiles are packed together into a single texture: the tile-map. Tiles within n-leaves are stored contiguously. Thus for each leaf we allocate a texture rectangle with a size of n(2 k + 1) × (2 k + 1), 1 ≤ n ≤ 6. The coordinates of the top left corners are stored in the octree leaves. The square shape of the tiles allows for simpler and therefore faster packing than with arbitrarily shaped charts. In our implementation we used a naive approach which places larger tiles first, from left-to-right and top-to-bottom. For speed-up, we track the first free column of every texture row. Although the packing can be further optimized by using quad-trees, it already performs very well, placing 18664 tiles in 96 milliseconds on the armadillo model of Figure 13.

Seamless interpolation

Interpolating the texture samples along the surface is key to avoid pixelated appearance. Seamless interpolation is a difficult issue which must not be overlooked. For instance, with volume ap- proaches interpolation requires up to 8 lookups into the data structure [START_REF] Lefebvre | Perfect spatial hashing[END_REF], and more if adaptive texturing is used [START_REF] Benson | Octree textures[END_REF]. Of course, this strongly impacts performance. This can be reduced by storing small blocks of data instead of point-wise colors, but border sample replication largely increases space overhead -especially in a volume where a thick layer has to be defined around the surface (see Figure 3).

Our TileTrees enable fast seamless interpolation over smooth surfaces. We rely on the graphics hardware interpolation when accessing the tiles, and only have to perform a few more operations to obtain a seamless result. In the following discussion, we assume the per-sample color is already known. Please refer to Section 4 for an overview of how to fill a TileTree with texture content. Also, please note that seamless interpolation is currently limited to smooth surfaces. By smooth surface, it is to be understood that we refer to a continuous normal field over the surface, may it be a triangle mesh. We discuss this issue in more details in Section 6.

For correct interpolation, there are three cases to consider: fullleaves and stacked leaves, partially covered faces, and n-leaves interior.

full-leaves

Within full-leaves and stacked-leaves a correct seamless interpolation is guaranteed: The tile has all the necessary samples. Recall we have a one pixel border replication between neighboring tiles (see Section 3.4 and Figure 10, left).

partially covered faces

Within boundary-leaves and n-leaves the surface often only partially covers a face. Therefore, some tile samples have no defined color. At boundaries, these undefined colors would bleed-in during interpolation. Fortunately, the color of these samples is simply located in a tile of the neighboring leaf. For instance, consider the boundary-leaf of Figure 8. The missing samples are located in the n-leaf just below. We simply fill-in undefined samples by reading their color in the neighboring leaf.

n-leaves interior N-leaves have an additional difficulty: The face accessed during rendering is abruptly changing along the surface (see Figure 11).

The key idea to achieve a correct interpolation is to define the final color as a weighted sum of the contribution of all faces. Note that three faces can contribute at most: The three faces corresponding to the direction of the normal. We name the corresponding tiles T x , T y and T z , one for each main direction.

To define the interpolation weights, we store a binary flag into the alpha channel of the tile samples. This flag determines whether a sample is used by the enclosed surface (see Figure 11). This is easily computed by considering the surface normal at the location onto which the sample projects. Note that if the surface is not found under the sample, the color of the closest sample may be repeated. Alternatively, we can march along the faces to find the color of the sample on the neighboring tile. Note however that none of this will introduce a discontinuity: The final color is a continuous interpolation of the colors from all faces.

The flag is interpolated when accessing the tile data, so its value varies contiguously between [0, 1] on the surface. Within the n-leaf we now have three continuously varying flag values: α x , α y and α z interpolated from tiles T x , T y and T z . Note that if a face is not used by the surface it has no associated tile and we force its flag value to 0. The key idea is that the flag value will be 1 whenever the tile contains proper samples for the surface, and will continuously drop to 0 when the tile is no longer relevant. Interpolation only has to occur in areas where none of the flag values equal 1. This leads to a first definition of the weights w x , w y and w z :

w x = α x • (1 -α y ) • (1 -α z ) w y = α y • (1 -α z ) • (1 -α x ) w z = α z • (1 -α x ) • (1 -α y )
From which we compute the final color as:

c = (c x • w x + c y • w y + c z • w z ) (w x + w y + w z )
where c x , c y and c z are colors fetched from tiles T x , T y and T z .

This works well in most cases, however these weights are not robust. If more than one flag equals 1, or all equal 0, the weights are null and the color is undefined. Both cases are possible if small geometric features are present in between tile samples. Fortunately, there exists a simple solution to this issue. We need to enforce that only one flag reaches 1 simultaneously. The normal to the surface gives exactly that: It always selects a single face, so we use it to dampen the flags. We thus compute the weights as:

damp = abs(nrm)/max(|nrm x |, |nrm y |, |nrm z |) w x = α x damp x • (1 -α y damp y ) • (1 -α z damp z ) w y = α y damp y • (1 -α z damp z ) • (1 -α x damp x ) w z = α z damp z • (1 -α x damp x ) • (1 -α y damp y )
where nrm is the normal to the surface at the point being considered, and abs a per-component absolute value. The zero case can then be avoided by always adding a small epsilon to the flag values. As long as the normal field is smooth, the weights are continuous and the final result is a seamless interpolation of the samples.

adaptive resolution

Whenever adaptive resolution is used, an additional difficulty appears: At the boundary between two tiles of different resolution, some samples of the higher resolution tile have no corresponding sample on the coarser resolution tile. This is illustrated Figure 10,right. With no specific treatment this produces obvious high-frequency discontinuities. In order to ensure smooth interpolation, we force the color of higher-resolution border samples to match the bi-linear interpolation of the lower-resolution samples.

MIP-mapping

Due to the tile resolution of 2 k + 1, we cannot directly apply MIPmapping to the tile map. MIP-mapping can be achieved by computing a separate tile map for each resolution level. This requires to store one tile coordinate per-level in the octree leaves. During rendering, the appropriate MIP-mapping level is computed and the color is fetched from the corresponding tile map. Two levels may be accessed for linear interpolation in-between MIP-mapping levels. Also note that in case of extreme undersampling, the tree itself may be MIP-mapped.

Implementation details

For the tree storage and lookup we rely on the hardware implementation of [START_REF] Lefebvre | Octree Textures on the GPU[END_REF]. Each leaf stores:

• A bit vector marking tile presence on each face (6 bits).

• The coordinates of the top left corner of the tiles within the tile map (two 16 bits numbers). • The resolution of the tile (8 bits).

The complete pseudo-code for the shader is given below:

Filling with content

We introduced the TileTree data structure and explained how to access it during rendering. We now have to define means of filling a TileTree with texture content. In this section we describe an interactive painting tool for TileTrees, and briefly explain how to convert between TileTrees and other texture representations.

Interactive painting

Interactive painting is performed easily using TileTrees. The idea is simple: When building the tile map, we also create an auxiliary texture storing the coordinates of the surface points projecting to the tile samples. A simple ray-surface intersection is used for this purpose.

Once the auxiliary texture is built, painting is performed as a render to texture operation: We directly paint into the tile map using the GPU. We rasterize a quad covering the entire tile map, retrieve the world space coordinate of the samples from the auxiliary table, and check whether samples are inside the brush. If inside, their color is updated. Alpha blending is used to attenuate the brush influence. Painting is extremely fast, and the speed does not depend on the brush size: In fact all pixels may be updated at once if desired.

Painting is slightly more complex when adaptive resolution is used. Recall that for adaptive resolution we need to compute the color of some samples to obtain a smooth interpolation (see Section 3.5). In our current implementation, we update these samples after each paint stroke. Also, in our current application the user is in charge of increasing or decreasing the local tile resolution. A painting scheme automatically adapting the texture resolution, such as the one proposed by [START_REF] Carr | Painting detail[END_REF], could be easily designed on top of TileTrees. Please refer to the accompanying video for an example of an interactive painting session.

Conversion

Converting from an existing texture is a convenient feature. This can be used, for instance, to provide a basis for further painting onto an existing object. The key idea, similarly to interactive painting, is to rely on the coordinates of the surface points projecting to the samples. With a triangle mesh, it is easy to track texture coordinates and to fetch an initial color from an existing atlas. With a volume texture, the 3d coordinates can be directly used to obtain a color at each sample. Converting a TileTree back into a texture atlas can be performed similarly to the fast octree-atlas conversion described in [START_REF] Lefebvre | Octree Textures on the GPU[END_REF] 13.

Results and Discussion

We compare TileTrees with other volume texture mapping approaches: octree textures and hashed textures. Table 1 summaries memory size and performance for each approach. TileTrees are slower than blocked hashed textures, but require 3 times less memory. They are, however, faster than hashed textures with 8 lookups for tri-linear interpolation, while still using less memory. It is remarkable that even with the space overhead of border sample duplication and memory waste of partially covered tile, TileTrees are still smaller than tri-linear hashed textures. This is of course due to the fact that volume texture mapping requires much more samples for interpolation. Note that for a fair comparison we did not use the adaptive capability of the TileTree, which would have further reduce memory usage.

Table 5 shows how octree complexity and tile map usage are linked.

We fix the final resolution to 1024 3 and vary the maximum octree depth. As the depth increases, we get a better usage of the tile map, but it reduces performance as the octree access gets more expansive.

Table 3 shows how the TileTree size evolves with the user adjustable coverage threshold. A higher coverage constraint decreases tile map size, but also increases the octree size. The optimal is therefore obtained for an intermediate value. In practice we often use a coverage threshold of 1 for compactness.

Limitations and Future work

TileTrees have two main limitations.

First, seamless interpolation fails where normals are not continuous along the surface. Typically, edges of a cube will not have a seamless interpolation. While this may be acceptable if the surfaces have different materials, it may be a problem if a continuous texture is desired across these edges. One possible direction to circumvent this issue is to use a smoothed normal for computing the interpolation weights. However, to properly take into account triangles at angles greater than 90 degrees, interpolation must now consider all faces, including those in a direction opposite to the normal. This complicates the TileTree access.

Second, and this may be the most important limitation, the normal field used for access has to be consistent with the real geometry. In particular, if normals have a large angle compared to the real surface, a very high distortion will result: The TileTree is mistaken in using a face that does not match surface orientation. This problem, however, only exists on triangle meshes with extremely coarse tessellations. In this situation a discontinuous normal may be used along the edge, removing distortion at the expense of the aforementioned seam in the interpolation.

Finally, as additional future work we would like to explore the opportunity of using TileTrees for efficient texture loading and caching.

Conclusion

We introduced the TileTree, a new data structure for efficient texture mapping. TileTrees store square texture tiles in the leaves of an octree. The surface is projected onto the tiles during rendering. The resulting texture is seamlessly interpolated along smooth regions of the surface, with little memory and access overhead.

We showed that TileTrees are more compact in memory than other volume approaches, while offering many of their advantages. A low distortion texture mapping is achieved. No parameterization needs to be explicitly stored, making the approach available for implicitly defined surfaces. Moreover, TileTrees natively support adaptive resolution, at no additional rendering cost.

We hope that TileTrees will provide artists and developers with a practical tool to texture map surfaces with as little difficulty as possible.

Figure 2 :

 2 Figure 2: We position texture tiles around the surface using an octree. During rendering the surface is projected onto the tiles of closest orientation. The figure shows the 2D equivalent of a tile tree: A quadtree positioning 1D tiles around a curve.

Figure 4 :

 4 Figure 4: The normal to the surface is used to select on which face to project. The surface point is then mapped to the face with a simple parallel projection.

Figure 5 :

 5 Figure 5: Left: Each leaf may contain up to one fold in the direction of projection. Right: If more than one fold is present the projection is no longer injective.

Figure 6 :

 6 Figure 6: We enforce coverage by subdividing further leaves with coverage under a user specified threshold.

Figure 7 :

 7 Figure 7: Leaves classification: full-leaves appear in blue, stackedleaves in dark-blue, boundary-leaves in green and n-leaves in red.

Figure 8 :

 8 Figure 8: The 2 main types and 4 sub-types of TileTree leaves.

Figure 10 :

 10 Figure 10: Left: For samples to match across boundaries, tiles must have a size of 2 k + 1. Right: Samples of tiles at different resolution are aligned. Color at samples marked by two circles is computed to be the bi-linear interpolation of the neighbors. This ensure continuity across resolutions.

Figure 11 :

 11 Figure11: Within the outlined cell, the face used to texture the surface is abruptly changing, resulting in a visible seam. To perform interpolation within this cell, we flag whether each tile sample is used by the enclosed surface.

Figure 12

 12 Figure12illustrates seamless interpolation and adaptive resolution.

Figure 12 :

 12 Figure 12: Left: Close-up on an n-leaf without interpolation. Middle: Same with seamless interpolation enabled. Right: Interpolation and adaptive resolution.

  access tile data for present tiles float4 clr0=0,clr1=0,clr2=0; if (faceid.x>-1) clr0=tileLkup(leaf,faceid.x,uvw.yz); if (faceid.y>-1) clr1=tileLkup(leaf,faceid.y,uvw.xz); if (faceid.z>-1) clr2=tileLkup(leaf,faceid.z,uvw.xy); /// sample usage vector float3 alpha_xyz = 1e-6+float3(clr0.w,clr1.w,clr2.w); /// seamless interpolation float3 anrm = abs(nrm); float3 damp = anrm/max(anrm.x,max(anrm.y,anrm.z)); alpha_xyz * = damp; float3 inv = (1-alpha_xyz); float3 w = alpha_xyz * inv.yzx * inv.zxy; /// compute final color return (clr0 * w.x+clr1 * w.y+clr2 * w.z)/(dot(w,1)); }

Figure 13 :

 13 Figure 13: Left: Armadillo model textured with a uniform resolution of 1024 3 . The entire TileTree fits in 11.4 MB. Right: Dragon model textured with a uniform resolution of 1024 3 . The entire TileTree fits in 11.3 MB.

Table 1 :

 1 ]. Comparison of a TileTree with octree texture and hashed textures on the armadillo model with an equivalent volume texture resolution of 1024 3 . Frame rate is measured with the viewpoint of Figure

		Memory size Frame rate
	TileTree
		11.4 MB	91 FPS
	Hashed texture
	8 lookups for tri-linear	15.7 MB	34 FPS
	Octree texture
	8 lookups for tri-linear	32.6 MB	25 FPS
	Hashed texture
	blocking for tri-linear	45.9 MB	135 FPS

Table 2 :

 2 TileTree behavior for varying maximum tree depth and fixed resolution of 1024 3 .

	Tree max	Octree	Tile map Tile map	Frame
	depth	size	size	usage	rate
	5	27 KB	17.4 MB	49%	110 FPS
	6	97 KB	13.5 MB	59%	98 FPS
	7	303 KB 11.1 MB	68%	93 FPS
	8	831 KB 10.9 MB	75%	91 FPS
	Coverage Number	Octree	Tile map	Tile map
	threshold	of tiles	size	size	usage
	0	13802	103 KB 18.12 MB	52%
	0.25	20520	217 KB	11.5 MB	63.8%
	0.5	24423	260 KB	11.0 MB	66.5%
	0.75	27373	288 KB	11.0 MB	67.5%
	1	29185	303 KB	11.1 MB	67.6%

Table 3 :

 3 TileTree for a fixed resolution of 1024 3 with varying coverage threshold. Maximum tree depth is set to 7.

Acknowledgements

Thanks to Christian Eisenacher for carefuly proof-reading the paper and to George Drettakis for the video voice over.