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

《计算机游戏概论3D基本算法.ppt》由会员分享，可在线阅读，更多相关《计算机游戏概论3D基本算法.ppt（108页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第九章 3D基本算法结束本本 章章 重重 点点n9-1 9-1 3D3D坐标系坐标系n9-2 9-2 坐标矩阵坐标矩阵n9-3 9-3 投影转换投影转换n9-4 9-4 裁剪裁剪n9-5 9-5 隐藏面消除隐藏面消除第九章 3D基本算法结束9-1 3D坐标系坐标系n坐标转换的作用是用来产生对象让我们可以看到，其中不同的坐标系统所呈现出来的方式会有所不同，如同我们以不同的角度去观看一个特定的目标，以不同角度所看到的对象显示效果会有所不同。第九章 3D基本算法结束9.1.1 9.1.1 坐标转换坐标转换n坐标系统必须要有一个基本的原点位置，从原点再延伸出去两个或三个坐标轴，形成一个特定的空间，这个

2、空间即是我们所谓的2D空间或3D空间。第九章 3D基本算法结束n如果在空间中形成了两个以上的坐标系统，我们就必须要使用其中的一个坐标系统来描述其它不同的坐标系统，这些不同的坐标系统必须要经过一些特殊的转换才能让这个坐标系统所接受，而这种转换的过程我们就称为坐标转换。第九章 3D基本算法结束9.1.2 Model9.1.2 Model坐标系统坐标系统n即是物体本身中的坐标环境，物体本身也有一即是物体本身中的坐标环境，物体本身也有一个原点坐标，而物体其它的参考顶点是由原点个原点坐标，而物体其它的参考顶点是由原点所衍生出来的，如下图所示：所衍生出来的，如下图所示：第九章 3D基本算法结束9.1.3

3、World9.1.3 World坐标系统坐标系统n在在3D3D的世界里，有几个目标物体就会有几个的世界里，有几个目标物体就会有几个ModelModel坐标系统，而这些坐标系统，而这些ModelModel坐标又不能表坐标又不能表示自己在示自己在3D3D世界里的真正位置，所以必须再世界里的真正位置，所以必须再定义出另外一个可供定义出另外一个可供3D3D世界里的物体参考之世界里的物体参考之坐标系统，并且使得所有的物体可以正确地坐标系统，并且使得所有的物体可以正确地被摆放自己应该的位置坐标上，这种另外再被摆放自己应该的位置坐标上，这种另外再定义出来的坐标系统则称为定义出来的坐标系统则称为WorldWo

4、rld坐标系统坐标系统。第九章 3D基本算法结束9.1.4 View9.1.4 View坐标系统坐标系统n当我们有了物体本身的当我们有了物体本身的ModeModel l坐标系统与坐标系统与能够表现物体在能够表现物体在3D3D世界的位置坐标之世界的位置坐标之WorldWorld坐标系统，接下来必须要有一个观看上述坐标系统，接下来必须要有一个观看上述两者的坐标系统，这样屏幕的显示才会有依两者的坐标系统，这样屏幕的显示才会有依据，而这个可以观看的坐标系统我们称为据，而这个可以观看的坐标系统我们称为ViewView坐标系统。坐标系统。第九章 3D基本算法结束9.1.5 9.1.5 坐标转换坐标转换n在

5、在3D世界中，坐标转换过程是相当复杂的，世界中，坐标转换过程是相当复杂的，它必须经过它必须经过4个不同的转换步骤，最后才个不同的转换步骤，最后才能显示在屏幕上，这才是我们所要的画面。能显示在屏幕上，这才是我们所要的画面。流程：流程：Model坐标系统World坐标系统View坐标系统投影空间坐标Projectiontransform最后的二维坐标DispalyViewport参数第九章 3D基本算法结束9-29-2 坐标矩阵坐标矩阵 n矩阵的表示方式是以4*4矩阵来呈现的，因为这种矩阵的表现方式可以用来表示平移、旋转及缩放等三种转换功能，而这就已经包含了3D世界的转换型式了。这一种矩阵的运算对

6、象及所产生的结果坐标，我们称之为齐次坐标(Homogeneous Coordinate)。第九章 3D基本算法结束9.2.1 9.2.1 齐次坐标齐次坐标n齐次坐标具有四个不同的元素，简称齐次坐标具有四个不同的元素，简称四元素，其表示法为（四元素，其表示法为（x,y,z,wx,y,z,w），），如果将齐次坐标表示成如果将齐次坐标表示成3D3D坐标的话，其表坐标的话，其表示法则为（示法则为（x/w,y/w,z/wx/w,y/w,z/w）。通常）。通常w w元素都元素都会被设成会被设成1 1。nW W用意是用来表示一个比例因子。用意是用来表示一个比例因子。第九章 3D基本算法结束9.2.2 9.2

