GAMES101-Note2-Rasterization

对应Games101 lesson4-7

Posted by Tao on Monday, February 7, 2022

经过上一节我们将所有的物体都映射到了一个\([-1,1]^3\)的立方体里,那么下一步我们该怎么办?下一步就是将这些物体画在屏幕上,这一步就叫做光栅化 (Rasterization)

Canonical Cube to Screen

屏幕的定义

既然要画在屏幕上就需要把屏幕的概念定义好:

  • 它是一个包含像素(pixels)数组(array)
  • 数组的尺寸:分辨率(resolution),例如\(1920 \times 1080p\)
  • 屏幕是一个典型的光栅成像设备

Raster在德语里就是screen,光栅化Rasterize == drawing onto the screen

像素pixel是"picture element"的简写,在这里我们定义一个像素是一个颜色均匀的小正方形,它包含\((red,green,blue)\)三个值。

屏幕空间

屏幕空间就是在屏幕上建立一个坐标系,约定俗成地,以左下角为原点\((0,0)\),向右为\(X\),向上为\(Y\),因此任何屏幕上的点都可以用来表示。

  • 每一个像素的坐标都是用\((x,y)\)来表达,这里的\(x\)和\(y\)均为整数。例如图中蓝色的像素为\((2,1)\)
  • 如果我们定义屏幕的分辨率为\(width \times height\),则所有的像素的坐标的范围为从\((0,0)\)到\((width-1,height-1)\)
  • 像素\((x,y)\)的中心点位于\((x+0.5,y+0.5)\)。例如蓝色像素的中心为\((2.5,1.5)\)
  • 整个屏幕覆盖的范围为从\((0,0)\)到\((width,height)\)

因此为了完成\([-1,1]^3\)的立方体映射到屏幕这一操作,我们需要将物体的\(z\)坐标移去,将\(xy\)平面上的\([-1,1]^2\)变换到\([0,width] \times [0,height]\)。我们只需将宽度和高度都除以2,然后再将它的中心从\((0,0)\)移动到屏幕空间左下角,也就是移动宽度除以2和高度除以2的距离。视口变换的表达式如下:

$$M_{viewport} = \begin{bmatrix} \frac{width}{2} & 0 & 0 & \frac{width}{2} \\ 0 & \frac{height}{2} & 0 & \frac{height}{2} \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

到这一步时,我们已经得到平面上的图,三维空间中的网格模型经过以上变换,变成了屏幕空间中的多边形,我们需要把这些多边形进一步“打碎”,打成像素,变成每一个像素上的颜色值,这就是我们所说的光栅化。

Triangle Meshes

为什么选用三角形网格?

  • 它是最基本的多边形
  • 任何多边形都可以被拆分成多个三角形

三角形网格的独特性质

  • 三角形一定是平面图形。三点共面
  • 三角形的内外定义清晰。可以通过向量叉积来定义一个点在三角形内还是三角形外
  • 面内插值方便。只要定义三角形三个顶点不同的属性,就可在三角形内部做这个属性的渐变效果,也就是说,通过三角形面内的一个点和其他点的位置关系,可以得到一个插值。(重心坐标插值方法)

三角形插值

通过屏幕上三个顶点坐标,可以知道一个三角形在屏幕中的位置,如左图所示。为了绘制出这个三角形,我们需要判断每个像素的中心点是否在三角形内部,这里介绍一个最简单的方法:采样。

采样

采样就是给定一个连续的函数,在不同的点处求它的函数值。也就是说,采样就是把一个连续的函数离散化的过程。

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

采样是一个非常重要的概念,在图形学里会涉及到各种各样的采样,我们可以采样时间、面积、方向、体积等等。我们这里说的采样,是指利用像素中心对屏幕空间进行采样,也就是说我们需要求出某一个函数在屏幕中不同的像素中心的值。

sample

我们这里的采样就是去判断每一个像素的中心是否在三角形的内部,因此我们可以定义出这个函数:

$$ inside(tri,x,y) = \begin{cases} 1 &\text{Point(x,y) in triangle t}\\ 0 &\text{Otherwise} \end{cases} \text{,x,y not necessarily integers} $$

Rasterization = Sampling A 2D Indicator Function

我们使用两个for循环来遍历所有的像素,对每一个像素执行采样方法即可完成光栅化的过程:

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);

