Thomas Moeck

Nicolas Bonneel

Nicolas Tsingos

George Drettakis

Isabelle Viaud

Progressive Perceptual Audio Rendering of Complex Scenes

Keywords: Audio rendering, auditory masking, ventriloquism, clustering

Figure 1: Left: A scene with 1815 mobile sound sources. Audio is rendered in realtime with our progressive lossy processing technique using 15% of the frequency coefficients and with an average of 12 clusters for 3D audio processing. Degradations compared to the reference solution are minimal. Right: a scene with 1004 mobile sound sources, running with 25% of the frequency coefficients and 12 clusters.

Introduction

Spatialized audio rendering is a very important factor for the realism of interactive virtual environments, such as those used in computer games, virtual reality, or driving/flight simulators, etc. The complexity and realism of the scenes used in these applications has increased dramatically over the last few years. The number of objects which produce noise or sounds can become very large, e.g., cars in a street scene, crowds in the stadium of a sports game etc. In addition, recent sophisticated physics engines can be used to synthesize complex sound effects driven by the physics, for example the individual impact sounds of thousands of pieces of a fractured object.

Realistic 3D audio for such complex sounds scenes is beyond the capabilities of even the most recent 3D audio rendering algorithms. The computational bottlenecks are numerous, but can be grouped into two broad types: the cost of spatialization, which is related to the audio restitution format used; and the per sound source cost, which relates to the different kinds of effects desired. An example of the former bottleneck is Head Related Transfer Function (HRTF) processing for binaural rendering [START_REF] Møller | Fundamentals of binaural technology[END_REF]], or the rendering of numerous output channels for a Wave Field Synthesis (WFS) system [START_REF] Berkhout | Acoustic control by wave field synthesis[END_REF], which can use hundreds of speakers. The latter bottleneck includes typical spatial effects such as delays, the Doppler effect, reverberation calculations, but also any kind of studio effect the sound engineers/designers wish to use in the application at hand.

Recent research has proposed solutions to these computational limitations. Perceptual masking with sound source clustering [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF], or other clustering methods [START_REF] Herder | Optimization of sound spatialization resource management through clustering[END_REF]Wand and Straßer 2004] do resolve some of the issues. However, the clustering algorithms proposed to date are either restricted to static scenes, or add an unacceptable computation overhead due to a quadratic step in cluster construction when the number of sources is large. In addition, the cost of per source computation, sometimes called premixing, can quickly become a bottleneck, again for complex soundscapes.

In this paper we present two contributions:

• The first contribution is the speed improvement of the clustering and premixing steps of the [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF]] approach. First, we introduce a new recursive clustering method, which can operate with a fixed or variable target cluster budget, and thus addresses the issue of spatialization cost mentioned above. Second, we develop a novel "pinnacle-based" scalable premixing algorithm, based on [START_REF] Tsingos | Scalable perceptual mixing and filtering of audio signals using an augmented spectral representation[END_REF]], pro-viding a flexible, perceptually-based framework for the treatment of the per-source computation costs.

• The second contribution is the investigation of perceptual issues related to clustering and premixing, based on pilot user studies we conducted. In particular, we investigate the influence of visuals on audio clustering for audio-visual scenes, and propose a modified metric taking into account the indication that it is probably better to have more sources in the view frustum. For scalable premixing, we evaluated the different metrics which can be used, including recently developed perceptual models, such as the audio saliency map [START_REF] Kayser | Mechanisms for allocating auditory attention: An auditory saliency map[END_REF], and performed a perceptual quality test for the new algorithm.

In the following, we briefly overview related previous work, including that in the acoustics and perception literature. We then present the new recursive clustering method in Sect. 3, the new study and the resulting algorithm for scalable premixing in Sect. 4 and the study and novel metric for crossmodal audio-visual clustering in Sect. 5. We present some implementation issues and results, then conclude with a discussion of our approach.

Previous work

Relatively little effort has been devoted to the design of scalable rendering strategies for 3D audio, which can provide level-of-detail selection and graceful degradation. We give below a short overview of the previous work most relevant to our problem.

Encoding and rendering of spatial auditory cues. Progressive spatial sound encoding techniques can be roughly subdivided in two categories.

A first category is based on a physical reconstruction of the wavefield at the ears of the listener. For instance, several approaches have been proposed to perform progressive binaural rendering [START_REF] Blauert | Spatial Hearing : The Psychophysics of Human Sound Localization[END_REF]] by decomposing HRTFs on a set of basis functions through principal component analysis [START_REF] Chen | A spatial feature extraction and regularization model for the head-related transfer function[END_REF][START_REF] Larcher | Study and comparison of efficient methods for 3d audio spatialization based on linear decomposition of HRTF data[END_REF][START_REF] Jot | Binaural simulation of complex acoustic scenes for interactive audio[END_REF]; while providing level-ofdetail, they are limited to this unique restitution format. Alternatively, decomposition of the wavefield can be used (e.g., spherical harmonics) [START_REF] Malham | 3D sound spatialization using ambisonic techniques[END_REF] for level-of-detail, relatively independently of restitution setup (e.g., conversion to binaural format [START_REF] Jot | A comparative study of 3D audio encoding and rendering techniques[END_REF]). High accuracy requires a large number of channels however, limiting the methods' applicability.

Another category performs world-space compression of positional cues by clustering nearby sound sources and using a unique representative position per cluster for spatial audio processing [START_REF] Herder | Optimization of sound spatialization resource management through clustering[END_REF]Wand and Straßer 2004;[START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF]]. Wand et al. [Wand and Straßer 2004] group sources in a hierarchical spatial data structure as used for point-based rendering. However, their approach is very efficient only in the case of static sources. Tsingos et al. [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF]] recently introduced a clustering algorithm driven by a loudness-weighted geometrical cost-function (see Sec. 3). They also use precomputed descriptors (e.g., loudness and tonality) to sort the sources by decreasing importance and perform a greedy culling operation by evaluating auditory masking at each time-frame of the simulation. Inaudible sources can then be safely discarded. Although this approach was found to perform well for environments containing a few hundred sources, it is unclear that it scales well to larger numbers of sources and clusters due to the cost of the proposed clustering algorithm which, in their case, implies a near quadratic number of evaluations of the cost-function.

Scalable audio processing. Fouad et al. [START_REF] Fouad | Perceptually based scheduling algorithms for real-time synthesis of complex sonic environments[END_REF] propose a level-of-detail progressive audio rendering approach in the time-domain; by processing every n-th sample, artifacts are introduced at low budget levels. Wand and Straßer [Wand and Straßer 2004] introduce an importance sampling strategy using random selection, but ignore the signal properties, thus potentially limiting the applicability of this method.

A family of approaches has been proposed to directly process perceptually-coded audio signals [START_REF] Lanciani | Psychoacoustically-based processing of MPEG-I layer 1-2 encoded signals[END_REF][START_REF] Lanciani | Subband-domain filtering of MPEG audio signals[END_REF][START_REF] Darlington | Digital audio effects in the wavelet domain[END_REF][START_REF] Touimi | A generic framework for filtering in subband domain[END_REF][START_REF] Touimi | Efficient method for multiple compressed audio streams spatialization[END_REF] yielding faster implementations than a full decode-process-recode cycle. Although they are well suited to distributed applications involving streaming over low-bandwith channels, they require specific coding of the filters and processing. Moreover, they cannot guarantee efficient processing for a mixture of several signals, nor that they would produce an optimal result. Other methods have explored how to extend these approaches by concurrently prioritizing subparts of the original signals to process to guarantee a minimal degradation in the final result [START_REF] Gallo | Prioritizing signals for selective real-time audio processing[END_REF][START_REF] Tsingos | Scalable perceptual mixing and filtering of audio signals using an augmented spectral representation[END_REF][START_REF] Kelly | The continuity illusion in virtual auditory space[END_REF]. Most of them exploit masking and continuity illusion phenomena [START_REF] Kelly | The continuity illusion in virtual auditory space[END_REF] to remove entire frames of the original audio data in the timedomain [START_REF] Gallo | Prioritizing signals for selective real-time audio processing[END_REF] or, on a finer scale, process only a limited number of frequency-domain Fourier coefficients [START_REF] Tsingos | Scalable perceptual mixing and filtering of audio signals using an augmented spectral representation[END_REF]].

Crossmodal studies. While the primary application of 3D audio rendering techniques is simulation and gaming, no spatial audio rendering work to date evaluates the influence of combined visual and audio restitution on the required quality of the simulation. However, a vast amount of literature in neurosciences suggest that cross-modal effects, such as ventriloquism, might significantly affect 3D audio perception [START_REF] Hairston | Visual localization ability influences cross-modal bias[END_REF][START_REF] Alais | The ventriloquism effect results from near-optimal bimodal integration[END_REF]. This effect tells us that in presence of visual cues, the location of a sound source is perceived shifted toward the visual cue, up to a certain threshold of spatial congruency. Above this threshold, there is a conflict between the perceived sound location and its visual representation and the ventriloquism effect no longer occurs. The spatial window (or angular threshold) of this effect seems to depend on several factors (e.g., temporal synchronicity between the two channels and perceptual unity of the bimodal event) and can vary from a few degrees [START_REF] Lewald | Spatio-temporal constraints for auditory-visual integration[END_REF]] up to 15 • [START_REF] Hairston | Visual localization ability influences cross-modal bias[END_REF]].

Optimized Recursive Clustering

