A fundamental operation in 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.
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 screen is 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).
Try to draw these straight lines by clicking on pixels in the following grid:
from (2, 17) to (10, 17)
from (18, 2) to (18, 14)
from (1, 5) to (8, 12)
Drawing a horizontal, vertical or 45 degree 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 .
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 ,
and where the line crosses the y axis, which is .
In other words, when you are x pixels across the screen with your line, the pixel to colour in would be (, ).
For example, choosing and 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 , and crosses the y axis 3 pixels up ().
You should experiment with drawing graphs for various values of and (for example, start with , and try these three lines: , and ) by putting in the values.
What angle are these lines at?
The formula can be used to work out which pixels should be coloured in for a line that goes between and .
What are and for the points A and B on the grid below?
See if you can work out the and values for a line from A to B, or you can calculate them using the following formulas:
Now draw the same line as in the previous section (between A and B) using the formula to calculate for each value of from to (you will need to round to the nearest integer to work out which pixel to colour in).
If the formulas have been applied correctly, the value should range from to .
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.
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 value is greater than the change in 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 just choose points that will give horizontal or vertical 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 .
How many arithmetic calculations (multiplications and additions) were needed for Bresenham's algorithm?
How many would have been needed if you used the 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 (, ) with a radius of :
Repeat the following rules in order until becomes greater than :
Fill the pixel at coordinate (, )
Increase by 1
If is greater than or equal to 0, subtract from , and then subtract 1 from .
Follow the rules to draw a circle on the grid, using (, ) as the centre of the circle, and the radius.
Notice that it will only draw the start of the circle and then it stops because is greater than !
When becomes greater than , 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?
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.
Line and circle drawing
To compare Bresenham's method with using the equation of a line (), 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).