Downloads: jar library | source code

There are two common methods for generating such images. One of them is known as tie-dye. Unfortunately, that particular technique went out with the sixties, and I don't know exactly how its done (except for a few details about tying up a shirt and subsequently dying it). The second technique is a recursive algorithm known as *random midpoint displacement*. I think we can safely say that recursive algorithms will never go out of style! At the very least, I know a bit more about them than I do about sixties fashion (or any fashion, for that matter). The algorithm begins with a rectangular grid that has four points, one at each corner. These corners are each randomly assigned a color value. Now, five new points are added to the grid. One point is added to each edge that has a color value in-between the color value of the two corners connected to the edge (i.e., it is the average value of those two corners). The fifth point is placed in the center, or midpoint, of the grid. It is the average of the original four corners. This is where the algorithm gets its name. The *midpoint* is *randomly displaced*. That is to say, some random value is chosen, and the color value is shifted by the value. The range of possible random numbers is made to be proportional to the size of the square. A large square may have its midpoint displaced a great deal, and a small square can not have its midpoint displaced by more than a little bit.

More rigorous implementations of the algorithm actually use fancy applications of Gaussian statistics to set the range of random values. Unfortunately, I know even less about Gaussian statistics than I know about tie-dye, so I found that fudging it was fine for producing pretty pictures. If you are interested though, you may want to look for references with more careful descriptions of the algorithm.

If you were reading carefully, you may have noticed that adding the five extra points divided the original rectangle into four similar rectangles of one fourth the area! The algorithm is repeated for each of these new squares, yielding a total of sixteen squares! The process can be repeated recursively as necessary. In this case, it is repeated until each rectangle is less than the size of a single pixel. At that point, the recursion ends, and the square is drawn.

While there is no question that this is an exceedingly cool algorithm (you just can't get enough of those, right?), a great deal of the magic actually has to do with the selection of colors. In this applet, every color value is a number of type float from zero to one. What the algorithm does is create a field of smoothly changing color values. A function converts these color values to colors so that the color values from zero to one flow smoothly between colors, creating the plasma effect.

Believe it or not, random midpoint displacement is quite useful in some situations. It's ideal for generating terrains. Imagine that, instead of a color value, a height value is used instead. This can create very realistic looking, randomly generated mountains or hills, a technique that is used quite often and with great success in Hollywood. Also, by carefully mapping certain colors to different color values, useful textures and images can be generated. I can't claim that I am actually *aware* of an example of this, but somebody must have done it!

This image is an example of terrain generated with random midpoint displacement. The algorithm was used to select the color values, and those color values were also used as height values.

If you are interested in trying to implement this technique yourself, I highly recommend it. It's a fantastic exercise in recursion, and a sure-fire way to impress women. Trust me; it can't miss! I have provided the source code for those who want to look at it for some help or those who just wish to see the specifics of my implementation.

While one of the rectangular grid-pieces is being divided into four similar rectangles, the color values for its four corners are named *c1*, *c2*, *c3*, and *c4*. The variable *c1* is the color value for the top-left hand corner, and the three other variables proceed clockwise around the rectangle. The variables *Edge1*, *Edge2*, *Edge3*, and *Edge4* hold the color values for the four new points that are created on the edges. *Edge1* stores the color value for the point created on the top edge, and the other three edge variables also proceed clockwise around the rectangle. Finally, the variable *Middle* refers to exactly what you would guess -- the midpoint. Hopefully those notes will help make the program clearer. Most other important information should be in the comments.

Note that the implementation of the algorithm described here is the result of some tweaking on my part to make it quick to implement (while making the prettiest pictures) and is by no means rigorous. These sources, which I used, and others may help you understand the technique better.

Hahn, Patrick. (1997). *Plasma Fractals*. Retrieved January 30, 2002 from http://www2.vo.lu/homepages/phahn/fractals/plasma.htm.

Marak, Ivo. *Random Midpoint Displacement Method*. Retrieved January 30, 2002 from http://www.cg.tuwien.ac.at/studentwork/CESCG97/marak/node3.html *Justin Seyster* (2002)

jseyster at cs dot sunysb dot edu

© 2010 Java Science Go to the main page