异端邪说 II - 为何4D齐次变换/裁剪/投影是浪费的

• 下载 NewClip3D.zip - 3.02 KB

引言

如今几乎所有的3D图形系统都基于4D齐次变换/裁剪/投影计算。随着3D图形技术几十年的成熟发展，这项技术已经证明了自己。一些非齐次系统来了又走，它们处理正交或平行视图比齐次系统更高效，但在处理透视视图时却表现不佳。以今天的标准来看，齐次数学已经胜出。

然而，在各种变换/裁剪/投影实现方案的开发过程中，裁剪算法中一个未经探索的小特性似乎被忽视了。出于某种原因，似乎没有人考虑过使用 x = 0 和 y = 0 平面作为六个裁剪平面中的两个。Direct3D 在架构上设计了一个 z = 0 的裁剪平面，大概是为了比 OpenGL 对应的 z = -w 裁剪平面提供一些微小的效率提升。

通过重新推导 x = 0 和 y = 0 裁剪平面的数学公式，再加上一些其他技巧，并将一个基于3D的算法与4D齐次计算进行比较，实际上揭示了所提出的3D算法在处理平行视图和透视视图时都明显更高效。也许是时候重新审视变换/裁剪/投影技术，让它迈出下一步的进化了。

齐次数学简述

齐次数学是一种非常优雅的技术，用于处理3D向量及其变换。齐次坐标是通过给一个3D向量附加一个值为1的'w'分量而创建的4D向量。例如，(x y z) 点 (1.2 3.4 5.6) 变成了 (x y z w) 点 (1.2 3.4 5.6 1.0)。要恢复为3D点，只需除以 w，例如，(1.2 2.4 48.0 2.0) 变成了 (0.6 1.2 24.0)。常见的3D变换都可以通过一个4x4矩阵乘法来实现……

• 平移 – 加上一个平移向量

  

• 旋转 – 与旋转后坐标系的 x、y 和 z 轴进行3次点积运算

  旋转后的 x、y 和 z 轴分别是 (xx xy xz)，(yx yy yz) 和 (zx zy zz)。

  

• 缩放 – 将每个坐标乘以一个因子

  

• 斜切（剪切） – 加上另一个坐标的缩放值。例如，在 z 轴方向上对 x 和 y 进行斜切……

  

• 透视投影 – 根据与视点的相对距离缩放 x 和 y

  如果你举起一块玻璃板，闭上一只眼睛，然后描摹透过玻璃板看到的真实世界图像，描摹出的点的坐标是 ( x•f(z) y•f(z) )，其中 f(z)=EyeZ/(EyeZ-z)，而 EyeZ 是玻璃板到你眼睛的距离。这些值的坐标系原点位于玻璃板上离你眼睛最近的点，+X 轴向右，+Y 轴向上，+Z 轴向后。

  

  将4D向量变换到2D……

  

任意数量的4x4齐次矩阵可以相乘，将任意序列的变换合并成一个单一的矩阵。图形系统通常创建矩阵，将对象的原生3D坐标映射到光照空间（进行光照计算），然后使用另一个矩阵将光照空间坐标映射到裁剪空间（进行裁剪操作）。

记住，重要的是对向量所做的改变。如何进行这些改变不那么重要，尽管这确实会影响效率。齐次数学只是一套可以用来实现这些变换改变的技术。

4D齐次变换/裁剪/投影

观察（Viewing）是将一个视体（view volume）内的物体映射到屏幕上的过程。对于矩形图像，视体要么是一个长方体，要么是一个截断的矩形棱锥体，也就是视锥体（frustum）。视体外的物体被忽略，视体内的物体被渲染，而跨越视体边界的物体则被裁剪到边界处，其剩余部分再被渲染。

OpenGL^®、Direct3D^® 以及其他3D图形API都描述了两种类型的投影：正交投影和透视投影。实际上，围绕这些投影存在着相当大但未被认识到的混淆。特别是，透视投影的原点，出于看似合乎逻辑的原因，被选在了视点（eyepoint）。而视点恰好是一个奇点，它迫使齐次投影矩阵右下角的值为零。正交投影的右下角值为1，因此这导致了一个错误的结论，即这两种投影是根本不同的。实际上，正交投影只是更通用的透视投影的一个特例。更多细节请参见我2009年10月的文章《A New Perspective on Viewing》（观察的新视角）。

