Draw Line (DDA algorithm)

It's turn out 'Draw a line' on screen is the 'Classic problem' in computer.😂.

Cuz in JavaScript canvas, we can just use:

ctx.lineTo()

Using this function, u can easily draw line on canvas. But it a way different without library call…

Our screen is render by pixel by pixel, imagine those pixels are super small and tiny grid:

And draw a line on screen actually means, we need to fill those grid! So the 'Classic problem' is how can we draw those grid effectively and make those lines look perfect!

So We have great genius to solve this problem before, that they invent a lot of method and mostly are the algorithm like:

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

In this section, we're going to use DDA, which is simpler. And yup DDA need to divded values, it take resources so it will slower. But it was not big deal in our case and our morden PC.

DDA concept actually is from the math for finding 'Slope' y = mx + c:

The keys are:

• the m which represent of 'Slope', if m value become bigger, that means the line will become more 'Slope'.
• the c which represent of intercept with y-axis, means the bigger value c, the line will become higer.

And let's us draw more graph to explain what means more m more slope.

It was really similar what we saw in Vector or rotate the Vector(sin/cos) in previous section.

the

• Δx, actually is x intercept and also is 'adjacent' in trigonometry.
• Δy, is y intercept and can represnet as 'opposite' in trigonometry.

So, we can say the m actually is the angle!Right? It make sense!

The bigger angle, the r(hypotenuse) will become more slope.

And m = Δy / Δx, which exactly is tan(a) = opposite / adjacent

And not done yet. Do you familiar with is pattern? m = y / x, not just tan not just trigonometry.

If we think about 'speed', how we get the 'speed'? - Position over Time!

It's actually same! Just without the 'c' (y-axis intercept) cuz it start from 0!.

So Position / Time, we want to know how fast when the object comparison with time.

Furthermore, m = Δy / Δx we want to know how 'slope/fast' y is when comparison with x.

DDA:

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;
  }
}

Main point is

• When Δx = longest_side_length, then Δx / Δx = 1, and Δy < 1
• Or when Δy = longest_side_length, then Δy / Δy = 1 and Δx < 1

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

Result

Resources: pikuma course