[笔记] 计算机图形学入门 - 光栅化

好康的：https://www.bilibili.com/video/BV1X7411F744

好玩的：https://www.mathcha.io/editor

三角形

定义

定义视锥：（一般用垂直）视角、宽高比

定义屏幕：屏幕从(0,0)到(w,h)，像素从(0,0)到(w-1,h-1)，各像素中心位置为(x+0.5,y+0.5)

其他略

视口变换

将标准立方体转换到屏幕

1. (-1,-1)移动到(0,0)

2. 宽高从1和1变为width和height

3. 得到变换矩阵

绘制多边形

科普略

采样

即将函数离散化的过程，判断像素中心和三角形关系（是否在三角形内）

设函数inside(tri,x,y)为判断像素(x,y)是否在三角形(tri)内的函数

注：像素中心不是像素，假设像素是第(x’,y’)个，则该像素中心坐标应该为(x’+0.5,y’+0.5)

• inside实现

  依次用三条边的向量叉乘顶点和像素中心点连成的向量（保存顺时针或逆时针），判断点在边的那一侧，如果不是都在同侧则说明在外部，否则在内部。落在边上根据图形api不同处理方式不同，这里忽略

  eg：三角形ABC和点Q，则依次、、，符号相同则在内，不同则在外

• 轴向包围盒（AABB）：

  不用每个像素都调用一次inside，取三角形三个顶点所在坐标，分别取三者中最小、最大的x、y坐标，形成的矩形区域就是轴向包围盒，只用取包围盒内的像素来调用inside就行

  还有更多优化手段，略

• 锯齿/走样问题（Aliasing）

抗锯齿

采样瑕疵（artifacts）：楼梯状锯齿（staircase pattern），摩尔纹，车轮效应（wagon whell effect）

本质：采样速度跟不上信号变化速度

结论：先模糊再采样

理论

一些定义和概念

• 傅里叶变换：通过傅里叶级数展开，一切函数都可以用三角函数来近似模拟。**傅里叶变换可逆，用于信号在时域（或空域）和频域之间的变换。**实际上是将函数拆分成一个个不同频率（逐渐增加）的波形函数相加减（傅里叶级数）。而图像的傅里叶变换其实是将图像的灰度分布函数变换为图像的频率分布函数。

• 走样：采样频率低而信号频率高。

• 滤波：把某个特定的频率的区段抹去。

时域（空域）、频域和滤波

将图像的空域转为频域的示例（左边是空域图，右边是频域图）：

我们定义频域图的中心表示原图像中的最低频部分（0频率点），向外侧延伸频率逐渐增大。这里的频率指的是灰度变化的梯度。

频域图上的点亮度表示图像的能量大小，也就是信息量（灰度值）。纯黑的图片没有能量，所以其频域图也为全黑。反之纯白的图片有能量但全部集中在低频区域（整张图没有任何地方有灰度变化），表现在频域图就是一张全黑的图片中心有一个极亮的点。

对图像而言，大部分能量都集中在低频，也就是说图像大部分信息都是过渡比较平缓（相邻区域之间灰度相差相对小）的；少数能量在高频，比如边缘和线条处信息快速变化（相邻区域之间灰度相差相对大）

也可以这么来理解：一个函数傅里叶展开为级数后最占主导、最接近原函数的是最前面的相对低频率的波形函数，没那么占主导、不那么接近原函数的是后面的相对高频率的波形函数。波形函数越接近原函数，表现其拥有的原函数的信息越多，反之则少。

所以一般来说，都会出现这种信息大部分都集中在低频的现象。而将这些傅里叶展开后的内容变为图像来展示，就表现为中心亮，两边暗的图像。

需要注意的是，频谱图上的各点与图像（空域）上各点并不存在一一对应的关系，频谱上每⼀点都与空域所有点有关，空域每⼀点都与频谱上所有点有关。

