Computer graphics will be familiar from games, films and images, and there is amazing software available to create images, but how does the software work? The role of a computer scientist is not just to use graphics systems, but to create them, and especially invent new techniques.

The entertainment industry is always trying to develop new graphics software so that they can push the boundaries and create new experiences. We've seen this in the evolution of animated films, from simple 2D films to realistic computer generated movies with detailed 3D images. The names of dozens of computer scientists now regularly appear in the credits for films that us CGI or animation, and some have even won Oscars for their innovative software!

Movie and gaming companies can't always just use existing software to make the next great thing --- they need computer scientists to come up with better graphics techniques to make something that's never been seen before. The creative possibilities are endless!

Computer graphics are used in a wide variety of situations: games and animated movies are common examples, but graphics techniques are also used to visualise large amounts of data (such as all cellphone calls being made in one day or friend connections in a social network), to display and animate graphical user interfaces, to create virtual reality and augmented reality worlds, and much more.

  • Jargon Buster: Pixels

    A digital image on a screen or printer is physically made up of a grid of tiny squares called pixels. They are usually too small to see easily (otherwise the image would look blocky). Photographs usually use millions of pixels (a megapixel is a million pixels; for example, a screen that is 1080 pixels across and 720 down would contain 777,600 pixels, or 0.7776 megapixels).

    The pixels is fundamental to computer graphics, as a lot of the work of computer graphics programmers is taking some abstract idea (such as objects in a scene), and working out the colour each pixel should be to make the viewer think they are looking at the scene. A digital camera also does this - but it just senses the colour falling on each of its millions of sensors, and stores those so that the pixels can be displayed when needed.

In this chapter we'll look at some of the basic techniques that are used to create computer graphics. These will give you an idea of the techniques that are used in graphics programming, although it's just the beginning of what's possible.

For this chapter we are using a system called WebGL which can render 3D graphics in your browser. If your browser is up to date everything should be fine. If you have issues, or if the performance is poor, there is information here about how to get it going.

A computer graphics image is just the result of a whole lot of mathematical calculations. In fact, every pixel you see in an image has usually had many calculations made to work out what colour it should be, and there are often millions of pixels in a typical image.

Let's start with some simple but common calculations that are needed for in graphics programming. The following interactive shows a cube with symbols on each face. You can move it around using what's called a transform, which simply adjusts where it is placed in space. Try typing in 3D coordinates into this interactive to find each code.

You've just applied 3D translation transforms to the cube. Translation just means moving it in the three dimensions up and down, forward and back, and sideways.

Now try the following challenge, which requires you to rotate the box to find the codes.

There are several transformations that are used in computer graphics, but the most common ones are translation (moving the object), rotation (spinning it) and scaling (changing its size). They come up often in graphics because they are applied not only to objects, but to things like the positions of the camera and lighting sources.

In this section you can apply transformations to various images. We'll start by making the changes manually, one point at a time, but we'll move up to a quick shortcut method that uses a matrix to do the work for you. We'll start by looking at how these work in two dimensions - it's a bit easier to think about than three dimensions.

The following interactive shows an arrow, and on the left you can see a list of the points that correspond to its 7 corners (usually referred to as cartesian coordinates). The arrow is on a grid, where the centre point is the "zero" point. Points are specified using two numbers, x and y, usually written as (x,y). The x value is how far the point is to the right of the centre and the y value is how far above the centre it is. For example, the first point in the list is the tip at (0,4), which means it's 0 units to the right of the centre (i.e. at the centre), and 4 units above it. Which point does the last pair (3,1) correspond to? What does it mean if a coordinate has a negative x value?

The transform you did in the above interactive is called a translation --- it translates the arrow around the grid. This kind of transform is used in graphics to specify where an object should be placed in a scene, but it has many other uses, such as making an animated object move along a path, or specifying the position of the imaginary camera (viewpoint).

The next challenge involves changing the size of the image.

This transformation is called scaling, and although it can obviously be used to control the size of an object, this can in turn be used to create a visual effect such as making the object appear closer or further away.

In the following interactive, try to get the blue arrow to match up with the red one. It will require a mixture of scaling and translation.

