DAY 02: Draw a straight line (DDA algorithm & Bresenham’s algorithm)

It is recommended to pay attention to the public account “Lu Egg Lab” or directly read the original blog, update more timely, better reading experience

---

Write article is not easy, entreat everybody audience master point praise 👍, collect 📁, comment 💬 three even support!! Thank you. It really means a lot to me!

---

On the first day, we set up the C++ operating environment and drew a point. According to the order of point → line → plane, today we will talk about how to draw a straight line.

This article mainly explains the derivation and thinking of line drawing algorithm (don’t worry, only involves a little middle school mathematics knowledge), and finally will give the code implementation, we rest assured to look down.

1.DDA straight line algorithm

1.1 Simple Implementation

Let’s go back to our middle school geometry, how do you represent a straight line in two dimensions? The most common is the slope-intercept form:

$y = kx + b$

Where the slope is KKK, and the intercept of the line on the yyy axis is BBB.

Slope-intercept form is mathematically fine, but in real engineering projects, because of limited hardware resources, we can’t and need not represent an infinite line, The reality is often to know the beginning (x1,y1)(x_1, y_1)(x1,y1) and the end (x2,y2(x_2, y_2(x2,y2) of a line segment, and then draw it.

X1 ≤x≤x2x_1 \leq x \leq x_2x1≤x≤x2, y1≤y≤y2y_1 \leq y \leq y_2y1≤y≤y2:

$\frac{x-x_{1}}{x_{2}-x_{1}}=\frac{y-y_{1}}{y_{2}-y_{1}}$

XXX and YYy can be expressed by using the parameter λ\lambdaλ :

$\left.\begin{array}{l}x=\lambda\left(x_{2}-x_{1}\right)+x_{1} \\ y=\lambda\left(y_{2}-y_{1}\right)+y_{1}\end{array}\right\} 0 \leq \lambda \leq 1$

In this case, we can find the corresponding x and y by taking different λ\lambdaλ.

In accordance with the above ideas, we can use code to implement. The C++ implementation is also simple, as follows (dl stands for dλd \lambdadλ) :

void line(
  int x1, int y1, 
  int x2, int y2, 
  TGAImage &image, TGAColor color) { 
    const float dl = 0.01;
    int dx = x2 - x1;
    int dy = y2 - y1;
    for (float t=0.0; t<1.0; t+=dl) { 
        int x = x1 + dx * t;
        int y = y1 + dy * t;
        image.set(x, y, color); }}Copy the code

This is a preliminary implementation of the line algorithm, can only say “work”, status and the sort algorithm in the “bubble sort”, the purpose achieved, but the performance is not very good:

• For every point I draw, I’m going to multiply twice
• Extensive use of floating point operations (as we all know, vfloatv_{float}vfloat < vfixedv_{fixed}vfixed < vintv_{int}vint)
• ifdlSmall, will result in a pixel will be drawn many times, double calculation
• ifdlIf I take it too big, it will break the line

1.2 optimization

Now let’s optimize the above algorithm step by step.

First of all, notice that the scene of drawing a straight line on the screen is theoretically continuous, but in practice discrete.

For example, when XXX changes from x1x_1x1 to x2x_2x2, XXX grows by step 1 each time it is drawn, that is, xnew=xold+1x_{new} = x_{old} + 1xnew=xold+1.

This time ynew = yold + y2 – y1x2 – x1 = yold + ky_ = y_ {new} {old} + \ frac {y_2 – y_1} {x_ {2} – x_ {1}} = y_ {old} + Kynew = yold + x2 – x1y2 – y1 = yold + k.

Let’s write the above formula in code, which looks like this:

void line(
  int x1, int y1, 
  int x2, int y2, 
  TGAImage &image, TGAColor color) { 
  float x = x1;
  float y = y1;
  float step = std::abs(x2 - x1);
  float dlx = (x2 - x1) / step;
  float dly = (y2 - y1) / step;
  
  for (int i=1; i<step; i++) { 
    image.set(x, y, color); x = x + dlx; y = y + dlx; }}Copy the code

The problem with this algorithm is that if you draw a line with a slope greater than 1, the line will break. For example, drawing from point (0, 0) to point (2, 4) will only draw two points according to the above algorithm, but what we expect is the picture on the right, at least each pixel should be connected:

The solution is also simple: when drawing this relatively “steep” line (the absolute value of the slope is greater than 1), base it on the change in y instead of x to avoid the discontinuity of the line above.

The final line algorithm looks like this:

void line(
  int x1, int y1, 
  int x2, int y2, 
  TGAImage &image, TGAColor color) { 
  float x = x1;
  float y = y1;
  int dx = x2 - x1;
  int dy = y2 - y1;
  float step;
  float dlx, dly;

  // Base on the length of dx and dy
  if (std::abs(dx) >= std::abs(dy)) {
    step = std::abs(dx);
  } else {
    step = std::abs(dy);
  }

  dlx = dx / step;
  dly = dy / step;

  for (int i=1; i<step; i++) {
    image.set(x, y, color); x = x + dlx; y = y + dly; }}Copy the code

Then we use this algorithm to test the line with different starting points and different slopes, and see that the effect works well:

This algorithm is the classic DDA (Digital Differential Analyzer) algorithm, which is much more efficient than our original code:

• Eliminate multiplication in the loop
• Repeated drawing operations are avoided
• Ensure that line segments are continuous and do not break

But it also has a performance-consuming problem: it involves a lot of floating point calculations.

As the algorithm at the bottom of the renderer, we definitely want it to be as fast as possible. Let’s look at Bresenham’s straight line algorithm, which eliminates floating point operations.

2.Bresenham’s straight line algorithm

2.1 Preliminary Implementation

This section will not start with a complete version of Bresenham’s algorithm, but we will start with a section and conclude with a complete algorithm.

To start, let’s consider a subset of all lines, those with slopes between [0,1][0, 1][0,1] : 0≤k≤10 \leq k \leq 10≤k≤1.

As we said in the previous section, the scenario of drawing a line on the screen is theoretically continuous, but in practice discrete. Assuming that a point (x, y)(x,\ y)(x, y) has been drawn, there are only two possibilities for the position of the next new point on the pixel screen:

• 
  $(x + 1,\ y)$
• 
  $(x + 1,\ y + 1)$

The question then becomes, where should the next new point be?

I think you all have a plan, and the general idea is as follows

• Xnew =x+1x_{new} =x+ 1xnew=x+1 into the equation of the line, and calculate the value of ynewy_{new}ynew
• Then compared
  $y_{new}$ 和
  $Y + 0.5$The size of the
  • Ynew y + 0.5 or less y_ {new} \ leq y ynew acuities were y + 0.5 + 0.5), click on (x + 1, y) (x + 1, \ y) (x + 1, y)
  • Ynew > y + 0.5 y_ {new} > y + 0.5 ynew > y + 0.5, click on (x + 1, y + 1) (x + 1, \ y + 1) (x + 1, y + 1)