In previous work [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF], large numbers of sound sources are dynamically grouped together in clusters, and a single new representative point source is created. While this approach allows the treatment of several hundred sound sources on a standard platform, it does incur some computational overhead, which becomes a potential bottleneck as a function of the number of inputsources/target-clusters and the available computational budget. To resolve this limitation, we next present a new recursive clustering algorithm. For improved efficiency and accuracy we propose two recursive algorithms: One with a fixed budget of clusters and one with a variable number of clusters. The fixed budget approach allows us to set a fixed computational cost for 3D audio processing and is also useful to address a fixed number of 3D-audio hardware channels when available for rendering. The variable number of clusters dynamically adjusts the computational cost to obtain the best trade-off between quality and speed in each frame, given a user-specified error threshold.

We also discuss a variant of this algorithm which has been included in the commercially available game "Test Drive Unlimited" by EdenGames/ATARI.

In the method of [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF], sources are grouped together For details see [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF]].

Recursive fixed-budget approach

In a first pass, we run the original clustering algorithm with a target number of clusters n 0 . In each subsequent pass, every generated cluster gets divided into n k clusters. The total budget of clustering is thus ∏ k n k . The original clustering algorithm can be considered as a special case where only n 0 is set. In our tests, we typically used a two-level recursion.

Variable cluster budget

This approach dynamically allocates the number of clusters in realtime. This is especially useful for scenes where sounds are frequently changing during time in shape, energy as well as in location. The algorithm then flexibly allocates the required number of clusters; thus clusters are not wasted where they are not needed.

First, every sound source which has not been masked [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF], is put in one cluster which is then recursively split into two until an appropriate condition is met. In every recursion step the error in angle relative to the listener position is computed, for each sound source in a cluster, relative to its centroid. If the average angle error is below a threshold, cluster splitting is terminated. In our tests, we found that a 25 • threshold value proved satisfactory.

Quantitative error/performance comparison

We have performed a quantitative comparison between the previous clustering approach of [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF], and the two proposed recursive clustering methods. We ran several thousand tests with random configurations of 800 sound sources, using the different algorithms and measuring the time and the error (in terms of distance and angle) for each method.

Figure 3 shows the results of the tests for fixed budgets of 12 and 6 clusters using different two-level subdivision strategies. For instance, line 3/4 corresponds to a clustering using 12 clusters (3 toplevel clusters recursively refined into 4). The line 12/1 corresponds Figure 3: Benchmarks for hierarchical clustering of 800 sources using different 6 and 12 cluster configurations. We display average clustering error (also denoted by circle size). Note the significant speed-up compared to the non-hierarchical algorithm for the 12 cluster configurations (in red) while the errors remain similar.

to the previous clustering approach of [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF]] where all 12 clusters are top level.

As we can see, the performance of the recursive approaches are clearly better than the direct algorithm. For the same final budget, the 3/4 and 4/3 configurations appear to be better choices in terms of speed. As expected the error is larger for hierarchical clustering since it leads to less optimal cluster placement. However, as the number of clusters grows this effect tends to disappear. The variable cluster method is faster on average. However, with our current settings it also created fewer clusters (6.6 clusters created on average) and, as a consequence, has higher average error. Interestingly, the peak number of clusters created by the variable method is 22, which underlines the flexibility and adaptability of the approach.

To limit the error compared to a non-hierarchical implementation, it is preferable to create more top level clusters. For instance a 4/3 split is better than a 2/6 split for a 12 cluster configuration, altough it might be slightly slower. Hence, this choice depends on the desired time vs. error tradeoff for the application at hand.

Implementation in a commercial game

The audio clustering technique was used in the development of the commercially available computer game Test Drive Unlimited. In this car racing game, the sound of each racing vehicule is synthesized based on numerous mechanical quantities. The sound emitted by each wheel is controlled by 20 physical variables while 8 variables control the engine/transmission sounds. Four additional vari- ables control aerodynamic phenomena. These variables are used for real-time control and playback of a set of pre-recorded sound samples. All sound sources are then rendered in 5.1 or 7.1 surround sound. For implementation on the XBOX360, Eden Games adopted a variant of the recursive variable budget technique described above. In particular, a budget of 8 clusters was used at each recursion level. If the quality criterion is not met for this budget, a local clustering step is applied in each cluster. However, the local nature of clustering resulted in audible artifacts from one frame to the next, because of sources moving from one cluster to another. To resolve this problem, sources are ordered by perceptual priority, and the most important ones will prefer to be clustered with the cluster of the previous frame, effecting a form of temporal coherence.

Despite this improvement, extreme cases still presented some difficulty, notably the case of a car crashing into an obstacle. In this case, the physics engine generates numerous short-lasting sound sources in the immediate neighbourhood of the vehicle. Temporal coherence is thus useless in this context. The solution to this issue is to apply a separate clustering step to the sources generated by physics events; this results in more clusters overall, but resolves the problems of quality.

A snapshot of Test Drive Unlimited with a visualisation of the sound source clusters superimposed in red, is shown in Figure 4.

Scalable perceptual premixing

In order to apply the final spatial audio processing to each cluster (see Figure 2), the signals corresponding to each source must first be premixed. The premixing stage can be as simple as summingup the signals of the different sources in each cluster. In addition, a number of audio effects usually have to be applied on a persource basis. Such effects include filtering (e.g., distance, occlusions), pitch-shifting (e.g., Doppler effect) or other studio-like effects [Zölzer 2002]. Hence, when large numbers of sound sources are still present in the scene after auditory culling (masking) or for systems with limited processing power, the cost of this stage can quickly become the bottleneck of the audio rendering pipeline.

In this section, we propose a progressive signal processing technique that can be used to implement scalable per-source processing. Our work is based on the approach of [START_REF] Tsingos | Scalable perceptual mixing and filtering of audio signals using an augmented spectral representation[END_REF]] which we briefly summarize in Figure 5. This approach uses a specific time-frequency representation of audio signals. At each time-frame (typically 1024 samples at 44.1KHz), the complex-valued coefficients of a short-time Fourier transform (STFT) are precomputed and stored in decreasing modulus order. In real-time during the simulation, the algorithm prioritizes the signals and allocates to each source a number of coefficients to process, so that a predefined budget of operations is In [START_REF] Tsingos | Scalable perceptual mixing and filtering of audio signals using an augmented spectral representation[END_REF]], the integral of these curves is used to measure the coding efficiency for each frame of input signal.

respected. In [START_REF] Tsingos | Scalable perceptual mixing and filtering of audio signals using an augmented spectral representation[END_REF]], this importance sampling stage is driven by the energy of each source at each time-frame and used to determine the cut-off point in the list of STFT coefficients. However, using only energy for importance sampling leads to suboptimal results since it does not account for the sparseness of the representation obtained for each signal. For instance, a loud tonal signal might require fewer coefficients than a weaker noisier signal for transparent reconstruction (Figure 6). An additional weighting term measuring the efficiency of coding for each frame of input signal was thus proposed for budget allocation.

In the following, we introduce an improved budget allocation strategy. We also present the results of a perceptual quality study aimed at evaluating our novel technique and several possible importance metrics used for prioritizing source signals.

Improved budget allocation

The pinnacle value. Contrary to [START_REF] Tsingos | Scalable perceptual mixing and filtering of audio signals using an augmented spectral representation[END_REF]], our improved budget allocation pre-computes the explicit number of STFT coefficients necessary to transparently reconstruct the original signal. This value, that we call pinnacle, is pre-computed for each timeframe of input audio data and stored together with the progressive STFT representation. To compute the pinnacle value, we first sort the STFT coefficients by decreasing modulus order. The energy of each coefficient is integrated until a threshold of at least 99.5% of the total energy of the frame is reached and the number of corresponding coefficients is greater than (1tonality)N/2, where N is the total number of complex Fourier coefficients in the frame and tonality ∈ [0, 1] is the tonality index of the frame [START_REF] Painter | Perceptual coding of digital audio[END_REF][START_REF] Kurniawati | The significance of tonality index and nonlinear psychoacoustics models for masking threshold estimation[END_REF]. This index is close to 1 for tonal signals and drops to 0 for noisier signals.

Iterative importance sampling. We assume a constant number of arithmetic operations will be required for each complex STFT coefficient. Hence, fitting a budget number of operations for our pipeline at each processing frame directly amounts to selecting a budget number of coefficients for each frame of input sound signal. We can take advantage of pre-storing our FFT in decreasing energy order by directly processing the n i first coefficients for each input signal s i , so that the sum of all n i s does not exceed our total budget N. To determine the n i s, we first assign an importance value to each signal. This importance value can typically be the energy or loudness of the signal as proposed in [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF][START_REF] Tsingos | Scalable perceptual mixing and filtering of audio signals using an augmented spectral representation[END_REF]. In this work, we also experimented with a saliency value derived from the model recently proposed in [START_REF] Kayser | Mechanisms for allocating auditory attention: An auditory saliency map[END_REF]]. This model is very similar to the visual saliency maps [START_REF] Itti | A model of saliency-based visual attention for rapid scene analysis[END_REF]] but it is applied on a time-frequency domain representation of audio signals. In our case, after computing the auditory saliency map, we integrated saliency values over a small number of frequency subbands (we typically use 4 on a non-linear frequency scale).

Then, every input signal gets assigned a number of bins n i relative to its relative importance as follows:

n i = I i / ∑ i I i • targetCoeffs (1)
where I i is the importance of the source i. Ideally, n i should be smaller than the signal's pinnacle value to avoid suboptimal budget allocation as can be the case with the approach of [START_REF] Tsingos | Scalable perceptual mixing and filtering of audio signals using an augmented spectral representation[END_REF]].

To avoid such situations, all remaining coefficients above pinnacle threshold are re-assigned to the remaining signals, that do not already satisfy the pinnacle value criterion. This allocation is again relative to the importance values of the signals:

