In the previous of my not so amazing C# tutorials I described how to draw 2D triangles. This was a useful exercise since drawing triangles, filled or not, involved interpolating values (we need to go from there to there in that many steps). Interpolation is a useful technique that can be used in a number of situations from moving models/sprites to faking missing data in scientific charts – anything that requires finding a number of intermediate states really. However that was not the only reason for selecting triangles. The author of the previous tutorial (all tremble before my evil goatee) also claimed that triangles are useful for making more complex geometric shapes. Lets put this claim to the test by using our pretty triangles to make a nice round (well, almost) circle. Building circles out of triangles might sound a bit insane as generally speaking triangles are not exactly known for their roundness. This is I guess what makes it fan. What makes this even more fan is that we are going to draw our circles without using any of them confusing cos() and sin() functions. Instead we are going to use Pythagoras, a dead Greek philosopher.

It is time to consider the task at hand. A good starting point would be to consider what a circle actually is. One definition could be that of a collection of pixels which have the same distance (radius) from a central point. For a filled circle we would need to modify the above definition a tiny bit to include the pixels with a distance less than or equal to the radius of the circle. In other words, in order to draw circles we need to measure distance! This is where Pythagoras and his theorem come in. Apparently 2500 years ago that guy spent an incredible amount of time observing tiles (probably he was constipated or something). Now, imagine three bathroom tiles forming a right triangle – Pythagoras noticed that the area of the two smaller bathroom tiles is the same as the area of the bigger bathroom tile. This is what we call Pythagoras’ theorem. Let us try to visualise these words of wisdom with the aid of a diagram as not everybody has conveniently placed bathroom tiles in their toilets (figure 1.1).

According to figure 1.1, dark blue is equal to dark green + dark red (well, the areas those colours correspond to anyway). This is informative, but a more mathematical way of expressing it would be even more helpful. According to geometry, the area of a square can be found by multiplying one of its sides – any of them will do as they are of equal length, savvy - with itself. Therefore we can express Pythagoras’ observation as:

c² = a² +b²

We can easily deduce that any point with coordinates (a, b) forms a right triangle with the axis centre (0, 0). The length of the hypotenuse will be the distance and can be found by calculating the square route of the squares of the two sides. Interestingly enough, Pythagoras’ theorem will work with any number of dimensions (number of values used to define a point). It has been mathematically proven apparently. The distance will always be equal with the square route of the sum of the squares of the values you decided to use to define a point (you have n dimensional when n values are used for each point – mathematicians have no imagination). In this case we are using two (a, b), but we could easily apply the same formula for three (x, y, z) or more dimensions; large numbers of dimensions can be found in a number of scientific applications – this however is beyond the scope of this article/tutorial.

It is time now to use this theorem to produce a circle. Have a look at figure 1.2. Typically the radius will be given. Since we know our circle will be 2*radius pixels tall we know that the values in the Y-axis will be larger than negative radius and less than positive radius. For each value in the Y-axis we can calculate its corresponding X-Axis position (and this plot a point) by using the formula we introduced.

x = SQRT ( r² – y²)

Where x is the X-Axis coordinate for our point, r is the circle radius, and y a value we picked in the range of –radius to radius. If we pick all the different y values within that range ( -r <= y <= r) we can draw a perfect circle. Instead we are going to cheat a bit as calculating square routes takes quite a bit of processing time. Clearly, the less of those types of calculations we need to do the better. As it happens circles are rather symmetrical. Take a minute to look at figure 2.

As we can see in figure 2.1 a circle can be split in two half-circles. We did so by drawing a line alongside the Y-Axis. We can pick y values in the range or –r to r (yellow line) and calculate their corresponding x values. Using x will give us the x and y values (x, y) we need to draw half the circle – negating x will give us the other half (-x, y). As it turns out this is the only way to use our formula as it will always produce a positive result! This is because any number, positive or negative, multiplied by itself will give a positive result. Using the square root function provided by the math library will also always give a positive result (though in proper maths you would get two possible results - a positive and a negative one). As such negating the x value is the only way to draw the other half of our circle.

