Computer Graphics Games101 Assignment 2 —- Triangular Rasterization, Supersampling Anti-Aliasing, Black Edge Processing

Games101 Assignment 2 —- Triangle rasterization, supersampling anti-aliasing, black edge processing

(This article is a collection of notes compiled based on coursework while studying computer graphics. Please point out any errors. If this is the same course, please do not copy and paste, thank you!)

Article directory

  • CG_homework1
    • 0. This assignment implements the function and a brief description (see the code description section below for details)
    • 1. C++ — CG basic syntax
    • 2. Code description
      • A. `insideTriangle()` determines whether the point is inside the triangle
      • B.`rasterize_triangle(const Triangle & amp; t)` Rasterization, supersampling super_sample
      • C. Black border processing (difficulty upgrade)

CG_homework1

0. This assignment implements functions and brief descriptions (for details, see the code description section below)

The following are several functions mainly written in this assignment, and their brief functional descriptions. The complete code of this assignment is on github; link. There may be some details that require minor settings in the project.

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

    Determine whether the point is inside the triangle through vector cross product

  2. void rst::rasterizer::rasterize_triangle(const Triangle & amp; t)

    Triangle rasterization, supersampling super_sample, is used to project a triangle graphic to pixels on the screen using supersampling and perform rendering optimization. Finally, the black edge problem is optimized by recording the supersampled sub-pixel value of each point.

  3. int rst::rasterizer::get_super_index(int x, int y)

    When supersampling, the recording domain is expanded four times and the index of pixels into the depth and color buffers is redefined.

  4. rst::rasterizer::rasterizer(int w, int h) : width(w), height(h)

    Expand the space of depth and color

1. C++ – CG basic syntax

  • Vector3f: A common data type, usually used to represent vectors or points in three-dimensional space.
    • The “Vector” in Vector3f means that it is a vector that can represent both direction and magnitude.
    • “3” indicates that this is athree-dimensional vector, which has three components.
    • “f” indicates that the components are floating point numbers, typically used to store decimal values.
  • Eigen::Vector2f: It is a data type in the Eigen library, which represents a two-dimensional floating point vector. The Eigen library is a C++ template library for performing linear algebra operations, specifically matrix and vector operations.
    • Eigen is the namespace of the library.
    • Vector2f means that this is a two-dimensional floating point vector.
    • Two-dimensional vectors are often used to represent points, directions, or displacements in two-dimensional space.
  • AP = P - A : Computes the vector from point A to point P. It obtains this vector by subtracting the coordinates of point A from the coordinates of point P.
  • eq1 = AB[0] * AP[1] - AB[1] * AP[0] : It is calculated in triangle rasterization to determine whether a point is inside the triangle strong>key steps. Supplement (ABXAP=x1y2-x2y1)
  • std::tie: Create a std::tuple{} to accept the result of subsequent centroid interpolation

2. Code description

A. insideTriangle() Determine whether the point is inside the triangle

insideTriangle() is an implementation of a common mathematical algorithm for determining whether a given point (x, y) is inside a triangle. It uses the concept of center of gravity coordinates to make judgments.

Here are the detailed steps on how the code works:

  1. First, three two-dimensional vectors are defined, A, B, and C, which represent the vertices of the triangle. These vertices are extracted from the _v array.
  2. Three vectors are calculated, AP, BP and CP, which represent the point P to the various vertices of the triangle< Vectors of code>A, B and C.
  3. Three values are calculated, eq1, eq2 and eq3, which are essentially the vectors AP, BP and CP are the cross products of the triangle sides AB, BC and CA respectively.
  4. Finally, check the signs of eq1, eq2, and eq3. If all three of them are positive or all negative, it means that point P is inside the triangle and the function returns true. Otherwise, it returns false.

Essentially it checks whether the pointis on the same sideof each side of the triangle, which is a property of points that are within a triangle. If all three checks pass, it considers the point to be inside the triangle.

When calculating, the vertices of the triangle are specified in counterclockwise order, using the right-hand rule. 

static bool insideTriangle(float x, float y, const Vector3f* _v)
{
    // TODO: Implement this function to check if the point (x, y) is inside the triangle represented by _v[0], _v[1], _v[2]
    const Eigen::Vector2f P(x, y);
    const Eigen::Vector2f A = _v[0].head(2), B = _v[1].head(2), C = _v[2].head(2);

    const Eigen::Vector2f AP = P - A;
    const Eigen::Vector2f BP = P - B;
    const Eigen::Vector2f CP = P - C;
    const Eigen::Vector2f AB = B - A;
    const Eigen::Vector2f BC = C - B;
    const Eigen::Vector2f CA = A - C;

    float eq1 = AB[0] * AP[1] - AB[1] * AP[0]; // ABXAP
    float eq2 = BC[0] * BP[1] - BC[1] * BP[0]; // BCXBP
    float eq3 = CA[0] * CP[1] - CA[1] * CP[0]; // CAXCP

    if (eq1 > 0 & amp; & amp; eq2 > 0 & amp; & amp; eq3 > 0) // Is it inside the triangle?
        return true;
    else if (eq1 < 0 & amp; & amp; eq2 < 0 & amp; & amp; eq3 < 0)
        return true;
    else
        return false;
    
}

