Software Development

I've been using Bresenham's Line Drawing Algorithm in many places I didn't expect. In short, what Bresenham's is good at is not line drawing, but more generically, at knowing the ratio of two increasing sequences. It's like two gears with different number of teeth. It will tell you based on the rotation of one gear if the other has done one full revolution. Not only that, but it will keep track of any partial rotation left over in order to tell you each successive full rotation of the other gear.

So essentially anything that has two increasing periods can be implemented via Bresenham's. This includes an averaging resampler for shrinking and enlarging images (this requires two Bresenham's algorithms, one for each axis), resampling statistical data to fit x nodes, etc. Now, for resampling partial values, this requires a little more work. One example of this is Wu's algorithm that handle anti-aliasing. But I don't consider this an extension of Bresenham's line drawing algorithm. It's not really based on the same algorithm though you could likely implement it using fixed point notation which is what I'm after.

First, Brensenham's algorithm. The simplest case is where we always increase on the x axis by one pixel. In this case, we want to know when to jump up to the next row when drawing a line. A better way to look at this is through a ratio. Suppose your line is 12 pixels wide and 5 pixels high. The ratio of the height vs the width is 5:12, or 5 to 12. Said another way, the height is five twelfths of the width. This means every time we advance one pixel on the x axis, the y axis will increase by five twelfths. When adding fractions, the denominator always stays the same. The top part is what gets added. So let's state this.

const Numerator = 5
const Denominator = 12
Accumulator = 0
Pixel_x_index = 0
Pixel_y_index = 0

The accumulator is simply a tracking variable that let's us know how many five twelfths we've used up. We actually add 5 to the accumulator every time we advance by one pixel on the x axis.

After the first pixel on the x-axis, we have the following.

// Step 1
const Numerator = 5
const Denominator = 12
Accumulator = 5
Pixel_x_index = 1
Pixel_y_index = 0

Numerator and Denominator never change. This is our fixed ratio. Only the accumulator changes (and the pixel indices).

// Step 2
const Numerator = 5
const Denominator = 12
Accumulator = 10
Pixel_x_index = 2
Pixel_y_index = 0

// Step 3
const Numerator = 5
const Denominator = 12
Accumulator = 15
Pixel_x_index = 3
Pixel_y_index = 0

Here, we have an interesting situation. The accumulator is larger than the Denominator. It's saying we have 15/12. Said another way, we have 1 and 3/12th. Since we have a one that can be extracted from the fraction, it means the y axis can jump up to the next row. Now we can subtract this 1 pixel and continue on. Subtracting 12/12 is subtracting 12 from the accumulator.

if (Accumulator > Denominator)
{
  // Go to next row.
  Pixel_y_index++;
  Accumulator -= Denominator;
}

As you can see we keep the fractional part. Here is what we have once we do this adjustment.

const Numerator = 5
const Denominator = 12
Accumulator = 3
Pixel_x_index = 3
Pixel_y_index = 1

Note that we have 3 in the Accumulator. This means that 3/12th of the pixel on row 1 would have that intensity. If we are using grayscale from 0 to 255, then 255 * 3/12 = 64 (rounded). The pixel below it would have intensity of 255-64 = 191. We'll get back to this. But just remember that we do have the fractional parts in case we want to implement antialiasing. Only problem is that divisions are quite slow.

Continuing on:

// Step 4
const Numerator = 5
const Denominator = 12
Accumulator = 8
Pixel_x_index = 4
Pixel_y_index = 1

// Step 5
const Numerator = 5
const Denominator = 12
Accumulator = 13
Pixel_x_index = 5
Pixel_y_index = 1

Here, we end up with the Accumulator being larger than 12 (the Denominator) yet again. So we jump to the next row again and subtract 12/12, which is equivalent to subtracting 12 from the accumulator since the denominator never changes with addition and subtraction. Note that we got 2 pixels on this row instead of 3 last time.

const Numerator = 5
const Denominator = 12
Accumulator = 1
Pixel_x_index = 5
Pixel_y_index = 2

And so on.