关于为什么会出现横竖两条亮线，课上和我查到资料都说是因为转化为频域图的时候认为图像的左右边界、上下边界是相接的导致的，但是个人还是不太理解，先在这里记一下。

使用高通滤波（将低频信号抹去只留下高频信号），可以快速得到图像的边界：

使用低通滤波（将高频信号抹去只留下低频信号），可以快速去掉图像的边界，得到模糊的图像：

同时抹去高频和低频的信号，则可以得到不那么模糊也不那么锋利的图像，也就是更大的边界：

卷积和乘积

图形学（和数学区分）上简化的定义：卷积=取原始信号和其周围信号的加权平均作为新的信号

时域（空域）上两个信号的卷积=转换到频域上的两个信号的乘积，反之亦然。

也就是为了处理一个图像，可以用卷积核和它进行卷积，也可以将它们都转换到频域（此时转换后的卷积核又叫滤波器）然后进行乘积，最后再进行反向的傅里叶变换得到处理后的图像。

卷积核越大，图像越模糊，也就是低通滤波，去掉高频信息，反应在滤波器上就是其频域图中心的白色区域越小。反之同理。

频域和采样

采样其实就是重复频域上的内容

一些定义和概念：

• 冲激函数：，其定积分为1，即，于是对于一个信号函数f(x)，可以通过来取得其f(0)处的值，也就是说其具有冲激函数与任何连续函数的乘积积分，最终只留下连续函数在冲激位置的值的性质，这可以用来对一个复杂的函数进行采样。

• 冲激函数对任意位置的扩展应用：，和前面类似，可以通过​从而达到在任意位置进行取样的目的。

• 冲激串，在轴上按一定周期部署一系列冲激函数，从而对整个信号函数进行离散的取样

• 用于采样的冲激串，在经过傅里叶变换后会变为不同周期的冲激串，但形式上还是冲激串

• 空域上乘积=频域上卷积，频域上乘积=空域上卷积

那么就有：在空域上一个信号函数和一个冲激串的乘积（也就是采样），在频域上等价于经过傅里叶变换后的该函数与经过傅里叶变换后的冲激串进行卷积（也就是复制）：

在图中就是(a)、(c)的乘积为(e)，(b)、(d)的乘积为(f)，而(a)和(b)、(c)和(d)、(e)和(f)都是同样的内容在傅里叶变换两侧的形式，左侧的乘积采样过程在右侧表现为卷积，也就是将(b)复制了很多份。

即：采样就是对原始信号频谱的重复

采样周期越大，重复周期越小。如果采样周期过大就会导致重复的频谱很密集，甚至发生混叠。这就是走样（Aliasing）的本质。

解决走样的方法

• 增加采样率（也就是减小采样周期，从而增加复制频谱的间隔），换言之，增加显示器分辨率

• 先做模糊再做采样（先通过低通滤波将高频信息去掉，也就是砍掉频谱的一部分，从而让采样后频谱不发生混叠）

  让图像模糊的方法：

  用单个像素的卷积核对三角形进行卷积（也就是对三角形落在每一个像素内的部分都进行平均，注意这里的像素不是点而是一个小方格）

实践

MSAA

可以简单理解为将一个像素分成多个子像素，计算三角形在像素内的覆盖率，然后根据覆盖率进行不同程度的上色。注意：子像素只是用来计算覆盖率，并不是提升了像素数量。

实际上复杂的多，子像素的分布不一定均匀，而且有的子像素会被复用。

FXAA

快速近似抗锯齿，单纯是进行图像的后期处理。先算出一张有锯齿的图，然后通过一些图像匹配的方法找到边界，然后将有锯齿的边界直接替换成无锯齿的边界。

TAA

时域抗锯齿。在不同时间点使用像素内不同位置的点来测试三角形是否覆盖该点，然后复用上一帧的测量结果来计算覆盖率。本质上是将MSAA的采样点分布在时间轴上，以达到不增加本帧计算量的效果。这种抗锯齿手段在画面快速变化的时候会很糟糕，但是处理静止画面很好使。

