Using (2)Triangles and Z-buffering

Welcome to follow the public account: Sumsmile/focus on image processing mobile development veteran

The first part mainly talks about the transformation of three coordinate systems in graphic rendering and line interpolation drawing, which is the most basic concept of rasterization. The second part goes further and talks about how to realize internal interpolation and front and back occlusion, namely z-buffering. Another important concept, MSAA(Multi-sampling AA), is added.

Directory:

1. Achieve results

Seemingly simple things take a little effort for beginners to fully understand.

2. Core concepts

Z-buffering first, serrations a little more difficult later

2.1 Z – the buffering principle

Multiple objects appear in the scene at the same time, and finally only one plane is displayed on the screen, which must be the front one and the back one. Just like painting, first draw the grass and mountains behind, and then draw the young trees in front.

The rendering process is slightly different in that before a frame is actually drawn to the screen, it is already fused, stripped of subsequent data, and finally drawn to the screen. It’s not like you’re painting a picture and you’re stacking frames on the screen.

Implementing a “cull” that preserves only the data from the most recent scenario is called z-buffering. If the screen resolution is 1280*720, use the same amount of memory to record the Z coordinates of 1280*720 points and keep them updated.

So here the Z coordinate is pointing out of the screen, and the bigger the Z coordinate is, the closer it is to the screen. In fact, coordinate systems are not necessarily the same in different graphics rendering apis.

In Android, SurfaceFlinger does something like z-buffering by combining multiple views into a single image.

2.2 Triangle Interpolation

Triangles have many features that make them ideal for rendering as the smallest unit, such as:

• All vertices/edges are in the same plane
• The internal points are well defined
• Interpolation between vertices within a triangle is easy to achieve (centroid interpolation)

Of course, other geometric shapes can also be used as minimum units, triangles are more common.

How can a continuous shape be drawn onto discrete pixels?

Based on linear interpolation, any point inside a triangle can be linearly interpolated according to the attributes of the vertex (such as color, z coordinates)

Here we do not derive linear/bilinear interpolation algorithm implementation, the principle is not complex, the derivation is slightly wordy.

It should be noted that it is not accurate to interpolate z coordinates after projection transformation, because the projection transformation is nonlinear, and the three coefficients obtained can not be directly used for interpolation, so they need to be corrected. The following code implementation is approximated to simplify complexity

Reference perspective correction interpolation [1]

2.3 MSAA anti-aliasing

Because of the discretization of screen pixels, the geometric lines of the hypotenuse are easily zigzagged, and the lower the resolution, the more pronounced.

How do you deal with serrations? Two ideas:

• First, the image sampling is dense enough and the resolution is high enough
• It is not economical to process images in a large resolution, which consumes more memory and processing resources. Supersampling is a good compromise.

The principle of oversampling: Assuming that each pixel is a square, four dots (actually only one dot) are evenly distributed within it, each accounting for 1/4 of the weight. If there are three dots in a pixel in the graph, then the red dot shows only 3/4 of the intensity.

The edges are well treated with color intensity, and the ambiguous pixels look lighter, mimicking the effect of the edges.

3. Core code description

Most of the project code is similar to the first code, focusing on two pieces of code, determining whether points are in a triangle, interpolation, and hypersampling.

3.1 Judge whether the pixels are in the triangle

Use the cross product to determine whether a point is in a triangle. Basic knowledge of linear algebra, the principle is very simple, do not repeat.

There are many versions of the code, some of the cross product with code implementation, slightly wordy, the following code directly with the vector library cross product method.

static bool insideTriangle(float x, float y, const Vector3f* _v)

{   

    Vector3f P(x+0.5 f,y+0.5 f.1.0 f);

    const Vector3f& A = _v[0];

    const Vector3f& B = _v[1];

    const Vector3f& C = _v[2];



    Vector3f AB =  B - A;

    Vector3f BC =  C - B;

    Vector3f CA =  A - C;



    Vector3f AP = P - A;

    Vector3f BP = P - B;

    Vector3f CP = P - C;



    float z1 = AB.cross(AP).z();

    float z2 = BC.cross(BP).z();

    float z3 = CA.cross(CP).z();



    return (z1 > 0 && z2 >0 && z3 > 0) ||  (z1 < 0 && z2 <0 && z3 < 0);

}

Copy the code

Draw method to handle projection transformation, the first article has been described in detail, after processing point coordinates transformation, call rasterize_triangle() method to perform the triangle rasterize_triangle()

void rst::rasterizer::draw(pos_buf_id pos_buffer, ind_buf_id ind_buffer, col_buf_id col_buffer, Primitive type)

{

.

.

    rasterize_triangle(t);

}

Copy the code

3.2 Triangle internal interpolation & MSAA implementation

Triangle rasterization, the most core code snippet, important places have comments

//Screen space rasterization