齐次裁剪首先获取一个物体的3D点，然后使用齐次矩阵乘法将这些点变换到齐次裁剪空间。OpenGL的齐次视体是一个立方体，其对角三维顶点分别为 (-w -w -w w) 到 (w w w w)，这对应于3D空间中从 (-1 -1 -1) 到 (1 1 1) 的立方体。这个立方体的表面位于以下平面上，使用齐次公式表示：x = -w, y = -w, z = -w, x = w, y = w 和 z = w。这些齐次平面公式的简洁性和对称性使得裁剪实现保持一致，这也正是齐次裁剪的巨大吸引力所在。

这些简单的公式给人一种印象，即齐次裁剪以相同的方式处理正交视图和透视视图。它确实如此，但这仅仅是因为齐次数学最终使得 w 对于平行视图来说与1相当，对于透视视图来说与 z 相当。相应的3D裁剪平面对于平行视图是 x = ±1 和 y = ±1，对于透视视图是 x = ±z 和 y = ±z。

几乎所有的图形元素最终都被简化为线段，并在齐次裁剪空间中进行裁剪。由于一条线段可能穿过任意数量的裁剪平面（从零到六个），裁剪算法需要确定哪些裁剪平面被穿过。这些是简单的比较或减法操作，例如：
x<w y<w z<w x>-w y>-w z>-w
每次比较确定了点在裁剪平面的哪一侧，然后通过一些位掩码逻辑，可以轻松地“接受”（如果线段完全在视体内）或“拒绝”（如果完全在视体外）该线段。详情请参阅任何一本通用的图形学教科书。

穿过一个或多个裁剪平面的线段需要被这些裁剪平面修剪。修剪将确定线段在视体内的部分（如果有的话）。为每个3D交点计算所有三个坐标值并不如计算一个参数值高效，这个参数值是沿着线的相对距离，也就是公式中的 t 参数：

比较这些相对距离，以确定线段在视体内的实际部分（如果有的话）。如果视体内存在修剪后的线段，可以使用这些相对距离来计算修剪后的4D齐次线段。

对于一条穿过所有六个裁剪平面的线，相对距离的计算示例如下：

dw = w1-w0
a = (x1-x0)+dw
b = (y1-y0)+dw
dz = z1-z0
tLft = (-x0-w0) / a
tRgt = (x1-w1) / a
tBtm = (-y0-w0) / b
tTop = (y1-w1) / b
tBck = (z1-w1) / (dw-dz)
tFrt = -z0 / dz

本次讨论省略了大量的逻辑。这些逻辑可以在通用的图形学教科书中找到。

一旦确定了一个或两个边界 t 参数，就可以根据向量公式计算出裁剪后的4D坐标：

然后，通过除以 w 将裁剪后的线段端点变换到规范3D空间，得到 (xc/wc, yc/wc, zc/wc)。这些坐标会进一步缩放和平移到像素和深度缓冲空间，在这里几何体被转换成像素颜色和深度缓冲值。

新的3D变换/裁剪/投影

一个正则空间（regular space）被定义为角度正确的空间。世界空间被定义为一个正则空间，并且通常情况下，物体也在正则的物体空间中定义。非均匀缩放和斜切变换会将一个正则空间映射到一个非正则空间，其中线与线之间的角度是不正确的。对于真实世界的变换，只有平移和旋转是有效的，因为真实世界的固体物体不会缩放或斜切。

线段裁剪计算在正则和非正则空间中都有效，因为该计算基于沿线段的参数化距离。这意味着可以选择裁剪空间来优化裁剪计算。齐次裁剪正是这样做的，它为OpenGL选择了一个立方体，为DirectX选择了一个方棱柱。同样，3D裁剪也可以自由选择任何合适的视体。这里提出的形状使用了三个穿过原点的裁剪平面：x = 0, y = 0 和 z = 0；前裁剪平面是 z = 1，而顶部和右侧的裁剪平面是 x=1-iez*z 和 y=1-iez*z，其中 iez=1/EyeZ。裁剪空间的视点是 (0 0 EyeZ)。平行投影的 EyeZ 在无穷远处，所以 iez = 0。

图1. 裁剪空间视体的侧视图。

世界空间中的任何矩形视锥体或棱柱体视体，都可以通过一个3x3矩阵乘法进行旋转、非均匀缩放、斜切，并加上一个3D平移向量，从而将其映射到所提议的裁剪空间视体。

对于每个点，计算以下值：

