Philosophy is written in this grand book - I mean universe - which stands continuously open to our gaze, but it cannot be understood unless one first learns to comprehend the language in which it is written. It is written in the language of mathematics, and its characters are triangles, circles, and other geometrical figures, without which it is humanly impossible to understand a single word of it; without these, one is wandering about in a dark labyrinth.

Galileo

Clouds are not spheres, mountains are not cones, coastlines are not circles, and bark is not smooth, nor does lightning travel in a straight line. ... Mathematicians have disdained this challenge, however, and have increasingly chosen to flee from nature by devising theories unrelated to anything we can see or feel. ...

Responding to this challenge, I conceived and developed a new geometry of nature and implemented its use in a number of diverse fields.

Benoit Mandelbrot

What is new is the ability to start with an actual image and find the fractals that will imitate it to any desired degree of accuracy. Since our method includes a compact way of representing these fractals, we end up with a highly compressed data set for reconstructing the original image.

Michael Barnsley and Alan Sloan

We have seen that one of the best measures of visual realism in computer graphics is the extent to which shading models and rendering algorithms incorporate the physics of light and its interactions with objects. Yet, in spite of the successes of ray tracing and radiosity techniques, experts in computer graphics can consistently detect the artificial nature of synthetic images (i.e., computer-generated images). Even novices in computer graphics often sense something artificial about synthetic images, with the objects themselves providing clues on the rendering technique. Glass balls, teapots, and checkerboards suggest ray tracing while walls, tables, and lamp shades hint at radiosity. It is rare, indeed, to find a synthetic image of natural objects that is at all convincing in its visual realism. That is, the representation and rendering techniques we have discussed to date are extremely effective in displaying objects that are human-made, symmetrical, or geometric primitives, but they fail miserably in generating realistic images of such common objects as trees, clouds, and mountains. Why is that?

The answer is both simple and profound, and it is deeply rooted in the concept of dimensionality itself. The simple answer is given by Yale mathematician Benoit Mandelbrot in the introductory quotation who observes that most natural objects do not conform to simple geometric shapes. The more profound answer is that the geometry best describing most natural objects is not traditional 3D Euclidean geometry, but rather what Mandelbrot describes as the fractal geometry of nature. Mandelbrot coined the term fractal to describe both natural and mathematical objects that share the property of having fractional dimensionality, a term we define shortly. The concept of dimensionality plays a key role in distinguishing fractal objects from those 1D, 2D, and 3D objects we have studied so far. For this reason, the study of fractals as fractional-dimension objects is the natural concluding chapter of our N-Dimensional approach to computer graphics.

Fractal geometry is another confirmation of the principle of model authenticity introduced in previous chapters. This principle holds that realistic simulation of physical systems requires recognition and accurate simulation of the physics governing the behavior of those systems. The computer graphics task of rendering realistic images of natural scenes requires, according to this principle, that we model such scenes using the appropriate geometry--fractal geometry. Fractal geometry is one aspect of the emerging field of chaos and nonlinear dynamics, a revolutionary new area of physics and mathematics research. The remarkably realistic renderings of scenes based on fractal geometry confirm the principle of model authenticity.
 
 

The Fractal Geometry of Nature

Perhaps the most noteworthy aspect of fractal geometry is the enormous range of objects and systems it is capable of describing. A partial list includes: mountain landscapes, clouds, rainfall patterns, snowflakes, frost patterns, island formations, sea coasts, river basin patterns, tree branching, arteries, veins, bronchioles, high-energy physics particle jets, percolation patterns, moon craters, galaxy structure, Brownian motion of molecules, structure of magnetic domains, radio noise, stock market fluctuations, and the mountain landscape in the movie Star Trek II: Wrath of Khan.

The science of chaos and fractal geometry is a classical example of an interdisciplinary field. The following areas have both contributed to--and profited greatly from--the study of fractal geometry:

