3D图形编程指南3再续 -3D变换

<b>2.7.2 透视投影
　　</b>透视投影创建的对象投影图像的大小依赖于对象与观察者的距离。在透视投影中显现这种效果并不困难。可能，最先与我们联系起来的是一个空荡荡且很直的街道，以及街道两旁消失在无穷远处的建筑物。透视投影使我们以场景现实主义的特点产生图像。毕竟，如果道路不是汇集到一点，建筑物不是在远方变得越来越小的时候，即便是同样的街道也看起来非常不自然。
　　我们可以通过把观察者的眼睛仿真为一个点，而光线从所有对象反射回来汇聚到这个点上，来模拟透视投影变换。每条光线，在射到眼睛里之前，已经与观察者面前的平面相交叉。如果我们能够找到交叉横断面，并标绘那里的点，观察者的注意力会被欺骗，认为从标绘的点那里发射出的光线实际是来自与空间中其原始的位置。（参见图2.16）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image168.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图2.16 透视投影</B></FONT></TD></TR></TABLE>
　　我们可以与前面提到的方法一样，选择一个与参考系的<I>XY</I>面平行的投影面。在这种情况下，我们可以注意到一些与原点和图像上的点相联系的简单关系。（参看图2.17）

<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image169.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图2.17 透视投影几何</B></FONT></TD></TR></TABLE>
　　首先看一下平面的情况。观察者的眼睛位于参考系的原点。观察者的眼睛与投影面的距离称之为“焦点距离”。其目的是确定哪些点在光线从A点发射到观察者的眼睛的时候横断投影面 。我们必须在屏幕的的那个位置上标绘像素。明显地，我们遇到了另一个类似的处理三角形的问题。要注意到这么两个事实：大小两个三角形在坐标系的起点是相同的，以及两个三角形的正切值是相同的。我们有：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image170.gif"></TD></TR></TABLE>
　　对Y有同样的公式。和起来，这两个公式这么描述3D情形：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image171.gif"></TD></TR>
<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image172.gif"></TD></TR></TABLE>
　　上面我们考虑的情形只用于观察者位于坐标系原点，沿着Z轴看的情况。如果不是这种情况，与平行投影一样，我们必须先进行一个仿射变换，把原始的空间转换到在这里描述的简单透视变换的情况。在第五章讨论这种仿射变换。
　　z坐标的位置必须得到某种程度的澄清。在透视变换之后， 我们将要把图元渲染到平面屏幕上。需要x和y坐标，但是不需要z坐标，这样我们可以去掉z。然而，当我们试图渲染具有多个表面的对象时，要知道所有多边形的z深度，这样，就可以推论出什么是可见的，什么是不可见的（细节在后面几章中讨论）。我们令<I>z'=z</I>，可以保留深度值。但是，由于x和y进行了变换，而z不变，这样，实际上深度可能发生了相对变化。这就是说， 如果原始空间中一个多边形遮掩另一个多边形，在经过投影后，实际上前者出现在后者的后面，被后者所遮掩。（参见图2.18）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image173.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图2.18 在投影变换前后的深度关系</B></FONT></TD></TR></TABLE>
　　为了避免这种不受欢迎的效果,我们同样可以对z应用非线性变换。比如说，<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image174.gif">，这里的C是常量。
　　透视效果的实现是非常直截了当的。然而，既然计算随着焦点距离变化，我们必须理解它的物理意义，这样才
能选择合适的数值。（参见图2.19）

