裁剪

目前我们的代码中,已经有了渲染管线的概念。但现在还只是最基本的管线处理:顶点处理 - 透视除法 - 视口变换 - 光栅化 - 片元处理。

本篇文章,我们添加裁剪流程。具体的裁剪概念如图 1 所示,有三个三角形,对应三种情况。如果顶点全在视图之内,则全部保留;如果顶点都在视图之外,则全部丢弃;如果有一部分在视图外,则进行裁剪,获取显示在视图之内的新的多边形。

图1 裁剪

1. Sutherland-Hodgman 裁剪算法

我们采用 Sutherland-Hodgman 算法进行裁剪。Sutherland-Hodgman 算法的主要思想是逐边处理,将裁剪问题拆分成多个边界裁剪的步骤。具体的算法步骤如下:

1. 维护一个输入顶点列表(初始化为多边形的顶点),一个输出顶点列表(初始化为空)。

2. 遍历顶点列表中的线段(由相邻顶点构成),根据线段与边界的相交情况,更新输出顶点列表。

3. 将输出顶点列表内容作为输入顶点列表,再次清空输出顶点列表,用于下一边界处理。重复循环以上步骤。

步骤 2 中讲的是“根据线段与边界的相交情况,更新输出顶点列表”,我们来看具体如何更新输出顶点列表。线段与边界相交的情况,如图 2 所示,总共有四种情况:

1. 如果线段的起点和终点,都在边界内,则将终点加入输出列表。

2. 如果线段的起点在边界外侧,终点在内侧,则将交点和终点加入输出列表。

3. 如果线段的起点在边界内侧,终点在外侧,则将交点加入输出列表。

4. 如果线段的起点和终点,都在边界外,则什么也不添加。

图2 输出顶点

看着情形有点复杂。其实可以这么考虑:

因为线段是相邻点构成的,是“循环”的。即原来作为起点的顶点,也作过后续线段的终点。

所以防止重复添加,我们只添加终点。在内侧的起点,也会作为终点被添加在内,所以也不会遗漏。需要额外添加的是交点,因为它不在输入顶点之内,所以在得到交点的时候就要添加,

此处不对算法进行证明,但给出具体的特例进行理解。我们先以二维情况进行说明。如图 3 所示,我们先考虑上边界。初始情况下,输入顶点是 [0,1,2],输出顶点为空。

针对线段 2->0,都在边界外,全部丢弃。

针对线段 0->1,输出顶点增加交点 0' 和 1。

针对线段 1->2,输出顶点增加交点 2'。

图3 上边界

第二轮,如图 4 所示,我们取右边界。此时输入顶点为上一轮的输出顶点 [0',1,2'],输出顶点情况。

针对线段 2'->0',输出顶点增加交点 2'' 和 0'。

针对线段 0'->1,输出顶点增加 1。

针对线段 1->2',输出顶点增加交点 1'。

图4 右边界

其他边界情况,顶点都在这些边界内侧,顶点都“原封不动”。所以,最终裁剪得到的区域是 [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}\) 进行插值计算。

图5 距离比例

3. 代码实现

所有“前置知识”我们已经都搞明白了:我们理解了 Sutherland-Hodgman 裁剪算法。并且知道在三维情况下,如何判断点在边界内侧还是外侧,如何求交点。所以我们开始裁剪流程的代码实现。

代码清单 1 是 Sutherland-Hodgman 裁剪算法的实现,我们依次对各个边界进行裁剪操作。其中的六个边界好理解,就是立方体的六个面。但是 (0,0,0,1) 这个边界需要琢磨。

