3D圖像算法從入門到進階(包含C實現(xiàn))

D圖象算法3D簡介我們首先從坐標(biāo)系統(tǒng)開始。你也許知道在2D里我們經(jīng)常使用笛卡兒坐標(biāo)系統(tǒng)在平面上來識別點。我們使用二維(X,Y):X表示水平軸坐標(biāo),Y表示縱軸坐標(biāo)。在3維坐標(biāo)系，我們增加了Z，一般用它來表示深度。所以為表示三維坐標(biāo)系的一個點，我們用三個參數(shù)(X,Y,Z)。這里有不同的笛卡兒三維系統(tǒng)可以使用。但是它們都是左手螺旋或右手螺旋的。右手螺旋是右手手指的卷曲方向指向Z軸正方向，而大拇指指向X軸正方向。左手螺旋是左手手指的卷曲方向指向Z軸負方向。實際上，我們可以在任何方向上旋轉(zhuǎn)這些坐標(biāo)系，而且它們?nèi)匀槐３直旧淼奶匦?。在計算機圖形學(xué)，常用坐標(biāo)系為左手坐標(biāo)系(手背向上)，所以我們也使用它。：

X正軸朝右

Y正軸向上

Z正軸指向屏幕里

矢量

什么是矢量？幾句話，它是坐標(biāo)集合。首先我們從二維矢量開始，(X,Y)：例如矢量P(4,5)（一般，我們用->表示矢量）。我們認為矢量P代表點(4,5)，它是從原點指向(4,5)的有方向和長度的箭頭。我們談?wù)撌噶康拈L度指從原點到該點的距離。二維距離計算公式是

|P|=sqrt(x^2+y^2)

這里有一個有趣的事實：在1D（點在單一的坐標(biāo)軸上），平方根為它的絕對值。讓我們討論三維矢量：例如P(4,-5,9)，它的長度為

|P|=sqrt(x^2+y^2+z^2)

它代表在笛卡兒3D空間的一個點?；驈脑c到該點的一個箭頭代表該矢量。在有關(guān)操作一節(jié)里，我們討論更多的知識。

矩陣

開始，我們從簡單的開始：我們使用二維矩陣4乘4矩陣，為什么是4乘4？因為我們在三維坐標(biāo)系里而且我們需要附加的行和列來完成計算工作（本質(zhì)原因：在計算機圖形學(xué)里應(yīng)用的圖形變換，實際上是在仿射空間而不是向量空間中進行的）。在二維坐標(biāo)系我們需要3乘3矩陣。著意味著我們在3D中有4個水平參數(shù)和4個垂直參數(shù)，一共16個。例如：

4x4單位矩陣

|1000|

|0100|

|0010|

|0001|

因為任何其它矩陣與之相乘都不改變，所以稱之為單位陣。又例如有矩陣如下：

|10

-72245|

|sin(a)cos(a)3432|

|-35

2817

6|

|45

-993216|

有關(guān)矢量和矩陣的操作

我們已經(jīng)介紹了一些非常簡單的基本概念，那么上面的知識與三維圖形有什么關(guān)系呢？

本節(jié)我們介紹3D變換的基本知識和其它的一些概念。它仍然是數(shù)學(xué)知識。我們要討論有關(guān)矢量和矩陣操作。讓我們從兩個矢量和開始：

(x1,y1,z1)+(x2,y2,z2)=(x1+x2,y1+y2,z1+z2)

幾何意義：等于兩個矢量組成的平行四邊形的長對角線的矢量兩個矢量減法的幾何意義：等于兩個矢量組成的三角形的另一條邊的矢量

很簡單，現(xiàn)在把矢量乘于系數(shù)（數(shù)乘）：

k？(x,y,z)=(kx,ky,kz)幾何意義：將矢量進行縮放點積如下表示：（點積是一個標(biāo)量）

(x1,y1,z1)?(x2,y2,z2)=x1x2+y1y2+z1z2

實際上，兩個矢量的點積被它們的模的乘積除，等于兩個矢量夾角的余弦（兩個矢量的模與其夾角的余弦之積稱為兩個矢量的數(shù)量積（或稱內(nèi)積、點積））。所以

cos(V^W)=V?W/|V||W|幾何意義：兩個矢量的點積衡量著兩個向量的角度關(guān)系。在物理上的意義如果兩個矢量分別代表力和位移，那么兩個矢量的點積就是功。

注意"^"并不表示指數(shù)而是兩個矢量的夾角。點積可以用來計算光線與平面的夾角，我們在計算陰影一節(jié)里會詳細討論。

現(xiàn)在討論叉乘：

(x1,y1,z1)X(x2,y2,z2)=(y1z2-z1y2,z1x2-x1z2,x1y2-y1x2)

幾何意義：叉乘的結(jié)果是一個偽向量，但是他的模是以此二向量為相鄰兩邊的平行四邊形面積

叉乘對于計算屏幕的法向量非常有用。

OK，我們已經(jīng)講完了矢量的基本概念。我們開始兩個矩陣的和。它與矢量相加非常相似，這里就不討論了。設(shè)I是矩陣的一行，J是矩陣的一列，(i,j)是矩陣的一個元素。我們討論與3D變換有關(guān)的重要的矩陣操作原理。矩陣相乘的幾何意義：把兩次線性變換合成一次兩個矩陣相乘，而且MxN<>NxM。例如：(矩陣乘法是有順序的)

AB4x4矩陣相乘公式