Super Resolution / Super Sampling

实际上不是抗锯齿，但有点类似。而且如果先超采样最后再降回来也可以达到抗锯齿的效果（SSAA）。

本质是将高分辨率但采样不足的图恢复到高采样频率的效果，也就是小图到大图。比如DLSS，就是用深度学习来猜测没被采样到的细节。

作业

Assignment2

本来根据助教在hw2的疑问#post-3410和hw2的疑问#post-3662的回复，应该在rasterizer.cpp内应修改代码框架（否则三角形前后顺序会相反），但是如果按照助教说的改其实只是治标不治本，问题出现的根本原因还是作业框架使用了左手系，这里改了后面可能会有更麻烦的问题。所以和Assignment1类似，直接将投影矩阵改成左手系的即可。（详情见《变换》的笔记）

叉乘判断像素是否在内部，最后绘制像素。代码如下：

static bool insideTriangle(int x, int y, const Vector3f *_v) {
    // Check if the point (x, y) is inside the triangle represented by _v[0], _v[1], _v[2]
    float c1 = (_v[0].x() - (x + 0.5f)) * (_v[0].y() - _v[1].y()) - (_v[0].y() - (y + 0.5f)) * (_v[0].x() - _v[1].x());
    float c2 = (_v[1].x() - (x + 0.5f)) * (_v[1].y() - _v[2].y()) - (_v[1].y() - (y + 0.5f)) * (_v[1].x() - _v[2].x());
    float c3 = (_v[2].x() - (x + 0.5f)) * (_v[2].y() - _v[0].y()) - (_v[2].y() - (y + 0.5f)) * (_v[2].x() - _v[0].x());
    if ((c1 > 0 && c2 > 0 && c3 > 0) || (c1 < 0 && c2 < 0 && c3 < 0)) {
        return true;
    }
    return false;
}