代码清单 1 Sutherland-Hodgman
  1. void TSoftRenderer::SutherlandHodgmanClipTriangle(
  2.     const TVertexShaderOutput vertexOutputs[3],
  3.     std::vector<TVertexShaderOutput>& clipped)
  4. {
  5.     std::vector<TVertexShaderOutput> vertices = { vertexOutputs[0], vertexOutputs[1], vertexOutputs[2] };
  6.     std::vector<TVertexShaderOutput> tmpVertices;
  7.  
  8.     const tmath::Vec4f boundaries[] =
  9.     {
  10.         { 0,  0,  0, 1},
  11.         { 1,  0,  0, 1},
  12.         {-1,  0,  0, 1},
  13.         { 0,  1,  0, 1},
  14.         { 0, -1,  0, 1},
  15.         { 0,  0,  1, 1},
  16.         { 0,  0, -1, 1},
  17.     };
  18.  
  19.     for (const tmath::Vec4f& boundary : boundaries)
  20.     {
  21.         if (vertices.empty() == false)
  22.         {
  23.             ClipPolygonAgainstBoundary(vertices, tmpVertices, boundary);
  24.             vertices.swap(tmpVertices);
  25.             tmpVertices.clear();
  26.         }
  27.     }
  28.  
  29.     clipped = std::move(vertices);
  30. }