那么如何定义函数\(inside(tri,x,y)\)呢?也就是说我们需要去判断一个点是否在一个三角形内。我们可以用向量叉积的方法来判定,例如,如图所示,我们需要判断点\(Q\)是否在三角形\((P_0,P_1,P_2)\)内,我们需要执行如下过程(注意顶点顺序):

inside

  • 计算\(P_1P_2 \times P_1P_Q\),如果得到的向量的z值为正,则\(Q\)在向量\(P_1P_2\)的左侧,否则在右侧
  • 计算\(P_0P_1 \times P_0P_Q\),如果得到的向量的z值为正,则\(Q\)在向量\(P_0P_1\)的左侧,否则在右侧
  • 计算\(P_2P_0 \times P_2P_Q\),如果得到的向量的z值为正,则\(Q\)在向量\(P_2P_0\)的左侧,否则在右侧

当三个叉积向量全部为正或负(同号)时,该点在三角形内部。

in both tri

这里可能会有一种情况,刚好点在三角形边界上时该如何判断?要么不做处理,要么特殊处理。即点到底在三角形\(1\)还是三角形\(2\)上,可以自己定义标准,可以定义点既在\(1\)又在\(2\)上,也可以定义点不在这两个三角形上。

aabb

上面我们提到了通过采样来进行光栅化的过程,那么我们想,我们已经写了一个二重循环,也就是说考虑一个三角形的光栅化就需要将所有的像素都跑一遍,其实是没必要。一个三角形其实只能覆盖一个相对较小的区域,比如图中左边第一列根本不在蓝色的区域,就不可能碰到三角形,也就根本不用去考虑这些像素。蓝色的区域我们称为三角形的包围盒(Bounding Box),更严格地说是一个轴向包围盒(Axis Aligned Bounding Box,AABB)。求三角形的包围盒非常简单,只需要使用三个点最小和最大的x值和y值来构造一个区域。这样只有当这个三角形很窄长并且旋转45度左右的时候,才会用一个很大的Bounding Box来包住,此时效率最低。

还有一种方法是将三角形覆盖的区域中,每一行都去找它的最左和最右,这样的话一个多余的像素都不会多考虑。

aabb2

aliasing

经过以上操作,我们得到了如图所示结果,我们会发现这个结果不太对,因为它有锯齿(Jaggies),这是因为我们的采样率对信号来说是不够高的,所以产生了走样(Aliasing)。因此我们要使用抗锯齿(也称反走样)技术来进一步优化。

反走样 (Antialiasing)

我们用每一个像素的中心去检测是否在三角形内,然后把对应的像素涂上颜色,我们最后绘制出来的图案就是带有锯齿的图像。事实上我们不希望有锯齿,因此我们需要抗锯齿和反走样。锯齿的学名叫走样(Aliasing)反走样就称为Antialiasing

采样理论

前面有提到,采样是在图形学中广泛存在的一个做法。光栅化的过程其实就是在屏幕空间离散的点上进行是否在三角形内的采样。对于任何一个我们拍出来的照片,放大后就会发现很多格子,也就是像素,这也是我们表示图像的基本方法。一副照片其实就是所有到达感光元件的光学信息,通过把它离散成图像像素的过程,其实也是采样。采样不光可以发生在不同的位置,也可以发生在不同的时间,视频就是在时间中进行采样。因此采样是广泛存在的,同样,采样所产生的问题也是广泛存在的。

Sampling Artifacts in Computer Graphics

采样所产生的错误(或称瑕疵)称为Artifacts。 因为采样所产生的问题有:

  • 锯齿问题 (Jaggies) - sampling in space
  • 摩尔纹问题 (Moire) - undersampling images
  • 车轮效应 (Wagon wheel effect) - sampling in time
  • Many more… 采样产生问题的本质其实是信号变化过快导致采样速度跟不上。因此我们要通过频率来分析它。

Antialiasing Idea: Blurring (Pre-Filtering) Before Sampling

如何进行反走样,答案是在采样之前先做模糊(或滤波)。之前我们采样会发现,有些点完全在三角形内,有些点完全在三角形外,因此这些点要么是红的要么是白的。

anti-aliasing

但是如果我们在拿到一个三角形后,先做一个模糊操作,把它变成一个模糊的三角形,然后再去用像素中心点采样,这样就可以解决锯齿问题,得到下图效果。

anti-aliasing2 anti-aliasing3

举个例子,上图中,左图为抗锯齿操作之前,右图为抗锯齿操作之后。但是,先采样再模糊是不行的。下图是效果对比:左图是先采样再模糊,右图是先模糊再走样。先采样再模糊的操作称为Blurred Aliasing,先模糊再采样的操作称为反走样 Antialiasing