<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image175.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图2.19 焦点距离含义</B></FONT></TD></TR></TABLE>
　　焦点距离确定了视角的区域。焦点距离小则视角宽，焦点距离大则视角窄。这有助于把距离作为屏幕像素的度量。比如说，如果选择的焦点距离是160像素，显示分辨率是320×320像素，则视角是90度。
　　透视变换产生的图像可能起先看起来有点不自然的失真。必须采取点措施改善其真实度。在实践中，视角在75-85度时的焦点距离效果比较好一些。当然，这也取决于场景和屏幕的几何结构。
　　以矩阵的形式表达透视变换非常困难。实际上，通常的矩阵乘法只能处理线性变换。然而透视变换是非线性的。为了把它表达为矩阵形式，我们需要另一种特殊的约定。对平移我们已经使用了一种较小的约定。即在3×3矩阵上增加了一个额外的维。
　　这种能够表达透视变换的约定是为了保留齐次（<I>homogeneous</I>）坐标。 在X，Y，Z后增加到坐标向量里的1的值要保持为1。如果在应用变换期间，该位置上得到不同的值， 向量会被重新归一化：即在向量中的每个元素都乘上一个常数，最后的元素又成为1。假定使用这种策略，我们能够把透视变换表示为如下的矩阵形式：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image176.gif"></TD></TR></TABLE>
　　既然在结果向量的最后一个元素不是1，通过乘上<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image177.gif">来归一化：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image178.gif"></TD></TR></TABLE>
　　取决于对z坐标的需求，当我们不再需要z坐标的时候，可以去掉它，上面的矩阵形式有一些变化：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image179.gif"></TD></TR></TABLE>
　　向量变为（z坐标为0）：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image180.gif"></TD></TR></TABLE>
　　而且，如果观察者的位置由于某些位置的z为负值，不便于被选做坐标系的原点，比如说，变换公式和变换矩阵会因此产生不同的形式。我们应该依赖于特别的应用（在这些应用中必须使用变换）而定义必要的形式。
　　一般地，我们能够以收敛点数区分各种透视变换（一点透视，二点透视），或者也可以摄像机观察方向和屏幕法线的角度来区分。我们只考虑观察方向垂直于投影面的一点透视，因为它洞察了透视变换的特殊之处。为了应用的目的，我们也许需要稍微复杂一点的透视，这在大多数情况下，很容易就引出了我们已经讨论过的先进行仿射变换的情况。
　　透视变换还有几个其它的问题。比如说，z=0的点将被投影变换映射到哪里？要知道，从上面的公式中能看出，z=0的时候会导致计算错误。
　　另一个问题，z为负值的时候的计算会产生负坐标。我们看到的将会是对象（或对象的一部分）被翻转过头了。但是，带有负z坐标的的对象在观察面的后面，躲在了观察者的身后。这样，我们实际上看不到它了（至少是它的一部分）。
　　解决这个问题的唯一的办法是保证没有无效的Z坐标 。一条实现途径是对原始的点集进行3D裁剪（在后面章节中讨论2D和3D裁剪的细节）。
　　让我们在考虑一下矩阵形式表达的透视变换。上面讨论的所有的变换中，一个点要先被渲染，它必须按照接下来说的步骤做。首先，进行基于观察者位置和方位的仿射变换。在我们进行透视变换前，必须执行裁剪，除去在观察面后面的点。然后，我们再进行透视变换本身。以传统的矩阵形式表达裁剪非常地困难。正如我们所讨论过的，当我们用一个矩阵表达几个连续变换的时候，矩阵通常是有用的。然而，在这种情况下，我们需要不止一个矩阵，因为旋转和透视被裁剪隔开了。如果我们确信没有坐标在观察面之后，那么可以避免裁剪。这时候，我们可以以矩阵的形式表达每一个变换，并计算它们的级联矩阵。在其它情况中，不能避免裁剪，或许我们想把变换分隔为两个阶段，3D裁剪前和3D裁剪后。

<B>2.8 通过定点算法实现变换</B>
　　在前面的几节中，我们使用的是浮点乘法（sin(x)和cos(x)，实数函数）。然而这种计算开销非常大。考虑到3D变换极其依赖于小数（分数）乘法，找出一种可能的加速技术是非常值得的。其中一个用来代替浮点算法的就是“定点算法”。为了完成定点算法，我们使用整数乘除法。假定整数操作开销较小，利用定点算法会给我们某种更好的性能。
　　在这一节中，我们讨论一下数字计算机表达和处理数值的基本原理。这对我们理解定点算法的实现非常必要。然后，我们考虑在3D应用中这种算法起作用的特殊例子。

　　<B>2.8.1 整型数表示</B>
　　理解数字计算机表示整数的方式非常有用。（参见图2.20）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image181.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图2.20 表示整数</B></FONT></TD></TR></TABLE>
　　在任何计算系统中，多位数的数字都有不同的加权。比如说，十进制，加权是10的幂。比如102表示为：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image182.gif"></TD></TR></TABLE>
　　二进制的情形是一样的，唯一的不同之处是，加权是2的幂。因此在图2.20中表示的数值是：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image183.gif"></TD></TR></TABLE>
　　那么如何表示十进制的小数呢？对在小数点右侧的数字来说，我们把它以-10的幂递增。即：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image184.gif"></TD></TR></TABLE>
　　在这种表达形式中，小数点分隔了0次幂和负幂，不象以指数形式表示的数字，小数点的位置是不变的。让我们看看在二进制数中加入小数点的情况：（图2.21）

