Skip to main content

三角形设置

October 8, 2020About 17 minGraphic

三角形设置

我们进行了投影和转换之后就会获得一个标准立方体[-1，1]的3次方。 然后把这个立方体投射到屏幕上。最后我们需要把这个影像与我们的屏幕做成一个映射关系，把图像在屏幕上显示出来。

屏幕定义

我们需要要把图像显示在屏幕上，那什么是屏幕呢？地球人都知道是显示器。那我们的电脑是怎么去定义我们的显示器呢？

屏幕就是一个二维数组的像素组成，数组长度是分辨率。我们定义屏幕的几何表示如下图。

左下角为原点(0，0)，每个像素的长宽为1。因为每个像素的中心并不是该像素的坐标，从图中可以看出像素中心为(x+0.5，y+0.5)。例如蓝色像素的坐标为(2.5，1.5)。

这里的像素就是一个格子。这个格子中显示什么颜色，然后所有格子组合起来就可以形成一个图像。如下图：

我们把一个横排像素个数与一个竖排像素个数相乘就是我们常常听说的分辨率。

用程序表达一个像素除了上面的位置信息以外还有颜色信息。我们知道三原色（红、黄、蓝）可以合成几乎所有的颜色，所以在计算机中使用三个浮点数来存储，叫做RGB。我们经常会看到白色可以表示为：

  • (1，1，1)
  • (255，255，255)

这里的255表示每一个浮点数的容量为8-bit，可想而知如果每个浮点数的容量都变大到16-bit或者32-bit那么他可以存放的数据精度就更加的高，更直观的感受就是他画面中的细节更多，颜色更细腻。我们经常把存储大容量的数据的图片叫HDR(dhigh dynamic range)。有的时候会多一个alpha通道，所以叫做 RGBA。

三角形的离散化

我们明白屏幕是什么了，然后就是向屏幕中的像素填充颜色，那么我们怎么去判断说这个像素是什么颜色，是否有颜色呢？这里我们使用了把需要渲染出来的图像三角形化，就是把图像分割为无数个三角形。比如把这个头的模型划分成很多个三角形：

为什么要是用三角形呢？

  • 是最基础的多边形，可以组合其他多边形
  • 形成的面在一个平面上
  • 内外清晰分明
  • 三个点的插值可以覆盖整个三角形

然后把这图像平铺到屏幕上，如下图，红色网格就是屏幕像素：

我们的目的是为每一个像素填上颜色，这个颜色我们可以根据三角形面上的颜色是什么，从而对应到像素上是什么颜色。这里就产生了两个问题：

  1. 我们怎么判断一个像素是否在三角形中？

    解决：这里我们就使用像素坐标点与三角形做判断，具体可看之前三角形模块中的一个点是否在三角形中？

  2. 三角形的颜色是怎么确定？

    解决：我们使用三角形的顶点来存储颜色信息，再求得三角形的重心，以此对三个顶点的颜色做插值，最后得到整个三角形的颜色。同样在之前三角形模块中描述了三角的重心计算方式

Tips

当我们的像素坐标点刚好在一个三角形的边界上，那么这个像素是否被认定为被三角形覆盖，这个问题在不同的地方有不同的解决方案。我们也可以自定义规则，没有一个准确的规则。

这里我们就可以的为每一个三角形内的像素填色的伪代码

function rasterize_triangle(t)
    for Xmin to Xmax do
        for Ymin to Ymax do
            if is_in_trangle(t，x，y) then
                r，g，b = compute_barycentric(x，y，t)
                draw_color(r，g，b)

这里我们检测每一个三角形都需要遍历整个屏幕像素，是不是就没有很大的必要这样，有可能很多像素并没有被当前三角形覆盖，

我们可以对三角形做一个包围盒，求出最小x，最小y，最大x，最大y，然后就从最小x开始遍历而不是屏幕最小x坐标开始遍历。最终伪代码差不多就是这样：

