计算机游戏概论3D基本算法.ppt

1、本 章 重 点,9-1 3D坐标系 9-2 坐标矩阵 9-3 投影转换 9-4 裁剪 9-5 隐藏面消除,9-1 3D坐标系,坐标转换的作用是用来产生对象让我们可以看到，其中不同的坐标系统所呈现出来的方式会有所不同，如同我们以不同的角度去观看一个特定的目标，以不同角度所看到的对象显示效果会有所不同。,9.1.1 坐标转换,坐标系统必须要有一个基本的原点位置，从原点再延伸出去两个或三个坐标轴，形成一个特定的空间，这个空间即是我们所谓的2D空间或3D空间。,如果在空间中形成了两个以上的坐标系统，我们就必须要使用其中的一个坐标系统来描述其它不同的坐标系统，这些不同的坐标系统必须要经过一些特殊的转换才

2、能让这个坐标系统所接受，而这种转换的过程我们就称为坐标转换。,9.1.2 Model坐标系统,即是物体本身中的坐标环境，物体本身也有一个原点坐标，而物体其它的参考顶点是由原点所衍生出来的，如下图所示：,9.1.3 World坐标系统,在3D的世界里，有几个目标物体就会有几个Model坐标系统，而这些Model坐标又不能表示自己在3D世界里的真正位置，所以必须再定义出另外一个可供3D世界里的物体参考之坐标系统，并且使得所有的物体可以正确地被摆放自己应该的位置坐标上，这种另外再定义出来的坐标系统则称为World坐标系统。,9.1.4 View坐标系统,当我们有了物体本身的Model坐标系统与能够表

3、现物体在3D世界的位置坐标之World坐标系统，接下来必须要有一个观看上述两者的坐标系统，这样屏幕的显示才会有依据，而这个可以观看的坐标系统我们称为View坐标系统。,9.1.5 坐标转换,在3D世界中，坐标转换过程是相当复杂的，它必须经过4个不同的转换步骤，最后才能显示在屏幕上，这才是我们所要的画面。流程：,Model坐标系统,World坐标系统,View坐标系统,投影空间坐标,Projection transform,最后的二维坐标,Dispaly,Viewport参数,9-2 坐标矩阵,矩阵的表示方式是以4*4矩阵来呈现的，因为这种矩阵的表现方式可以用来表示平移、旋转及缩放等三种转换功能

4、，而这就已经包含了3D世界的转换型式了。这一种矩阵的运算对象及所产生的结果坐标，我们称之为齐次坐标(Homogeneous Coordinate)。,9.2.1 齐次坐标,齐次坐标具有四个不同的元素，简称四元素，其表示法为（x,y,z,w），如果将齐次坐标表示成3D坐标的话，其表示法则为（x/w,y/w,z/w）。通常w元素都会被设成1。 W用意是用来表示一个比例因子。,9.2.2 矩阵平移（Translation）,即是物体在3D世界里向着某一个向量方向移动，如下图,矩阵平移运算的表示法如下列所示：,9.2.3 矩阵旋转（Rotation）,定义是3D世界里的某一个物体绕着一个特定的坐标轴旋

5、转，如下图所示：,绕着x轴旋转,绕着y轴旋转,绕着z轴旋转,X,Y,(x,y),a,(x,y),Y=r*sin（a+ ） =r*sina*cos +r*sina*cos* =x*cos +y*cos ,9.2.4 矩阵缩放（Scaling）,即是物体沿着某一个轴进行一定比例缩放的运算。如下图所示：,物体向着X轴放大,矩阵的表示法如下列所示：,希腊字母 伊塔,9.2.5 矩阵的结合律,平移矩阵为A、旋转矩阵为B、缩放矩阵为C，而原来的顶点坐标为K、最后得到的顶点坐标为K，其矩阵相乘的公式如下列所示：,K=CBAK,其实我们可以将这种特定的矩阵相乘过程简化，因为矩阵相乘的运算是可以符合数学上所说的

6、结合律，也就是将A、B、C三个矩阵先结合成另一个矩阵，如下：,=CBA K=K,9.2.6 Direct3D矩阵,在Direct3D定义里，矩阵被宣告成一个名为D3DMATRIX的数据结构，如下：,typedef struct _D3DMATRIX ,union ,struct ,float _11, _12, _13, _14;,float _21, _22, _23, _24;,float _31, _32, _33, _34;,float _41, _42, _43, _44;,;,float m44;,;, D3DMATRIX;,#define D3D_OVERLOADS #inclu

