2.2 Scan Converting Lines

Cf. [FvDFH90, 3.2], [PK87, 3.3], and almond.srv.cs.cmu.edu/.../scanconv_2.pdf.

A line from point $(x_0,y_0)$ to point $(x_1,y_1)$ is mathematically given in explicit form by

$$y=k\,x+d$$, where the slope is $$k:=\frac{y_1-y_0}{x_1-x_0}$$ and $$d:=y_0-k\,x_0.$$

When we draw the line on the screen, we have to pick points with integer coordinates as close as possible to the line. If the slope satisfies $-1\leq k\leq 1$, then we should pick in any column with given integer value $x$ one point as close as possible to the corresponding point on the line. Its $y$-coordinate is given by $\bar y=\operatorname{ROUND}(k\,x+d)$. If the slope satisfies $\vert k\vert>1$ we may exchange $x$ and $y$, in order to reduce the problem to the particular case. This method by brute force is inefficient because of the multiplication and the function $\operatorname{ROUND}$.