Let’s refine our thinking and take into account the error in each choice:

Pictured above, in fact, drawn at the point (x, y) the (x, y) (x, y), theoretical point location is (x, y + ϵ) (x, y \ + \ epsilon) + ϵ (x, y).

When a point is moved from XXX to x+1x +1x +1, the theoretical position of the new point should be (x+1, y+ϵ+k)(x +1, \ y+ \epsilon +k)(x +1, y+ϵ+k), where k is the slope of the line.

To actually draw, compare y+ϵ+ky + \epsilon +ky +ϵ+k with y+0.5y +0.5y +0.5:

• Y + ϵ + k y, y + + 0.5 or less \ \ leq epsilon + k + 0.5 y y + ϵ + k y + 0.5 or less, click on (x + 1, y) (x + 1, \ y) (x + 1, y)
• Y > y + ϵ + k + y + \ epsilon + 0.5 k > > y y y + ϵ + + 0.5 k + 0.5, click on (x + 1, y + 1) (x + 1, \ y + 1) (x + 1, y + 1)

For the next new point x+2x +2x +2, we can update the error as ϵ\epsilonϵ :

• If (x+1, y)(x+1, \ y)(x+1, y), The ϵ new = (y + ϵ + k) – y = ϵ + k \ epsilon_ {new} = (y + \ epsilon + k) – y = \ epsilon + k ϵ new = (y + ϵ + k) – y = ϵ + k
• If (x+1, y+1)(x +1, \ y+1)(x +1, y+1), The ϵ new = (y + ϵ + k) – (y + 1) = ϵ + k – 1 \ epsilon_ {new} = (y + \ epsilon + k) – (y + 1) = \ epsilon ϵ + k – 1 new = (y + ϵ + k) – (y + 1) = ϵ + k – 1

