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

$\displaystyle y=k\,x+d$, where the slope is $\displaystyle k:=\frac{y_1-y_0}{x_1-x_0}$ and $\displaystyle 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}$.



Subsections
Andreas Kriegl 2003-07-23