(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 所示,我们依据起点与终点的情况,确定输出的顶点。

代码清单 2 单边界裁剪
  1. void TSoftRenderer::ClipPolygonAgainstBoundary(
  2.     const std::vector<TVertexShaderOutput>& vertices,
  3.     std::vector<TVertexShaderOutput>& outVertices,
  4.     const tmath::Vec4f& boundary)
  5. {
  6.     float t;
  7.     int prevIndex = vertices.size() - 1;
  8.  
  9.     for (int i = 0; i < vertices.size(); i++)
  10.     {
  11.         const TVertexShaderOutput& prev = vertices[prevIndex];
  12.         const TVertexShaderOutput& current = vertices[i];
  13.  
  14.         float prevDistance = tmath::dot(prev.position, boundary);
  15.         float currentDistance = tmath::dot(current.position, boundary);
  16.  
  17.         if (currentDistance > 0)
  18.         {
  19.             if (prevDistance <= 0)
  20.             {
  21.                 t = prevDistance / (prevDistance - currentDistance);
  22.                 outVertices.push_back(prev.Lerp(current, t));
  23.             }
  24.             outVertices.push_back(current);
  25.         }
  26.         else if (prevDistance > 0)
  27.         {
  28.             t = prevDistance / (prevDistance - currentDistance);
  29.             outVertices.push_back(prev.Lerp(current, t));
  30.         }
  31.  
  32.         prevIndex = i;
  33.     }
  34. }

从代码清单 3 中,我们可以看到,利用插值概念的好处是,我们还能直接插值得到交点的顶点颜色和 uv 坐标。

代码清单 3 插值
  1. TVertexShaderOutput TVertexShaderOutput::Lerp(const TVertexShaderOutput& other, float t) const
  2. {
  3.     TVertexShaderOutput res;
  4.  
  5.     res.position = this->position * (1 - t) + other.position * t;
  6.  
  7.     if (this->useColor)
  8.     {
  9.         res.useColor = true;
  10.         res.color = this->color * (1 - t) + other.color * t;
  11.     }
  12.     else
  13.     {
  14.         res.useUV = true;
  15.         res.uv = this->uv * (1 - t) + other.uv * t;
  16.     }
  17.  
  18.     return res;
  19. }

最后,我们把实现的裁剪功能增加到管线流程上。如代码清单 4 所示,我们把裁剪操作加到顶点处理之后(第 27 至 39 行)。接着对裁剪过后得到的顶点进行透视除法和屏幕坐标映射(第 41 行至 48 行)。因为裁剪得到的多边形可能不止三个边,所以我们把它“拆解”成多个三角形进行光栅化(第 50 至 60 行)。

代码清单 4 裁剪
  1. void TSoftRenderer::DrawElements(
  2.     TDrawMode mode,
  3.     uint32_t size,
  4. #if 0
  5.     TIndexDataType type,
  6. #endif
  7.     uint32_t offset)
  8. {
  9.     uint32_t* indexData = (uint32_t*)(m_currentElementBuffer->GetBufferData() + offset);
  10.  
  11.     FragmentShaderFunction fragFunc = std::bind(&TShader::FragmentShader, m_currentShader, std::placeholders::_1, std::placeholders::_2);
  12.     TShaderContext context(m_currentVertexArray);
  13.     TVertexShaderOutput vertexOutputs[3];
  14.     std::vector<TVertexShaderOutput> clippedVertices(10);
  15.     int primitive = GetPrimitiveCount(mode);
  16.  
  17.     for (uint32_t i = 0; i < size; i += primitive)
  18.     {
  19.         for (uint32_t j = 0; j < primitive; j++)
  20.         {
  21.             context.SetVertexIndex(indexData[i + j]);
  22.  
  23.             // VertexShader
  24.             m_currentShader->VertexShader(context, vertexOutputs[j]);
  25.         }
  26.  
  27.         clippedVertices.clear();
  28.         switch (mode)
  29.         {
  30.         case TDrawMode::Triangles:
  31.             SutherlandHodgmanClipTriangle(vertexOutputs, clippedVertices);
  32.             break;
  33.         case TDrawMode::Lines:
  34.         default:
  35.             assert(0);
  36.             break;
  37.         }  
  38.         if (clippedVertices.empty())
  39.             continue;
  40.  
  41.         for (TVertexShaderOutput& vertex : clippedVertices)
  42.         {
  43.             // 透视除法
  44.             vertex.position /= vertex.position.w();
  45.  
  46.             // NDC - 屏幕
  47.             vertex.position = m_screenMatrix * vertex.position;
  48.         }
  49.  
  50.         switch (mode)
  51.         {
  52.         case TDrawMode::Triangles:
  53.             for (uint32_t k = 1; k + 1 < clippedVertices.size(); k++)
  54.                 m_rz.RasterizeTriangle(clippedVertices[0], clippedVertices[k], clippedVertices[k + 1], fragFunc);
  55.             break;
  56.         case TDrawMode::Lines:
  57.         default:
  58.             assert(0);
  59.             break;
  60.         }
  61.     }
  62. }

测试

我们在之前旋转三角形的基础上,刻意触发裁剪。如代码清单 5 所示,我们查看在视口上、下、左、右边界上的剪裁情况,还有近裁剪面上的裁剪情况。

完整的代码在 tag/clipping

代码清单 5 测试
  1. void TClippingRenderTask::Transform()
  2. {
  3.     switch (m_direction)
  4.     {
  5.     case 0:
  6.         m_cameraOffset.x() += 0.01f;
  7.         if (m_cameraOffset.x() > 3.0f)
  8.         {
  9.             m_cameraOffset.x() = 0.0f;
  10.             m_direction = 1;
  11.         }
  12.         break;
  13.     case 1:
  14.         m_cameraOffset.x() -= 0.01f;
  15.         if (m_cameraOffset.x() < -3.0f)
  16.         {
  17.             m_cameraOffset.x() = 0.0f;
  18.             m_direction = 2;
  19.         }
  20.         break;
  21.     case 2:
  22.         m_cameraOffset.y() += 0.01f;
  23.         if (m_cameraOffset.y() > 3.0f)
  24.         {
  25.             m_cameraOffset.y() = 0.0f;
  26.             m_direction = 3;
  27.         }
  28.         break;
  29.     case 3:
  30.         m_cameraOffset.y() -= 0.01f;
  31.         if (m_cameraOffset.y() < -3.0f)
  32.         {
  33.             m_cameraOffset.y() = 0.0f;
  34.             m_direction = 4;
  35.         }
  36.         break;
  37.     case 4:
  38.         m_cameraOffset.z() -= 0.01f;
  39.         m_angle -= 0.1f;
  40.         if (m_cameraOffset.z() < 0.0f)
  41.         {
  42.             m_cameraOffset.z() = 3.0f;
  43.             m_angle = 0.0f;
  44.             m_direction = 0;
  45.         }
  46.         break;
  47.     default:
  48.         break;
  49.     }
  50.    
  51.     m_shader.modelMatrix = tmath::RotationMatrix(tmath::Vec3f(0.0f, 1.0f, 0.0f), m_angle);
  52.     m_shader.viewMatrix = tmath::TranslationMatrix(m_cameraOffset.x(), m_cameraOffset.y(), m_cameraOffset.z());
  53. }

最终的效果如视频 1 所示,可以看到裁剪的形状和对应的颜色没什么问题。

视频 1 裁剪