Scott Draves 和 Erik Reckase 于2007年7月份更新的文档，相比以前的文档，增加了很多内容，值得下载下来欣赏欣赏。

1 Overview
Some examples appear in Figure 1. The paper begins by defining classic, linear
iterated function systems and hence grounding our notation and terminology.
The classic formulation is then extended with non-linear variations in Section 3,
and then further extended with post transforms and final transforms in Sec-
tion 3.1. Section 4 describes how log-density display works and its importance,
and Section 5 covers the coloring algorithm. These three sections cover the core
innovations. Sections 6 and 8 explain other important properties of the imple-
mentation, and Section 7 shows how to create symmetric flames. The appendix
is a catalog of the variations including formulas and examples.
2 Classic Iterated Function Systems
A two-dimensional Iterated Function System (IFS) is a finite collection of n
functions Fi from R2 to R2. The solution of the system is the set S in R2 (and
hence an image) that is the fixed point of Hutchinson’s recursive set equation
[3]:
S =
n−1
[i=0
Fi(S)
1
a b
c d
Figure 1: Example fractal flame images. The names of these flames are: a) 206,
b) 191, c) 4000, and d) 29140. These images were selected for their aesthetic
properties.
2
Figure 2: Sierpinski’s Gasket, a simple IFS. X and y increase towards the lower
right. The recursive structure is visible as the whole image is made up of three
copies of itself, one for each function.
As implemented and popularized by Barnsley [1] the functions Fi are linear
(technically they are ane as each is a two by three matrix capable of expressing
scale, rotation, translation, and shear):
Fi(x, y) = (aix + biy + ci, dix + eiy + fi)
For example, if the functions are
F0(x, y) = ( x
2 , y
2 ) F1(x, y) = ( x+1
2 , y
2 ) F2(x, y) = ( x
2 , y+1
2 )
then the fixed-point S is Sierpinski’s Gasket, as seen in Figure 2.
In order to facilitate the proofs and guarantee convergence of the algorithms,
the functions are normally constrained to be contractive, that is, to bring points
closer together. In fact, the normal algorithm works under the much weaker
condition that the whole system is contractive on average. Useful guarantees
of this become dicult to provide when the functions are non-linear. Instead
we recommend using a numerically robust implementation, and simply accept
that some parameter sets result in better images than others, and some result
in degenerate images.
The normal algorithm for solving for S is called the chaos game. In pseu-
docode it is:
(x, y)= a random point in the bi-unit square
iterate { i = a random integer from 0 to n − 1 inclusive
(x, y) = Fi(x, y)
plot(x, y) except during the first 20 iterations
}
The bi-unit square are those points where x and y are both in [-1,1]. The
chaos game works because if (x, y) ∈ S then Fi(x, y) ∈ S too. Though we start
3
out with a random point, because the functions are on average contractive the
distance between the solution set and the point decreases exponentially. After
20 iterations with a typical contraction factor of 0.5 the point will be within
10−6 of the solution, much less than a pixel’s width. Every point of the solution
set will be generated eventually because an infinite string of random symbols
(the choices for i) contains every finite substring of symbols. This is explained
in more formally in Section 4.8 of [1].
No sucient number of iterations is given by the algorithm. Because the
chaos game operates by stochastic sampling, the more iterations one makes the
closer the result will be to the exact solution. The judgement of how close is
close enough remains for the user.
In fractal flames, the number of samples is specified with the more abstract
parameter quality, or samples per output pixel. That way the image quality
(in the sense of lack of noise) remains constant in face of changes to the image
resolution and the camera.
It is useful to be able to weight the functions so they are not chosen with
equal frequency in line 3 of the chaos game. We assign a weight, or relative
probability wi to each function Fi. This allows interpolation between function
systems with dierent numbers of functions: the additional functions can be
phased in by starting their weights at zero. Dierently weighted functions are
also necessary to draw symmetric flames as shown in Section 7.
Some implementations of the chaos game make each function’s weight pro-
portional to its contraction factor. When drawing one-bit per pixel images
this has the advantage of converging faster than equal weighting because it
avoids redrawing pixels. But in our context with mutiple bits per pixel and
non-linear functions (where the contraction factor is not constant) this device
is best avoided.

。。。。。。。。。。。。。。。。