Rasterization

Posted on

Rasterization

Screen

对于一个宽高为width, height的屏幕来说，从一个视点来看可以形成一个视锥：

定义一个宽高比
$$
{\rm Aspect Ratio }=\frac{\rm width}{\rm height}
$$
以及一个垂直视角 Vertical Field of View(fovY):连接屏幕宽的中点，和视点形成的夹角；

同理定义水平可视角度；

image-20241207172656304

形式化来说
$$
\tan\frac{\rm fovY}{2}=\frac{t}{|n|}\
{\rm AspectRatio} =\frac{r}{t}
$$
image-20241207173113298

将屏幕(screen)抽象出如下要素

  • 一个由像素(pixel)构成的二维数组
  • 数组的大小称为分辨率(resolution)
  • 屏幕是典型的光栅成像设备

光栅化定义为将物品画在屏幕上的过程；

像素可以理解为一个颜色不变的小方块

如果我们需要将标准立方体一个面$[-1,1]^2$上的物品视图变换到$[0,\rm width]\times[0,height]$上，只需左乘以下矩阵
$$
\boldsymbol M_{view} =\left( \begin{array}{c}
{\rm width}/2 & 0 & 0 & {\rm width}/2\
0 & {\rm height/2}& 0 & {\rm height/2}\
0 & 0 & 1 & 0\
0 & 9 & 0 & 1
\end{array} \right)
$$

Sampleing

三角形有诸多性质，包括任意多边形可以进行三角剖分，三角形一定是平面图，边界和内部容易用叉积判断，重心坐标插值简单；

三角光栅化就是考虑像素中心和三角形的位置关系‘

光栅化的最简单办法：采样(sampling)

采样可如下形式化定义：

1
for(int x = 0; x<xmax; ++x) output[x] = f(x);

采样的对象很多，包括一维的时间，二维的面积，方向，三维的体积；

对于屏幕内的任意一点(x,y),定义采样

函数以判断点是否在三角形内
$$
\rm inside(t,x,y) = \begin{cases}\rm
1&\rm Point(x,y)\ in\ Triangle\ t\
0&\rm Otherwise
\end{cases}
$$
那么采样过程可以理解为扫描整个屏幕上的像素点

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

image-20241207185400978

显然没有必要遍历整个屏幕，我们只需要考虑三角形的包围盒即可；

Sampling Artifacts

很显然，如果采样率过低，或者分辨率过低，就会产生锯齿(Jagies)问题，或者走样(Aliasing)现象;

假如说对一张图片，去掉一半的行，或者对着屏幕拍照，可能会有摩尔纹(Moire);

高速旋转的车轮可能看上去是倒转的(Wagon wheel effect);

抽象出这些现象的原因：信号变化太快但是采样太慢，用信号与系统的观点来看就是实际信号频率大于采样频率；

Blurring(Pre-Filtering) Before Sampling 是一个常见的反走样的技巧(Antialiasing idea);

但是反之(先采样再模糊)效果不好；

image-20241208144930773

DSP

在频域分析中，我们常用Fourier级数展开将几乎任意一种函数写成频率，振幅不同的波叠加
$$
f(x)=\frac{a_0}{2}+\sum_{n=1}^{\infty}a_n\cos n\omega x+b_n\sin n\omega x
$$

  • 直流分量：$\frac{a_0}{2}=\frac{1}{T}\int_{-T/2}^{T/2}f(x)dx$

  • 傅里叶系数：
    $$
    a_n=\frac{2}{T}\int_{-T/2}^{T/2}{f(x)\cos(n\omega x)dx}\
    b_n=\frac{2}{T}\int_{-T/2}^{T/2}{f(x)\sin(n\omega x)dx}
    $$

将周期信号$f(t)$推广成有限时间的非周期信号,也即时域从周期转化为非周期时，频域从离散的转化为连续的：原始的Fourier变换（FT）及其逆变换,其作用可以将函数从时域变换成频域；
$$
F(\omega)=\int_{-\infty}^{\infty}f(t)e^{-i\omega x}dx\
f(x)=\frac{1}{2\pi}\int_{-\infty}^{\infty}F(\omega)e^{i\omega x}d\omega
$$
我们分离出这些信号波，并用同一种方法采样，如下图

image-20241208150318558

可以看到，如果采样频率很低，跟不上信号本身的频率，那么采样就难以恢复出原来的信号；

image-20241208150436078

同样的采样函数，采样完全不同的信号函数得出一样的结果，仅凭结果无法区分两个信号，这样的现象称为走样(aliases);

对于一张图像来说，我们常用如下的2DFT,先要将图像转化成灰度图，然后将这张图片看作上下左右循环重复的大图；

