Bresenham's Circle Generation Algorithm

---

---

Bresenham's Circle Generation Algorithm is a fundamental technique in computer graphics to generate circles. In this chapter, we will explain how the algorithm works, its steps, and provide a detailed example, for a better understanding.

Bresenham's Circle Generation Algorithm

Bresenham's algorithm for circles works by generating points from 90 to 45. It makes moves only in the +X and -Y directions. The goal is to find the pixels that best approximate a true circle on a digital screen.

How does the Bresenham's Circle Generation Algorithm Works?

Let's understand how the Bresenham's circle generation algorithm works −

• Point Generation − The algorithm starts at 90° and moves towards 45°. It decides which pixel to light up next based on two possible actions:
• Move one unit in the x-direction − Move one unit in both the x-direction and negative y-direction
• Decision VariableTo choose between these actions, the algorithm uses a decision variable 'd'. This variable helps determine which pixel is closest to the true circle.
• Eight-Way Symmetry − The algorithm uses eight-way symmetry. This means it only calculates points for one octant of the circle, as given in the above figure for the octates. Then it reflects these points to create the full circle.

Algorithm Steps

Here is a step-by-step breakdown of Bresenham's Circle Algorithm −

Step 1 − Start the algorithm

Step 2 − Declare variables: p, q (circle centre coordinates), x, y (current point), r (radius), d (decision variable)

Step 3 − Input the radius r

Step 4 − Calculate initial d: d = 3 - 2r

Step 5 − Set initial x = 0, y = r

Step 6 − Check if x y. If true, stop. If false, continue

Step 7 − Plot eight symmetric points

Step 8 − Update d and x (and y if needed)

Step 9 − Go back to step 6

Step 10 − End the algorithm

Example

For centre at point (0, 0) with radius 10, the algorithm will work in the following way −

x = 0, y = r = 10 is the starting point, and the decision variable d is initialized. For each step, the decision variable d is updated. If d <= 0, only x is incremented; otherwise, both x and y are updated.

At each step, the 8-way symmetric points are calculated and printed as shown in the table. The resulting coordinates will draw the circle with the centre at (0, 0) and radius 10.

Advantages of Bresenham's Circle Generation Algorithm

Bresenham's Circle Generation Algorithm has several benefits, it uses only integer addition and subtraction which is efficient. And this makes it faster than other circle-drawing methods. It produces circles that closely approximate true circles.

Conclusion

In this chapter, we explained the Bresenham's Circle Generation Algorithm in detail. We covered its basic concept, how it works, and provided a step-by-step breakdown of the algorithm. We also walked through a detailed example.

In the next chapter, we will see another circle generation algorithm called the mid-point algorithm which is quite similar to Bresenham's algorithm.