Is WebGL straight?

Preface 📒

As the question says, “Is the line straight?” When thinking about this question, let’s go back to the previous article and think about what the straight lines consist of: pixels, lines and triangles in WebGL, although all three are defined as the most basic graphics, they are also inextricably related to each other, as the song in “Wine Is Dry and Nothing Is Sold” says: “No line” 😉 a straight line is a graph made up of many pixels.

We know that pixels are actually square, so if the displayed line is horizontal or perpendicular to the horizontal direction, then the pixels must be arranged along or perpendicular to the horizontal direction, then the line must be straight. In tetris distance, the line should correspond to this figure in Tetris:

But most of the time lines are not strictly horizontal or vertical, so in this case we see lines that look more like permutations of these shapes:

So how are these pixels arranged? This leads to our topic today – scan conversion algorithm of line segment 👏

Scan conversion algorithm of straight line segment 📈

In the WebGL workflow, we mentioned a process called rasterization. The process of determining the set of pixels that best approximate the graph and writing the pixels with specified attributes is called rasterization or scan transformation of the graph.

Understand yet? Yet? In plain English, it is the process of converting an image into pixels.

This paper mainly introduces three kinds of linear rasterization algorithms: numerical differentiation method, midpoint line drawing method and Bresenham algorithm.

Numerical differentiation

Numerical differentiation method (DDA) is also called discrete interpolation analysis method (numerical analysis method).

You know you can represent a line in coordinates y=kx+by =kx+by =kx+b, so when we know that we want to plot the endpoints of the line P0(x0,y0), P1(x1,y1)P_0(x_0, y_0), P_1(x_1, y_1)P0(x0,y0), After P1(x1,y1), the expression of its line can be obtained by two-point formula: Y – y0y1 – y0 = x – x0x1 – x0 \ frac {y – y_0} {y_1 – y_0} = \ frac {x – x_0} {x_1 – x_0} y1 – y0y – y0 = x1 – x0x – x0, thereby to convert y = kx + by + by = = kx kx in the form of a + b. X, yx, yx, y are the coordinates of points on the screen respectively, assuming that XXX starts from P0P_0P0 and moves 1 pixel each time to endpoint P1P_1P1, then the next point we require yi+1y_{I +1}yi+1:

So we’ve reduced the algorithm for finding points to an addition. At the same time, for the screen, there is no decimal for the coordinate value of pixels, so it is necessary to round the yyY value obtained. The code is as follows:

// vertex shader
attribute vec4 a_Position;
void main() {
  // Set the dot size to 10px to make it more obvious
  gl_PointSize = 10.0;
  gl_Position = a_Position;
}
// fragment shader
void main() {
  gl_FragColor = vec4(1.0.1.0.0.0.1.0);
}
Copy the code

let current = 0; // Current vertex index
let handle = -1;
let a_Position;
const POINTS = []; // The array of vertices to draw
const P0 = [-300, -200]; // Start endpoint
const P1 = [500.200]; // Terminates the endpoint
const k = (P1[1] - P0[1]) / (P1[0] - P0[0]); / / the slope

/ / the main function
// It is basically the same as the previous basic article
function main() {
  const canvas = document.querySelector('#canvas');
  const gl = canvas.getContext('webgl');

  initShaders(gl, VS, FS);

  a_Position = gl.getAttribLocation(gl.program, 'a_Position');

  gl.clearColor(0.0.0.0.0.0.1.0);
  gl.clear(gl.COLOR_BUFFER_BIT);

  animation(gl);
}

function animation(gl) {
  if (current === P1[0] - P0[0]) { / / out of animation
    cancelAnimationFrame(handle);
    return;
  }
  DDA(gl);
  handle = requestAnimationFrame(() = > animation(gl));
}

