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 + c\label{eqn_line} \quad \text{ on $x \in [x_1, x_2]$}
   4         \text{ for } m = \frac{(y_2 - y_1)}{(x_2 - x_1)}
   5         \text{ and } c = y_1 - m x_1
   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{Precision and Rounding}). 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 It should be noted that algorithms for drawing lines can be based upon sampling $y(x)$ only if $|m| \leq 1$; otherwise sampling at every integer $x$ coordinate would leave gaps in the line because $\Delta y > 1$. Line drawing algorithms can be trivially adopted to sample $x(y)$ if $|m| > 1$.
  11
  12 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}.
  13
  14 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{wu1991anefficient}.
  15
  16 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 approximately antialiased lines which, while equivelant in results to existing algorithms by Fujimoto and Iwata, set the state of the art in performance\cite{wu1991anefficient}\footnote{Techniques for antialiasing primitives other than straight lines are discussed in some detail in Chapter 4 of ``Computer Graphics'' \cite{computergraphics2}}.
  17 .
  18
  19
  20
  21 \begin{figure}[H]
  22         \centering
  23         \includegraphics[width=0.25\textwidth]{figures/line1.pdf}
  24         \includegraphics[width=0.25\textwidth]{figures/line2.pdf}
  25         \includegraphics[width=0.25\textwidth]{figures/line3.pdf}
  26         \caption{Rasterising a Straight Line}\label{rasterising-line}
  27         a) Before Rasterisation b) Bresenham's Algorithm c) Anti-aliased Line (Idealised)
  28 \end{figure}