7、.2 矩阵平移（矩阵平移（TranslationTranslation）n即是物体在即是物体在3D3D世界里向着某一个向量方向世界里向着某一个向量方向移动，如下图移动，如下图 第九章 3D基本算法结束n矩阵平移运算的表示法如下列所示：矩阵平移运算的表示法如下列所示：第九章 3D基本算法结束9.2.3 9.2.3 矩阵旋转（矩阵旋转（RotationRotation）n定义是定义是3D3D世界里的某一个物体绕着一个特世界里的某一个物体绕着一个特定的坐标轴旋转，如下图所示：定的坐标轴旋转，如下图所示：第九章 3D基本算法结束n绕着绕着x x轴旋转轴旋转 第九章 3D基本算法结束n绕着绕着y y轴旋

8、转轴旋转 第九章 3D基本算法结束n绕着绕着z z轴旋转轴旋转 第九章 3D基本算法结束XY(x,y)a(x,y)Y=r*sin（a+）=r*sina*cos+r*sina*cos*=x*cos+y*cos第九章 3D基本算法结束9.2.4 9.2.4 矩阵缩放（矩阵缩放（ScalingScaling）n即是物体沿着某一个轴进行一定比例缩放即是物体沿着某一个轴进行一定比例缩放的运算。如下图所示：的运算。如下图所示：物体向着物体向着X X轴放大轴放大第九章 3D基本算法结束n矩阵的表示法如下列所示：矩阵的表示法如下列所示：希腊字母伊塔第九章 3D基本算法结束9.2.5 9.2.5 矩阵的结合律矩

9、阵的结合律 n平移矩阵为平移矩阵为A A、旋转矩阵为、旋转矩阵为B B、缩放矩阵为、缩放矩阵为C C，而，而原来的顶点坐标为原来的顶点坐标为K K、最后得到的顶点坐标为、最后得到的顶点坐标为KK，其矩阵相乘的公式如下列所示：，其矩阵相乘的公式如下列所示：K=CBAK第九章 3D基本算法结束n其实我们可以将这种特定的矩阵相乘过程简其实我们可以将这种特定的矩阵相乘过程简化，因为矩阵相乘的运算是可以符合数学上化，因为矩阵相乘的运算是可以符合数学上所说的结合律，也就是将所说的结合律，也就是将A A、B B、C C三个矩三个矩阵先结合成另一个矩阵，如下：阵先结合成另一个矩阵，如下：=CBA=CBAK=K

10、=K K第九章 3D基本算法结束9.2.6 Direct3D9.2.6 Direct3D矩阵矩阵n在在Direct3DDirect3D定义里，矩阵被宣告成一个名定义里，矩阵被宣告成一个名为为D3DMATRIXD3DMATRIX的数据结构，如下：的数据结构，如下：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;第九章 3D基本算法结束#define D3

11、D_OVERLOADS#define D3D_OVERLOADS#include#include D3DMATRIX mat;D3DMATRIX mat;/下面三种表示方式的意思都是一样的下面三种表示方式的意思都是一样的mat._13=0.8f;mat._13=0.8f;mat13=0.8f;mat13=0.8f;mat(1,3)=0.8f;mat(1,3)=0.8f;索引值从“0”开始，先row，后col第九章 3D基本算法结束n如果我们要建立一个平移的矩阵，其表示如果我们要建立一个平移的矩阵，其表示法如下图所示：法如下图所示：第九章 3D基本算法结束n在程序代码里，我们就可以将它编写成如在

12、程序代码里，我们就可以将它编写成如下列所示：下列所示：D3DMATRIX mat=D3DMATRIX mat=1,0,0,D3DVAL(4.0)1,0,0,D3DVAL(4.0)0,1,0,D3DVAL(8.0)0,1,0,D3DVAL(8.0)0,0,1,D3DVAL(16.0)0,0,1,D3DVAL(16.0)0,0,0,10,0,0,1;第九章 3D基本算法结束9.2.7 9.2.7 向量表示法向量表示法 n在在Direct3DDirect3D定义里，向量被声明成一个名定义里，向量被声明成一个名为为D3DVECTORD3DVECTOR的数据结构，如下列所的数据结构，如下列所示：示：ty

