Games101 notes (I)

Preliminary knowledge ： linear algebra 、 Advanced mathematics

 

Catalog

One 、 Transformation

1. Matrix transformation

 2. View transformation

Two 、 Rasterize

1 Representation of screen pixels

2. Rasterization algorithm

DDA Numerical differentiation algorithm

Midpoint Bresenham Algorithm

  Triangle rasterization algorithm

3. Anti-Aliasing

4.Z-Buffer Algorithm

  3、 ... and 、 To color

1. Diffuse reflection

2. highlights

 3. Coloring method

Graphics rendering pipeline

---

One 、 Transformation

1. Matrix transformation

2D Transformation

The zoom

The tensile

rotate

  Transformations can be written in matrix form

 

  about 2D Yes

2D_point=(x,y,1)^T

2D_vector=(x,y,0)^T

  about 3D Yes

3D_point=(x,y,z,1)^T

3D_vector=(x,y,z,0)^T

 3D Homogeneous coordinates represent

 2. View transformation

  In the virtual world （x,y,z) Transform the coordinate object to In pixel positions (x,y) In the screen coordinate system represented by (2 dimension )

Model transformation ： rotate , translation , The zoom

Camera conversion ：

Camera or eye position (eye postion) e
Look in the direction (gaze postion) g
The viewpoint is in the up direction (view-up vector ) t

Projection transformation

Orthographic projection ： The relative position of the coordinates will not change , Convert all to one In the space of

Perspective projection ： Perspective projection is the most similar way to what the human eye sees , Follow the near big far small

 

 

  Compress first and then orthographic projection , The transformation matrix is ：

Finally, this compressed space , Re orthogonal projection into a standard small cube , Therefore, the perspective projection transformation is defined ：

 

Add ： View transformation
Model transformation （modeling tranformation）： Transform an object itself （ The zoom 、 rotate 、 Displacement ）
Change of perspective （view tranformation）： Judge the relative position of objects according to the eyes
Projection transformation （projection tranformation）： Project objects in three-dimensional space onto a standard two-dimensional plane ([-1,1]^2) above
Viewport transform （viewport transformation）： Will be in the standard plane mapped to the screen resolution range , namely [-1,1]^2→\rightarrow→[0,width]*[0,height], among width and height Refers to the screen resolution size
 

  Rotation transformation ：

 

Viewport transform ：

 

games101 Homework 1

Eigen::Matrix4f get_model_matrix(float rotation_angle)
{
    Eigen::Matrix4f model = Eigen::Matrix4f::Identity();

    // TODO: Implement this function
    // Create the model matrix for rotating the triangle around the Z axis.
    // Then return it.
    Eigen::Matrix4f tran;
    float angle = rotation_angle / 180.0 * MY_PI;
    tran << cos(angle), -1 * sin(angle), 0, 0,
        sin(angle), cos(angle), 0, 0,
        0, 0, 1, 0,
        0, 0, 0, 1;
    model = tran * model;

    return model;
}

Eigen::Matrix4f get_projection_matrix(float eye_fov, float aspect_ratio,
                                      float zNear, float zFar)
{
    // Students will implement this function

    Eigen::Matrix4f projection = Eigen::Matrix4f::Identity();
    Eigen::Matrix4f per2orth;
    per2orth << zNear, 0, 0, 0,
        0, zNear, 0, 0,
        0, 0, zNear + zFar, -zNear * zFar,
        0, 0, 1, 0;
    float angle = eye_fov * MY_PI / 180.0;
    float t = zNear * tan(angle / 2.0);
    float b = -t;
    float r = t * aspect_ratio;
    float l = -r;

    Eigen::Matrix4f orth;
    orth << 2.0 / (r - l), 0, 0, 0,
        0, 2.0 / (t - b), 0, 0,
        0, 0, 2 / (zNear - zFar), 0,
        0, 0, 0, 1;
    Eigen::Matrix4f trans;
    trans << 1, 0, 0, -(r + l) / 2.0,
        0, 1, 0, -(t + b) / 2.0,
        0, 0, 1, -(zNear + zFar) / 2.0,
        0, 0, 0, 1;
    projection = projection * orth * trans * per2orth;

    // TODO: Implement this function
    // Create the projection matrix for the given parameters.
    // Then return it.


    return projection;
}

Two 、 Rasterize

The purpose of rasterization is to make the object you want to show real on the screen