Next, see what happens if you swap the x and y value for each coordinate.

This is a simple rotation transformation, also useful for positioning objects in a scene, but also for specifying things like camera angles.

Typing all these coordinates by hand is inefficent. Luckily there's a much better way of achieving all this. Read on!

There's a much easier way to specify transformations than having to change each coordinate separately. Transformations are usually done in graphics using matrix arithmetic, which is a shorthand notation for doing lots of simple arithmetic operations in one go. The matrix for the two-dimensional transformations we've been doing above has four values in it. For the 2 dimensional scaling transform where we made each x and y value twice as large, the matrix is written as:

\[ \begin{bmatrix} 2 & 0 \\ 0 & 2 \\ \end{bmatrix} \]

where the top left value just means multiply all the x values by 2, and the bottom right value means multiply all the y values by 2.

You can try it out in the following interactive:

At this stage you may want to have the interactive open in a separate window so that you can read the text below and work on the interactive at the same time.

Let's take a closer look at what is happening here. As we mentioned earlier, each point on our arrow can be represented by two values (x and y). The rightmost point, on the arrow in the interactive above, we say is at point (3,1) in our coordinate space.

When we are applying a scaling transformation we are actually doing a type of "matrix multiplication." For example, let's scale point (3,1) by a factor of 2 as we did in the previous interactive:

\[ \begin{bmatrix} 2 & 0 \\ 0 & 2 \\ \end{bmatrix} \times \begin{bmatrix} 3 \\ 1 \\ \end{bmatrix} = \begin{bmatrix} 6 \\ 2 \\ \end{bmatrix} \]

This gives us a new position of (6,2) for the rightmost point, which matches the previous interactive after applying the scaling matrix! This same matrix multiplication is applied to each of the seven points on the arrow.

Now try changing the matrix to

\[ \begin{bmatrix} 3 & 0 \\ 0 & 3 \\ \end{bmatrix} \]

For the rightmost point (starting at (3,1)), the matrix muliplication for scaling by a factor of 3 is:

\[ \begin{bmatrix} 3 & 0 \\ 0 & 3 \\ \end{bmatrix} \times \begin{bmatrix} 3 \\ 1 \\ \end{bmatrix} = \begin{bmatrix} 9 \\ 3 \\ \end{bmatrix} \]

Now let's try scaling with a number less than one:

\[ \begin{bmatrix} 0.2 & 0 \\ 0 & 0.2 \\ \end{bmatrix} \]

For the rightmost point (starting at (3,1)), the matrix muliplication for scaling by a factor of 0.2 is:

\[ \begin{bmatrix} 0.2 & 0 \\ 0 & 0.2 \\ \end{bmatrix} \times \begin{bmatrix} 3 \\ 1 \\ \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.2 \\ \end{bmatrix} \]

By now you might be starting to see a recurring pattern in our matrix multiplication for scaling. To scale by a factor of s, we can apply the general rule:

\[ \begin{bmatrix} s & 0 \\ 0 & s \\ \end{bmatrix} \times \begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} sx \\ sy \\ \end{bmatrix} \]
  • Extra For Experts: Matrix Multiplication Challenge

    Pick 2 or 3 more points on the arrow (include some with negative x and y values) and try to do the matrix multiplication for scaling each factor above (2, 3 and 0.2). You'll know if you got the correct answer because it should match the scaled arrow in the interactive!

What happens if you use the following matrix?

\[ \begin{bmatrix} 2 & 0 \\ 0 & 4 \\ \end{bmatrix} \]

A simple way of looking at the matrix is that the top row determines the transformed x value, simply by saying how much of the original x value and y value contribute to the new x value. So in the matrix:

\[ \begin{bmatrix} 2 & 0 \\ 0 & 4 \\ \end{bmatrix} \]

the top row just means that the new x value is 2 lots of the original x, and none of the original y, which is why all the x values double. The second row determines the y value: in the above example, it means that the new y value uses none of the original x, but 4 times the original y value. If you try this matrix, you should find that the location of all the x points is doubled, and the location of all the y points is multiplied by 4.

Now try the following matrix:

\[ \begin{bmatrix} 0 & 1 \\ 1 & 0 \\ \end{bmatrix} \]

