Draw Line (DDA Algorithm)

Instead of using library api call drawLine() why don’t we write a drawLine()

ctx.lineTo()

Like JavaScript on browser, we can call lintTo to draw a line on screen easily.

But it just all too convenient that we forgot what exactly draw line is. It was a ‘Classic problem’ in computer.

Now, we can think about our mointor display is a thousand of thousand tiny squares combine together. Those macro tiny square box we usually call pixel.

When we disaply something on screen, actually we’re filling those tiny boxes.

So in fundamental way to said, if we draw a line on screen, actually is filling some squares to make it like a line.

What make this become a classic problem is how we can fill those grid in effective ways?

Today, we have great genius to solve this problems, there are some famous algorithm:

• DDA (Digital Differential Analyzer)
• Bresenham’s line algorithm
• Xiaolin Wu’s line algorithm

We wil talk about the DDA first, because it is most simple idea and just need basic math conectp which is slope:

Recap some concept:

• the m represent to ‘Slope’, if m value become bigger, the means the line will become more slope
• the c which is ‘intercept’ with y-axis. If bigger value of c, the line will become higer.

Let’s us draw a line and analyze it.

Do you see that, when we mark Δx and Δy, which make it like a right trangle. So let us go into trigonometry mode to make it more details.

Δx:

• is x intercept, instead of y saying how higher, we x intercept talking about go to left a bit or right a bit.
• in trigonometry it is ‘adjacent’.

Δy:

• is y intercept.
• in trigonometry it is ‘opposite’.

Notice that now we have adjacent & opposite, what is the formula to get the ‘Hypotenuse’?

Pipe out x and y:

$$ \tan(\alpha) = \frac{\Delta y}{\Delta x} $$

Now , lets go back to the slope formula: $$ y = mx+c $$

Do you see there some similar? Lets do some simple algebra, assume the c = 0 means we start the line from (0,0) and move the m to left:

$$ m = \frac{y}{x} $$

Hey, do you see that, is just exactly same as the above formula. So that means the m actually is tan(a) which is a ratio. A ratio to talk about adjacent and opposite relationship.

Think about in this case:

This graph is talking about some object speed. The formula is:

$$ Speed = \frac{Position}{Time} $$

Look similar? Notice that how all the knowledge connect together.

Now the graph show that the Position(Δy) and the Time(Δx) relationship. What is the object speed or how fast the position is compare with time.

If we go back to:

$$ m = \frac{Δy}{Δx} $$

Now we know the formula mean how the slope is when y comparison with x.Or flip it: how slop is it when the x compare to y. Cus we have y intercept also have x intercept.

So in DDA, we need to know which side is longest:

void draw_line(int x0, int y0, int x1, int y1, uint32_t color) {
  int delta_x = (x1 - x0);
  int delta_y = (y1 - y0);
  int longest_side_length = (abs(delta_x) >= abs(delta_y)) ? abs(delta_x) : abs(delta_y);
}

If x longer, we will find y/x, how the slope y need to draw when compare with x. So When Δx = longest_side_length, then Δx / Δx = 1, and Δy < 1.

If y longer, we will find x/y, how the slope x need to draw when compare with y. So Δy = longest_side_length, then Δy / Δy = 1 and Δx < 1

void draw_line(int x0, int y0, int x1, int y1, uint32_t color) {
  int delta_x = (x1 - x0);
  int delta_y = (y1 - y0);

  int longest_side_length = (abs(delta_x) >= abs(delta_y)) ? abs(delta_x) : abs(delta_y);

  float x_inc = delta_x / (float)longest_side_length;
  float y_inc = delta_y / (float)longest_side_length;

Then we can draw line base on those ratio value.

void draw_line(int x0, int y0, int x1, int y1, uint32_t color) {
  int delta_x = (x1 - x0);
  int delta_y = (y1 - y0);

  int longest_side_length = (abs(delta_x) >= abs(delta_y)) ? abs(delta_x) : abs(delta_y);

  float x_inc = delta_x / (float)longest_side_length;
  float y_inc = delta_y / (float)longest_side_length;

  float current_x = x0;
  float current_y = y0;
  for (int i = 0; i <= longest_side_length; i++) {
    draw_pixel(round(current_x), round(current_y), color);
    current_x += x_inc;
    current_y += y_inc;
  }
}

It basiclly say, when x is longest length, mean we will draw 1 square x side and draw y < 1 length each loop. When y is longest length, we draw y as 1 square y side and draw x < 1 length.