如果A=(aij)4x4，B=(bij)4x4,那么

AxB=

|S>a1jbj1S>a1jbj2S>a1jbj3S>a1jbj4|

||

|S>a2jbj1S>a2jbj2S>a2jbj3S>a2jbj4|

||

|S>a3jbj1S>a3jbj2S>a3jbj3S>a3jbj4|

||

|S>a4jbj1S>a4jbj2S>a4jbj3S>a4jbj4|

其中j=1,2,3,4

而且如果AxB=(cik)4x4那么我們可以在一行上寫下：

cik=S>4,j=1aijbjk

(a1,a2,a3)xB=

(Sum(aibi1)+b4,1,Sum(aibi2)+b4,2,Sum(aibi3)+b4,3)

現(xiàn)在,我們可以試著把一些矩陣乘以單位矩陣來了解矩陣相乘的性質(zhì)。我們把矩陣與矢量相乘結(jié)合在一起。下面有一個公式把3D矢量乘以一個4x4矩陣（得到另外一個三維矢量）如果B=(bij)4x4，那么：

(a1,a2,a3)xB=(S>aibi1+b4,1,S>aibi2+b4,2,S>aibi3+b4,3)>

這就是矢量和矩陣操作公式。從這里開始，代碼與數(shù)學(xué)之間的聯(lián)系開始清晰。

變換

我們已經(jīng)見過象這樣的公式：

t(tx,ty):(x,y)==>(x+tx,y+ty)

這是在二維笛卡兒坐標(biāo)系的平移等式。下面是縮放公式：

s(k):(x,y)==>(kx,ky)

旋轉(zhuǎn)等式:

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)

旋轉(zhuǎn)公式（圍繞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軸旋轉(zhuǎn)角q的矩陣

|1000|

|0cos(q)sin(q)0|

|0-sin(q)cos(q)0|

|0001|

繞Y軸旋轉(zhuǎn)角q的矩陣:

|cos(q)0-sin(q)0|

|0100|

|sin(q)0cos(q)0|

|0001|

繞Z軸旋轉(zhuǎn)角q的矩陣:

|cos(q)sin(q)00|

|-sin(q)cos(q)00|

|0010|

|0001|

所以我們已經(jīng)可以結(jié)束關(guān)于變換的部分.通過這些矩陣我們可以對三維點進行任何變換.

平面和法向量

平面是平坦的，無限的，指向特定方向的表面可以定義平面如下：

Ax+By+Cz+D=0

其中A,B,C稱為平面的法向量，D是平面到原點的距離。我們可以通過計算平面上的兩個矢量的叉積得到平面的法向量。為得到這兩個矢量，我們需要三個點。P1，P2，P3逆時針排列（轉(zhuǎn)入仿射空間了），可以得到：

矢量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分量?？梢院喕僮靼慈缦碌仁剑?/p>

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)

三維變換

存儲坐標(biāo)

實現(xiàn)矩陣系統(tǒng)

實現(xiàn)三角法系統(tǒng)

創(chuàng)建變換矩陣

如何創(chuàng)建透視

變換對象

存儲坐標(biāo)

首先可以編寫星空模擬代碼。那么我們基本的結(jié)構(gòu)是什么樣？每一個對象的描述是如何存儲的？為解決這個問題，首先我們思考另一個問題：我們需要的是什么樣的坐標(biāo)系？最明顯的答案是：

屏幕坐標(biāo)系：相對于顯示器的原點的2D坐標(biāo)系

本地坐標(biāo)系：相對于對象的原點的3D坐標(biāo)系

但是我們不要忘記變換中間用到的坐標(biāo)系，例如：

世界坐標(biāo)系：相對于3D世界的原點三維坐標(biāo)系

對齊(視點)坐標(biāo)系：世界坐標(biāo)系的變換，觀察者的位置在世界坐標(biāo)系的原點。

下面是坐標(biāo)的基本結(jié)構(gòu)：

//二維坐標(biāo)

typedefstruct

{

shortx,y;

}_2D;

//三維坐標(biāo)

typedefstruct

{

floatx,y,z;

}_3D;

這里,我們定義了稱為頂點的坐標(biāo)結(jié)構(gòu)。因為“頂點”一詞指兩個或兩個以上菱形邊的交點。我們的頂點可以簡單地認為是描述不同系統(tǒng)的矢量。

//不同的坐標(biāo)系的坐標(biāo)

typedefstruct

{

_3DLocal;

_3DWorld;

_3DAligned;

}Vertex_t;

實現(xiàn)矩陣系統(tǒng)

我們需要存儲我們的矩陣在4x4浮點數(shù)矩陣中。所以當(dāng)我們需要做變換是我們定義如下矩陣：

floatmatrix[4][4];

然后我們定義一些函數(shù)來拷貝臨時矩陣到全局矩陣:

voidMAT_Copy(floatsource[4][4],floatdest[4][4])

{

inti,j;

for(i=0;i<4;i++)

for(j=0;j<4;j++)

dest[i][j]=source[i][j];

}

很簡單！現(xiàn)在我們來寫兩個矩陣相乘的函數(shù)。同時可以理解上面的一些有關(guān)矩陣相乘的公式代碼如下：

voidMAT_Mult(floatmat1[4][4],floatmat2[4][4],floatdest[4][4])