1 Representation of screen pixels

  Every pixel in the screen is represented by integer coordinates , The maximum and minimum values correspond to the resolution , Considering that each pixel has a certain area , We define (x+0.5,y+0.5) For the sake of (x,y) The center of the pixel , As shown in the black circle in the figure .

Pixels ：

1） It's small squares one by one .

2） The color in each square is exactly the same , Pixel is the smallest unit , There will be no change inside the pixel .

3） We use it 256 Level 0-255 To represent grayscale （ Such as grade 0 It means black , Grade 255 It means white ）, The color in a pixel can be
rgb（red,green,blue） Three values to define , The density of each red, blue and green is represented by various combinations of red, green and blue , For example, red is (255,0,0), White is （255,255,255）.

4） There is no difference in color within a pixel .

Screen space is to establish a two-dimensional coordinate system with the lower left corner of the screen as the origin

1） use (x,y) Represents the position of the pixel .（ Blue pixels are represented by （2,1） Coordinates to represent ）

2） If a screen resolution is width * height, Then we define the pixel subscript from （0,0） To （width - 1,height - 1）,
And (x,y) The center of the pixel is （x + 0.5, y + 0.5）, For example, the center of the blue pixel is （2.5,1.5）.

3） The screen range ranges from （0,0） To （width,height）

Now we're going to place a center at the coordinate origin , The edge length is 2 The cube of is displayed in a length of height、 Wide for width On the screen of

  The specific operation requires a viewport transformation , Accurately speaking, through The zoom And translation Transformation ,

2. Rasterization algorithm

Rasterization is to consider how to present images in raster display . Generally, the image is divided into many different triangles for display .

The reason for choosing a triangle is

1） Triangles are the most basic polygons .

1） The three points of the triangle are connected , The three points must be on a plane .

2） The inside and outside of a triangle are clearly defined , You can judge whether the point is inside the triangle by the cross product of the vector .

3） A well-defined method of triangle vertex interpolation .（ The method used to find the coordinates of the center of gravity later ）

2） Any polygon can be disassembled into multiple triangles .

DDA Numerical differentiation algorithm

It can be used at any two points y = k x + b To express , among k It's the slope , If ∣ k ∣ < 1 Then its main direction of travel is x Axis , namely x The axis changes more than y Shaft speed , On the contrary, if ∣ k ∣ > 1 Then its main direction of travel is y Axis , namely y The axis changes more than x Shaft speed .

Midpoint Bresenham Algorithm

Definition f ( x , y ) = y − k x − b 

At this point, we take the midpoint of these two orange squares , As the point corresponding to the circle symbol in the figure , If this point is below the linear equation , Then it is obvious that we should choose the upper right square .

  Triangle rasterization algorithm

 

  Sample every pixel in the screen , If this pixel is in a triangle, then this pixel should be used

The judgment point is in the triangle

Use cross product to distinguish ： As shown in the figure , We know in advance the three vertices of the triangle we want to rasterize P0,P1,P2, And test points Q. Just calculate separately If the three have the same sign, it represents the point P On the same side of the three line segments , Then it must be inside the triangle , If the sign is different, it means that the point must be outside the triangle .

static bool insideTriangle(int x, int y, const Vector3f* _v)
{   
    //.head(2) The first two values of this point , namely x,y
    Eigen::Vector2f q;
    q << x, y;
    Eigen::Vector2f a, b, c,v0_q,v1_q,v2_q;
    a = _v[1].head(2) - _v[0].head(2);
    b = _v[2].head(2) - _v[1].head(2);
    c = _v[0].head(2) - _v[2].head(2);

    v0_q = q- _v[0].head(2);
    v1_q = q- _v[1].head(2);
    v2_q = q - _v[2].head(2);

    return  a[0] * v0_q[1] - a[1] * v0_q[0] > 0 && b[0] * v1_q[1] - b[1] * v1_q[0] > 0 && c[0] * v2_q[1] - c[1] * v2_q[0]>0;

    // TODO : Implement this function to check if the point (x, y) is inside the triangle represented by _v[0], _v[1], _v[2]
}

3. Anti-Aliasing

The frequency of sampling is too low to keep up with the frequency of the image , Cause the distortion of the final result .

From a simple point of view, the reason for this problem is , We use finite discrete pixels to approximate continuous triangles , Then this kind of sawtooth aliasing will naturally occur , Because this approximation is inaccurate .

  Oversampling anti aliasing SSAA

