cs249 lecture notes, Fall 2001
Week 10, Thursday

Assignment for today: draw a sketch of a blueprint
for a self-similar figure (as in Figure 5.22) and compute
the values of e, f, phi, psi, r and s for each lens system.


Barnsley's fern
---------------

Barnsley described a fern in terms of a set of transformations
(see handout)

The idea is that if something is self similar, we can describe
it entirely just by enumerating the _ways_ in which it is
self-similar!

Potentially a very dense form of image encoding.

Blueprints: diagram showing the initial image and each transformation
	    of it

Lens: a transformation defined by translation (e, f),
      rotation (phi, psi) and scaling (r, s).

MRCM: multiple reduction copy machine


The fern set
------------

We can think of a lens as a function on v

v1 = f(v0)

v2 = f(v1) = f(f(v0)

and so on.

We can identify a set of points in the plane such that
if v belongs to the set, the f(v) belongs to the set.

Not surprising: once you get to a point in the set, you
                never leave

    (these points form a fixed point)

Somewhat surprising: no matter where you start, you get
	             to the set pretty quickly.

    (these points form an attractor)

Quite surprising: the set of points with this property
                  looks quite a lot like a fern.

    (these points form a fern)


The fern algorithm
------------------

So, this leads us to an algorithm for generating a fern

1) start with any point in the plane

2) choose one of the transformations at random and apply
   it to the point

3) plot the resulting point

4) go to step 2

The first couple of points in the sequence might not be
on the fern, but after a few iterations, we're there.


Here's some fern code, with comments...

The top-level function clears the screen and invokes
drawFern:

function fern ()
clf; hold on;
drawFern (10, 5000);
axis equal;

drawFern takes two input variables: how many sequences to draw,
and how long to make each sequence.

function drawFern (n, m)
for i=1:n
    v = random ('Uniform', 0, 1, 2, 1);
    vs = computePoints (v, m);
    h = plot (vs(:,1), vs(:,2), 'r.');
    set (h, 'MarkerSize', 1);
end

random generates a random starting point in the unit square
We have seen this use of plot and set before.

computePoints takes two input variables: the starting point
(a column vector) and the length of the sequence 

function vs = computePoints (v, n)

      % the rs are the rotation matrices;
      % the ts are the translation vectors

t1 = [0.0 1.6]';
r1 = rotate (-2.5, -2.5, 0.85, 0.85);
t2 = [0.0 1.6]';   
r2 = rotate (49,   49,   0.3,  0.34);
t3 = [0.0 0.44]';
r3 = rotate (120,  -50,   0.3,  0.37);
t4 = [0.0 0.0]';
r4 = rotate (0,    0,   0.0,  0.16);

      % p and cp control the probability of choosing
      % each of the transformations

p = [81 9 9 1];
cp = cumsum (p);

      % random produces a vector of values between 0 and 100
      % each value determines the next transformation
      % vs contains all the points in the sequence.

x = random ('Uniform', 0, sum(p), 1, n);
vs = ones (n, 2);

for i=1:length(x)
    if     (x(i) < cp(1))
        v = r1 * v + t1;
    elseif (x(i) < cp(2))
        v = r2 * v + t2;
    elseif (x(i) < cp(3))
        v = r3 * v + t3;
    else
        v = r4 * v + t4;
    end
    vs(i,1) = v(1);
    vs(i,2) = v(2);
end

rotate creates the rotation vectors, as we saw in class.

function res = rotate (phi, psi, r, s)
phi = pi * phi / 180;
psi = pi * psi / 180;
res = [r*cos(phi) -s*sin(psi); r*sin(phi) s*cos(psi)];



Fern parameters
---------------

Why does the 4th parameter have such a low probability?

What happens if we increase it?

How can we make the fern more curvy?  Straighter?

How can we make the fern wider?  Narrower?

How can we make a fern with opposite phylotaxy, rather
than alternate phylotaxy?