20.1
`
`Extensions of Previous Techniques
`/
`
`1013
`
`20.1 . 1 Advanced Modeling with Splines
`
`With the tensor-product spline-patch surfaces defined in Chapter II , more control vertices
`must be added to gain a higher level of detail. The Oslo algorithm and its descendents
`[COHE80; BART87] can be applied to the control mesh of such splines to produce new
`control meshes with more vertices but identical resulting surfaces. This refinement of the
`cont.rol mesh is shown for a line spline in Fig. 20.1. The circled black dots control the shape
`of the thickened segment in the figure; if one of these i.s moved, the shape of the thickened
`segment changes. But bow many control vertices do we need to redraw tbe arc in its changed
`form? For tbe portions outside the thickened segment, we can use the (comparatively few)
`white vertices; for tbe portion inside the thickened segment, we can use the circled black
`vertices. This localization of detail is the fundamental notion of hierarchical B-spline
`modeling developed by Forsey and Bartels [FORS88].
`Two problems arise: maintaining a data structure for the hierarchical spline, and
`altering the large-scale spline without damaging the small-scale one. These two problems
`can be solved together. We wish to alter the large-scale spline so that the small-scale spline
`follows the alteration. We do this alteration by describing the locations of tbe (adjustable)
`control vertices for the small-scale spline in a coordinate system based on the larger spline.
`This prescribes the data structure for the splines as well- a tree in which the control
`vertices of each spline are specified in coordinates based on its parent node in the tree. The
`initial position of each control vertex defines the origin of its coordinate system, and the
`displacements along the normal to the large spline and in the directions tangent to the
`coordinate curves of the large spline determine a basis for this coordinate system. Thus,
`when the large spline is altered, the origin and basis vectors for the displacement coordinate
`system are moved as well.
`Figure 20.2 shows how this procedure works for a line spline. Color Plate IV.4(a) is an
`example of the impressive results this technique can yield. Notice that the final object is just
`a union of portions of various spline patches, so the conventional rendering techniques that
`can handle splines (including polygonal and ray-tracing renderers) can be adapted to render
`these objects. About 500 control nodes. each of which contains a parametric position, a
`level of overlay (i.e., depth in the heirarchy) and an offset, were used to define the dragon's
`head. By defining the offsets of control vertices relative to particular segments in a skeletal
`
`0
`
`0
`
`0
`
`(a)
`
`o'-o--o
`
`o'---o---1 o
`
`o .._o--o
`
`(b)
`
`Fig. 20.1 The spline curve in (a) is generated from the control vertices shown there.
`This collection of control vertices can be refined as shown in (b). The black dots in (b)
`are the new control vertices; the circled black dots are the ones that contribute to the
`thickened segment.
`
`1075
`
`

`
`1014
`
`Advanced Modeling Techniques
`
`0
`
`(a)
`
`.,'-o-~
`
`(b)
`
`··'---
`
`(C)
`
`Fig. 20.2 (a) A line spline with its control points. (b) The same spline with subdivided
`control points in the central segment. Only the middle control point can be moved if
`continuity is to be maintained. The coordinate system for the displacement of the
`middle control point is shown a s well. (c) The middle control point after it is moved,
`along with the displacement vector in the new coordinate system.
`
`model (instead of relative to the parent surface), Forsey and Bartels have extended this
`technique to automate the production of skin, as shown in Color Plate JV.4(b).
`Sederberg and Parry describe a different approach to altering spline models [SEDE86]
`that can be used to alter arbitrary models, although it is based on spline deformations of
`3-space. A function from 3-space to 3-space may be thought of as a way to assign new
`positions to each point in space. Suppose we have such a function and it leaves most points
`unmoved, but deforms some region of space. (Figure 20.3 shows an analogous deformation
`in a region of the plane.) !fa solid is described by the coordinates of its points in the original
`space, then applying the function to the coordinates of every point of the solid yields a solid
`that has been deformed by the function, just as the shaded area was deformed in Fig. 20.3.
`Sederberg and Parry use functions from 3-space to 3-space that are based on Bernstein
`polynomials, which have the form'
`Q •.• (1) = (~) ,, <t - ,r •. o < , < t.
`These polynomials have the property that L 1=0Q. ,,{t) = I (see Exercise 20.1) and that the
`individual Qs are always between 0 and I.
`If we establish a coordinate system in 3-space defined by an origin X and three basis
`vectors S, T, and U, we can form an (n + I) x (m + I) x (p + I) lattice of points in
`3-space by considering all points
`Pijl =X + (i!n) S + (j!m)T + (kip) U , 0 < is n, 0 < j < m, 0 :s k < p,
`which is a gridlike arrangement of points in a parallelepiped based at X with sides
`determined b~...S· T and U. Any linear combination 'i.c~iik of these points satisfying 0 s
`C;ik s I and 2,;cijl = I lies within the convex hull of the points Pijl, that is, within the
`parallelepiped. Furthermore, every point within the parallelepiped can be expressed as a
`combination P = X + sS + IT + uU for some triple of numbers 0 s s, 1, u s I. Suppose
`we define a function on the parallelepiped by the formula
`
`1The notation e) means n!l(i!(n -
`
`i)!).
`
`1076
`
`

`
`20.1
`
`Extensions of Previous Techniques
`
`1015
`
`Fig. 20.3 The plane is deformed so that the region inside the rectangle is distoned,
`but the rest of the plane remains fixed. A figure drawn within the rectangle is also
`deformed.
`
`F(X + sS + ff + uU)
`
`••0 }•0 1•0
`
`I
`
`= ± f t (~) ("!) (p) t 1 (I - 1)• - 1 sl ( I - s)'•-i u• (I - u)P-• P 111
`
`J
`
`/(
`
`Then because of the convexity property of the Bernstein polynomials, the parallelepiped
`maps to itse.lf, with the boundary going to the boundary. In fact, if the PiiJt are left in the
`positions defined previously, F sends each point in the parallelepiped to itself. If the P iJits
`are moved, the map is no longer the identity. As long as only internal P iJits are moved,
`however, the map will remain the identity on the boundary of the parallelepiped. Thus, the
`PuaS provide shape control over any item within the b<»t. Color Plate IV.S shows an example
`of adjusting a free-form shape; Color Plate IV .6 shows a hammer modeled using free-form
`deformations.
`Computing vertices of a polygonal object after transformation by a trivariate Bernstein
`polynomial is simple (we just express each vertex as a linear combination X + sS + ff +
`uU and substitute in the formula for F), so the method is suited for use with all polygonal
`renderers. It is less clear how to ray-trace these deformed objects, although the specialized
`methods described for another class of deformations by Barr (BARR84] might be applied.
`
`20.1 .2 Noise-Based Texture Mapping
`
`Peachey [PEAC85) and Perlin [PERL85) have extended traditional texture mapping by
`using solid textures. Recall that in traditional bump mapping or panern mapping the texture
`was extracted from a 2D image that was mapped onto the surface to be rendered (see
`Chapters 14 and 16). Described differently, for each point of the surface, a point in the 2D
`texture is computed, the values surrounding this point are averaged by some filter, and the
`resulting texture value is assigned to the surface point.
`This mechanism is altered slightly for solid textures. A texture value is assigned to each
`point in a 3D texture spaa. To each point of the object to be textured, there is associated
`
`1077
`
`