void rst::rasterizer::rasterize_triangle(const Triangle& t) {

    // The three points of the triangle are converted into 4-dimensional vectors, adding w dimensions

    auto v = t.toVector4();



 // Find the smallest quadrilateral enclosing a triangle, so that only the quadrilateral can be handled

    // v is a two-dimensional array with three vectors, each with four components of x, y, z, and w

 float min_x = std::min(v[0] [0].std::min(v[1] [0], v[2] [0]));

    float max_x = std::max(v[0] [0].std::max(v[1] [0], v[2] [0]));

 float min_y = std::min(v[0] [1].std::min(v[1] [1], v[2] [1]));

 float max_y = std::max(v[0] [1].std::max(v[1] [1], v[2] [1]));



 min_x = (int)std: :floor(min_x);

 max_x = (int)std: :ceil(max_x);

 min_y = (int)std: :floor(min_y);

 max_y = (int)std: :ceil(max_y);



    // Controls whether to turn on MSAA anti-aliasing

 bool MSAA = false;

 //MSAA 4X

 if (MSAA) {

  // Subdivide the coordinates of four small points in the grid

  std: :vector<Eigen::Vector2f> pos

  {

   {0.25.0.25},

   {0.75.0.25},

   {0.25.0.75},

   {0.75.0.75},

  };

  for (int x = min_x; x <= max_x; x++) {

   for (int y = min_y; y <= max_y; y++) {

    // Record the minimum depth

    float minDepth = FLT_MAX;

    // The number of dots that fall into the triangle

    int count = 0;

    // Determine the coordinates of the four dots

    for (int i = 0; i < 4; i++) {

     // Whether the dot is inside the triangle

     if (insideTriangle((float)x + pos[i][0], (float)y + pos[i][1], t.v)) {

      // If at, interpolate depth z

      auto tup = computeBarycentric2D((float)x + pos[i][0], (float)y + pos[i][1], t.v);

      float alpha;

      float beta;

      float gamma;

                        // STD ::tie means to break tUP to alpha beta gamma

      std::tie(alpha, beta, gamma) = tup;



                        / / reciprocal countdown

      float w_reciprocal = 1.0 / (alpha / v[0].w() + beta / v[1].w() + gamma / v[2].w());



                        // Interpolate the z value of the current frame according to the weight of the three frames of the triangle, and calculate the z value

                        // Alpha beta gamma needs to be corrected

                        // Here is a question: why can't we find the z-coordinate mapping of each point in the projection transformation?

      float z_interpolated = alpha * v[0].z() / v[0].w() + beta * v[1].z() / v[1].w() + gamma * v[2].z() / v[2].w();

      z_interpolated *= w_reciprocal;

                        // Find the depth of the four dots corresponding to the current point, to represent the current point z value, used to compare with other points z

      minDepth = std::min(minDepth, z_interpolated);

                        // contains a point count +1

      count++;

     }

    }

    if(count ! =0) {

     if (depth_buf[get_index(x, y)] > minDepth) {



                        // Simple color/4 is also ok, the processing is more rough.

                        // Note that getColor uses only one value, and all three points of the triangle have the same color

                        // The color value stored in the current buffer is also taken into account

      Vector3f color = t.getColor()*count/4 + (4-count)*frame_buf[get_index(x,y)]/4;

      Vector3f point(3);

      point << (float)x, (float)y, minDepth;

      // Replace the depth

      depth_buf[get_index(x, y)] = minDepth;

      // Change the color

      set_pixel(point, color);

     }

    }

   }

  }

 }

 else {

        // MSAA anti-aliasing is not considered

  for (int x = min_x; x <= max_x; x++) {

   for (int y = min_y; y <= max_y; y++) {

    if (insideTriangle((float)x + 0.5, (float)y + 0.5, t.v)) {

     auto tup = computeBarycentric2D((float)x + 0.5, (float)y + 0.5, t.v);

     float alpha;

     float beta;

     float gamma;

     std::tie(alpha, beta, gamma) = tup;

     float w_reciprocal = 1.0 / (alpha / v[0].w() + beta / v[1].w() + gamma / v[2].w());

     float z_interpolated = alpha * v[0].z() / v[0].w() + beta * v[1].z() / v[1].w() + gamma * v[2].z() / v[2].w();

     z_interpolated *= w_reciprocal;



     if (depth_buf[get_index(x, y)] > z_interpolated) {

      Vector3f color = t.getColor();

      Vector3f point(3);

      point << (float)x, (float)y, z_interpolated;

      depth_buf[get_index(x, y)] = z_interpolated;

      set_pixel(point, color);

     }

    }

   }

  }

 }

}

Copy the code

3.3 Compiling and Running

cd build

make -j4

./Rasterizer image01.png



// filename = std::string(argv[1]); Can read the command line parameters, record the name of the image to save

// the first argument to argv[I] is./Rasterizer

// The second argument is image01.png, which saves the image and renders it to the screen without arguments



Copy the code

4. The conclusion

Most of the pictures and formulas in the article are quoted from yan Lingqi – Modern Graphics

The next post is on ray tracing, which is the hard part of graphics rendering.

Welcome to follow the public account: Sumsmile/focus on image processing mobile development veteran

^{[2] [3] [4] [5] [6]}

The resources

[1]

Perspective correction interpolation and graphics rendering pipeline summary: https://zhuanlan.zhihu.com/p/144331875

[2]

Note – rasterizer and shading: https://zhuanlan.zhihu.com/p/140779399

[3]

Discussion area holds the homework 3 about depth value problem on pit and some ideas: http://games-cn.org/forums/topic/zuoye3-guanyushenduzhiwentizijicaidekengheyixiexiangfa/

[4]

Games101-2 good implementation: https://blog.csdn.net/qq_36242312/article/details/105758619

[5]

Code 1: https://github.com/kingiluob/Games101/blob/master/Assignment2/rasterizer.cpp

[6]

Code implementation – 2: https://github.com/Quanwei1992/GAMES101/blob/master/02/rasterizer.cpp