<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image185.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图2.21 定点数的表示</B></FONT></TD></TR></TABLE>
　　与前面非常类似，我们可以知道在图2.21中表示的数字是：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image186.gif"></TD></TR></TABLE>
　　让我们找找我们能够表示的数字的范围。以十进制类推，在十进制中，以0.01步进，两位数可以覆盖到0.99。小于0.01的数字不能表示出来，除非增加小数点后的位数。对二进制来说也是这样，参见图2.21的例子，我们能表示的最小数字是二进制的0.01，即十进制的1/4。要表示更高精度的的数字需要增加二进制小数点后面的位数。
　　再让我们看看负数的表示。虽然有好几种方法， 但有一种在今天最流行。它被称之为“2的补码形式”。即在最左边的数字前加负号。（参见图2.22）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image187.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图2.22 负整数的表示</B></FONT></TD></TR></TABLE>
　　上面表示的数字是：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image188.gif"></TD></TR></TABLE>
　　这种方式的好处是无需为了适应两种补数而改变正数加减法的算法。这要归功于整数的自然溢出循环，如果在能够表示的最大值上加个1，我们会从最重要的位（最左端）获得一个进位，忽略它，数值就是确切的0。有符号表达式中的-1是无符号表达式中的最大值。当然，-1+1=0。尽管加法和减法算法不必为了适应2的补码形式的负数而改变， 但乘除法算法需要改变。这就是为什么在大多数计算机上引入了有符号乘法和无符号乘法的缘故。
　　既然在2的补码表达式中最左端的位进位带来了负数加权，而且因为它有最高的幂，在上面的例子中能够表达的最小的负数是二进制的10000，即十进制的-16。所有其它的数位都有正数加权，因此能够表达的最大的正数是二进制的01111，即十进制的15。这个轻微的不对称在大多数情况下不是什么重要的问题，然而sin(x)和cos(x)函数值在1和-1之间。为了表达它，我们选择了单整数域的格式：


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image189.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图2.23 单整数域定点数</B></FONT></TD></TR></TABLE>
　　这样，由于上面提到的不对称性，有个-1（10000）值。然而，没有正1，只有一个大约数：(01111) = 1/2+1/4+1/8+1/16=15/16，（参见图2.23）。对大多数图形应用来说，使用15位所代表的小数足够接近1，不会有任何问题。然而，对某些应用来说，有时候会产生积累错误，这时候就需要整数位了。

<B>　　2.8.2、定点数运算</B>
　　我们已经讨论过，可以使用规则的正数加减法来实现对应的定点运算。对乘除法来说，则情形有点复杂。让我们考虑一下两个十进制数相乘的时候发生了些什么。举例来说，一个十进制整数被一个带有小数点的十进制数乘，结果只需要一个整数。那么：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image190.gif"></TD></TR></TABLE>
　　正如我们看到的，乘法的实际结果在小数点后有许多位，既然我们只需要一个整数，我们必须去掉小数点后面的数字，实际上是把数字右移两位（整数部分、符号以及小数部分连续存储在一个或多个字节中）。对定点二进制数来说，处理方法是同样的。比如说，如果一个整数被（二进制）小数点后有8位的数乘， 其结果在（二进制）小数点后也有8位。如果我们只对整数形式感兴趣，我们必须把数字右移8位，去掉所有的小数部分。同样的技术也用于除法。如果我们要使两个整数相除，得到是定点数结果，被除数必须向左移（增加定点域），这样就可以用一个整数去除定点数了。