Blurred Aliasing

那么,为什么采样速度跟不上信号变化的速度就会产生走样?为什么要先做采样再做模糊达不到反走样的效果呢?为了弄清楚这些事我们需要了解频域Frequency Domain方面的知识

Frequency Domain

我们来看最简单的波:sines and cosines。通过调整\(x\)前面的系数,例如\(2\pi x\)和\(4\pi x\),我们能得到不同的余弦波,它们的不同在于频率不同,我们定义\(\cos2 \pi fx\),其中\(f\)为频率,因此\(\cos4\pi x\)的频率\(f=2\),因此我们可以用频率\(f\)来定义余弦波的变化有多快。同样道理,我们还可以定义它的周期\(f=\frac{1}{T}\),通俗地讲,所谓周期就是每隔多少\(x\),函数会重复自己一次,例如\(\cos2\pi x\)每隔\(1\)会重复一次,\(\cos4\pi x\)每隔\(0.5\)会重复一次。因此周期是频率的倒数。

frequency

那么为什么我们要介绍周期和频率呢?因为傅里叶变换(Fourier Transform)会用到它们。微积分里面有一个概念是函数展开,其中一个就是傅里叶级数展开

傅里叶级数展开就是说,对于任何一个周期函数,都可以把它写成一系列正弦和余弦函数的线性组合以及一个常数项

frequency2

这样我们就可以把一个函数描述成很多不同的正弦余弦项的和。这说明傅里叶级数展开和傅里叶变换是紧密相连的。给定任何一个函数,我都可以经过一个复杂的操作变成另外一个函数,也可以把变换后的函数通过逆变换变回原来的函数,这样的操作就称为傅里叶变换和逆傅里叶变换。

frequency3

不同的函数都有着不同的频率,仔细上图傅里叶级数展开的中\(\omega\)的系数分别为\(3t,5t,7t,…\)这些值都代表了不同的频率,也就是说通过傅里叶级数展开可以将任何一个周期性函数分解为不同的频率。所谓傅里叶变换其实就是把函数变成不同的频率的段,并且把这些不同频率的段显示出来。

举个例子,如下图所示,通过傅里叶变换我们得到了这5个不同的函数,我们知道这些函数都含有不同的频率,假设我们对这些函数进行一次相同间隔的采样我们会发现如下结果

frequency4

从\(f_1\)到\(f_5\)会发现,\(f_5\)的采样效果非常差。这也就是说通过频率分析,我们可以体会到,对于一个函数来说,它本身有一定的频率,采样也有一定的频率,但是如果我们采样的频率很低而函数本身的频率很高,就会跟不上它的变化,就没有办法将原始的信号拟合出来。

frequency5

再看一个例子,蓝色线是函数本身,黑色线为采样得到的函数。现在如果我们把黑色线看作是另一函数,我们发现,如果我们用同样的一个采样方法采样两种截然不同的信号,我们会得到完全相同的结果。即采样频率相差很多的蓝色的函数和黑色的函数所得到的结果完全相同。这一现象就称为“走样”。

Filtering

现在我们知道了走样的定义,也知道了傅里叶变换,那么就可以开始真正的分析一些函数倒底拥有怎样的频率。这里有一个重要的概念——滤波(Filtering),它就是把某个特定的频段去除。傅里叶变换可以帮助我们理解这个问题,它可以将函数从实域变到频域。如下图所示,左图是一个人的图像,也就是实域,我们将其作傅里叶变换,得到右图为频域。

frequency6

那么右边这幅图应该如何理解呢?中心是左边这张图最低频的区域,四周为高频区域,也就是说从中心到四周,其频率会越来越高。其亮度表达了左图在该频域的信息量。这张图就说明左图大多数的信息都是集中在低频上的,高频的信息相对于低频会少很多,实际上自然中所有的图片基本都是这样的。有人可能会问为什么图片中有一个十字,水平一条线、竖直一条线很明显。简单地说,这是因为在分析一个信号时它是一个周期重复的信号,对于没有周期重复的信号的话就将无限多个图像叠放,因为很少有图像左边界和右边界完全一致,不一致的情况下,我们把这个图像的左侧放到它的右侧,就会产生一个极高的高频,傅里叶变换就会产生这两条线,为了分析,我们暂时忽略这两条线。也就是说,傅里叶变换能够让我们看到这个图像在各个不同的频率的样子,我们称之为频谱

