这节课稍微理论，显得枯燥一点，但对于理解整个图形渲染管线有帮助，调到前面来讲。

图形绘制流水线的基本实现策略

从高层视角来说，图形绘制接收输入，产生输出，具体来说：
以顶点和状态变量，即几何对象、属性和相机参数等作为输入，以位于帧缓存中的彩色像素阵列作为输出。

作为一个基本的图形系统，需要完成的任务有：

• 几何变化
• 裁剪
• 光照/明暗处理
• 隐藏面消除
• 图元光栅化

后面会讲述这些任务。
图形学的绘制流水线中，两个关键的要素就是几何图元和像素。根据选取的变量不同，图形绘制流水线分为两种实现策略：

• 基于对象空间的方法：
  对于每个对象，确定它所覆盖的像素，并用对象的状态确定像素亮度。缺点是无法处理全局运算，不能获得全局效果。

 for(each_object)   render(object);

• 基于图像空间的方法：
  对于每个像素，确定投影到这个像素的离观察者最近的那个对象，从而基于该对象计算像素的亮度
  优点：非常适合处理全局效果
  缺点：无法事先确定哪些图元影响哪些像素，每个的像素计算量较大

for(each_pixel)   render(pixel);

图形绘制系统的四个主要任务

四个任务是：

• 建模
• 几何处理
• 光栅化
• 片元处理
  

建模

建模一般有3种方法：

• 手工建模：像我们手工定义立方体的顶点、片元、法向量等信息，这就属于手工建模
• 三维扫描：可以理解为从全角度扫描实际模型，进行建模，看看B站的这个视频就可以理解了：三维扫描
• 程序建模：利用现代软件建立模型，各种导入导出，例如MagicaVoxel，MagicaVoxel使用教程┃EP.1┃基础教程

几何处理

这个阶段的目的主要是确定哪些几何对象要被显示，并把明暗值或者颜色值赋给顶点。它的4个处理过程是：

• 投影：模视转换、投影规范化
• 图元组装：把顶点组装成对象
• 裁剪：将位于视见体外的几何图元进行裁剪
• 明暗处理：模拟光照效果确定最终的着色

光栅化

基于顶点给出表示对象的一组像素就称为光栅化（rasterization）或者扫描转化（scan conversion），光栅化产生片元。同时，光栅化将归一化坐标转化为屏幕坐标：

片元处理

这个阶段的目的主要是综合多种因素，从光栅后得到的片元数据中确定最终的像素颜色。这个阶段包含了一些处理流程如：

• 纹理映射
• 隐藏面消除
• 透明
• 反走样

裁剪

目的：用来确定哪些图元的那些部分可能会出现在屏幕上，并且把没有被裁减掉的图元送入光栅化模块中

发生时机：裁剪处理可以发生在观察流水线的一个或多个地方；在OpenGL中，是用一个三维视见体对图元进行裁剪

裁剪这块我们重点掌握的是一些简单的裁剪算法。

二维线段的裁剪

对于平面上的直线，最直接的方法就是求出视景体和每一条二维直线的交点，只对交点以内的部分进行渲染。如下图：

但这样子做未免太过于低效，因为有些直线压根和视景体没有交点，求交点只是白白浪费了资源。Cohen-Sutherland算法可以一定程度上解决这个问题：

Cohen-Sutherland算法

• 算法思想：通过对端点编码的方式，尽可能不经过求交就消除许多情形
• 有4种情形：

  • 线段的两个端点都在四条直线内 处理策略：原样绘制直线

  • 两个端点都在直线外，而且在一条直线的同侧 处理策略：抛弃这条直线
    

  • 一个端点在内部，一个端点在外部 处理策略：必须进行至少一次求交

  • 都在外面 处理策略：必须进行至少一次求交
    

• 定义编码：延长四条边，把空间分成九个区域
  对于每个端点，定义一个编码
  

考虑一条线段，它的两个端点编码分别为o1=outcode(x1, y1) 和 o2=outcode(x2, y2)，我们可以根据这两个端点的编码情况进行讨论，分为四种情况：

• o1=o2=0： 线段的两个端点都位于裁剪窗口内部，需要将该线段送入光栅化模块进行光栅化处理
• o1不为0，o2等于0（或相反）： 线段的一个端点位于裁剪窗口之内，另一个端点位于裁剪窗口之外，需要对这样的线段进行裁剪处理
• o1 & o2 不为0： 通过对线段的两个端点编码进行按位与运算，可以确定这两个端点是否位于裁剪窗口某条裁剪边的同一侧，可以丢弃这条线段
• o1 & o2 为0： 线段的两个端点都位于裁剪窗口之外，但是它们分别位于裁剪窗口的两条不同裁剪边的外侧，仅仅从端点的编码无法区分是否应该丢弃该线段还是把该线段的一部分裁剪掉

