Assignment 0: Iterated Function Systems

The goal of this assignment is to get familiar with C++ and with two
simple libraries that we will use for linear algebra and images. The
incidental goal is also to have fun with bizarre fractal objects. IFS
are self-similar fractals: a subpart of the object is similar to the
whole. The classic example of an IFS is Barnsley's fern, where each
subpart of the fern is exactly the same as the whole fern. IFS are
described by a set of affine transformations (rotations, translations,
scale, skew, etc.) These transformations capture the self-similarity
of the object. IFS can be defined in any dimension, but we will play
with two-dimensional ones. Formally, an IFS is defined by *n*
affine transformations. Each transformation *f _{i}*
must be contractive: The distance between points must be reduced. An

We render an IFS by iterating the transform on random input points from the unit square. We approximate the fixed point by applying the transformation many times. The algorithm is as follows:

for "lots" of random points (x_{0}, y_{0}) for k=0 to num_iters_{ }pick a random transform f_{i}(x_{k+1}, y_{k+1}) = f_{i}(x_{k}, y_{k}) display a dot at (x_{k}, y_{k})

To reduce the number of points necessary to make an image of reasonable quality, probabilities are assigned to each transformation, instead of choosing a transformation with uniform probability.

- Write a C++ class
`IFS`that renders iterated function systems, including the interface (in a file`ifs.h`) and the implementation (`ifs.C`). Your code should run under Linux or Windows. The IFS class should include:- a field to store
*n*, the number of transformations - an array of matrices representing the
*n*transformations - an array of the corresponding probabilities for choosing a transformation
- a constructor that creates an IFS
- an input method that reads the IFS description
- a render method that takes as input an image instance, a number of points and a number of iterations
- a destructor that frees the memory of the various arrays (using
`delete`)

- a field to store
- Write the main program
`main.C`that creates an`Image`instance, reads an IFS description from a file, renders the IFS to the image, and saves the image. - Use the linear algebra library for the point and transformation representations.
- Perform proper memory management --- free memory when an object is destroyed.
- Extra credit: create a new IFS, figure out the probabilities,
determine the bounding box, change the color scheme, anti-aliasing,
depth-first vs. breadth-first, etc. Include a short paragraph in
your
`README.txt`file describing your extensions.

- Random numbers can be obtained using the
`drand48()`or`rand()`, and`RAND_MAX`. See`stdlib.h`. - To debug your code, set the number of iterations to one. This will allow you to check that you got the transformations right.
- Be careful, arrays are indexed from 0 to
*n-1*in C++. Reading beyond the bounds of the array will probably result in a segmentation fault. - Use
`assert()`to check function pre-conditions, array indices, etc. See`assert.h`.

- M.Barnsley, Fractals Everywhere, Academic Press, 1988.
- http://spanky.triumf.ca/www/fractal-info/ifs-type.htm
- http://www.cut-the-knot.org/ctk/ifs.shtml

ifs -input sierpinski_triangle.txt -points 10000 -iters 0 -size 200 -output sierpinski_triangle_0.tga ifs -input sierpinski_triangle.txt -points 10000 -iters 1 -size 200 -output sierpinski_triangle_1.tga ifs -input sierpinski_triangle.txt -points 10000 -iters 2 -size 200 -output sierpinski_triangle_2.tga ifs -input sierpinski_triangle.txt -points 10000 -iters 3 -size 200 -output sierpinski_triangle_3.tga ifs -input sierpinski_triangle.txt -points 10000 -iters 4 -size 200 -output sierpinski_triangle_4.tga ifs -input sierpinski_triangle.txt -points 10000 -iters 30 -size 200 -output sierpinski_triangle.tga

ifs -input fern.txt -points 50000 -iters 30 -size 400 -output fern.tga

See the main Assignments Page for submission information.