Skip to content

05. Line Drawing Techniques

Dated: 14-04-2025

Line

A line, or straight line, is, roughly speaking, an (infinitely) thin, (infinitely) long, straight geometrical object, i.e. a curve that is long and straight.

Colinear Points

Three or more points that lie on the same line are called collinear.

Techniques to Draw a line

Incremental line Algorithm

We will exploit

\[y = mx + b\]

where

\[m = \frac{dy}{dx}\]
\[b = y - mx\]

Algorithm

def Incremental_Line (Point p1, Point p2):
    dx = p2.x – p1.x
    dy = p2.y – p1.y
    m = dy / dx
    x = p1.x
    y = p1.y
    b = y – m * x

    if len(m) < 1:
        for counter in range(p1.x, p2.x):
            drawPixel (x, y)
            x = x + 1
            y = m * x + b
    else
        for counter in range(p1.y, p2.y):
            drawPixel (x, y)
            y = y + 1
            x = (y - b) / m
Why is it that we have two cases, i.e. \(|m| < 1\) and \(|m| > 1\), why not just increment either \(x\) or \(y\) and then find out the other one.
  • \(|m| < 1\) implies that for each increment in \(x\), the increment in \(y\) is \(< 1\), taking us into subpixel. If we were to use \(y\) for increment in this case, it would miss out some discrete values of \(x\), hence creating gaps.
  • Vise versa for \(|m| > 1\).

Digital Differential Analyzer (DDA) line Algorithm

if len(dx) > len(dy):
    steps = len(dx)
else
    steps = len(dy)

Here, step is the total number of pixels.1

xIncrement = dx / steps
yIncrement = dy / steps

Then 

for counter in range(1, steps):
    drawPixel(x1, y1)
    x1 = x1 + xIncrement
    y1 = y1 + yIncrement

Bresenham's line Algorithm

Assume a line with slope2 \(m < 1\), then if the current point is \((x_i, y_i)\) then the next point can be either of the following

  • \((x_i + 1, y_i)\)
  • \((x_i + 1, y_i + 1)\)

The actual position on the line is \((x_i + 1, m(x_i + 1) + c)\).
Now taking distance of this true point from the top and bottom of the pixel respectively (\(d_2\) and \(d_1\)) gives us

\[d_1 = y - y_i = m \times (x_i + 1) + b - y_i\]
\[d_2 = y_i + 1 - y = y_i + 1 - m(x_i + 1) - b\]

Let's define a decision function3 \(p\) as

\[p_i = dx (d_1 - d_2)\]
\[\therefore d_1 > d_2 \implies p_i > 0\]

Plugging in the values of \(d_1\) and \(d_2\) while also knowing that \(m = \frac {dy}{dx}\), we get

\[p_i = 2dy(x_i + 1) - 2dx y_i + dx(2b - 1)\]

Abstracting away a section of this equation into \(k=2 dy + dx (2b-1)\), we get

\[p_i = 2dyx_i - 2dxy_i + k\]

Now we calculate \(p_{i + 1}\)

\[p_{i+1} = 2\,dy\,x_{i+1} - 2\,dx\,y_{i+1} + k\]
\[\because x_{i + 1} = x_i + 1\]
\[p_{i+1} = 2\,dy\,(x_i + 1) - 2\,dx\,y_{i+1} + k\]
\[p_{i+1} = 2\,dy\,x_i + 2\,dy - 2\,dx\,y_{i+1} + k\]

Now evaluating

\[p_{i + 1} - p_i\]

we get

\[p_{i+1} = p_i + 2\,dy - 2\,dx\,(y_{i+1} - y_i)\]

So now

\[d_1 > d_2 \implies p_{i + 1} = p_i + 2dy - 2dx\]
\[d_1 < d_2 \implies p_{i + 1} = p_i + 2dy\]

Also, plugging in \(b = y - mx\) into \(p_i\), a lot of terms cancel out and we are remained with

\[p_i = 2dy - dx\]

Algorithm

dx = x2 - x1
dy = y2 - y1
p = 2 dy - dx
c1 = 2 dy
c2 = 2 (dy - dx)
x = x1
y = y1

plot(x, y, color)

while (x < x2):
    x++;

    if (p < 0):
        p = p + c1
    else
        p = p + c2

    y++

    plot(x, y, color)

Improving Performance

We can improve the applications by

  • Replacing function3 calls with macros or inline code.
  • Unrolling the loops

We can calculate the next frame buffer4 by calculating the first one and then replacing x++ with address++ and y++ with address = address + XResolution.

Improved Versions of Bresenham's Algorithm

  • Symmetry (forward and backward simultaneously)
  • Segmentation (divide into smaller identical segments - GCD(Dx, Dy) )
  • Double step, triple step, n step

Settings a Pixel

Initial task: load the frame buffer4 or bitmap4
Assume the simplest case: 8-bit, non-interlaced graphics system.
Then each byte in the frame buffer4 corresponds to a pixel1 position.

\[\text{addr}(X, Y) = \text{addr}(0, 0) + Y \times (X_m + 1) + X(\text{all in bytes})\]
  • \(\text{addr}(X, Y)\) - The address of the pixel1 at \((X, Y)\) coordinates.
  • \(\text{addr}(0, 0)\) - The address of the initial pixel.1
  • \((X_m + 1)\) - Number of pixels1 per raster line(row).

References

  1. Read more about pixels. ↩↩↩↩↩

  2. Read more about slopes. ↩

  3. Read more about functions. ↩↩

  4. Read more about frame buffers. ↩↩↩↩