n i + = I i / ∑ i I i • extraCoeffs (2)
The relative importance of each remaining signal is updated according to the reallocation of coefficients. If the budget is high enough, the process is iterated until all signals satisfy the pinnacle criteria or receive a maximal number of coefficients.

Quality evaluation study

To evaluate possible importance metrics and evaluate our pinnaclebased algorithm we conducted a quality evaluation study.

Experimental procedure. Seven subjects aged from 23 to 40 and reporting normal hearing volunteered for five different test sessions.

For each session, we used a Multiple Stimuli with Hidden Reference and Anchors procedure (MUSHRA, ITU-R BS.1534) [START_REF] Stoll | EBU subjective listening tests on internet audio codecs[END_REF]EBU 2003;International Telecom. Union 2001-2003]. Subjects were asked to simultaneously rank a total of 15 stimuli relative to a reference stimulus on a continuous 0 to 100 quality scale. The highest score corresponds to a signal indistinguishable from the reference. The reference stimuli were different mixtures of ambient, music and speech signals. In all cases, 12 of the 15 test-stimuli consisted of degraded versions of the mixture computed using our progressive mixing algorithm at various budgets (5%, 10% and 25% for music and ambient and 2%, 5% and 10% for speech), using our pinnacle-based technique, not using the pinnacle and using either loudness or saliency-based prioritization. In all cases, our processing is done using 32-bit floating point arithmetic and reconstructs signals at 44.1KHz. Two anchor stimuli, providing reference degradations, were also included. In our case, we chose a downsampled 16KHz/16-bit version of the mixture and a mp3-encoded version at 64Kbps. Finally, a hidden reference was also included. Stimuli were presented over headphones. Subjects could switch between stimuli at any point while listening. They could also define looping regions to concentrate on specific parts of the stimuli. A volume adjustment slider was provided so that subjects could select a comfortable listening level.

Results. Our study confirmed that the scalable processing approach is capable of generating high quality results using 25% of the original audio data and produces acceptable results with budgets as low as 10%. In the case of speech signals, for which the STFT representation is sparser, the algorithm could generate an acceptable mixture (avg. score 56/100) with only 2% of the original coefficients. As can be seen on Figure 7 (left), our approach yields significantly better results than a 16KHz reference signal (16KHz processing would correspond to a 30% reduction of data compared to our 44.1KHz processing). At 25% budget (or 10% in the case of speech), we obtain results comparable or better than the 64Kbps mp3-encoded reference. We performed an analysis of variance (ANOVA) [START_REF] Howell | Statistical methods for psychology[END_REF]] on the results. As expected, the analysis confirmed a significant effect of the computing budget (p<0.01) on the quality of the resulting signal (Figure 7 right). We can see that the variation of perceived qualty is not generally a linear function of budget, especially for more tonal signals (music, speech) which can be efficiently encoded until a sharp breakdown point is reached. Interaction between budget and importance metric was found to be significant (0.05<p<0.01). At low or high budgets, the two metrics lead to very similar results. However, for intermediate budgets, loudness-based prioritization improved perceived quality relative to the saliency-based alternative. Similarly, using our new pinnacle algorithm also leads to a slight improvement in the results, especially for cases where both tonal and noisier signals are present. Noisier stationary sounds, which do not contain strong spectral features, usually receive a lower saliency value although they might contain significant energy and require more coefficients to be properly reconstructed. We believe this might explain why saliency-based prioritization led to lower perceived quality in some cases.

Cross-modal effects for sound scene simplification

In the preceding sections, we have improved different aspects of audio rendering for complex scenes, without consideration for the corresponding visuals. Intuitively, it would seem that such interaction of visual and audio rendering should be taken into account, and play a role in the choice of metrics used in the audio clustering algorithm. A first attempt was presented in [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF]], but was inconclusive presumably due to the difficulties with speech stimuli, which are generally considered to be a special case.

Research in ventriloquism (see Section 2), could imply that we should be more tolerant to localization errors for sound rendering when we have accompanying visuals. If this were the case, we could change the weighting terms in the clustering algorithm to create fewer clusters for sound sources in the visible frustum. However, a counter argument would be that in the presence of visuals, we are more sensitive to localization, and we should favour more clusters in the viewing frustum.

% 1 0 % 2 5 % 5 % 1 0 % 2 5 % 5 % 1 0 % 2 5 % 5 % 1 0 % 2 5 % saliency saliency+pinnacle 5 % 1 0 % 2 5 % 5 % 1 0 % 2 5 % 5 % 1 0 % 2 5 % 5 % 1 0 % 2 5 % 2 % 5 % 1 0 % 2 % 5 % 1 0 % 2 % 5 % 1 0 % 2 % 5 % 1 0 % m p 3
Our goal was to see whether we could provide some insight into this question with a pilot perceptual study. The next step was to develop and test an improved audio clustering algorithm based on the indications obtained experimentally.

Experimental setup and methodology

We chose the following experimental setup to provide some insight on whether we need more clusters in the visible frustum or not.

The subjects are presented with a scene composed of 10 animatedbut not moving -objects emitting "ecologically valid" sounds, i.e., a moo-ing sound for the cow, a helicopter sound, etc. (Figure 8; also see and hear accompanying video).

We have two main conditions: audio only (i.e., no visuals) (condition A) and audio-visual (AV). Within each main condition we have a control condition, in which sources follow a uniform angular distribution, and the condition we test, where the proportion of clusters in the visible frustum and outside the visible frustum is varied.

We ran our test with 6 subjects (male, aged 23-45, with normal or corrected to normal vision, reporting normal hearing). All were naive about the experiment. Five of them had no experience in audio. Prior to the test, subjects were familiarized with isolated sound effects and their corresponding visual representation.

The subject stands 1 meter away from a 136 x 102 cm screen (Barco Baron Workbench), with an optical headtracking device (ART) and active stereo glasses (see the video). The field of view in this large screen experiment is approximately 70 • .

Headphones are used for audio output and our system uses binaural rendering [START_REF] Blauert | Spatial Hearing : The Psychophysics of Human Sound Localization[END_REF][START_REF] Møller | Fundamentals of binaural technology[END_REF]] using the LISTEN HRTF database (http://recherche.ircam.fr/equipes/salles/listen/). Our subjects were not part of the database. Hence, they performed a "point and click" pre-test to select the best HRTFs over a subset of 6 HRTF selected to be "most representative" similar to [START_REF] Sarlat | Ventriloquism aftereffects occur in the rear hemisphere[END_REF]].

The marks attributed for the test are given with a joystick.

The A condition was presented first for three candidates, while AV condition was presented first for the other three. No significant effect of ordering was observed.

To achieve the desired effect, objects are placed in a circle around the observer; 5 are placed in the viewing frustum and 5 outside.

For both control and main conditions, four configurations are used We used the ITU-recommended triple stimulus, double blind with hidden reference technique [START_REF] And | Methods for quality assessment of low bit-rate audio codecs[END_REF][START_REF] Itu-R | Methods for subjective assessment of small impairments in audio systems including multichannel sound systems[END_REF]: 2 versions of the scene were presented ("A" and "B") and a given reference scene which corresponds to unclustered sound rendering. One of the 2 scenes was always the same as the reference (a hidden reference) and the other one corresponds to one of our clustering configurations. For each condition, the subject was presented with a screen with three rectangles ("A", "R" and "B"), shown in Fig. 8. The subjects were given a gamepad, and were instructed to switch between "A", "B" and "R" using three buttons on the pad, which were highlighted depending on the version being rendered. The subjects were asked to compare the quality of the approximations ("A" or "B") compared to the reference. They were asked to perform a "quality judgment paying particular attention to the localization of sounds" for the 2 test scenes, and instructed to attribute one of 4 levels of evaluation "No difference", "Slightly different", "Different" and "Clearly different" from the reference, which were indicated in rectangles next to the letter indicating the scene version (see Fig. 8 and accompanying video).

Analysis and results

We attributed a mark for each evaluation (from 0 to 3). As suggested by this ITU-R standard protocol, we only kept the difference between the test sample and the hidden reference. We also normal- ized the data by dividing each mark by the mean score of the user (the average of all marks of the candidate over all his tests).

There was no significant difference between the A and AV conditions regarding the respective scores of each cluster configuration. However, the difference of quality ratings between configurations was not similar in the two conditions. In condition A, 1/4 and 2/3 configurations lead to a similar quality evaluation (see Figure 9). In condition AV, the best quality is perceived in configuration 2/3. While 2/3 and 1/4 configurations are not perceived differently in condition A (Wilcoxon test, N=90, T=640.5, Z=0.21, p=0,83), the quality scores of 2/3 configuration are higher than those of 1/4 configuration in condition AV (Wilcoxon test, N=90, T=306.5, Z=2.56, p=0.01).

Overall, we consider the above results as a significant indication that, when we use the audio clustering algorithm with visual representation of the sound sources, it is better to have two clusters in the view frustrum, compared to a uniform angular distribution. This is indicated by the results for the 2/3 configuration, which is statistically different from all the other configurations in the AV condition. We expect this effect to be particularly true for scenes where there are visible sound sources in the periphery of the view frustum.

An audio-visual metric for clustering

Given the above observation, we developed a new weight in the clustering metric which encourages more clusters in the view frustum. We modify the cost-function of the clustering algorithm by adding the following weigthing term:

1 + α cos θ s -cos θ f 1 -cos θ f n (3)
where θ s is the angle between the view direction and the direction of the sound source relative to the observer, θ f is the angular half-width of the view frustum and α controls the amplitude and n decay-rate of this visual improvement factor.

Implementation and Results

We ran tests on two scenes, one is a variant of the highway scene from [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF]], and another is a city scene. Both scenes are shown in Figure 1. In both cases, we used a platform with dual-core 3GHz Xeon processor and NVidia 7950GX2 graphics accelerator; our system is built using the Ogre3D graphics engine and our custom audio library. Audio was processed at 44.1KHz using 1024-sample-long time-frames (i.e., 23 msec.). The following tests were performed with masking disabled to get a stable performance measure.