13、pedef struct _D3DVECTOR float x;float y;float z;D3DVECTOR;第九章 3D基本算法结束矩阵相乘矩阵相乘/将矩阵pM1与矩阵pM2相乘之后的结果传给矩阵pOutD3DXMATRIX*D3DXMatrixMultiply(D3DXMATRIX*pOut,CONSTD3DXMATRIX*pM1,CONSTD3DXMATRIX*pM2);基本的矩阵及向量运算函数基本的矩阵及向量运算函数第九章 3D基本算法结束向量相乘向量相乘 /将向量pV1与向量pV2相乘之后的结果传给向量pOutD3DXVECTOR3*D3DXVec3Cross(D3DXVECT

14、OR3*pOut,CONSTD3DXVECTOR3*pV1,CONSTD3DXVECTOR3*pV2);基本的矩阵及向量运算函数基本的矩阵及向量运算函数第九章 3D基本算法结束两个向量进行两个向量进行dot productdot product的运算的运算 FLOATD3DXVec3Dot(CONSTD3DXVECTOR3*pV1,CONSTD3DXVECTOR3*pV2);基本的矩阵及向量运算函数基本的矩阵及向量运算函数第九章 3D基本算法结束计算向量的长度计算向量的长度 FLOATD3DXVec3Length(CONSTD3DXVECTOR3*pV);基本的矩阵及向量运算函数基本的矩阵及向

15、量运算函数第九章 3D基本算法结束计算向量的单位向量计算向量的单位向量 D3DXVECTOR3*D3DXVec3Normalize(D3DXVECTOR3*pOut,CONSTD3DXVECTOR3*pV);基本的矩阵及向量运算函数基本的矩阵及向量运算函数第九章 3D基本算法结束向量相加向量相加 D3DXVECTOR3*D3DXVec3Add(D3DXVECTOR3*pOut,CONSTD3DXVECTOR3*pV1,CONSTD3DXVECTOR3*pV2);基本的矩阵及向量运算函数基本的矩阵及向量运算函数第九章 3D基本算法结束9-39-3 投影转换投影转换 n将三维的坐标系统转换成二维的

16、坐标，将三维的坐标系统转换成二维的坐标，并将并将3D3D世界里的坐标单位映像到世界里的坐标单位映像到2D2D屏幕屏幕的坐标单位上，才能在计算机屏幕上看的坐标单位上，才能在计算机屏幕上看到所谓的到所谓的3D3D世界，而这整个转换的过程世界，而这整个转换的过程我们称之为投影。我们称之为投影。第九章 3D基本算法结束9.3.1 9.3.1 平行投影平行投影 n当我们省略掉三维空间里的一维元素之后，当我们省略掉三维空间里的一维元素之后，我们就可以得到了一个平行投影的图形坐标，我们就可以得到了一个平行投影的图形坐标，在这个时候，三维空间中的所有顶点都会从在这个时候，三维空间中的所有顶点都会从三维空间映像

17、到三维空间映像到2D2D平面的并行线上，因此我平面的并行线上，因此我们就称这种方式为平行投影。们就称这种方式为平行投影。第九章 3D基本算法结束n平行投影平行投影第九章 3D基本算法结束n我们可以在投影线与投影面交叉角度的基础上更进一步地细分平行投影。如果交叉的角度是直角的话，我们则称之为正交投影（orthographic）；不是直角的话，我们则称为倾斜投影（oblique）。第九章 3D基本算法结束 9.3.2 9.3.2 透视投影透视投影 n透视投影所建立出来的对象投影图像之大透视投影所建立出来的对象投影图像之大小必须依赖对象与观察者的距离。小必须依赖对象与观察者的距离。第九章 3D基本算

18、法结束第九章 3D基本算法结束n原点与图像上的顶点相联系之关系。如下原点与图像上的顶点相联系之关系。如下图所示：图所示：第九章 3D基本算法结束无深度投影无深度投影具深度投影具深度投影第九章 3D基本算法结束n焦点距离越小则视角宽度越广，而焦点距焦点距离越小则视角宽度越广，而焦点距离越大则视角宽度越窄离越大则视角宽度越窄。第九章 3D基本算法结束9-4 9-4 裁剪裁剪 n2D2D裁剪裁剪n裁剪是对于某种图形做出修剪的动作，其裁剪是对于某种图形做出修剪的动作，其目的是为了让看不见的顶点不加以描绘，目的是为了让看不见的顶点不加以描绘，以提升执行的速度。以提升执行的速度。第九章 3D基本算法结束第