//Screen space rasterization
void rst::rasterizer::rasterize_triangle(const Triangle &t) {
    auto v = t.toVector4();
    
    // Find out the bounding box of current triangle.
    int left = floor(std::min({v[0].x(), v[1].x(), v[2].x()}));
    int right = ceil(std::max({v[0].x(), v[1].x(), v[2].x()}));
    int bottom = floor(std::min({v[0].y(), v[1].y(), v[2].y()}));
    int top = ceil(std::max({v[0].y(), v[1].y(), v[2].y()}));
    
    // Iterate through the pixel and find if the current pixel is inside the triangle
    for (int x = left; x <= right; x++) {
        for (int y = bottom; y <= top; y++) {
            if (!insideTriangle(x, y, t.v)) continue;
            // If so, use the following code to get the interpolated z value.
            auto [alpha, beta, gamma] = computeBarycentric2D(0.5f + x, 0.5f + 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;

            if (z_interpolated > depth_buf[get_index(x, y)]) continue;
            depth_buf[get_index(x, y)] = z_interpolated;
            // set the current pixel (use the set_pixel function) to the color of the triangle (use getColor function) if it should be painted.
            set_pixel(Vector3f(x, y, 1), t.getColor());
        }
    }
}

提高项要求用super-sampling做抗锯齿，这里对代码进行一波大改。

首先修改insideTriangle，参数由像素坐标变为像素中心坐标（同时修改头文件）：

-static bool insideTriangle(int x, int y, const Vector3f *_v) {
-    // Check if the point (x, y) is inside the triangle represented by _v[0], _v[1], _v[2]
-    float c1 = (_v[0].x() - (x + 0.5f)) * (_v[0].y() - _v[1].y()) - (_v[0].y() - (y + 0.5f)) * (_v[0].x() - _v[1].x());
-    float c2 = (_v[1].x() - (x + 0.5f)) * (_v[1].y() - _v[2].y()) - (_v[1].y() - (y + 0.5f)) * (_v[1].x() - _v[2].x());
-    float c3 = (_v[2].x() - (x + 0.5f)) * (_v[2].y() - _v[0].y()) - (_v[2].y() - (y + 0.5f)) * (_v[2].x() - _v[0].x());
+static bool insideTriangle(float x, float y, const Vector3f *_v) {
+    // Check if the point center (x, y) is inside the triangle represented by _v[0], _v[1], _v[2]
+    float c1 = (_v[0].x() - x) * (_v[0].y() - _v[1].y()) - (_v[0].y() - y) * (_v[0].x() - _v[1].x());
+    float c2 = (_v[1].x() - x) * (_v[1].y() - _v[2].y()) - (_v[1].y() - y) * (_v[1].x() - _v[2].x());
+    float c3 = (_v[2].x() - x) * (_v[2].y() - _v[0].y()) - (_v[2].y() - y) * (_v[2].x() - _v[0].x());
     if ((c1 > 0 && c2 > 0 && c3 > 0) || (c1 < 0 && c2 < 0 && c3 < 0)) {
         return true;
     }
     return false;
 }

然后在头文件加上指示采样倍数的变量：

int super_sampling_times = 2; // super-sampling 倍数

然后将depth_buf改名为sample_depth_buf，设置为和super_sampling_times挂钩，添加sample_frame_buf（同时修改头文件），然后对相关方法进行一些修改：

 void rst::rasterizer::clear(rst::Buffers buff)
 {
     if ((buff & rst::Buffers::Color) == rst::Buffers::Color)
     {
         std::fill(frame_buf.begin(), frame_buf.end(), Eigen::Vector3f{0, 0, 0});
+        std::fill(sample_frame_buf.begin(), sample_frame_buf.end(), Eigen::Vector3f{0, 0, 0});
     }
     if ((buff & rst::Buffers::Depth) == rst::Buffers::Depth)
     {
-        std::fill(depth_buf.begin(), depth_buf.end(), std::numeric_limits<float>::infinity());
+        std::fill(sample_depth_buf.begin(), sample_depth_buf.end(), std::numeric_limits<float>::infinity());
     }
 }
 
 rst::rasterizer::rasterizer(int w, int h) : width(w), height(h)
 {
     frame_buf.resize(w * h);
-    depth_buf.resize(w * h);
+    sample_frame_buf.resize(w * h * super_sampling_times * super_sampling_times);
+    sample_depth_buf.resize(w * h * super_sampling_times * super_sampling_times);
 }
 
 int rst::rasterizer::get_index(int sample_x, int sample_y)
 {
-    return (height -1 - sample_y) * width + sample_x;
+    return (height * super_sampling_times -1 - sample_y) * width * super_sampling_times + sample_x;
 }

模仿set_pixel写一个set_sample_pixel方法：

void rst::rasterizer::set_sample_pixel(const Eigen::Vector3f &point, const Eigen::Vector3f &color)
{
    //old index: auto ind = point.y() + point.x() * width;
    auto ind = (height * super_sampling_times - 1 - point.y()) * width * super_sampling_times + point.x();
    sample_frame_buf[ind] = color;
}

降低到原像素时颜色需要混合，所以添加get_sample_pixel方法获取sample_frame_buf内像素的颜色（同时修改头文件），downgrade方法处理多像素合一：

const Eigen::Vector3f &rst::rasterizer::get_sample_pixel(int x, int y)
{
    //old index: auto ind = point.y() + point.x() * width;
    auto ind = (height * super_sampling_times - 1 - y) * width * super_sampling_times + x;
    return sample_frame_buf[ind] ;
}
void rst::rasterizer::downgrade_frame() {
    for (int x = 0; x < width; x++) {
        for (int y = 0; y < height; y++) {
            Vector3f color(0, 0, 0);
            for (int x_more = 0; x_more < super_sampling_times; x_more++) {
                int sample_x = super_sampling_times * x + x_more;
                for (int y_more = 0; y_more < super_sampling_times; y_more++) {
                    int sample_y = super_sampling_times * y + y_more;
                    color += (get_sample_pixel(sample_x, sample_y) / super_sampling_times / super_sampling_times);
                }
            }
            set_pixel(Vector3f(x, y, 1), color);
        }
    }
}

然后是最重要的rasterize_triangle方法：

//Screen space rasterization
void rst::rasterizer::rasterize_triangle(const Triangle &t) {
    auto v = t.toVector4();

    // Find out the bounding box of current triangle.
    int left = floor(std::min({v[0].x(), v[1].x(), v[2].x()}));
    int right = ceil(std::max({v[0].x(), v[1].x(), v[2].x()}));
    int bottom = floor(std::min({v[0].y(), v[1].y(), v[2].y()}));
    int top = ceil(std::max({v[0].y(), v[1].y(), v[2].y()}));

    if (super_sampling_times < 1) return;
    // Iterate through the pixel and find if the current pixel is inside the triangle
    for (int x = left; x <= right; x++) {
        for (int y = bottom; y <= top; y++) {
            int subpixel_num = 0;
            for (int x_more = 0; x_more < super_sampling_times; x_more++) {
                int sample_x = super_sampling_times * x + x_more;
                for (int y_more = 0; y_more < super_sampling_times; y_more++) {
                    int sample_y = super_sampling_times * y + y_more;
                    Vector2f pixel_center((float) (2 * x_more + 1) / (2 * super_sampling_times) + x,
                                          (float) (2 * y_more + 1) / (2 * super_sampling_times) + y);
                    if (!insideTriangle(pixel_center.x(), pixel_center.y(), t.v)) continue;
                    // If so, use the following code to get the interpolated z value.
                    auto [alpha, beta, gamma] = computeBarycentric2D(pixel_center.x(), pixel_center.y(), t.v);
                    float w_reciprocal = 1.0f / (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;
                    int depth_index = get_index(sample_x, sample_y);
                    if (z_interpolated >= sample_depth_buf[depth_index]) continue;
                    sample_depth_buf[depth_index] = z_interpolated;
                    subpixel_num++;
                }
            }
            // set the current pixel (use the set_pixel function) to the color of the triangle (use getColor function) if it should be painted.
            if (subpixel_num == 0) continue;
            float weight = ((float) subpixel_num) / (super_sampling_times * super_sampling_times);
            set_pixel(Vector3f(x, y, 1), t.getColor() * weight + get_pixel(x, y) * (1.0f - weight));
        }
    }
}

最后在draw方法的最后调用downgrade_frame()方法即可。

结果如下：

这里值得注意的是这里的方法是建一个sample_frame_buf来存放super sampling的图像，然后最后downgrade回原像素，也就是超采样后再像素多合一降回来（当然也可以每次计算sample_frame_buf后马上写入frame_buf，但是除了增加写入frame_buf的次数和更方便理解以外没有任何好处）

而如果是只考虑覆盖率，一边画一边合成颜色的话（可以看作MSAA），有几率（因为绘制顺序会影响）导致边缘出现黑色条，原因是底层的三角形边缘与黑色混合后又和顶层三角形混合了。

如果不混合非本三角形内的颜色，就有可能会产生很黑的黑边。如果混合非本三角形内的像素，则有可能会产生比较浅的黑边，比如这样：

解决方案其实也有，就是再新增一个last_origin_color_buf来储存每个像素（非子像素）原本应该上的色，即上一次上色时如果不混合的情况下应该上的颜色。这样处理，在再次往这个像素内上色的时候，就不需要拿像素本身已经着的颜色，而是去拿上一次上色时未混合的颜色。这样就可以保证第三次上色的时候，只和第二次上色混合，而不会被第一次、第二次结果混合的颜色所影响（一开始全黑也可以看作是一次上色）。这样的效果和SSAA差不多，但是比起SSAA那种需要多储存一份大小的数组，这样处理只需要多储存一份的数组，空间上有更大的优势。

具体代码懒得写了，随缘吧。