7、de D3DMATRIX mat; /下面三种表示方式的意思都是一样的 mat._13 = 0.8f; mat13 = 0.8f; mat(1,3) = 0.8f;,索引值从“0”开始，先row，后col,如果我们要建立一个平移的矩阵，其表示法如下图所示：,在程序代码里，我们就可以将它编写成如下列所示：,D3DMATRIX mat = 1, 0, 0, D3DVAL(4.0) 0, 1, 0, D3DVAL(8.0) 0, 0, 1, D3DVAL(16.0) 0, 0, 0, 1 ;,9.2.7 向量表示法,在Direct3D定义里，向量被声明成一个名为D3DVECTOR的数据结构，如下列所

8、示：,typedef struct _D3DVECTOR ,float x;,float y;,float z; D3DVECTOR;,矩阵相乘,/将矩阵pM1与矩阵pM2相乘之后的结果传给矩阵pOut,D3DXMATRIX* D3DXMatrixMultiply(,D3DXMATRIX* pOut,CONST D3DXMATRIX* pM1,CONST D3DXMATRIX* pM2 );,基本的矩阵及向量运算函数,向量相乘,/将向量pV1与向量pV2相乘之后的结果传给向量pOut,D3DXVECTOR3* D3DXVec3Cross(,D3DXVECTOR3* pOut,CONST D3D

9、XVECTOR3* pV1,CONST D3DXVECTOR3* pV2 );,基本的矩阵及向量运算函数,两个向量进行dot product的运算,FLOAT D3DXVec3Dot(,CONST D3DXVECTOR3* pV1,CONST D3DXVECTOR3* pV2 );,基本的矩阵及向量运算函数,计算向量的长度,FLOAT D3DXVec3Length(,CONST D3DXVECTOR3* pV );,基本的矩阵及向量运算函数,计算向量的单位向量,D3DXVECTOR3* D3DXVec3Normalize(,D3DXVECTOR3* pOut,CONST D3DXVECTOR3

10、* pV );,基本的矩阵及向量运算函数,向量相加,D3DXVECTOR3* D3DXVec3Add(,D3DXVECTOR3* pOut,CONST D3DXVECTOR3* pV1,CONST D3DXVECTOR3* pV2 );,基本的矩阵及向量运算函数,9-3 投影转换,将三维的坐标系统转换成二维的坐标，并将3D世界里的坐标单位映像到2D屏幕的坐标单位上，才能在计算机屏幕上看到所谓的3D世界，而这整个转换的过程我们称之为投影。,9.3.1 平行投影,当我们省略掉三维空间里的一维元素之后，我们就可以得到了一个平行投影的图形坐标，在这个时候，三维空间中的所有顶点都会从三维空间映像到2D平

11、面的并行线上，因此我们就称这种方式为平行投影。,平行投影,我们可以在投影线与投影面交叉角度的基础上更进一步地细分平行投影。如果交叉的角度是直角的话，我们则称之为正交投影（orthographic）；不是直角的话，我们则称为倾斜投影（oblique）。,9.3.2 透视投影,透视投影所建立出来的对象投影图像之大小必须依赖对象与观察者的距离。,原点与图像上的顶点相联系之关系。如下图所示：,无深度投影,具深度投影,焦点距离越小则视角宽度越广，而焦点距离越大则视角宽度越窄。,9-4 裁剪,2D裁剪 裁剪是对于某种图形做出修剪的动作，其目的是为了让看不见的顶点不加以描绘，以提升执行的速度。,第三种剪裁法

12、,第二种剪裁法,第一种剪裁法,线段的裁剪,线段裁剪的方法可以分析图形的相对约束位置，并且找出符合这一点的图形部分。在线段裁剪的情况下，它需要找出其交叉点或线段与裁剪边界的交叉点，通常不是直接就能够把这种交叉发生的地方看得一清二楚的。如下图所示：,在光栅处理阶段之前，先进行裁剪处理，适合处理简单的图形单位。（如多边形） 在光栅处理阶段同时进行，适合于复杂图形。 当裁剪区域中几何结构比较复杂时，选择较大的Buffer光栅图形。然后在Buffer中选择在该复杂裁剪区域内部的图形。,光栅处理：投影转换把物体图形坐标从3D空间映射到屏幕的2D空间，这些图形必须在2D空间中被绘制，使观察者可见。既然我们考

