COMP30075 Assignment 2006


You should write a program which implements a simple Iterated Function System (IFS). This will allow you to create a class of regular point fractal pictures. This is an exercise in 2D transformations. IFSs are not discussed in the Lecture Notes but transformations are.

Practical Matters

You may use any programming system of your choice, including MatLab, provided that you can submit GIF format images. GIMP is a useful public domain utility for image format conversion, available for both Windows and Linux. Jasc PaintShop Pro will also perform conversion and is available on University computers.

In case you have no means of writing picture files, you are also supplied with a simple graphics package written in C, which allows you to create picture files in 24 bit targa (tga) format. You are not obliged to use this. If you do want to, it is in ~maspjw/ACG/ on the BUCS machines, together with some simple test routines. Two versions are provided. The BIG_ENDIAN directory contains code for the BUCS machines and the LITTLE_ENDIAN version contains code for Intel processors. For Microsoft machines, use LITTLE_ENDIAN. For Linux machines, use the version appropriate for your processor. You may use any other package of your choice, including MatLab.

Submit:

  • A print-out of your code. This should have a separate top submission sheet. It should also include the URL of a web page containing at least two sample pictures from your program and the scalings, rotations and translation which created them. Make sure this web page is readable by other people.
  • The "Additional Marks" discussion (see below): maximum 2 pages.
The time you are recommended to allow for this project is 20 hours.

Due date/time: Monday November 20th mid-day

Submit to the CM30075 postbox, Computer Science Dept Office 1W2.23

Marking: 25% of the Unit total

Setter: P J Willis


Marking scheme

  • Explanation of why an IFS works: 5 marks
  • Description of programme organisation etc: 5 marks
  • Sample pictures: 5 marks
  • Program quality: 5 marks
There are a further five marks which are for additional but relevant information. You should describe this in a section of your write-up headed "Additional Marks". For example, this might be some feature of your programme which permits extra visual effects or it might be a discussion of extending the method to 3D etc. It is your choice.

Rules, Regulations etc

Most of the formal rules are available via our web page. You are reminded that, while you may freely discuss the project with other students and use sources other than the lecture notes, all work submitted must be your own. It is an offence to taking the programs, writings or ideas of another and represent them as your own. If you need to include someone else's work, the original author and the source of the material must be clearly stated.

I am quite happy that you share information on the graphics library etc because that aspect is not marked. Indeed I encourage you to help each other with this, so you can quickly get to the main project work. However the project is otherwise an individual project and all work must be your own.

Please make sure you are familiar with the Assessed Coursework section of the Undergraduate Programmes Handbook. You are reminded that (unless there are mitigating circumstances) a late submission will receive a maximum mark of 40% if submitted up to 5 days late; 0% if later still.


Details

For our purposes, an IFS is a set of 2D transformations which are iteratively applied to a 2D point. At each iteration, one of the functions is chosen at random, then applied to the coordinates of the point to produce a new point. This point is then plotted. By doing this several thousand times, a set of points is plotted. If the functions are contraction mappings (scale factor less than 1.0), then the point set converges on a pattern, such as these examples.

The first example was produced from three functions, each with zero rotation and 0.5 scaling. The functions differ only in their translation. If we assume the picture coordinate space covers [-0.5, 0.5] in each of x and y, then the translations are (-0.25, -0.25), (0.25 0.25), (-0.25 0.25). You can see that the overall effect is to pull the cloud of points in the directions of these three mappings; but the effect happens at recursively smaller scales too, to produce self-similarity.

So, your program should read in data, such as the following example:

 3

 0.0   0.4
-0.25 -0.25

 0.0   0.4
 0.25  0.25

 0.0   0.4
-0.25  0.25
The integer at the start says how many mappings there will be (you can assume no more than 10). There are then four values to define each mapping. The first pair are the rotation angle (in degrees) and the scale value (between 0 and 1). The second pair are the x-translation and the y-translation of the mapping, relative to the centre of the picture. That is, the picture is a square centred on (0,0) with bottom left at (-0.5, -0.5) and top right at (0.5, 0.5). Test with pictures of 256 pixels square.

This should not be a lengthy programme, 4 or 5 sides of A4. You might like to know that you can achieve a rotation of (x,y) about the origin with x= x.cos(theta) - y.sin(theta); y= x.sin(theta) + y.cos(theta). Don't forget that, if using C, the sin/cos routines expect radians and you have to link to the maths library (-lm) to use them.