以下面5条线段为例

AB 对应case #1：A编码为0000，B编码为0000，为可接受线段，整条送入流水线进行裁剪
CD 对应case #2：C编码为0000，D编码为0010，编码(D)中的1确定线段与哪条边相交，需要1次交
EF 对应case #3：E编码为0010，F编码为0010，两个编码中有某一位同时等于1，表示线段在相应边的外侧
GH/IJ 对应case #4：无法确定是否抛弃，需要求交

三维Cohen-Sutherland算法

• 利用6位进行编码
• 与二维剪裁的主要区别是使用平面而不是直线裁剪线段
  

Cohen-Sutherland算法效率

• 在绝大多数应用中，裁剪窗口相对于整个对象数据库而言是比较小的；大多数线段是在窗口的一条边或多条边外面，从而可以基于编码把它们抛弃，效率高。
• 当线段需要用多步进行缩短时，代码要被重复执行，这时效率不高。

Liang-Barsky裁剪算法

• 算法思想：在计算出来线段所在直线与窗口各边交点对应的α值后，我们可以通过这些参数值的顺序区分出各种情形
  
• 实例：如下图，定义线段与底边相交点为α1，左边相交点为α2，顶边相交点为α3，右边相交点为α4。算法求解出来的α得到如下的关系。如果是左图，说明线段相交次序为：底边-左边-顶边-右边，这个时候需要对左边-顶边求交；如果是右图，说明线段相交次序为：底边-顶边-左边-右边，这种次序下是不可能有交集的。
  

多边形裁剪

• 裁剪一个多边形可能得到多个多边形
  

• 裁剪一个凸多边形最多只能得到一个凸多边形（反证法）

Sutherland-Hodgeman裁剪

认为线段的裁剪就是一个黑盒子，输入是待裁剪线段的一对端点坐标，输出是裁剪后线段的一对顶点坐标

线段裁剪的流水线结构

一维情况（从裁剪区4条边考虑）

二维情况

三维情况：增加前后裁剪器

包围盒

不是直接对复杂多边形进行裁剪，而是先用一个方向与坐标轴平行的立方体或其它形状包围多边形。

光栅化

光栅化也称为扫描转化，把一组顶点定义的对象内部的像素用相应的亮度激活，明暗处理的结果由对象的颜色、纹理、以及明暗处理模型确定。上下图就好理解：

想要了解更多请参考这里

内外检测

内外检测的目的在于确定一个顶点是在多边形的内部还是外部，有下面的一些测试算法：

• 奇偶测试法：也叫相交测试法，这种方法比较常用，基本的思想是：从一点p引射线，如果与多边形边界交点数为偶数，则p在多边形外，否则在多边形内部。如果交点为顶点，需要特别处理。
• 环绕测试法：做法是从一个顶点出发，依次遍历各边，最后回到该顶点，如果环绕圈数不为0就在多边形的内部，反之。

隐藏面消除

隐藏面消除，就是指前面的物体遮挡住了后面的物体，使得后面的物体被全部遮挡或部分遮挡，被遮挡的部分，其实没必要进入图形绘制流水线。一般有下面算法：

• 对象空间算法：两两考虑对象，检测相互之间的位置
• 画家算法：把多边形沿从后到前的顺序显示出来
• 深度排序：根据物体在三轴方向上的深度，有序绘制，先处理简单情形，再处理复杂情形
• 背面剔除：看不见的面，直接不用绘制
• 图像空间算法：对每条投影线（对于n × m分辨率的帧缓冲区，共有nm条投影线），找到k个多边形中最近的那个
• Z缓冲区算法：应用一个称为z缓冲区或者深度缓冲区的地方存贮在每个像素，到目前为止找到的最近对象的深度。显示每个多边形时，把它的深度与z缓冲区中存贮的深度进行比较，如果新值小的话，把新的亮度值放到颜色缓冲区中并且用新深度更新z缓冲区。
  

反走样技术

看下这个立方体，边缘有些边缘锯齿，学术上称为几何走样，发生在光栅化阶段。反走样简单了解一下就可以了。

• 基于面积平均的反走样：
  
• 多边形的反走样