{

inti,j;

for(i=0;i<4;i++)

for(j=0;j<4;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相乘后的新矩陣

現(xiàn)在你明白了嗎？現(xiàn)在我們設(shè)計矢量與矩陣相乘的公式。

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源矢量(坐標(biāo))

//mat變換矩陣

//Dest目標(biāo)矩陣(坐標(biāo))

我們已經(jīng)得到了矩陣變換函數(shù)，不錯吧??！

//注意,這里的矩陣變換與我們學(xué)過的矩陣變換不同

//一般的,Y=TX,T為變換矩陣，這里為Y=XT，

//由于矩陣T為4x4矩陣

實現(xiàn)三角法系統(tǒng)

幾乎每一個C編譯器都帶有有三角函數(shù)的數(shù)學(xué)庫，但是我們需要簡單的三角函數(shù)時，不是每次都使用它們。正弦和余弦的計算是階乘和除法的大量運算。為提高計算速度，我們建立自己的三角函數(shù)表。首先決定你需要的角度的個數(shù)，然后在這些地方用下面的值代替：

floatSinTable[256],CosTable[256];

然后使用宏定義，它會把每一個角度變成正值，并對于大于360度的角度進行周期變換，然后返回需要的值。如果需要的角度數(shù)是2的冪次，那么我們可以使用"&"代替"%"，它使程序運行更快。例如256。所以在程序中盡量選取2的冪次。

三角法系統(tǒng)：

#defineSIN(x)SinTable[ABS((int)x&255)]

#defineCOS(x)CosTable[ABS((int)x&255)]

一旦我們已經(jīng)定義了需要的東西，建立初始化函數(shù)，并且在程序中調(diào)用宏。

voidM3D_Init()

{

intd;

for(d=0;d<256;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;mat[2][2]=1;mat[2][3]=0;

mat[3][0]=0;mat[3][1]=0;mat[3][2]=0;mat[3][3]=1;

}

//定義單位陣

voidTR_Translate(floatmatrix[4][4],floattx,floatty,floattz)

{

floattmat[4][4];

tmat[0][0]=1;tmat[0][1]=0;tmat[0][2]=0;tmat[0][3]=0;

tmat[1][0]=0;tmat[1][1]=1;tmat[1][2]=0;tmat[1][3]=0;

tmat[2][0]=0;tmat[2][1]=0;tmat[2][2]=1;tmat[2][3]=0;

tmat[3][0]=tx;tmat[3][1]=ty;tmat[3][2]=tz;tmat[3][3]=1;

MAT_Mult(matrix,tmat,mat1);

MAT_Copy(mat1,matrix);

}

//tx,ty.tz平移參數(shù)

//matrix源矩陣和目標(biāo)矩陣

//矩陣平移函數(shù)

voidTR_Scale(floatmatrix[4][4],floatsx,floatsy,floatsz)

{

floatsmat[4][4];

smat[0][0]=sx;smat[0][1]=0;smat[0][2]=0;smat[0][3]=0;

smat[1][0]=0;smat[1][1]=sy;smat[1][2]=0;smat[1][3]=0;

smat[2][0]=0;smat[2][1]=0;smat[2][2]=sz;smat[2][3]=0;

smat[3][0]=0;smat[3][1]=0;smat[3][2]=0;smat[3][3]=1;

MAT_Mult(matrix,smat,mat1);

MAT_Copy(mat1,matrix);

}

//矩陣縮放

voidTR_Rotate(floatmatrix[4][4],intax,intay,intaz)

{

floatxmat[4][4],ymat[4][4],zmat[4][4];

xmat[0][0]=1;xmat[0][1]=0;xmat[0][2]=0;

xmat[0][3]=0;

xmat[1][0]=0;xmat[1][1]=COS(ax);xmat[1][2]=SIN(ax);

xmat[1][3]=0;

xmat[2][0]=0;xmat[2][1]=-SIN(ax);xmat[2][2]=COS(ax);xmat[2][3]=0;

xmat[3][0]=0;xmat[3][1]=0;xmat[3][2]=0;xmat[3][3]=1;

ymat[0][0]=COS(ay);ymat[0][1]=0;ymat[0][2]=-SIN(ay);ymat[0][3]=0;

ymat[1][0]=0;ymat[1][1]=1;ymat[1][2]=0;ymat[1][3]=0;

ymat[2][0]=SIN(ay);ymat[2][1]=0;ymat[2][2]=COS(ay);ymat[2][3]=0;

ymat[3][0]=0;ymat[3][1]=0;ymat[3][2]=0;ymat[3][3]=1;

zmat[0][0]=COS(az);zmat[0][1]=SIN(az);zmat[0][2]=0;zmat[0][3]=0;

zmat[1][0]=-SIN(az);zmat[1][1]=COS(az);zmat[1][2]=0;zmat[1][3]=0;

zmat[2][0]=0;zmat[2][1]=0;zmat[2][2]=1;zmat[2][3]=0;

zmat[3][0]=0;zmat[3][1]=0;zmat[3][2]=0;zmat[3][3]=1;

MAT_Mult(matrix,ymat,mat1);

MAT_Mult(mat1,xmat,mat2);

MAT_Mult(mat2,zmat,matrix);

}

//ax繞X軸旋轉(zhuǎn)的角度

//ay繞Y軸旋轉(zhuǎn)的角度

//az繞Z軸旋轉(zhuǎn)的角度

//矩陣旋轉(zhuǎn)

如何建立透視

如何建立對象的立體視覺,即顯示器上的一些事物看起來離我們很近,而另外一些事物離我們很遠。透視問題一直是困繞我們的一個問題。有許多方法被使用。我們使用的3D世界到2D屏幕的投影公式：

P(f):(x,y,z)==>(f*x/z+XOrigin,f*y/z+YOrigin)

其中f是“焦點距離”，它表示從觀察者到屏幕的距離，一般在80到200厘米之間。XOrigin和YOrigin是屏幕中心的坐標(biāo)，(x,y,z)在對齊坐標(biāo)系上。那么投影函數(shù)應(yīng)該是什么樣？

#defineFOCAL_DISTANCE200

//定義焦點距離

voidProject(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;

}

//得到屏幕上的投影坐標(biāo)

因為0不能做除數(shù)，所以對z進行判斷。

變換對象

既然我們已經(jīng)掌握了所有的變換頂點的工具，就應(yīng)該了解需要執(zhí)行的主要步驟。

一、初始化每一個頂點的本地坐標(biāo)

二、設(shè)置全局矩陣為單位陣

三、根據(jù)對象的尺寸縮放全局矩陣

四、根據(jù)對象的角度來旋轉(zhuǎn)全局矩陣

五、根據(jù)對象的位置移動全局矩陣

六、把本地坐標(biāo)乘以全局矩陣來得到世界坐標(biāo)系

七、設(shè)置全局矩陣為單位陣

八、用觀測者的位置的負值平移全局矩陣

九、用觀測者的角度的負值旋轉(zhuǎn)全局矩陣

十、把世界坐標(biāo)系與全局矩陣相乘得到對齊坐標(biāo)系

十一、投影對齊坐標(biāo)系來得到屏幕坐標(biāo)

即：本地坐標(biāo)系-->世界坐標(biāo)系-->對齊坐標(biāo)系-->屏幕坐標(biāo)系

多邊形填充

多邊形結(jié)構(gòu)

發(fā)現(xiàn)三角形

繪制三角形

多邊形結(jié)構(gòu)

我們?nèi)绾未鎯ξ覀兊亩噙呅?？首先，我們必須知道再這種狀態(tài)下多邊形是二維多邊形，而且由于初始多邊形是三維的，我們僅需要一個臨時的二維多邊形，所以我們能夠設(shè)置二維頂點的最大數(shù)為一個常量，而沒有浪費內(nèi)存：

2D結(jié)構(gòu)：

typedefstruct

{

_2DPoints[20];

intPointsCount;

intTexture;

}Polygon2D_t;

3D結(jié)構(gòu):

typedefstruct

{

intCount;

int*Vertex;

intTexture;

Vertex_tP,M,N;

}Polygon_t;

為什么頂點數(shù)組包含整數(shù)值呢?仔細思考一下,例如在立方體內(nèi),三個多邊形公用同一個

頂點,所以在三個多邊形里存儲和變換同一個頂點會浪費內(nèi)存和時間。我們更愿意存儲

它們在一個對象結(jié)構(gòu)里，而且在多邊形結(jié)構(gòu)里，我們會放置相應(yīng)頂點的索引。請看

下面的結(jié)構(gòu)：

typedefstruct

{

intVertexCount;

intPolygonCount;

Vertex_t*Vertex;

Polygon_t*Polygon;

_3DScaling;

_3DPosition;

_3DAngle;

intNeedUpdate;

}Object_t;

發(fā)現(xiàn)三角形

因為繪制一個三角形比繪制任意的多邊形要簡單，所以我們從把多邊形分割成

三頂點的形狀。這種方法非常簡單和直接：

voidPOLY_Draw(Polygon2D_t*Polygon)

{

_2DP1,P2,P3;

inti;

P1=Polygon->Points[0];

for(i=1;i<Polygon->PointsCount-1;i++)

{

P2=Polygon->Points[i];

P3=Polygon->Points[i+1];

POLY_Triangle(P1,P2,P3,Polygon->Texture);

}

}

//上面的算法，對于凹多邊形就不太適用

_____

|\|

|\|

|____\|

繪制三角形

現(xiàn)在怎樣得到三角形函數(shù)?我們怎樣才能畫出每一條有關(guān)的直線,并且如何發(fā)現(xiàn)

每一行的起始和結(jié)實的x坐標(biāo)。我們通過定義兩個簡單有用的宏定義開始來區(qū)別

垂直地兩個點和兩個數(shù)：

#defineMIN(a,b)((a<b)?(a):(b))

#defineMAX(a,b)((a>b)?(a):(b))

#defineMaxPoint(a,b)((a.y>b.y)?a:b)

#defineMinPoint(a,b)((b.y>a.y)?a:b)

然后我們定義三個宏來區(qū)別三個點：

#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(a,b),MinPoint(b,c))

你也許注意到MidPoint3宏不總是正常地工作，取決于三個點排列的順序，

例如,a<b&a<c那么由MidPoint3得到的是a,但它不是中間點。

我們用if語句來修正這個缺點，下面為函數(shù)的代碼：

voidPOLY_Triangle(_2Dp1,_2Dp2,_2Dp3,charc)

{

_2Dp1d,p2d,p3d;

intxd1,yd1,xd2,yd2,i;

intLx,Rx;

首先我們把三個點進行排序：

p1d=MinPoint3(p1,p2,p3);

p2d=MidPoint3(p2,p3,p1);

p3d=MaxPoint3(p3,p1,p2);

當(dāng)調(diào)用這些宏的時候為什么會有點的順序的改變？（作者也不清楚）可能這些點被逆時針傳遞。試圖改變這些宏你的屏幕顯示的是垃圾！現(xiàn)在我們并不確定中間的點，所以我們做一些檢查，

而且在這種狀態(tài)下，得到的中間點有似乎是錯誤的，所以我們修正：

if(p2.y<p1.y)

{

p1d=MinPoint3(p2,p1,p3);

p2d=MidPoint3(p1,p3,p2);

}

這些點的排列順序看起來很奇怪，但是試圖改變他們那么所有的東西就亂套了。只有理解或

接受這些結(jié)論?，F(xiàn)在我們計算增量

xd1=p2d.x-p1d.x;

yd1=p2d.y-p1d.y;

xd2=p3d.x-p1d.x;

yd2=p3d.y-p1d.y;

OK，第一步已經(jīng)完成，如果有增量y：

if(yd1)

for(i=p1d.y;i<=p2d.y;i++)

{

我們用x的起始坐標(biāo)計算x值，在當(dāng)前點和起始點之間加上增量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);

}

現(xiàn)在我們重新計算第一個增量，而且計算第二條邊

xd1=p3d.x-p2d.x;

yd1=p3d.y-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);

}

}

