What is the Bresenham algorithm?




Professor Jack Bresenham defined this mathmatical algorithm in 1962 and it was published in the IBM Systems Journal of 1965.
The original algorithm was designed for the line plotters of the time, and subsequently is often used in screen line plotting, and in scanners. Originally the algorithm only covered the drawing of straight lines, he later incorporated the drawing of circles into it.
In a nutshell the algorithm determines where two dimensional points should be plotted in order to draw a straight line between two named points.
A computer screens output is in pixels, and from a mathmatical viewpoint present difficulty in drawing straight lines. The Bresenham midpoint algorithm solves this problem as well as gaining that most important commodity to today's game programmers of speed.
For plotting, the algorithm works by moving in finite steps, with each step being marginally longer or shorter than the other, over a certain distance the distance moved will have smoothed itself out. So if each pixel square is 6 pixels and your plot needs to move 5.356 pixel squares then your screen line would sometimes move 5 squares and sometimes 6 squares, over time the algorithm will pick the correct combination of of 5 and 6 squares to actually travel the 5.356 squares required.
The RTC clock here uses the Bresenham idea and was adapted for this purpose by
Roman Black and Bob Ammerman, and published on the Piclist.
It works by implementing a fast subtract by 24 function and works as follows -
We want to count seconds, therefore with an internal clock frequency of 1MHz, the processor counts 1,000,000 times a second which is 1uS.
With one microsecond one million counts are required to reach 1 second. So we need to load our software registers with 1 million.
However, there is a snag as an 8 bit counter only counts to 256 and rolls over to zero. To get around this, one is added initially to the middle byte of the 24 bit counter which is the same as adding 256.
                                              0000 1111 | 0100 0010 | 0100 000 + 1 0000 0000 is the same as adding 1 to the middle byte 0100 0010.
This takes care of timer2's eight bit count.
All that needs to be done now is to check when the midbyte reaches zero
So initially the RTC registers are set up as
                                    tickhigh = H'0F 
                                                                        tickmid  = H'42 +1 
                                                                        ticklow  = H'40


Now when timer2 has reached 256, we need to subtract 256 from the midbyte, this is what ensures the RTC seconds are accurate and will always be in sync with the Pic's internal clock, making this more accurate than using a 32.678KHz crystal which is subject to tolerances and heat variance.
So first we check whether the middle byte tickmid has decreased to zero, if it has, then we decrease the high byte tickhigh, if not then all we need to do is decrease tickmid by one and no more needs to be done.
                                                                       movf tickmid,F
                                                                       btfsc STATUS,Z
                                                                       decf tickhigh,F
                                                                       decfsz tickmid,F
Note the fast 24 bit subtraction has just happened by decreasing the middle byte by one.
                                    decfsz tickmid,F


If tickmid has reached zero then 1 second may have been reached.
Remember for tickmid to reach zero, 256 counts must have passed.
One second will only have been reached when both tickmid and tickhigh are zero at the same time. So now the high byte needs to be checked
                                                                      movf tickhigh,F 
                                                                      btfss STATUS,Z
If the high byte isn't zero, then there is no more to be done and the program can carry on doing other things for another 256 counts.
When both the middle byte and the high byte have reached zero then we know that one second has passed (or as in this case 1 million counts) and we need to restart all over again, except this time there is no need to add an extra 256 counts to the middle byte, because now we are in sync.
So the software counters are reloaded and the only adjustment that needs to happen is to the low byte counter, as whilst all this checking has been going on, timer2 will have advanced a number of counts, so these need to be added to the initial count.
                                                                      tickhigh = COUNTH
                                                                      tickmid = COUNTM
                                                                      ticklow = ticklow + COUNTL 
One second has passed and the counters have been reloaded, there is just one last thing that needs to be checked, has adding the initial low byte count caused the low byte to overflow to 256? If not, no problem and the seconds count is increased by one, if however this did cause the low byte to overflow, then the middle byte needs to be increased by one or if you prefer 256, and then the seconds counter can be incremented.
                                                                       btfsc STATUS,C
                                                                       tickmid+=1 
                                                                       sec+= 1
The complete section of code:
                                                                      movf tickmid,F
                                                                      btfsc STATUS,Z
                                                                      decf tickhigh,F
                                                                      decfsz tickmid,F
                                                                      goto end of interrupt
                                                                      movf tickhigh,F 
                                                                      btfss STATUS,Z
                                                                      goto end of interrupt
                                                                      tickhigh = COUNTH
                                                                      tickmid = COUNTM
                                                                      ticklow = ticklow + COUNTL
                                                                      btfsc STATUS,C
                                                                      tickmid+=1 
                                                                      sec+= 1
This routine can be amended slightly to generate a frequency as in producing a baud rate.
The difference is the way in which the initial counter values are created.
So if you need to produce a 9600 baud frequency, the maths are as follows.
Clock Frequency = Crystal frequency / 4
counter values = Clock Frequency / frequency rate
1MHz = 4MHz / 4
counter values = 1MHz / 9600 = 104.166 = H' 00 00 68
20 Mhz /4 = 5MHz / 9600 = 520.833 = H' 00 02 08
Note that although the frequency will be spot on, there will be jitter as each count will not be exactly the same each time around, but over a period of time will be exact. This code would not be suitable for high speed communications because of this.
Home