19、三种剪裁法第三种剪裁法第二种剪裁法第二种剪裁法第一种剪裁法第一种剪裁法第九章 3D基本算法结束线段的裁剪线段的裁剪 n线段裁剪的方法可以分析图形的相对约束位置，并且找出符合这一点的图形部分。在线段裁剪的情况下，它需要找出其交叉点或线段与裁剪边界的交叉点，通常不是直接就能够把这种交叉发生的地方看得一清二楚的。如下图所示：第九章 3D基本算法结束1.在光栅处理阶段之前，先进行裁剪处理，在光栅处理阶段之前，先进行裁剪处理，适合处理简单的图形单位。（如多边形）适合处理简单的图形单位。（如多边形）2.在光栅处理阶段同时进行，适合于复杂在光栅处理阶段同时进行，适合于复杂图形。图形。3.当裁剪区域中几何结构

20、比较复杂时，选当裁剪区域中几何结构比较复杂时，选择较大的择较大的Buffer光栅图形。然后在光栅图形。然后在Buffer中选择在该复杂裁剪区域内部的图形。中选择在该复杂裁剪区域内部的图形。第九章 3D基本算法结束n光栅处理：投影转换把物体图形坐标从光栅处理：投影转换把物体图形坐标从3D空间映射到屏幕的空间映射到屏幕的2D空间，这些图形必须空间，这些图形必须在在2D空间中被绘制，使观察者可见。既然空间中被绘制，使观察者可见。既然我们考虑的是由一系列整齐地镶嵌的小方我们考虑的是由一系列整齐地镶嵌的小方块组成的光栅图形，因此我们要确定这种块组成的光栅图形，因此我们要确定这种几何像素的模拟描述要如何能

21、够被正确地几何像素的模拟描述要如何能够被正确地转换成一系列的离散图形，而这种过程我转换成一系列的离散图形，而这种过程我们称之为们称之为“光栅处理光栅处理”（rasterization）第九章 3D基本算法结束9.4.2 9.4.2 点的裁剪点的裁剪n点的裁剪可以利用这点的裁剪可以利用这4 4个有限线段的约束个有限线段的约束来检查点的坐标是否应该要被裁剪。来检查点的坐标是否应该要被裁剪。第九章 3D基本算法结束9.4.3 9.4.3 线段的裁剪线段的裁剪n我们可以将线段的裁剪扩展到上述方法，我们可以将线段的裁剪扩展到上述方法，然而增加内循环的复杂性。然而增加内循环的复杂性。n这种线段裁剪方法可以

22、分析图形的相对约这种线段裁剪方法可以分析图形的相对约束位置，并且找出符合这一点的图形部分。束位置，并且找出符合这一点的图形部分。在线段裁剪的情况下，它需要找出交叉点在线段裁剪的情况下，它需要找出交叉点或线段与裁剪边界的交叉点，通常不是直或线段与裁剪边界的交叉点，通常不是直接就能够把这种交叉的地方看清楚。如下接就能够把这种交叉的地方看清楚。如下图：图：第九章 3D基本算法结束剪裁线剪裁线剪裁线剪裁线第九章 3D基本算法结束剪裁线剪裁线剪裁线剪裁线第九章 3D基本算法结束区域外编码（区域外编码（region out coderegion out code）第一步，区域编码第一步，区域编码延延长长窗

23、窗口口边边界界，将将平平面面分分成成9 9个个区区域域，每每个个区区域域用用4 4位位二二进进制制代代码码表表示示，称称为为区区域域码码。其其作作用用是是识识别别点点相相对对于于裁裁剪窗口边界的位置。剪窗口边界的位置。约定约定4 4位码中最右边一位为第位码中最右边一位为第1 1位，则编码规则如下：位，则编码规则如下：100000001001101000010010010101000110leftrightabovebelow第九章 3D基本算法结束第二步第二步 ，建立线段端点的区域编码。，建立线段端点的区域编码。设设(x,y)(x,y)是线段端点的坐标，则第是线段端点的坐标，则第1 1位取位取

24、的符号位。的符号位。第第2 2位取位取的符号位。的符号位。第第3 3位取位取的符号位的符号位。第第4 4位取位取的符号位的符号位。第三步，判断线段与窗口间的位置关系。第三步，判断线段与窗口间的位置关系。（1 1）若线段两端点的编码均为）若线段两端点的编码均为“00000000”,则线段全部位于窗口内。则线段全部位于窗口内。（2 2）若线段两端点编码的逻辑）若线段两端点编码的逻辑“与与”不是不是00000000，则线段必位于窗口，则线段必位于窗口外。外。第九章 3D基本算法结束（3 3）若根据（）若根据（1 1）、（）、（2 2）不能直接判定线段在窗口内或窗口外，我们需要）不能直接判定线段在窗口

