Rasterization

Rasterization(光栅化)

After obtaining the results of the viewport transformation, we need to draw them on screen pixels, and this process is called rasterization.

For each geometric shape (such as a triangle), the rasterizer calculates which pixels are covered by the shape and generates fragments for these pixels.

Each fragment contains information such as color and depth, which will be further processed (e.g., shaded, depth-tested, etc.) to ultimately generate the pixel colors on the screen.

光栅化: 将视口变换后的几何图形转换为屏幕上的像素。对于每个几何图形（如三角形），光栅化器会计算哪些像素被该图形覆盖，并为这些像素生成片段（Fragment）。每个片段包含颜色、深度等信息，这些信息将被进一步处理（如着色、深度测试等），最终生成屏幕上的像素颜色。

Why Triangles?

  • Most basic polygon(最基本的多边形)
  • Guaranteed to be planar(保证是平面)
  • Well-defined interior(明确区分内外)
  • Well-defined method for interpolating values at vertices over triangle(barycentric interpolation)(一种用于在三角形顶点之间插值（重心插值）的明确定义的方法)

Sampling(采样)

What pixel values approximate a triangle?

Sampling is a function

Evaluating a function at a point is sampling. We can discretize a function by sampling.

sample if each pixel center is inside triangle

In the previous vector cross calculation, we learned how to determine whether a point is inside a polygon. Here, we use another method.

射线法(Ray Casting Method)

  • 待计算点延x轴正方法发射一条无限远的射线(方向任意, 也不用无限远, 判断与多边形每条边交点即可)
  • 遍历所有边，统计交点数量
  • 如果射线与某条边相交，交点的$x$坐标会大于$x_{p}$
  • 如果 $y_{i}$ 和 $y_{i+1}$分别在$y_{p}$的两侧 $y_{i} ≤ y_{p}$ 且 $y_{i+1} > y_{p} $ 或者 $y_{i} > y_{p}$ 且 $y_{i+1} ≤ y_{p}$
  • 如果交点数量为奇数，点p在多边形内部，若为偶数，则在外部

交点$x$坐标计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool inside(const Point& p, const std::vector<Point>& polygon) {
    int n = polygon.size();
    bool inside = false;
    for (int i = 0; i < n; ++i) {
        int j = (i + 1) % n; 
        const Point& Vi = polygon[i];
        const Point& Vj = polygon[j];
        if ((Vi.y <= p.y && Vj.y > p.y) || (Vi.y > p.y && Vj.y <= p.y)) {
            double x_intersect = Vi.x + (p.y - Vi.y) * (Vj.x - Vi.x) / (Vj.y - Vi.y);
            if (x_intersect > p.x) {
                inside = !inside; 
            }
        }
    }

    return inside;
}

Rasterization = sampling a 2d indicator function

1
2
3
4
5
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);
    }
}

By applying the method mentioned above to fill pixels, we will obtain the figure shown below.

It doesn’t look very good… What’s Wrong with this ?

Jaggies !