If you'll note, the numerator is set to the smaller value and the denominator to the larger value. That's always the same setup. Then each step is simply adding the numerator to the accumulator (which is also a numerator, but one that we keep updating).

For the fractional part, it is always accumulator divided by the denominator for the current pixel and 255 - top_pixel_value for the bottom pixel. As you'll notice, this makes our line start one line too low. This is why Bresenham's line drawing algorithm starts with the accumulator set to the halfway point of a pixel. Unfortunately, this makes it more difficult to understand what is going on. In our example, we would just start with the accumulator at 6 (half of the denominator), but not if we do antialiasing.

For different slopes where the x axis is less than the y axis, then you need to alter your variables accordingly. These would be the Pixel_x_index and Pixel_y_index would be increased or decreased depending on the quadrant and slope.

When it comes to antialiasing, we already showed how you can use Accumulator/Denominator. But that's slow because of the division, not to mention the multiplication with 255. For the pixel value, we could use 256 instead and left shift and then do a quick check to make sure it stays at or below 255. Taking the top bit and subtracting works fine for example.

As to removing the division, there is a trick that can be done. But it has a limitation. You need twice as many bits as the next power of two of the denominator. For example, we have 12. The next largest power of 2 is 16. That takes 4 bits. We would then need 8 bits for this to work. What we do is rescale 12 to 16 and apply the same scaling factor to the numerator. Let's try that.

ScaleFactor = 16 / 12 = 1.3333...
Numerator = 5 * ScaleFactor = 6.6666666....
Denominator = 16

The numerator is a floating point number. This won't work. This is where those extra four bits come into play. We multiply by 16 again, both the numerator and the denominator. This is why we need twice the number of bits. To have a place to keep fractional bits in a fixed point notation. The drawback is that you are limited to line widths or heights of 65536 with 32bit integers. Usually not a problem, but can be if you deal with large images.

Numerator = 107 (rounded up)
Denominator = 256

Now, we have a new ratio. It's not quite the same ratio. But it will still work. The fact that we used as many bits for the fractional part of the numerator as it takes to hold the original value of the numerator means that we will have to go larger than that to get a significant error. And since we'll never go over as that is the length of our line, we are safe.

// Step 1
Accumulator = 107
Pixel_x_index = 1
Pixel_y_index = 0

// Step 2
Accumulator = 214
Pixel_x_index = 2
Pixel_y_index = 0

// Step 3
Accumulator = 321
Pixel_x_index = 3
Pixel_y_index = 0

Here, 321 is larger than 256. So we increase the y index. Note now that since our denominator is already 256, we can use the numerator's value (after subtracting 256) as the pixel value.

After adjusting:
Accumulator = 65
Pixel_x_index = 3
Pixel_y_index = 1

If the denominator was 512 instead of 256, you would shift to the right by 1 before using it as the pixel value. If the denominator was 1024, you would shift by 2 and so on. No more divisions. It is usually best to have the denominator be at least 256 just to have better precision.

Note that our accumulator is 65. The original value we had calculated was 64. So there is some rounding error going on. However, these will stay the same throughout. You could calculate the exact value and adjust. So if we're two off, we could subtract 2 from the Accumulator during setup. I don't feel this is necessary for most cases though.

// Step 4
Accumulator = 172
Pixel_x_index = 4
Pixel_y_index = 1

// Step 5
Accumulator = 279
Pixel_x_index = 5
Pixel_y_index = 1

Here, we're higher than 256 again. So we adjust and increase the y index.

Accumulator = 23
Pixel_x_index = 5
Pixel_y_index = 2

Again, we're off by 2. The original value would have been 21.

There is another advantage to having powers of two besides being able to do antialiasing. We can now skip over several pixels at once. We no longer need to put the smaller value as the Accumulator. We can now put the larger value. In the example above, if we do a right shift by 8, we would get how many pixels to set.

