《2022年D图象算法[归 .pdf》由会员分享，可在线阅读，更多相关《2022年D图象算法[归 .pdf（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、3D 图象算法Jerome St-Louis 3D 简介我们首先从坐标系统开始。你也许知道在2D 里我们经常使用Ren?笛卡儿坐标系统在平面上来识别点。我们使用二维(X,Y):X表示水平轴坐标,Y 表示纵轴坐标。在3 维坐标系，我们增加了Z，一般用它来表示深度。所以为表示三维坐标系的一个点，我们用三个参数(X,Y,Z)。这里有不同的笛卡儿三维系统可以使用。但是它们都是左手螺旋或右手螺旋的。右手螺旋是右手手指的卷曲方向指向Z 轴正方向，而大拇指指向X 轴正方向。左手螺旋是左手手指的卷曲方向指向Z 轴负方向。实际上，我们可以在任何方向上旋转这些坐标系，而且它们仍然保持本身的特性。在计算机图形学，常
2、用坐标系为左手坐标系，所以我们也使用它。：X 正轴朝右Y 正轴向上Z 正轴指向屏幕里矢量什么是矢量？几句话，它是坐标集合。首先我们从二维矢量开始，(X,Y)：例如矢量P(4,5)（一般，我们用-表示矢量）。我们认为矢量P 代表点(4,5)，它是从原点指向(4,5)的有方向和长度的箭头。我们谈论矢量的长度指从原点到该点的距离。二维距离计算公式是|P|=sqrt(x2+y2)这里有一个有趣的事实：在1D（点在单一的坐标轴上），平方根为它的绝对值。让我们讨论三维矢量：例如P(4,-5,9)，它的长度为|P|=sqrt(x2+y2+z2)它代表在笛卡儿3D 空间的一个点。或从原点到该点的一个箭头代表该
3、矢量。在有关操作一节里，我们讨论更多的知识。矩阵开始，我们从简单的开始：我们使用二维矩阵4 乘 4 矩阵，为什么是4 乘 4？因为我们在三维坐标系里而且我们需要附加的行和列来完成计算工作。在二维坐标系我们需要3 乘 3 矩阵。着意味着我们在3D 中有 4 个水平参数和4 个垂直参数，一共16 个。例如：4x4 单位矩阵|1 0 0 0|0 1 0 0|0 0 1 0|0 0 0 1|因为任何其它矩阵与之相乘都不改变，所以称之为单位阵。又例如有矩阵如下：|10 -7 22 45|sin(a)cos(a)34 32|-35 28 17 6|45 -99 32 16|名师资料总结-精品资料欢迎下载-
4、名师精心整理-第 1 页，共 28 页 -有关矢量和矩阵的操作我们已经介绍了一些非常简单的基本概念，那么上面的知识与三维图形有什么关系呢？本节我们介绍3D 变换的基本知识和其它的一些概念。它仍然是数学知识。我们要讨论有关矢量和矩阵操作。让我们从两个矢量和开始：(x1,y1,z1)+(x2,y2,z2)=(x1+x2,y1+y2,z1+z2)很简单，现在把矢量乘于系数：k?(x,y,z)=(kx,ky,kz)可以把上面的公式称为点积，如下表示：(x1,y1,z1)?(x2,y2,z2)=x1x2+y1y2+z1z2 实际上，两个矢量的点积被它们的模的乘积除，等于两个矢量夹角的余弦。所以cos(V
5、 W)=V?W/|V|W|注意 并不表示指数而是两个矢量的夹角。点积可以用来计算光线于平面的夹角，我们在计算阴影一节里会详细讨论。现在讨论叉乘：(x1,y1,z1)X(x2,y2,z2)=(y1z2-z1y2,z1x2-x1z2,x1y2-y1x2)叉乘对于计算屏幕的法向量非常有用。OK，我们已经讲完了矢量的基本概念。我们开始两个矩阵的和。它与矢量相加非常相似，这里就不讨论了。设I 是矩阵的一行，J 是矩阵的一列，(i,j)是矩阵的一个元素。我们讨论与3D 变换有关的重要的矩阵操作原理。两个矩阵相乘，而且M x N N x M。例如：A 4x4 矩阵相乘公式如果A=(aij)4x4，B=(bi
6、j)4x4,那么A x B=|S a1jbj1 S a1jbj2 S a1jbj3 S a1jbj4|S a2jbj1 S a2jbj2 S a2jbj3 S a2jbj4|S a3jbj1 S a3jbj2 S a3jbj3 S a3jbj4|S a4jbj1 S a4jbj2 S a4jbj3 S a4jbj4|其中j=1,2,3,4 而且如果AxB=(cik)4x4 那么我们可以在一行上写下：cik=S4,j=1 aijbjk(a1,a2,a3)x B=(Sum(aibi1)+b4,1,Sum(aibi2)+b4,2,Sum(aibi3)+b4,3)名师资料总结-精品资料欢迎下载-名师精
7、心整理-第 2 页，共 28 页 -现在,我们可以试着把一些矩阵乘以单位阵来了解矩阵相乘的性质。我们把矩阵与矢量相乘结合在一起。下面有一个公式把3D 矢量乘以一个4x4 矩阵（得到另外一个三维矢量）如果 B=(bij)4x4，那么：(a1,a2,a3)x B=(Saibi1+b4,1,Saibi2+b4,2,Saibi3+b4,3)这就是矢量和矩阵操作公式。从这里开始，代码与数学之间的联系开始清晰。变换我们已经见过象这样的公式：t(tx,ty):(x,y)=(x+tx,y+ty)这是在二维笛卡儿坐标系的平移等式。下面是缩放公式：s(k):(x,y)=(kx,ky)旋转等式:r(q):(x,y)
8、=(x cos(q)-y sin(q),x sin(q)+y cos(q)以上都是二维公式，在三维里公式的形式仍然很相近。平移公式：t(tx,ty,tz):(x,y,z)=(x+tx,y+ty,z+tz)缩放公式：s(k):(x,y,z)=(kx,ky,kz)旋转公式（围绕Z 轴）：r(q):(x,y,z)=(x cos(q)-y sin(q),x sin(q)+y cos(q),z)所以我们可以写出像在二维中同样的变换公式。我们通过乘以变换矩阵而得到新的矢量，新矢量将指向变换点。下面是所有三维变换矩阵：平移(tx,ty,tz)的矩阵|1 0 0 0|0 1 0 0|0 0 1 0|tx ty
9、 tz 1|缩放(sx,sy,sz)的矩阵|sz 0 0 0|0 sy 0 0|0 0 sx 0|0 0 0 1|名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 28 页 -绕 X 轴旋转角 q 的矩阵|1 0 0 0|0 cos(q)sin(q)0|0-sin(q)cos(q)0|0 0 0 1|绕 Y 轴旋转角 q 的矩阵:|cos(q)0-sin(q)0|0 1 0 0|sin(q)0 cos(q)0|0 0 0 1|绕 Z 轴旋转角q 的矩阵:|cos(q)sin(q)0 0|-sin(q)cos(q)0 0|0 0 1 0|0 0 0 1|所以我们已经可以结束关于变换的
10、部分.通过这些矩阵我们可以对三维点进行任何变换.平面和法向量平面是平坦的，无限的，指向特定方向的表面可以定义平面如下：Ax+By+Cz+D=0 其中A,B,C 称为平面的法向量，D 是平面到原点的距离。我们可以通过计算平面上的两个矢量的叉积得到平面的法向量。为得到这两个矢量，我们需要三个点。P1，P2，P3 逆时针排列，可以得到：矢量 1=P1-P2 和矢量 2=P3-P2 计算法向量为：法向量=矢量 1 X 矢量 2 把 D 移到等式的右边得到：D=-(Ax+By+Cz)或名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 28 页 -D=-(A?1.x+B?2.y+C?3.z)或
11、更简单:D=-Normal?P1 但是为计算A,B,C 分量。可以简化操作按如下等式：A=y1(z2-z3)+y2(z3-z1)+y3(z1-z2)B=z1(x2-x3)+z2(x3-x1)+z3(x1-x2)C=x1(y2-y3)+x2(y3-y1)+x3(y1-y2)D=-x1(y2z3-y3z2)-x2(y3z1-y1z3)-x3(y1z2-y2z1)三维变换存储坐标实现矩阵系统实现三角法系统创建变换矩阵如何创建透视变换对象存储坐标首先可以编写星空模拟代码。那么我们基本的结构是什么样？每一个对象的描述是如何存储的？为解决这个问题，首先我们思考另一个问题：我们需要的是什么样的坐标系？最明显
12、的答案是：屏幕坐标系：相对于显示器的原点的2D 坐标系本地坐标系：相对于对象的原点的3D 坐标系但是我们不要忘记变换中间用到的坐标系，例如：世界坐标系：相对于3D 世界的原点三维坐标系对齐(视点)坐标系：世界坐标系的变换，观察者的位置在世界坐标系的原点。下面是坐标的基本结构：/二维坐标typedef struct short x,y;_2D;/三维坐标typedef struct float x,y,z;_3D;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 28 页 -这里,我们定义了称为顶点的坐标结构。因为“顶点”一词指两个或两个以上菱形边的交点。我们的顶点可以简单地认为是描
13、述不同系统的矢量。/不同的坐标系的坐标typedef struct _3D Local;_3D World;_3D Aligned;Vertex_t;实现矩阵系统我们需要存储我们的矩阵在4x4 浮点数矩阵中。所以当我们需要做变换是我们定义如下矩阵：float matrix44;然后我们定义一些函数来拷贝临时矩阵到全局矩阵:void MAT_Copy(float source44,float dest44)int i,j;for(i=0;i4;i+)for(j=0;j4;j+)destij=sourceij;很简单！现在我们来写两个矩阵相乘的函数。同时可以理解上面的一些有关矩阵相乘的公式代码如下
14、：void MAT_Mult(float mat144,float mat244,float dest44)int i,j;for(i=0;i4;i+)for(j=0;jx=Source-x*mat00+Source-y*mat10+Source-z*mat20+mat30;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 28 页 -Dest-y=Source-x*mat01+Source-y*mat11+Source-z*mat21+mat31;Dest-z=Source-x*mat02+Source-y*mat12+Source-z*mat22+mat32;/Source-源
15、矢量(坐标)/mat-变换矩阵/Dest-目标矩阵(坐标)我们已经得到了矩阵变换函数，不错吧！/注意,这里的矩阵变换与我们学过的矩阵变换不同/一般的,Y=TX,T为变换矩阵，这里为Y=XT，/由于矩阵T 为 4x4 矩阵实现三角法系统几乎每一个C 编译器都带有有三角函数的数学库，但是我们需要简单的三角函数时，不是每次都使用它们。正弦和余弦的计算是阶乘和除法的大量运算。为提高计算速度，我们建立自己的三角函数表。首先决定你需要的角度的个数，然后在这些地方用下面的值代替：float SinTable256,CosTable256;然后使用宏定义，它会把每一个角度变成正值，并对于大于360 度的角度进
16、行周期变换，然后返回需要的值。如果需要的角度数是2 的幂次，那么我们可以使用&代替%，它使程序运行更快。例如256。所以在程序中尽量选取2 的幂次。三角法系统：#define SIN(x)SinTableABS(int)x&255)#define COS(x)CosTableABS(int)x&255)一旦我们已经定义了需要的东西，建立初始化函数，并且在程序中调用宏。void M3D_Init()int d;for(d=0;d(f*x/z+XOrigin,f*y/z+YOrigin)其中 f 是“焦点距离”，它表示从观察者到屏幕的距离，一般在80 到 200 厘米之间。XOrigin和YOri
17、gin 是屏幕中心的坐标，(x,y,z)在对齐坐标系上。那么投影函数应该是什么样？#define FOCAL_DISTANCE 200/定义焦点距离void Project(vertex_t*Vertex)if(!Vertex-Aligned.z)Vertex-Aligned.z=1;Vertex-Screen.x=FOCAL_DISTANCE*Vertex-Aligned.x/Vertex-Aligned.z+XOrigin;Vertex-Screen.y=FOCAL_DISTANCE*Vertex-Aligned.y/Vertex-Aligned.z+YOrigin;/得到屏幕上的投影坐标
18、因为 0 不能做除数，所以对z 进行判断。名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 28 页 -变换对象既然我们已经掌握了所有的变换顶点的工具，就应该了解需要执行的主要步骤。一、初始化每一个顶点的本地坐标二、设置全局矩阵为单位阵三、根据对象的尺寸缩放全局矩阵四、根据对象的角度来旋转全局矩阵五、根据对象的位置移动全局矩阵六、把本地坐标乘以全局矩阵来得到世界坐标系七、设置全局矩阵为单位阵八、用观测者的位置的负值平移全局矩阵九、用观测者的角度的负值旋转全局矩阵十、把世界坐标系与全局矩阵相乘得到对齐坐标系十一、投影对齐坐标系来得到屏幕坐标即：本地坐标系-世界坐标系-对齐坐标系-屏幕
19、坐标系多边形填充多边形结构发现三角形绘制三角形多边形结构我们如何存储我们的多边形？首先，我们必须知道再这种状态下多边形是二维多边形，而且由于初始多边形是三维的，我们仅需要一个临时的二维多边形，所以我们能够设置二维顶点的最大数为一个常量，而没有浪费内存：2D 结构：typedef struct _2D Points20;int PointsCount;int Texture;Polygon2D_t;3D 结构:typedef struct int Count;int*Vertex;int Texture;Vertex_t P,M,N;Polygon_t;名师资料总结-精品资料欢迎下载-名师精心整
20、理-第 10 页，共 28 页 -为什么顶点数组包含整数值呢?仔细思考一下,例如在立方体内,三个多边形公用同一个顶点,所以在三个多边形里存储和变换同一个顶点会浪费内存和时间。我们更愿意存储它们在一个对象结构里，而且在多边形结构里，我们会放置相应顶点的索引。请看下面的结构：typedef struct int VertexCount;int PolygonCount;Vertex_t*Vertex;Polygon_t*Polygon;_3D Scaling;_3D Position;_3D Angle;int NeedUpdate;Object_t;发现三角形因为绘制一个三角形比绘制任意的多边形
21、要简单，所以我们从把多边形分割成三顶点的形状。这种方法非常简单和直接：void POLY_Draw(Polygon2D_t*Polygon)_2D P1,P2,P3;int i;P1=Polygon-Points0;for(i=1;i PointsCount-1;i+)P2=Polygon-Pointsi;P3=Polygon-Pointsi+1;POLY_Triangle(P1,P2,P3,Polygon-Texture);/上面的算法，对于凹多边形就不太适用_|_|绘制三角形现在怎样得到三角形函数?我们怎样才能画出每一条有关的直线,并且如何发现每一行的起始和结实的x 坐标。我们通过定义两个
22、简单有用的宏定义开始来区别垂直地两个点和两个数：#define MIN(a,b)(ab)?(a):(b)#define MaxPoint(a,b)(a.y b.y)?a:b)#define MinPoint(a,b)(b.y a.y)?a:b)然后我们定义三个宏来区别三个点：#define MaxPoint3(a,b,c)MaxPoint(MaxPoint(a,b),MaxPoint(b,c)#define MidPoint3(a,b,c)MaxPoint(MinPoint(a,b),MinPoint(a,c)#define MinPoint3(a,b,c)MinPoint(MinPoint(
23、a,b),MinPoint(b,c)你也许注意到MidPoint3 宏不总是正常地工作，取决于三个点排列的顺序，例如,ab&ac 那么由 MidPoint3 得到的是a,但它不是中间点。我们用 if 语句来修正这个缺点，下面为函数的代码：void POLY_Triangle(_2D p1,_2D p2,_2D p3,char c)_2D p1d,p2d,p3d;int xd1,yd1,xd2,yd2,i;int Lx,Rx;首先我们把三个点进行排序：p1d=MinPoint3(p1,p2,p3);p2d=MidPoint3(p2,p3,p1);p3d=MaxPoint3(p3,p1,p2);当
24、调用这些宏的时候为什么会有点的顺序的改变？（作者也不清楚）可能这些点被逆时针传递。试图改变这些宏你的屏幕显示的是垃圾！现在我们并不确定中间的点，所以我们做一些检查，而且在这种状态下，得到的中间点有似乎是错误的，所以我们修正：if(p2.y p1.y)p1d=MinPoint3(p2,p1,p3);p2d=MidPoint3(p1,p3,p2);这些点的排列顺序看起来很奇怪，但是试图改变他们那么所有的东西就乱套了。只有理解或接受这些结论。现在我们计算增量xd1=p2d.x-p1d.x;yd1=p2d.y-p1d.y;xd2=p3d.x-p1d.x;yd2=p3d.y-p1d.y;OK，第一步已经
25、完成，如果有增量y：if(yd1)名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 28 页 -for(i=p1d.y;i=p2d.y;i+)我们用 x 的起始坐标计算x 值，在当前点和起始点之间加上增量y，乘以斜率(x/y)的相反值。Lx=p1d.x+(i-p1d.y)*xd1)/yd1;Rx=p1d.x+(i-p1d.y)*xd2)/yd2;如果不在同一个点，绘制线段，按次序传递这两个点：if(Lx!=Rx)VID_HLine(MIN(Lx,Rx),MAX(Lx,Rx),i,c);现在我们重新计算第一个增量，而且计算第二条边xd1=p3d.x-p2d.x;yd1=p3d.y-
26、p2d.y;if(yd1)for(i=p2d.y;i=p3d.y;i+)Lx=p1d.x+(i-p1d.y)*xd2)/yd2;Rx=p2d.x+(i-p2d.y)*xd1)/yd1;if(Lx!=Rx)VID_HLine(MIN(Lx,Rx),MAX(Lx,Rx),i,c);以上我们已经得到多边形填充公式，对于平面填充更加简单：void VID_HLine(int x1,int x2,int y,char c)int x;for(x=x1;x=x2;x+)putpixel(x,y,c);Sutherland-Hodgman 剪贴概述Z-剪贴屏幕剪贴概述一般地，我们更愿意剪贴我们的多边形。必须
27、靠着屏幕的边缘剪贴，但也必须在观察的前方（我们不需要绘制观察者后面的事物，当z 左边非常小时）。当我们剪贴一个多边形，并不考虑是否每一个点在限制以内，而我们更愿意增加必须的顶点，所以我们需要一个第三个多边形结构：typedef struct 名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 28 页 -int Count;_3D Vertex20;CPolygon_t;由于我们有附加的顶点来投影，我们不再投影顶点，而是投影剪贴的3D 多边形到2D 多边形。void M3D_Project(CPolygon_t*Polygon,Polygon2D_t*Clipped,int foc
28、aldistance)int v;for(v=0;vCount;v+)if(!Polygon-Vertexv.z)Polygon-Vertexv.z+;Clipped-Pointsv.x=Polygon-Vertexv.x*focaldistance/Polygon-Vertexv.z+Origin.x;Clipped-Pointsv.y=Polygon-Vertexv.y*focaldistance/Polygon-Vertexv.z+Origin.y;Clipped-PointsCount=Polygon-Count;Z-剪贴首先我们定义计算在第一个点和第二个点之间以及在第一个点和最小z
29、值的 z 增量的宏。然后，我们计算比例，注意不要被零除。WORD ZMin=20;#define INIT_ZDELTAS dold=V2.z-V1.z;dnew=ZMin-V1.z;#define INIT_ZCLIP INIT_ZDELTAS if(dold)m=dnew/dold;我们建立一个函数，它主要剪贴多边形指针的参数（它将记下作为结果的剪贴的顶点），第一个顶点（我们剪贴的边的开始）和第二个顶点（最后）：void CLIP_Front(CPolygon_t*Polygon,_3D V1,_3D V2)float dold,dnew,m=1;INIT_ZCLIP 现在我们必须检测边缘
30、是否完全地在视口里，离开或进入视口。如果边缘没有完全地在视口里，我们计算视口与边缘的交线，用m 值表示，用INIT_ZCLIP计算。如果边缘在视口里：if(V1.z=ZMin)&(V2.z=ZMin)Polygon-VertexPolygon-Count+=V2;如果边缘正离开视口：if(V1.z=ZMin)&(V2.zVertexPolygon-Count.x=V1.x+(V2.x-V1.x)*m;名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 28 页 -Polygon-VertexPolygon-Count.y=V1.y+(V2.y-V1.y)*m;Polygon-Ver
31、texPolygon-Count+.z=ZMin;如果边缘正进入视口：if(V1.z=ZMin)Polygon-VertexPolygon-Count.x=V1.x+(V2.x-V1.x)*m;Polygon-VertexPolygon-Count.y=V1.y+(V2.y-V1.y)*m;Polygon-VertexPolygon-Count+.z=ZMin;Polygon-VertexPolygon-Count+=V2;这就是边缘Z-剪贴函数 现在我们可以写下完整的多边形Z-剪贴程序。为了有代表性，定义一个宏用来在一个对象结构中寻找适当的多边形顶点。#define Vert(x)Objec
32、t-VertexPolygon-Vertexx 下面是它的函数：void CLIP_Z(Polygon_t*Polygon,Object_t*Object,CPolygon_t*ZClipped)int d,v;ZClipped-Count=0;for(v=0;vCount;v+)d=v+1;if(d=Polygon-Count)d=0;CLIP_Front(ZClipped,Vert(v).Aligned,Vert(d).Aligned);这个函数相当简单：它仅仅调用FrontClip 函数来做顶点交换。剪贴屏幕剪贴屏幕的边缘同Z-剪贴相同，但是我们有四个边缘而不是一个。所以我们需要四个不同
33、的函数。但是它们需要同样的增量初始化：#define INIT_DELTAS dx=V2.x-V1.x;dy=V2.y-V1.y;#define INIT_CLIP INIT_DELTAS if(dx)m=dy/dx;边缘是：_2D TopLeft,DownRight;为了进一步简化_2D 和 _3D 结构的使用，我们定义两个有用的函数：名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 28 页 -_2D P2D(short x,short y)_2D Temp;Temp.x=x;Temp.y=y;return Temp;_3D P3D(float x,float y,float
34、 z)_3D Temp;Temp.x=x;Temp.y=y;Temp.z=z;return Temp;然后使用这两个函数来指定视口：TopLeft=P2D(0,0);DownRight=P2D(319,199);下面是四个边缘剪贴函数：/*=剪贴左边缘=*/void CLIP_Left(Polygon2D_t*Polygon,_2D V1,_2D V2)float dx,dy,m=1;INIT_CLIP/*OK*if(V1.x=TopLeft.x)&(V2.x=TopLeft.x)Polygon-PointsPolygon-PointsCount+=V2;/*LEAVING*if(V1.x=T
35、opLeft.x)&(V2.xPointsPolygon-PointsCount.x=TopLeft.x;Polygon-PointsPolygon-PointsCount+.y=V1.y+m*(TopLeft.x-V1.x);/*ENTERING*if(V1.x=TopLeft.x)Polygon-PointsPolygon-PointsCount.x=TopLeft.x;名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 28 页 -Polygon-PointsPolygon-PointsCount+.y=V1.y+m*(TopLeft.x-V1.x);Polygon-Poin
36、tsPolygon-PointsCount+=V2;/*=剪贴右边缘=*/void CLIP_Right(Polygon2D_t*Polygon,_2D V1,_2D V2)float dx,dy,m=1;INIT_CLIP/*OK*if(V1.x=DownRight.x)&(V2.xPointsPolygon-PointsCount+=V2;/*LEAVING*if(V1.xDownRight.x)Polygon-PointsPolygon-PointsCount.x=DownRight.x;Polygon-PointsPolygon-PointsCount+.y=V1.y+m*(DownR
37、ight.x-V1.x);/*ENTERING*if(V1.xDownRight.x)&(V2.xPointsPolygon-PointsCount.x=DownRight.x;Polygon-PointsPolygon-PointsCount+.y=V1.y+m*(DownRight.x-V1.x);Polygon-PointsPolygon-PointsCount+=V2;/*=剪贴上边缘=*/void CLIP_Top(Polygon2D_t*Polygon,_2D V1,_2D V2)float dx,dy,m=1;INIT_CLIP/*OK*if(V1.y=TopLeft.y)&(V
38、2.y=TopLeft.y)Polygon-PointsPolygon-PointsCount+=V2;/*LEAVING*名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 28 页 -if(V1.y=TopLeft.y)&(V2.yPointsPolygon-PointsCount.x=V1.x+(TopLeft.y-V1.y)/m;else Polygon-PointsPolygon-PointsCount.x=V1.x;Polygon-PointsPolygon-PointsCount+.y=TopLeft.y;/*ENTERING*if(V1.y=TopLeft.y)if
39、(dx)Polygon-PointsPolygon-PointsCount.x=V1.x+(TopLeft.y-V1.y)/m;else Polygon-PointsPolygon-PointsCount.x=V1.x;Polygon-PointsPolygon-PointsCount+.y=TopLeft.y;Polygon-PointsPolygon-PointsCount+=V2;/*=剪贴下边缘=*/void CLIP_Bottom(Polygon2D_t*Polygon,_2D V1,_2D V2)float dx,dy,m=1;INIT_CLIP/*OK*if(V1.y=DownR
40、ight.y)&(V2.yPointsPolygon-PointsCount+=V2;/*LEAVING*if(V1.yDownRight.y)if(dx)Polygon-PointsPolygon-PointsCount.x=V1.x+(DownRight.y-V1.y)/m;else Polygon-PointsPolygon-PointsCount.x=V1.x;Polygon-PointsPolygon-PointsCount+.y=DownRight.y;/*ENTERING*if(V1.yDownRight.y)&(V2.yPointsPolygon-PointsCount.x=V
41、1.x+(DownRight.y-V1.y)/m;else Polygon-PointsPolygon-PointsCount.x=V1.x;Polygon-PointsPolygon-PointsCount+.y=DownRight.y;Polygon-PointsPolygon-PointsCount+=V2;为了得到完整的多边形剪贴函数，我们需要定义一个附加的全局变量：polygon2D_t TmpPoly;void CLIP_Polygon(Polygon2D_t*Polygon,Polygon2D_t*Clipped)int v,d;Clipped-PointsCount=0;Tmp
42、Poly.PointsCount=0;for(v=0;vPointsCount;v+)d=v+1;if(d=Polygon-PointsCount)d=0;CLIP_Left(&TmpPoly,Polygon-Pointsv,Polygon-Pointsd);for(v=0;vTmpPoly.PointsCount;v+)d=v+1;if(d=TmpPoly.PointsCount)d=0;CLIP_Right(Clipped,TmpPoly.Pointsv,TmpPoly.Pointsd);TmpPoly.PointsCount=0;for(v=0;vPointsCount;v+)d=v+1
43、;if(d=Clipped-PointsCount)d=0;CLIP_Top(&TmpPoly,Clipped-Pointsv,Clipped-Pointsd);Clipped-PointsCount=0;for(v=0;vTmpPoly.PointsCount;v+)d=v+1;if(d=TmpPoly.PointsCount)d=0;名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 28 页 -CLIP_Bottom(Clipped,TmpPoly.Pointsv,TmpPoly.Pointsd);程序原理同Z-剪贴一样，所以我们可以轻松地领会它。隐面消除Dilemna 底面
44、消除Z-缓冲The Dilemna 三维引擎的核心是它的HSR 系统，所以我们必须考虑选择那一种。一般来说，最流行的几种算法是：画笔算法需要的时间增长更快难以实现（尤其重叠测试）不能准确地排序复杂的场景字节空间分区树特别快难以实现仅仅能排序静态多边形需要存储树Z-缓存需要的时间随多边形的数目线性地增加在多边形大于5000 后速度比画笔算法快能够完美地渲染任何场景，即使逻辑上不正确非常容易实现简单需要大量的内存很慢所以我们的选择是Z-缓存。当然也可以选择其他算法。底面消除除了这些方法，我们可以很容易地消除多边形的背面来节省大量的计算时间。首先我们定义一些有用的函数来计算平面和法向量以及填充。然后
45、，我们给这个函数增加纹理和阴影计算。这些变量为全局变量：float A,B,C,D;BOOL backface;下面是我们的引擎函数，每一个坐标都是浮点变量：void ENG3D_SetPlane(Polygon_t*Polygon,Object_t*Object)float x1=Vert(0).Aligned.x;float x2=Vert(1).Aligned.x;名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 28 页 -float x3=Vert(2).Aligned.x;float y1=Vert(0).Aligned.y;float y2=Vert(1).Alig
46、ned.y;float y3=Vert(2).Aligned.y;float z1=Vert(0).Aligned.z;float z2=Vert(1).Aligned.z;float z3=Vert(2).Aligned.z;然后我们计算平面等式的每一个成员：A=y1*(z2-z3)+y2*(z3-z1)+y3*(z1-z2);B=z1*(x2-x3)+z2*(x3-x1)+z3*(x1-x2);C=x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2);D=-x1*(y2*z3-y3*z2)-x2*(y3*z1-y1*z3)-x3*(y1*z2-y2*z1);再检查是否它面朝我们
47、或背朝：backface=D0;Z-缓存Z-缓存是把显示在屏幕上的每一个点的z 坐标保持在一个巨大的数组中，并且当我们我们检查是否它靠近观察者或是否在观察者后面。我们仅仅在第一种情况下绘制它。所以我们不得不计算每一个点的z 值。但是首先，我们定义全局树组和为他分配空间。（内存等于追至方向与水平方向的乘积）：typedef long ZBUFTYPE;ZBUFTYPE*zbuffer;zbuffer=(ZBUFTYPE*)malloc(sizeof(ZBUFTYPE)*MEMORYSIZE);我们使用长整形作为z-缓存类型，因为我们要使用定点数。我们必须记住设置每一个z 坐标来尽可能得到更快的速
48、度：int c;for(c=0;c 下面是程序：#define FIXMUL(1ZBufferoffset)zbufferoffset=z;SCREENBUFFERoffset=color;z+=dz;3D 纹理映射概述魔幻数字纹理映射的透视修正概述在做纹理映射时首先考虑的是建立纹理数组和初始化3D 纹理坐标。纹理将存储在：#define MAXTEXTURES 16 bitmap_t TexturesMAXTEXTURES;我们从 PCX 文件分配和加载纹理。这里假设纹理大小为64x64。我们使用polygon_t 结构的纹理坐标：vertex_t P,M,N;我们在函数中初始化纹理，该函数
49、在建立多边形后被调用。P 是纹理的原点，M 是纹理的水平线末端，N 是垂直线的末端。void TEX_Setup(Polygon_t*Polygon,Object_t*Object)Polygon-P.Local=P3D(Vert(1).Local.x,Vert(1).Local.y,Vert(1).Local.z);Polygon-M.Local=P3D(Vert(0).Local.x,Vert(0).Local.y,Vert(0).Local.z);Polygon-N.Local=P3D(Vert(2).Local.x,Vert(2).Local.y,Vert(2).Local.z);我们
50、需要象任何其他对象的顶点一样变换纹理坐标，所以我们需要建立世界变换和一个对齐变换函数：void TR_Object(Object_t*Object,float matrix44)int v,p;for(v=0;vVertexCount;v+)VEC_MultMatrix(&Object-Vertexv.Local,matrix,&Object-Vertexv.World);名师资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 28 页 -for(p=0;pPolygonCount;p+)VEC_MultMatrix(&Object-Polygonp.P.Local,matrix,&O