Subdivide each original pixel , The more sampling points, the better the anti aliasing effect , But the computational burden will also increase

  Multi sampling anti aliasing MSAA

MSAA Is to SSAA An improvement of

  We still have sampling points , But I will only calculate how many sampling points will be triangulated cover, When calculating the color, only the pixel center coordinates will be used to calculate the color once ( That is, all the information will be interpolated to the pixel center, and then the calculated color )

4.Z-Buffer Algorithm

Judge the sequence of objects ： Select the pixel closest to the camera to display

1. Z-Buffer The algorithm needs to maintain a depth array for each pixel, which is recorded as zbuffer, The initial value of each position is set to infinity （ That is, infinity from the camera ）.
2. Then we traverse every pixel on each triangle [x,y], If the depth value of the pixel z, Less than zbuffer[x,y] The value in , Update zbuffer[x,y] The value is the depth value of the point z, And update the pixel at the same time [x,y] The color of is the color of the point on the triangular surface .

 

  3、 ... and 、 To color

  Objects can be observed by us , It is because the human eye receives light from objects

1. Specular reflection
2. Diffuse reflection
3. The ambient light

1. Diffuse reflection

Diffuse reflection is that light is incident from a certain angle and then reflected in all directions from the incident point , And the intensity of light reflected in each different direction is equal

Only when the incident light is perpendicular to the plane can it receive all the light energy completely , The more inclined the incident angle is, the greater the energy loss , say concretely , We should multiply the light intensity by one cos=l*n, among l Is the direction of incident light ,n Is the normal direction of the plane .
In addition to the incident angle , The distance between the light source and the irradiation point should also be considered , Intuitive, , The farther away, of course, the weaker the intensity

 

The center of the figure is a point light , Light is emitted evenly around , It is conceivable that the energy emitted by the light source is actually certain , Then the sum of the energy received in any two circles must be equal . And the farther away from the center of the circle , The larger the area of the circle , The weaker the energy received per unit area

Simulate diffuse reflection

 

among kd Is the diffuse reflection coefficient ,i Incident light intensity ,n.l As shown in the figure, they are normal vector and incident direction ,max In order to eliminate the included angle greater than 90° Light .
 

2. highlights

  The reflected light can be seen only when the observation direction is concentrated close to the reflection direction , Therefore, specular reflection will be considered R And v The angle between α

  among ks Is the specular reflection coefficient ,I Is the incident light intensity ,r Is the distance from the light source to the incident point , Notice here max Eliminate more than 90° After the light , We also multiplied by an index p, The reason for adding this item is very direct , Because the farther away from the reflected light, the less you should see the reflected light , Need an index p Accelerated decay

The ambient light

The ambient light + Diffuse reflection + highlights ：

 3. Coloring method

 Flat Shading： Take each face as a shading unit

 Gouraud Shading： Shade the vertices of each triangle once , Add up the normal vectors of all faces sharing this point to find the mean , Finally, the normal vector of the vertex is obtained by Standardization , For each point inside the triangle, there is ：

  among c 0 , c 1 , c 2 Color the three vertices of the triangle α,β,γ Is the coordinate of the center of gravity of a point in the triangle ,c The color obtained after interpolation for this point .
Phong Shading： Coloring every point inside the triangle

repair ： The coordinates of the center of gravity

Graphics rendering pipeline

Vertex Processing : For all vertex data Model,View, and Projection Transformation of , Finally, the coordinate information projected onto the two-dimensional plane is obtained

Triangle processing : According to the original geometric information , Become a triangle , Each face is represented by 3 The vertices make up

Rasterize

Slice element processing

Homework 3

phong_fragment_shader： The most basic coloring model is Blinn-Phong Reflection model .

highlights + Diffuse reflection + Indirect light or ambient light

• We now consider that the illumination is for any point , Suppose this point is called shading point, So what is the coloring result of this point ？ We define it in a very small range , It's a plane , That is, the plane tangent to its surface
• Since it is a plane , Then there is normal n Perpendicular to the plane
• Similarly, we can also define an observation direction , We stipulate that from shading point The direction to the camera is the observation direction v
• In the same way , from shading point The direction to the light source is called the illumination direction l
• Be careful , Because we only care about the direction of these vectors , So they are all unit vectors , The length is 1

 

 texture_fragment： Than phong_fragment_shader Multi map