`
`1016
`
`Advanced Modeling Techniques
`
`some point in the texture space; the value of the texture at that point is also associated with
`the surface point. We can illustrate this solid texturing by considering an analogous physical
`example. If ~-e take a block of marble (the texture space), then each point of the marble,
`both on the surface and in the inside, has some color. Thus, if we carve a sphere from this
`marble block, the points on the surface of the sphere are also colored. If we carve the sphere
`from a different section of the marble, the colors are different, of course.
`The two tasks associated with this mechanism are the generation of textures and the
`mapping from objects to the texture space (i.e. , the association of points on the object with
`points in the texture space). The mapping to texture space is easy in systems wllere the
`object is modeled in some space, then is transformed into "world space" before rendering.
`In this case, the natural choice for texture space is modeling space. During rendering, a 30
`point on the object is transformed by the inverse of the modeling transformation to give a
`point in modeling space whose coordinates provide the index into the solid texture (this
`situation corresponds to our carving in marble). When this is done, changing the
`world-space position of the object does not affect its pattern. Using world-space coordinates
`as indices into the solid texture can provide interesting special effects. If the marble sphere
`is translated in the course of an animation, the texture slides through it, and it appears to be
`continuously recarved from new marble. In other systems, some coordinate system (or else
`some map from world space to texture space) must be chosen to associate each point on the
`object with a texture value.
`Generating textures is a different matter. Before discussing it, Jet us reconsider the
`function of texture mapping. When a texture map is used for environment mapping onto a
`reflective surface, there is no underlying solid texture. The same is true when a texture map
`is used, say, to put a label on a box, or when bump mapping is applied to an object to
`simulate architectural details such as regularly spaced ceiling tiles, or to generate surface
`characteristics such as the directional reflections on brushed metals. But when we simulate
`the texture of a material such as concrete, wood, or marble, the internal structure of the
`underlying material determines the resulting appearance of the object. In such cases, solid
`textures are most applicable.
`One type of intermediate case, too, that is handled nicely by solid textures is surface
`characteristics, such as the texture of stucco, that should be statistically independent of their
`surface position. Here ordinary pattern mapping tends to produce an orientation because of
`the coordinate system in which the pattern map is defined, and because of the
`transformation from the mapping space onto the object, which tends to compress or expand
`the pattern in some places (e.g., when mapping onto a sphere with standard coordinates,
`one tends to compress the pattern near the poles). SoHd textures handle this problem by
`associating values that can be made effectively independent of the shape of the surface (see
`Color Plate IV. 7c).
`Generating a solid texture requires associating one or more numbers with each point in
`some volume. We can specify these numbers by generating them at each point of a 30
`lattice (this is sometimes called a 3D image), and then interpolating to give intermediate
`values, or simply by giving one or more real-valued functions on a region in 3-space.
`Most of the functions used by Perlin are based on noise functions. He defines a
`function Noise(x, y, z) with certain properties: statistical invariance under rigid motions and
`
`1078
`
`

`
`20.1
`
`Extensions of Previous Techniques
`
`1017
`
`band limiting in the frequency domain. The first of these means that any statistical
`property, such as the average value or the variance over a region, is about the same as the
`value measured over a congruent region in some other location and orientation. The second
`condition says that the Fourier transform of the signal is zero outside of a narrow range of
`frequencies (see Section 14.10). In practical terms, this means that the function has no
`sudden changes, but has no locations where the change is too gradual, either. One way of
`expressing the band limiting is that, for any unit vector (a. b, c) and any point (Xo. y0 , zo),
`the integral
`
`0
`
`~ J Noise(x0 + ta, Yo + tb , z0 + rc)f(mt) dr
`i.s zero when /(r) = sin(t) or cos{l), and m is outside some small range of values.
`Essentially, this says that the noise along a parameterized line in the (a, b, c) direction has
`no periodic character with period m.
`Such a noise function can be generated in a number of ways, including direct Fourier
`synthesis, but Perlin has a quick and easily implemented method. For each point in the
`integer lattice (i.e., for each point (x0, y0, zo) with x0 Yo and z0 all integers) we compute and
`store four pseudorandom2 real numbers (a, b, c , d). Computed' = d- (ax0 + by0 + cz0).
`Notice that if we substitute the point (Xo, y0 , z0) into the formula ax + by + cz + d' we get
`the value d. We now define the Noise function at an arbitrary point (x, y, z) by the r~ rules:
`lf (x, y, z) is a point of the integer lattice, then Noise(x, y, z) = the d value at that lattice
`point = ax0 + by0 + cz0 + d'. For any point not on the lattice, the values of a, b, c, and d'
`are interpolated from the values at the nearby lattice points (Perlin recommends a cubic
`first in x, then in y, then in z) to give values for a, b, c, and d' at the point
`interpolation-
`(x, y, z). Now Noise(x, y, z) is computed: Noise(x, y, z) = ax + by + cz + d'.
`Since the coefficients a, b, c, and d' are interpolated by cubics on the integer lattice, it
`is clear that there are no discontinuities in their values (in fact, they will all be differentiable
`functions with well-behaved derivatives). Hence, the value of Noise(x, y, z) is also well
`behaved and has no high-frequency components (i.e., sudden changes).
`Noise functions can be used to generate textures by altering colors, normal vectors, and
`so on [PERL85]. For example, a random gray-scale value can be assigned to a point by
`setting its color to (r, g, b) = Noise(x, y, z) * (1.0, 1.0, 1.0) (assuming that the Noise()
`function has been scaled so that its values I ie between 0 and I). A random color can be
`assigned to a point by (r, g, b)= (NoiseA(x, y, z), NoiseB(x, y, z), NoiseC(x, y, z)), where
`NoiseAO , NoiseB() and NoiseC() are all different instances of the Noise() function. An
`alternate way to assign random colors is to use the gradient of the noise function:
`Dnoise(x, y, z) = (dNoise/dx, dNoise/dy, dNoiseldz),
`which generates a vector of three values at each poinL These values can be mapped to color
`v-.tlues.
`
`2Pseudorandom-number generation is provided by the RandomO function in many systems. See also
`[KNUT69].
`
`1079
`
`

`
`1018
`
`Advanced Modeling Techniques
`
`If an object has sufficiently great extent, it may not be practical to gen.erate a texture for
`its entire bounding box. Instead, as in Chapter 16, we generate the texture on a finite box
`(perhaps 256 by 256 by 256) and use the low-order bits of the point's coordinates to index
`into this array (using modular arithmetic to wrap around from 255 to 0). We can use this
`finite texture array to generat.e another type of noise by defining Noise2(x, y, z) = Noise(2x,
`2y, 2z). Noise2 will have features that are one-half of the size of those generated by NoiseO.
`By generating a combination of such multiples of NoiseO, we can create a number of
`fascinating textures; see Exercises 20.2 and 20.3. Perlin has extended solid textures to allow
`the modification of geometry as well [PERL89). Some examples of the results are shown in
`Color Plates IV.8 and IV.9.
`Peachey [PEAC85] uses somewhat different mechanisms for specifying solid textures.
`One of the most interesting is what he calls projection textures, although the term
`"extrusion textures" might apply as well. ln such textures, the value of the teltture function
`is constant along certain parallel lines in the volume. For example, such a texture might be
`constant along each line parallel to the z axis, while on any (x, y)-plane cross-seetion it
`might look like a conventionai2D texture. The effect is like that of a (nonperspective) slide
`projector: When someone walks in front of the screen, the image is mapped onto the person
`instead of onto the screen. These textures are most interesting when several are combined.
`If the teJttures are constant along different lines, the results can effectively simulate
`completely random textures. The textures in Color Plate IV. 10 are all based on projection
`textures.
`
`20.2 PROCEDURAL MODELS
`
`Procedural models describe objects that can interact with external events to modify
`themselves. Thus, a model of a sphere that generates a polygonal representation of the
`sphere at a requested fineness of subdivision is procedural: The actual model is determined
`by the fineness parameter. A model that determines the origin of its coordinate system by
`requesting information from nearby entities is also procedural. A collection of polygons
`speci lied by their vertices is not a procedural model.
`Procedural models have been in use for a long time. One of their best features is that
`they save space: It is far easier to say "sphere with 120 polygons" than to list the 120
`polygons explicitly. Magnenat-Thalman and Thalman [MAGN85] describe a procedural
`model for bridges in which a bridge consists of a road, a superstructure, piers, and parapets,
`and is specified by giving descriptions of these aloqg with an orientation to determine the
`bridge's position. Each of the pieees (road, piers, etc.) is specified by a number of
`parameters (length of the road, number of joints in the road, height of the pier, etc.) and the
`procedure then generates the model from these. This is akin to the primitive instancing of
`Chapter 12, but differs in that the geometric or topological nature of the object may be
`influenced by the parameters. Also, the model generated does not need to consist of a
`collection of solids; it might be a collection of point light sources used to exhibit the bridge
`in a night scene, for instance. In any case, specifying a few parameters leads to the creation
`of a very large model. In the case of the bridge, the only things created are various sorts of
`bridges. In subsequent procedural models, such as particle systems, however, highly
`
`1080
`
`

`
`20.2
`
`Procedural M odels
`
`1019
`
`variable classes of objects are supported under a single class of procedures.
`One important aspect of procedural models is their ability to interact with their
`environment. Amburn, Grant, and Whitt.ed introduce two eKtensions to standard procedur(cid:173)
`al models: a communication method through which independent procedures can influence
`one another's behaviors, and a genera.lization of the notion of subdivision to include a
`change of representation [AMBU86].
`lnterobject communication can be used to control the shapes of objects defined by
`procedures. Amburn, Grant, and Whitted use as an eKample a road passing through wooded
`terrain. The terrain is generated by stochastic subdivision of triangles (see Section 20.3),
`the trees are generated using grammar-based models (see Section 20.4), and the road is
`generated by eKtrusion of a line along a spline path. At the top level, the road must follow
`the geometry of the terrain. At a finer level of detail, however, the terrain is bulldozed to let
`the road be smooth. Each of these objects thus must control the other. The bases of the trees
`must be placed on the terrain, but not too close to the road. To execute this interobject
`control, each of the subdivision procedures proceeds for a few steps, then checks its
`progress against that of the others.
`This interobject checking can be eKtremely expensive; the road may be modeled with
`hundreds of rectangles and the terrain with thousands of triangles. Checking for
`intersections among these and establishing communications between each pair is prohibi(cid:173)
`tively laborious. lnstead, during the construction of the road, bounding boKes for the road,
`for each pair of control points for the road, and for each segment of the road were
`constructed. Similar bounding boxes were maintained during the subdivision of the
`triangles. As soon as the bounding box of a child triangle no longer intersected that of the
`road, communications between the two were severed. Thus, there were only a few overlaps
`at the finest level of subdivision.
`These subdivisions were also subject to changes of representation. At some point in a
`subdivision process, the current model representation may no longer seem adequate to the
`modeler; and the modeler (or some other procedure in the model) may request that some
`procedural object change its representation. Thus, a shape that is initially modeled with
`Bezier spline patches, recursively subdivided, may at some point be altered to implement
`further changes using stochastic subdivision to make a ''crinkly'' material of some specific
`overall shape. Amburn, Grant, and Whitted store these changes of representation in a script
`associated either with the individual object or with the class of the object; the script might
`say, for example, "At the third level of subdivision, change from Bezier to stochastic. At
`the fifth level, change to a particle system representation. " The human modeler is also
`allowed to interact with the objects as the procedural modifications take place. Our hope is
`that, in the future, such interactions will no longer be necessary, and that the models will be
`able to determine for themselves the best possible representation.
`Most of the remaining models in this chapter are procedural in some way. Many of
`them are generated by repeated subdivision or repeated spawning of smaller objects. The
`subdivis.ion terminates at a level determined by the modeler, the model , or (depending on
`implementation) the renderer, which can request that no subpixel artifacts be generated, for
`example. The power of these models is manifested in how they amplify the modeler's effort:
`Very small changes in specifications can result in drastic changes of form. (Of course, this
`can be a drawback in some cases, if the modeler cannot direct a tiny change in the result.)
`
`1081
`
`

`
`1 020
`
`Advanced Modeling Techniques
`
`20.3 FRACTAL MODELS
`
`Fractals have recently attracted much attention (VOSS87; MAND82; PEIT86]. The images
`resulting from them are spectacular, and many different approaches to generating fractals
`have been developed. The term fractal has been generalized by the computer graphics
`community to include objects outside Mandelbrot's original definition. It has come to mean
`anything which has a substantial measure of exact or statistical self-similarity, and that is
`how we use it here, although its precise mathematical definition requires statistical
`self-similarity at all resolutions. Thus, only fractals generated by infinitely recursive
`processes are true fractal objects. On the other hand, those generated by finite processes
`may exhibit no visible change in detail after some stage, so they are adequate approxima(cid:173)
`tions of the ideal. What we mean by self-similarity is best illustrated by an example, the von
`Koch snowflake. Starting with a line segment with a bump on it, as shown in Fig. 20.4, we
`replace each segment of the line by a figure exactly like the original line. This process is
`repeated: Each segment in part (b) of the figure is replaced by a shape exactly like the entire
`figure. (It makes no difference whether the replacement is by the shape shown in part (a) or
`by the shape shown in part (b); if the one in part (a) is used, the result after 2• steps is the
`same as the result after n steps if each segment of the current figure is replaced by the entire
`current figure at each stage.) If this process is repeated infinitely many times, the result is
`said to be self-similar: The entire object is similar (i.e., can be translated, rotated, and
`scaled) to a subportion of itself.
`An object that is not exactly self-similar may still seem fractal; that is, it may be
`substantially self-similar. The precise definition of statistical self-similarity is not necessary
`here- we need only to note that objects that "look like" themselves when scaled down are
`still called fractal.
`Associated with this notion of self-similarity is the notion of fractal dimension. To
`define fractal dimension, we shaiJ examine some properties of objects whose dimension we
`know. A l.ine segment is ID; if we divide a line into N equal parts, the parts each look like
`the original I ine scaled down by a factor of N = N JJ1. A square is 20: if we divide it into N
`parts, each part looks like the original scaled down by a factorofvN = N112• (Foreltample,
`a square divides nicely into nine subsquares; each one looks I ike the original scaled by a
`factor oft.) What about the von Koch snowflake? When it is divided into four pieces (the
`pieces associated with the original four segments in Fig. 20.4a), each resulting piece looks
`like the original scaled down by a factor of 3. We would like to say it bas a dimension d,
`where 411d = 3. The value of d must be Jog(4)/log(3) = 1.26 .... This is the definition of
`fractal dimension.
`
`(a)
`
`(b)
`
`(c)
`
`Fig. 20.4 Construction of the von Koch snowflake: each segment in (a) is replaced by
`an exact copy of the entire figure, shrunk by a factor of 3. The same process is applied
`to the segments in (b) to generate those in (c).
`
`1082
`
`

`
`20.3
`
`Fractal Models
`
`1021
`
`Fig. 20.5 (a) The Julia-Fatou set for c = -0.12375 + 0 .056805i; (b) the Jutia-Fatou
`set for c = -0.012 + 0 .74i.
`
`The most famous two fractal objects deserve mention here: the Julia-Fatou set and the
`Mandelbrot set. These objects are generated from the study of the rule x -+ .1- + c (and
`this is the simplest and best known). Here x is a complex
`many other rules as well-
`number,3 x =a + bi. If a complex number has modulus< I, then squaring it repeatedly
`makes it go toward zero. If it bas a modulus > I, repeated squaring makes it grow larger
`and larger. Numbers with modulus I still have modulus I after repeated squarings. Thus.
`some complex numbers "fall toward zero" when they are repeatedly squared, some "fall
`toward infinity, " and some do neither-the last group forms the boundary between the
`numbers attracted to zero and those attracted to infinity.
`Suppose we repeatedly apply the mapping x --. .1- + c to each complex number x for
`some nonzero value of c, such as c = - 0.12375 + 0 .056805i; some complex numbers will
`be attracted to infinity, some will be attracted to finite numbers, and some will go toward
`neither. Drawing the set of points that go toward neither, we get the Julia-Fatou set shown
`in Fig. 20.5(a).
`Notice that the region in Fig. 20.5 (b) is not as well connected as is that in part (a) of
`the figure. In part (b), some points fall toward each of the three black dots shown, some go
`
`•tr you are unfamiliar with complex numbers, it suffices to treat i as a special symbol and merely to
`know the definitions of addition and multiplication of complex numbers. lf t = c + di is a second
`complex number, then x + z is defined to be (a + c) + (b + d)i, and xz is defined to be (ac - bd) +
`(ad + bc)i. We can represent complex numbers as points in the plane by identifying the point (a, b)
`with the complex number (a + bi). The modulus of the number a + bi is the real number (lr + iJ)'",
`which gives a measure of the "size" of the complex number.
`
`1083
`
`

`
`1022
`
`Advanced M odeling Techniques
`
`to infinity. and some do neither. These last points are the ones drawn as the outline of the
`shape in part (b). The shape of the Julia-Fatou set evidently depends on the value of the
`number c. If we compute the Julia sets for all possible values of c and color the point c black
`when the Julia-Fatou set is connected (i.e, is made of one piece, not broken into disjoint
`"islands") and white when the set is not connected, we get the object shown in Fig. 20.6,
`which is known as the Mandelbrot set. Note that the Mandelbrot set is self-similar in that,
`around the edge of the large disk in the set, there are several smaller sets, each looking a
`great deal like the large one scaled down.
`Fortunately, there is an easier way to generate approximations of the Mandelbrot set:
`For each value of c, take the complex number 0 = 0 + Oi and apply the process x-+ J! + c
`to it some finite number of times (perhaps 1000). If after this many iterations it is outside
`the disk defined by modulus < I 00, then we color c white; otherwise, we color it black. As
`the number of iterations and the radius of the disk are increased, the resulting picture
`becomes a better approximation of the set. Peitgen and Richter [PEIT86] give explicit
`directions for generating many spectacular images of Mandelbrot and Julia-Fatou sets.
`These results are extremely suggestive for modeling natural forms, since many natural
`objects seem to exhibit striking self-similarity. Mountains have peaks and smaller peaks
`and rocks and gravel, which all look similar; trees have limbs and branches and twigs,
`which all look similar; coastlines have bays and inlets and estuaries and rivulets and
`drainage ditches, which all look similar. Hence, modeling self-similarity at some scale
`seems to be a way to generate appealing-looking models of natural phenomena. The scale at
`which the self-similarity breaks down is not particularly important here, since the intent is
`modeling rather than mathematics. ThlL~, when an object has been generated recursively
`through enough steps that all further changes happen at well below pixel resolution, there is
`no need to continue.
`Fournier, Fussell, and Carpenter [FOUR82] developed a mechanism for generating a
`class of fractal mountains based on recursive subdivision. It is easiest to explain in 10.
`
`Fig. 20.6 The Mandelbrot set. Each point c in the complex plane is colored black if the
`Julia set for the process x -+ II- + c is connected.
`
`1084
`
`

`
`20.3
`
`y
`
`Fractal Models
`
`1023
`
`y
`
`y
`
`~------------L----. x
`0
`
`0
`
`X
`
`0
`
`X
`
`(a)
`
`(b)
`
`(c)
`
`Fig. 20.7 (a) A line segment on the x axis. (b) The midpoint of the line has been
`translated in they direct ion by a random amount. (c) The result of one further iteration.
`
`Suppose we start with a tine segment lying on the x axis, as shown in Fig. 20. 7(a). lf we
`now subdivide the line into two halves and then move the midpoint some distance in they
`direction, we get the shape shown in Pig. 20.7(b). To continue subdividing each segment,
`we compute a new value for the midpoint of the segment from (x,, y,) to (x,. 1, y .. ,) as
`follows: x,... = i{.x; + x, . 1), y_ = t(y, + y,. ,) + P(.x;., - x;) R(x.,..), where PO is a
`function determining the extent of the perturbation in terms of the size of the line being
`perturbed, and R() is a random number' between 0 and 1 selected on the basis of x,_ (see
`Fig. 20. 7c). If P(s) = s, then the first point cannot be displaced by more than 1, each of the
`next two points (which are at most at heightia!ready) cannot be displaced by more than t.
`and so on. Hence, all the resulting points fit in the unit square. For P(s) = t', the shape of
`the result depends on the value of a; smaller values of a yield larger perturbations, and vice
`versa. Of course, other functions, such as P(s) = 2 -•, can be used as well.
`Fournier, Fussell, and Carpenter use this process to modify 20 shapes in the following
`fashion. They start with a triangle, mark the midpoint of each edge, and connect the three
`midpoints, as shown in Fig. 20.8 (a). They coordinate of each midpoint is then modified in
`the manner we have described, so that the resulting set of four triangles looks like Fig. 20.8
`(b). This process, when iterated, produces quite realistic-looking mountains, as shown in
`Color Plate IV .11 (although, in an overhead view, one perceives a very regular polygonal
`structure).
`Notice that we can start with an arrangement of triangles that have a certain shape, then
`apply this process to generate the finer detail. This ability is particularly important in some
`modeling applications, in which the layout of objects in a scene may be stochastic at a low
`level but ordered at a high level: The foliage in an ornamental garden may be generated by a
`stochastic mechanism, but its arrangement in the garden must follow st