The highway scene contains 1004 sound sources, which are car engine and car stereo music sounds, cow "mooing" sound, train sounds, and water sounds in a stream. We found that a scalable premix budget of 25% is satisfactory in terms of audio quality (please hear and see the accompanying video). Comparing to the reference, we found that our entire perceptual processing pipeline resulted in an average signal-to-interference ratio of 18dB (min=5dB, max=30dB) for the sequence presented in the video. In this scene, clustering took 4.7 msec. per frame. Premixing was very simple and only included distance attenuation and accumulating source signals for each cluster. Premixing using 100% of the original audio data took 6 msec. Using our scalable processing with 25% budget we bring this cost down to 1.83 msec.

The street scene contains 1800 sound sources, which are footstep sounds and voices for the people in the crowd, car engine sounds, car radio sounds, bird sounds and sirens. Again, a scalable premix budget of 15% is satisfactory for this scene. Overall, we measured an average signal-to-interference ratio of 17dB (min=4dB, max=34dB) for the sequence presented in the video. In this scene, clustering took 5.46 msec. per frame while premixing using 100% of the original audio data took 6.84 msec. Using our scalable processing with 15% budget we bring the cost of premixing down to 2.17 msec.

In the commercial game Test Drive Unlimited, the average number of simultaneous sound sources is 130. A typical "player car" can generate up to 75 sound sources, while "AI" cars have a simplified model of maximum 42 sources. A maximum of 32 clusters were used in the game, although in a vast majority of cases 10 clusters are sufficient. Overall, the clustering approach discussed in Section 3.4 results in a reduction of 50-60% of CPU usage for the audio engine, which is freed for other application tasks, such as AI, gameplay etc.

To test the new audio-visual criterion, we constructed a variant of the street scene and an appropriate path, in which the positive effect of this criterion is clearly audible. For this test, we used α = 10 and n = 1.5, which proved to be satisfactory. The scene used can be seen and heard in the video; the user follows a path in the scene (see accompanying video) and stops in a given location in the scene.

We have 132 sources in the scene and target budget of 8 clusters. By switching between the reference, and the approximations with and without the audio-visual metric, we can clearly hear the improvement when more clusters are used in the view frustum. In particular, the car on the right has a siren whose sound is audibly displaced towards the centre with the audio-only metric.

In this paper, we proposed a fast hierarchical clustering approach that can handle large numbers of sources and clusters. We also proposed a progressive processing pipeline for per-source effects (i.e., the premixing) that allows us to choose the best performance/quality ratio depending on the application and hardware constraints. Combined with auditory masking evaluation, these new algorithms allow for real-time rendering of thousands of mobile sound sources while finely controlling processing load vs. quality. In fact, while designing the test examples for the paper, the major problem we faced was authoring environments complex enough and most of the performance limitations actually came from the graphics engine. However, with next-generation games making increased used of procedurally-generated audio (e.g., based on physics engines), scenes with thousands of sound events to process are likely to become common in the near future.

In our examples we only used simple per-source processing. However, in most gaming applications each source is likely to be processed with a chain of various effects (e.g., occlusion filters, echoes, re-timing, pitchshifting, etc.) that would make our scalable approach even more attractive.

We also presented our perceptual studies for clustering and scalable premixing. A cross-modal perceptual study aimed at determining possible influence of the visuals on the required quality for audio clustering. Although one could expect ventriloquism to allow for rendering simplifications for visible sources, our study suggest that more clusters might actually be required in this case. A possible explanation for this is that, in a complex scene, clustering is likely to simplify auditory localization cues beyond common ventriloquism thresholds. As a consequence, we introduced a new metric to augment the importance of sources inside the view frustum.

We demonstrated an example where, with a large number of sound sources outside the view frustum, it leads to improved results. We also performed a user-study of quality for the scalable premixing approach and showed that it leads to high quality results with budgets as low as 20 to 15% of the original input audio data. Although saliency-based importance appeared to show some limitations for our scalable processing algorithm compared to loudness, it might still be useful for prioritizing sources for clustering.

In the future, it would be interesting to experiment with auditory saliency metrics to drive clustering and evaluate our algorithms on various combinations of A/V displays (e.g., 5.1 surround or WFS setups). Also, the influence of ventriloquism on these algorithms merits further study. We also believe that authoring is now becoming a fundamental problem. Adapting our algorithms to handle combinations of sample-based and procedurally synthesized sounds seems a promising area of future research.

Figure 2 :

 2 Figure2: Overview of our overall sound rendering pipeline. In particular, we introduce an improved hierarchical sound source clustering that better handles visible sources and a premixing technique for progressive per-source processing.

Figure 4 :

 4 Figure 4: Sound source clustering in the Test Drive Unlimited engine. Red wireframe spheres are clusters. c Eden Games-ATARI 2006.

Figure 5 :Figure 6 :

 56 Figure 5: Overview of our progressive perceptual premixing.

Figure 7 :

 7 Figure 7: Left: Average MUSHRA scores and 95% confidence intervals for our progressive processing tests. Right: Average MUSHRA scores and 95% confidence intervals as a function of budget. Note how perceived quality does not vary linearly with the processing budget and also varies depending on the type (i.e., sparseness) of the sounds.

Figure 8 :

 8 Figure 8: An example view of the experimental setup for the audiovisual pilot user study. randomly, by varying the proportion of clusters. Condition 1/4 has one cluster in the view frustum and 4 outside, 2/3, has 2 in the view frustum and 3 outside, etc. A uniform distribution of clusters corresponds to condition 1/4, with only 1 cluster in the frustum. Each condition is repeated 15 times with randomized object positions; these repetitions are randomized to avoid ordering effects.

Figure 9 :

 9 Figure9: Mean values and 95% confidence intervals (N=6) in A and AV conditions as a function of the number of clusters inside/outside the view frustrum. For AV, the 2/3 configuration gives the best quality scores, which is not the case in the A condition. The "*" underlines that quality judgements in 1/4 and 2/3 cluster configurations for AV are significantly different (p<0.05), while the same comparison is non significant (n.s.) in the A condition.

Figure 10 :

 10 Figure 10: Left: the clusters without the audio-visual metric. Right: the clusters with our new metric. We clearly see that the new metric separates the sources appropriately.

Acknowledgements

This research was funded by the EU IST FET Open project IST-014891-2 CROSSMOD (http://www.crossmod.org). We thank Autodesk for the donation of Maya, P. Richard and A. Olivier-Mangon for modelling/animation and G. Lemaitre for help with ANOVA.


Ares Lagae
email: ares.lagae@cs.kuleuven.be

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

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

Philip Dutré
email: philip.dutre@cs.kuleuven.be

Procedural Noise using Sparse Gabor Convolution

Keywords: CR Categories: I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism-Color, shading, shadowing, and texture noise, procedural texture, rendering, shading

Figure 1: (Left) We present a procedural noise that offers accurate spectral control. The user can interactively manipulate the power spectrum. (Middle) We apply the noise to a surface without the need for texture coordinates, and provide high-quality anisotropic filtering. Thanks to increased expressiveness of the noise, a simple colormap is enough to produce visually interesting textures. (Right) Since our surface noise does not require a texture parameterization, the surface can evolve dynamically and even sustain topology changes.

Introduction

Visual complexity is a key ingredient of compelling computer generated imagery. Randomness, or noise, was identified early on as a useful tool for generating that visual complexity. Since its introduction by [START_REF] Perlin | An image synthesizer[END_REF], noise has become an essential modeling tool in computer graphics. It is mainly used in procedural modeling and texturing [START_REF] Ebert | Texturing and Modeling: A Procedural Approach[END_REF], but also in other areas of computer graphics, such as animation and simulation [START_REF] Bridson | Curl-noise for procedural fluid flow[END_REF]]. Noise is used in many different contexts, and should therefore be as versatile as possible. This is witnessed by the procedural nature of noise, which is probably one of its most significant advantages: it is compact, described by only a few parameters, yet it can be quickly evaluated at any point in space. This makes it very suitable for rendering. The random nature of noise means that it is best described in terms of spectral content or energy in each frequency band. Controlling the appearance of noise, e.g., for modeling, therefore requires spectral control. Noise is mainly used for adding details to surfaces. This is typically achieved by traditional texture mapping using a two-dimensional noise, or using a solid noise. Solid noise is not subject to artifacts, such as distortions and seams, and is setup free. This means that surfaces can be textured without preprocessing, such as a texture parameterization, regardless of complexity. Setup-free surface noise is not only simple and convenient, but also essential, when surfaces are implicit, point sampled or dynamic. High-quality rendering of noise requires anisotropic filtering to avoid artifacts. This requires noise to be anisotropic. Of course, noise should also be fast to evaluate. From the above, it is clear that we want a procedural noise with accurate spectral control, providing setup-free surface texturing. In addition it should be anisotropic and allow high-quality anisotropic filtering. Many previous noises have a subset of these properties (Sec. 1.1); none of them however provides them all. In this paper we introduce a noise that does have them all:

