What is Brownian motion? Brownian motion is the random motion of particles suspended in a fluid (a liquid or a gas) resulting from their collision with the fast-moving molecules in the fluid. The motion is named after Scottish botanist Robert Brown who first described the motion in 1827 while looking through a microscope at pollen of the plant Clarkia pulchella immersed in water. The concept is as simple as a particle making random jumps, and tracing out a trail. Regular Brownian motion occurs when all the jumps taken by the particle are independent. In fractional Brownian motion (FBm), the steps taken by the particle are correlated in time. Fractal Brownian motion is a process which is used by artists and scientists to model complex shapes that arise in nature, and artificial phenomena. Examples include dispersion of ink in water, stock prices, clouds, plants, rugged shapes of mountains, riverbeds, and fractal landscapes.
One of the simplest methods for generating a fractal profile is “midpoint displacement“. The algorithm was first described by Fournier et al. [1] as a recursive subdivision algorithm for generating an approximation of an FBm.
Fournier and colleagues [1] included a couple of Pascal programs to calculate parametric and nonparametric subdivision (they are not explained as well as they could be in the paper). The Processing code below is based loosely on those programs, and includes two subprograms, fractal(), and subdivide(). The parent subprogram fractal() has a number of parameters: (x1,y1) and (x2,y2) describe the two points which denote the line. The remaining two parameters, h and scale help define the scaling of the subdivisions.
his a parameter which determines the “fractal dimension” of the output sequence, and essentially describes the degree of geometric irregularity. It has values between 0 and 1. Ashapproaches 0 irregularity is high, ashapproaches 1 it is low (smoother).scaleis the roughness parameter of the curve. 0 = straight line, and >0 implies increasing roughness.
void fractal(float x1, float x2, float y1, float y2, float h, float scale){
float std, ratio;
ratio = pow(2.0,-h);
std = scale * ratio;
subdivide(x1,x2,y1,y2,std,ratio);
}
The subprogram subdivide() performs the recursive subdivisions. If the difference between x-coordinates is greater than a certain value, epsilon, then the line is subdivided (epsilon=2). This is achieved by calculating the midpoint of both x (xmid) and y (ymid) coordinates. The ymid position is modified using both std, and a Gaussian random number with zero mean and unit variance. The subprogram subdivide() is then recursively called on the left and right intervals from the midpoint.
void subdivide(float x1, float x2, float y1, float y2, float std, float ratio){
float xmid, ymid;
if (x2-x1 > epsilon){
xmid = 0.5 * (x1 + x2);
ymid = 0.5 * (y1 + y2) + std * randomGaussian();
std = std * ratio;
subdivide(x1,xmid,y1,ymid,std,ratio);
subdivide(xmid,x2,ymid,y2,std,ratio);
}
else
line(x1,y1,x2,y2);
}
Below are some examples, showing various values of h and scale.
Not surprisingly fractalizing a line is a recursive process. A generalized algorithm is described below. Starting with a line of length n, the mid-point of the line is displaced up or down by a random amount. This is repeated for each of the two segments produced. This is essentially a random walk that connects two points, and is controlled by a few parameters. The basic algorithm of the midpoint displacement method is:
- Maintain an interval with endpoints (x0,y0) and (x1,y1).
- Divide the interval in half.
- Set xmid = (x0 + x1)/2 and ymid = (y0 + y1)/2
- Choose a displacement at random using a Gaussian distribution.
- Apply the algorithm to the left and right intervals.
Refs:
- Fournier, A., Fussell, D., Carpenter, L., “Computer rendering of stochastic models”, CACM, 25, pp.371-384 (1982).
The Craft of Coding 