OneMinusIezZ = 1 - iez * z
RgtOffset = x - OneMinusIez
TopOffset = y - OneMinusIez
FrtOffset = z - 1;

对于一条穿过所有六个平面的线，3D参数化线段裁剪的计算示例如下：

dx = x1 - x0
dy = y1 - y0
dz = z1 - z0
dRgt = Rgt1 - Rgt0
dTop = Top1 - Top0
tLft = -x0/dx
tRgt = -RgtOffset0/dRgt
tBtm = -y0/dy
tTop = -TopOffset0/dTop
tBck = -z0/dz
tFrt = -FrtOffset0/dz

利用一个或两个边界 t 参数，向量计算提供了3D裁剪后的点……

现在，使用以下公式将3D点投影到规范空间：

Z 怎么办？

嗯。Z 有点奇怪。我们到底需要对 z 做什么？嗯，从显示硬件的角度来看，z 用于遮挡。在渲染过程中，z-buffer 会被填充深度值，以确定一个新像素是否位于现有像素的前面。线段光栅化算法非常高效，使用简单的加法器来绘制一条线。如果能以同样的方式光栅化深度值，那就太好了。这意味着，对于生成的每个像素，深度计算将只是简单地加上一个固定的 delta z 或 delta depth 值。

现在，如果你取显示空间中的一条线（例如通过递增像素 x 坐标并给 z 坐标加上适当的 delta z 值创建），并使用 z 深度值的简单缩放将这条线映射回裁剪空间视体，你会得到一条曲线，而不是一条直线。（从视点看时，这条曲线确实显示为一条直线。）要将显示空间中的一条线映射到裁剪空间中的一条线，需要在 z 方向上进行非线性缩放。

图2. 世界空间到裁剪空间到规范空间到显示空间

那么，这种非线性的“压缩”计算是什么呢？齐次数学来拯救了！齐次数学将观察空间视体映射到规范齐次空间的一个副产品，就是所需要的非线性 z 方向压缩。见图3。不幸的是，这有一个副作用：z 方向的分辨率随距离变化，并取决于前后裁剪平面到视点距离的比率。如果这个比率太大，裁剪空间视体的大部分会被严重地压缩到规范空间和显示空间视体的前端，导致靠近后裁剪平面的 z-buffer 分辨率非常差。这个分辨率问题在图形学文献中有详细记载。

图3. 裁剪空间到规范空间的 z “压缩”

图3显示了当 iez = 1/1.5 时 z 方向的压缩情况。反向压缩的计算是：

显示空间 z 坐标列表：
        (0 0.125 0.25 0.375 0.5 0.625 0.75 0.875 1.0)
映射到规范空间列表：
        (0 0.3 0.5 0.643 0.75 0.833 0.9 0.955 1.0)

另一个更近期的解决非线性 z 方向问题的方案是 w-buffering。它不是在渲染期间加上一个固定的深度值，而是计算非线性的深度值，以匹配裁剪空间中迭代的固定 delta z。这个计算需要对每一个像素进行一次除法运算，但遮挡性能得到了显著提升，从而可以减少深度缓冲区的位数和/或大大增加前后裁剪平面距离之间的比率。W-buffering 越来越受欢迎，因为额外计算的成本被深度缓冲区 RAM 的节省所抵消。

本节的要点是指出为什么 z 需要与齐次变换进行相同的计算。第二点是，z-buffering 或 w-buffering 都可以与所提议的变换/投影/裁剪技术一起使用。对于 w-buffering 可能还有一些额外的优化，但这需要进一步研究。

比较变换/裁剪/投影的计算量

现在来看一些血淋淋的细节……