• Physics
• Mathematics
• Computer graphics
• Art and music
• Data Compression and Communications

Chaos theory and fractal geometry have also contributed significantly to the following fields:

• Medicine
• Engineering
• Economics
• Cinema

The unifying and central role of fractal geometry is illustrated in Figure 11.1.
 

Figure 11.1

Fractal geometry and chaos theory play a central and unifying role in many disciplines.

Properties of Fractals

Fractal objects share certain characteristics which distinguish them from more traditional objects defined by Euclidean geometry. These include:

• Fractals have the property of self-similarity or statistical self-similarity. That is, upon magnification of the structure of a fractal, new structure emerges that appears identical or statistically similar to that of the original structure.
  
  
• The generating functions or algorithms for fractals are generally simple, but usually lead to structure that is amazingly complex
  
  
• The natural language for generating fractals is iteration or recursion.
  
  
• The dimensionality of fractals is noninteger (i.e., fractional).
  
  

Let's examine some of these properties in more detail.
 

Fractional Dimensions

Our indoctrination with traditional Euclidean geometry makes the integer classification of n-dimensional systems seem like the only natural and logical one. We all know intuitively what 1D, 2D, and 3D objects are. A line or smooth curve is a 1D object; a plane, polygon, or Bézier patch is a 2D object ; and a sphere, cylinder, or superquadric is a 3D object. However, Figure 11.2 suggests that life may not always be so simple.

 

(a)	(b)	(c)
(d)	(e)	(f)

Figure 11.2

Sierpinski Gasket . What starts as a simple set of sixteen 1D lines becomes more complex and "space filling" with each iteration. By the sixth iteration, the 1D figure has evolved into a 2D figure.

It is clear that what starts out as a 1D outline tends toward a 2D figure as each level of recursion is carried out.

Another experiment illustrating the ambiguity of our traditional concept of dimension is the following. Start with a flat sheet of white paper. It is clearly a 2D object. Now crumple it up somewhat. What is it now? Well, it is a sort of random set of somewhat curved 2D patches. Now crumple it tighter and tighter until it is about the size of a golf ball. Hold it between your thumb and forefinger and call across the room to your friend, "Let's go play golf!" She'll reply, "Fine, I see you've got a ball." But a golf ball is 3D and this is only a sheet of paper. Is it 2D or 3D?

So the concept of dimensionality must be considered in a more systematic and analytic way. The following definition of dimension D was proposed by Hausdorff early in the twentieth century. Consider the problem of measuring the coast line of England. Using a satellite photograph and a ruler with appropriate divisions, say 1 km, we would measure a length we can designate L1. To get a more accurate answer, we could use a series of high-altitude aircraft photographs and a ruler with finer divisions of say one hundred or ten m to determine a new length, L2. If this were still not adequate, we could send out teams of surveyors with meter sticks who would report back a length, L3.

Note that L1 represents the length of coast line of the major land masses, bays, and other geologic features with a scale of a few kilometers or more. However, big bays have little bays and big peninsulas have smaller peninsulas, and L2 is a better representation of such smaller-scale features. The L3 answer generated by the surveyors' meter sticks represents an even finer-grained measurement. In principle, this refinement could continue indefinitely down through the centimeter and millimeter scales appropriate for rocks and pebbles until we reached the millimicron scale of atoms.

How are the measurements, L1, L2, and L3 related? Obviously, L1 < L2 < L3. That is, the result obtained is determined by the scale of the ruler used to make the measurement. In other words, the size of irregular objects depends upon the number of increments used to determine the size. This is not the case for regular Euclidean objects. This scale dependence of fractal objects provides the basis for the definition of dimensionality.

Consider the relationship between the number of incremental elements, N, and the element size, r, for the following 1D, 2D, and 3D objects.

1D       r = 1/4, N = 4   Figure 11.3 Relationship between r and N, where: r = scale size of element, N = number of elements.

2D       r = 1/4, N = 16