Use pseudocode to represent the thought process above:

$\begin{aligned} & \epsilon \leftarrow 0, \quad y \leftarrow y_{1} \\ & \pmb{for} \ x \leftarrow x_{1} \ \pmb{to} \ x_{2} \ \pmb{do} \\ & \quad \pmb{draw} \ \pmb{point} \ \pmb{at} \ (x, \ y) \\ \ & \quad \ PMB {if} \ (\ (\epsilon + k) < 0.5) \\ & \quad \quad \epsilon \leftarrow \epsilon + k \\ &quad \pmb{else} \\ & \quad \quad y \leftarrow y + 1 \\ & \quad \quad \epsilon \leftarrow \epsilon + k – 1 \\ & \quad \pmb{end} \ \pmb{if} \\ & \pmb{end} \ \pmb{for} \end{aligned}$

2.2 Eliminate floating point arithmetic

Looking at the pseudocode above, we can see that 0.5 appears, which means floating point operations exist. Let’s eliminate floating point numbers with some equivalent mathematical transformations.

First, for the inequality ϵ+k<0.5\epsilon +k<0.5 ϵ+k<0.5, we multiply the left and right sides of the inequality by twice the Delta x\Delta x δ x, thus eliminating both the slope division and the floating-point operation caused by the constant 0.5:

$\epsilon + \Delta y / \Delta x < 0.5$

$2 \epsilon \Delta x + 2 \Delta y <\Delta x$

ϵ ‘\epsilon^{\prime}ϵ’ for ϵ δ x\epsilon\Delta xϵ δ x, Type can be converted into 2 (ϵ Δ ‘+ y) < Δ x2 (\ epsilon ^ {\ prime} + \ Delta y) < \ Delta x2 (ϵ Δ’ + y) < Δ x

Similarly, when we update ϵ\epsilonϵ, we also replace it with ϵ ‘\epsilon^{\prime}ϵ’ for the following two formulas:

• 
  $\epsilon = \epsilon + m$

• 
  $\epsilon = \epsilon + m – 1$

Multiply both sides of the equation by Delta x\Delta x Delta x

• 
  $\epsilon \Delta x = \epsilon \Delta x+\Delta y$

• 
  $\epsilon \Delta x = \epsilon \Delta x+\Delta y-\Delta x$

ϵ ‘\epsilon^{\prime}ϵ’ for ϵ δ x\epsilon\Delta xϵ δ x:

• 
  $\epsilon^{\prime} = \epsilon^{\prime}+\Delta y$

• 
  $\epsilon^{\prime} = \epsilon^{\prime}+\Delta y-\Delta x$

In this case, we get pseudocode that strips out floating point operations:

