As described in [1] , an IFS consists of a finite set of affine contractive functions The set for example forms a Sierpinski triangle with where p is a vector.

The associated set S is the fixed point of Hutchinsons's recursive set equation It is not possible to directly evaluate the set, as the Hutchinson Equation (Eq. 18.3 ) describes an infinite recursion. An approximate approach is the Chaos Game [1] , which solves the Hutchinson Equation by a Monte Carlo method. Figure 18.3 shows it in a basic version. The Chaos Game starts by selecting a random point of the bi-unit square p = (x , y ) with | x | ≤ 1, | y | ≤ 1 and starts its iterating phase by choosing a random function f _i in each iteration and evaluates p := f _i (p ). With increasing numbers of calculated iterations, p converges closer to the set [6] . After a sufficient number of steps, the point can be plotted in every iteration.

Iterated Function Systems have numerous applications, as outlined in [3] , such as graphs of functions, dynamical systems, and brownian motion. Furthermore, this approach could be used in multilayer material simulations in ray tracing. In this chapter, we concentrate on IFS for the simulation of Fractal Flames.

We chose to start with a random point and to select a function at random, even though randomness is not a requirement of the algorithm. The initial point is actually arbitrary; and it will still converge to the set, given that the last iterations contain all possible combinations of functions. As we aim for real-time performance, we can evaluate only a very limited number of iterations, but on a lot of points, exploiting parallelization. Should the resulting fractal be too complicated to achieve subpixel convergence, the random initialization still creates a uniform appearance. This is, especially over the course of some frames, more visually pleasing than deterministic artifacts.

Fractal Flames, as described in [2] , extend the IFS algorithm by allowing a larger class of functions that can be in the set F . The only restriction that is imposed on the functions f _i is the contraction on average. These functions can be described by: with P _i (x , y ) = (α _i x + β _i y + γ _i , δ _i x + ϵ _i y + χ _i ), where a _i ⋯ g _i and α _i ⋯ χ _i express affine transformations on 2-D points, while V _j , so-called variations apply nonlinear transformations, which are scaled by the factors v _ij . Typically, each function has its own set of up to 20 variations V _j . A few variation functions can be found in Figure 18.4 . An extensive collection of those variations can be found in [2] .

Every function is assigned a weight w _i that controls the probability that f _i is chosen in a Chaos Game iteration. This parameter controls the influence of a function in the computed image. Furthermore, a color c _i ∈ [0, 1] is assigned. Every point has a third component that holds the current color c , which is updated by c := (c + c _i )/2 in each iteration and is finally mapped into the output color space.

The computed points are visualized by creating a colored histogram. Because the computed histogram has a very high dynamic range, a tone-mapping operator is applied.

The optimized Chaos Game algorithm requires synchronization across all threads and blocks after each iteration because the data gets shuffled across all threads. Because of CUDA's lack of such a synchronization instruction, the Chaos Game had to be split into three kernels to achieve synchronization by multiple kernel executions (see Figure 18.6 and Figure 18.7 ).

The initialization kernel performs one iteration of the Chaos Game on the randomly permuted Hammersley point set. The warm-up kernel performs one Chaos Game iteration and is called multiple times until the output data points converged to the fractal. The last kernel generates a larger set of points by randomly transforming each of the previously generated points 64 times, producing 64 independent samples for each input sample. The generated points are recorded in a vertex buffer object (VBO), which is then passed to the rendering stage. From those kernels, the point-generation kernel takes by far the most computation time. Those runtimes on a GTX280 are 34.80μs init, 43.12μs warm-up, and 1660.59μs generate points. The init kernel occupies 1.5% of the total Chaos Game runtime; the warm-up kernel is called 15 times and thus takes 27.6%, whereas the point-generation kernel takes 70.9%.

The point-generation kernel needs to select a point from the point buffer multiple times, calculate one iteration, and write the result into the VBO. As the input point array does not change, texture caching can be used. The effect of this optimization is a 6.9% speed improvement for the 9500GT and 18% for the GTX280. The access pattern is pretty bad for the texture-caching mechanisms of a GPU because it completely lacks locality. Because the memory consumption of the samples is approximately 200 kB, the cache of a GPU seems to be big enough to hold a large number of samples; therefore, this method yields a major performance improvement. Benchmarks have been conducted to measure the effect of the number of samples on the texture caching. As shown in Figure 18.8 , the number of threads — and therefore the number of samples in the texture cache — doesn't have a huge impact: the runtime stays constant up to 2 ¹² threads and then increases linearly with the number of threads; the cached version is constantly faster.

Note that only the warm-up kernel has a completely random memory-access pattern during read and write. It needs to randomly access the point array to read a point for the iteration and to write out its result. To avoid race conditions on write accesses, either data has to be written back to the position the point was read from, or else a second array storing points is needed. The former approach involves random reads and writes, whereas the latter one has higher memory use. The initialization kernel needs to randomly select a starting point, but it can write the iterated points in a coalesced manner. Because of its low runtime, there is no need to optimize it further.

The generated points are rendered as a tone-mapped histogram using OpenGL. This step consumes approximately 70% of the total time, depending on the particular view.

The 1-D color component needs to be mapped into the RGBA(red, green, blue, alpha) representation. This is done by a 1-D texture look-up in a shader. To create the colored histogram, the points are rendered using the OpenGL point primitive and using an additive blending mode. This yields brighter spots where multiple points are drawn in the same pixel. To cope with the large range of values, a floating-point buffer is employed. The resulting histogram is then tone mapped and gamma corrected, because the range between dark and bright pixel values is very high. For the sake of simplicity and efficiency, we use L ′ = L /(L + 1) to calculate the new pixel lightness L ′ from the input lightness L , but more sophisticated operators are possible [2] .

Monte Carlo-generated images are typically quite noisy. This is especially true for the real-time implementation of Fractal Flames because only a limited number of samples can be calculated in the given time frame. Using temporal antialiasing smoothes out the noise by blending between the actual frame and the previously rendered ones. This is implemented by using frame buffer objects and it increases the image quality significantly.

Some static data is needed during runtime; this data is calculated by the host during program start-up. A set of Hammersley Points [4] is used as the starting-point pattern to ensure a stratified distribution, which increases the quality of the generated pictures. The presorting algorithm needs permutations that are generated by creating multiple arrays containing the array index and a random number calculated by the Mersenne Twister [5] . These arrays are then sorted by the random numbers, which can be discarded afterwards. The resulting set of permutations is uploaded onto the device. Since some of the implemented functions need random numbers, a set of random numbers also is created and uploaded onto the device. All of this generated data is never changed during runtime.

In the runtime phase, it is necessary to specify various parameters that characterize the fractal. Every function needs to be evaluated in p (f _i ) ⋅ num_threads threads, where p (f _i ) is the user-specified probability that function f _i is chosen in the Chaos Game. The number of functions is small compared to the number of threads, and therefore, it doesn't matter if this mapping is done in warp size granularity instead of thread granularity. Each thread is mapped to a function by an index array that is compressed into a prefix sum. A thread can find out which function it has to evaluate by performing a binary search on this array. This search does not introduce a performance penalty in our experiments, but reduces the memory requirements significantly. The parameters and the prefix sum are accumulated in a struct that is uploaded into the constant memory each frame.