• We introduce a new procedural noise with accurate spectral control using Gabor kernels, by extending sparse convolution noise [START_REF] Lewis | Algorithms for solid noise synthesis[END_REF]]. Our noise has a memory footprint of only a few bytes, is nonperiodic and is anisotropic. • We introduce setup-free surface noise with high-quality anisotropic filtering, a method for mapping noise onto a surface that does not require a texture parameterization. Surface noise is complementary to solid noise: it maintains the aspect of a two-dimensional noise pattern along the object. Solid noise is supported as well.

• We demonstrate a powerful interactive design tool for noises and procedural textures, based on the intuitive properties of our noise (frequency, orientation and bandwidth). Our new procedural noise is illustrated in Fig. 1 using our interactive tool for noise design. First, we create an anisotropic noise. The inset displays the widget for spectral control and the main image displays the corresponding noise. Next, we add an isotropic noise. Then, we create a procedural texture by combining the noise with a color map, and we render a surface with the procedural texture using anisotropic filtering. Finally, we apply the noise to an impicit surface whose topology can change interactively.

Related Work

We group the desirable properties of noise into five categories, and discuss related work as a function of these properties.

Procedural Perlin noise [START_REF] Perlin | An image synthesizer[END_REF]] is likely the most popular noise in computer graphics. Key to the success of Perlin noise is that it is procedural. According to the advantages of a procedural representation identified by [START_REF] Ebert | Texturing and Modeling: A Procedural Approach[END_REF], noise should have compact storage requirements, should not be based on discretely sampled data, should be nonperiodic, and should be intuitively parameterized. These properties imply that noise should be evaluated on the fly rather than stored.

Spectral Control

Noise is a modeling tool, and therefore controlling the appearance of noise is of key importance. The power spectrum of the noise, which describes the contribution of each frequency band, is a powerful and natural framework for controlling it [START_REF] Perlin | An image synthesizer[END_REF][START_REF] Lewis | Algorithms for solid noise synthesis[END_REF][START_REF] Perlin | Hypertexture. In Computer Graphics[END_REF]]. Perlin noise achieves spectral control by using a weighted sum of band-limited octaves of noise. However, [START_REF] Cook | Wavelet noise[END_REF] showed that Perlin noise is only approximately band limited, and is therefore subject to aliasing and detail loss. Although Perlin repeatedly improved his noise [START_REF] Perlin | Improving noise[END_REF][START_REF] Olano | Real-time shading languages[END_REF], this problem was not addressed. Therefore, most recent work focuses on constructing band-limited noise [START_REF] Cook | Wavelet noise[END_REF][START_REF] Kensler | Better gradient noise[END_REF]]. However, band-limited noise is not a goal by itself, it is only a means for controlling the power spectrum of the noise. Moreover, a weighted sum of octaves of noise does not provide the desired spectral control. This was already recognized by [START_REF] Lewis | Algorithms for solid noise synthesis[END_REF], who introduced solid procedural noises with improved control over the power spectrum.

Surface Noise

Noise is commonly used for texturing surfaces. Traditional texturing requires a surface parameterization, which usually introduces distortions and discontinuities. This means that surface noise cannot always be obtained by simply mapping a twodimensional noise texture onto a surface [START_REF] Goldberg | Anisotropic noise[END_REF]. [START_REF] Perlin | An image synthesizer[END_REF] and [START_REF] Peachy | Solid texturing of complex surfaces[END_REF] introduced solid texturing, an attractive alternative for traditional texturing not subject to these problems. Solid texturing does not require a surface parameterization and is setup free. Therefore, noise on a surface is typically obtained using solid noise, even when not modeling a solid material. However, [START_REF] Cook | Wavelet noise[END_REF] showed that mapping bandlimited solid noise onto a surface does not result in band-limited surface noise. This means that surface noise also can not be obtained by simply mapping solid noise onto a surface. Moreover, solid noise and surface noise have a distinct appearance. Noise should therefore differentiate between two-dimensional noise, surface noise and solid noise, and, similar to solid noise, surface noise should be setup free.

Anisotropy High-quality rendering requires anisotropic filtering to avoid aliasing. Band-limited isotropic noise can be isotropically filtered using frequency clamping, that is by disabling octaves in the sum of weighted octaves that would result in aliasing [START_REF] Cook | Wavelet noise[END_REF]. [START_REF] Hart | Antialiased parameterized solid texturing simplified for consumerlevel hardware implementation[END_REF] addressed isotropic filtering of procedural solid textures by prefiltering the color lookup table. However, [START_REF] Goldberg | Anisotropic noise[END_REF] showed that anisotropic filtering requires anisotropic noise. Anisotropic noise is also useful to model anisotropic phenomena.

Fast to Evaluate

Noise was introduced in the context of off-line rendering, but has recently become more accessible to interactive applications [START_REF] Hart | Perlin noise pixel shaders[END_REF][START_REF] Olano | Modified noise for evaluation on graphics hardware[END_REF][START_REF] Frisvad | Fast high-quality noise[END_REF][START_REF] Goldberg | Anisotropic noise[END_REF]. Noise is used in many different contexts, ranging from games to production rendering. Therefore, noise should be interactive and enable a speed vs. quality trade-off.

None of the existing noises has all of these properties, which is illustrated in Tab. 1 (Sec. 7). For example, wavelet noise [START_REF] Cook | Wavelet noise[END_REF] and the noise of [START_REF] Kensler | Better gradient noise[END_REF] are band limited and support setup-free surface noise, but do not support anisotropic noise or anisotropic filtering, and the noise of [START_REF] Goldberg | Anisotropic noise[END_REF] supports anisotropic noise and anisotropic filtering, but does not support solid noise or setup-free surface noise.

In the following sections, we first explain how the Gabor kernel combined with sparse convolution produces band-limited anisotropic noise with accurate spectral control (Sec. 2). We then generalize to more complex spectra using a random sampling of the parameters of the Gabor kernels during sparse convolution (Sec. 3). We next discuss procedural, on-the-fly noise evaluation (Sec. 5), and detail our anisotropically filtered setup-free surface noise. Results and comparisons are given in Sec. 6 and Sec. 7.

Band-Limited Anisotropic Noise

In this section we present our procedural band-limited anisotropic noise. We review sparse convolution noise (Sec. 2.1), generalize sparse convolution noise as a random pulse process (Sec. 2.2), show that our choice of Gabor kernel as a pulse is well motivated (Sec. 2.3), and formulate our anisotropic noise as a random pulse process using a Gabor kernel (Sec. 2.4). We assume that the reader is familiar with Fourier analysis (e.g., [START_REF] Bracewell | The Fourier Transform and its Applications[END_REF]).

Sparse Convolution Noise

In 1989, Lewis introduced sparse convolution noise, a procedural noise that offers improved control over the power spectrum. Lewis defines sparse convolution noise N as a convolution of a kernel h and a Poisson impulse process

N (x, y) = » h * X i wiδ (x i ,y i ) - (x, y) , (1)
where * denotes convolution, δ is the impulse and δ (x i ,y i ) (x, y) = δ (x -xi, y -yi). The Poisson impulse process consists of impulses of uncorrelated intensity {wi} at uncorrelated locations {(xi, yi)}. Lewis calls this process sparse white noise, because it consists of only a few scattered impulses and has a constant power spectrum. The power spectrum of sparse convolution noise is that of the kernel scaled by a constant, which follows from the Convolution Theorem. Lewis used the radially symmetric smooth cosine kernel

h(r) = 1/2 + 1/2 cos (πr) (|r| < 1). (2)
Lewis procedurally evaluates sparse convolution noise by introducing a grid, and generating the positions and weights of the kernels in each cell on the fly. The grid reduces the evaluation of the noise to the grid cells close to the point of evaluation. An example of sparse convolution noise is shown in Fig. 8(b).

The Random Pulse Process

Sparse convolution noise is a random pulse process in which the pulse is the radially symmetric smooth cosine kernel. The random pulse process Y is defined as a sum of randomly weighted and positioned pulses

Y (x) = X i wih (x -xi) , (3)
where h is the pulse, the random locations {xi} are governed by a Poisson distribution with mean λ, called the impulse density, and the weights {wi} are realizations of a random variable W . In this work, we assume that the random variable W has zero mean. Note that the location of the impulses follows a uniform random distribution, and therefore, the number of impulses per unit area, or impulse density λ, follows a Poisson distribution. Poisson processes and shot noise, the family of stochastic processes that the random pulse process belongs to, are well known in statistics [Papoulis and Pillai 2002, 10.2;van Etten 2005, 8].

The random pulse process has zero mean, and the variance σ 2 Y of the process is

σ 2 Y = λE h W 2 i Z ∞ -∞ h 2 (x) dx, (4)
where E denotes expectation value. The power spectrum of the process is

SY Y (f ) = λE h W 2 i |H (f )| 2 , ( 5
)
where H is the Fourier transform of the pulse h. The total power equals σ 2 Y , which follows from Rayleigh's Theorem. The amplitude distribution of shot noise tends to a normal distribution as the impulse density λ increases [START_REF] Papoulis | High density shot noise and Gaussianity[END_REF]]. Therefore, the amplitude distribution of the process can be approximated by a normal distribution with zero mean and variance σ 2 Y .

The Gabor Kernel

The key to accurate control over the power spectrum of the random pulse process is the choice of an appropriate pulse. Our main insight is that the pulse should be parameterized and have compact support in the spatial domain to enable efficient procedural evaluation, and also have compact support in the frequency domain to enable precise control over the power spectrum. We therefore chose the Gabor kernel [START_REF] Gabor | Theory of communication[END_REF]] which has all of these properties. In some sense, this is the theoretically optimal choice of pulse in this context, since Gabor showed that the kernel has the smallest joint uncertainty in both domains. The Gabor kernel is a multiplication of a Gaussian envelope and a harmonic (Fig. 2(a)-(d)). We use a two-dimensional real Gabor kernel of the cosine type, parameterized by magnitude, frequency, and width. The Gabor kernel g is