$\begin{aligned} & \epsilon^{\prime} \leftarrow 0, \quad y \leftarrow y_{1} \\ & \pmb{for} \ x \leftarrow x_{1} \ \pmb{to} \ x_{2} \ \pmb{do} \\ & \quad \pmb{draw} \ \pmb{point} \ \pmb{at} \ (x, \ y) \\ & \quad \pmb{if} \ ( \ 2 (\epsilon^{\prime} + \Delta y) < \Delta x) \\ & \quad \quad \epsilon^{\prime} \leftarrow \epsilon^{\prime} + \Delta y \\ & \quad \pmb{else} \\ & \quad \quad y \leftarrow y + 1 \\ & \quad \quad \epsilon^{\prime} \leftarrow \epsilon^{\prime} + \Delta y – \Delta x \\ & \quad \pmb{end} \ \pmb{if} \\ & \pmb{end} \ \pmb{for} \end{aligned}$

C++ implementation is as follows:

void line(Screen &s,
  int x1, int y1,
  int x2, int y2,
  TGAImage &image, TGAColor color) {
  int y = y1;
  int eps = 0;
  int dx = x2 - x1;
  int dy = y2 - y1;

  for (int x = x1; x <= x2; x++) {
    image.set(x, y, color);
    eps += dy;
    // Replace *2 with the bit operator <<1
    if((eps << 1) >= dx) { y++; eps -= dx; }}}Copy the code

In this way, we achieve an efficient algorithm whose slope is in the interval of [0,1][0, 1]. In other words, now we can draw lines in 1/8 quadrants. The rest of the range of lines can be drawn by swapping xy and so on. The implementation is a bit of dirty work, but if you are interested, you can go to GitHub to see the full implementation.

3. Draw the model

This part can be combined with the original English tutorial learning, I only do some details on the supplement.

The first two sections are all algorithm-based learning. This section starts by loading an African.obj model and then connecting the points on each triangular face of the model.

OBJ files are a widely used 3D model file format (OBJ is the suffix) to describe a 3D model. The key words of the model are more complicated, so this paper will not expand temporarily due to space limitation. You can search and learn by yourself.

The flow of this section is also clear: load the.obj file from disk → analyze the.obj file by line → build the model → loop through each triangle in the model → join the three sides of the triangle → render the graph

The first three steps of the appeal process have been wrapped by the original author. We can directly drag the source code model.h and model. CPP into the main project. Those who are interested can see the source code implementation. I’m going to skip it because it doesn’t have much to do with graphics.

The final code for drawing a triangle is as follows, and I have commented out the key steps:

// Instantiate the model
model = new Model("obj/african_head.obj");

// All triangles in the loop model
for (int i = 0; i < model->nfaces(a); i++) { std::vector<int> face = model->face(i);

  // Loop a triangle with three vertices
  for (int j = 0; j < 3; j++) {
    Vec3f v0 = model->vert(face[j]);
    Vec3f v1 = model->vert(face[(j + 1) % 3]);
    
    // Since the model space range is [-1, 1]^3, we need to shift the model coordinates to screen coordinates
    // Point + 1 * width(height) / 2
    int x0 = (v0.x + 1.) * width / 2.;
    int y0 = (v0.y + 1.) * height / 2.;
    int x1 = (v1.x + 1.) * width / 2.;
    int y1 = (v1.y + 1.) * height / 2.;
    
    Draw a line / /
    line(x0, y0, x1, y1, image, white); }}Copy the code

The final rendered image looks like this:

Today we learned how to draw a line, tomorrow we will learn how to draw a triangle.

---

If you are interested in graphics, you can visit “Lu Egg Lab” at 🛰️ and reply to “Graphics” to get classic textbooks “Tiger Book 4” and “Real Time Rendering 4”.

Write article is not easy, entreat everybody audience master point praise 👍, collect 📁, comment 💬 three even support!! Thank you. It really means a lot to me!

---

Reference connection:

Line Drawing on Raster Displays

The Bresenham Line-Drawing Algorithm

DDA Line Drawing Algorithm – Computer Graphics

Bresenham’s Line Drawing Algorithm

---