Can't understand "recursive definition of decision parameter" in Bresenham's line algorithm.

Question

Hello math-syths. I'm studying graphics programming, but my math background is harshly vague, so please use a little patience!

I'm reading about the derivation of Bresenham's line drawing algorithm (Saloni Baweja), and it seems to be pretty clear. The only thing that I can't understand seems to be the simplest part of the entire derivation.

I know I'm lacking some skills here, but knowing that: $c=2{\Delta}y+2{\Delta}xb-{\Delta}x$

How's does exactly: $p_{i+1} - p_i =2{\Delta}yx_{i+1}-2{\Delta}xy_{i+1}+c-(2{\Delta}yx_{i}-2{\Delta}xy_{i}+c)$

Ends up being: $2{\Delta}y(x_{i+1}-x_i)-2{\Delta}x(y_{i+1}-y_i) $?

TIA and sorry for such a mundane question.

Answer 1

$$p_{i+1} - p_i =2{\Delta}yx_{i+1}-2{\Delta}xy_{i+1}+c-(2{\Delta}yx_{i}-2{\Delta}xy_{i}+c)$$

Expand: $$=2{\Delta}yx_{i+1}-2{\Delta}xy_{i+1}+c-2{\Delta}yx_{i}+2{\Delta}xy_{i}-c$$

Reorder: $$=2{\Delta}yx_{i+1}-2{\Delta}yx_{i}+2{\Delta}xy_{i}-2{\Delta}xy_{i+1}+c-c$$

Remove $c-c=0$ and add parens:

$$=(2{\Delta}yx_{i+1}-2{\Delta}yx_{i})+(2{\Delta}xy_{i}-2{\Delta}xy_{i+1})$$

Factor out $2{\Delta}y$ and $2{\Delta}x$:

$$=2{\Delta}y(x_{i+1}-x_{i})+2{\Delta}x(y_{i}-y_{i+1})$$

Change sign of the second term:

$$=2{\Delta}y(x_{i+1}-x_{i})-2{\Delta}x(y_{i+1}-y_i)$$

---

Regarding the algorithm, I never remember exactly the formula but here is how to find it again:

• Assume the slope is in $\mathopen]0,1\mathclose[$ (otherwise change the problem, for instance by permuting $x$ and $y$).
• Then $x_i$ must increase by $1$ at each step, and $y_i$ increases by $\delta_i$, which is $0$ or $1$.
• The equation of the line is $(x_B-x_A)(y_i-y_A)-(y_B-y_A)(x_i-x_A)=0$. Keep track of the error $e_i=(x_B-x_A)(y_i-y_A)-(y_B-y_A)(x_i-x_A)$, and choose $\delta_i$ so as to minimize $|e_i|$. To compute only with whole integers, you must actually keep track of $2e_i$.

That's all there is to it.