>>
Show me a version of Bresenham line algorithm where there is only one
addition per step.
As I see it, there is at least one addition and two subtractions.
We accumulate the error, that is one addition.
We shift left the error one for multiply by two.
We compare error with deltax which requires a subtraction at minimum.
That is one subtraction.
Based on the comparision, we may subtract deltax from the error and
increment the y axis.  That is two subtractions.
<<

Bresenham's algorithm works on 3 numbers.  I'll call them E, DEA, and DEB.
Once the setup is over, the algorithm goes like this:

loop:
  if E >= 0
    then
      <take a B step>
      E <-- E + DEB
    else
      <take an A step>
      E <-- E + DEA
    endif
  goto loop;

The IF merely requires checking the sign bit of E, so I don't consider that
an "operation".  You do have to add either DEA or DEB into E each step.
That's the add operation I was talking about.  The A step and B step
operations are up to you, but an A step is usually advancing by 1 in the
minor axis, and a B step is leaving the minor axis value alone.  What you do
with the major axis is also up to you, but you would usually advance it by
1.  You also will need to terminate the loop.  Since the number of
iterations can be determined ahead of time, this is usually just
decrementing a counter until it reaches zero.

So there is only one real math "operation" required, but I should have
mentioned the additional 2 or 3 increment/decrement operations per
iteration.

I don't know where you came up with the parts about shifting the error left
one bit and comparing it to deltax.  I think you may be confusing the setup
with the running operation.  There is lots of literature on this.  You may
even be able to find Jack Bresenham's original paper in the IBM journal.


********************************************************************
Olin Lathrop, embedded systems consultant in Littleton Massachusetts
(978) 742-9014, olin@embedinc.com, http://www.embedinc.com

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics