Another look at Bresenham (3)

Let's get rid of float operations

the following decision parameter has the same sign as d1 - d2 :

(4) Pk = DX ( d1 - d2) = 2 DY . xk - 2 DX . yk + c = DX( 2 m (xk + 1) - 2 yk + 2b -1)
with c = constante = 2 DY + DX (2b -1)

Let's get rid of multiplications

Pk+1 = 2 DY . xk+1 - 2 DX .yk+1 + c

Pk+1 - Pk = 2 DY (xk+1 - xk) - 2 DX (yk+1 - yk) (get rid of the constance)

Pk+1 = Pk + 2 DY - 2 DX (yk+1 - yk)

Pk+1 = Pk + D'Y     or     = Pk + D'Y - D'X

with (yk+1 - yk) = 0 or 1 depending on Pk sign
(Pk < 0 <=> 0)        and    D'Y = 2 DY   and    D'X = 2 DX 

P0 = 2DY - DX     (   = 2 DY . x0 - 2 DX . y0 + 2 DY + DX (2b -1)  )

(in our implemented algo, 'fraction' is the decision parameter Pk)

eScience