接着,如果我们使用滤波,去掉频域中心的内容,也就是去掉低频的内容,保留高频的区域,然后我们再使用逆傅里叶变换得到实域,就会得到如图所示结果。从图中我们可以看到,高频信息表示的其实就是图像内容上的边界。这样的滤波称为高通滤波(High-pass filter)。那么通常我们所说的边界其实就是指图像上的某一区域的周围发生了剧烈的变换,也就是所谓的边界,比如人的衣服和背景之间的色差,这样的信息就是高频信息,那么如果我们只显示高频的信息,得到的就是图片中各物体的边界。

frequency7

再反过来,将高频信息全部去除,只保留低频信息,得到如下图所示结果。我们会发现得到了一张相对模糊的图,绝大部分细节被去除了。这里就是应用了低通滤波器(Low-pass filter)。边界被去除了就会变得模糊。

frequency8

接下来,我们将高频和最低频信息都去除,保留中间频率的信息,得到下图所示结果。我们得到了不是很明显的边界特征,因为最明显的边界特征对应最高的频率。

frequency9

更多关于这方面的信息可以去了解一门课,叫《数字图像处理》,图形学中就不再过多赘述了。这是一个经典操作,现在更多的操作是通过机器学习来完成的。

Convolution Theorem

我们说滤波其实就是去掉特定频率的信息,从另外一个角度上看,滤波又等于卷积,或者平均,Filtering = Convolution ( = Averaging)。平均的概念比较好理解,低通滤波器就是将图片模糊,也就是一种平均操作。然后卷积是什么呢?

Convolution

如上图所示,对于一系列信号数组,滤波器就好像一个窗口,它可以左右移动,窗口的大小是3个格子,这其实是要做一个卷积Convolution操作。这是在说,在移动这个窗口的时候,窗口三个数所对应的信号的三个数做一个点积操作,如下图所示,最后将结果写回这个格子。对所有格子做这样的操作,就会得到新的数组。注意这里的卷积定义不是数学上的定义,是图形学简化的定义。

Convolution2

卷积理论:实域上如果要对两个信号进行卷积,其实,对应到两个信号各自的频域上,就是两个信号的频域的乘积。在实域上如果是对两个信号进行卷积,那就是频域上对其信号的乘积。通过这个理论我们可以直接对图进行一个卷积操作,也可以将这幅图先用傅里叶变换,变换到频域上,再把卷积的滤波器变到频域上,两者相乘,得到频域上的结果,再把它逆傅里叶变换变回实域,这两个操作是一样的。

Convolution3

我们对图片进行一个平均或者是卷积操作,即对任何一个像素,取它周围\(3×3\)个像素的平均,那么得到的结果就是一个模糊的图像。我也可以使用傅里叶变换的方法来做这样的操作,最后通过逆傅里叶变换变回这幅图。实域卷积=频域乘积,频域卷积=实域乘积。

再举一个例子,下左图为实域,右图为频域,如果左图中的方形变大了,频域会如何变换呢?

Convolution4

答案如下图所示,变小了。因为我们为了模糊一张图,用了一个\(3×3\)的卷积操作,如果我们换成一个\(21×21\)的方形做卷积,那么得到的结果会越来越模糊,也就更接近于低频。如果我们用一个很小的方形做卷积,那么对应频域的范围就会很大,也就能留下更高的频域,最后模糊的效果就会不明显。

Convolution5

从频率的角度看采样

下面我们再从频率的角度来看什么是采样。采样就是在重复频率或者说频域上的内容Sampling = Repeating Frequency Contents。

如上图所示,图\(a\)为某个连续的函数,其频域为图\(b\),假设我们要采样这个函数,就要取一系列离散的点,留下这些离散点的函数值。也就是让函数\(a\)去乘另外一个函数,这个函数只在一些固定的位置有值,其他地方没有值,也就是图\(c\),这样的函数称为冲击函数。我们令\(a\)函数乘\(c\)函数,得到的就是图\(e\)函数,这就是采样。也就是给定一个原始函数\(a\),我们乘上一个冲击函数就可以得到采样结果。在频域上,冲击函数的频域还是冲击函数,只不过间隔有所变化。我们记得实域的乘积对应到频域上是卷积,即\(b\)卷积\(d\),最后的结果就是将\(b\)重复了很多次。那也就是说,采样就是在重复原始信号的频谱。