In figure 2.2 we split the circle into 4 equal parts along the X and Y axis. We only need to calculate the x values corresponding to the red part of the line by using y value in the range of 0 to r (yellow line), where r is our radius. We can use each set or x and y value to draw 4 points by negating or not the x and y values (4 combinations). So, in other words, we need one set of calculations for each four circle points. This is good but we can do even better!

In figure 2.3 we split the circle in 8 parts. This is done by drawing imaginary lines in the horizontal, vertical, 45 degrees and -45 degrees directions. What is special about the 45 degree angle is that it happens when x becomes equal to y. Any point (x, y) bellow this 45 degree mark can be used to find a circle point above the 45 degree mark (y, x) by swapping the x and y values around. So if we know the x and y values that correspond to a 40 (45 - 5) degree angle – swapping the x and the y around (y, x) would give us the point for the 50 (45 + 5) degree value. What this means in effect is that we can reduce the number of calculations further as we only need y values in the range of 0 to k (yellow line), where k = x = y. By replacing x and y with k in our formula it is straightforward to prove that:

k = SQRT (1/2) * r

We can use what we done so far to draw a perfect circle in k steps (with y value in the range of 0 to k and y increased by one for each loop iteration). This will be pretty efficient as we will only be doing the calculation once for every 8 circle points. I am going to cheat even more though. We do not really need a pixel perfect circle. What we need is an approximation, something that looks round enough! Sample enough points (y values) and you can trick people into thinking the circle is round, yes. So we need a function that only calculates some values and uses line segments to fill in the gaps between them. Assuming we want “steps” number of iterations, we need to calculate x values placed k/steps pixels apart in terms of the Y-axis. The result will look perfect only if steps=k, but assuming enough “steps” are used very few people will be able to tell the difference. Performance gains from this trick will be minimal if near perfect circles are required all the time but it is more fun to do that way anyway. It is time to start coding then. Our function takes as parameters the circle position (x, y), the radius, the number of steps, the weight (width) of the circle outline to draw and finally the colour. First we need to ensure that our parameter “steps” is valid and calculate the number of pixels (step) we are going to climb up the Y-axis in each loop iteration.

// exit if steps are 0 or less (to avoid error)
if (steps < 1) return;

// calculate midpoint for a 45 degrees arc, assuming r = 1
// x = y and x^2 + y^2 = 1 => 2*x^2 = 1 => x = sqrt(1/2)
float k = (float)Math.Sqrt(0.5) * (float)radius;
// find out the loop iterations
float step = k / (float)steps;
// a step of less than 1 pixel is pointless so..
if (step < 1)
{
     step = 1;
     steps = (int)k;
}

Having a step value of less than 1 is both unnecessary and a performance drain – thus the last 5 lines of code ensuring that it never happens. The worst case scenario (performance wise) is k steps with a step of 1 pixel. Let us carry on then – back to the coding. We need to define some variables to hold out line segments start and end points. Lets agree that p stands for previous and n stands for next.

// Variables used to store start of line (previous value)
float px;
float py;
// Store end of line (next value)
float nx = radius;
float ny = 0;
// pre-calculate radius 
float r2 = radius * radius;

Notice that assuming we start our loop with a y value of 0 the first x value will be radius. Also that we pre-calculate our radius squared value. This tiny optimisation will save us a tiny bit of processing time – every little helps though so why not. Now it is time to do out main loop.

// y is known as we know our Y-axis step
for (int i = 0; i < steps; i++)
{
     // store previous point (start of line)
     px = nx;
     py = ny;
     // calculate next point (end of line)
     ny += step;
     nx = (float)Math.Sqrt(r2 - (ny * ny));

     // draw lines for all 8 45 degree segments
     Line(x - px, y - py, x - nx, y - ny, weight, color);
     Line(x + px, y - py, x + nx, y - ny, weight, color);
     Line(x - px, y + py, x - nx, y + ny, weight, color);
     Line(x + px, y + py, x + nx, y + ny, weight, color);
     Line(x + py, y + px, x + ny, y + nx, weight, color);
     Line(x + py, y - px, x + ny, y - nx, weight, color);
     Line(x - py, y + px, x - ny, y + nx, weight, color);
     Line(x - py, y - px, x - ny, y - nx, weight, color);
}