g (x, y) = Ke -πa 2 " x 2 +y 2 " cos [2πF0 (x cos ω0 + y sin ω0)] , (6)
where K and a are the magnitude and width of the Gaussian envelope, and (F0, ω0) is the frequency of the harmonic in polar coordinates. F0 and ω0 are the magnitude and the orientation of the frequency. The Fourier transform of the Gabor kernel G is

G (fx, fy) = K 2a 2  e -π a 2 h (fx -F 0 cos ω 0 ) 2 +(fy -F 0 sin ω 0) 2 i +e -π a 2 h (fx +F 0 cos ω 0 ) 2 +(fy +F 0 sin ω 0) 2 iff , (7)
where (F0 cos ω0, F0 sin ω0) is the frequency of the harmonic in Cartesian coordinates. The Fourier transform consists of two identical Gaussians, one located at the frequency of the harmonic, and its symmetric counterpart (Fig. 2(e)-(f)), which follows from the Convolution Theorem.

The parameters of the Gabor kernel have an intuitive meaning in both domains. The frequency (F0, ω0) of the harmonic corresponds to the location of the Gaussian in the frequency domain, and the width a of the Gaussian envelope corresponds to the width of the Gaussian in the frequency domain. The frequency (F0, ω0) can therefore be interpreted as the principal frequency, and the width a as the bandwidth, the range of frequencies around the principal frequency. The full width at half maximum, a parameter commonly used to describe the width of a function, of the Gaussian envelope and the Gaussian in the frequency domain is approximately 1/a (Fig. 2(a)) and a (Fig. 2(e)).

Gabor kernels were introduced in 1946 by Gabor to study communication theory. Gabor kernels are frequently used in computer vision, e.g., for texture analysis and synthesis [START_REF] Navarro | Robust method for texture synthesis-by-analysis based on a multiscale Gabor scheme[END_REF], as well as in perception.

Band-Limited Anisotropic Noise

We can now define our new band-limited anisotropic noise N as a random pulse process, with the Gabor kernel g as a pulse

N (x, y) = X i wig (x -xi, y -yi) . (8)
We derive the properties of this band-limited anisotropic noise from the properties of the random pulse process and the Gabor kernel.

The noise has zero mean, and the variance of the noise is (Eq. ( 4))

σ 2 N = λE h W 2 i Z ∞ -∞ Z ∞ -∞ g 2 (x, y) dx dy. (9)
The power spectrum of the noise is (Eq. 5)

SNN (fx, fy) = λE h W 2 i |G (fx, fy)| 2 . ( 10
)
The intensity distribution of the noise can be approximated by a normal distribution with zero mean and variance σ 2 N . The power spectrum of band-limited anisotropic noise is the power spectrum of the Gabor kernel scaled by the constant λE ˆW 2 ˜. This means that we can control the power spectrum of the noise using the intuitive parameters of the Gabor kernel. The magnitude K, the orientation ω0 and the magnitude F0 of the frequency, and the width a of the Gabor kernel correspond to the magnitude, orientation, principal frequency and bandwidth of the noise. An example of band-limited anisotropic noise is shown in Fig. 3. The accompanying video illustrates how the individual Gabor kernels are combined to form the noise.

Noise with On-The-Fly Spectral Control

We achieve spectral control by using a different Gabor kernel for each impulse, with parameters randomly sampled from a parametric description of the desired power spectrum. This is a very powerful way to generalize the noise defined by Eq. ( 8), allowing us to define band-limited isotropic noise (Sec. 3.1) and noise with controllable band-limits (Sec. 3.2). Using our method, it is also easy to develop a system for interactive noise design (Sec. 3.3).

Band-Limited Isotropic Noise

We define our new band-limited isotropic noise N as a random pulse process

N (x, y) = X i wig (x -xi, y -yi; ω0,i) , (11)
where the pulse is a Gabor kernel with a random frequency orientation, and the frequency orientations {ω0,i} are realizations of a random variable with a continuous uniform distribution on the interval [0, 2π). Similar to band-limited anisotropic noise, we derive the properties of this band-limited isotropic noise from the properties of the random pulse process and the Gabor kernel. The power spectrum of the noise, obtained by integrating the pulse over all possible orientations [van Wijk 1991], is

SNN (fx, fy) = λE h W 2 i 1 2π Z 2π 0 |G(fx, fy; ω0,i)| 2 dω0. (12)
The total power of the noise is equal to the total power of bandlimited anisotropic noise. Therefore, the variance of the noise is equal to the variance of band-limited anisotropic noise. The intensity distribution of the noise can therefore also be approximated by a normal distribution with zero mean and variance σ 2 N . The power spectrum of band-limited isotropic noise is radially symmetric, because the noise is isotropic. In terms of radial frequency f 2 r = f 2 x + f 2 y , the power spectrum is

SNN (fr) = λE h W 2 i K 2 2a 4 e -2π a 2 " f 2 r +F 2 0 " » 1 + I0 " 4πF0 a 2 fr «- , (13)
where I0 is the modified Bessel function of the first kind. By approximating the Bessel function I0 with an exponential [Abramowitz and Stegun 1964, 9.7.1], and because the region of interest of the power spectrum is the region near the principal frequency (fr ≈ F0), we can approximate the power spectrum by

SNN (fr) ≈ λE h W 2 i K 2 4 √ 2πF0a 3 e -2π a 2 (fr -F 0 ) 2 . ( 14
)
Similar to band-limited anisotropic noise, this is a Gaussian with a principal frequency of F0 and a width of a (inset in Fig. 4(b)). We control the power spectrum of band-limited isotropic noise in the same way as the power spectrum of anisotropic noise, although the orientation of the frequency ω0 is integrated out. Our bandlimited isotropic noise is the first noise that allows precise control over the principal frequency and the bandwidth of the noise. An example of band-limited isotropic noise is shown in Fig. 4. Note how a ring is formed in the frequency domain due to the integration of the orientation.

Noise with Controllable Band-Limits

We generalize band-limited anisotropic and isotropic noise to noise with controllable band-limits, which has a power spectrum that covers a specific region of frequency space.

A region of frequency space can be described in polar coordinates by an annular sector [F0,min; F0,max) × [ω0,min; ω0,max) (see Fig. 7 for examples). This region contains all frequencies with a magnitude between F0,min and F0,max, and an orientation between ω0,min and ω0,max. By randomly sampling the parameters F0 and ω0 of the Gabor kernel associated with each impulse, a noise with a power spectrum equal to this region of frequency space is obtained.

The bandwidth parameter a controls the fall-off of the transition near the edge of the annular sector.

Noise with controllable band-limits generalizes band-limited anisotropic noise (F0,min = F0,max = F0, ω0,min = ω0,max = ω0), band-limited isotropic noise (F0,min = F0,max = F0, ω0,min = 0, ω0,max = 2π), but also includes band-limited isotropic noise with a precise control over the frequency range [F0,min, F0,max) and the fall-off a of the band-limit, and non-band-limited noise (F0,min = F0,max = 0).

Interactive Noise Design

We have developed an interactive tool for noise design. The tool is based on widgets for band-limited anisotropic and isotropic noise, noise with controllable band-limits, and linear combinations of these. The widgets allow the user to manipulate the power spectrum of the noise on diagrams similar to the ones shown in Fig. 3(c) and 4(c). We have observed that this results in straightforward interaction. The best way to appreciate the interactive tool and widgets is to watch the accompanying video.

Procedural Evaluation

The procedural evaluation of our noise is similar to that of sparse convolution noise [START_REF] Lewis | Algorithms for solid noise synthesis[END_REF]] and cellular noise [Worley 1996]. Similar to Lewis (see Sec. 2.1) and Worley, we introduce a grid, and generate the properties of the Gabor kernels in each cell on-the-fly using a pseudo-random number generator. The cell size of the grid equals the radius of the Gabor kernels, which reduces the evaluation of the noise to the cell containing the point of evaluation and the direct neighboring cells. In this section we discuss these components in more detail. Pseudocode is provided in the appendix, and compilable C++ example code is provided in the auxiliary material.

Grid

In order to introduce a grid, we truncate the Gabor kernel, since it has an infinite support. We truncate the kernel where the Gaussian envelope reaches 5% of its peak value K, which corresponds to a kernel radius of roughly 1/a (dashed line in Fig. 2(a)). This introduces a small discontinuity in the noise, which in our experience does not affect the visual appearance, even when the noise derivative is used [START_REF] Perlin | Improving noise[END_REF]]. If required, this discontinuity could be alleviated by truncating at a larger kernel radius, or avoided by multiplying with a continuous window function. Note that, in contrast to the other parameters of the noise, the spatial variation of the bandwidth is restricted, because the cell size is coupled to the width of the Gabor kernel.

Pseudo-Random Number Generator

The properties of the Gabor kernels in each cell are generated on-the-fly using a pseudorandom number generator. We use the linear congruential generator

xn+1 = 3039177861 xn (mod 2 32 ), (15)
introduced by [START_REF] Borosh | Optimal multipliers for pseudo-random number generation by the linear congruential method[END_REF]. This generator is fast, and, despite its simplicity, optimal with respect to statistical independence of successive pseudo-random numbers.

Seeding Strategy To ensure consistency, the pseudo-random number generator associated with a cell always has to be initialized with the same seed. If a periodic noise with period N is required, we determine the seed for the cell with coordinates (x, y)

