Bresenham Circles

In computer graphics there are only so many pixels available to represent shapes and objects. Also, there are no partial, or fractional, pixels to draw part of a line with coordinates that aren’t integer values. To show a line on the screen generated by a mathematical function, it’s necessary to make a pixel approximation for the real point on a line. The placement of pixels is limited to the available locations in the rows and columns of the screen.

Bresenham Algorithm

Early in the history of computer graphics, a method of deciding how to plot pixels for points on a real line was created. It’s called Bresenham’s Algorithm. The method decides on where to place a pixel based on finding out what screen location is the best guess, or approximation, for a point on a line. In the case of circles, a circle function might generate Y values from X values that start at the circle’s center an continue until X equals the circle’s radius. You might remember that the circle equation is:

X^2 + Y^2 = RADIUS^2

Of course, for every X we can find what Y is using these blocks:

let X = 0
let RADIUS = 0
let Y = 0
Y = Math.sqrt(RADIUS ** 2 - X ** 2)

The Decision Parameter

The problem is the real value for Y isn’t always an integer and a we need to decide what integer value would be the best to use for Y.

You can see in the picture below that a pixel on the left is plotted and there are two choices for plotting the next pixel, the blue pixel above the line or the red pixel below it.

The goal is to choose the pixel that is closest to the edge of the real circle. To decide which of the two choices is best for the next pixel location, something called a decision parameter is created. You see that the lengths of the blue and red lines are different than the length of the radius line. These lengths compared to the circle radius to give a radius error for the two pixel choices. The decision parameter is the combination of the two radius errors and becomes either a negative or positive number. If it’s negative, the blue pixel chosen. If positive, the red pixel is used.

To note the location of the current pixel we use the letter i added to the cooridinate names of (X, Y) so that they look like (Xi, Yi). To name the next pixel location we use the letter j with the coordinate.

If the current pixel is at (Xi, Yi) then the blue pixel is at (Xi + 1, Yi). The red pixel then, is at (Xi + 1, Yi - 1). So, for these pixels, we know that Xj = Xi + 1 for both blue and red pixels, Yj = Yi for the blue pixel, and Yj = Yi - 1 for the red pixel.

The decision parameter is created by adding the errors from both pixel choices. The error amount is the difference between the square of the circle radius and the squares of the coordinate distances to the pixel choices: X^2 + y^2 - radius^2.

Using this error expression, the blue and red pixel errors are:

• Blue pixel error: (Xi + 1)^2 + Yi^2 - radius^2
• Red pixel error: (Xi + 1)^2 + (Yi - 1)^2 - radius^2

We name our decision parameter with the letter D. Just like with the names of the cooridates, the current D is Di and the next value is named Dj.

When the blue pixel error is added to the red pixel error, combining all the terms, the value for Di becomes:

• The equation for parameter Di = 2 * (Xi + 1)^2 + Yi^2 + (Yi - 1)^2 - 2 * radius^2

So, this is the value of the decision parameter for the current pixel choice. To get a value of Dj for the next pixel choice, just replace Yi with Yj and use this trick, replace Xi with Xi + 1:

• The equation for parameter Dj = 2 * (Xi + 2)^2 + Yj^2 + (Yj - 1)^2 - 2 * radius^2

Decision evaluation

When the blue pixel is closest to the actual circle edge we know that the decision parameter will be negative because the positive distance above the circle is less then the negative distance of the red pixel below. In the opposite case, the red pixel is closest to the circle when the decision paramter is positive. This is because the negative distance from the circle is less than the positive distance of the blue pixel above.

For the pixel error shown in the picture, the pixel chosen will be the blue pixel as you can see that it’s closer and the value for both errors combined is negative.

The way to find out the decision parameter for the next pixel choice (Dj) is to use Di twice in the equation for Dj. It’s added in once with its unknown form (using just the symbol Di) and then subtracted by it’s expanded form (using the expression shown for Di above). This doesn’t break the equation for Dj since Dj = Di + (expression for Dj) - (expression for Di). The steps to get to the final form for Dj aren’t shown since there many terms to use and some reduction in the expression is needed.

As it turns out, the equation for Dj has two forms depending on whether Di is negative or positive. The negative case means that the terms for the blue pixel coordinate are used in the equation. The terms for the coordinate of the red pixel are used when Di is positive. This gives us two simple forms of calculating Dj:

• Di <= 0: Dj = Di + 4 * Xi + 6

  let x = 0
  let d = 0
  d += 4 * x + 6

• Di > 0: Dj = Di + 4 * (Xi - Yi) + 10

  let x = 0, y = 0, d = 0
  d += 4 * (x -y) + 10

Program for Bresenham Circles

The program draws new circles with either an increasing or decreasing radius. The value of x varies from 0 to radius to pick pixels for just one-eighth of the circle, an octant. The pixels for the other 7 corresponding octants are plotted based on the symmetry properties of a circle.

The decision parameter is set to an inital value where Xi = 0 and Yi = radius. Using these values in the equation for Di gives us: Di = 3 - 2 * radius. Both the pixel choice and the Dj calculation occur in the conditionals for Di <= 0 or Di > 0.

let x = 0
let y = 0
let d = 0
let cx = 31
let cy = 31
let radius = 0
let grow = true
let circleSprite: Sprite = null
let circle: Image = null
circle = image.create(64, 64)
circleSprite = sprites.create(circle, 0)

forever(function () {
    circle.fill(6)
    d = 3 - 2 * radius
    x = 0
    y = radius

    while (x <= y) {
        circle.setPixel(cx + x, cy + y, 4)
        circle.setPixel(cx + x, cx - y, 4)
        circle.setPixel(cx - x, cx + y, 4)
        circle.setPixel(cx - x, cy - y, 4)
        circle.setPixel(cx + y, cy + x, 4)
        circle.setPixel(cx + y, cy - x, 4)
        circle.setPixel(cx - y, cy + x, 4)
        circle.setPixel(cx - y, cy - x, 4)
        if (d <= 0) {
            d += 4 * x + 6
        } else {
            y += -1
            d += 4 * (x - y) + 10
        }
        x += 1
    }

    if (grow) {
        radius += 1
    } else {
        radius -= 1
    }
    if (radius > 31) {
        grow = false
    } else if (radius < 1) {
        grow = true
    }
    pause(100)
})