4D齐次		提议的3D方法
变换 (x y z 1)* [4x4]	12次乘法, 12次加减	(x y z) * [3x3] + (tx ty tz)	9次乘法, 9次加减
简单接受/ 拒绝测试 x>-w y>-w z>-w x<w y<w z<w	6次加减	a=1-iez*z RgtOff=x-a TopOff=y-a x<0 y<0 z<0 z>1 RgtOff>0 TopOff>0	1 * 2次加减 见注2
最坏情况的裁剪 dz = z0-z1 dw = w0-w1 a = (x0-x1)+dw b = (y0-y1)+dw tlft = (-x0-w0) / a trgt = (x0-w0) / a tbtm = (-y0-w0) / b ttop = (y0-w0) / b tfrt = -z0 / dz tbck = (z0-w0) / (dw-dz) tEnter=max(tltf,tbtm,tbck) tExit=min(trgt,ttop,tfrt) tEnter<tExit Pin = P0 + dP * tEnter Pout = P0 + dP * tExit	6次加减 6次加减 6 / 5次加减 8次乘法, 8次加减	dx=x0-x1 dy=y0-y1 dz=z0-z1 dRgt=RgtOff0-RgtOff1 dTop=TopOff0-TopOff1 tLft=-x0/dx tRgt=-RgtOff/dRgt tBtm=-y0/dy tTop=-TopOff/dTop tBck=-z0/dz tFrt=(1-z1)/dz tEnter=max(tltf,tbtm,tbck) tExit=min(trgt,ttop,tfrt) tEnter<tExit Pin = P0 + dP * tin Pout = P0 + dP * tout	5次加减 6 / 5次加减 (t 比较) 6次乘法, 6次加减
透视和 平行投影 xcan = xc / wc ycan = yc / wc zcan = zc / wc	3次除法 (简单情况) 6次除法 (裁剪后)	透视投影 （平行投影被优化掉了） xcan = xc / a ycan = yc / a zcan = zc / a	3次除法 (简单情况) 6次除法 (裁剪后)
总计 对于简单接受/ 拒绝的线段	3 / 12 * 18次加减		3 / 10 * (-17%) 11次加减 (-39%)
总计 对于最坏情况，即线段 穿过所有六个 裁剪平面	9 / 20 * 43次加减		9次除法 (相同) 16 * (-20%) 27次加减 (-37%)

注释

1. 该分析基于像多段线（polylines）和三角扇（triangle fans）这样的图元，其中每个新点定义一个新的图形项。像线段这样的图元会使许多操作加倍。
2. 在硬件实现中，与0和1的比较和算术运算以及取反操作可以被高度优化，因此不计入在内。

对于给定的视图，节省的计算量取决于需要多少次裁剪操作，而这又取决于视图本身。因此，节省的下限是乘法减少17%，加减法减少37%。平行投影还能省去3次除法和1次乘法。

对于某些系统，例如低成本手持游戏设备，可以优化 iez 透视值，提供一组特定的值，从而将乘法简化为几次加/减/移位操作。

优点和缺点

显然，这种优化的变换/裁剪/投影算法的真正好处来自于计算量的减少。迄今为止能想到的唯一可能的缺点是齐次矩阵能够组合两个或多个透视投影。就我个人而言，在实践中从未遇到过这种情况。有谁知道任何实际组合了两个或多个透视变换或类似奇怪组合的3D程序吗？

从理论上的自由度角度来看，一个4x4齐次变换有15个自由度，可以将任何六个平面构成的体映射到，比如说，一个立方体上。回顾一下《观察的新视角》（A New Perspective on Viewing），可以发现3个旋转、3个平移和7个视体形状值覆盖了所有类型的视图。ZNear 和 ZFar 值可以进一步优化为 ZHalfDepth，因此3D观察总共需要12个参数或自由度。所提议的变换/裁剪/投影技术使用了13个独立参数。为了说明一种限制，一个截断的楔形视体可以被4x4齐次矩阵映射，但不能被所提议的技术映射。我从未见过甚至听说过在任何图形学文献或3D程序中暗示过这种形状。

代码

提供了一个带有 main() 入口点的单个 C++ 文件。它只在裁剪空间中实现了裁剪算法（当然！）。该程序从标准输入读取视点和一系列3D点（每行一个），并将裁剪后的向量或文本 "Rejected" 输出到标准输出。

结论

所提议的3D变换/裁剪/投影技术减少了3D图形变换/裁剪/投影的计算量。任何3D计算效率的提升都会带来更快的帧率和/或更低的功耗，这两者都是有价值的结果。更低的功耗意味着便携设备的电池寿命更长，也为地球减少了碳足迹。

不过，是否有什么被忽略了呢？如果有，谁会指出来呢？

参考文献

1. 《计算机图形学：原理与实践》，第2版，1990年，Foley等人著。
2. 《3D游戏编程与计算机图形学数学》，第2版，2004年，Lengyel著。
3. http://www.opengl.org/resources/faq/technical/depthbuffer.htm
4. 新的视角

历史

• 2010年3月24日：初次发布。
• 2010年3月24日：修正了拼写错误 "eiz" 为 "iez"，并修正了第4个参考文献链接。
• 2014年2月21日：修正了伪代码格式。