as seed (x, y) = ((y%N ) N ) + (x%N ) + o, (16)
which corresponds to enumerating the cells in row-major order. If a nonperiodic noise is required, we use Morton order [START_REF] Morton | A computer oriented geodetic data base and a new technique in file sequencing[END_REF]]. This seeding strategy ensures that the noise always returns the same value when evaluated at the same location. The noise is randomized by adding a global random offset o. In contrast to Lewis and Worley, we do not use a random seeding strategy. This is not required because the sequences of pseudo-random numbers produced for every seed are uncorrelated.

Cell and Kernel Properties

The number of impulses in a cell is randomly generated according to a Poisson distribution. We use the algorithm of Knuth for small means [Knuth 1997, 3.4.1]. We express the impulse density λ in expected number of impulses N per kernel area πr 2 , which corresponds to an impulse density of N/π impulses per cell. The properties associated with the Gabor kernels, such as their position and weight, are randomly generated according to the corresponding probability distributions. For the weights, we use a random variable W with a continuous uniform distribution on the interval [-1, +1]. All random numbers are generated using the properly seeded pseudo-random number generator associated with the cell.

We have implemented the procedural evaluation for the CPU and GPU. Our current GPU implementation is a straightforward mapping of the procedural evaluation to a GPU pixel shader. A faster GPU implementation could be obtained by exploiting spatial coherence using recent GPU architectures, rather than independently evaluating noise in every pixel. It might also be worthwile to investigate the use of random number generators designed for the GPU [START_REF] Tzeng | Parallel white noise generation on a GPU via cryptographic hash[END_REF]. Our noise has a memory footprint of only 32 bytes (see example code). Our procedural evaluation allows a speed vs. quality tradeoff by adapting the impulse density and by using approximate transformation methods. We typically use 100 impulses per kernel in our CPU implementation, although good results are already obtained at lower impulse densities, and 25 to 50 impulses per kernel in our GPU implementation (values used in all video examples).

We have validated our procedural CPU and GPU implementations by verifying that the power spectrum converges to the analytical power spectrum (Fig. 3 and4), and by comparing the results to those of a non-procedural CPU implementation based on frequency filtering of white noise (Fig. 8(f)-(h)).

Anisotropically Filtered Surface Noise

Our noise generalizes to arbitrary dimensions. However, many applications require noise on a surface, and high-quality rendering requires anisotropic filtering. In this section we therefore present surface noise (Sec. 5.1) that is anisotropically filtered (Sec. 5.2). [START_REF] Cook | Wavelet noise[END_REF] obtain surface noise by performing a weighted line integral of solid wavelet noise along the direction perpendicular to the surface. [START_REF] Goldberg | Anisotropic noise[END_REF] obtain surface noise by mapping two-dimensional noise onto the surface and compensating for distortion introduced by the texture parameterization. Our noise is compatible with both approaches, but also admits a direct formulation of surface noise. Similarly to [START_REF] Lefebvre | Texture sprites: Texture elements splatted on surfaces[END_REF], we locally project kernels onto the surface. We obtain surface noise at a point on a surface p with surface normal n by projecting a three-dimensional Poisson distribution on the plane determined by p and n, and evaluating our two-dimensional noise in that plane (Fig. 5(a)). Isotropic surface noise is obtained by randomly orienting the local surface frame of each Gabor kernel (Fig. 5(b)-(c)), and anisotropic surface noise by aligning the local surface frame with a vector field that guides the anisotropy (Fig. 5(d)-(e)). The two-dimensional Poisson distribution in the tangent plane with impulse density λ is obtained by projecting all points of a three-dimensional Poisson distribution with impulse density λ/2r inside the cylinder with radius r, height 2r, center p and orientation n onto the plane. The points are generated on-the-fly, similar as in Sec. 4, using a three-dimensional grid. The weight of a point is defined as one minus the distance to the plane divided by r, which avoids the generation of an additional random number. Note that this method is similar in spirit to the method of Cook and DeRose, but is more efficient because it avoids the explicit integration. Our isotropic surface noise is setup free, and is not tied to a specific geometry representation. Our anisotropic surface noise is setup free as well. We generate the vector field that guides the anisotropy procedurally by computing a local surface frame from the surface normal and a global direction, but the vector field can also be designed by the user [Zhang et al. 2007;[START_REF] Fisher | Design of tangent vector fields[END_REF]]. Our surface noise implicitly assumes that texture detail is small compared to geometric detail, a common assumption in texturing. A limitation of surface noise is that a discontinuity in the surface normal results in a discontinuity in the noise. If this behavior is not desired, then a continuous normal should be used instead (Fig. 5(f)).

Setup-Free Surface Noise

Anisotropic Filtering

Anisotropic texture filtering can be formulated as a convolution of a texture with a filter in the spatial domain, or as a multiplication in the frequency domain. We exploit the spectral control of our noise to achieve high-quality anisotropic filtering of surface noise. We use the analytic formulation of anisotropic filtering of Heckbert [1989]. The filter in image space is the Gaussian

f (x, y) = 1 σ √ 2π e -1 2σ 2 " x 2 +y 2 " , (17)
where σ is the width of the Gaussian. The corresponding frequency domain filter in texture space is the Gaussian

F " J T [fu fv] T " = e -2π 2 σ 2 [fu fv ]JJ T [fu fv ] T , (18)
where J is the Jacobian of the mapping from image to texture coordinates. The power spectrum of anisotropically filtered noise is obtained by multiplying the power spectrum of unfiltered noise with the frequency domain filter (power spectra in Fig. 6). In the frequency domain, our noise is a sum of Gaussians. The frequency domain filter is a Gaussian as well. Because Gaussians are closed under multiplication, anisotropically filtered noise is again a sum of Gaussians. This means that we can generate anisotropically filtered noise by simply adjusting the parameters of each Gabor kernel based on J and σ when evaluating the noise. We obtain the parameters of the anisotropically filtered Gabor kernel K ′ , a ′ , F ′ 0 and ω ′ 0 as follows. We express Gaussians using the notation

N (f ; µ, Σ) = e -1 2 (f -µ)Σ -1 (f -µ) T , (19)
where µ and Σ generalize the mean and standard deviation of the Gaussian, f and µ are two-dimensional vectors, and Σ is a 2 × 2 matrix. Using this notation, the frequency domain filter in texture space is (Eq. ( 18))

NF (f ; 0, ΣF ) , Σ -1 F = 4π 2 σ 2 " JJ T " , (20)
and the unfiltered Gabor kernel in the frequency domain is (Eq. ( 7))

NG (f ; µG, ΣG) , µG = (F0 cos ω0, F0 sin ω0), Σ -1 G = 2π a 2 I. (21)
The anisotropically filtered Gabor kernel in the frequency domain is the product of the frequency domain filter in texture space NF and the unfiltered Gabor kernel in the frequency domain NG

NF (f ; 0, ΣF ) NG (f ; µG, ΣG) = N (0; µG, ΣF + ΣG) NF G (f ; µF G , ΣF G ) , ΣF G = " Σ -1 F + Σ -1 G " -1 , µF G = ΣF G " Σ -1 G µG " . (22)
This is again a Gaussian in frequency space, or a Gabor kernel. The parameters (F ′ 0 , ω ′ 0 ) of the anisotropically filtered Gabor kernel are the polar coordinates of µF G, and a ′ and K ′ are

a ′2 = 2π q |ΣF G |, K ′ = K a ′2 a 2 N (0; µG, ΣF + ΣG) . (23)
The Gaussian of Eq. ( 22) is in general anisotropic. We approximate this anisotropic Gaussian in frequency space with a Gabor kernel, which is an isotropic Gaussian. Although this approximation could be avoided by using Gabor kernels with an anisotropic Gaussian envelope, it works very well in practice. This is illustrated in Fig. 6. This method is not limited to a specific rendering paradigm. The partial derivatives of the Jacobian can be obtained using ray differentials [START_REF] Igehy | Tracing ray differentials[END_REF]] in renderers based on ray tracing, and using finite differencing in renderers based on rasterization. Filtering procedural textures obtained by nonlinear transformations of noise is an unsolved problem. However, our noise is more expressive than previous noises, and in many cases removes the need for nonlinear transformations. In Sec. 6 we show that most procedural textures can be obtained using only our noise and a color lookup table. We anisotropically filter these procedural textures by filtering the noise, as described above, and the color lookup table, with a method similar to [START_REF] Hart | Antialiased parameterized solid texturing simplified for consumerlevel hardware implementation[END_REF].

Results

We show several noise patterns and procedural textures generated with our application for interactive noise design in Fig. 1, Fig. 7 and the accompanying video. Note that all surfaces are triangle meshes, and that surface noise is anisotropically filtered unless noted otherwise. We demonstrate a wide range of procedural textures generated using only our noise and a color map. This includes typical procedural solid textures (e.g., the marble vase and the wooden statuette in Fig. 7), but also cellular-like textures (e.g., the snake skin in Fig. 7). We show that in addition to anisotropic filtering, anisotropic noise is also useful for modeling anisotropic textures (e.g., the straw hat, the wooden chair and the tree bark in Fig. 7) and even structured textures (e.g., the textile cushion in Fig. 7). This extends the range of textures that can be generated procedurally. We demonstrate that our method for anisotropic filtering results in high-quality animations and does not introduce artifacts such as swimming (see video). We show that our surface noise does not require a texture parameterization by texturing an implicit surface that changes shape and topology interactively (see video and Fig. 1). This would not be possible with traditional texture mapping or with surface noise that is not setup free. We demonstrate that solid noise is not a substitute for surface noise by illustrating the difference between solid noise and surface noise (see straw hat example in video). We achieve frame rates of roughly 30 frames per second at a resolution of 800 × 600 using an NVIDIA GeForce GTX 280 (see video), making our noise well-suited for interactive applications.

