Using Bresenham line algorithm for better PWM

In this tutorial, i explain the use of a line drawing algoritm to distribute PWM pulses to reduce flicker with dimmed led’s.
PWM is cool. It’s an acronym for Pulse Width Modulation. You can use it to make awesome synthesizer sounds, drive servo motors, and control the brightness of led’s!

The trick with lights is a kind of magic. When you switch a led on, its almost instantly on. No heating up or such as you would with a regular incandescent bulb (note 3). it goes to maximum brightness in a microsecond. the same thing happens when you turn it off. It has no afterglow. If you turn it on and off very quickly, and i mean many many times a second, the human mind cannot see it going on and off again any more. Above 100 flickers per second, or 100 Hz, the human brain can no longer distinguish the on/off pulses and sees it as a constant brightness (note 1).

I used this effect to dim the lights of my lego truck project, and save a lot of battery power on the side!

This persistence of Vision can be used to dim the leds at almost arbitrary brightness. Let’s use some widely known definitions: a complete cycle on and off is called a pulse. The length of time it is on, compared to the time it is off, is called the pulse width. If you lower the ratio between on and off, the led appears to be dimmer.

Now there’s a little problem with that pulse width. If the total length of the pulse is too long, the eyes start to notice the on/off effect. In practice, this just means that the off-period basically is too long. Especially when doing PWM in software, this can be a nuisance because you cannot switch the led’s on and off fast enough to hide the flicker.

The solution used on most of the software PWM libraries, like softPWM or the excellent M5451 library, is to evenly distribute the times over the entire pulse time, as shown in the crude drawing on the right.

In this example, we have a total pulse time of 100 units, say milliseconds, but the LED is only on for 20% of the time. Instead of turning it on for 20msecs and turning it of for 80, we turn it on for 5 msecs with 20 msecs in between. Over the total period of 100 milliseconds, the led was on for an equal amount of time, but without the noticeable 80 milliseconds. Going even further we could turn it on for 1 msec and off for 4 msecs (20 times). The principle of dividing the pulse to achieve the same average density is called Pulse Density Manipulation or PDM (note 2)

Foto

Distribution of on/off times
This was a easy example. We calculated this one by hand. But if we wanted to change the brightness to let’s say 57, that would become more difficult. “Oh yeah, it’s easy” you say, “just divide the 57/100, we only need to ….” ah you see? it gets difficult.
In the early days of computer programming, there were no OS core graphics libraries to use, or even download the libraries from the internet. Everything had to be programmed by hand. There was the simple problem of drawing a line on a pixelated computer screen, on its own a difficult concept. You could use floating point arithmetic to calculated the coordinates but that was far from efficient.
An excellent mathematician named Bresenham came up with an algoritm to draw lines without the need for floating point numbers. All could be done with standard integers. Basically the algorithm magnifies the floating point fractions to a number big enough to fit in an integer.
Look at the right, A) is a most simple, 45 degree line.  and B) a flatter line.

With a) for every horizontal step, the vertical step is increased 1. Line B) is much less steeps, and needs more horizontal steps before increasing the vertical value. 

Foto

Using steps to draw a line in computer graphics
Back to our pulse distribution problem. We use the vertical steps as ‘ON’ pulses, while the time is indicated by the horizontal steps.

As time progresses to the right, we check if a vertical step is needed. If the vertical rises one step, we turn the light on. If it stays on the same vertical, turn it off.

The process repeats at the end of the graph, we start with 0 again, looping until infinity.

Foto

Using line drawing logic to distribute the pulses
Until now, i’ve used the number 100 as a maximum time, and brightness. Computers like to work with multiples of 2, so in my software i used the maximum value of a single byte, 255. 0 is fully off and 255 is maximum brightness (always on).
Although Bresenham’s algorithm can cope with lines going to the left, right, up, down in all directions, for our problem we can ignore all those other quadrants, because our vertical increase is always less than 100%, compared to the time passed. We can use this effect to simplicate our algorithm. The algorithm below was taken from the Wikipedia page for Bresenham’s algorithm. I won’t repeat the intricate working here, the wiki page does a far better job than me.

By using constants for x0, x1 and y0 the algorithm gets substantially simpler.

Foto

Optimizing the algoritm
After optimisation, the function turns down to this:
function distribute(brightness)
{
   int error = 128;
   for x from 0 to 255;
   {
      error := error - brightness;
      if error < 0 then
      {
         lightOn();
         error := error + 255;
      }
      else
      {
          lightOff();
      }
      //wait for the width of a single pulse.
      delay(1);
   }
}

And there you have it. PWM and pulse distribution. I only refactored this algorithm so i can be used in a tight loop, and the error and brightness parameters are taken from array so each light can have a separate brightness.

I recognise the work of others as mentioned before, and I know that this algorithm is used in other places. But I didn’t understand the inner workings at first, therefore i wanted to re-invent it myself as a study. Needless to say, the end result is surprisingly similar to G.Andrew Stones M5451 driver. As such, he deserves credit for using the concept.
Rob van der Veer
Notes & Corrections
  1. The frequency of Vision Persistence was not 30 Hz, but 100 Hz (thanks to Headroom for pointing that out)
  2. The principle explained here is Pulse Density Manipulation and is not really PWM (stimmer)
  3. As a reader pointed out, there’s no problem using PWM to dim a regular bulb – something i didn’t know.

Categorised in:

3 Comments

  • Hi Rob,

    thanks for the code and example! I now have nicely dimming LEDs from 100% down to 10% brightness (I have them at 500 Hz, so 10% brightness is a flicker at 50 Hz, which is barely noticeable).

  • Great post but the optimized code is unreadable – would you just post it as plan text? Thanks

    • I fixed it. Thanks for mentioning it. It looked good on my browser but not on my phone. Something must have gone wrong (years ago) when I imported the content.