function rasterize_triangle(t)
    Xmin = min(t)
    Ymin = min(t)
    Xmax = max(t)
    Ymax = max(t)
    for Xmin 
    to Xmax do
        for Ymin to Ymax do
            if is_in_trangle(t，x，y) then
                r，g，b = compute_barycentric(x，y，t)
                draw_color(r，g，b)

采样

我们这个时候已经可以把图片渲染到屏幕上了，把一个一个的像素的颜色填上去就可以了，我们逐个像素渲染出来就是这样：

这里跟我们想象中的模样不一样，我们想要的效果是：

这种情况就是叫做锯齿（aliasing）。我们需要解决这个问题，就先要说到采样。判断像素点是否在三角形内，然后采取在三角形内的像素块，这个过程就是采样。

在百度百科解释采样是指用每隔一定时间的信号样值序列来代替原来在时间上连续的信号，也就是在时间上将模拟信号离散化。简单的说就是把一个状态记录下来，然后把这个记录集中展示出来。

但是采样出现下面这几个问题（Sampling Artifact） ：

  • Jaggies 锯齿 - 采样的间距
  • Moire 摩尔纹 - 采样不足
  • Wagon wheel effect 轮子反转 - 采样的时间

造成这些问题的原因是信号变化的太快但是采样很慢，采样就跟不上信号的变化。

举个例子，我们使用一个sin的波形图来看看，上面的采样点多一些，可以清晰的描绘出来sin的波形。

我们看下面，采样点少一些，把点用线连起来就不是我们想要的波形。我们直观看到的点少点多，经上面定义说，我们是每隔一段时间记录，换言之就是上面的采样频率要高一些，也就是隔的时间短一些。

换个方向理解，我们如果分别采样下图中的蓝色线和虚线，这样我们得到的采样点都是一样，那么是无法区别这两种波形。这就是造成走样的原因。

走样

那需要怎么去解决这个问题呢？这里先把图片做一个模糊，然后对其做采样：

这样我们的边缘部分是不是就没有那么突变颜色了，就可以减少锯齿感。

这样子看是不是就会比上面的锯齿感不是那么的明显了呢。

那又怎么去做一个图片的模糊呢？这里使用到了 卷积（Convolution） ，
他的原理就是把两个函数合成一个，从图像的方向理解就是把两个波形合成一个波形，通俗的说法就是当你要计算一个点A的数据的时候，给你一个框，用这个框去框住点A周围的点，最后把这些点做一个合成计算得到新的点A′。我们把这个框叫做 滤波，滤波就可以认为是把一部分东西去掉。

这个合成的规则我们使用一个例子来说明：

a 为一个原函数，一个基础波形。b 为一个滤波（Filter）函数。下面的图为 a 与 b 的卷积结果，计算过程：

  1. 我们假设求 a[i] 卷积后的结果 a★b[i]
  2. 根据上图花括号框住的对应关系，可以写出式子：（a[i-2] * 1 + a[i-1] * 4 + a[i] * 6 + a[i+1] * 4 + a[i+2] * 1） * 1/16
  3. 也就是把两两对应的数值相乘然后平均，因为 b 中只有中间一部分为非零，所以不需要写出来。

这个滤波器的合成计算规则就像是给需要计算的数据做一个加权平均，我们可以把这个总结成公式：

Tips

公式中没有求平均，因为我们的过滤器所有的权重（值）加上的和为1。

公式中的 r 就是为我们滤波器的范围，上图中的 r 为2，这里 b[0] 对应的就是 a[i]

一个简单的伪代码：

function convolve(sequence a， filter b， int i)
  s = 0
  r = b.radius
  for j = i − r to i + r do
    s = s + a[j]b[i − j]
    return s

上面的例子只是对应了一维的变换，也就是波形中y坐标的改变。我们需要对图片做卷积，那就是二维的，这里我们就会用到卷积核的一个东西，就是滤波器为一个矩形，如下图：

我们求一个点 a[i,j] 与数组 b 的卷积，b 就是一个卷积核，把这个矩形的中心 b[0,0] 放在 a[i,j] 上，然后把卷积核覆盖在 a 中对应的点分别乘上对应数组 b 中的值，把所有乘积就相加即可获得该点的卷积。 公式如：