3D       r = 1/4, N = 64

Note that the relationship between the scale r and number of elements, N, may be written:

1D: N r¹ = 1

2D: N r² = 1

3D: N r³ = 1

This may be generalized for dimension, D, as:

 N rD   = 1 					 	[11.1] 

The quantity D is defined as the Hausdorff dimension and may be extracted from Equation 11.1 and expressed in terms of the number of elements and their size as:

D = ln(N)/ln(1/r)					[11.2]

Note that nothing in the defining Equation 11.2 requires that D assumes only integer values. For fractal objects D takes on noninteger values. Consider D for the following fractal objects.

The von Koch triangular snowflake has some very interesting properties. The geometric generator applied iteratively to each section of the figure is shown in 11.4(a), and the results of the first iteration given in 11.4(c). Note that the length of the "shoreline" (perimeter) of the original triangle is L1 = 3; after one iteration, the perimeter is L2 = (4/3)L1; after two iterations, L3 = (4/3)2L1; and so on. Thus the perimeter of the von Koch snowflake goes to infinity as the number of iterations goes to infinity, even though the curve itself is bounded by the square subtending 11.4(c). Substituting the number of elements used to measure a side (N = 4) and the length of each (r = 1/3), Equation 11.2 yields the dimensionality D = 1.2618&hellip; for the von Koch snowflake.
 

(a)

(b)

(c)

Figure 11.4

von Koch fractal triangle generator. Applying the geometric substitution shown in (a) to each segment of the triangle (b) produces first iteration of the von Koch snowflake, shown in (c). Since N = 4 and r = 1/3, the Hausdorff dimension of the Koch triangle is D @ 1.26.

In light of the previous discussion of the length of coastline, one might expect that the dimensionality of an object would increase as the complexity of sub-structure increases. The von Koch square, shown with its generator and the results of the first iteration in Figure 11.5, exhibits a complexity greater than that of the triangular snowflake. Now, to characterize the increase in length of shoreline after each iteration, we need N = 8 elements each of length r = 1/4 unit. Substituting these values into Equation 11.2 does, in fact, yield an increased dimensionality of D = 1.5.

 

(a)

(b)

Figure 11.5

von Koch fractal square generator. Applying the substitution indicated in (a) to each segment converts the square into the fractal curve shown after the first iteration in (b). Since N = 8 and r = 1/4, the dimensionality of this fractal is D = 1.5.

An intuitive interpretation of the dimensionality of fractals has been given by Richard Voss, one of Mandelbrot's colleagues at IBM, who stated, "Fractal dimension measures how the length of a coast line changes as we change the size of the ruler." We will discuss shortly algorithms for generating fractal landscapes which accurately simulate mountain scenes. An interesting result of the research on the dimensionality of natural fractal objects is the X.2 Rule. This rule states that very realistic fractal coast lines, mountains, and clouds are generated by objects with dimensionality Di, where:

Coastlines			Di = 1.2

Mountains			Di = 2.2

Clouds					Di = 3.2-3.3

A natural interpretation of the fractional dimension of coastlines involves their "area filling" character. That is, as we move from the simple triadic Koch curve through the more complex quadric Koch curve to the highly irregular Sierpinski curve the dimension ranges from 1.26 through 1.5 to nearly 2. Mountain landscapes involve distorting a smooth, 2D surface by stochastic processes acting on the third dimension. If the disturbance is small, "rolling hills" with D ~ 2.1 result; increasing the dimension to D > 2.5 causes a rugged landscape with jagged peaks and steep-walled canyons. Modeling of clouds requires specifying at each 3D point a fourth dimension such as the temperature or translucency of the condensation at that point.
 

Classification of Fractals

From the preceding discussion, several properties of fractals provide the basis for a classification system, including dimensionality, self-similarity, and generation technique. One property which cleanly distinguishes two distinct classes of fractals is the role of chance in their generation and resulting structure. Figure 11.6 summarizes this classification scheme.

