GAMES101 Series Summary (2) - grating

Posted on Edited on In Waline:

GAMES101 系列总结（一）：线性代数与模型变换中我们讲了如何通过MVP矩阵将模型上的点坐标变为[−1,1]3[-1,1]^3的一个立方体之中的坐标，这篇文章我们继续介绍，如何将这个立方体中的点绘制到屏幕上。

The grating is mainly divided into three parts. The first is to split all the points into triangles one by one. This process is called Triangles. In this process, there may be serrations caused by the position covered by some triangles that cannot be represented by pixels., so we have to do anti-aliasing, this process is called Antialiasin, and there is how to conduct depth testing in the process of mapping from three-dimensional to two-dimensional, that is, how to use Z-Buffer.

Triangles

What is Screen?

First of all, we need to understand what the screen is composed of. The answer to this question is that the screen is composed of pixels. In fact, the screen resolution we usually say, such as 1920 * 1080, 2K, 4K refers to how many pixels the screen has. Each pixel can be simply understood as one by one. Small lights of different colors can be emitted.

Of course, the more pixels, the more delicate the effects we can simulate and restore, and the more pixels to a certain extent, that is, when we cannot recognize the pixels with the naked eye, it is what we often call the retina screen.

We assume that a screen consists of the following pixels:

  • We can represent pixels with coordinates (x, y), and both x and y are integers
  • pixel coordinates from (0,0) to (width - 1, height - 1)
  • the center of the pixel (x, y) is at (x + 0.5, y + 0.5)
  • Screen coverage is (0,0) to (width, height)

We went through the previous MVP matrix and actually adjusted the entire optic cone to a cube of $[-1, 1] ^ 3 $. What we need to do now is to adjust the coordinates of the points in this cube to the screen of $[0, width] * [0, height] $

Specifically, it is divided into two steps:

  1. Temporarily ignore the z coordinate (here, temporarily ignore means that the z coordinate is not used here, but will be used later in the depth test), then the coordinate of the point changes from $[-1,1] ^ 2 $becomes $[-1,1] ^ 3 $
    Use a matrix to convert $[-1, 1] ^ 2 $to $[0, width] * [0, height] $

Mviewport=[width200width20height2height2000100001]M_{viewport} = \begin{bmatrix} \frac{width}{2} & 0 & 0 & \frac{width}{2} \\ 0 & \frac{height}{2} & \frac{height}{2} & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}

Triangular surface

We just talked about how to change the coordinates of points into pixel coordinates on the screen, but isolated points cannot represent an object. We need the surface formed by connecting these points to represent the object.

So should we connect these points into a few sides?

Is the answer a triangle?

So why use a triangle? The reasons are as follows:

  1. Triangles are the most basic polygons, and any polygon can be divided into several triangles
  2. Unique Attributes
    1. Guaranteed to be flat. For example, a quadrilateral, the four points may not be on the same plane
    2. The interior is clearly defined. For example, a quadrilateral has convex polygons and concave polygons. The latter is more difficult to judge whether the point is inside the quadrilateral
    3. Well-defined interpolation method, with vertices on triangles (barycenter interpolation)

Convert triangular surfaces to screen pixels

Now that we have transformed the points on the model into two-dimensional screen space $[0,0] $to $[width, height] $, and become triangular patches one by one, the question now is how to determine These patches cover those pixels, or how to use the color of this triangular surface to determine the color of the screen pixels, as shown in the figure below:

Sampling

The first method is to simply sample and traverse each pixel on the screen. For the color of each pixel, we define a function to calculate it, as follows:

1
2
for (int x = 0; x < xmax; ++x) 
    output[x] = f(x);

So how is this f defined?

One way is to determine whether the center of this pixel is inside the triangle. If so, assign it the color of the cover point on the triangle surface, as shown in the figure below:

Expressed in formula is:

inside(t,x,y)={1,Point(x,y)intriangle0,otherwiseinside(t,x,y) = \begin{cases} 1, &Point(x,y) &in & triangle \\ 0, & otherwise \end{cases}

1
2
3
for (int x = 0; x < xmax; ++x) 
    for (int y = 0; y < ymax; ++y) 
        image[x][y] = inside(tri,x + 0.5, y + 0.5);

So how to tell if a point is inside a triangle? You can see the previous blog, which talked about this question, through the cross product of vectors

So, is this method completed in this way? Not yet, there is another situation we have not considered, that is, what if the center point of the pixel is not inside the triangle nor outside the triangle, that is, just on the side, or even on the sides of two triangles at the same time, as shown in the figure below:

The solution is relatively simple, you can just choose one at will.

Bounding box

In addition, there is a question, do we want to perform this inside function for every pixel on the screen?

The answer is no, we can first calculate the bounding box of the triangle, and then traverse the pixels inside the bounding box, and the pixels outside the bounding box will never be affected by this triangle.

Sampling result

After the above process, the pixels of a triangle on the screen will be represented as:

It can be seen that if the resolution is not enough, there will be obvious jaggings, as follows,

What will happen to the sampling?

Jaggies (serrated)

The effect of sawtooth is what the previous picture shows

So how do we do anti-aliasing?

Blurring

The core idea of this approach is that the reason for the jaggings is that all the pixels are either pure red or pure white

We can avoid this non-red and white situation by doing some blurring in advance, as shown in the figure below:

Oversampling

The so-called super sampling means that before we used a pixel value corresponding to a coordinate to the triangle to make judgments, now we split a pixel into multiple sampling points to the triangle to sample

The basic steps are:

  1. Select an N * N matrix to sample each pixel
  2. Sample each sample point, and then take the average value as the final value of the pixel

Molar pattern

Take a place

Wagon

Take a place

z-bufferings

In fact, this problem is that although we just grating, although we temporarily ignored the z coordinate, but we are 3D, there may be multiple triangles covering the same pixel point, what should we do at this time?

One way is that we iterate over each triangle to see its z-coordinate size, and if we encounter a triangle closer to the camera, we replace the color of the current pixel with its color value.

But there is a problem is that we only have the coordinates of each point, how to judge the z coordinate of a triangle, and secondly, how to deal with the situation where three triangles cover each other, as shown below:

The solution is that we still traverse each triangle, but the depth value is recorded by each pixel itself. What we record is the depth information of the pixel’s current color corresponding to a point on the triangle, not the depth information of the triangle

1
2
3
4
5
6
7
for (each triangle T)
    for (each sample (x,y,z) in T)
        if (z < zbuffer[x,y]) // closest sample so far
            framebuffer[x,y] = rgb; // update color
            zbuffer[x,y] = z; // update depth
        else
            ; // do nothing, this sample is occluded