所以,如果我们采样地不够快,原始信号重复的间隔就会非常小,意味着采样之间的距离很大,采样的越稀疏,频谱就越密集,频谱越密集,采样就越稀疏。如果频域上重复的时候叠在一起了,就发生了走样现象。所谓走样在频率图像上发生了混叠。

图形学中的反走样

增加采样率是终极解决办法,直接更换硬件来提高分辨率,例如用视网膜显示器来看图形,高分辨率意味着采样率高,意味着频谱与频谱之间的搬移间隔大,就不容易出现频谱的混叠。但是这并不是反走样要做的事情,反走样不会增加分辨率。

反走样操作:先模糊再采样。通过前面的讲解,我们知道先模糊再采样这一操作是有意义的。模糊就是用低通滤波将高频信息拿掉,然后再采样。

为什么这样是正确的?我们再看一个例子,一个函数的频谱就是如图所示的梯形,稀疏的采样就会发生频谱的混叠,产生走样。如果我们先做一个模糊,也就是把高频信号砍掉,也就是去掉虚线方块之外的信息,剩下的就是下图的信号。然后再采样,就不会发生混叠了。

在实际的操作中,我们用什么样的方法来对图像进行模糊呢?用一个一定大小的低通滤波器来进行卷积。最简单的块就是一个像素,一个像素就是一个box filter。因此我们的解决方案为:

  • 原本的函数\(f(x,y)\),判定了一个三角形要么在三角形里要么在三角形外,这就是一个二值函数,我们用每一个像素对它进行一个卷积操作,也就是求一个平均,然后用平均值的中心采样(其实不需要采样,因为就一个像素对应一个box filter,就只有一个值)

对于任何一个像素,我们都能知道它可能被覆盖,我们对它的覆盖面积求平均,然后根据覆盖得多少赋值。

Antialiasing By Supersampling (MSAA)

那么我们如何把一个像素被三角形覆盖的区域算出来呢?实现并不容易,因此人们研究出一种近似算法,称为Antialiasing By Supersampling (MSAA),它是一个反走样的近似,并不能严格意义地解决反走样的问题。

MSAA

算法是将每一个像素划分成许多小像素,每一个小像素有一个中心,我们可以判断这些点在三角形内,再将这些点平均起来,如果点足够多就能得到比较好的结果。其实就是在一个像素内部增加采样点。例如一个像素里,如果4个采样点都不在三角形内,就判定它不在三角形内,如果有一个采样点在三角形内,覆盖率就为\(25\%\),如果三个点在,覆盖率就为\(75\%\)。通过这样的方法就能实现抗锯齿的效果。

MSAA2

MSAA3

因此MSAA解决的是对信号的模糊的操作,而下一步采样的操作被隐含在这一步里了。MSAA不是靠提升分辨率和采样率来直接解决走样问题。

通过MSAA,我们得到了一个不错的反走样效果,但是为了引入MSAA,我们牺牲了什么?很显然,我们使用了更多的点来测试是否在三角形内,也就是增大了计算量。因为这些点只是为了检测三角形的覆盖而已,却要付出很多倍的计算量。为了减少计算量,在工业界上不会规则地划分成均匀的4个点,而会用一些分布不均的点来使很多样本得到复用。

FXAA和TAA

其他的具有里程碑意义的方法有:FXAA (Fast Approximate AA) 和TAA (Temporal AA)。FXAA是图像的后期处理方法,先把有锯齿的图得到,再通过一种操作把锯齿消掉。但是如果先得到锯齿的图,再做模糊操作是不对的,FXAA是通过图像匹配的方法找到边界然后替换成没有锯齿的边界,效率非常高。TAA方法是最近几年兴起的方法,它可以寻找上一帧的信息,用像素内的一个点没有做MSAA来感知,假如我们看到的是静止的场景,相邻两帧看到的信息一样,那么我们可以用不同位置上的点来感知覆盖信息,那么大家会发现在时间范围内,得到的边界会各不相同。TAA是复用上一帧得到的像素的值,相当于将MSAA的样本分布在时间上,这样就没有引入任何额外的操作,这是一个非常聪明的作法,对于运动物体,我们会在后面的实时光线追踪继续讲解。

超分辨率问题

如果我们有一张\(512×512\)的图,我们想将其放大至\(1024×1024\),但是我们又不想看到锯齿,就也要解决样本不足的问题,因此超分辨率问题和反走样问题是非常相似的。有效的做法是DLSS(Deep Learning Super Sampling),利用深度学习来解决。

Z-Bufferring