13、虑的是由一系列整齐地镶嵌的小方块组成的光栅图形，因此我们要确定这种几何像素的模拟描述要如何能够被正确地转换成一系列的离散图形，而这种过程我们称之为“光栅处理”（rasterization）,9.4.2 点的裁剪,点的裁剪可以利用这4个有限线段的约束来检查点的坐标是否应该要被裁剪。,9.4.3 线段的裁剪,我们可以将线段的裁剪扩展到上述方法，然而增加内循环的复杂性。 这种线段裁剪方法可以分析图形的相对约束位置，并且找出符合这一点的图形部分。在线段裁剪的情况下，它需要找出交叉点或线段与裁剪边界的交叉点，通常不是直接就能够把这种交叉的地方看清楚。如下图：,剪裁线,剪裁线,剪裁线,剪裁线,区域外编码（

14、region out code）,第一步，区域编码 延长窗口边界，将平面分成9个区域，每个区域用4位二进制代码表示，称为区域码。其作用是识别点相对于裁剪窗口边界的位置。,约定4位码中最右边一位为第1位，则编码规则如下：,1000,0000,1001,1010,0001,0010,0101,0100,0110,left,right,above,below,第二步 ，建立线段端点的区域编码。,设(x,y)是线段端点的坐标，则第1位取,的符号位。,第2位取,的符号位。,第3位取,的符号位。,第4位取,的符号位。,第三步，判断线段与窗口间的位置关系。 （1）若线段两端点的编码均为“ 0000”, 则线

15、段全部位于窗口内。 （2）若线段两端点编码的逻辑“与”不是0000，则线段必位于窗口外。,（3）若根据（1）、（2）不能直接判定线段在窗口内或窗口外，我们需要计算线段与窗口边界的交。由下图可知，这些线段可能穿入窗口的内部，也可能不穿过窗口的内部。,P1,P1,P3,P4,P2,P2,P3,这类线段的处理过程： 将线段的位于窗口外端点与窗口边界进行比较，以确定线段的多大部分被舍弃。对剩余的部分线段继续按（1）、（2）和（3）进行处理。直到线段完全在窗口内或完全在窗口外为止。,具体操作： （1）可以按照left,right, bottom, top的顺序检查线段端点与窗口边界之间的关系。 现通过例

16、子对该算法进行说明。考虑线段P1P2的端点P1,依次检查P1与窗口的左、右和下边界间的位置关系，发现P1点在裁剪窗口的下面。于是求出该线段与窗口底边界的交点P1。这时，线段变为P1P2。由于P2在裁剪窗口之外，通过检查该端点与窗口边界的关系发现，它在窗口的左侧。可以计算出线段P1P2与窗口左边界的交点为P2，该点位于窗口的上部，因此最后的交点为P2。线段P1P2保留。,P1,P1,P3,P4,P2,P2,P3,P2,或,或,类似地，线段与水平边界交点的x坐标为：,其中，,（2） 线段与边界的求交算法 一般地，由(x1, y1)到(x2,y2)的截距式表示可求出该线段与垂直边界交点的y坐标为：,

17、剪裁线,Y1=y2-y（x2-x1）/ x,对于图形的应用而言，不涉及到乘法或除法的方法通常可以增加运算速度，在裁剪这种情况中，我们可以使用“二元搜寻”这种方法来运算。,第一次运算的终点,第二次运算的终点,第三次运算的终点,9.4.4 多边形的裁剪,在矩形屏幕情形下，我们将每一个裁剪边缘计算裁剪例程一次，最后获得符合所有强制标准的多边形。如下图所示：,原来线段,剪裁后线段,3D裁剪,9-5隐藏面消除,背面剔除(back culling)算法 许多三维物体中，它们所占据的空间都被一些连续的表面所包围着。当我们观察这些物体的时候，只能看到这些包围表面中的正面部分，背面则无法看到。背面剔除算法就是将

18、这些我们看不到的背面多边形去除掉。如下图所示：,我们只能看见三为物体中的其中一面而已,凸面体,凹面体,这个面被其它面挡住了,对于透视投影而言，投影线会相交在观察者的眼中，它们的方向是不同的。我们可以在世界或观察空间中的任意一点上构造一个指向观察者眼睛的向量，并且使它指向该点的方向，如此一来，我们就得到了这一点的观察方向了。如下图所示：,9.5.2 排序,另一种方法也可以用来剔除这些看不到的顶点，其方法可以充分的利用图形硬件的缓冲储存结构来加速其运算。不管场景中的多边形有没有挡住其它的多边形，只要按照从后面到前面的顺序光栅化图形就可以正确的显示所有可见的图形了，也就是将离观察者最近的一个多边形最