Figured 11.6

Classification scheme for fractals based on the role of chance.

Deterministic Fractals

Deterministic fractals have structures which are fixed uniquely by the algorithm employed in their creation. That is, for a given set of parameters, a deterministic fractal generator will produce identical structures each time it is run. Chance plays no role in the final structure of the deterministic fractal.

Interestingly, identical fractals may be produced by distinct algorithms. The Sierpinski gasket, for instance, can be generated by the "Chaos Game" algorithm or by an iterated function system algorithm discussed presently. Some of these algorithms do employ random number generators within the deterministic program. The final structure of the fractal, however, shows no indication of random processes and is a function of the control parameters only.
 

Stochastic Fractals

The distinctive characteristic of stochastic fractals is that random processes play a central role in determining the structure of the fractal object. Phenomena such as turbulence, seacoast, and mountain formation are deterministic at a physical level but are extremely sensitive to the initial conditions, a property common to all chaotic systems. The complex interaction of the system with the initial conditions and subsequent environment results in apparently random turbulent behavior and fractal mountain landscapes.

It is virtually impossible to accurately represent the initial condition and successfully simulate the subsequent system development of such natural systems. A far more tractable approach has been to simulate the fractal geometry of such objects by introducing random processes in creating the scenes. The approach has proven successful in simulating Brownian motion, percolation behavior, and mountain geography.
 

Generating Fractals

The best way to understand fractals is to study algorithms for generating the major types of fractals, build programs to implement these algorithms, and observe the graphical results. The broad categories of fractals defined in the last section can be further refined according to the general algorithmic approach used in generating the fractal.

Categories of Fractal Algorithms

The fractals of interest in this chapter can all be generated by the following classes of algorithms:

• Linear replacement mapping - Fractal curves such as the Koch and Sierpinski curves are generated by successive refinement of a given line by some generator function.
  
  
• Iterated function systems - Many natural objects such as ferns and trees can be generated by the successive application of a series of contractive affine transformations.
  
  
• Complex plane mapping - Mathematical objects such as the Julia and Mandelbrot sets are generated by successive mapping on the complex plane.
  
  
• Stochastic processes - Mountain landscapes and other irregular objects are generated by applying random processes within a recursive algorithm.
   

Linear Replacement Mapping

The basic idea of replacement mapping is that a generator function maps a given, parent structure into a new, more complex child structure. An original object is defined, and, in the first iteration, the replacement mapping is applied to each element of the original object, producing a refined child object. In the second iteration, each element of the child object is transformed into an even more refined grandchild object, and so on. Theoretically, a fractal generated by replacement mapping would require an infinite number of iterations. In practice, for graphical applications, the iteration or recursion need continue only until the structures being mapped fall to subpixel dimensions. The simplest form of replacement mapping is linear replacement mapping, the conversion of a single line into a more complex object.

The basic algorithm for linear replacement mapping is summarized below.

Linear Replacement Mapping Algorithm

1. Define initial structure in terms of lines defined by end points.

2. Define replacement mapping replacing each line with refined set of lines.

3. Iterate refinement until desired level is achieved. 

To implement this algorithm we add two additional conditions:

1. The algorithm should be generalized enough to map any arbitrary configuration of lines by a conversion of each line into another arbitrary set of lines.

2. The algorithm should be capable of iteration to an arbitrary level of refinement.

In order to implement the first condition, the first two steps of the algorithm can be isolated to individual subroutines. To satisfy the second condition we can use a file swapping technique to avoid limiting the problem size by the dimensions of internal data structures. The following Pascal program implements the Linear Replacement Mapping Algorithm, subject to the generality conditions.

Pascal Program Koch

program Koch;
{Program to draw and iteratively refine }
{ von Koch curves by the method of }
{ linear replacement mapping. }

		x´ = S x + T					[11.3]

					[11.4]

		X´= X Wi					 [11.5]