chapters/Background_Lines.tex

   1 It is well known that in cartesian coordinates, a line between points $(x_1, y_1)$ and $(x_2, y_2)$, can be described by:
   2 \begin{align}
   3         y(x) &= m x + b\label{eqn_line} \quad \text{ on $x \in [x_1, x_2]$}  \\
   4         \text{ for } & m = (y_2 - y_1)/(x_2 - x_1) \\
   5         \text{ and } & b
   6 \end{align}
   7
   8 On a raster display, only points $(x,y)$ with integer coordinates can be displayed; however $m$ will generally not be an integer. Thus a straight forward use of Equation \ref{eqn_line} will require costly floating point operations and rounding (See Section\ref{}). Modifications based on computing steps $\delta x$ and $\delta y$ eliminate the multiplication but are still less than ideal in terms of performance\cite{computergraphics2}.
   9
  10 Bresenham's Line Algorithm was developed in 1965 with the motivation of controlling a particular mechanical plotter in use at the time\cite{bresenham1965algorithm}. The plotter's motion was confined to move between discrete positions on a grid one cell at a time, horizontally, vertically or diagonally. As a result, the algorithm presented by Bresenham requires only integer addition and subtraction, and it is easily adopted for drawing pixels on a raster display. Bresenham himself points out that rasterisation processes have existed since long before the first computer displays\cite{bresenham1996pixel}.
  11
  12 In Figure \ref{rasterising-line} a) and b) we illustrate the rasterisation of a line width a single pixel width. The path followed by Bresenham's algorithm is shown. It can be seen that the pixels which are more than half filled by the line are set by the algorithm. This causes a jagged effect called aliasing which is particularly noticable on low resolution displays. From a signal processing point of view this can be understood as due to the sampling of a continuous signal on a discrete grid\cite{citationneeded}. \rephrase{I studied this sort of thing in Physics, once upon a time... if you just say "Nyquist Sampling" and wave your hands people usually buy it.}
  13
  14 Figure \ref{rasterising-line} c) shows an (idealised) antialiased rendering of the line. The pixel intensity has been set to the average of the line and background colours over that pixel. Such an ideal implementation would be impractically computationally expensive on real devices\cite{elias2000graphics}. In 1991 Wu introduced an algorithm for drawing antialiased lines which, while equivelant in results to existing algorithms by Fujimoto and Iwata, set the state of the art in performance\cite{wu1991anefficient}.
  15
  16 \rephrase{NOTE: Should I actually discuss how the algorithms work? Or just ``review'' the literature? Bearing in mind that how they actually work doesn't really relate to infinite precision document formats...}
  17
  18 \begin{figure}[H]
  19         \centering
  20         \includegraphics[width=0.25\textwidth]{figures/line1.pdf}
  21         \includegraphics[width=0.25\textwidth]{figures/line2.pdf}
  22         \includegraphics[width=0.25\textwidth]{figures/line3.pdf}
  23         \caption{Rasterising a Straight Line}\label{rasterising-line}
  24         a) Before Rasterisation b) Bresenham's Algorithm c) Antialiased Line (Idealised)
  25 \end{figure} % As much as I hate to break up the party, these fit best over the page (at the moment)
  26