以上我們已經(jīng)得到多邊形填充公式，對于平面填充更加簡單：

voidVID_HLine(intx1,intx2,inty,charc)

{

intx;

for(x=x1;x<=x2;x++)

putpixel(x,y,c);

}

Sutherland-Hodgman剪貼

概述

Z-剪貼

屏幕剪貼

概述

一般地，我們更愿意剪貼我們的多邊形。必須靠著屏幕的邊緣剪貼，但也必須在觀察的前方（我們不需要繪制觀察者后面的事物，當(dāng)z左邊非常小時）。當(dāng)我們剪貼一個多邊形，并不考慮是否每一個點在限制以內(nèi)，而我們更愿意增加必須的頂點，所以我們需要一個第三個多邊形結(jié)構(gòu)：

typedefstruct

{

intCount;

_3DVertex[20];

}CPolygon_t;

由于我們有附加的頂點來投影，我們不再投影頂點，而是投影剪貼的3D多邊形到

2D多邊形。

voidM3D_Project(CPolygon_t*Polygon,Polygon2D_t*Clipped,intfocaldistance)

{

intv;

for(v=0;v<Polygon->Count;v++)

{

if(!Polygon->Vertex[v].z)Polygon->Vertex[v].z++;

Clipped->Points[v].x=Polygon->Vertex[v].x*focaldistance/Polygon->Vertex[v].z+Origin.x;

Clipped->Points[v].y=Polygon->Vertex[v].y*focaldistance/Polygon->Vertex[v].z+Origin.y;

}

Clipped->PointsCount=Polygon->Count;

}

