|
What do recursive drawing, iterated function systems, and fractal geometry have in common? They all play a part in producing realistic looking natural objects.
July 01, 1991
URL:http://www.drdobbs.com/architecture-and-design/recursive-images/184408581
Copyright © 1991, Dr. Dobb's Journal
Copyright © 1991, Dr. Dobb's Journal
Copyright © 1991, Dr. Dobb's Journal
Copyright © 1991, Dr. Dobb's Journal
Copyright © 1991, Dr. Dobb's Journal
Steven is an associate professor of mathematics at Colorado College in Colorado Springs, C0 80903. His interests include computer graphics and probabilistic algorithms. Steven's Bitnet address is: SJANKE%CCNODE @COLORADO.
The world of images seems to divide up into those that we can draw easily on a computer and those that seem almost impossible. Buildings, pie charts, and cars are relatively straight forward, whereas clouds, trees, and mountains are quite another matter. With scanners, of course, most images can be put on the screen, but then storage requirements soar and manipulation routines are often awkward. It is much more efficient and aesthetically pleasing when we can write just a few lines of code to generate the images we want. Because there are nice algorithms for lines and circles, anything that can be described with our standard Euclidian geometry seems easy to draw. Yet standard geometry falls short when describing trees (organic trees, not data structures!) and other natural objects that are randomly bumpy, wiggly, and intricate. In the last decade or so, a new geometry, called "fractal geometry," has emerged to do a better job of describing natural objects.
The main idea behind the fractal geometry view is that some images look like they are made up of small copies of themselves. A single branch of a real tree often looks like the entire tree. A small piece of a cloud looks like the entire cloud. These recursive descriptions (called "self-similarity") can be worked into an algorithm and coded easily to draw some natural-looking objects with relative ease.
Recursion is most often thought of in the context of a recursive procedure -- a procedure that calls itself. The output of a procedure becomes the input of the same procedure. In mathematical terms, the output of some function becomes the input of that same function. This process is then iterated an arbitrary number of times. To see this in action, let's first look at the recursive approach to drawing a tree and then turn to the slightly more complex approach of using Iterated Function Systems (IFS). This second technique is the focus of much current research in image compression and is proving to be a more general technique than seems obvious at first glance.
The observation that one branch of a tree often looks like the entire tree leads almost immediately to an effective algorithm. The main procedure, called TREE, must draw a branch of the tree that will then split into a few subbranches. We can draw a piece of the tree by indicating the starting point, a direction, and a length. Then we let TREE call itself with new starting points, new directions, and new lengths in order to produce subbranches. Listing One, page 74, gives a Tur
There are four parameters for procedure TREE: The first two give the starting position, the third gives the direction (that is, angle), and the fourth is the level of recursion. The length of a branch is not given as a parameter: It is calculated by knowing the current position in the tree. The trunk is the longest, and the branches at the top of the tree are the smallest. The LEVEL parameter is used both to indicate the depth of recursion and to calculate the length of the current branch.
After drawing a branch, TREE calls itself twice with new starting points and directions. This means that each branch splits into two subbranches. Because LEVEL is decremented on each recursive call, it can be tested to stop the recursion. Ten levels of recursion seem to give a reasonable image.
Now for the artistic refinements.... It is a simple matter to draw the main branches in brown and the final branches in green to indicate leaves. Or you may choose to write a subprocedure for drawing more recognizable leaves. Perhaps the most realistic refinement is the addition of randomness. The branching direction can be randomly distributed within a range, the length of a branch can be random, and the number of branches can be randomly chosen to be, say, two or three. RECURTRE uses a simple random element to govern branching direction, so rather than producing symmetrical, uniform trees, it produced trees such as the one shown in Figure 1. With just a little more effort, the branches can be given thickness and support flowers or fruit.
It takes some practice, but by altering the range of branching angles, the distribution of those angles, and the distribution of branch lengths, you can draw a wide variety of tree shapes. The overall shape of real trees varies from the triangular shape of fir trees to the more spherical shape of oak trees to the somewhat cylindrical shape of poplar trees. For an intriguing problem, try determining what parameters really govern the final shape of the tree.
Recall again that recursion simply means that the output of a function becomes the input for the same function. In the RECURTRE program (Listing One), the inputs and outputs are branches. The TREE procedure takes the description of a branch as an input and outputs descriptions of two branches. Each of the new branches is then input into the procedure again. Rather than use branches as inputs and outputs, it is also possible to focus on individual pixels. This way, procedures (or functions) take a single pixel as input and output one more pixel. Then the sequence of pixels generated should form an interesting image.
(A note on terminology: Usually, a function that moves pixels around the screen is referred to as a transformation. Because transformation is the term used most often in the technical literature, it makes sense to use it here.)
Let's consider a transformation that takes a point on the screen with coordinates (X,Y) and simply multiplies each coordinate by one-half. Then, if the input to the transformation is (100,200) the output is (50,100); with (50,100) as the input, the output is (25,50). This process, which always makes the current output the next input, generates a sequence of points. In the present case, it is easy to see that the sequence of points approaches (0,0). Notice that if (0,0) is then made the input of the transformation, the output is also (0,0). The point (0,0) is called a "fixed point" of the transformation. Plotting the sequence of points on the screen gives pixels on a straight line, which get closer together as they approach the origin.
Take another transformation that again multiplies the coordinates of a point by one-half, but also adds 10 to the X coordinate. This time, the point (20,0) is a fixed point because one-half of 20 plus 10 gives 20 back. The sequence of plotted points bunches up as it approaches (20,0). Notice one important fact: No matter which point you start with, the sequence always approaches the fixed point. This is somewhat amazing, but true. You can start anywhere you like on the screen and still be confident that the sequence will get closer and closer to the fixed point.
Now imagine that there are two transformations, say, T1 and T2. Start with some point, P, and apply both functions to this point. The result will be two new points: Call them A and B. Then take these new points and drop them into each of the two transformations. T1 operates on A and B to produce two new points, and T2 operates on A and B to give two new points. At this stage of the game there are points P, A, B, and four new points. T1 and T2 can now operate on the four new points to produce eight newer points. Continuing in this way, the transformations build a set of points on the screen.
In this set of plotted points, there is a sequence of points that approaches the fixed point of T1. This is because there is a sequence of points where only T1 has been applied. Similarly, there is also a sequence that approaches the fixed point of T2. Moreover, consider a new transformation, T3, which moves points by first applying T1 and then applying T2. In the set of plotted points, you can also find a sequence that approaches the fixed point of T3. In fact, if you plot enough points, you will have sequences that approach the fixed point of any finite combination of our original two transformations!
This is beginning to look interesting. One starting point and two simple transformations give what could be a complicated set of points on the screen. Maybe there is an interesting image forming here. With a little more mathematics, it becomes clear that there is a unique set, call it "S," that has a nice property. If you pick any arbitrary point of S and apply either of the two transformations, you get another point of S. S is called an attractor for the two transformations T1 and T2. The set of points plotted on the screen is an approximation of S. If you are lucky enough to start with a point in S, you will stay in S. If you start with a point outside S, some of the first points plotted may not be very close to S, but points further along in the sequence do get closer to S. The more points you plot, the more detail you will get. Often the set S has intricate detail and is called a "fractal."
Before going much further, notice one unfortunate fact. At each stage of the algorithm there are twice as many new points as at the previous stage! The exponential nature of this generation makes the algorithm impractical. But there is a secret door: It turns out that instead of applying each of the transformations T1 and T2 to the new set of points, you can flip a coin and choose one of them to apply. This way only one new point is generated at each stage, and the algorithm is saved. The amazing fact is that by using this "Random Algorithm" you still get a picture of S! Although the algorithm incorporates randomness, the resulting image always looks the same.
Let's see what we have so far. A couple of transformations plus a starting point produce a rather complicated set of points. T1 and T2 are simple transformations, but imagine transformations that move points in such a way that they shrink images, or rotate images, or translate images, or skew images, and so on. Choose some of them to form a special set. When applying the Random Algorithm, you must randomly pick one of the transformations from the special set to apply next. The selection can be made by giving equal weight to each transformation in the set, or you can decide to pick some of the transformations more often than the others. To implement a general-selection technique, simply assign a probability to each transformation to determine how often it is picked. With two transformations, if the first is assigned a probability of two-thirds, it will be picked twice as often as the second. The set of transformations plus the set of probabilities is referred to as the IFS.
A brief historical note: The Australian mathematician John Hutchison developed most of the theoretical basis for iterated function systems about eight years ago. Since then, Michael Barnsley (Georgia Institute of Technology; Iterated Systems) noticed the connection to graphics and developed the Random Algorithm. Barnsley has been the most profit contributor to the field in the last several years.
The discussion so far would be of little interest if the attractors S were just a boring set of pixels. So look at Figure 2. This is a common example called the "Sierpinski triangle." The IFS that produced this image has three transformation with probability one-third assigned to each of them. This attractor is not very organic looking, but it is rather complicated -- and only three transformations are needed to describe it.
There is a restriction on the transformations allowed in an IFS: They must be what are called "contractions." If a transformation from an IFS is applied to two pixels on the screen, the distance between the two new pixels must be less than the distance between the original two pixels. This means that the transformation shrinks things. It may also rotate or translate, but a little shrinking is necessary. There are a lot of these contractions in the world, but for practical purposes it suffices to restrict attention to transformations that can be described as follows: Let the input point have coordinates (X,Y), and suppose the output point has coordinates (Xnew, Ynew), where
Xnew = a*X + b*Y + c
Ynew = d*X + e*Y + f
The six numbers a,b,c,d,e,f describe the transformation; an appropriate data structure here might be a 2 x 3 array with a,b,c in the first row and d,e,f in the second. The numbers a,b,d,e determine how the transformation shrinks and rotates figures while the numbers c and f determine how figures are translated around the screen. Because translation is dependent on the scale you choose, the actual values of c and f are not important. If the unit distance is one inch, then c and f will have smaller values than if the unit distance is one pixel. The important factor is the ratio of c to f.
Note that an arbitrary selection of the six numbers will certainly describe a transformation, but it may not be a contraction. In practice, it is usually easier to look at the effect of the transformation to see if it shrinks things, rather than to worry whether the particular selection of six numbers is theoretically allowed.
Listing Two, page 74, presents a program for implementing the Random Algorithm for iterated function systems. For simplicity, the transformations are designated in a constant declaration along with the probabilities. Starting with the initial point (0,0), which is mapped to a prixel in the middle of the screen, the program generates several thousand new points and plots them. Each new point is determined by randomly selecting one of the functions in the IFS using the given probabilities and then applying the chosen transformation to the current point. Simply change the constant declaration to produce the attractor for other IFSs.
Table 1 gives the transformations and probabilities for generating the Sierpinski triangle -- a fern leaf (which is the image most often associated with IFSs) and a tree. When reading the table, keep in mind that it is the ratio of c to f that is important, not their actual values. Figure 3 shows a more organic looking tree, which is the attractor for the IFS given in the table. It should be clear that the relatively small amount of space necessary to save the transformations makes the IFS technique singularly important in image compression applications.
a b c d e f prob
----------------------------------------------------------------------------
Sierpinski Triangle:
T1 0.5 0 0 0 0.5 0 0.33
T2 0.5 0 100 0 0.5 0 0.33
T3 0.5 0 50 0 0.5 -100 0.33
Fern:
T1 0 0 0 0 0.16 0 0.02
T2 0.2 -0.26 0 0.23 0.22 -24 0.065
T3 -0.15 0.28 0 0.24 -6.6 0.065 0.26
T4 0.85 0.04 0 -0.04 0.85 -24 0.85
Tree:
T1 0.04 0 0 0 0.36 21 0.02
T2 0.04 0 8 0 0.36 21 0.02
T3 0.4 0 4 0 0.4 -27 0.20
T4 0.54 0.09 -4 0.11 0.44 -105 0.34
T5 0.34 0.29 -24 -0.29 0.34 -45 0.21
T6 0.22 -0.45 36 0.48 0.25 -60 0.21
There is still an outstanding practical problem. How do you go from a desired image to the appropriate IFS? This task is still an art, but there is an extremely useful technique developed by Barnsley. To understand it, let's consider again a transformation from an IFS. Because the transformation moves pixels around the screen, it has an effect on shapes. For example, if you take a triangle on the screen and apply the transformation to the points on the triangle, you get a new triangle. Because the transformation is a contraction, the new triangle is a little smaller than the original and it may be skewed, rotated, or translated. It is useful to visualize transformations by plotting their effects on simple shapes.
All transformations in the IFS for the Sierpinski triangle shrink things to half their original size. Then two of the transformations translate the resulting images either over to the right or over to the right and up. You can guess what the transformations do by looking at the picture and noticing that there are triangles inside triangles. Moreover, the smaller triangles have sides that are half the size of the sides enclosing them.
Now here is Barnsley's technique. Start with a rough outline of the image you want. Apply a transformation, and look at the result. Maybe it shrinks the outline and rotates a little. Pick transformations so that their results effectively cover the original outline with smaller copies of itself. This is the self-similarity! If you cover your outline carefully enough, the resulting IFS will produce the desired image. This fact is called the "Collage Theorem," because a collage of shapes makes up the final image (see Figure 4).
Listing Three, page 74, presents a development system for designing iterated function systems by utilizing the Collage Theorem. The system has three sections. In section 1, the user draws the outline of the desired image on the screen. This is done simply by moving a cursor around and pressing the appropriate key when you wish to set a vertex.
In section 2, the user actually builds the appropriate transformations by observing their effect on the original outline. The array of coefficients describing the transformation is displayed in the upper-left corner of the screen. By shrinking, rotating, and translating in various ways, the user tries to cover the original outline using as many transformations as necessary. The more accurate the cover, the closer the IFS approximates the intended image.
After fixing the various transformations, the user moves to section 3 where the Random Algorithm is used to produce the attractor for the IFS. At this point, the user may choose to have the original outline on the screen for comparison. Also by selecting color, the pixels will be plotted in a color corresponding to the last transformation applied. For example, if transformation 2 is picked randomly to apply, then the resulting pixel is colored with color number 2. The coloring simply gives the user a better idea of how the IFS is working.
In section 3, the program actually calculates a set of probabilities for the IFS. This is done simply by determining how much each transformation shrinks images and then assigning lower probability to those that shrink the most. (For the mathematically inclined, the determinant of the transformation's array is calculated.) This technique for assigning probabilities is by no means unique or optimal. It is merely a practical way to get a more or less uniform image. Other probability assignments can give interesting control over the image, as discussed shortly. Once probabilities are calculated, the Random Algorithm begins. Remember, you really can begin anywhere you wish. The program selects the point (0,0) as the starting point. You may wish to try other starting points to see if there is an effect on the image.
The program in Listing Three is fairly straightforward. A simple user interface was chosen to keep the complexity down. In the final image, 3000 points are plotted, but this can easily be increased or decreased by changing the value of the variable NM in the main body of the GENERATE procedure. One of the final options is to save the transformations. Each transformation is stored as a 2 x 3 array on the data file.
There are several generalizations of the IFS technique that lead to more realistic images. Three of them are particularly interesting.
First, the selection of probabilities can give enough control over the image to allow for color or gray-scale rendering. The idea is this: As the sequence of points is generated, some areas of the screen are "hit" more often than others. In fact, some pixels are plotted more than once. By setting the color of a screen area according to how many times it is hit, you can produce a color image. Then, by adjusting the probabilities and perhaps adding or deleting transformations, you can shade your image in various ways.
For the very intrepid, a second generalization is useful. The transformations talked about so far are transformations that move points in the plane. But there is no reason to restrict the technique to two dimensions. If you take transformations that move points in space, then you have a three-dimensional attractor. With an appropriate rendering algorithm, this image could look more realistic than the two-dimensional ones.
Finally, two IFSs can be mixed in interesting ways. Listing Four, page 78, produces the forest of ferns shown in Figure 5 by mixing the transformations for a fern with two more transformations that give the forest shape. Basically, the fern is drawn using the Random Algorithm, but with probability one-third of the two other transformations that are invoked. One key to this particular mixing method is that the algorithm keeps track of where it was in the fern before invoking the forest transformations. After using the forest transformations, the algorithm returns to the previous point in the fern.
There are exciting possibilities with IFSs and several unsolved problems, both theoretical and practical. Yet it is easy to get in the middle of this fractal landscape of images by doing a little experimenting on your own.
Barnsley, Michael. Fractals Everywhere. San Diego, Calif.: Academic Press, 1988.
Mandelbrot, Benoit. The Fractal Geometry of Nature. San Francisco, Calif.: W.H. Freeman, 1982.
Peitgen, Heinz-Otto and Dietmar Shaupe, editors. The Science of Fractal Images. New York, N.Y.: Springer-Verlag, 1988.
_RECURSIVE IMAGES_ by Steven Janke[LISTING ONE]
PROGRAM RECURTRE;
uses graph;
var inc,firstdirection :real;
gd,gm,depth,scale :integer;
startx,starty :integer;
xasp,yasp :word;
asp :real;
const pi:real=3.14159;
procedure TREE(X,Y:integer; DIR:real; LEVEL:integer);
var xnew,ynew:integer;
begin
if level>0 then {At level zero, recursion ends.}
begin
xnew:= round(level*scale*cos(dir))+x; {Multiplying by level }
ynew:= round(asp*level*scale*sin(dir))+y; {varies the branch size.}
if level<3 then setcolor(green) else setcolor(brown); {Green leaves}
line(x,y,xnew,ynew);
TREE(xnew,ynew,dir+random*inc,level-1); {Two recursive calls - one}
TREE(xnew,ynew,dir-random*inc,level-1); {for each new branch.}
end;
end;
procedure INIT;
begin
firstdirection:=-pi/2; {Negative since y increases down the screen.}
inc:=pi/4;
scale:=5;
depth:=10;
startx:=round(GETMAXX/2); starty:=round(0.75*GETMAXY);
GETAspectRatio(xasp,yasp); asp:=xasp/yasp; {Find aspect ratio}
end;
BEGIN
gd:=detect;
initgraph(gd,gm,'\tp\units'); {Graphic drivers kept in \tp\units.}
cleardevice; randomize;
INIT;
TREE(startx, starty, firstdirection, depth);
readln;
closegraph;
END.
[LISTING TWO]
PROGRAM IFSDRAW; {Random Algorithm for drawing IFS attractor.}
uses graph;
var gd, gm :integer; {For graphics initialization}
xoff, yoff :integer; {Offset to determine origin}
xsc, ysc :real; {Scale variables}
n, cl :integer; {Index variable, color variable}
x,y,asp :real; {Starting point and aspect ratio}
xasp,yasp :word; {Used to determine aspect ratio}
const {Normally, these constants would be read from a data file. They
are listed as constants here only for illustration. These
particular transformations form an IFS for Sierpinski's triangle.}
Totaltran:integer=3;
CT:array[1..3,1..7] of real =
{Format: a, b, c, d, e, f, probability}
(( 0.5, 0, 0, 0, 0.5, 0, 0.33),
( 0.5, 0, 100, 0, 0.5, 0, 0.33),
( 0.5, 0, 50, 0, 0.5, -100, 0.33));
procedure SETPROB;
{To get a running sum of the probabilities for random number generation.}
var i:integer;
sum:real;
begin
sum:=0;
for i:=1 to totaltran-1 do
begin sum:=sum+CT[i,7]; CT[i,7]:=sum; end;
CT[totaltran,7]:=1; {This is set to 1 to avoid any round-off problem.}
end;
procedure MAKETRAN;
{Determine which transformation is next and then apply it.}
var nx,ny:real;
s:integer;
function FINDTRAN:integer;
{Return a random number between 1 and the number of transformations.}
var i:integer;
w:real;
begin
w:=random; i:=1;
while w>CT[i,7] do i:=i+1;
FINDTRAN:=i;
end;
begin
S:=FINDTRAN;
NX:=CT[S,1]*X + CT[S,2]*Y + CT[S,3];
NY:=CT[S,4]*X + CT[S,5]*Y + CT[S,6];
X:=NX; Y:=NY;
end;
procedure INIT;
begin
XSC:=1; YSC:=1; {Scale factors}
XOFF:=round(GETMAXX/2); YOFF:=round(GETMAXY/2); {Determines origin}
X:=0; Y:=0; {Starting point}
cl:=white;
GETAspectRatio(xasp,yasp); {BGI function for determining aspect ratio}
asp:=xasp/yasp;
end;
BEGIN
gd:=detect; initgraph(gd,gm,' '); cleardevice;
INIT; SETPROB;
for N:=1 to 5000 do
begin
MAKETRAN;
putpixel(round(X*XSC)+XOFF, (round(asp*Y*YSC)+YOFF),cl);
end;
readln;
closegraph;
END.
[LISTING THREE]
PROGRAM IFS; {ITERATED FUNCTION SYSTEM DESIGNER}
uses graph,crt;
type matrix = array[1..2,1..3] of real;
var points:array[1..100,1..2] of integer; {Points and Pts store vertices}
pts:array[1..100,1..2] of real; {of main figure.}
gd,gm: integer; {For graphics initialization.}
cp:integer; {Total number of vertices in main figure.}
xoff,yoff:integer; {Offset for main figure placement.}
asp,xt,yt:real; {Aspect ratio and offsets for transformation.}
select:boolean; {For menu selection.}
tran:matrix; {Coefficients of current transformation.}
tranlist: array[1..50] of matrix; {List of transformations}
totaltran:integer; {Total number of transformations.}
procedure APPLYTRAN; {--------------------------------------------}
{Applies the current transformation to the vertices of main figure.}
var i:integer;
a:real;
begin
for i:=1 to cp do
begin
a:=tran[1,1]*pts[i,1]+tran[1,2]*pts[i,2];
pts[i,2]:=tran[2,1]*pts[i,1]+tran[2,2]*pts[i,2];
pts[i,1]:=a;
end;
end;
procedure INIT; {-------------------------------------------------}
var xasp,yasp:word;
begin
cp:=1;
xoff:=round(GETMAXX/2); yoff:=round(GETMAXY/2);
xt:=0; yt:=0;
GETASPECTRATIO(Xasp,Yasp); asp:=xasp/yasp;
totaltran:=0;
end;
procedure INITTRAN; {---------------------------------------------}
begin
tran[1,1]:=1; tran[1,2]:=0; tran[2,1]:=0; tran[2,2]:=1;
end;
procedure SAVETRAN(n:integer); {----------------------------------}
begin
tranlist[n]:=tran;
tranlist[n,1,3]:=xt; tranlist[n,2,3]:=yt;
xt:=0; yt:=0;
end;
procedure CONVPOINTS; {-------------------------------------------}
{Converts screen coordinates in Points to world coordinates in Pts.}
var i:integer;
begin
for i:=1 to cp do
begin
pts[i,1]:=points[i,1]-xoff;
pts[i,2]:=(points[i,2]-yoff)/asp;
end;
end;
procedure DRAWFIG(col:integer); {---------------------------------}
var i,holdcol:integer;
begin
holdcol:=getcolor; setcolor(col);
for i:=1 to cp-1 do
line(round(pts[i,1]+xoff+xt),round(pts[i,2]*asp+yoff+yt*asp),
round(pts[i+1,1]+xoff+xt),round(pts[i+1,2]*asp+yoff+yt*asp));
setcolor(holdcol);
end;
procedure REDRAW(N:integer); {-------------------------------------}
{Redraws orignial figure plus the results of each transformation.}
{Transformation number N is not drawn.}
var i:integer;
begin
xt:=0; yt:=0;
cleardevice; CONVPOINTS; DRAWFIG(blue);
for i:=1 to totaltran do
if i<>n then
begin
CONVPOINTS; tran:=tranlist[i];
xt:=tranlist[i,1,3]; yt:=tranlist[i,2,3];
APPLYTRAN;
DRAWFIG(red);
end;
xt:=0; yt:=0;
end;
procedure SCALE(xsize,ysize:real); {-------------------------------}
{Changes the size of a figure.}
var i,j:integer;
begin
for i:=1 to cp do
begin pts[i,1]:=xsize*pts[i,1];
pts[i,2]:=ysize*pts[i,2];
end;
for i:=1 to 2 do tran[1,i]:=xsize*tran[1,i];
for i:=1 to 2 do tran[2,i]:=ysize*tran[2,i];
end;
procedure POSITION; {---------------------------------------------}
{Positions figure as a new transformation is constructed.}
var k:char;
xx,yy:integer;
procedure DIRECTIONS; {....................................}
begin
gotoxy(1,16); writeln('SCALE (S/W)');
writeln('SCALEX (A/Q)');
writeln('SCALEY (D/E)');
writeln('ROTATE (R/F)');
writeln('ROTATEX (T/G)');
writeln('ROTATEY (Y/H)');
writeln('REFLECT (X)');
writeln('Use ARROWS to translate.');
gotoxy(1,25); write('... Press Enter when finished ...');
end;
procedure REFLECT; {......................................}
{Flips the figure around the line x=y.}
var i:integer;
xx:real;
begin
for i:=1 to cp do
begin xx:=pts[i,1]; pts[i,1]:=pts[i,2]; pts[i,2]:=xx; end;
xx:=tran[1,1]; tran[1,1]:=tran[2,1]; tran[2,1]:=xx;
xx:=tran[1,2]; tran[1,2]:=tran[2,2]; tran[2,2]:=xx;
end;
procedure ROTATE(xangle,yangle:real); {...................}
{Rotates the figure. If xangle and yangle are unequal, rotation}
{is skewed.}
var i,j:integer;
a,b,xca,xsa,yca,ysa:real;
begin
xca:=cos(xangle); xsa:=sin(xangle);
yca:=cos(yangle); ysa:=sin(yangle);
for i:=1 to cp do
begin
a:=pts[i,1]*xca-pts[i,2]*ysa;
pts[i,2]:=pts[i,1]*xsa+pts[i,2]*yca;
pts[i,1]:=a;
end;
a:=tran[1,1]*xca-tran[2,1]*ysa;
b:=tran[1,2]*xca-tran[2,2]*ysa;
tran[2,1]:=tran[1,1]*xsa+tran[2,1]*yca;
tran[2,2]:=tran[1,2]*xsa+tran[2,2]*yca;
tran[1,1]:=a; tran[1,2]:=b;
end;
procedure WRITETRAN; {......................................}
var i,j:integer;
begin
gotoxy(1,3); writeln('Current Transformation: ');
for i:=1 to 2 do
begin
for j:=1 to 2 do
begin
gotoxy(1+(j-1)*10, 5+(i-1));
writeln(tran[i,j]:7:2);
end;
gotoxy(21, 5+(i-1));
if i=1 then writeln(xt:7:2) else writeln(yt:7:2);
end;
end;
begin
xx:=round(xt); yy:=round(asp*yt);
WRITETRAN; DIRECTIONS;
k:=readkey;
while ord(k)<>13 do
begin
DRAWFIG(green);
case ord(k) of
0: begin
k:=readkey;
case ord(k) of
72: yy:=yy-3;
77: xx:=xx+4;
80: yy:=yy+3;
75: xx:=xx-4;
end;
end;
83,115: scale(0.9,0.9); { S for decrease }
87,119: scale(1.1,1.1); { W for increase }
65,97 : scale(0.9,1); { A for x decrease }
68,100: scale(1,0.9); { D for y decrease }
81,113: scale(1.1,1); { Q for x increase }
69,101: scale(1,1.1); { E for y decrease }
82,114: rotate(0.1,0.1); { R for rotate cw }
70,102: rotate(-0.1,-0.1); { F for rotate ccw }
84,116: rotate(-0.1,0); { T for x rotate cw }
71,103: rotate(0.1,0); { G for x rotate ccw }
89,121: rotate(0,-0.1); { Y for y rotate cw }
72,104: rotate(0,0.1); { H for y rotate ccw }
88,120: reflect; { X to reflect in x=y }
end;
xt:=xx; yt:=yy/asp; DRAWFIG(green);
WRITETRAN;
k:=readkey;
end;
end;
procedure SHAPE; {-------- SECTION I ------------------------------}
{Sets up the main figure.}
var i,j,er:integer;
k:char;
procedure BOX(x,y,col:integer); {..........................}
var vs,hs,holdcol:integer;
begin
hs:=3; vs:=2; holdcol:=getcolor; setcolor(col);
line(x-hs,y-vs,x+hs,y-vs);
line(x+hs,y-vs,x+hs,y+vs);
line(x+hs,y+vs,x-hs,y+vs);
line(x-hs,y+vs,x-hs,y-vs);
setcolor(holdcol);
end;
begin
gotoxy(1,1); writeln('ITERATED FUNCTION SYSTEM DESIGNER');
writeln('Section I: Draw outline of desired figure ....');
gotoxy(1,23); writeln('Use arrows to position cursor.');
writeln('Press P to place a vertex.');
write('Press Enter when finished.');
i:=xoff; j:=yoff; setwritemode(xorput);
BOX(i,j,white);
k:=readkey; er:=1; {Variable er used to determine when to draw box.}
while ord(k)<>13 do
begin
case ord(k) of
0: begin if er=1 then BOX(i,j,white); er:=1;
k:=readkey;
case ord(k) of
72: j:=j-6;
77: i:=i+8;
80: j:=j+6;
75: i:=i-8;
end;
BOX(i,j,white);
end;
80,112: begin er:=0; points[cp,1]:=i; points[cp,2]:=j;
if cp>1 then begin setcolor(blue);
line(points[cp-1,1],points[cp-1,2],
points[cp,1], points[cp,2]);
setcolor(white); end;
cp:=cp+1;
end;
end;
k:=readkey;
end;
points[cp,1]:=points[1,1]; points[cp,2]:=points[1,2];
setcolor(blue);
line(points[cp-1,1],points[cp-1,2],points[1,1],points[1,2]);
setcolor(white); setwritemode(copyput);
end;
procedure MAKETRAN; {---------- SECTION II ------------------------}
{Allows construction and alteration of transformations.}
var nt,choice:integer;
s,me:char;
function MENUII:integer; {........................................}
var xn:integer;
begin
gotoxy(1,1); writeln('1. Another Transformation');
writeln('2. Next Transformation');
writeln('3. Prepare to Draw');
gotoxy(1,5); writeln('Select Number: '); me:=readkey;
while (ord(me)<49) or (ord(me)>51) do me:=readkey;
MENUII:=ord(me)-48;
gotoxy(1,1);
for xn:=1 to 5 do writeln(' ');
end;
begin
gotoxy(1,1); writeln('Section II: Build Transformations ...');
choice:=1; nt:=0;
if totaltran<>0 then choice:=2;
while choice<>3 do
begin
if choice=2 then
begin nt:=nt+1;
if nt>totaltran then nt:=1;
REDRAW(nt);
tran:=tranlist[nt];
xt:=tranlist[nt,1,3]; yt:=tranlist[nt,2,3];
end
else begin INITTRAN; totaltran:=totaltran+1;
nt:=totaltran;end;
CONVPOINTS;
if choice=2 then APPLYTRAN else SCALE(0.5,0.5);
setwritemode(xorput);
DRAWFIG(green);
POSITION;
setwritemode(copyput);
SAVETRAN(NT);
REDRAW(0);
CHOICE:=MENUII;
end;
cleardevice;
end;
procedure GENERATE; {------------ SECTION III ---------------------}
{Draw the resulting picture by applying transformations at random.}
var xx,nm,wh,bd,cl,choice:integer;
x,y:real;
me:char;
probs:array[1..50] of real;
procedure ASSIGNPROB; {....................................}
{Determines probability of each transformation.}
var i:integer;
s:real;
begin
for i:=1 to totaltran do
begin
tran:=tranlist[i];
probs[i]:=abs(tran[1,1]*tran[2,2] - tran[1,2]*tran[2,1]);
if probs[i]<0.02 then probs[i]:=0.02;
end;
s:=0; for i:=1 to totaltran do s:=s+probs[i];
for i:=1 to totaltran do probs[i]:=probs[i]/s;
s:=0; for i:=1 to totaltran do begin s:=s+probs[i]; probs[i]:=s; end;
probs[i]:=1;
end;
function PICK:integer; {..................................}
{Picks a transformation with designated probability distribution.}
var j:integer;
p:real;
begin
p:=random; j:=1;
while p>probs[j] do j:=j+1;
PICK:=j;
end;
procedure APPLY(w:integer); {..............................}
{Applies chosen transformation to current point X,Y.}
var z:real;
begin
tran:=tranlist[w];
z:=tran[1,1]*X+tran[1,2]*Y;
Y:=tran[2,1]*X+tran[2,2]*Y;
X:=z+tran[1,3];
Y:=Y+tran[2,3];
end;
procedure PUTIT(cc:integer); {.............................}
begin
if cl=0 then cc:=white;
putpixel(round(X+xoff),round(Y*asp+yoff),cc);
end;
procedure MENUIII; {.......................................}
var s:string;
xx:integer;
begin
bd:=0;cl:=0;
gotoxy(1,3); write('1. Border (Toggles)');
gotoxy(25,3); writeln('Excluded');
write('2. Color (Toggles)');
gotoxy(25,4); writeln('No');
writeln('3. Draw Image');
writeln;writeln('Select Number: ');
me:='5';
while (ord(me)<>51) do
begin
me:=readkey;
while (ord(me)<49) or (ord(me)>51) do me:=readkey;
case ord(me) of
49: begin if bd=0 then begin bd:=1; s:='Included'; end
else begin bd:=0; s:='Excluded'; end;
gotoxy(25,3);write(s);
end;
50: begin if cl=0 then begin cl:=1; s:='Yes';end
else begin cl:=0; s:='No ';end;
gotoxy(25,4);write(s);
end;
end;
end;
gotoxy(1,3);
for xx:=1 to 5 do writeln(' ');
end;
begin
cleardevice; ASSIGNPROB; randomize;
gotoxy(1,1); writeln('Section III: Draw Image ... ');
MENUIII;
if bd=1 then begin CONVPOINTS; DRAWFIG(blue); end;
nm:=3000; {Number of points to plotted in final image.}
X:=0;Y:=0; {Initial point drawn.}
PUTIT(7);
for xx:=1 to nm do
begin
wh:=PICK; APPLY(wh); PUTIT((wh mod 7)+1);
end;
end;
procedure FILESAVE;
{To save transformations on disk.}
var i:integer;
tranfile:file of matrix;
begin
assign(tranfile, 'IFS.DAT');
rewrite(tranfile);
for i:=1 to totaltran do write(tranfile, tranlist[i]);
close(tranfile);
end;
function MENUIV:boolean; {.......................................}
var s:string;
me:char;
begin
gotoxy(1,3); writeln('1. Return to Section II');
writeln('2. Save transformations on file');
writeln('3. Quit');
writeln;writeln('Select Number: ');
me:='2';
while me='2' do
begin
me:=readkey;
while (ord(me)<49) or (ord(me)>51) do me:=readkey;
if me='2' then begin FILESAVE;
gotoxy(1,9); writeln('DATA SAVED');
end;
end;
if me='1' then MENUIV:=true else MENUIV:=false;
end;
BEGIN {----------------- Main Body ------------------------------}
gd:=detect; initgraph(gd,gm,'');
directvideo:=false; {Allows text using WRITE statements.}
INIT; cleardevice;
SHAPE; {... Section I ...}
select:=true;
while select do
begin
REDRAW(0);
MAKETRAN; {... Section II ...}
GENERATE; {... Section III ...}
select:=MENUIV;
end;
cleardevice; closegraph;
END.
[LISTING FOUR]
PROGRAM FOREST; {A mixture of two systems to produce a forest of ferns}
uses graph;
var n,xoff,yoff,gd,gm,cl: integer;
xsc,ysc,x,y,bx,by,asp:real;
xasp,yasp:word;
const
{CT holds the IFS for a fern}
CT:array[1..4,1..7] of real =
(( 0, 0, 0, 0, 0.16, 0, 0.02),
( 0.2,-0.26, 0, 0.23, 0.22, -24, 0.065),
(-0.15, 0.28, 0, 0.26, 0.24, -6.6, 0.065),
( 0.85, 0.04, 0,-0.04, 0.85, -24, 0.85));
{PL holds additional IFS functions to produce the forest}
PL:array[1..2,1..6] of real =
(( 0.8, 0, 80, 0, 0.8, -65),
( 0.8, 0, -80, 0, 0.8, -60));
PROB:array[1..6] of real = (0.008, 0.034, 0.06, 0.4, 0.7, 1.0);
procedure MAKETRAN;
var nx,ny:real;
s:integer;
function FINDTRAN:integer;
var i:integer;
w:real;
begin
w:=random; I:=1;
while w>PROB[i] do i:=i+1;
FINDTRAN:=i;
end;
begin
s:=FINDTRAN;
if s<5 then {Generate another point in the fern.}
begin
nx:=CT[s,1]*x + CT[s,2]*y + CT[s,3];
ny:=CT[s,4]*x + CT[S,5]*y + CT[s,6];
x:=nx; y:=ny; bx:=x; by:=y;
end
else {Generate another point in the forest.}
begin
s:=s-4;
nx:=PL[s,1]*bx + PL[s,2]*by + PL[s,3];
ny:=PL[s,4]*bx + PL[s,5]*by + PL[s,6];
bx:=nx; by:=ny;
end;
end;
procedure INIT;
begin
xsc:=1.3; ysc:=1;
xoff:=round(GETMAXX/2); yoff:=GETMAXY-50;
x:=0; y:=0;
bx:=0; by:=0;
GETAspectRatio(xasp,yasp); asp:=xasp/yasp;
end;
BEGIN
gd:=detect; initgraph(gd,gm,' ');
INIT; cleardevice;
for N:=1 to 32000 do
begin
MAKETRAN;
putpixel(round(bx*xsc)+xoff,(round(asp*by*ysc)+yoff),green);
end;
readln; cleardevice; closegraph;
END.
Copyright © 1991, Dr. Dobb's Journal
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.