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?