　　<B>2.8.3 定点算法的实现</B>
　　有一个通用的定点算法库是非常有帮助的。然而，定点算法依赖于选择的精度。既然可以方便地在不同的应用中使用不同的精度，我们就可以选择几种不同的定点数格式，在应用程序中每个指定的地方，直接地用于某些特殊的公式。
　　还有很重要的一点是是不是我们能够使用高级C结构进行所有的运算？ 或者是不是有必要把运算用汇编实现？在大多数汇编中，乘法的结果有两倍的数位。既然某些位被小数占用，我们需要得到最大数量的位。另外，乘法的结果通常是放在两个寄存器中，可以用移位来代替对运算结果的调整，也能够从寄存器中得到高位进位，利用寄存器的位长有效地完成0开销的右移。但在另一方面，汇编代码在实践中移植比较困难。显然， 对特定的应用来说，这种困难或许可以被解决。
　　定点算法对实现需要大量乘法的3D变换来说显然非常有用。让我们假定以整数存储点坐标。<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image191.gif">或<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image192.gif">函数的结果显然是小数形式的，在变换矩阵中当然也是这样。所有的这些可以使用同样的定点数格式来存储。如果我们决定预先计算三角函数的结果并把它们存储在数组中，就有必要把浮点数转化为定点数。如果我们简单地使用定点数存储方式把浮点数赋值为定点数，小数部分会丢失。既然我们同样需要转换小数部分内容，就要尝试在赋值之前把小数位移动到整数位。纯粹的移动操作没什么意义，不能为浮点数定义。然而，右移N个二进制位与除以<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image193.gif">有同样的效果。同样地，左移N个二进制位相当于乘上<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image194.gif">。使用这一点，很容易看出，从浮点数向定点数变换需要移动的小数数量等于N个二进制位。前者在赋值为后者的表达形式之前应该被预乘上<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image194.gif">。
　　在使用定点算法的典型3D应用中，当我们构建变换矩阵的时候，定点数通常是被定点数乘。结果具有的小数位通常是需要的2倍。因此，我们必须通过右移调整。（参看程序清单2.5）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/2.1/Image195.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>程序清单2.5 为构建旋转系数使用定点数</B></FONT></TD></TR></TABLE>
　　在实现旋转变换的历程中，我们用整数乘定点系数。结果中有与定点系数相同数量的小数位。如果我们对以整数形式得到旋转变换结果感兴趣（既然我们得到这些坐标的最终目的是索引存在图像中的离散位图，这就不是不合理的，），那么，通过把结果右移，去掉所有的小数位。
　　还有几个涉及到定点算法的问题。我们必须小心地注意数值运算允许的范围。如果我们使用的是32位数，并选择了16为表达小数部分，一位用于符号位，那么只有15位用于整数部分。在两个定点数乘过之后，所有的32个位实际上都是小数（结果的小数位是两个数的小数位之和）。整数部分进入了左进位的不可知的领域。既然乘法的结果有两倍于每个数字的数位，当我们以汇编编写这种运算的代码的时候，能够完全避免这个问题。然而，如果只使用高级语言实现定点算法的时候，这成了一个严重的问题。
　　最后，整数乘法加移位是不是真的比浮点乘法快？尽管从算法的复杂性来看，这好象是没什么问题，但在实践上，现实中的硬件可不一定是这样。
　　下面是在某种情况下对一些处理器的大概测试，比较浮点乘法和定点乘法性能。（参看表2.1）


<TABLE cellSpacing=1 cellPadding=5 width="85%" align=center bgColor=#000000 border=0>

<TR>
<TD class=BGRed colSpan=2><B><FONT color=#cccccc>表2.1 浮点与定点性能对比</FONT></B></TD></TR>

<TR>
<TD vAlign=top width="50%" bgColor=#ffffff>Sparc</TD>
<TD vAlign=top width="50%" bgColor=#ffffff>浮点比定点快1.3倍</TD></TR>
<TR>
<TD vAlign=top width="50%" bgColor=#ffffff>Motorolla 68040</TD>
<TD vAlign=top width="50%" bgColor=#ffffff>浮点比定点快1.5倍</TD></TR>
<TR>
<TD vAlign=top width="50%" bgColor=#ffffff>Intel P5 (Pentium)</TD>
<TD vAlign=top width="50%" bgColor=#ffffff>浮点比定点快1.6倍</TD></TR>
<TR>
<TD vAlign=top width="50%" bgColor=#ffffff>rs4000</TD>
<TD vAlign=top width="50%" bgColor=#ffffff>浮点比定点快1.1倍</TD></TR>
<TR>
<TD vAlign=top width="50%" bgColor=#ffffff>rs6000</TD>
<TD vAlign=top width="50%" bgColor=#ffffff>浮点比定点慢1.1倍</TD></TR>
<TR>
<TD vAlign=top width="50%" bgColor=#ffffff>Intel 80386sx</TD>
<TD vAlign=top width="50%" bgColor=#ffffff>浮点比定点慢5.1倍</TD></TR></TABLE>
<DIV align=center><B></B></DIV>
　　正如我们看到的，如今，带有快速浮点处理单元的处理器做浮点数乘法比整数快。然而，这对加法来说这不成为问题。应该再次强调，整数算法一般比浮点开销要少，然而，后者在设计上使用了更多的硅晶体，因此对乘法来说速度更快。一些速度上的增加要归因于管道线性化（pipe-linening），它只是对一系列的浮点指令改善了吞吐量（这一点，我们要承认，矩阵运算也在其中）。在移植性的方面（不算处理器使用浮点单元做整数计算而产生退化的情况），整数算法足够快；反之，不带FPU处理器的浮点乘法却非常的慢。在许多种不同的权衡中，我们主要根据算法在时间上的困难程度来选择使用哪一种算法。如果算法主要是递增的，那么定点算法是一个很好的选择，因为加法是主要的运算。另一方面，如果乘法是主要运算，就要根据处理器来选择计算方案。

　　<B>小结</B>
<FONT face=楷体_GB2312 color=#993300>　　综上所述，在本章，我们讨论了如何完成基本几何变换。我们讨论的技术可以描述位置、方位和虚拟对象运动以及可见性的变化。
　　后面讨论的内容，很大程度上要依赖于本章。</FONT>