3D图象算法

3D图象算法JeromeSt-Louis3D简介我们首先从坐标系统开始。你也许知道在2D里我们经常使用Ren?笛卡儿坐标系统在平面上来识别点。我们使用二维(X,Y):X表示水平轴坐标,Y表示纵轴坐标。在3维坐标系，我们增加了Z，一般用它来表示深度。所以为表示三维坐标系的一个点，我们用三个参数(X,Y,Z)。这里有不同的笛卡儿三维系统可以使用。但是它们都是左手螺旋或右手螺旋的。右手螺旋是右手手指的卷曲方向指向Z轴正方向，而大拇指指向X轴正方向。左手螺旋是左手手指的卷曲方向指向Z轴负方向。实际上，我们可以在任何方向上旋转这些坐标系，而且它们仍然保持本身的特性。在计算机图形学，常用坐标系为左手坐标系，所以我们也使用它。：X正轴朝右Y正轴向上Z正轴指向屏幕里矢量什么是矢量？几句话，它是坐标集合。首先我们从二维矢量开始，(X,Y)：例如矢量P(4,5)（一般，我们用-表示矢量）。我们认为矢量P代表点(4,5)，它是从原点指向(4,5)的有方向和长度的箭头。我们谈论矢量的长度指从原点到该点的距离。二维距离计算公式是|P|=sqrt(x^2+y^2)这里有一个有趣的事实：在1D（点在单一的坐标轴上），平方根为它的绝对值。让我们讨论三维矢量：例如P(4,-5,9)，它的长度为|P|=sqrt(x^2+y^2+z^2)它代表在笛卡儿3D空间的一个点。或从原点到该点的一个箭头代表该矢量。在有关操作一节里，我们讨论更多的知识。矩阵开始，我们从简单的开始：我们使用二维矩阵4乘4矩阵，为什么是4乘4？因为我们在三维坐标系里而且我们需要附加的行和列来完成计算工作。在二维坐标系我们需要3乘3矩阵。着意味着我们在3D中有4个水平参数和4个垂直参数，一共16个。例如：4x4单位矩阵|1000||0100||0010||0001|因为任何其它矩阵与之相乘都不改变，所以称之为单位阵。又例如有矩阵如下：|10-72245||sin(a)cos(a)3432||-3528176||45-993216|有关矢量和矩阵的操作我们已经介绍了一些非常简单的基本概念，那么上面的知识与三维图形有什么关系呢？本节我们介绍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^W)=V?W/|V||W|注意^并不表示指数而是两个矢量的夹角。点积可以用来计算光线于平面的夹角，我们在计算阴影一节里会详细讨论。现在讨论叉乘：(x1,y1,z1)X(x2,y2,z2)=(y1z2-z1y2,z1x2-x1z2,x1y2-y1x2)叉乘对于计算屏幕的法向量非常有用。OK，我们已经讲完了矢量的基本概念。我们开始两个矩阵的和。它与矢量相加非常相似，这里就不讨论了。设I是矩阵的一行，J是矩阵的一列，(i,j)是矩阵的一个元素。我们讨论与3D变换有关的重要的矩阵操作原理。两个矩阵相乘，而且MxNNxM。例如：A4x4矩阵相乘公式如果A=(aij)4x4，B=(bij)4x4,那么AxB=|Sa1jbj1Sa1jbj2Sa1jbj3Sa1jbj4||||Sa2jbj1Sa2jbj2Sa2jbj3Sa2jbj4||||Sa3jbj1Sa3jbj2Sa3jbj3Sa3jbj4||||Sa4jbj1Sa4jbj2Sa4jbj3Sa4jbj4|其中j=1,2,3,4而且如果AxB=(cik)4x4那么我们可以在一行上写下：cik=S4,j=1aijbjk(a1,a2,a3)xB=(Sum(aibi1)+b4,1,Sum(aibi2)+b4,2,Sum(aibi3)+b4,3)现在,我们可以试着把一些矩阵乘以单位阵来了解矩阵相乘的性质。我们把矩阵与矢量相乘结合在一起。下面有一个公式把3D矢量乘以一个4x4矩阵（得到另外一个三维矢量）如果B=(bij)4x4，那么：(a1,a2,a3)xB=(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)==(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)所以我们可以写出像在二维中同样的变换公式。我们通过乘以变换矩阵而得到新的矢量，新矢量将指向变换点。下面是所有三维变换矩阵：平移(tx,ty,tz)的矩阵|1000||0100||0010||txtytz1|缩放(sx,sy,sz)的矩阵|sz000||0sy00||00sx0||0001|绕X轴旋转角q的矩阵|1000||0cos(q)sin(q)0||0-sin(q)cos(q)0||0001|绕Y轴旋转角q的矩阵:|cos(q)0-sin(q)0||0100||sin(q)0cos(q)0||0001|绕Z轴旋转角q的矩阵:|cos(q)sin(q)00||-sin(q)cos(q)00||0010||0001|所以我们已经可以结束关于变换的部分.通过这些矩阵我们可以对三维点进行任何变换.平面和法向量平面是平坦的，无限的，指向特定方向的表面可以定义平面如下：Ax+By+Cz+D=0其中A,B,C称为平面的法向量，D是平面到原点的距离。我们可以通过计算平面上的两个矢量的叉积得到平面的法向量。为得到这两个矢量，我们需要三个点。P1，P2，P3逆时针排列，可以得到：矢量1=P1-P2和矢量2=P3-P2计算法向量为：法向量=矢量1X矢量2把D移到等式的右边得到：D=-(Ax+By+Cz)或D=-(A??1.x+B??2.y+C??3.z)或更简单: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)三维变换存储坐标实现矩阵系统实现三角法系统创建变换矩阵如何创建透视变换对象存储坐标首先可以编写星空模拟代码。那么我们基本的结构是什么样？每一个对象的描述是如何存储的？为解决这个问题，首先我们思考另一个问题：我们需要的是什么样的坐标系？最明显的答案是：屏幕坐标系：相对于显示器的原点的2D坐标系本地坐标系：相对于对象的原点的3D坐标系但是我们不要忘记变换中间用到的坐标系，例如：世界坐标系：相对于3D世界的原点三维坐标系对齐(视点)坐标系：世界坐标系的变换，观察者的位置在世界坐标系的原点。下面是坐标的基本结构：//二维坐标typedefstruct{shortx,y;}_2D;//三维坐标typedefstruct{floatx,y,z;}_3D;这里,我们定义了称为顶点的坐标结构。因为“顶点”一词指两个或两个以上菱形边的交点。我们的顶点可以简单地认为是描述不同系统的矢量。//不同的坐标系的坐标typedefstruct{_3DLocal;_3DWorld;_3DAligned;}Vertex_t;实现矩阵系统我们需要存储我们的矩阵在4x4浮点数矩阵中。所以当我们需要做变换是我们定义如下矩阵：floatmatrix[4][4];然后我们定义一些函数来拷贝临时矩阵到全局矩阵:voidMAT_Copy(floatsource[4][4],floatdest[4][4]){inti,j;for(i=0;i4;i++)for(j=0;j4;j++)dest[i][j]=source[i][j];}很简单！现在我们来写两个矩阵相乘的函数。同时可以理解上面的一些有关矩阵相乘的公式代码如下：voidMAT_Mult(floatmat1[4][4],floatmat2[4][4],floatdest[4][4]){inti,j;for(i=0;i4;i++)for(j=0;j4;j++)dest[i][j]=mat1[i][0]*mat2[0][j]+mat1[i][1]*mat2[1][j]+mat1[i][2]*mat2[2][j]+mat1[i][3]*mat2[3][j];}//mat1----矩阵1//mat2----矩阵2//dest----相乘后的新矩阵现在你明白了吗？现在我们设计矢量与矩阵相乘的公式。voidVEC_MultMatrix(_3D*Source,floatmat[4][4],_3D*Dest){Dest-x=Source-x*mat[0][0]+Source-y*mat[1][0]+Source-z*mat[2][0]+mat[3][0];Dest-y=Source-x*mat[0][1]+Source-y*mat[1][1]+Source-z*mat[2][1]+mat[3][1];Dest-z=Source-x*mat[0][2]+Source-y*mat[1][2]+Source-z*mat[2][2]+mat[3][2];}//Source-----源矢量(坐标)//mat--------变换矩阵//Dest-------目标矩阵(坐标)我们已经得到了矩阵变换函数，不错吧！！//注意,这里的矩阵变换与我们学过的矩阵变换不同//一般的,Y=TX,T为变换矩阵，这里为Y=XT，//由于矩阵T为4x4矩阵实现三角法系统几乎每一个C编译器都带有有三角函数的数学库，但是我们需要简单的三角函数时，不是每次都使用它们。正弦和余弦的计算是阶乘和除法的大量运算。为提高计算速度，我们建立自己的三角函数表。首先决定你需要的角度的个数，然后在这些地方用下面的值代替：floatSinTable[256],CosTable[256];然后使用宏定义，它会把每一个角度变成正值，并对于大于360度的角度进行周期变换，然后返回需要的值。如果需要的角度数是2的幂次，那么我们可以使用&代替%，它使程序运行更快。例如256。所以在程序中尽量选取2的幂次。三角法系统：#defineSIN(x)SinTable[ABS((int)x&255)]#defineCOS(x)CosTable[ABS((int)x&255)]一旦我们已经定义了需要的东西，建立初始化函数，并且在程序中调用宏。voidM3D_Init(){intd;for(d=0;d256;d++){SinTable[d]=sin(d*PI/128.0);CosTable[d]=cos(d*PI/128.0);}}建立变换矩阵下面使用C编写的变换矩阵代码floatmat1[4][4],mat2[4][4];voidMAT_Identity(floatmat[4][4]){mat[0][0]=1;mat[0][1]=0;mat[0][2]=0;mat[0][3]=0;mat[1][0]=0;mat[1][1]=1;mat[1][2]=0;mat[1][3]=0;mat[2][0]=0;mat[2][1]=0;m