25、内或窗口外，我们需要计算线段与窗口边界的交。由下图可知，这些线段可能穿入窗口的内部，也计算线段与窗口边界的交。由下图可知，这些线段可能穿入窗口的内部，也可能不穿过窗口的内部。可能不穿过窗口的内部。P1P1P3P4P2P2P3这类线段的处理过程：这类线段的处理过程：将线段的位于窗口外端点与窗口边将线段的位于窗口外端点与窗口边界进行比较，以确定线段的多大部界进行比较，以确定线段的多大部分被舍弃。对剩余的部分线段继续分被舍弃。对剩余的部分线段继续按（按（1 1）、（）、（2 2）和（）和（3 3）进行处理。）进行处理。直到线段完全在窗口内或完全在窗直到线段完全在窗口内或完全在窗口外为止。口外为止。第

26、九章 3D基本算法结束具体操作：具体操作：（1 1）可以按照）可以按照left,right,bottom,topleft,right,bottom,top的顺序的顺序检查线段端点与窗口边界之间的关系。检查线段端点与窗口边界之间的关系。现通过例子对该算法进行说明。考虑线段现通过例子对该算法进行说明。考虑线段P P1 1P P2 2的端的端点点P P1 1,依次检查依次检查P P1 1与窗口的左、右和下边界间的位与窗口的左、右和下边界间的位置关系，发现置关系，发现P P1 1点在裁剪窗口的下面。于是求出该点在裁剪窗口的下面。于是求出该线段与窗口底边界的交点线段与窗口底边界的交点P P1 1。这时，

27、线段变为。这时，线段变为P P1 1P P2 2。由于。由于P P2 2在裁剪窗口之外，通过检查该端点在裁剪窗口之外，通过检查该端点与窗口边界的关系发现，它在窗口的左侧。可以与窗口边界的关系发现，它在窗口的左侧。可以计算出线段计算出线段P P1 1P P2 2与窗口左边界的交点为与窗口左边界的交点为P P2 2，该点，该点位于窗口的上部，因此最后的交点为位于窗口的上部，因此最后的交点为P P2 2。线段。线段P P1 1P P2 2保留。保留。P1P1P3P4P2P2P3P2第九章 3D基本算法结束或或或或类似地，线段与水平边界交点的类似地，线段与水平边界交点的x x坐标为：坐标为：其中，其中