Z-剪貼

首先我們定義計算在第一個點和第二個點之間以及在第一個點和最小z值的z增量的宏。

然后，我們計算比例，注意不要被零除。

WORDZMin=20;

#defineINIT_ZDELTASdold=V2.z-V1.z;dnew=ZMin-V1.z;

#defineINIT_ZCLIPINIT_ZDELTASif(dold)m=dnew/dold;

我們建立一個函數(shù)，它主要剪貼多邊形指針的參數(shù)（它將記下作為結(jié)果的剪貼的頂點），第一個頂點（我們剪貼的邊的開始）和第二個頂點（最后）：

voidCLIP_Front(CPolygon_t*Polygon,_3DV1,_3DV2)

{

floatdold,dnew,m=1;

INIT_ZCLIP

現(xiàn)在我們必須檢測邊緣是否完全地在視口里，離開或進入視口。如果邊緣沒有完全地

在視口里，我們計算視口與邊緣的交線，用m值表示，用INIT_ZCLIP計算。

如果邊緣在視口里：

if((V1.z>=ZMin)&&(V2.z>=ZMin))

Polygon->Vertex[Polygon->Count++]=V2;

如果邊緣正離開視口：

if((V1.z>=ZMin)&&(V2.z<ZMin))

{

Polygon->Vertex[Polygon->Count].x=V1.x+(V2.x-V1.x)*m;

Polygon->Vertex[Polygon->Count].y=V1.y+(V2.y-V1.y)*m;

Polygon->Vertex[Polygon->Count++].z=ZMin;

}

如果邊緣正進入視口：

if((V1.z<ZMin)&&(V2.z>=ZMin))

{

Polygon->Vertex[Polygon->Count].x=V1.x+(V2.x-V1.x)*m;

Polygon->Vertex[Polygon->Count].y=V1.y+(V2.y-V1.y)*m;

Polygon->Vertex[Polygon->Count++].z=ZMin;

Polygon->Vertex[Polygon->Count++]=V2;

}

這就是邊緣Z-剪貼函數(shù)

}

現(xiàn)在我們可以寫下完整的多邊形Z-剪貼程序。為了有代表性，定義一個宏用來

在一個對象結(jié)構(gòu)中尋找適當(dāng)?shù)亩噙呅雾旤c。

#defineVert(x)Object->Vertex[Polygon->Vertex[x]]

下面是它的函數(shù)：

voidCLIP_Z(Polygon_t*Polygon,Object_t*Object,CPolygon_t*ZClipped)