This is actually rather straightforward – notice how swapping signs and x and y values around is been used to draw all the points around our circle centre (x, y). That said the circle centre coordinates (x, y) are always added to the p and n values we calculate (otherwise we would simply always draw out circle around the 0. 0 point). Now it is time to consider how to draw a filled circle using triangles like I promised. All we need to do is actually modify this last piece of code - replace lines with triangles. Now the best (as more efficient) way of doing that would be to draw triangles connecting corresponding points in opposite sides of the Y-axis. Instead this time I am going to go for convenience rather than performance and draw my triangles using the centre point of the circle as the third triangle point. This is easier to do but it does mean I am using more triangles than necessary.

// y is known as we know our Y-axis step
for (int i = 0; i < steps; i++)
{
     // store previous point (start of line)
     px = nx;
     py = ny;
     // calculate next point (end of line)
     ny += step;
     nx = (float)Math.Sqrt(r2 - (ny * ny));
     // Fill gaps between points
     FillTriangle(x + nx, y + ny, x + px, y + py, x, y, color);
     FillTriangle(x - nx, y + ny, x - px, y + py, x, y, color);
     FillTriangle(x + nx, y - ny, x + px, y - py, x, y, color);
     FillTriangle(x - nx, y - ny, x - px, y - py, x, y, color);
     FillTriangle(x + ny, y + nx, x + py, y + px, x, y, color);
     FillTriangle(x - ny, y + nx, x - py, y + px, x, y, color);
     FillTriangle(x + ny, y - nx, x + py, y - px, x, y, color);
     FillTriangle(x - ny, y - nx, x - py, y - px, x, y, color);

     // Fill gaps between triangles
     Triangle(x + nx, y + ny, x + px, y + py, x, y, 4, color);
     Triangle(x - nx, y + ny, x - px, y + py, x, y, 4, color);
     Triangle(x + nx, y - ny, x + px, y - py, x, y, 4, color);
     Triangle(x - nx, y - ny, x - px, y - py, x, y, 4, color);
     Triangle(x + ny, y + nx, x + py, y + px, x, y, 4, color);
     Triangle(x - ny, y + nx, x - py, y + px, x, y, 4, color);
     Triangle(x + ny, y - nx, x + py, y - px, x, y, 4, color);
     Triangle(x - ny, y - nx, x - py, y - px, x, y, 4, color);
}

The one thing that did not work quite as planned was that adjacent filled triangles left small gaps in between them (edges do not align perfectly). A filled circle full of tiny little holes is not as pretty and nice as it should be. A quick fix is drawing some triangle outlines (using the triangle() function found in our library) with a weight (outline width) of 4 pixels. I admit this is not ideal but hey, it works. Most importantly, I have proven my point – triangles are both elegant and useful. You can make all sorts of shapes out of them, including the most unlikely of them all – a circle. This subject also gave an excuse to introduce Pythagoras’ theorem. This is a must know thing for all programmer interested in computers graphics and games and staff; another tool for the graphics programmer Swiss army knife then. The source code (C Sharp) for the circle (as well as the previous tutorial which this one builds upon) can be found in the cs file attached.

Note: When I decided to make this tutorial I did the mistake of searching for similar things from Google. I was so overwhelmed by the number of circle tutorials out there that I almost did not make one. Eventually I did so since I had already started with the previous tutorial and I needed to finish off – circles needed to be added to the simple 2D library we constructed as they are very basic 2D primitive operations. I hope I did manage to explain things somewhat better (you will be the judge of that) but all in all perhaps I need to pick up less well documented tutorial subjects in the future. Let me know if you have any ideas/suggestions. I can’t promise I will do them but I promise I will consider them.