28、，（2 2）线段与边界的求交算法线段与边界的求交算法一般地，由一般地，由(x(x1 1,y,y1 1)到到(x(x2 2,y,y2 2)的截距式表示可求出该线段与垂直的截距式表示可求出该线段与垂直边界交点的边界交点的y y坐标为：坐标为：第九章 3D基本算法结束剪裁线剪裁线Y1=y2-y（x2-x1）/x第九章 3D基本算法结束n对于图形的应用而言，不涉及到乘法或除对于图形的应用而言，不涉及到乘法或除法的方法通常可以增加运算速度，在裁剪法的方法通常可以增加运算速度，在裁剪这种情况中，我们可以使用这种情况中，我们可以使用“二元搜寻二元搜寻”这种方法来运算。这种方法来运算。第九章 3D基本算法结束

29、第一次运算的终点第二次运算的终点第三次运算的终点第九章 3D基本算法结束9.4.4 9.4.4 多边形的裁剪多边形的裁剪第九章 3D基本算法结束n在矩形屏幕情形下，我们将每一个裁剪边缘在矩形屏幕情形下，我们将每一个裁剪边缘计算裁剪例程一次，最后获得符合所有强制计算裁剪例程一次，最后获得符合所有强制标准的多边形。如下图所示：标准的多边形。如下图所示：第九章 3D基本算法结束第九章 3D基本算法结束原来线段原来线段剪裁后线段剪裁后线段第九章 3D基本算法结束第九章 3D基本算法结束3D3D裁剪裁剪 第九章 3D基本算法结束第九章 3D基本算法结束第九章 3D基本算法结束第九章 3D基本算法结束9-

30、59-5隐藏面消除隐藏面消除 n背面剔除背面剔除(back(back culling)culling)算法算法n许多三维物体中，它们所占据的空间都被一些连续的表面所包围着。当我们观察这些物体的时候，只能看到这些包围表面中的正面部分，背面则无法看到。背面剔除算法就是将这些我们看不到的背面多边形去除掉。如下图所示：第九章 3D基本算法结束我们只能看见三为物体中的其中一面而已我们只能看见三为物体中的其中一面而已第九章 3D基本算法结束凸面体凸面体凹面体凹面体第九章 3D基本算法结束这个面被其它面挡住了这个面被其它面挡住了第九章 3D基本算法结束第九章 3D基本算法结束n对于透视投影而言，投影线会相交

31、在观察者对于透视投影而言，投影线会相交在观察者的眼中，它们的方向是不同的。我们可以在的眼中，它们的方向是不同的。我们可以在世界或观察空间中的任意一点上构造一个指世界或观察空间中的任意一点上构造一个指向观察者眼睛的向量，并且使它指向该点的向观察者眼睛的向量，并且使它指向该点的方向，如此一来，我们就得到了这一点的观方向，如此一来，我们就得到了这一点的观察方向了。如下图所示：察方向了。如下图所示：第九章 3D基本算法结束第九章 3D基本算法结束9.5.2 9.5.2 排序排序 n另一种方法也可以用来剔除这些看不到的顶另一种方法也可以用来剔除这些看不到的顶点，其方法可以充分的利用图形硬件的缓冲点，其方

32、法可以充分的利用图形硬件的缓冲储存结构来加速其运算。不管场景中的多边储存结构来加速其运算。不管场景中的多边形有没有挡住其它的多边形，只要按照从后形有没有挡住其它的多边形，只要按照从后面到前面的顺序光栅化图形就可以正确的显面到前面的顺序光栅化图形就可以正确的显示所有可见的图形了，也就是将离观察者最示所有可见的图形了，也就是将离观察者最近的一个多边形最后进行光栅化处理。这种近的一个多边形最后进行光栅化处理。这种方法就是我们称它为画家算法。方法就是我们称它为画家算法。第九章 3D基本算法结束第九章 3D基本算法结束n从前边节已经看到，一般多边形模型隐藏面从前边节已经看到，一般多边形模型隐藏面消除的代

33、价极高，然而在大多数情况下，我消除的代价极高，然而在大多数情况下，我们要处理的对象有一些特殊的属性，利用这们要处理的对象有一些特殊的属性，利用这些属性可以减轻隐藏面的消除工作量。例如些属性可以减轻隐藏面的消除工作量。例如在以在以“高度值运算高度值运算“来处理表面的地形曲面来处理表面的地形曲面时。就很容易地获得多边形视点从前到后的时。就很容易地获得多边形视点从前到后的顶点顺序。顶点顺序。n由于这种表面方法具有矩形自然的属性，地由于这种表面方法具有矩形自然的属性，地形就可以被分割成许多正方形的单元格。形就可以被分割成许多正方形的单元格。9.5.3 9.5.3 八叉树八叉树 第九章 3D基本算法结束

34、n当观察者在一些单元边界内位于虚拟地形表当观察者在一些单元边界内位于虚拟地形表面上或表面的上方。我们能够把整个的地形面上或表面的上方。我们能够把整个的地形分割为四个规则的子地形，如下图。分割为四个规则的子地形，如下图。第九章 3D基本算法结束n我们可以将地形单元的光栅处理顺序编列我们可以将地形单元的光栅处理顺序编列成如下所示：成如下所示：第一次：第一次：1 1、2 2、3 3、4 4。第二次：第二次：5 5、6 6、7 7、8 8、9 9、1010。第三次：第三次：1111、1212、1313、1414、1515、16;16;第四次：第四次：1717、1818、1919、2020、2121、2

35、222、2323、2424、2525。第九章 3D基本算法结束n光栅处理的顺序将会依据观察者在场景中光栅处理的顺序将会依据观察者在场景中角度的不同而有所改变。如下图所示：角度的不同而有所改变。如下图所示：第九章 3D基本算法结束n有这种规律的特性，我们可以将它作为由后到前寻找地有这种规律的特性，我们可以将它作为由后到前寻找地形顺序的依据，而这种特性就可以使用形顺序的依据，而这种特性就可以使用“八叉树八叉树”的存的存储规则，或者也可以用在空间占有的矩形来描述映射。储规则，或者也可以用在空间占有的矩形来描述映射。n在这种情况下，我们利用类似高度场的方法，扩展成为在这种情况下，我们利用类似高度场的方

36、法，扩展成为处理三维顶点而不是二维顶点。处理三维顶点而不是二维顶点。第九章 3D基本算法结束n八叉树的处理规则就是利用递归结构的方八叉树的处理规则就是利用递归结构的方式来进行的，在每个细分的层次上有着同样规式来进行的，在每个细分的层次上有着同样规则的属性。因此，在每个层次上我们可以利用则的属性。因此，在每个层次上我们可以利用同样的编列顺序，以获得整个结构元素由后到同样的编列顺序，以获得整个结构元素由后到前的顺序依据。前的顺序依据。第九章 3D基本算法结束第九章 3D基本算法结束9.5.4 9.5.4 二元空间分割树二元空间分割树n二元空间分割树，Binary Space Partitionin

37、g Tree是一种空间分割的方法，简称BSP Tree。nBSP Tree在一开始将资料文件读进来的时候，就将整个数据文件中的数据（即是墙的数值）先建成一个二元树的数据结构。如下图所示：第九章 3D基本算法结束FrontbackNode中的数据代表一面墙当地形数据被读进来时，BSP Tree会同时被建立（只一次）第九章 3D基本算法结束n当视点开始移动时，平面景象就必须被重当视点开始移动时，平面景象就必须被重新绘制。而重绘就是以视点为基础，对此新绘制。而重绘就是以视点为基础，对此BSP Tree加以分析，只要在加以分析，只要在BSP Tree中，中，且位于此视点前方，它就会被存放在一个且位于此

38、视点前方，它就会被存放在一个串行当中，最后我们只要按照串行的顺序串行当中，最后我们只要按照串行的顺序逐个地将它们绘制在平面上就可以了。逐个地将它们绘制在平面上就可以了。n另一种方法：利用深度测试来显示室内环另一种方法：利用深度测试来显示室内环境及场景。境及场景。第九章 3D基本算法结束A A区域显示在区域显示在X X多边形上多边形上B B区域显示在区域显示在Y Y多边形上多边形上第九章 3D基本算法结束此图的现象在现实中视不可能存在的此图的现象在现实中视不可能存在的第九章 3D基本算法结束n使用使用OpenGL或或Direct3D的函数库去显示的函数库去显示此多边形，它们就会自动做深度探测（此

39、多边形，它们就会自动做深度探测（Z-Buffer），但是效率极差，这就是要使用），但是效率极差，这就是要使用二元空间分割树的原因。二元空间分割树的原因。n二元空间分割树可以利用节点（二元空间分割树可以利用节点（Node）来）来快速和有效的排序多边形，而且在计算机快速和有效的排序多边形，而且在计算机运行时，我们又可以简单的了解运行时，我们又可以简单的了解camera到到最远多边形之间的关系。最远多边形之间的关系。第九章 3D基本算法结束n需要深度测试需要深度测试第九章 3D基本算法结束当二元空间分割树建立时，必须完成下面几项任务：当二元空间分割树建立时，必须完成下面几项任务：1.从函数中选择一个

40、多边形。从函数中选择一个多边形。2.通过平面方程（通过平面方程（Ax+Bx+Cx+D=0）转换多边形为平）转换多边形为平面数据。面数据。3.通过函数分类所有的多边形（前、后、重叠、穿通过函数分类所有的多边形（前、后、重叠、穿越）。越）。4.分割跨越平面的多边形。分割跨越平面的多边形。5.如果任何一个多边形在平面的前方，回到（如果任何一个多边形在平面的前方，回到（1）并）并处理这些多边形。处理这些多边形。6.如果任何一个多边形在平面的后方，回到（如果任何一个多边形在平面的后方，回到（1）并）并处理这些多边形。处理这些多边形。7.在目前的节点中加入与平面重叠的多边形与串中。在目前的节点中加入与平面

41、重叠的多边形与串中。第九章 3D基本算法结束第九章 3D基本算法结束详细的二元素详细的二元素第九章 3D基本算法结束n再利用D平面为主Node来做分割的动作。在分类和切割后的结果如下图所示：第九章 3D基本算法结束n现在的二元空间分现在的二元空间分割树看起来就如下割树看起来就如下图：图：第九章 3D基本算法结束n再继续分割上述二元树结构的再继续分割上述二元树结构的话，二元树结构就会变成如下话，二元树结构就会变成如下图所示：图所示：第九章 3D基本算法结束 当映射多边形时，我们可以利用当映射多边形时，我们可以利用cameracamera的位置与每个平面比较，然的位置与每个平面比较，然后再以距离为

42、基本顺序原则。后再以距离为基本顺序原则。一开始，基本节点是一开始，基本节点是B B多边形，接着执行下面步骤：多边形，接着执行下面步骤：1.1.(1)(1)求出平面与求出平面与cameracamera之间的距离。之间的距离。2.2.(2)(2)如果距离大于如果距离大于0 0：3.3.移向后面节点并回到步骤（移向后面节点并回到步骤（1 1）。）。4.4.显示目前节点内的多边形。显示目前节点内的多边形。5.5.移向前面节点并回到步骤（移向前面节点并回到步骤（1 1）6.6.(3)(3)如果（如果（2 2）是错误的：）是错误的：7.7.移向前面节点并回到步骤（移向前面节点并回到步骤（1 1）8.8.显

43、示目前节点内的多边形。显示目前节点内的多边形。9.9.移向后面节点并回到步骤（移向后面节点并回到步骤（1 1）第九章 3D基本算法结束完成上面步骤，绘制节点的顺序：完成上面步骤，绘制节点的顺序：Node ANode A、Node CbNode Cb、Node FbNode Fb、Node FaNode Fa、Node GabNode Gab、Node GaaNode Gaa、Node ENode E、Node GbNode Gb、Node CaNode Ca、Node DNode D第九章 3D基本算法结束9.5.5 9.5.5 细节层次细节层次 n在在real timereal time图形

44、中。需要绘制图形中。需要绘制3D3D场景的场景的复杂度非常高（包含几十个甚至上百万个复杂度非常高（包含几十个甚至上百万个多边形），所以要实现这种复杂场景的绘多边形），所以要实现这种复杂场景的绘制是非常困难的。制是非常困难的。第九章 3D基本算法结束第九章 3D基本算法结束n解决方法：利用减少场景的复杂度来提高解决方法：利用减少场景的复杂度来提高图像的绘制速度，而图像的绘制速度，而“细节层次细节层次”（Level of DetailLODLevel of DetailLOD）这一门用）这一门用来显示和简化场景的技术就是在这种背景来显示和简化场景的技术就是在这种背景下产生的。下产生的。第九章 3D

45、基本算法结束n细节层次细节层次绘制简化的技术是在不影响画面绘制简化的技术是在不影响画面视觉效果的条件下，逐步简化景物的表面视觉效果的条件下，逐步简化景物的表面细节来减少场景的几何图形所产生之复杂细节来减少场景的几何图形所产生之复杂性，并且它又可以提高绘制算法的效率。性，并且它又可以提高绘制算法的效率。第九章 3D基本算法结束n对于原始网格模型不同细节层次的模型建对于原始网格模型不同细节层次的模型建立，我们可以假设场景的模型都是以三角立，我们可以假设场景的模型都是以三角形的网格呈现（在实际应用中，为了绘制形的网格呈现（在实际应用中，为了绘制方便，方便，3D3D场景一般都被转化为三角形网格场景一般

46、都被转化为三角形网格状），因此可以状），因此可以n从网格的几何特性着手，而这种技术可以从网格的几何特性着手，而这种技术可以归纳为归纳为3 3种不同的基本演算，分别是：种不同的基本演算，分别是：“顶点删除顶点删除”，“边界压缩边界压缩”及及“面的收缩面的收缩”。n网格简化（网格简化（real time renderingreal time rendering）第九章 3D基本算法结束顶点删除顶点删除 n删除网格中的一个顶点，然后再对它的相邻删除网格中的一个顶点，然后再对它的相邻三角形做出一个空洞，这个空洞就当作是三三角形做出一个空洞，这个空洞就当作是三角的剖分，以保持网格的一致性。角的剖分，以保

47、持网格的一致性。第九章 3D基本算法结束边界压缩边界压缩（Edge CollapseEdge Collapse边塌陷）边塌陷）n将网格上的一条边压缩成一个顶点，这个顶将网格上的一条边压缩成一个顶点，这个顶点与该边相邻的两个三角形一起退化掉，而点与该边相邻的两个三角形一起退化掉，而再把它的两个顶点融合成一个新的顶点。再把它的两个顶点融合成一个新的顶点。第九章 3D基本算法结束面的收缩面的收缩n将网格上的一个面收缩成一个顶点，让该三将网格上的一个面收缩成一个顶点，让该三角形本身的和与其相邻的三个三角形一起退角形本身的和与其相邻的三个三角形一起退化掉，而它的三个顶点则收缩成另一个新的化掉，而它的三个顶点则收缩成另一个新的顶点。顶点。第九章 3D基本算法结束n细节层次简化是实时细节层次简化是实时3D3D图形学应用比较多图形学应用比较多的一种技术，通过这种技术，我们可以简的一种技术，通过这种技术，我们可以简化场景的复杂度，同时也可以采用不同分化场景的复杂度，同时也可以采用不同分辨率的模型来显示复杂场景的不同物体，辨率的模型来显示复杂场景的不同物体，以满足实时以满足实时3D3D的要求。的要求。第九章 3D基本算法结束n本章结束本章结束