简单的伪代码如下：

function convolve2d(sequence2d a， filter2d b， int i， int j)
  s = 0
  r = b.radius
  for i′ = i − r to i + r do
    for j′ = j − r to j + r do
      s = s + a[i′][j′]b[i − i′][j − j′]
  return s

换个方向理解就是图片的模糊就是把一个像素与它周围的一些像素值按照一定的比例融合。
一些常见滤波器：

box filter

是一个分段常函数，他的积分等于1。他的默认滤波半径为 r = ½ 。分为两种离散和连续：

离散的公式：

连续的公式：

tent filter

也是一个常数分段函数。他的默认滤波半径为 r = 1 。图示：

公式：
gaussian filter

是一种常用的滤波器，它可以使采样更加的丝滑。

高斯滤波是没有默认滤波半径，他是通过σ这个参数来控制效果。公式：

cubic filter
  • b-spline cubic filter
  • catmull-room cubic filter
  • mitchell-netravali cubic filter

这个滤波器分为4段，

公式为：

采样原理

我们知道使用模糊可以解决这个走样的问题，但是为什么就解决了呢？我们可以从频率的方向来理解。采样是每隔一段时间记录一段信号，最后把这些信号连续起来。之前我们说到造成锯齿的原因是信号量变化太快了，使用的间隔时间跟不上这个变化，这个间隔时间就是频率。我们可以把一张图片转化为频率图。就要使用到 傅里叶变换。

傅里叶变换就是任何公式都可以写成正弦和余弦函数的组合。从图像上理解就是多个正弦波和余弦波叠加成最后公式的图像。如下图：

转换公式：

逆转换公式：

也就是说傅里叶变换是可逆的，可以一个波形分解成多个波形，也可以用多个波形组成原来的那个波形。这里我们可以使用傅里叶变换把图片的信号数据转换到频率数据。

我们可以把右边的图分为：

  • 低频区：中心亮白色的地方
  • 高频区：中心外围有很多白色黑色交替的地方

这里的高频低频是使用颜色变化的多少来判断的。我们尝试来去掉频率图中的一些部分，然后使用逆傅里叶变换，获得图像的图：

  • 去掉低频的部分：

左边的图我们只能看出一些轮廓，那是否就说明 高频部分就是表示的图像的边缘部分。

  • 去掉高频的部分：

左边的图像变得模糊了，根据上面的我们知道高频部分表示的图像的边缘部分，我们去掉了高频部分，所以就没有边缘了，看起来就有模糊的感觉。

  • 去掉部分高频与低频的部分：

从上面可以看出想要达到使图片模糊的效果就是去掉图片中的高频部分，上面说到滤波的功能就是过滤掉部分原波形的数据。这个是不是就对应上关系了，正如下图：

  • 上面的图片是在空间领域使用卷积，得到一个模糊的结果。
  • 下面的图片是先使用傅里叶变换获得频率图，然后使用一个低频滤波，得到过滤后的频率图，最后再使用逆傅里叶转换回去，得到模糊的结果。

现在我们已经明白一个图片转换成频率图后，其中高频代表了什么，低频代表了什么。如果要去掉一部分频率，可以直接使用图片的数据乘上一个滤波。那我们接下来看采样在频率领域是怎么表示的。

  • 左边：给你一个函数a乘上函数c（冲激函数），就可以得到函数e。也可以理解为使用函数c来采样出函数a。
  • 右边：b为函数a的频率图，d为函数c的频率图，f为e的频率图。

从这里我们就可以得到一个结论：采样是重复频率上的内容。我们可以看到f图中重复了很多个b。如果重复的这个间距很近以至于到两个b函数右重合，就会想下图一样：

这样会产生出 走样 ，回想上面说到走样锯齿的产生就是信号的变化过快，我们看上面那个函数图中的c和f，他们每两个脉冲（箭头）的间隔，就可以理解为我们采样的频率。我们采样的频率是一定的，信号变化突然加速，这样就会产生上图中下面的那个情况。