众所周知,空间中会有好多三角形,三角形各自离相机的距离也不一样,那么我们该如何将这些三角形画在屏幕上并且它们的遮挡关系是对的呢?近处的永远要遮挡远处的。在这里我们使用的方法就是深度缓存(Z-Buffering)

Painter’s Algorithm

场景中有很多不同的物体,既然要把这些物体放在屏幕上就要涉及到顺序的问题,以保证这张图是对的。一个比较直观的方法是像画水粉、油画一样,先把最远的物体绘制出来,再把近的物体覆盖在远的物体上,层层叠加来形成最终的结果。

Painter&rsquo;s_algorithm

画家先画远处的山,再画近处的草地,最后再在草地上画上树。这样由远及近地对物体做光栅化的算法就称之为画家算法(Painter’s Algortihm)。例如如果我们画一个立方体,可以先画远景的山,然后再画中景的草地,最后绘制最前方的三角面,这样就能出正确的结果。但是仔细思考会发现,如果绘制的顺序必须要非常严格,如果错了会造成多余的线被绘制。因此在一定程度上说,这个算法是可以的,它要求对所有物体的深度进行排序,排序的复杂度为\(O(n logn)\)(对于\(n\)个三角形)。但是当三个空间三角形构成一组互承关系时,三个两两之间存在了覆盖关系,这样就没法定义它们之间的深度关系,也就无法对它们进行排序。因此为了解决这个问题,人们提出了Z-Buffer。

Painter&rsquo;s_algorithm2

Z-Buffer

在图形学里,人们广泛采用了Z-Buffer,引入了深度缓存的概念。这一算法其实就是避免空间中三角形的排序,它是从像素的角度来检测能看到的三角形,对于每一个像素去记录它所看见的最浅的深度的物体,也就是距离相机最近距离的物体。在图形学中,我们不光能渲染出最后的结果(Frame Buffer),在生成这个图像的同时,我们还能得到一个深度图(Depth Buffer)它记录了每个像素所看到的几何图形的最浅深度的信息。我们利用深度图来维护遮挡信息。

Depth buffer

在变换中,我们提到,我们始终假设相机是放在原点,并且看向\(-Z\),这样所有的点的\(Z\)坐标都是负的,并且它们越小,说明离得越远。为了方便理解,现在我们换一个概念,我们把它看作是点到摄像机的距离,这样\(Z\)就总是正的,那么\(Z\)值越小,物体越近。

如上图所示,假设对于有一个能看到框体的像素,它先记录了地板的深度,接着再记录物体的深度,如果物体的深度比地板要小,那么意味着这个物体要遮挡住地板,这个点就要画上看到物体的颜色,然后右侧的深度图也会做相应的更新。这一流程的伪代码如下:

// first step: initialize depth buffer to infinite
for (each triangle T)
  for(each sample (x,y,z) in T)
    if (z<zbuffer[x,y])              // closest sample so far
      framebuffer[x,y] = rgs;        // update color
      zbuffer[x,y] = z;              // update depth
    else
       ;                             // do nothing, this sample is occluded

Depth buffer2

注意:R为无限大的一个值。初始化时要把所有的像素定义为无限大(或者足够大的一个值)。

在使用画家算法时,我们要把所有的三角形做一次排序,这需要花费\(O(nlogn)\)的时间。而深度缓存,每个三角形都覆盖常数个像素的话,无非就是考虑每个三角形所覆盖的常数个数的像素,也就是\(O(n)\)的算法复杂度。它并没有进行排序,只是不断地更新结果,记录当前所看到的最小深度值,因此只花了线性的时间。

如果假设不会出现两个不同的三角形在同一个像素上有着相同的深度,因为深度缓存算法与顺序无关,所以不管通过什么顺序绘制三角形,最后的结果都会是相同的。在图形学中,我们都是用浮点型来表示的,浮点型和浮点型判断相等是非常困难的事,基本上可以认为两个浮点数是完全不会相同的。此外,这一算法可以应用在几乎所有的硬件中。

之前提到,为了做反走样,我们使用了MSAA算法,对一个像素取很多采样点,对于这些不同的采样点,如果我们要运用深度缓存,就要对每一个采样点检测它所能看到的深度,因此Z-Buffer还得考虑到它不是对每个像素记录深度,实际上是对每个采样点做记录。

「如果这篇文章对你有用,请随意打赏」

Heisenberg Blog

如果这篇文章对你有用,请随意打赏

使用微信扫描二维码完成支付


comments powered by Disqus