{

intd,v;

ZClipped->Count=0;

for(v=0;v<Polygon->Count;v++)

{

d=v+1;

if(d==Polygon->Count)d=0;

CLIP_Front(ZClipped,Vert(v).Aligned,Vert(d).Aligned);

}

}

這個函數(shù)相當(dāng)簡單：它僅僅調(diào)用FrontClip函數(shù)來做頂點交換。

剪貼屏幕

剪貼屏幕的邊緣同Z-剪貼相同，但是我們有四個邊緣而不是一個。所以我們需要四個

不同的函數(shù)。但是它們需要同樣的增量初始化：

#defineINIT_DELTASdx=V2.x-V1.x;dy=V2.y-V1.y;

#defineINIT_CLIPINIT_DELTASif(dx)m=dy/dx;

邊緣是：

_2DTopLeft,DownRight;

為了進一步簡化_2D和_3D結(jié)構(gòu)的使用，我們定義兩個有用的函數(shù)：

_2DP2D(shortx,shorty)

{

_2DTemp;

Temp.x=x;

Temp.y=y;

returnTemp;

}

_3DP3D(floatx,floaty,floatz)

{

_3DTemp;

Temp.x=x;

Temp.y=y;

Temp.z=z;

returnTemp;

}

然后使用這兩個函數(shù)來指定視口：

TopLeft=P2D(0,0);

DownRight=P2D(319,199);

下面是四個邊緣剪貼函數(shù)：

/*

=======================

剪貼左邊緣

=======================

*/

voidCLIP_Left(Polygon2D_t*Polygon,_2DV1,_2DV2)

{

floatdx,dy,m=1;

INIT_CLIP

//************OK************

if((V1.x>=TopLeft.x)&&(V2.x>=TopLeft.x))

Polygon->Points[Polygon->PointsCount++]=V2;

//*********LEAVING**********

if((V1.x>=TopLeft.x)&&(V2.x<TopLeft.x))

{

Polygon->Points[Polygon->PointsCount].x=TopLeft.x;

Polygon->Points[Polygon->PointsCount++].y=V1.y+m*(TopLeft.x-V1.x);

}

//********ENTERING*********

if((V1.x<TopLeft.x)&&(V2.x>=TopLeft.x))

{

Polygon->Points[Polygon->PointsCount].x=TopLeft.x;

Polygon->Points[Polygon->PointsCount++].y=V1.y+m*(TopLeft.x-V1.x);

Polygon->Points[Polygon->PointsCount++]=V2;

}

}

/*

=======================

剪貼右邊緣

=======================

*/

voidCLIP_Right(Polygon2D_t*Polygon,_2DV1,_2DV2)

{

floatdx,dy,m=1;

INIT_CLIP

//************OK************

if((V1.x<=DownRight.x)&&(V2.x<=DownRight.x))

Polygon->Points[Polygon->PointsCount++]=V2;

//*********LEAVING**********

if((V1.x<=DownRight.x)&&(V2.x>DownRight.x))

{

Polygon->Points[Polygon->PointsCount].x=DownRight.x;

Polygon->Points[Polygon->PointsCount++].y=V1.y+m*(DownRight.x-V1.x);

}

//********ENTERING*********

if((V1.x>DownRight.x)&&(V2.x<=DownRight.x))

{

Polygon->Points[Polygon->PointsCount].x=DownRight.x;

Polygon->Points[Polygon->PointsCount++].y=V1.y+m*(DownRight.x-V1.x);

Polygon->Points[Polygon->PointsCount++]=V2;

}

}

/*

=======================

剪貼上邊緣

=======================

*/

voidCLIP_Top(Polygon2D_t*Polygon,_2DV1,_2DV2)

{

floatdx,dy,m=1;

INIT_CLIP

//************OK************

if((V1.y>=TopLeft.y)&&(V2.y>=TopLeft.y))

Polygon->Points[Polygon->PointsCount++]=V2;

//*********LEAVING**********

if((V1.y>=TopLeft.y)&&(V2.y<TopLeft.y))

{

if(dx)

Polygon->Points[Polygon->PointsCount].x=V1.x+(TopLeft.y-V1.y)/m;

else

Polygon->Points[Polygon->PointsCount].x=V1.x;

Polygon->Points[Polygon->PointsCount++].y=TopLeft.y;

}

//********ENTERING*********

if((V1.y<TopLeft.y)&&(V2.y>=TopLeft.y))

{

if(dx)

Polygon->Points[Polygon->PointsCount].x=V1.x+(TopLeft.y-V1.y)/m;

else

Polygon->Points[Polygon->PointsCount].x=V1.x;

Polygon->Points[Polygon->PointsCount++].y=TopLeft.y;

Polygon->Points[Polygon->PointsCount++]=V2;

}

}

/*

=======================

剪貼下邊緣

=======================

*/

voidCLIP_Bottom(Polygon2D_t*Polygon,_2DV1,_2DV2)

{

floatdx,dy,m=1;

INIT_CLIP

//************OK************

if((V1.y<=DownRight.y)&&(V2.y<=DownRight.y))

Polygon->Points[Polygon->PointsCount++]=V2;

//*********LEAVING**********

if((V1.y<=DownRight.y)&&(V2.y>DownRight.y))

{

if(dx)

Polygon->Points[Polygon->PointsCount].x=V1.x+(DownRight.y-V1.y)/m;

else

Polygon->Points[Polygon->PointsCount].x=V1.x;

Polygon->Points[Polygon->PointsCount++].y=DownRight.y;

}

//********ENTERING*********

if((V1.y>DownRight.y)&&(V2.y<=DownRight.y))

{

if(dx)

Polygon->Points[Polygon->PointsCount].x=V1.x+(DownRight.y-V1.y)/m;

else

Polygon->Points[Polygon->PointsCount].x=V1.x;

Polygon->Points[Polygon->PointsCount++].y=DownRight.y;

Polygon->Points[Polygon->PointsCount++]=V2;

}

}