我们要解决这个交叉的问题：

  • 提高采样的频率，让信号的变化一直低于采样频率
  • 把交叉部分使用滤波直接给砍掉就可以了，过滤掉那一部分的频率即可，如下图：

抗锯齿

锯齿的产生是由于采样率不足，那么我们可以通过以下方式来时进行抗锯齿：

  • 提高采样率
    这是一种终极解决方法，如果 640x480 分辨率的屏幕换成 1920x1080 分辨率的屏幕，像素变小了，相当于提高了采样率，但这并不现实，我们需要的是在同一块屏幕实现抗锯齿的方法。

  • 反走样
    从上面的例子可以知道，我们可以先对图像进行一次模糊操作，在进行采样就可以实现抗锯齿。

    在频率上，这种操作相当于先用低通滤波把高频信息过滤掉，再进行采样。这里用的低通滤波就是利用 卷积 求出当前像素和周围像素的平均值。

    对于同一个像素，我们知道它原来有多少地方被覆盖了，这时候如果可以先算出覆盖比例，那么我们就可以根据这个比例对像素进行填充了。

如上图所示： 我们可以用肉眼看出四个像素分别被覆盖了12.5%、50%、87.5%、100%，但屏幕在填充像素是不能只填充一部分的，只能填充一整个像素。因此这时候可以对像素进行一次平均，最后得到像素的颜色。

超采样（MSAA）

事实上，刚刚提到的计算像素覆面积的做法是很难实现的。但我们可以通过超采样的方式来模拟。

所谓的超采样就是在一个像素里面放多个采样点来检测三角形是否有被覆盖。

上图表示一个像素里面包含了16个采样点，每个采样点采样后再把结果平均起来，最后就能得到三角形对改像素覆盖程度的 近似值。

如果想要更准确的近似值得的话，可以用更多的采样点，但这样计算量就会更大。

接下来看看实际例子：

上图中一个像素里面只有一个采样点。就有部分像素存在模棱两可的情况。

超采样的第一步是要为每个像素增加采样点，这里让每个像素有4个采样：

接下来是对每个像素中的所有采样点的结果进行平均：

最后就能得到平均后的结果：

对于 MSAA ，我们需要早知道如下几点：

  • MSAA 是对抗锯齿操作的第一步，也就是模糊操作（求平均）
  • MSAA 增加采样点，并不是为了提高采样率（分辨率没有提高），而是为了得到一个更合理的三角形覆盖率。
  • MSAA 的代价是计算量大增，如果一个像素里面有4个采样点，那么计算量就打了4倍，如果一个像素里面有16个采样点，那么计算量就大了16倍。（事实上，工业界会复用、优化这些采样点，因此计算量并没有增加理论上那么多）

画家算法

当我们要在屏幕上绘制物体的时候，会涉及到物体与物体的遮挡问题。最常见的做法是像画家绘画那样，先绘制远处的物体，再绘制近处的物体。

画家算法要求我们先在深度上进行一次排序（需要 nlogn 的时间），然后再进行绘制。但有些情况是无法通过画家算法来解决的，如下图：

上图中，无论怎么排序，都无法得到上图的结果。

深度缓冲（Z-Buffer）

深度缓冲用来记录每个像素的最小深度。

他的工作原理是：每次渲染的时候除了生成最终的图像之外，还生成一张深度图，该深度图记录了每个像素当前的最小深度。

具体实现步骤如下：

  1. 初始化像素的深度为∞
  2. 在光栅化工程中，不断更新其深度：
for (each triangle T)
  for (each sample(x,y,z) in T)
    if (z < zbuffer[x,y]) 
    {
        framebuffer[x,y] = rgb;
        zbuffer[x,y] = z;
    }

对于 n 个三角形，要得到某个像素的最小深度值，我们只需要便利所有三角形即可，因此其复杂度为 O(n)。

深度缓冲还有以下的好处：

  • 绘制三角形的顺序不影响最终结果
  • 所有 GPU 都支持深度测试

需要注意的是 ： 深度缓冲不能处理透明物体