/ / DDA algorithm
function DDA(gl) {
  // Store the next point to be drawn in the vertex array, and convert px to webGL's [-1.0, 1.0]
  POINTS.push([
    (current+P0[0) /1200.// x
    (Math.round(current*k+P0[1) /])800.// y
  ]);
  current++;

  gl.clear(gl.COLOR_BUFFER_BIT);

  // loop drawing
  for(let i = 0; i < current; i++) {
    gl.vertexAttrib3f(a_Position, POINTS[i][0], POINTS[i][1].0.0);
    gl.drawArrays(gl.POINTS, 0.1); }}Copy the code

The effect is as follows:

Note, the algorithm applies only to ∣ k ∣ | | k \ leq 1 or less ∣ k ∣ 1 or less, when k > 1 k > 1 k > 1, need to x, yx, yx, y interchangeably, namely the increase of yyy 1, XXX corresponding increase 1 k \ frac {1} {k} k1.

Dotted line method

If the current drawing point is (xi,yi)(x_i, y_i)(xi,yi), then we actually have two choices when drawing the next point: P0 (xi + 1, yi) P_0 (x_i + 1, y_i) P0 (xi + 1, yi) and P1 (, yi xi + 1 + 1) P_1 (y_i x_i + 1, + 1) P1 (, yi xi + 1 + 1). If M=(xi+1,yi+0.5)M=(x_i+1,y_i+0.5)M=(xi+1,yi+0.5) M=(xi+1,yi+0.5) is the midpoint of P0, P1P_0, P_1P0, P1, QQQ is the intersection of ideal line and line x=xi+1x=x_i +1x= xi+1. When MMM is below QQQ, P1P_1P1 should be the next pixel; Otherwise, P0P_0P0 should be the next pixel. This is how the dotted line method works, as shown below:

After standardizing the equation of the line, we can get: F(x,y)=ax+by+cF(x,y)=ax+by+cF(x,y)=ax+by+c, In which a = y0 – y1, b = x1 – x0, c = x0y1 – x1y0a = y_0 – y_1, b = x_1 – x_0, c = x_0y_1 – x_1y_0a = y0 – y1, b = x1 – x0, c = x0y1 – x1y0, at the same time, point and line has the following relationship:

Therefore, just substitute point MMM into F(x,y)F(x,y)F(x,y) to determine the relationship between the midpoint MMM and the line. Subsequent drawings are no different.

Bresenham algorithm

This algorithm is similar to the midpoint line method, except that an error term DDD is defined in this algorithm. DDD is not a fixed value, but changes with the change of vertices. The initial value of the error term is 0, and every time XXX subscript increases by 1, DDD value increases the slope value of the line KKK, that is, d=d+kd=d+kd=d+ K. The relation between the position of the vertex to be drawn and the error term DDD is as follows:

• D ≥0.5d \ GEQ 0.5d≥0.5 Lines and xi + 1 xi + 1 + 1 x_i intersection point is the most close to the current pixel (xi, yi) (x_i y_i) (xi, yi) in the top right pixels (, yi xi + 1 + 1) (y_i x_i + 1, + 1) (, yi xi + 1 + 1);
• When d< 0.5D < 0.5D <0.5, the intersection point is closer to the pixel (xi+1,yi)(x_i+1, y_i)(xi+1,yi) to the right of the current pixel;

Note that if the next point to be drawn is the upper right pixel, DDD is reduced by 1 because we have selected the new YYY-oriented reference point.

Conclusion 🎬

Summarize the principles of three straight line segment scanning algorithms:

1. Numerical differentiation method: use y=kx+by=kx+by=kx+b, find yyy, and round to get the next pixel to draw;
2. Midpoint line drawing method: if the midpoint is above the intersection of the ideal line and x=xi+1x= X_I +1x=xi+1, the right pixel is drawn; otherwise, the upper right pixel is drawn.
3. Bresenham algorithm: if the error term D ≥0.5d \ GE 0.5d≥0.5, draw the upper right pixel, otherwise draw the right pixel.

This is how a computer draws a straight line, simple, does it match what you expect? Looking back at the opening question, “Is a straight line straight?” maybe you have the answer yourself! 🤫

You can see that the lines in the image above are jagged. This is because pixel approximation errors distort the image, a phenomenon called aliasing. Of course, there are also technical methods to solve this problem, and these technologies are called anti-aliasing, such as the most violent method is to improve the resolution, as well as regional sampling, weighted regional sampling and other ways. Interested partners can learn about 😉

Thanks for reading and welcome to Refactor!