19、后进行光栅化处理。这种方法就是我们称它为画家算法。,从前边节已经看到，一般多边形模型隐藏面消除的代价极高，然而在大多数情况下，我们要处理的对象有一些特殊的属性，利用这些属性可以减轻隐藏面的消除工作量。例如在以“高度值运算“来处理表面的地形曲面时。就很容易地获得多边形视点从前到后的顶点顺序。 由于这种表面方法具有矩形自然的属性，地形就可以被分割成许多正方形的单元格。,9.5.3 八叉树,当观察者在一些单元边界内位于虚拟地形表面上或表面的上方。我们能够把整个的地形分割为四个规则的子地形，如下图。,我们可以将地形单元的光栅处理顺序编列成如下所示：,第一次：1、2、3、4。第二次：5、6、7、8、9、

20、10。第三次：11、12、13、14、15、16;第四次：17、18、19、20、21、22、23、24、25。,光栅处理的顺序将会依据观察者在场景中角度的不同而有所改变。如下图所示：,有这种规律的特性，我们可以将它作为由后到前寻找地形顺序的依据，而这种特性就可以使用“八叉树”的存储规则，或者也可以用在空间占有的矩形来描述映射。 在这种情况下，我们利用类似高度场的方法，扩展成为处理三维顶点而不是二维顶点。,八叉树的处理规则就是利用递归结构的方式来进行的，在每个细分的层次上有着同样规则的属性。因此，在每个层次上我们可以利用同样的编列顺序，以获得整个结构元素由后到前的顺序依据。,9.5.4 二元空

21、间分割树,二元空间分割树，Binary Space Partitioning Tree是一种空间分割的方法，简称BSP Tree。 BSP Tree在一开始将资料文件读进来的时候，就将整个数据文件中的数据（即是墙的数值）先建成一个二元树的数据结构。如下图所示：,Front,back,Node中的数据代表一面墙,当地形数据被读进来时，BSP Tree会同时被建立（只一次）,当视点开始移动时，平面景象就必须被重新绘制。而重绘就是以视点为基础，对此BSP Tree加以分析，只要在BSP Tree中，且位于此视点前方，它就会被存放在一个串行当中，最后我们只要按照串行的顺序逐个地将它们绘制在平面上就可以

22、了。 另一种方法：利用深度测试来显示室内环境及场景。,A区域显示在X多边形上,B区域显示在Y多边形上,此图的现象在现实中视不可能存在的,使用OpenGL或Direct3D的函数库去显示此多边形，它们就会自动做深度探测（Z-Buffer），但是效率极差，这就是要使用二元空间分割树的原因。 二元空间分割树可以利用节点（Node）来快速和有效的排序多边形，而且在计算机运行时，我们又可以简单的了解camera到最远多边形之间的关系。,需要深度测试,当二元空间分割树建立时，必须完成下面几项任务：,从函数中选择一个多边形。 通过平面方程（Ax+Bx+Cx+D=0）转换多边形为平面数据。 通过函数分类所有的

23、多边形（前、后、重叠、穿越）。 分割跨越平面的多边形。 如果任何一个多边形在平面的前方，回到（1）并处理这些多边形。 如果任何一个多边形在平面的后方，回到（1）并处理这些多边形。 在目前的节点中加入与平面重叠的多边形与串中。,详细的二元素,再利用D平面为主Node来做分割的动作。在分类和切割后的结果如下图所示：,现在的二元空间分割树看起来就如下图：,再继续分割上述二元树结构的话，二元树结构就会变成如下图所示：,当映射多边形时，我们可以利用camera的位置与每个平面比较，然后再以距离为基本顺序原则。 一开始，基本节点是B多边形，接着执行下面步骤：,(1)求出平面与camera之间的距离。 (2)如果距离大于0： 移向后面节点并回到步骤（1）。 显示目前节点内的多边形。 移向前面节点并回到步骤（1） (3)如果（2）是错误的： 移向前面节点并回到步骤（1） 显示目前节点内的多边形。 移向后面节点并回到步骤（1）,完成上面步骤，绘