This matrix should have rotated the arrow to the right.

The new x value has none of the original x, but exactly the original y value, and vice versa. This swaps all the x and y coordinates, which is the same as rotating the object to the right.

Where it gets interesting is when you use a little of each value; try the following matrix:

\[ \begin{bmatrix} 0.7 & 0.7 \\ -0.7 & 0.7 \\ \end{bmatrix} \]

Now the x value of each coordinate is a mixture of 0.7 of the original x, and 0.7 of the original y. This is called a rotation.

In general, to rotate an image by a given angle you need to use the sine (abbreviated sin) and cosine (abbreviated cos) functions from trigonometry. You can use the interactive below to calculate values for the sin and cos functions.

To rotate the image anticlockwise by \(\theta\) degrees, you'll need the following values in the matrix, which rely on trig functions:

\[ \begin{bmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \\ \end{bmatrix} \]

Note that the following interactives involving rotation transformations expect accuracy of 2 decimal places.

What is the matrix for rotation by 360 degrees?

Recall that the general matrix for scaling is:

\[ \begin{bmatrix} s & 0 \\ 0 & s \\ \end{bmatrix} \]

A bit simpler than the one for rotation!

A translation can't be specified by this kind of matrix, so in the interactives we've provided an extra place to specify an x and y value to translate the input. Try it out in the following interactive.

The next interactive needs you to combine translation with scaling.

The order in which translation and scaling happen makes a difference. Try the following challenge!

In the above interactive, you'll have noticed that scaling is affected by how far the object is from the centre. If you want to scale around a fixed point in the object (so it expands where it is), then an easy way is to translate it back to the centre (also called the origin), scale it, and then translate it back to where it was. The following interactive allows you to move the arrow, then scale it, and move it back.

The same problem comes up with rotation. The following interactive allows you to use a translation first to make the scaling more predicable.

Now that you've had a bit of practice with translation, scaling and rotation, try out these two challenges that combine all three:

These combined transformations are common, and they might seem like a lot of work because each matrix has to be applied to every point in an object. Our arrows only had 7 points, but complex images can have thousands or even millions of points in them. Fortunately we can combine all the matrix operations in advance to give just one operation to apply to each point.

Several transforms being applied to the same image (for example, rotate, move and scale the wheel of a car) can be made more efficient by creating one matrix that has the effect of all the transforms combined.The combination is done by "multiplying" all the matrices.

Multiplying two matrices can't be done by just multiplying the corresponding elements (as we learned earlier when applying scaling transformations); if you are multiplying two 2x2 matrices with the a and b values shown below, the resulting values from the multiplication are calculated as follows:

\[ \begin{bmatrix} a_{11} & a_{21} \\ a_{12} & a_{22} \\ \end{bmatrix} \times \begin{bmatrix} b_{11} & b_{21} \\ b_{12} & b_{22} \\ \end{bmatrix} = \begin{bmatrix} a_{11}b_{11}+a_{21}b_{12} & a_{11}b_{21}+a_{21}b_{22} \\ a_{12}b_{11}+a_{22}b_{12} & a_{12}b_{21}+a_{22}b_{22} \\ \end{bmatrix} \]

It's a bit complicated, but this calculation is only done once to work out the combined transformation, and it gives you a single matrix that will provide two transforms in one operation.

As a simple example, consider what happens when you scale by 2 and then rotate by 45 degrees. The two matrices to multiply work out like this:

\[ \begin{bmatrix} 2 & 0 \\ 0 & 2 \\ \end{bmatrix} \times \begin{bmatrix} 0.7 & 0.7 \\ -0.7 & 0.7 \\ \end{bmatrix} = \begin{bmatrix} 2 \times 0.7+ 0 \times -0.7 & 2 \times 0.7+ 0 \times 0.7 \\ 0 \times 0.7+ 2 \times -0.7 & 0 \times 0.7+ 2 \times 0.7 \\ \end{bmatrix} = \begin{bmatrix} 1.4 & 1.4 \\ -1.4 & 1.4 \\ \end{bmatrix} \]

You can put the matrix we just calculated into the following interactive to see if it does indeed scale by 2 and rotate 45 degrees. Also try making up your own combination of transforms to see if they give the result you expect.

In computer graphics systems there can be many transformations combined, and this is done by multiplying them all together (two at a time) to produce one matrix that does all the transforms in one go. That transform might then be applied to millions of points, so the time taken to do the matrix multiplication at the start will pay off well.

The project below gives the chance to explore combining matrices, and has an interactive that will calculate the multiplied matrices for you.

So far we've just done the transforms in two dimensions. To do this in 3D, we need a z coordinate as well, which is the depth of the object into the screen. A matrix for operating on 3D points is 3 by 3. For example, the 3D matrix for doubling the size of an object is as follows; it multiplies each of the x, y and z values of a point by 2.

\[ \begin{bmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \\ \end{bmatrix} \]

You can try out this 3D matrix in the following interactive.

The above image mesh has 3644 points in it, and your matrix was applied to each one of them to work out the new image.

The next interactive allows you to do translation (using a vector). Use it to get used to translating in the three dimensions (don't worry about using matrices this time.)

Rotation is trickier because you can now rotate in different directions. In 2D rotations were around the centre (origin) of the grid, but in 3D rotations are around a line (either the horizontal x-axis, the vertical y-axis, or the z-axis, which goes into the screen!)

The 2D rotation we used earlier can be applied to 3 dimensions using this matrix:

\[ \begin{bmatrix} \cos(\theta) & -\sin(\theta) & 0 \\ \sin(\theta) & \cos(\theta) & 0 \\ 0 & 0 & 1\\ \end{bmatrix} \]

Try applying that to the image above. This is rotating around the z-axis (a line going into the screen); that is, it's just moving the image around in the 2D plane. It's really the same as the rotation we used previously, as the last line (0, 0, 1) just keeps the z point the same.

Try the following matrix, which rotates around the x-axis (notice that the x value always stays the same because of the 1,0,0 in the first line):

\[ \begin{bmatrix} 1 & 0 & 0 \\ 0 & \cos(\theta) & -\sin(\theta) \\ 0 & \sin(\theta) & \cos(\theta) \\ \end{bmatrix} \]

And this one for the y-axis:

\[ \begin{bmatrix} \cos(\theta) & 0 &\sin(\theta) \\ 0 & 1 & 0\\ -\sin(\theta) & 0 & \cos(\theta) \\ \end{bmatrix} \]

The following interactive allows you to combine 3D matrices.

In the above examples, when you have several matrices being applied to every point in the image, a lot of time can be saved by converting the series of matrices and transforms to just one formula that does all of the transforms in one go. The following interactive can do those calculations for you.

For example, in the following interactive, type in the matrix for doubling the size of an object (put the number 2 instead of 1 on the main diagonal values), then add another matrix that triples the size of the image (3 on the main diagonal). The interactive shows a matrix on the right that combines the two --- does it look right?

The interactive also allows you to combine in translations (just three numbers, for x, y and z). Try combining a scaling followed by a translation. What if you add a rotation --- does the order matter?

  • Curiosity: Matrix multiplication in 3D

    In case you're wondering, the interactive is using the following formula to combine two matrices (you don't have to understand this to use it). It is called matrix multiplication, and while it might be a bit tricky, it's very useful in computer graphics because it reduces all the transformations you need to just one matrix, which is then applied to every point being transformed. This is way better than having to run all the matrices of every point.

    \[ \begin{bmatrix} a_{11} & a_{21} & a_{31}\\ a_{12} & a_{22} & a_{32}\\ a_{13} & a_{23} & a_{33}\\ \end{bmatrix} \times \begin{bmatrix} b_{11} & b_{21} & b_{31}\\ b_{12} & b_{22} & b_{32}\\ b_{13} & b_{23} & b_{33}\\ \end{bmatrix} =\\ \begin{bmatrix} a_{11}b_{11}+a_{21}b_{12}+a_{31}b_{13} & a_{11}b_{21}+a_{21}b_{22}+a_{31}b_{23} & a_{11}b_{31}+a_{21}b_{32}+a_{31}b_{33}\\ a_{12}b_{11}+a_{22}b_{12}+a_{32}b_{13} & a_{12}b_{21}+a_{22}b_{22}+a_{32}b_{23} & a_{12}b_{31}+a_{22}b_{32}+a_{32}b_{33} \\ a_{13}b_{11}+a_{23}b_{12}+a_{33}b_{13} & a_{13}b_{21}+a_{23}b_{22}+a_{33}b_{23}& a_{13}b_{31}+a_{23}b_{32}+a_{33}b_{33} \\ \end{bmatrix} \]
  • Project: 3D transforms

    For this project, you will demonstrate what you've learned in the section above by explaining a 3D transformation of a few objects. You should take screenshots of each step to illustrate the process for your report.

    The following scene-creation interactive allows you to choose objects (and their colours etc.), and apply one transformation to them. To position them more interestingly, you will need to come up with multiple transformations (e.g. scale, then rotate, then translate), and use the "simplifier" interactive to combine all the matrices into one operation.

    The scene-creation interactive can be run from here:

    To generate combined transformations, you can use the following transform simplifier interactive:

    Because you can't save your work in the interactives, keep notes and screen shots as you go along. These will be useful for your report, and also can be used if you need to start over again.

    Introduce your project with a examples of 3D images, and how they are used (perhaps from movies or scenes that other people have created). Describe any innovations in the particular image (e.g. computer generated movies usually push the boundaries of what was previously possible, so discuss what boundaries were moved by a particular movie, and who wrote the programs to achieve the new effects). One way to confirm that a movie is innovative in this area is if it has won an award for the graphics software.

    To show the basics of computer graphics, try putting a few objects in a particular arrangement (e.g. with the teapot sitting beside some cups), and explain the transforms needed to achieve this, showing the matrices needed.

    Give simple examples of translation, scaling and rotation using your scene. You should include multiple transforms applied to one object, and show how they can be used to position an object.

    Show how the matrices for a series of transforms can be multiplied together to get one matrix that applies all the transforms at once.

    Discuss how the single matrix derived from all the others is more efficient, using your scene as an example to explain this.

  • Project: WebGL and OpenGL

    If you're confident with programming and want to explore graphics at a more practical level, you could do a similar project to the previous one using a graphics programming system such as WebGL (which is the system used in the demonstrations above), or a widely used graphics system such as OpenGL. There is an interactive tutorial on OpenGL called JPOT.

    Note that these project can be very time consuming because these are powerful systems, and there is quite a bit of detail to get right even for a simple operation.

A fundamental operation is computer graphics is to draw lines and circles. For example, these are used as the components of scalable fonts and vector graphics; the letter "g" is specified as a series of lines and curves, so that when you zoom in on it the computer can redraw it at whatever resolution is needed. If the system only stored the pixels for the letter shape, then zooming in would result in a low quality image.

The points used to create the letter 'g' in Google's logo

In 3D graphics shapes are often stored using lines and curves that mark out the edges of tiny flat surfaces (usually triangles), each of which is so small that you can't see them unless you zoom right in.

The lines and circles that specify an object are usually given using numbers (for example, a line between a given starting and finishing position or a circle with a given centre and radius). From this a graphics program must calculate which pixels on the screen should be coloured in to represent the line or circle, or it may just need to work out where the line is without drawing it.

For example, here's a grid of pixels with 5 lines shown magnified. The vertical line would have been specified as going from pixel (2,9) to (2,16) --- that is, starting 2 across and 9 up, and finishing 2 across and 16 up. Of course, this is only a small part of a screen, as normally they are more like 1000 by 1000 pixels or more; even a smartphone can be hundreds of pixels high and wide.

These are things that are easy to do with pencil and paper using a ruler and compass, but on a computer the calculations need to be done for every pixel, and if you use the wrong method then it will take too long and the image will be displayed slowly or a live animation will appear jerky. In this section we will look into some very simple but clever algorithms that enable a computer to do these calculations very quickly.

To draw a line, a computer must work out which pixels need to be filled so that the line looks straight. You can try this by colouring in squares on a grid, such as the one below (they are many times bigger than the pixels on a normal printer or screen). We'll identify the pixels on the grid using two values, (x,y), where x is the distance across from the left, and y is the distance up from the bottom. The bottom left pixel below is (0,0), and the top right one is (19,19).

On the following grid, try to draw these straight lines by filling in pixels in the grid:

  • from (2, 17) to (10, 17)
  • from (18, 2) to (18, 14)
  • from (1, 5) to (8, 12)

Drawing a horizontal, vertical or diagonal line like the ones above is easy; it's the ones at different angles that require some calculation.

Without using a ruler, can you draw a straight line from A to B on the following grid by colouring in pixels?

Once you have finished drawing your line, try checking it with a ruler. Place the ruler so that it goes from the centre of A to the centre of B. Does it cross all of the pixels that you have coloured?

The mathematical formula for a line is \(y = mx + c\). This gives you the y value for each x value across the screen, and you get to specify two things: the slope of the line, which is \(m\), and where the line crosses the y axis, which is \(c\). In other words, when you are x pixels across the screen with your line, the pixel to colour in would be (\(x\), \(mx + c\)).

For example, choosing \(m=2\) and \(c=3\) means that the line would go through the points (0,3), (1,5), (2,7), (3,9) and so on. This line goes up 2 pixels for every one across \(m=2\), and crosses the y axis 3 pixels up (\(c=3\)).

You should experiment with drawing graphs for various values of \(m\) and \(c\) (for example, start with \(c=0\), and try these three lines: \(m=1\), \(m=0.5\) and\(m=0\)) by putting in the values. What angle are these lines at?

The \(mx + c\) formula can be used to work out which pixels should be coloured in for a line that goes between \((x_1, y_1)\) and \((x_2, y_2)\). What are \((x_1, y_1)\) and \((x_2, y_2)\) for the points A and B on the grid below?

See if you can work out the \(m\) and \(b\) values for a line from A to B, or you can calculate them using the following formulas:

\[ m = \frac{(y_2 - y_1)}{(x_2 - x_1)}\\ b = \frac{(y_1x_2 - y_2x_1)}{(x_2-x_1)} \]

Now draw the same line as in the previous section (between A and B) using the formula \(y = mx + c\) to calculate \(y\) for each value of \(x\) from \(x_1\) to \(x_2\) (you will need to round \(y\) to the nearest integer to work out which pixel to colour in). If the formulas have been applied correctly, the \(y\) value should range from \(y_1\) to \(y_2\).

Once you have completed the line, check it with a ruler. How does it compare to your first attempt?

Now consider the number of calculations that are needed to work out each point. It won't seem like many, but remember that a computer might be calculating hundreds of points on thousands of lines in a complicated image. Although this formula works fine, it's too slow to generate the complex graphics needed for good animations and games. In the next section we will explore a method that greatly speeds this up.

A faster way for a computer to calculate which pixels to colour in is to use Bresenham's Line Algorithm. It follows these simple rules. First, calculate these three values:

\[ A = 2 \times (y_2 - y_1) \\ B = A - 2 \times (x_2 - x_1) \\ P = A - (x_2 - x_1) \]

To draw the line, fill the starting pixel, and then for every position along the x axis:

  • if \(P\) is less than 0, draw the new pixel on the same line as the last pixel, and add \(A\) to \(P\).
  • if \(P\) was 0 or greater, draw the new pixel one line higher than the last pixel, and add \(B\) to \(P\).
  • repeat this decision until we reach the end of the line.

Without using a ruler, use Bresenham's Line Algorithm to draw a straight line from A to B:

Once you have completed the line, check it with a ruler. How does it compare to the previous attempts?

So far the version of Bresenham's line drawing algorithm that you have used only works for lines that have a gradient (slope) between 0 and 1 (that is, from horizontal to 45 degrees). To make this algorithm more general, so that it can be used to draw any line, some additional rules are needed:

  • If a line is sloping downward instead of sloping upward, then when P is 0 or greater, draw the next column's pixel one row below the previous pixel, instead of above it.
  • If the change in \(y\) value is greater than the change in \(x\) value (which means that the slope is more than 1), then the calculations for A, B, and the initial value for P will need to be changed. When calculating A, B, and the initial P, use X where you previously would have used Y, and vice versa. When drawing pixels, instead of going across every column in the X axis, go through every row in the Y axis, drawing one pixel per row.

In the grid above, choose two points of your own that are unique to you. Don't choose points that will give horizontal, vertical or diagonal lines!

Now use Bresenham's algorithm to draw the line. Check that it gives the same points as you would have chosen using a ruler, or using the formula \(y = mx+b\). How many arithmetic calculations (multiplications and additions) were needed for Bresenham's algorithm? How many would have been needed if you used the \(y = mx+b\) formula? Which is faster (bear in mind that adding is a lot faster than multiplying for most computers).

You could write a program or design a spreadsheet to do these calculations for you --- that's what graphics programmers have to do.

As well as straight lines, another common shape that computers often need to draw are circles. An algorithm similar to Bresenham's line drawing algorithm, called the Midpoint Circle Algorithm, has been developed for drawing a circle efficiently.

A circle is defined by a centre point, and a radius. Points on a circle are all the radius distance from the centre of the circle.

Try to draw a circle by hand by filling in pixels (without using a ruler or compass). Note how difficult it is to make the circle look round.

It is possible to draw the circle using a formula based on Pythagoras' theorem, but it requires calculating a square root for each pixel, which is very slow. The following algorithm is much faster, and only involves simple arithmetic so it runs quickly on a computer.

Here are the rules for the Midpoint Circle Algorithm for a circle around (\(c_{x}\), \(c_{y}\)) with a radius of \(R\):

\[ E = -R\\ X = R\\ Y = 0 \]

Repeat the following rules in order until \(Y\) becomes greater than \(X\):

  • Fill the pixel at coordinate (\(c_{x} + X\), \(c_{y} + Y\))
  • Increase \(E\) by \(2 \times Y + 1\)
  • Increase \(Y\) by 1
  • If \(E\) is greater than or equal to 0, subtract \(2 \times X - 1\) from \(E\), and then subtract 1 from \(X\).

Follow the rules to draw a circle on the grid, using (\(c_{x}\), \(c_{y}\)) as the centre of the circle, and \(R\) the radius. Notice that it will only draw the start of the circle and then it stops because \(Y\) is greater than \(X\)!

When \(Y\) becomes greater than \(X\), one eighth (an octant) of the circle is drawn. The remainder of the circle can be drawn by reflecting the octant that you already have (you can think of this as repeating the pattern of steps you just did in reverse). You should reflect pixels along the X and Y axis, so that the line of reflection crosses the middle of the centre pixel of the circle. Half of the circle is now drawn, the left and the right half. To add the remainder of the circle, another line of reflection must be used. Can you work out which line of reflection is needed to complete the circle?

  • Jargon Buster: Quadrants and octants

    A quadrant is a quarter of an area; the four quadrants that cover the whole area are marked off by a vertical and horizontal line that cross. An octant is one eighth of an area, and the 8 octants are marked off by 4 lines that intersect at one point (vertical, horizontal, and two diagonal lines).

To complete the circle, you need to reflect along the diagonal. The line of reflection should have a slope of 1 or -1, and should cross through the middle of the centre pixel of the circle.

While using a line of reflection on the octant is easier for a human to understand, a computer can draw all of the reflected points at the same time it draws a point in the first octant because when it is drawing pixel with an offset of (x,y) from the centre of the circle, it can also draw the pixels with offsets (x,-y), (-x,y), (-x,-y), (y,x), (y,-x), (-y,x) and (-y,-x), which give all eight reflections of the original point!

By the way, this kind of algorithm can be adapted to draw ellipses, but it has to draw a whole quadrant because you don't have octant symmetry in an ellipse.

Computers need to draw lines, circles and ellipses for a wide variety of tasks, from game graphics to lines in an architect's drawing, and even a tiny circle for the dot on the top of the letter 'i' in a word processor. By combining line and circle drawing with techniques like 'filling' and 'antialiasing', computers can draw smooth, clear images that are resolution independent. When an image on a computer is described as an outline with fill colours it is called vector graphics --- these can be re-drawn at any resolution. This means that with a vector image, zooming in to the image will not cause the pixelation seen when zooming in to bitmap graphics, which only store the pixels and therefore make the pixels larger when you zoom in. However, with vector graphics the pixels are recalculated every time the image is redrawn, and that's why it's important to use a fast algorithm like the one above to draw the images.

Outline fonts are one of the most common uses for vector graphics as they allow the text size to be increased to very large sizes, with no loss of quality to the letter shapes.

Computer scientists have found fast algorithms for drawing other shapes too, which means that the image appears quickly, and graphics can display quickly on relatively slow hardware - for example, a smartphone needs to do these calculations all the time to display images, and reducing the amount of calculations can extend its battery life, as well as make it appear faster.

As usual, things aren't quite as simple as shown here. For example, consider a horizontal line that goes from (0,0) to (10,0), which has 11 pixels. Now compare it with a 45 degree line that goes from (0,0) to (10,10). It still has 11 pixels, but the line is longer (about 41% longer to be precise). This means that the line would appear thinner or fainter on a screen, and extra work needs to be done (mainly anti-aliasing) to make the line look ok. We've only just begun to explore how techniques in graphics are needed to quickly render high quality images.

  • Project: Line and circle drawing

    To compare Bresenham's method with using the equation of a line (\(y = mx+b\)), choose your own start and end point of a line (of course, make sure it's at an interesting angle), and show the calculations that would be made by each method. Count up the number of additions, subtractions, multiplications and divisions that are made in each case to make the comparison. Note that addition and subtraction is usually a lot faster than multiplication and division on a computer.

    You can estimate how long each operation takes on your computer by running a program that does thousands of each operation, and timing how long it takes for each. From this you can estimate the total time taken by each of the two methods. A good measurement for these is how many lines (of your chosen length) your computer could calculate per second.

    If you're evaluating how fast circle drawing is, you can compare the number of addition and multiplication operations with those required by the Pythagoras formula that is a basis for the simple equation of a circle (for this calculation, the line from the centre of the circle to a particular pixel on the edge is the hypotenuse of a triangle, and the other two sides are a horizontal line from the centre, and a vertical line up to the point that we're wanting to locate. You'll need to calculate the y value for each x value; the length of the hypotenuse is always equal to the radius).

We've only scraped the surface of the field of computer graphics. Computer scientists have developed algorithms for many areas of graphics, including:

  • lighting (so that virtual lights can be added to the scene, which then creates shading and depth)
  • texture mapping (to simulate realistic materials like grass, skin, wood, water, and so on),
  • anti-aliasing (to avoid jaggie edges and strange artifacts when images are rendered digitally)
  • projection (working out how to map the 3D objects in a scene onto a 2D screen that the viewer is using),
  • hidden object removal (working out which parts of an image can't be seen by the viewer),
  • photo-realistic rendering (making the image as realistic as possible), as well as deliberately un-realistic simulations, such as "painterly rendering" (making an image look like it was done with brush strokes), and
  • efficiently simulating real-world phenomena like fire, waves, human movement, and so on.

The matrix multiplication system used in this chapter is a simplified version of the one used by production systems, which are based on homogeneous coordinates. A homogeneous system uses a 4 by 4 matrix (instead of 3 by 3 that we were using for 3D). It has the advantage that all operations can be done by multiplication (in the 3 by 3 system that we used, you had to multiply for scaling and rotation, but add for translation), and it also makes some other graphics operations a lot easier. Graphics processing units (GPUs) in modern desktop computers are particularly good at processing homogeneous systems, which gives very fast graphics.

  • Curiosity: Moebius strips and GPUs

    Homogeneous coordinate systems, which are fundamental to modern computer graphics systems, were first introduced in 1827 by a German mathematician called August Ferdinand Möbius. Möbius is perhaps better known for coming up with the Möbius strip, which is a piece of paper with only one side!

    Matrix operations are used for many things other than computer graphics, including computer vision, engineering simulations, and solving complex equations. Although GPUs were developed for computer graphics, they are often used as processors in their own right because they are so fast at such calculations.

    The idea of homogeneous coordinates was developed 100 years before the first working computer existed, and it's almost 200 years later that Möbius's work is being used on millions of computers to render fast graphics. An animation of a Möbius strip therefore uses two of his ideas, bringing things full circle, so to speak.