Drawing lines

When you think about it, we transfer information in only one of two ways: drawing and/or speaking. Given that fact, it is very important for anyone interested in communicating to attain a good grasp on the fundamentals. For the purpose of this post, I’ll focus on drawing.

Pick up a pen or pencil and a clean sheet of paper and, without much effort, your hands will form shapes and symbols out of ink. The artistic quality of said shapes - I will not question, I’m more interested in the mechanics of translating ideas onto arbitrary surfaces, specifically any digital display. To do that, we first need to understand how they work.

Dots #

Under the hood of any modern display, exists an array of individual dots, each one capable of being switched on or off. While on, they display a combination of red, green and blue lights (with more than 16 million possible combinations).

For the purpose of simplicity, we can imitate a similar setup by printing an array of individual characters inside the terminal app and colouring dots: bright red if “on”, dim gray if “off”.

To maintain consistent state between drawing strokes, we will store information for each “dot” inside a two-dimensional array of integers. And for the initial state (blank) we set each element of that array to 0 to represent off.

int dots[height][width];

Points #

So this will be the display, but how do we draw on it? We can start by drawing a point, the most primitive of geometric notions. As is expected, not a difficult task, we just pick a coordinate (x, y) and go inside our dots array to set that element to 1 to turn it on.

dots[20][20] = 1; // Turn on the element on 20th row, 20th column

Lines #

Next up - lines, they should be easy, right? You take two points and connect them with an infinite amount of points in between. This is easy to do by hand, you just instinctively know how to travel from point a to point b with your pen. This is much harder on a screen, because we have to turn on every distinct point one by one in between the starting ones.

There may be better techniques to do this, but the one I’m using right now is to calculate the slope and iterate over each point on the x-axis while generating y-axis coordinates. This is a regular linear (no surprise…) function at work. The problem is that linear functions map Real values to Real values, and we only have a finite number of elements in our dots array. As a result, we have to approximate, which ones to turn on.

int     xDelta = to.x - from.x, 
        yDelta = to.y - from.y,
        i;
float   slope = (float)yDelta/(float)xDelta;

for (i = from.x; i < to.x; i++) {
    dots[(int)roundf(slope * i)][i] = 1;
}

And if we try to draw a line going from point (0,0) to point (20,20), here’s what we get.

Now that the basic constructs are in place, we can further develop our drawing capabilities by combining them, I.e. to get a triangle, you need three lines arranged in a pattern, similarly for a rectangle, etc. This is a good exercise when trying to understand the underlying problem of computer graphics - the necessity to transfer continuous notions into discreet chunks of data.