Now, instead of increasing the x axis at every iteration, we can increase the y axis at every iteration and find out how many pixels on the x axis to turn on. Remember that if you're using this inverted technique, you need even more bits to store the larger numerator. Not only that, but since this is inverted, we need to take into account partial pixels on the x axis. In the original version, a partial pixel was enough to go up to the next row. So we need to add a full x pixel value to the accumulator before we start to take this into account so that we see these partial pixels.

ScaleFactor = 16/5 = 3.2
Numerator = 12 * ScaleFactor = 12 * 3.2 = 38.4
Denominator = 16

Multiply by 16 to get some fractional bits.
Numerator = 614
Denominator = 256

If you'll note, the ratio is nearly identical as before. But it's inverted.

// Step 0. Add full x pixel to accumulator
Accumulator = 256
Pixel_y_index = 0
Pixel_x_index = 0

// Step 1
Accumulator = 870
Pixel_y_index = 1
Pixel_x_index = 0

As you can see, the Accumulator is larger than the denominator (of 256) on the very first step. But that's ok. We simply shift right by 8 to get the number of pixels on the x axis to turn on. The value is 3. So there are 3 pixel to set exactly like the initial version indicated. The next step (when we increase the y pixel) should tell us that 2 pixels need to be set. First we adjust. We currently have:

Accumulator = 870
Pixel_y_index = 1
Pixel_x_index = 3

And before continuing, instead of subtracting 256, we can simply clear out the high bits starting at bit 8. The fractional part is all we want and this is what was achieved by subtracting 256 before since only bit 8 could be set. But now that more than bit 8 can be set, we clear all the high bits. This is simply done with the following:

Accumulator = Accumulator & (~255).

Accumulator = 102
Pixel_y_index = 1
Pixel_x_index = 3

// Step 2
Accumulator = 716
Pixel_y_index = 2
Pixel_x_index = 3

716 >> 8 = 2

So two pixels are set on the x axis. Exactly like the original.

// Adjust
Accumulator = 204
Pixel_y_index = 2
Pixel_x_index = 5


The nice part about this is that we can still do antialiasing by taking extra step for partial pixels in the exact manner that we did before.

So that's Bresenham's from simple to more advanced. I use the above technique to write image resampling code when the video card cannot be used (ie. must be in software) and it works really well. The only thing to watch out for in the inverted method is that you need more bits to hold the larger number. Also beware fractional starting points. Those can be difficult to determine the exact starting value for the accumulator.

One final word. You may have seen some algorithms that check if the accumulator (or error variable) is above 0. That's just another way of doing the same thing as the non-inverted version. Instead of checking if Accumulator >= Denominator, they simply subtract the denominator FIRST and then check if the accumulator goes above 0. It's 100% identical as to what we were doing. Some older machines would be faster checking against 0 than a value stored in a register or memory location. I doubt this is a worthwhile optimization anymore.

// Original check
if (Accumulator >= Denominator) ...

// Subtract Denominator from both sides
if (Accumulator - Denominator >= Denominator - Denominator) ...

// Simplify
if (Accumulator - Denominator >= 0) ...

As you can see, it's mathematically equivalent. Just subtract the Denominator from the Accumulator beforehand and you can do "if (Accumulator >= 0)".

I hope that Bresenham's Line Drawing Algorithm is clearer and joins its rightful place as a tracker of ratios that can be used in all sorts of applications instead of limiting it to line drawing. In my opinion, it is truly one of the great computer algorithms of all time.

Here is another theory that is commonly accepted, but is completely bogus. In the first part of this article, I only want to dispute the theory. The second half of this article deals with mapping natural numbers to real numbers. I'm playing devil's advocate in the second part because I actually believe that Cantor's conclusion is correct, but not the theory that he uses in trying to get there. Unfortunately, I must reject the conclusion as well for the time being.

As a quick recap, Cantor's theory says that you can't count to N² by using N entries and N digits. So no matter how many digits you use (say X digits), you can always create a new (X+1)^th number not already listed (by using the opposite of the digits in the diagonal). This is supposed to mean that the list of entries with infinite digits can never be put into a list because if you try to do so, you can create a new entry not found in said list. IOW, the number of entries will always be larger than the number of digits.

BOGUS!

Read more...