目前我们的代码中,已经有了渲染管线的概念。但现在还只是最基本的管线处理:顶点处理 - 透视除法 - 视口变换 - 光栅化 - 片元处理。
本篇文章,我们添加裁剪流程。具体的裁剪概念如图 1 所示,有三个三角形,对应三种情况。如果顶点全在视图之内,则全部保留;如果顶点都在视图之外,则全部丢弃;如果有一部分在视图外,则进行裁剪,获取显示在视图之内的新的多边形。
1. Sutherland-Hodgman 裁剪算法
我们采用 Sutherland-Hodgman 算法进行裁剪。Sutherland-Hodgman 算法的主要思想是逐边处理,将裁剪问题拆分成多个边界裁剪的步骤。具体的算法步骤如下:
1. 维护一个输入顶点列表(初始化为多边形的顶点),一个输出顶点列表(初始化为空)。
2. 遍历顶点列表中的线段(由相邻顶点构成),根据线段与边界的相交情况,更新输出顶点列表。
3. 将输出顶点列表内容作为输入顶点列表,再次清空输出顶点列表,用于下一边界处理。重复循环以上步骤。
步骤 2 中讲的是“根据线段与边界的相交情况,更新输出顶点列表”,我们来看具体如何更新输出顶点列表。线段与边界相交的情况,如图 2 所示,总共有四种情况:
1. 如果线段的起点和终点,都在边界内,则将终点加入输出列表。
2. 如果线段的起点在边界外侧,终点在内侧,则将交点和终点加入输出列表。
3. 如果线段的起点在边界内侧,终点在外侧,则将交点加入输出列表。
4. 如果线段的起点和终点,都在边界外,则什么也不添加。
看着情形有点复杂。其实可以这么考虑:
因为线段是相邻点构成的,是“循环”的。即原来作为起点的顶点,也作过后续线段的终点。
所以防止重复添加,我们只添加终点。在内侧的起点,也会作为终点被添加在内,所以也不会遗漏。需要额外添加的是交点,因为它不在输入顶点之内,所以在得到交点的时候就要添加,
此处不对算法进行证明,但给出具体的特例进行理解。我们先以二维情况进行说明。如图 3 所示,我们先考虑上边界。初始情况下,输入顶点是 [0,1,2],输出顶点为空。
针对线段 2->0,都在边界外,全部丢弃。
针对线段 0->1,输出顶点增加交点 0' 和 1。
针对线段 1->2,输出顶点增加交点 2'。
第二轮,如图 4 所示,我们取右边界。此时输入顶点为上一轮的输出顶点 [0',1,2'],输出顶点情况。
针对线段 2'->0',输出顶点增加交点 2'' 和 0'。
针对线段 0'->1,输出顶点增加 1。
针对线段 1->2',输出顶点增加交点 1'。
其他边界情况,顶点都在这些边界内侧,顶点都“原封不动”。所以,最终裁剪得到的区域是 [2'',0',1,1'] 组成的四边形区域。
Sutherland-Hodgman 算法应该是可以用归纳法证明的。这边的特例可以当成一个起点。
2. 三维情况
三维的流程和二维的流程是一样的,只不过这边的边界从二维的线段变成了三维的平面。现在我们要解决的问题是:
1. 如何判断一个点是在平面的内侧还是外侧?
2. 如何求线段和平面的交点。
我们把推导顶点到平面的距离公式作为引子。
方程 \(\textbf{a}x+\textbf{b}y+\textbf{c}z+\textbf{d}=0\) 表示为一个平面,该平面的法线向量是 \((\textbf{a},\textbf{b},\textbf{c})\)。
任取平面上两点 \(P_0,P_1\),\(\overrightarrow{P_0P_1}=(x_1-x_0,y_1-y_0,z_1-z_0)\)。
有 \(\overrightarrow{n}\cdot\overrightarrow{P_0P_1}=(\textbf{a}x_1+\textbf{b}y_1+\textbf{c}z_1+\textbf{d})-(\textbf{a}x_0+\textbf{b}y_0+\textbf{c}z_0+\textbf{d})=0\)。
所以平面的法线向量是 \((\textbf{a},\textbf{b},\textbf{c})\)。
也侧面说明了为什么 \(\textbf{a}x+\textbf{b}y+\textbf{c}z+\textbf{d}=0\) 能表示平面。
该平面就是满足 \(\overrightarrow{n}\cdot\overrightarrow{P_0P_1}=0\) 的点组成的集合。
\(d\) 的几何含义是,经过原点的平面,往法向相反方向移动的距离。
有了平面定义,我们继续推导,点 \(P_0=(x_0,y_0,z_0)\) 到平面 \(\textbf{a}x+\textbf{b}y+\textbf{c}z+\textbf{d}=0\) 的距离。因为距离最短,所以 \(P_0\) 必然要沿着法线方向“滑动”。沿着法线方向滑动到平面上所经历的长度,就是到平面的距离。
设滑动的距离是 \(t\),到达平面上的点 \(P=(x_0+\textbf{a}t,y_0+\textbf{b}t,z_0+\textbf{c}t)\)。
因为点 \(P\) 在平面上,所以代入平面方程有
\(\textbf{a}(x_0+\textbf{a}t)+\textbf{b}(y_0+\textbf{b}t)+\textbf{c}(z_0+\textbf{c}t)+d=0\)
可得
\(t=-\frac{\textbf{a}x_0+\textbf{b}y_0+\textbf{c}z_0+\textbf{d}}{\textbf{a}^2+\textbf{b}^2+\textbf{c}^2}\)
但是我们滑动的距离是以法向量长度为单位的,所以 \(t\) 还要乘上法向量的长度 \(\sqrt{\textbf{a}^2+\textbf{b}^2+\textbf{c}^2}\)。同时距离取正,所以最终得到了我们熟悉的距离公式:
\(D=\frac{\lvert \textbf{a}x_0+\textbf{b}y_0+\textbf{c}z_0+\textbf{d} \rvert}{\sqrt{\textbf{a}^2+\textbf{b}^2+\textbf{c}^2}}\)
\(t\) 的内容,对我们的问题很有帮助。可以看到其分子内容,就是点的齐次表示 \((x_0,y_0,z_0,1)\) 和平面定义 \((\textbf{a},\textbf{b},\textbf{c},\textbf{d})\) 的点积。
如果我们规定,点在平面法线指向的一侧,为内侧;在法向相反的方向,为外侧。通过 \((x_0,y_0,z_0,1)\) 和 \((\textbf{a},\textbf{b},\textbf{c},\textbf{d})\) 的点积结果,我们有:
1. 结果大于 0,点在平面内侧。因为此时 \(t\) 小于 0,即我们要沿法线的相反方向才能到达平面,即原来点就在法线指向的一侧。
2. 结果小于 0,点在平面外侧。
此时我们就已经解决了第一个问题。我们能够判断点在平面的内侧还是外侧了。
第二个问题是求交点。其实也不复杂,如图 5 所示,可以想象,交点的各分量坐标,和两点的距离是成比例关系的。我们可以取点到平面的距离比例 \(\frac{\lvert D_1 \rvert}{\lvert D_1 \rvert + \lvert D_2 \rvert}\) 进行插值计算。
3. 代码实现
所有“前置知识”我们已经都搞明白了:我们理解了 Sutherland-Hodgman 裁剪算法。并且知道在三维情况下,如何判断点在边界内侧还是外侧,如何求交点。所以我们开始裁剪流程的代码实现。
代码清单 1 是 Sutherland-Hodgman 裁剪算法的实现,我们依次对各个边界进行裁剪操作。其中的六个边界好理解,就是立方体的六个面。但是 (0,0,0,1) 这个边界需要琢磨。
(0,0,0,1) 这个边界,和顶点的点积结果是 w,即要满足 w>0。这是合理的,因为 w<=0 的点在近裁剪平面上或后方,肯定是不显示的。主要是后续的插值计算比较费解。
这边插值的比例是 w_1/(w_1-w_2),针对 w1、w2 做插值,可以看到插值后的 w_clip 一定为 0。
所以目前理解为插值得到的是在 w=0 裁剪面上的点。看着也是合理的,但总感觉和 z 边界的处理有点重合。留作问题。
还要一个要考虑的点是,输入顶点的 w 分量不为 1。但是现在已经确保裁剪得到的 w>=0 了,不改变符号,所以裁剪流程中的判断不受影响。
我们来看具体的边界裁剪实现。如代码清单 2 所示,我们依据起点与终点的情况,确定输出的顶点。
从代码清单 3 中,我们可以看到,利用插值概念的好处是,我们还能直接插值得到交点的顶点颜色和 uv 坐标。
最后,我们把实现的裁剪功能增加到管线流程上。如代码清单 4 所示,我们把裁剪操作加到顶点处理之后(第 27 至 39 行)。接着对裁剪过后得到的顶点进行透视除法和屏幕坐标映射(第 41 行至 48 行)。因为裁剪得到的多边形可能不止三个边,所以我们把它“拆解”成多个三角形进行光栅化(第 50 至 60 行)。
测试
我们在之前旋转三角形的基础上,刻意触发裁剪。如代码清单 5 所示,我们查看在视口上、下、左、右边界上的剪裁情况,还有近裁剪面上的裁剪情况。
完整的代码在 tag/clipping。
最终的效果如视频 1 所示,可以看到裁剪的形状和对应的颜色没什么问题。