MIT 6.837:Clipping 裁剪

MIT 6.837:Clipping 裁剪

裁剪是渲染管线系统中的一个阶段,它位于视口变换后、投影变换前,主要完成可视范围之外的三角面的删除。

为什么需要裁剪

当物体在相机背后时,它不能被相机观察到,但在投影时却会被投影到成像平面上。当物体有点在相机所在平面时,投影会将它投影至无穷远点上,这是由于在投影过程中出现了除以 0 的情况。

裁剪可以避免以上两种问题,生成正确的结果。同时,删除那些在可视范围以外的三角面也可以减少后续阶段的计算量,提高效率。

裁剪的策略

如何裁剪物体

  • 将物体裁剪至视锥体的面内
  • 将物体裁剪至近平面

在什么阶段裁剪物体

  • 在世界坐标系内,利用视锥 6 个平面的方程裁剪
  • 在裁剪坐标系内,使用规范化前(即 w 不为 1)的齐次坐标
    • 与相机位置无关
    • 通用的做法,实现简单
  • 使用规范化后的齐次坐标
    • 需要除以 z,如物体在相机平面内则会出现无穷大值

裁剪直线

判断点是否在视锥内

一个平面可以由法向量 $\boldsymbol{n}$ 和偏移量 $d$ 表示,其平面方程 $\boldsymbol{P} \cdot \boldsymbol{n} = d$ 可化为 $Ax+By+Cz+D=0$。在齐次坐标下,我们将前式的 $A,B,C,D$ 表达为四维向量 $\boldsymbol{H}=(A,B,C,D)$,则有平面的齐次方程 $\boldsymbol{H} \cdot \boldsymbol{P} = 0$。

对于给定点 P,其与平面向量之点乘值 $\boldsymbol{H} \cdot \boldsymbol{P}$ 代表了一个有符号的距离,如为正说明点在平面法向量指向一侧(内侧),为负则为另一侧。利用此性质,我们可以判断此距离值为正则需要保留,为负则需要裁剪。

22 - MIT 6.837:Clipping 裁剪

视锥由 6 个平面构成,只要让每个平面的法向量指向视锥内侧,利用上述方法即可判断一个点是否在视锥内,从而实现对点的裁剪。视锥的各平面齐次向量分别为

$$ \begin{align}
\boldsymbol{H}_{\text{near}} &= (0, 0, -1, n) \\
\boldsymbol{H}_{\text{far}} &= (0, 0, 1, f) \\
\boldsymbol{H}_{\text{bottom}} &= (0, n, b, 0) \\
\boldsymbol{H}_{\text{top}} &= (0, -n, t, 0) \\
\boldsymbol{H}_{\text{left}} &= (l, n, 0, 0) \\
\boldsymbol{H}_{\text{right}} &= (-r, -n, 0, 0)
\end{align} $$

裁剪直线

将直线方程代入平面方程,解出进入和离开视锥的交点,只保留交点内的一段。

裁剪线段

23 - MIT 6.837:Clipping 裁剪

对于线段的两端点 P 和 Q,判断它们与每个面的相交情况

  • P 和 Q 都在平面外:线段被裁剪
  • P 和 Q 有一个在平面外,另一个在平面内:将在平面外的一段裁剪至平面上
  • P 和 Q 都在平面内:不需要裁剪

Cohen-Sutherland 算法

24 - MIT 6.837:Clipping 裁剪

上面的逐面裁剪方法存在无效计算。如上图所示,线段在平面 H1、H2 被裁剪至交点,而在平面 H3 则完全被裁剪,因此在前面的求交是无效计算。如果能提前快速知道这个线段能被完全裁剪,则可以减少计算量。

26 - MIT 6.837:Clipping 裁剪

我们把裁剪平面切分出的部分分为 9 块分别编区位码(outcode),每一块区域用对应位上的 1 标志在哪个平面之外,而如果在所有平面内则为全 0 码。在裁剪线段 PQ 前,对端点分别求其区位码为 1010 与 0110,而两端点区位码之与为 0010,其中包含 1 位,说明线段 PQ 都在某一平面之外,可以被完全裁剪。

此方法同样适用于多边形的裁剪判断。在三维情况时,空间被划分为 27 块,区位码需设置 6 位。

27 - MIT 6.837:Clipping 裁剪

此方法仍然存在效果不佳的情况,如上图所示,两端点区位码之与为 0,但线段可以被完整裁剪。

裁剪多边形

裁剪多边形的一个常用方法是 Weiler-Atherton 裁剪算法。在此算法中,认为多边形的边具有方向,求出多边形与裁剪空间的交点,并按边的方向将交点分类为进入或离开裁剪空间。

28 - MIT 6.837:Clipping 裁剪

得到交点信息后,在相邻的进入/离开交点对之间按一定顺序「行走」多边形或裁剪空间边界,直至走过的边围成一个多边形,即裁剪后的多边形。离开-进入交点间走裁剪空间边界,即交点连线;进入-离开交点间走多边形的边。

此外,如果多边形与边界并无交点,则多边形要么被完全裁剪,要么无需裁剪,通过判断顶点是否在视锥内即可。



发表评论

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据