《3D图像算法从入门到进阶(包含C实现).docx》由会员分享，可在线阅读，更多相关《3D图像算法从入门到进阶(包含C实现).docx（24页珍藏版）》请在课桌文档上搜索。
1、3D图象算法3D简介我们首先从坐标系统起先。你或许知道在2D里我们常常运用笛卡儿坐标系统在平面上来识别点。我们运用二维(X,Y):X表示水平轴坐标,Y表示纵轴坐标。在3维坐标系，我们增加了Z,一般用它来表示深度。所以为表示三维坐标系的一个点，我们用三个参数(X,Y,Z)这里有不同的笛卡儿三维系统可以运用。但是它们都是左手螺旋或右手螺旋的。右手螺旋是右手手指的卷曲方向指向Z轴正方向，而大拇指指向X轴正方向。左手螺旋是左手手指的卷曲方向指向Z轴负方向。事实上，我们可以在任何方向上旋转这些坐标系,而且它们仍旧保持本身的特性。在计算机图形学，常用坐标系为左手坐标系(手背向上)，所以我们也运用它。：X正
2、轴朝右Y正轴向上Z正轴指向屏幕里矢量什么是矢量？几句话，它是坐标集合。首先我们从二维矢量起先，(X,Y)：例如矢量P(4,5)(一般，我们用表示矢量)。我们认为矢量P代表点(4,5),它是从原点指向(4,5)的有方向和长度的箭头。我们谈论矢量的长度指从原点到该点的距离。二维距离计算公式是IPl=sqrt(x2+y2)这里有一个好玩的事实：在ID(点在单一的坐标轴上)，平方根为它的肯定值。让我们探讨三维矢量：例如P(4,-5,9),它的长度为IPI=sqrt(x2+y-2+z2)它代表在笛卡儿3D空间的一个点。或从原点到该点的一个箭头代表该矢量。在有关操作一节里，我们探讨更多的学问。矩阵起先，我
3、们从简洁的起先：我们运用二维矩阵4乘4矩阵，为什么是4乘4?因为我们在二维坐标系里而且我们须要附加的行和列来完成计算工作(本质缘由：在计算机图形学里应用的图形变换，事实上是在仿射空间而不是向量空间中进行的)。在二维坐标系我们须要3乘3矩阵。着意味着我们在3D中有4个水平参数和4个垂直参数，一共16个。例如：4x4单位矩阵IlOOOIo100100io100oii因为任何其它矩阵与之相乘都不变更，所以称之为单位阵。又例如有矩阵如下：I10-72245IIsin（八）cos（八）3432I-3528176II45-993216有关矢量和矩阵的操作我们已经介绍了一些特别简洁的基本概念，那么上面的学问
4、与三维图形有什么关系呢？本节我们介绍3D变换的基本学问和其它的一些概念。它仍旧是数学学问。我们要探讨有关矢量和矩阵操作。让我们从两个矢量和起先：(xl,yl,zl)+(x2,y2,z2)=(xl+x2,yl+y2,zl+z2)儿何意义：等于两个矢量组成的平行四边形的长对角线的矢量两个矢量减法的几何意义：等于两个矢量组成的三角形的另一条边的矢量很简洁，现在把矢量乘于系数(数乘)：k?(X,y,z)=(kx,ky,kz)几何意义：将矢量进行缩放点积如下表示：(点积是个标量)(xl,yl,zl)?(x2,y2,z2)=xlx2+yly2+zlz2事实上，两个矢量的点枳被它们的模的乘积除，等于两个矢量
5、夹角的余弦(两个矢量的模与其夹角的余弦之积称为两个矢量的数量积(或称内积、点积)。所以cos(VCW)=V?w/IVIIWI几何意义：两个矢量的点积衡量着两个向量的角度关系。在物理上的意义假如两个矢量分别代表力和位移,那么两个矢量的点积就是功。留意并不表示指数而是两个矢量的夹角。点积可以用来计算光线与平面的夹角，我们在计算阴影一节里会具体探讨。现在探讨叉乘：(xl,yl,zl)X(x2,y2,z2)=(ylz2-zly2,zlx2-xlz2,xly2-ylx2)几何意义：叉乘的结果是一个伪向量，但是他的模是以此二向量为相邻两边的平行四边形面积叉乘对于计算屏幕的法向量特别有用。OK,我们已经讲完
6、了矢量的基本概念。我们起先两个矩阵的和。它与矢量相加特别相像，这里就不探讨了。设I是矩阵的一行，J是矩阵的一列，(i,j)是矩阵的一个元素。我们探讨与3D变换有关的重要的矩阵操作原理。矩阵相乘的几何意义：把两次线性变换合成一次两个矩阵相乘，而且MXNNXM0例如：(矩阵乘法是有依次的)AB4x4矩阵相乘公式假如A=(aij)4x4,B=(bij)4x4,那么AXB=SaljbjlSaljbj2Saljbj3SSa2jbjlSa2jbj2Sa2jbj3SSa3jbjlSa3jbj2Sa3jbj3SSa4jbjlSa4jbj2Sa4jbj3Saljbj4Ia2jbj4Ia3jbj4Ia4jbj4I
7、其中j=l,2,3,4而且假如AxB=(cik)4x4那么我们可以在一行上写下：cik=S4,j=laijbjk(al,a2,a3)xB=(Sum(aibil)+b4,1,Sum(aibi2)+b4,2,Sum(aibi3)+b4,3)现在,我们可以试着把一些矩阵乘以单位矩阵来了解矩阵相乘的性质。我们把矩阵与矢量相乘结合在一起。下面有一个公式把3D矢量乘以一个4x4矩阵(得到另外一个三维矢量)假如B=(bij)4x4,那么：(al,a2,a3)XB=(Saibil+b4,1,Saibi2+b4,2,Saibi3b4,3)这就是矢量和矩阵操作公式。从这里起先，代码与数学之间的联系起先清晰。变换我
8、们已经见过象这样的公式：t(tx,ty):(X,y)=(X+tx,y+ty)这是在二维笛卡儿坐标系的平移等式。下面是缩放公式：s(k):(X,y)=(kx,ky)旋转等式：r(q):(X,y)=(Xcos(q)-ysin(q),Xsin(q)+ycos(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)=(Xcos(q)-ysin(q),Xsin(q)+ycos(q),z)所以我们可以写出像在二维中同样的变换公
9、式。我们通过乘以变换矩阵而得到新的矢量，新矢量将指向变换点。下面是全部三维变换矩阵：平移(tx,ty,tz)的矩阵10000100100lOItxtytz1I缩放(sx,sy,SZ)的矩阵Isz000II0sy00II00SX0II0001I绕X轴旋转角q的矩阵I1000I0cos(q)sin(q)0I0-sin(q)cos(q)0I0001绕Y轴旋转角q的矩阵：Icos(q)0-sin(q)0I0100IIsin(q)0cos(q)0I0001绕Z轴旋转角q的矩阵:Icos(q)sin(q)00|I-sin(q)cos(q)00|I0010II0001I所以我们已经可以结束关于变换的部分.通
10、过这些矩阵我们可以对三维点进行任何变换.平面和法向量平面是平坦的，无限的，指向特定方向的表面可以定义平面如下：Ax+By+Cz+D=0其中A,B,C称为平面的法向量，D是平面到原点的距离。我们可以通过计算平面上的两个矢量的叉积得到平面的法向量。为得到这两个矢量，我们须要三个点。Pl,P2,P3逆时针排列(转入仿射空间了)，可以矢量I=PI-P2和矢量2=P3-P2计算法向量为：法向量=矢量1X矢量2把D移到等式的右边得到：D=-(Ax+By+Cz)或D=-(A?l.x+B?2.y+C?3.z)或更简洁：D=-Normal?P1但是为计算A,B,C重量。可以简化操作按如下等式：A=yl(z2-z
11、3)+y2(z3-zl)+y3(zl-z2)B=Zl(x2-x3)+z2(x3-xl)+z3(xl-x2)C=xl(y2-y3)+x2(y3-yl)+x3(yl-y2)D=-xl(y2z3-y3z2)-x2(y3zl-ylz3)-x3(ylz2-y2zl)三维变换存储坐标实现矩阵系统实现三角法系统创建变换矩阵如何创建透视变换对象存储坐标首先可以编写星空模拟代码。那么我们基本的结构是什么样？每一个对象的描述是如何存储的？为解决这个问题，首先我们思索另一个问题：我们须要的是什么样的坐标系？最明显的答案是：屏幕坐标系：相对于显示器的原点的2D坐标系本地坐标系：相对于对象的原点的3D坐标系但是我们不要
12、遗忘变换中间用到的坐标系，例如：世界坐标系：相对于3D世界的原点三维坐标系对齐(视点)坐标系：世界坐标系的变换，视察者的位置在世界坐标系的原点。下面是坐标的基本结构：/二维坐标typedefstructshortx,y;_2D;三维坐标typedefstructfloatx,y,z;_3D;这里,我们定义了称为顶点的坐标结构。因为“顶点”一词指两个或两个以上菱形边的交点。我们的顶点可以简洁地认为是描述不同系统的矢量。不同的坐标系的坐标typedefstruct(_3D1.ocal;_3DWorld;_3DAligned;Vertex_t;实现矩阵系统我们须要存储我们的矩阵在4x4浮点数矩阵中。
13、所以当我们须要做变换是我们定义如下矩阵：floatmatrix44;然后我们定义一些函数来拷贝临时矩阵到全局矩阵：voidMAT_Copy(floatsource44,floatdest44)(inti,j;for(i=0;i4;i+)for(j=0;j4;j+)destij=sourceij;很简洁！现在我们来写两个矩阵相乘的函数。同时可以理解上面的一些有关矩阵相乘的公式代码如下：voidMATMuIt(floatmat144,floatmat244,floatdest44)(inti,j;for(i=0;i4;i+)for(j=0;jx=Source-x*mat00+Source-y*ma
14、t10+Source-z*mat20+mat30;Dest-y=Source-x*mat0l+Source-y*mat1l+Source-z*mat2l+mat31;Dest-z=Source-x*mat02+Source-y*mat12+Source-z*mat22+mat32;)/Source源矢量(坐标)/mat变换矩阵/Dest目标矩阵(坐标)我们已经得到了矩阵变换函数，不错吧！留意,这里的矩阵变换与我们学过的矩阵变换不同一般的,Y=TX,T为变换矩阵，这里为Y=XT,由于矩阵T为4x4矩阵实现三角法系统几乎每一个C编译器都带有有三角函数的数学库，但是我们须要简洁的三角函数时，不是每次
15、都运用它们。正弦和余弦的计算是阶乘和除法的大量运算。为提高计算速度，我们建立自己的三角函数表。首先确定你须要的角度的个数，然后在这些地方用下面的值代替：floatSinTable256,CosTable256;然后运用宏定义，它会把每一个角度变成正值，并对于大于360度的角度进行周期变换，然后返回须要的值。假如须要的角度数是2的幕次，那么我们可以运用&代替线，它使程序运行更快。例如256。所以在程序中尽量选取2的基次。三角法系统：defineSIN(x)SinTableABS(int)X&255)defineCOS(x)CosTableABS(int)x&255)一旦我们已经定义了须要的东西，
16、建立初始化函数，并且在程序中调用宏。voidM3D_Init()intd;for(d=0;d(f*x/z+XOrigin,f*y/z+YOrigin)其中f是“焦点距离”，它表示从视察者到屏幕的距离，一般在80到200厘米之间。XOrigin和YOrigin是屏幕中心的坐标，(x,y,z)在对齐坐标系上。那么投影函数应当是什么样？defineF0CA1._DISTANCE200定义焦点距南voidProject(vertex_t*Vertex)if(!Verte-A1igned.z)Verte-Aligned.z=l;Verte-Screen.x=F0CA1._DISTANCE*Verte-A
17、ligned.x/Verte-Aligned.z+XOrigin;Verte-Screen.y=FoCA1.DISTANCE*Verte-A1igned.y/Verte-Aligned.z+YOrigin;)得到屏幕上的投影坐标因为0不能做除数，所以对Z进行推断。变换对象既然我们已经驾驭了全部的变换顶点的工具，就应当了解须要执行的主要步骤。一、初始化每一个顶点的本地坐标二、设置全局矩阵为单位阵三、依据对象的尺寸缩放全局矩阵四、依据对象的角度来旋转全局矩阵五、依据对象的位置移动全局矩阵六、把本地坐标乘以全局矩阵来得到世界坐标系七、设置全局矩阵为单位阵八、用观测者的位置的负值平移全局矩阵九、用观测
18、者的角度的负值旋转全局矩阵十、把世界坐标系与全局矩阵相乘得到对齐坐标系十一、投影对齐坐标系来得到屏幕坐标即：本地坐标系一世界坐标系一对齐坐标系一屏幕坐标系多边形填充多边形结构发觉三角形绘制三角形多边形结构我们如何存储我们的多边形？首先，我们必需知道再这种状态下多边形是二维多边形，而且由于初始多边形是三维的，我们仅须要一个临时的二维多边形，所以我们能够设置二维顶点的最大数为一个常量，而没有奢侈内存：2D结构：typedefstruct_2DPoints20;intPointsCount;intTexture;Polygon2D_t;3D结构：typedefstruct(intCount;int*
19、Vertex;intTexture;Vertex_tP,M,N;Polygont;为什么顶点数组包含整数值呢?细致思索一下,例如在立方体内，三个多边形公用同一个顶点,所以在三个多边形里存储和变换同一个顶点会奢侈内存和时间。我们更情愿存储它们在一个对象结构里，而且在多边形结构里，我们会放置相应顶点的索引。请看下面的结构：typedefstructintVertexCount;intPolygonCount;Vertex_t*Vertex;Polygon_t*Polygon;_3DScaling;_3DPosition;_3DAngle;intNeedUpdate;Object_t;发觉三角形因为
20、绘制一个三角形比绘制随意的多边形要简洁，所以我们从把多边形分割成三顶点的形态。这种方法特别简洁和干脆：voidPO1.Y_Draw(Polygon2Dt*Polygon)(_2DP1,P2,P3;inti;Pl=Polygon-Points0;for(i=l;iPointsCount-l;i+)P2=Polygon-Pointsi;P3=Polygo11-Pointsi+l;PO1.Y_Triang1e(P1,P2,P3,Polygon-Texture);上面的算法，对于凹多边形就不太适用lIIII1绘制三角形现在怎样得到三角形函数?我们怎样才能画出每一条有关的直线,并且如何发觉每一行的起始和
21、牢固的X坐标。我们通过定义两个简洁有用的宏定义起先来区分垂直地两个点和两个数：defineMIN(a,b)(ab)?（八）:(b)defineMaxPoint(a,b)(a.yb.y)?a:b)defineMinPoint(a,b)(b.ya.y)?a:b)然后我们定义三个宏来区分三个点：defineMaxPoint3(a,b,c)MaxPoint(MaxPoint(a,b),MaxPoint(b,c)defineMidPoint3(a,b,c)MaxPoint(MinPoint(a,b),MinPoint(a,c)defineMinPoint3(a,b,c)MinPoint(MinPoint
22、(a,b),MinPoint(b,c)你或许留意到MidPoint3宏不总是正常地工作，取决于三个点排列的依次，例如,ab&ac那么由MidPoint3得到的是a,但它不是中间点。我们用if语句来修正这个缺点，下面为函数的代码：voidPO1.Y_Triangle(_2Dpl,_2Dp2,_2Dp3,charc)(_2Dpld,p2d,p3d;intxdl,ydl,xd2,yd2,i;int1.x,Rx;首先我们把三个点进行排序：pld=MinPoint3(pl,p2,p3);p2d=MidPoint3(p2,p3,pl);p3d=MaxPoint3(p3,pl,p2);当调用这些宏的时候为什
23、么会有点的依次的变更？(作者也不清晰)可能这些点被逆时针传递。试图变更这些宏你的屏幕显示的是垃圾！现在我们并不确定中间的点，所以我们做一些检查，而且在这种状态下，得到的中间点有好像是错误的，所以我们修正：if(p2.ypl.y)Pld=MinPOint3(p2,pl,p3);p2d=MidPoint3(pl,p3,p2);这些点的排列依次看起来很惊奇，但是试图变更他们那么全部的东西就乱套了。只有理解或接受这些结论。现在我们计算增量xdl=p2d.-pld.x;ydl=p2d.y-pld.y;xd2=p3d.-pld.x;yd2=p3d.y-pld.y;OK,第一步已经完成，假如有增量y：if(
24、ydl)for(i=pld.y;i=p2d.y;i+)我们用X的起始坐标计算X值，在当前点和起始点之间加上增量y,乘以斜率（X/y）的相反值。1.x=plcl.X+Rx=pld.X+假如不在同一个点，绘制线段,(i-pld.y)*xdl)/ydl;(i-pld.y)*xd2)/yd2;按次序传递这两个点：if(1.x!=Rx)VIDJ1.ine(MIN(1.x,Rx),MAX(1.x,Rx),i,c);)现在我们重新计算第一个增量，而且计算其次条边xdl=p3d.-p2d.x;ydl=p3d.y-p2d.y;if(ydl)for(i=p2d.y;i=p3d.y;i+)(1.x=pld.x+(i
25、-pld.y)*xd2)/yd2;Rx=p2d.x+(i-p2d.y)*xdl)/ydl;if(1.x!=Rx)VIDJ1.ine(MIN(1.x,Rx),MAX(1.x,Rx),i,c);以上我们已经得到多边形填充公式，对于平面填充更加简洁:voidVIDJ1.ine(intxl,intx2,inty,charc)(intx;for(x=xl;x=x2;x+)putpixel(x,y,c);Sutherland-Hodgman剪贴概述Z-剪贴屏幕剪贴概述一般地，我们更情愿剪贴我们的多边形。必需靠着屏幕的边缘剪贴，但也必需在视察的前方(我们不须要绘制视察者后面的事物，当Z左边特别小时)。当我们
26、剪贴一个多边形，并不考虑是否每一个点在限制以内，而我们更情愿增加必需的顶点，所以我们须要一个第三个多边形结构：typedefstructintCount;_3DVertex20;CPolygon_t;由于我们有附加的顶点来投影，我们不再投影顶点，而是投影剪贴的3D多边形到2D多边形。voidM3DProject(CPolygon_t*Polygon,Polygon2Dt*Clipped,intfocaldistance)(intv;for(v=0;vCount;v+)(if(!Polygon-Vertexv.z)Polygon-Vertexv.z+;Clipped-Pointsv.x=Poly
27、go11-Vertexv.x*focalclistancePolygon-Vertexv.z+0rigiX；Clipped-Pointsv.y=Polygon-Vertexv.y*focaldistance/Polygon-Vertexv.z+0rigiy;)Clipped-PointsCount=Polygon-Count;Z-剪贴首先我们定义计算在第一个点和其次个点之间以及在第一个点和最小Z值的z增量的宏。然后，我们计算比例，留意不要被零除。WORDZMin=20;defineINIT_ZDE1.TASdold=V2.z-Vl.z;dnew=ZMin-Vl.z;defineINIT_ZC1
28、.IPINIT_ZDE1.TASif(dold)m=dnewdold;我们建立一个函数，它主要剪贴多边形指针的参数(它将登记作为结果的剪贴的顶点)，第一个顶点(我们剪贴的边的起先)和其次个顶点(最终)：voidC1.lP_Front(CPOlygon_t*Polygon,_3DVI,_3DV2)floatdold,dnew,m=l;INIT_ZC1.IP现在我们必需检测边缘是否完全地在视口里，离开或进入视口。假如边缘没有完全地在视口里，我们计算视口与边缘的交线，用m值表示，用INrr/C1.IP计算。假如边缘在视口里：if(VI.z=ZMin)&(V2.z=ZMin)Polygo11-Vert
29、exPolygon-Count+=V2;假如边缘正离开视口：if(VI.z=ZMin)&(V2.zVertexPolygon-Count.x=Vl.x+(V2.-Vl.x)*m;Polygon-VertexPolygon-Count.y=Vl.y+(V2.y-Vl.y)*m;Polygon-VertexPolygon-Count+.z=ZMin;假如边缘正进入视口：if(VI.z=ZMin)Polygon-VertexPolygon-Count.x=Vl.x+(V2.-Vl.x)*m;Polygo11-VertexPolygon-Count.y=Vl.y+(V2.y-Vl,y)*m;Polyg
30、o11-VertexPolygon-Count+.z=ZMin;Polygon-VertexPolygon-Count+=V2;这就是边缘Z-剪贴函数)现在我们可以写下完整的多边形Z-剪贴程序。为了有代表性，定义一个宏用来在一个对象结构中找寻适当的多边形顶点。defineVert(x)Object-VertexPolygon-Vertexx下面是它的函数:voidC1.IPZ(Polygon_t*Polygon,Object_t*0bject,CPolygon_t*ZC1ipped)(intd,v;ZClipped-Count=0;for(v=0;vCount;v+)d=v+l;if(d=Po
31、lygon-Count)d=0;C1.IPFront(ZClipped,Vert(v).Aligned,Vert(d).Aligned);这个函数相当简洁：它仅仅调用FrontClip函数来做顶点交换。剪贴屏幕剪贴屏幕的边缘同Z-剪贴相同，但是我们有四个边缘而不是一个。所以我们须要四个不同的函数。但是它们须要同样的增量初始化：defineINIT_DE1.TASdx=V2.-Vl.x;dy=V2.y-Vl.y;defineINIT_C1.IPINIT,DE1.TASif(dx)m=dydx;边缘是:_2DTop1.eft,DownRight;为了进一步简化_2D和_3D结构的运用，我们定义两个
32、有用的函数:_2DP2D(shortx,shorty)7_2DTemp;Temp,x=x;Temp,y=y;returnTemp;3DP3D(floatx,floaty,floatz)_3DTemp;Temp,x=x;Temp,y=y;Temp.z=z;returnTemp;然后运用这两个函数来指定视口:Top1.eft=P2D(0,0);DownRight=P2D(319,199);下面是四个边缘剪贴函数：/*剪贴左边缘*/voidC1.IP_1.eft(Polygon2D.t*Polygon,_2DV1,_2DV2)(floatdx,dy,m=l;INIT_C1.IPif(VI.x=Top
33、1.eft.x)&(V2.x=Top1.eft.x)Polygon-PointsPolygon-PointsCount+=V2;/*leaving*if(VI.x=Top1.eft.x)&(V2.xPointsPolygo11-PointsCount.X=Top1.eft.x;PoiygOn-PointsPolygon-APointsCount+.y=Vl.y+m*(Top1.eft.-Vl.x);/*entering*if(VI.x=Top1.eft.x)Polygon-PointsPolygon-PointsCount.X=Top1.eft.x;Polygon-PointsPo1ygon-
34、PointsCount+.y=V1.y+m*(Top1.eft.-Vl.x);Polygon-PointsPolygo11-PointsCount+=V2;)*剪贴右边缘*/voidC1.IP_Right(Polygon2D,t*Polygon,_2DV1,_2DV2)(floatdx,dy,m=l;INIT_C1.IPif(VI.x=DownRight.x)&(V2.xPointsPolygo11-PointsCount+=V2;/*leaving*if(VI.xDownRight.x)(Polygon-PointsPolygon-PointsCount.X=DownRight.x;Poly
35、gon-PointsPolygon-PointsCount+.y=Vl.y+m*(DownRight.-Vl.x);)/*eNTERING*if(VI.xDownRight.x)&(V2.xPointsPolygon-PointsCount.X=DownRight.x;Polygon-PointsPolygon-PointsCount+.y=Vl.y+m*(DownRight.-Vl.x);Polygon-PointsPolygon-PointsCount+=V2;)*剪贴上边缘*/voidC1.IP_Top(Polygon2D_t*Polygon,_2DVI,_2DV2)(floatdx,dy,m=l;INIT_C1.IPif(VI.y=Top1.eft.y)&(V2.y=Top1.eft.y)Polygon-PointsPolygo11-PointsCount+=V2;/*leaving*if(VI.y=Top1.eft.y)&(V2.yPointsPolygon-PointsCount.x=Vl.x+(Top1.eft.y-Vl.y)/m;elsePolygon-PointsPolygon-PointsCount.x=Vl.x;Polygon-PointsPolygon-PointsCount+.y=Top1.eft.y;/*ENTERING*