B.rasterize_triangle(const Triangle & amp; t) Rasterization, supersampling super_sample

Used to project a triangle primitive onto a pixel on the screen and render it

Supersampling improvement function:

rasterize_triangle(const Triangle & amp; t) : Function used for triangle rasterization (Rasterization), usually used in computer graphics to render three-dimensional graphics to a two-dimensional screen on the process. The specific calculation steps are as follows:

  1. Bounding Box calculation: First, the code calculates the bounding box (Bounding Box) surrounding the triangle. This is done by findingthe minimum and maximum values of the x and y coordinates of the three vertices. These coordinates are thenrounded in order to convert the Bounding Box into integer coordinates for use later in the loop.
  2. Super Sampling: The code defines a set of supersampling steps for anti-aliasing processing. Inside each pixel, it samples four sub-pixels and checks if they are inside the triangle. If so, a counter is incremented to determine how many sub-pixels fell within the triangle during the supersampling process, and the final color is taken as the average of the four.
  3. Iterate over the Bounding Box: The code then iterates through each pixel within the Bounding Box through two nested loops. For each pixel, it checks if any subpixel falls within the triangle, and if so, it increments the counter. The goal of this part is to determine the number of subpixels within a pixel to achieve supersampled anti-aliasing.
  4. Depth Test: If any subpixel is inside the triangle, the code will perform a depth test. It uses the triangle’s vertex data (v) and pixel positions (x,y) to calculate the interpolated depth value (z_interpolated). It thenis compared to the current depth value in the depth buffer (depth_buf). If the new depth value is smaller (meaning that the pixel is closer to the viewer), the color of the pixel is set to the weighted average of the triangle’s color (using the getColor function), and the depth in the depth buffer is updated value.
void rst::rasterizer::rasterize_triangle(const Triangle & amp; t) {<!-- -->
    auto v = t.toVector4();

    // TODO: Find out the bounding box of current triangle.
    // iterate through the pixel and find if the current pixel is inside the triangle

    //1. Find the Bounding Box, which is the largest and smallest x, y coordinates and then round up and down. And expand the bounding box a little, and the result is an integer value, which is convenient for iterative traversal.
    float xmin = std::min(std::min(v[0].x(), v[1].x()), v[2].x());
    float xmax = std::max(std::max(v[0].x(), v[1].x()), v[2].x());
    float ymin = std::min(std::min(v[0].y(), v[1].y()), v[2].y());
    float ymax = std::max(std::max(v[0].y(), v[1].y()), v[2].y());

    xmin = (int)std::floor(xmin);
    xmax = (int)std::ceil(xmax);
    ymin = (int)std::floor(ymin);
    ymax = (int)std::ceil(ymax);

    // Super sampling super_sample_step subdivides a square into four points, calculates the number of points, and takes the average value when coloring t.getColor()*count/4
    std::vector<Eigen::Vector2f> super_sample_step
    {<!-- -->
        {<!-- -->0.25,0.25},
        {<!-- -->0.75,0.25},
        {<!-- -->0.25,0.75},
        {<!-- -->0.75,0.75},
    };
   
    //2. Traverse all elements in the Bounding box to determine whether they are inside the triangle, and perform supersampling to determine how many points fall within the triangle.
    for (int x = xmin; x <= xmax; x + + )
    {<!-- -->
        for (int y = ymin; y <= ymax; y + + )
        {<!-- -->
            int count = 0;
            float minDepth = FLT_MAX;
            // If there is data in supersampling, the overall color will be averaged.
            for (int i = 0; i < 4; i + + )
            {<!-- -->
                if (insideTriangle(x + super_sample_step[i][0], y + super_sample_step[i][1], t.v))
                {<!-- -->
                    count + + ;
                }
            }

            //The coordinate value of the pixel is only 0.5 greater than the integer number value.
            if (count>0)
            {<!-- -->
                // Find the depth value z_interpolated

                float alpha, beta, gamma;
                std::tie(alpha, beta, gamma) = computeBarycentric2D(x, y, t.v);

                // std::tie: Create a std::tuple{<!-- -->} to accept the result of subsequent barycentric interpolation

                float w_reciprocal = 1.0 / (alpha / v[0].w() + beta / v[1].w() + gamma / v[2].w());
                // z_interpolated:
                // w_reciprocal:
                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 the current position depth is smaller than depth_buf), update the color value.
                
                if (z_interpolated < depth_buf[get_index(x, y)])
                {<!-- -->
                    set_pixel(Vector3f(x, y, z_interpolated), t.getColor()*count/4);
                    depth_buf[get_index(x, y)] = z_interpolated;
                }

            }
        }
    }
}

