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
- 2. Core concepts
- 2.1 Z – the buffering principle
- 2.2 Triangle Interpolation
- 2.3 MSAA anti-aliasing
- 3. Core code description
- 3.1 Judge whether the pixels are in the triangle
- 3.2 Triangle internal interpolation & MSAA implementation
- 3.3 Compiling and Running
- 4. The conclusion
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 codeDraw 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 code3.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 code3.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 code4. 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