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)