C. Black border processing (difficulty upgrade)

Cause analysis:

  • The black edge appears because the original depth information is not accurate enough. The pixels of the green triangle are rendered before the blue triangle is rendered. As a result, the color of the edge is first interpolated with the black background and becomes black, while the blue triangle is rendered black. Subsequent rendering failed to overwrite the color of the first rendered green triangle.

Solution:

  • Therefore, the way to solve this problem is to record the depth and color of the four samples of each pixel, that is, directly treat it as a quadruple image for processing, and then perform calculations and calculations separately. Coloring.

Improvement Summary:

Supersampling test: Inside each pixel, the code further traverses four supersampled sub-pixels. For each subpixel, it calls the insideTriangle function to check if it is inside a triangle. If inside a triangle, it does the following:

  • Calculate the center of gravity coordinates (alpha, beta, gamma) and interpolated depth value (z_interpolated). This part of the code seems to use the undefined variable v, and should use t.v.
  • Calculate the depth value of z_interpolated.
  • Updates the depth value and color of the corresponding subpixel position of the supersampled depth buffer super_depth_buf and the supersampled framebuffer super_frame_buf.

Determine if coloring is required: Next, the code checks for a flag called judge and if any of the subpixels passes the depth test, judge Set to 1. This flag is used to determine whether shading needs to be done at the original pixel location.

Coloring: If judge is set to 1, indicating that at least one subpixel passed the depth test, then the code will calculate the color at the original pixel position. It averages the colors of four supersampled subpixels and uses the set_pixel function to set the average color to the color of the original pixel location.

//Expand the space of depth and color
rst::rasterizer::rasterizer(int w, int h) : width(w), height(h)
{
    frame_buf.resize(w * h);
    depth_buf.resize(w * h);
    super_frame_buf.resize(w * h * 4);
    super_depth_buf.resize(w * h * 4);
}
// Redefine the index of the pixel into the depth and color buffer
int rst::rasterizer::get_super_index(int x, int y)
{
    //Record all fields expanded four times
    return (height * 2 - 1 - y) * width * 2 + x;
}

std::vector<Eigen::Vector2f> super_sample_step
{
    {0.25,0.25},
    {0.75,0.25},
    {0.25,0.75},
    {0.75,0.75},
};
// Traverse variables for depth detection and assign color values
 for (int x = xmin; x <= xmax; x + + )
{
     for (int y = ymin; y <= ymax; y + + )
     {
        int judge = 0;
        //The specific idea is to record four times the amount of data and write down all the supersampled data.
        for (int i = 0; i < 4; i + + )
        {
            // If depth judgment is performed inside the triangle
            if (insideTriangle(x + super_sample_step[i][0], y + super_sample_step[i][1], t.v))
            {
                float alpha, beta, gamma;
std::tie(alpha, beta, gamma) = computeBarycentric2D(x, y, t.v);
                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;
                //Carry out coordinate transformation again
                // The coordinate processing methods on the x and y axes are different. In the four block squares, the x axis will change four times from 0 to 3, and the y axis will change twice, so the processing is as follows.
                if (super_depth_buf[get_super_index(x*2 + i % 2, y*2 + i / 2)] > z_interpolated)
                {
                    judge = 1;
                    super_depth_buf[get_super_index(x*2 + i % 2, y*2 + i / 2)] = z_interpolated;
                    super_frame_buf[get_super_index(x*2 + i % 2, y*2 + i / 2)] = t.getColor();
                }
            }
        }
        if (judge)
        //If one of the four samples of a pixel passes the depth test, the pixel needs to be colored.
        {
            Vector3f point = { (float)x, (float)y,0 };
            Vector3f color = (super_frame_buf[get_super_index(x*2, y*2)] + super_frame_buf[get_super_index(x*2 + 1, y*2)] + super_frame_buf[get_super_index(x*2, y*2 + 1)] + super_frame_buf[get_super_index(x*2 + 1, y*2 + 1)])/4;
            set_pixel(point, color);
        }
    }
}
syntaxbug.com © 2021 All Rights Reserved.