為了得到完整的多邊形剪貼函數(shù)，我們需要定義一個附加的全局變量：

polygon2D_tTmpPoly;

voidCLIP_Polygon(Polygon2D_t*Polygon,Polygon2D_t*Clipped)

{

intv,d;

Clipped->PointsCount=0;

TmpPoly.PointsCount=0;

for(v=0;v<Polygon->PointsCount;v++)

{

d=v+1;

if(d==Polygon->PointsCount)d=0;

CLIP_Left(&TmpPoly,Polygon->Points[v],Polygon->Points[d]);

}

for(v=0;v<TmpPoly.PointsCount;v++)

{

d=v+1;

if(d==TmpPoly.PointsCount)d=0;

CLIP_Right(Clipped,TmpPoly.Points[v],TmpPoly.Points[d]);

}

TmpPoly.PointsCount=0;

for(v=0;v<Clipped->PointsCount;v++)

{

d=v+1;

if(d==Clipped->PointsCount)d=0;

CLIP_Top(&TmpPoly,Clipped->Points[v],Clipped->Points[d]);

}

Clipped->PointsCount=0;

for(v=0;v<TmpPoly.PointsCount;v++)

{

d=v+1;

if(d==TmpPoly.PointsCount)d=0;

CLIP_Bottom(Clipped,TmpPoly.Points[v],TmpPoly.Points[d]);

}

}

程序原理同Z-剪貼一樣，所以我們可以輕松地領(lǐng)會它。

隱面消除

Dilemna

底面消除

Z-緩沖

TheDilemna

三維引擎的核心是它的HSR系統(tǒng)，所以我們必須考慮選擇那一種。一般來說，最流行

的幾種算法是：

畫筆算法

需要的時間增長更快

難以實現(xiàn)（尤其重疊測試）

不能準(zhǔn)確地排序復(fù)雜的場景

字節(jié)空間分區(qū)樹

特別快

難以實現(xiàn)

僅僅能排序靜態(tài)多邊形

需要存儲樹

Z-緩存

需要的時間隨多邊形的數(shù)目線性地增加

在多邊形大于5000后速度比畫筆算法快

能夠完美地渲染任何場景，即使邏輯上不正確

非常容易實現(xiàn)

簡單

需要大量的內(nèi)存

很慢

所以我們的選擇是Z-緩存。當(dāng)然也可以選擇其他算法。

底面消除

除了這些方法，我們可以很容易地消除多邊形的背面來節(jié)省大量的計算時間。首先

我們定義一些有用的函數(shù)來計算平面和法向量以及填充。然后，我們給這個函數(shù)增加

紋理和陰影計算。這些變量為全局變量：

floatA,B,C,D;

BOOLbackface;

下面是我們的引擎函數(shù)，每一個坐標(biāo)都是浮點變量：

voidENG3D_SetPlane(Polygon_t*Polygon,Object_t*Object)

{

floatx1=Vert(0).Aligned.x;

floatx2=Vert(1).Aligned.x;

floatx3=Vert(2).Aligned.x;

floaty1=Vert(0).Aligned.y;

floaty2=Vert(1).Aligned.y;

floaty3=Vert(2).Aligned.y;

floatz1=Vert(0).Aligned.z;

floatz2=Vert(1).Aligned.z;

floatz3=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);

再檢查是否它面朝我們或背朝：

backface=D<0;

}

Z-緩存

Z-緩存是把顯示在屏幕上的每一個點的z坐標(biāo)保持在一個巨大的數(shù)組中，并且當(dāng)我們

我們檢查是否它靠近觀察者或是否在觀察者后面。我們僅僅在第一種情況下繪制它。所以我們不得不計算每一個點的z值。但是首先，我們定義全局樹組和為他分配空間。

（內(nèi)存等于追至方向與水平方向的乘積）：

typedeflongZBUFTYPE;

ZBUFTYPE*zbuffer;

zbuffer=(ZBUFTYPE*)malloc(sizeof(ZBUFTYPE)*MEMORYSIZE);

我們使用長整形作為z-緩存類型，因為我們要使用定點數(shù)。我們必須記住設(shè)置每一個z坐標(biāo)來盡可能得到更快的速度：

intc;

for(c=0;c<MEMORYSIZE;c++)

zbuffer[c]=-32767;

下面是數(shù)學(xué)公式。如何才能發(fā)現(xiàn)z坐標(biāo)？我們僅僅已經(jīng)定義的頂點，而不是多邊形的

每一個點。實際上，我們所需要做的是投影的反變換，投影公式是：

u=f?x/z

和

v=f?y/z

其中u是屏幕上x的坐標(biāo)，最小值為XOrigin，v是屏幕上的y的坐標(biāo)，最小值YOrigin。

平面公式是：

Ax+By+Cz+D=0

一旦我們已經(jīng)得到分離的x和y，有：

x=uz/f

和

y=vz/f

如果我們在平面等式中替代變量，公式變?yōu)椋?/p>

A(uz/f)+B(vz/f)+Cz=-D