2DFT将原始的灰度图像$I(x,y)$，转化成其频域图$F(u,v)$
$$
F(u,v)=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}f(x,y)e^{-i2\pi(ux+vy)}dxdy\
f(x,y)=\frac{1}{2\pi}\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}F(u,v)e^{i2\pi (ux+vy)}dxdy
$$
在图像的边界涉及重复图像的切换，所以变化应该很明显，频域图蕴含信息较多，因此需要中心化；

中心的区域定义为高频区，信息较多；对于非中心的区域为低频区，信息较少；

以下是一张图及其对应频域图(频谱)

image-20241208153535998

Filtering

滤波的含义是对于删去函数频域上特定频率大小的子波；

我们对图像作高通滤波(High-pass filter),保留频率高的信号，得到图像的轮廓，轮廓蕴含的信息较多，这也是符合直觉的；

image-20241208153740024

反之，我们将图片通过一个低通滤波器，得到其模糊图像，也就是边界的概念几乎消失；

image-20241208153829837

某种观点上看，滤波(Filtering)=卷积(convolution)=平均(averaging);

image-20241208154307669

Convolution Theorem

空间域中的卷积等于频域中的乘法，反之亦然;

可以看到，对一张图像，我们先作2DFT将图像转化成其频谱，对频谱应用卷积核，其本质为是将某一像素的频率用周围像素的加权平均代替，形成新的频谱，这就完成了滤波过程，将新的频谱应用2DIFT，得到滤波处理后的图像，表现为原图像的模糊；

image-20241208155056788

不同卷积核的滤波效果：

  • 更大的卷积核，对应更大范围的像素平均代替原来像素，更新后像素差异变小，处理后图像越模糊，对应低通滤波
  • 更小的卷积核对应高通滤波

对于采样的过程可数学形式化如下：

将连续信号$f(x)$采样，采样时间点间隔为$T_s$,冲击序列为
$$
\delta_s(x)=\sum_{n=-\infty}^{\infty}\delta(x-nT_s)
$$
取样信号为
$$
f_s(x)=\sum_{n=-\infty}^{\infty}f(x)\delta(x-nT_s)
$$
其频谱密度为
$$
F_s(\omega)=\int_{-\infty}^{\infty}f_s(x)e^{-i\omega x}dx\
=\sum_{n=-\infty}^{\infty}\int_{-\infty}^{\infty}f(x)\delta(x-nT_s)e^{-i\omega x}dx\
=\sum_{n=-\infty}^{\infty}f(nT_s)e^{-i\omega nT_s}
$$
image-20241208160358803

时域上的卷积等价于频域上的乘积，理解上图发现：采样本质上是对频域内容的重复；

我们在频域上重新理解走样，假设原本的信号频谱，每$F_s$重复一次；

若采样速度过慢，反映在频谱上重复越频繁，重复间隔变小，就会出现不同频率成分的混合，发生走样现象；

image-20241208160720284

Antialiasing idea

Increase Sampling Rate

提高显示器的分辨率，或者传感器的采样率是终极解决办法，从根本上避免频谱重叠问题；

但是受限于实际条件无法更换，或者成本高昂，可能无法做到；

Pre-blur before Sampling

先对图像/信号的高频信息通过低通滤波器删除掉，也即对图像/信号变模糊，再以原本稀疏的采样率采样，处理后的信号/图像的频率间隔变窄，采样重复也不会发生重叠现象；

image-20241208161738648

image-20241208161753146

模糊操作先前提到，本质上是应用卷积核；

在光栅化三角形时，经过模糊后，定义像素内平均值inside(t,x,y)为三角形覆盖像素的面积

模糊效果如下

image-20241208161850156

Multiple Sampling Anti Aliasing(MSAA)

多重采样抗锯齿(MSAA)算法是对上述算法的近似，是一种在计算机图形学中广泛使用的抗锯齿技术。它主要用于解决图形渲染时产生的边缘锯齿问题，使得图像边界更加平滑，更加贴近真实视觉效果。

思想：通过对像素内的多个位置进行采样并平均其值，来近似像素框滤镜的效果

  1. 在每个像素中采集 NxN 样本

    image-20241208162707054

  2. 平均每个像素“内部”的 NxN 样本

    image-20241208162721846

  3. 对每个涉及像素，用tradeoff值替代，而不是二元值0-1

    image-20241208162841499

缺点是计算开销大，一般可能采用更先进的算法，比如复用邻近像素

其他抗锯齿方案：

  • TXAA（Temporal Anti-Aliasing）：TXAA 是一种基于时间的抗锯齿技术，通过在多个帧之间进行颜色混合来消除锯齿。它结合了空间和时间上的信息，效果更好，但实现复杂且性能开销较大
  • FXAA(Fast Approximate AA):采样无关算法，是图像后期处理消除锯齿

Super resolution / super sampling

  • From low resolution to high resolution
  • Essentially still “not enough samples” problem
  • DLSS (Deep Learning Super Sampling）