Comparison and Discussion

In this section we compare our noise with Perlin noise, sparse convolution noise, wavelet noise, the noise of Goldberg et al., and the noise of Kensler et al. The noises and their power spectra are shown in Fig. 8, and a feature matrix of the noises is shown in Tab. 1.

Perlin Noise & Kensler's Noise

Perlin noise [START_REF] Perlin | Improving noise[END_REF]] and the noise of [START_REF] Kensler | Better gradient noise[END_REF] do not support anisotropic noise or anisotropic filtering. Kensler et al. also use a projection method for surface noise. However, the projection does not preserve the Perlin noise lattice, and it is not clear how this affects the properties of the surface noise.

Sparse Convolution Noise & Spot Noise

Our work is inspired by sparse convolution noise [START_REF] Lewis | Texture synthesis for digital painting[END_REF][START_REF] Lewis | Algorithms for solid noise synthesis[END_REF]] but is also related to spot noise [van Wijk 1991], a method for synthesizing stochastic textures for visualizing scalar and vector fields. Both methods offer some form of spectral control. However, Lewis only used a radially symmetric smooth cosine kernel, and spot noise does not have the properties of a procedural noise function.

Wavelet Noise Wavelet noise [START_REF] Cook | Wavelet noise[END_REF] does not support anisotropic noise or anisotropic filtering. Setup-free surface noise is obtained by performing a weighted line integral of solid noise. However, the storage requirements of solid wavelet noise are significant, a tile with a resolution of 256 3 requires 64 MB of storage. The noise is only approximately isotropic. The square feature in the power spectrum (Fig. 8(c)), caused by the separable B-splines, indicates an undesirable axis-aligned directional preference in the noise.

Goldberg's Anisotropic Noise

The noise of [START_REF] Goldberg | Anisotropic noise[END_REF] is impractical for solid noise, because it has storage requirements similar to wavelet noise. Surface noise is obtained by mapping two-dimensional noise onto the surface and compensating for distortions. Therefore, the noise requires a surface parameterization and a method for handling seams. This removes one of the major advantages of procedural texturing, that is that any surface can be textured without preprocessing. The noise stores discretely sampled data and is therefore potentially subject to discretization artifacts. Similar to wavelet noise, the noise is potentially subject to repeating patterns if only a single tile is used. Performance Tab. 2 shows the performance of our 2D noise and unfiltered and filtered surface noise, in frames per second (FPS) and megapixels per second (MPixels/s), using an NVIDIA GeForce GTX 280. In comparison, the noise of [START_REF] Goldberg | Anisotropic noise[END_REF], one of the fastest noises, runs at 538 FPS and 258 MPixels/s, (4 octaves, 800×600). This means that, assuming 30 impulses per cell, our 2D noise is about 4 times slower, while our filtered surface noise is 40 times slower, but offers accurate spectral control, is setup free, and is truly procedural. Although our noise is not as fast as most other noises, it runs at interactive rates and enables a speed vs. quality trade-off. Interference Patterns Very narrowly band-limited noise may exhibit interference patterns (see e.g., Fig. 7, top row, fourth pattern). This is because very narrowly band-limited noise consists only of harmonics with frequencies very close to the principal frequency. These harmonics slowly transition between perfectly in phase, causing constructive interference, and perfectly out of phase, causing destructive interference. We have verified that the interference patterns are not artifacts introduced by the procedural evaluation using our non-procedural CPU implementation based on frequency filtering.

Spectral Control

Our noise offers more accurate spectral control than a weighted sum of octaves. A weighted sum can only roughly approximate a desired power spectrum, because of the coarse discretization of frequency space, and therefore offers only limited spectral control. The resulting approximation errors can be visually noticeable and affect noise design and noise filtering.

Although the approximation can be improved by using a finer discretization, this increases storage requirements and evaluation cost. Our noise samples a parameteric description of the desired power spectrum instead of discretizing frequency space, and therefore offers more accurate spectral control. This is demonstrated in Sec. 3.1, 3.2 and 5.2.

Procedural Our noise has a memory footprint of only a few bytes, does not rely on discretely sampled data, is nonperiodic, and has intuitive parameters, and is therefore truly procedural. Our noise is also mathematically elegant and its properties are characterized analytically.

Conclusion

We consider accurate spectral control and setup-free surface noise to be the two most important advantages of our new procedural noise. Setup-free surface noise allows the user to map any texture designed with our noise onto a surface, while maintaining the appearance of the texture, without precomputation and undesired artifacts such as distortions and seams. Accurate spectral control allows the user to benefit from increased noise expressiveness, more advanced modeling capabilities and improved rendering quality.

A promising direction for future research is modeling procedural textures by example by guiding our noise with parametric descriptions of power spectra derived from real world textures. Other interesting topics for future work are decoupling the bandwidth of the noise and the size of the grid to enable noise with unrestricted spatially varying bandwidth, extending our method for anisotropic filtering to solid noise, and investigating the possibilities of other kernels and Gabor kernels with more parameters.

Figure 2 :

 2 Figure 2: The Gabor kernel. (a) Gaussian envelope. (b) Harmonic. (c) Gabor kernel. (d) Gabor kernel, 3D plot. (e) Fourier transform of Gabor kernel. (f) Fourier transform of Gabor kernel, 3D plot.

  Analyt. pow. spec.

Figure 3 :

 3 Figure 3: Band-limited anisotropic noise. (a) Anisotropic noise with intensity histogram (gray) and expected intensity distribution (red). (b) Power spectrum. (c) Analytical power spectrum.

Figure 4 :

 4 Figure 4: Band-limited isotropic noise. (a) Isotropic noise with intensity distribution. (b) Power spectrum with radially averaged power spectrum. (c) Analytical power spectrum.

  Iso. surf. frames. (c) Iso. surf. noise. (d) Aniso. surf. frames. (e) Aniso. surf. noise. (f) Discontinuity.

Figure 5 :

 5 Figure 5: Setup-free surface noise. (a) Projection of the three-dimensional Poisson distribution onto the tangent plane. (b) Randomly oriented local surface frames for isotropic surface noise. (c) Isotropic surface noise. (d) Local surface frames aligned with a vector field for anisotropic surface noise. (e) Anisotropic surface noise. (f) The discontinuous face normals used on the left result in a noise discontinuity, while the smooth vertex normals used on the right ensure continuity.

Figure 6 :

 6 Figure 6: Anisotropic filtering. (a) Isotropic noise. (b) Anisotropic noise. (Top row) Tilted plane with unfiltered and anisotropically filtered noise with close-ups. (Bottom row) Power spectrum of the unfiltered noise, frequency domain filter in texture space, reference power spectrum and power spectrum of the anisotropically filtered noise of the circled pixel.

Figure 7 :

 7 Figure 7: Results. (Top row) Several noise patterns generated with band-limited anisotropic and isotropic noise. (Middle) Several procedural textures generated with our application for interactive noise design. The marble vase and the wooden statuette are generated with solid noise. The granite vase, textile cushion, straw hat, leather boot, rusty car, wooden chair, snake skin and tree bark are generated with filtered surface noise. (Bottom rows) The color maps, noises and widgets used for the procedural textures generated with surface noise.

  (a) Perlin noise. (b) Lewis' noise. (c) Wavelet noise. (d) Goldberg's. (e) Kensler's. (f) Ours, CPU. (g) Ours, GPU. (h) Ours, valid.

Figure 8 :

 8 Figure 8: Isotropic noises and their power spectra. (a) Perlin noise. (b) Sparse convolution noise. (c) Wavelet noise. (d) The noise of Goldberg et al. (e) The noise of Kensler et al. (f) Our noise, CPU implementation. (g) Our noise, GPU implementation. (h) Our noise, validation.

  2 disc. sc. & or. : discrete scale and orientation -cont. K a F 0 ω 0 : continuous K, a, F 0 and ω 0 .

Table 1 :

 1 Noise feature matrix. Feature matrix showing Perlin noise, sparse convolution noise, wavelet noise, the noise of Goldberg et al., the noise of Kensler et al. and our noise versus the properties identified in Sec. 1.1.

  2D noise/unfiltered surface noise/filtered surface noise 2D noise: 512 × 512, surface noise: 175.516 visible pixels

	# impulses/cell	20	30	40	50
	FPS	290/111/50	201/76/34	156/61/26	126/53/22
	MPixels/s	76.2/19.6/8.9 52.8/13.5/6.1 41.0/10.8/4.6 33.2/9.4/3.9
	performance figures:

Table 2 :

 2 Noise performance. Performance of our 2D noise and unfiltered and filtered surface noise, in frames per second and megapixels per second, using an NVIDIA GeForce GTX 280.

Acknowledgments

We would like to thank the anonymous reviewers, and Bart Adams, Fernanda Andrade-Cabral, Fredo Durand, Eugene Fiume, Brian Smits, Joris Van Deun, Peter Van Gorp and Celine Vens. Ares Lagae is a Postdoctoral Fellow of the Research Foundation -Flanders (FWO), and acknowledges K.U.Leuven CREA funding (CREA/08/017).

Noise. Wiley. VAN WIJK, J. J. 1991. Spot noise texture synthesis for data visualization. In Computer Graphics (Proc. ACM SIGGRAPH 91), vol. 25, 309-318. WORLEY, S. 1996