我們可以提取z分量：

z(A(u/f)+B(v/f)+C)=-D

所以我們得到z：

z=-D/(A(u/f)+B(v/f)+C)

但是由于對于每一個像素我們需要執(zhí)行以上的除法，而計算1/z將提高程序的速度：

1/z=-(A(u/f)+B(v/f)+C)/D

1/z=-(A/(fD))u-(B/(fD))v-C/D

所以在一次像素程序運行的開始：

1/z=-(A/(fD))u1-(B/(fD))v-C/D

對于每一個像素，增量為：

-(A/(fD))>

下面是程序：

#defineFIXMUL(1<<20)

intoffset=y*MODEINFO.XResolution+x1;

inti=x1-Origin.x,j=y-Origin.y;

floatz_,dz_;

ZBUFTYPEz,dz;

//初始化1/z值(z:1/z)

dz_=((A/(float)Focal_Distance)/-D);

z_=((dz_*i)+((B*j/(float)Focal_Distance)+C)/-D);

dz=dz_*FIXMUL;

z=z_*FIXMUL;

然后，對于每一個像素，我們簡單的計算：

if(z>ZBuffer[offset])

{

zbuffer[offset]=z;

SCREENBUFFER[offset]=color;

}

z+=dz;

3D紋理映射

概述

魔幻數(shù)字

紋理映射的透視修正

概述

在做紋理映射時首先考慮的是建立紋理數(shù)組和初始化3D紋理坐標(biāo)。紋理將存儲在：

#defineMAXTEXTURES16

bitmap_tTextures[MAXTEXTURES];

我們從PCX文件分配和加載紋理。這里假設(shè)紋理大小為64x64。我們使用polygon_t

結(jié)構(gòu)的紋理坐標(biāo)：

vertex_tP,M,N;

我們在函數(shù)中初始化紋理，該函數(shù)在建立多邊形后被調(diào)用。P是紋理的原點，M是

紋理的水平線末端，N是垂直線的末端。

voidTEX_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);

}

我們需要象任何其他對象的頂點一樣變換紋理坐標(biāo)，所以我們需要建立世界變換和

一個對齊變換函數(shù)：

voidTR_Object(Object_t*Object,floatmatrix[4][4])

{

intv,p;

for(v=0;v<Object->VertexCount;v++)

VEC_MultMatrix(&Object->Vertex[v].Local,matrix,&Object->Vertex[v].World);

for(p=0;p<Object->PolygonCount;p++)

{

VEC_MultMatrix(&Object->Polygon[p].P.Local,matrix,&Object->Polygon[p].P.World);

VEC_MultMatrix(&Object->Polygon[p].M.Local,matrix,&Object->Polygon[p].M.World);

VEC_MultMatrix(&Object->Polygon[p].N.Local,matrix,&Object->Polygon[p].N.World);

}

}

voidTR_AlignObject(Object_t*Object,floatmatrix[4][4])

{

intv,p;

for(v=0;v<Object->VertexCount;v++)

VEC_MultMatrix(&Object->Vertex[v].World,matrix,&Object->Vertex[v].Aligned);

for(p=0;p<Object->PolygonCount;p++)

{

VEC_MultMatrix(&Object->Polygon[p].P.World,matrix,&Object->Polygon[p].P.Aligned);

VEC_MultMatrix(&Object->Polygon[p].M.World,matrix,&Object->Polygon[p].M.Aligned);

VEC_MultMatrix(&Object->Polygon[p].N.World,matrix,&Object->Polygon[p].N.Aligned);

}

}

魔幻數(shù)

既然我們已經(jīng)得到了變幻的紋理坐標(biāo)，我們的目標(biāo)是發(fā)現(xiàn)在紋理位圖上的像素

水平和垂直的坐標(biāo)在屏幕上如何繪制。紋理坐標(biāo)稱為u和v。下面的公式給出坐標(biāo)：

u=a*TEXTURE_SIZE/c

和

v=b*TEXTURE_SIZE/c

a，b，c滿足下面的等式：

a=Ox+Vxj+Hxi

b=Oy+Vyj+Hyi

c=Oz+Vzj+Hzi

其中O,H,V數(shù)是魔幻數(shù)。它根據(jù)下面的公式由紋理坐標(biāo)計算得到：

Ox=NxPy-NyPx

Hx=NyPz-NzPy

Vx=NzPx-NxPz

Oy=MxPy-MyPx

Hy=MyPz-MzPy

Vy=MzPx-MxPz

Oz=MyNx-MxNy

Hz=MzNy-MyNz

Vz=MxNz-MzNx

這里，我們不解釋魔幻數(shù)的原因。它看起來像奇怪的叉積。

紋理映射透視修正

O,H,V數(shù)的計算需要一些修正，所以我們增加下面到ENG3D_SetPlane:

//用于修正當(dāng)數(shù)字變得太大時候的錯誤

#defineFIX_FACTOR1/640

//初始化紋理矢量

P=Polygon->P.Aligned;

M=VEC_Difference(Polygon->M.Aligned,Polygon->P.Aligned);

N=VEC_Difference(Polygon->N.Aligned,Polygon->P.Aligned);

P.x*=Focal_Distance;

P.y*=Focal_Distance;

M.x*=Focal_Distance;

M.y*=Focal_Distance;

N.x*=Focal_Distance;

N.y*=Focal_Distance;

下面是VEC_Difference的實現(xiàn)：

_3DVEC_Differen