3d算法:3D图象算法

on 2009-2-12 in 游戏开发 | 0 Comment


3D介绍
　　 我们首先从坐标系统开始你也许知道在2D里我们经常使用Ren?笛卡儿坐标系统在平面上来识别点我们使用 2维(X,Y):X表示水平轴坐标,Y表示纵轴坐标在3维坐标系我们增加了Z般用它来表示深度所以为表示 3维坐标系个点我们用 3个参数(X,Y,Z)这里有区别笛卡儿 3维系统可以使用但是它们都是左手螺旋或右手螺旋右手螺旋是右手手指卷曲方向指向Z轴正方向而大拇指指向X轴正方向左手螺旋是左手手指卷曲方向指向Z轴负方向实际上我们可以在任何方向上旋转这些坐标系而且它们仍然保持本身特性在计算机图形学常用坐标系为左手坐标系所以我们也使用它:

X 正轴朝右
Y 正轴向上
Z 正轴指向屏幕里

矢量
什么是矢量？几句话它是坐标集合首先我们从 2维矢量开始(X,Y):例如矢量P(4,5)(般我们用->表示矢量)我们认为矢量P代表点(4,5)它是从原点指向(4,5)有方向和长度箭头我们谈论矢量长度指从原点到该点距离 2维距离计算公式是
| P | = sqrt( x^2 + y^2 )
这里有个有趣事实:在1D(点在单坐标轴上)平方根为它绝对值让我们讨论 3维矢量:例如P(4, -5, 9)它长度为
| P | = sqrt( x^2 + y^2 + z^2 )
它代表在笛卡儿3D空间个点或从原点到该点个箭头代表该矢量在有关操作节里我们讨论更多知识

矩阵
开始我们从简单开始:我们使用 2维矩阵4乘4矩阵为什么是4乘4？我们在 3维坐标系里而且我们需要附加行和列来完成计算工作在 2维坐标系我们需要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 |

有关矢量和矩阵操作
我们已经介绍了些非常简单基本概念那么上面知识和 3维图形有什么关系呢？
本节我们介绍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变换有关重要矩阵操作原理两个矩阵相乘而且M x N <> N x M例如:
A 4x4矩阵相乘公式
如果 A=(aij)4x4 B=(bij)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 = S>4, j=1 aijbjk
( a1, a2, a3 ) x B =
(Sum(aibi1) + b4,1, Sum(aibi2) + b4,2, Sum(aibi3) + b4,3 )

现在,我们可以试着把些矩阵乘以单位阵来了解矩阵相乘性质我们把矩阵和矢量相乘结合在起下面有个公式把3D矢量乘以个4x4矩阵(得到另外个 3维矢量)如果B=(bij)4x4那么:
( a1, a2, a3 ) x B = (S>aibi1 + b4,1, S>aibi2 + b4,2, S>aibi3 + b4,3 )>

这就是矢量和矩阵操作公式从这里开始代码和数学的间联系开始清晰

变换
我们已经见过象这样公式:
t( tx, ty ): ( x, y ) > ( x + tx, y + ty )

这是在 2维笛卡儿坐标系平移等式下面是缩放公式:

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

旋转等式:
r( q ): ( x, y ) > ( x cos(q) - y sin(q), x sin(q) + y cos(q) )
以上都是 2维公式在 3维里公式形式仍然很相近
平移公式:
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 )
所以我们可以写出像在 2维中同样变换公式我们通过乘以变换矩阵而得到新矢量新矢量将指向变换点下面是所有 3维变换矩阵:

平移(tx, ty, tz)矩阵

| 1 0 0 0 |
| 0 1 0 0 |
| 0 0 1 0 |
| tx ty tz 1 |


缩放(sx, sy, sz)矩阵
| sz 0 0 0 |
| 0 sy 0 0 |
| 0 0 sx 0 |
| 0 0 0 1 |


绕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 |

所以我们已经可以结束有关变换部分.通过这些矩阵我们可以对 3维点进行任何变换.

平面和法向量
平面是平坦无限指向特定方向表面可以定义平面如下:
Ax + By + Cz + D = 0



其中 A, B, C称为平面法向量D是平面到原点距离我们可以通过计算平面上两个矢量叉积得到平面法向量为得到这两个矢量我们需要 3个点P1P2P3逆时针排列可以得到:
矢量1 = P1 - P2

和

矢量2 = P3 - P2


计算法向量为:
法向量 = 矢量1 X 矢量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 )

3维变换
存储坐标
实现矩阵系统
实现 3角法系统
创建变换矩阵
如何创建透视
变换对象

存储坐标
首先可以编写星空模拟代码那么我们基本结构是什么样？每个对象描述是如何存储？为解决这个问题首先我们研究另个问题:我们需要是什么样坐标系？最明显答案是:
屏幕坐标系:相对于显示器原点2D坐标系
本地坐标系:相对于对象原点3D坐标系
但是我们不要忘记变换中间用到坐标系例如:
世界坐标系:相对于3D世界原点 3维坐标系
对齐(视点)坐标系:世界坐标系变换观察者位置在世界坐标系原点

下面是坐标基本结构:

// 2维坐标
typedef struct
{
x, y;
}_2D;

// 3维坐标
typedef struct
{
float x, y, z;
}_3D;

这里,我们定义了称为顶点坐标结构“顶点”词指两个或两个以上菱形边
交点我们顶点可以简单地认为是描述区别系统矢量

//区别坐标系坐标
typedef struct
{
_3D Local;
_3D World;
_3D Aligned;
}Vertex_t;

实现矩阵系统
我们需要存储我们矩阵在4x4浮点数矩阵中所以当我们需要做变换是我们定义如下矩阵:
float matrix[4][4];
然后我们定义些来拷贝临时矩阵到全局矩阵:

void MAT_Copy(float source[4][4], float dest[4][4])
{
i,j;
for(i=0; i<4; i)
for(j=0; j<4; j)
dest[i][j]=source[i][j];
}

很简单！现在我们来写两个矩阵相乘同时可以理解上面些有关矩阵相乘公式代码如下:

void MAT_Mult(float mat1[4][4], float mat2[4][4], float dest[4][4])
{
i,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----相乘后新矩阵

现在你明白了吗？现在我们设计矢量和矩阵相乘公式
void VEC_MultMatrix(_3D *Source,float mat[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矩阵

实现 3角法系统
几乎每个C编译器都带有有 3角数学库但是我们需要简单 3角时不是每次都使用它们正弦和余弦计算是阶乘和除法大量运算为提高计算速度我们建立自己 3角表首先决定你需要角度个数然后在这些地方用下面值代替:
float SinTable[256], CosTable[256];
然后使用宏定义它会把每个角度变成正值并对于大于360度角度进行周期变换然后返回需要值如果需要角度数是2幂次那么我们可以使用\"&\"代替\"%\"它使运行更快例如256所以在中尽量选取2幂次

3角法系统:
# SIN(x) SinTable[ABS(()x&255)]
# COS(x) CosTable[ABS(()x&255)]

旦我们已经定义了需要东西建立化并且在中宏

void M3D_Init
{
d;
for(d=0; d<256; d)
{
SinTable[d]=sin(d*PI/128.0);
CosTable[d]=cos(d*PI/128.0);
}
}

建立变换矩阵
下面使用C编写变换矩阵代码

float mat1[4][4], mat2[4][4];

void MAT_Identity(float mat[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;
}
//定义单位阵

void TR_Translate(float matrix[4][4],float tx,float ty,float tz)
{
float tmat[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------平移参数
//matrix--------源矩阵和目标矩阵
//矩阵平移

void TR_Scale(float matrix[4][4],float sx,float sy, float sz)
{
float smat[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);
}


//矩阵缩放

void TR_Rotate(float matrix[4][4], ax, ay, az)
{
float xmat[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轴旋转角度
//ay------绕Y轴旋转角度
//az------绕Z轴旋转角度
//矩阵旋转

如何建立透视
如何建立对象立体视觉,即显示器上些事物看起来离我们很近,而另外些事物离我们很远透视问题直是困绕我们个问题有许多思路方法被使用我们使用3D世界到2D屏幕投影公式:
P( f ):(x, y, z)>( f*x / z + XOrigin, f*y / z + YOrigin )

其中f是“焦点距离”它表示从观察者到屏幕距离般在80到200厘米的间XOrigin和YOrigin是屏幕中心坐标(x,y,z)在对齐坐标系上那么投影应该是什么样？

# FOCAL_DISTANCE 200
//定义焦点距离
void Project(vertex_t * Vertex)
{
(!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;
}
//得到屏幕上投影坐标
0不能做除数所以对z进行判断


变换对象
既然我们已经掌握了所有变换顶点工具就应该了解需要执行主要步骤
、化每个顶点本地坐标
2、设置全局矩阵为单位阵
3、根据对象尺寸缩放全局矩阵
4、根据对象角度来旋转全局矩阵
5、根据对象位置移动全局矩阵
6、把本地坐标乘以全局矩阵来得到世界坐标系
7、设置全局矩阵为单位阵
8、用观测者位置负值平移全局矩阵
9、用观测者角度负值旋转全局矩阵
十、把世界坐标系和全局矩阵相乘得到对齐坐标系
十、投影对齐坐标系来得到屏幕坐标
即:本地坐标系-->世界坐标系-->对齐坐标系-->屏幕坐标系


多边形填充
多边形结构
发现 3角形
绘制 3角形

多边形结构
我们如何存储我们多边形？首先我们必须知道再这种状态下多边形是 2维多边形而且由于多边形是 3维我们仅需要个临时 2维多边形所以我们能够设置 2维顶点最大数为个常量而没有浪费内存:

2D结构:
typedef struct
{
_2D Pos[20];
PosCount;
Texture;
}Polygon2D_t;

3D 结构:
typedef struct
{
Count;
* Vertex;
Texture;

Vertex_t P,M,N;
}Polygon_t;

为什么顶点包含整数值呢?仔细研究下,例如在立方体内, 3个多边形公用同个
顶点,所以在 3个多边形里存储和变换同个顶点会浪费内存和时间我们更愿意存储
它们在个对象结构里而且在多边形结构里我们会放置相应顶点索引请看
下面结构:
typedef struct
{
VertexCount;
PolygonCount;
Vertex_t * Vertex;
Polygon_t * Polygon;
_3D Scaling;
_3D Position;
_3D Angle;
NeedUpdate;
}Object_t;

发现 3角形
绘制个 3角形比绘制任意多边形要简单所以我们从把多边形分割成
3顶点形状这种思路方法非常简单和直接:
void POLY_Draw(Polygon2D_t *Polygon)
{
_2D P1,P2,P3;
i;

P1 = Polygon->Pos[0];
for(i=1; i < Polygon->PosCount-1; i)
{
P2=Polygon->Pos[i];
P3=Polygon->Pos[i+1];
POLY_Triangle(P1,P2,P3,Polygon->Texture);
}
}
//上面算法对于凹多边形就不太适用
_____
|\\ |
| \\ |
|____\\|

绘制 3角形
现在怎样得到 3角形?我们怎样才能画出每条有关直线,并且如何发现
每行起始和结实x坐标我们通过定义两个简单有用宏定义开始来区别
垂直地两个点和两个数:

# MIN(a,b) ((a<b)?(a):(b))
# MAX(a,b) ((a>b)?(a):(b))
# MaxPo(a,b) ((a.y > b.y) ? a : b)
# MinPo(a,b) ((b.y > a.y) ? a : b)

然后我们定义 3个宏来区别 3个点:

# MaxPo3(a,b,c) MaxPo(MaxPo(a,b),MaxPo(b,c))
# MidPo3(a,b,c) MaxPo(MinPo(a,b),MinPo(a,c))
# MinPo3(a,b,c) MinPo(MinPo(a,b),MinPo(b,c))

你也许注意到MidPo3宏不总是正常地工作取决于 3个点排列顺序
例如,a<b & a<c 那么由MidPo3得到是a,但它不是中间点
我们用语句来修正这个缺点下面为代码:

void POLY_Triangle(_2D p1,_2D p2,_2D p3,char c)
{
_2D p1d,p2d,p3d;
xd1,yd1,xd2,yd2,i;
Lx,Rx;

首先我们把 3个点进行排序:
p1d = MinPo3(p1,p2,p3);
p2d = MidPo3(p2,p3,p1);
p3d = MaxPo3(p3,p1,p2);

当这些宏时候为什么会有点顺序改变？(作者也不清楚)可能这些点被逆时针传递试图改变这些宏你屏幕显示是垃圾！现在我们并不确定中间点所以我们做些检查
而且在这种状态下得到中间点有似乎是所以我们修正:



(p2.y < p1.y)
{
p1d=MinPo3(p2,p1,p3);
p2d=MidPo3(p1,p3,p2);
}
这些点排列顺序看起来很奇怪但是试图改变他们那么所有东西就乱套了只有理解或
接受这些结论现在我们计算增量

xd1=p2d.x-p1d.x;
yd1=p2d.y-p1d.y;
xd2=p3d.x-p1d.x;
yd2=p3d.y-p1d.y;

OK第步已经完成如果有增量 y:
(yd1)
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;
如果不在同个点绘制线段按次序传递这两个点:

(Lx!=Rx)
VID_HLine(MIN(Lx,Rx),MAX(Lx,Rx),i,c);
}
现在我们重新计算第个增量而且计算第 2条边
xd1=p3d.x-p2d.x;
yd1=p3d.y-p2d.y;

(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;
(Lx!=Rx)
VID_HLine(MIN(Lx,Rx),MAX(Lx,Rx),i,c);
}
}

以上我们已经得到多边形填充公式对于平面填充更加简单:
void VID_HLine( x1, x2, y, char c)
{
x;
for(x=x1; x<=x2; x)
putpixel(x, y, c);
}

Sutherland-Hodgman剪贴
概述
Z-剪贴
屏幕剪贴

概述
般地我们更愿意剪贴我们多边形必须靠着屏幕边缘剪贴但也必须在观察前方(我们不需要绘制观察者后面事物当z左边非常小时)当我们剪贴个多边形并不考虑是否每个点在限制以内而我们更愿意增加必须顶点所以我们需要个第 3个多边形结构:
typedef struct
{
Count;
_3D Vertex[20];
}CPolygon_t;

由于我们有附加顶点来投影我们不再投影顶点而是投影剪贴3D多边形到
2D多边形
void M3D_Project(CPolygon_t *Polygon,Polygon2D_t *Clipped, focaldistance)
{
v;
for(v=0; v<Polygon->Count; v)
{
(!Polygon->Vertex[v].z)Polygon->Vertex[v].z;
Clipped->Pos[v].x=Polygon->Vertex[v].x*focaldistance/Polygon->Vertex[v].z+Origin.x;
Clipped->Pos[v].y=Polygon->Vertex[v].y*focaldistance/Polygon->Vertex[v].z+Origin.y;
}
Clipped->PosCount=Polygon->Count;
}

Z-剪贴
首先我们定义计算在第个点和第 2个点的间以及在第个点和最小z值z增量宏
然后我们计算比例注意不要被零除
WORD ZMin=20;
# INIT_ZDELTAS dold=V2.z-V1.z; d=ZMin-V1.z;
# INIT_ZCLIP INIT_ZDELTAS (dold) m=d/dold;

我们建立个它主要剪贴多边形指针参数(它将记下作为结果剪贴顶点)第个顶点(我们剪贴边开始)和第 2个顶点(最后):
void CLIP_Front(CPolygon_t *Polygon,_3D V1,_3D V2)
{
float dold,d, m=1;
INIT_ZCLIP

现在我们必须检测边缘是否完全地在视口里离开或进入视口如果边缘没有完全地
在视口里我们计算视口和边缘交线用m值表示用INIT_ZCLIP计算

如果边缘在视口里:
( (V1.z>=ZMin) && (V2.z>=ZMin) )
Polygon->Vertex[Polygon->Count]=V2;

如果边缘正离开视口:
( (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;
}

如果边缘正进入视口:
( (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-剪贴
}

现在我们可以写下完整多边形Z-剪贴为了有代表性定义个宏用来
在个对象结构中寻找适当多边形顶点
# Vert(x) Object->Vertex[Polygon->Vertex[x]]

下面是它:
void CLIP_Z(Polygon_t *Polygon,Object_t *Object,CPolygon_t *ZClipped)
{
d,v;
ZClipped->Count=0;
for (v=0; v<Polygon->Count; v)
{
d=v+1;
(dPolygon->Count)d=0;
CLIP_Front(ZClipped, Vert(v).Aligned,Vert(d).Aligned);
}
}

这个相当简单:它仅仅FrontClip来做顶点交换

剪贴屏幕
剪贴屏幕边缘同Z-剪贴相同但是我们有 4个边缘而不是个所以我们需要 4个
区别但是它们需要同样增量化:
# INIT_DELTAS dx=V2.x-V1.x; dy=V2.y-V1.y;
# INIT_CLIP INIT_DELTAS (dx)m=dy/dx;

边缘是:
_2D TopLeft, DownRight;

为了进步简化_2D和 _3D结构使用我们定义两个有用:
_2D P2D( x, y)
{
_2D Temp;
Temp.x=x;
Temp.y=y;
Temp;
}
_3D P3D(float x,float y,float z)
{
_3D Temp;
Temp.x=x;
Temp.y=y;
Temp.z=z;
Temp;
}

然后使用这两个来指定视口:
TopLeft=P2D(0, 0);
DownRight=P2D(319, 199);

下面是 4个边缘剪贴:
/*
=
剪贴左边缘
=
*/
void CLIP_Left(Polygon2D_t *Polygon,_2D V1,_2D V2)
{
float dx,dy, m=1;
INIT_CLIP

// ************OK************
( (V1.x>=TopLeft.x) && (V2.x>=TopLeft.x) )
Polygon->Pos[Polygon->PosCount]=V2;
// *********LEAVING**********
( (V1.x>=TopLeft.x) && (V2.x<TopLeft.x) )
{


Polygon->Pos[Polygon->PosCount].x=TopLeft.x;
Polygon->Pos[Polygon->PosCount].y=V1.y+m*(TopLeft.x-V1.x);
}
// ********ENTERING*********
( (V1.x<TopLeft.x) && (V2.x>=TopLeft.x) )
{
Polygon->Pos[Polygon->PosCount].x=TopLeft.x;
Polygon->Pos[Polygon->PosCount].y=V1.y+m*(TopLeft.x-V1.x);
Polygon->Pos[Polygon->PosCount]=V2;
}
}
/*
=
剪贴右边缘
=
*/

void CLIP_Right(Polygon2D_t *Polygon,_2D V1,_2D V2)
{
float dx,dy, m=1;
INIT_CLIP
// ************OK************
( (V1.x<=DownRight.x) && (V2.x<=DownRight.x) )
Polygon->Pos[Polygon->PosCount]=V2;
// *********LEAVING**********
( (V1.x<=DownRight.x) && (V2.x>DownRight.x) )
{
Polygon->Pos[Polygon->PosCount].x=DownRight.x;
Polygon->Pos[Polygon->PosCount].y=V1.y+m*(DownRight.x-V1.x);
}
// ********ENTERING*********
( (V1.x>DownRight.x) && (V2.x<=DownRight.x) )
{
Polygon->Pos[Polygon->PosCount].x=DownRight.x;
Polygon->Pos[Polygon->PosCount].y=V1.y+m*(DownRight.x-V1.x);
Polygon->Pos[Polygon->PosCount]=V2;
}
}
/*
=
剪贴上边缘
=
*/
void CLIP_Top(Polygon2D_t *Polygon,_2D V1,_2D V2)
{
float dx,dy, m=1;
INIT_CLIP
// ************OK************
( (V1.y>=TopLeft.y) && (V2.y>=TopLeft.y) )
Polygon->Pos[Polygon->PosCount]=V2;
// *********LEAVING**********
( (V1.y>=TopLeft.y) && (V2.y<TopLeft.y) )
{
(dx)
Polygon->Pos[Polygon->PosCount].x=V1.x+(TopLeft.y-V1.y)/m;

Polygon->Pos[Polygon->PosCount].x=V1.x;
Polygon->Pos[Polygon->PosCount].y=TopLeft.y;
}
// ********ENTERING*********
( (V1.y<TopLeft.y) && (V2.y>=TopLeft.y) )
{
(dx)
Polygon->Pos[Polygon->PosCount].x=V1.x+(TopLeft.y-V1.y)/m;

Polygon->Pos[Polygon->PosCount].x=V1.x;
Polygon->Pos[Polygon->PosCount].y=TopLeft.y;
Polygon->Pos[Polygon->PosCount]=V2;
}
}

/*
=
剪贴下边缘
=
*/

void CLIP_Bottom(Polygon2D_t *Polygon,_2D V1,_2D V2)
{
float dx,dy, m=1;
INIT_CLIP
// ************OK************
( (V1.y<=DownRight.y) && (V2.y<=DownRight.y) )
Polygon->Pos[Polygon->PosCount]=V2;
// *********LEAVING**********
( (V1.y<=DownRight.y) && (V2.y>DownRight.y) )
{
(dx)
Polygon->Pos[Polygon->PosCount].x=V1.x+(DownRight.y-V1.y)/m;

Polygon->Pos[Polygon->PosCount].x=V1.x;
Polygon->Pos[Polygon->PosCount].y=DownRight.y;
}
// ********ENTERING*********
( (V1.y>DownRight.y) && (V2.y<=DownRight.y) )
{
(dx)
Polygon->Pos[Polygon->PosCount].x=V1.x+(DownRight.y-V1.y)/m;

Polygon->Pos[Polygon->PosCount].x=V1.x;
Polygon->Pos[Polygon->PosCount].y=DownRight.y;
Polygon->Pos[Polygon->PosCount]=V2;
}
}

为了得到完整多边形剪贴我们需要定义个附加全局变量:
polygon2D_t TmpPoly;

void CLIP_Polygon(Polygon2D_t *Polygon,Polygon2D_t *Clipped)
{
v,d;

Clipped->PosCount=0;
TmpPoly.PosCount=0;

for (v=0; v<Polygon->PosCount; v)
{
d=v+1;
(dPolygon->PosCount)d=0;
CLIP_Left(&TmpPoly, Polygon->Pos[v],Polygon->Pos[d]);
}
for (v=0; v<TmpPoly.PosCount; v)
{
d=v+1;
(dTmpPoly.PosCount)d=0;
CLIP_Right(Clipped, TmpPoly.Pos[v],TmpPoly.Pos[d]);
}
TmpPoly.PosCount=0;
for (v=0; v<Clipped->PosCount; v)
{
d=v+1;
(dClipped->PosCount)d=0;
CLIP_Top(&TmpPoly, Clipped->Pos[v],Clipped->Pos[d]);
}
Clipped->PosCount=0;
for (v=0; v<TmpPoly.PosCount; v)
{
d=v+1;
(dTmpPoly.PosCount)d=0;
CLIP_Bottom(Clipped, TmpPoly.Pos[v],TmpPoly.Pos[d]);
}
}

原理同Z-剪贴样所以我们可以轻松地领会它


隐面消除
Dilemna
底面消除
Z-缓冲
The Dilemna
3维引擎核心是它HSR系统所以我们必须考虑选择那种般来说最流行
几种算法是:
画笔算法
需要时间增长更快
难以实现(尤其重叠测试)
不能准确地排序复杂场景
字节空间分区树
特别快
难以实现
仅仅能排序静态多边形
需要存储树
Z-缓存Cache
需要时间随多边形数目线性地增加
在多边形大于5000后速度比画笔算法快
能够完美地渲染任何场景即使逻辑上不正确
非常容易实现
简单
需要大量内存
很慢
所以我们选择是Z-缓存Cache当然也可以选择其他算法

底面消除
除了这些思路方法我们可以很容易地消除多边形背面来节省大量计算时间首先
我们定义些有用来计算平面和法向量以及填充然后我们给这个增加
纹理和阴影计算这些变量为全局变量:
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;
float x3=Vert(2).Aligned.x;
float y1=Vert(0).Aligned.y;
float y2=Vert(1).Aligned.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);

再检查是否它面朝我们或背朝:
backface=D<0;
}


Z-缓存Cache
Z-缓存Cache是把显示在屏幕上每个点z坐标保持在个巨大中并且当我们
我们检查是否它靠近观察者或是否在观察者后面我们仅仅在第种情况下绘制它所以我们不得不计算每个点z值但是首先我们定义全局树组和为他分配空间
(内存等于追至方向和水平方向乘积):
typedef long ZBUFTYPE;
ZBUFTYPE *zbuffer;
zbuffer=(ZBUFTYPE *)malloc((ZBUFTYPE)*MEMORYSIZE);
我们使用长整形作为z-缓存Cache类型我们要使用定点数我们必须记住设置每个z坐标来尽可能得到更快速度:
c;
for(c=0; c<MEMORYSIZE; c)
zbuffer[c]=-32767;

下面是数学公式如何才能发现z坐标？我们仅仅已经定义顶点而不是多边形
每个点实际上我们所需要做是投影反变换投影公式是:
u = f ?x / z

和

v = f ?y / z


其中u是屏幕上x坐标最小值为XOriginv是屏幕上y坐标最小值YOrigin
平面公式是:

Ax + By + Cz + D = 0

旦我们已经得到分离x和y有:
x = uz / f

和

y = vz / f


如果我们在平面等式中替代变量公式变为:

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)

但是由于对于每个像素我们需要执行以上除法而计算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))>


下面是:
# FIXMUL (1<<20)

off=y*MODEINFO.XResolution+x1;
i=x1-Origin.x, j=y-Origin.y;
float z_,dz_;
ZBUFTYPE z,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;

然后对于每个像素我们简单计算:
(z>ZBuffer[off])
{
zbuffer[off]=z;
SCREENBUFFER[off]=color;
}
zdz;


3D纹理映射
概述
魔幻数字
纹理映射透视修正

概述
在做纹理映射时首先考虑是建立纹理和化3D纹理坐标纹理将存储在:
# MAXTEXTURES 16
bitmap_t Textures[MAXTEXTURES];
我们从PCX文件分配和加载纹理这里假设纹理大小为64x64我们使用polygon_t
结构纹理坐标:
vertex_t P,M,N;

我们在中化纹理该在建立多边形后被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);
}

我们需要象任何其他对象顶点样变换纹理坐标所以我们需要建立世界变换和
个对齐变换:
void TR_Object(Object_t *Object, float matrix[4][4])
{
v,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);
}
}

void TR_AlignObject(Object_t *Object, float matrix[4][4])
{
v,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);
}
}

魔幻数

既然我们已经得到了变幻纹理坐标我们目标是发现在纹理位图上像素
水平和垂直坐标在屏幕上如何绘制纹理坐标称为u和v下面公式给出坐标:
u = a * TEXTURE_SIZE / c

和
v = b * TEXTURE_SIZE / c


abc满足下面等式:
a = Ox + Vx j + Hx i

b = Oy + Vy j + Hy i

c = Oz + Vz j + Hz i


其中O,H,V数是魔幻数它根据下面公式由纹理坐标计算得到:
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



这里我们不解释魔幻数原因它看起来像奇怪叉积


纹理映射透视修正
O,H,V数计算需要些修正所以我们增加下面到ENG3D_SetPlane:
//用于修正当数字变得太大时候
# FIX_FACTOR 1/640

//化纹理矢量
P=Polygon->P.Aligned;
M=VEC_Dference(Polygon->M.Aligned,Polygon->P.Aligned);
N=VEC_Dference(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_Dference实现:
_3D VEC_Dference(_3D Vector1, _3D Vector2)
{
P3D(Vector1.x-Vector2.x,Vector1.y-Vector2.y,Vector1.z-Vector2.z);
}

然后计算魔幻数
_3D O, H, V;
ENG3D_SetPlane:
H.x=(N.y*P.z-N.z*P.y)*FIX_FACTOR;
V.x=(N.z*P.x-N.x*P.z)*FIX_FACTOR;
O.x=(N.x*P.y-N.y*P.x)*FIX_FACTOR;

H.z=(M.z*N.y-M.y*N.z)*FIX_FACTOR;
V.z=(M.x*N.z-M.z*N.x)*FIX_FACTOR;
O.z=(M.y*N.x-M.x*N.y)*FIX_FACTOR;

H.y=(M.y*P.z-M.z*P.y)*FIX_FACTOR;
V.y=(M.z*P.x-M.x*P.z)*FIX_FACTOR;
O.y=(M.x*P.y-M.y*P.x)*FIX_FACTOR;
下面为TEX_HLine改变VID_HLine以便使用纹理映射(难以理解部分)首先我们
必须化魔幻数坐标:
a=-((long)O.x+((long)V.x*(long)j)+((long)H.x*(long)i))*64L;
b= ((long)O.y+((long)V.y*(long)j)+((long)H.y*(long)i))*64L;
c= ((long)O.z+((long)V.z*(long)j)+((long)H.z*(long)i));
long Hx,Hy,Hz;
u,v;
BYTE color=0;
BYTE *mapping=Textures[texture].Picture;
然后把H.x 和 H.y乘以64这样我们不需要为每个像素做计算我们用长整形数代替
浮点数:
Hx=H.x*-64;
Hy=H.y*64;
Hz=H.z;

对于每个像素改变最后个参数并且替代绘制原来参数:
(c)
{
u=a/c;
v=b/c;
color=mapping[((v&63)<<6)+(u&63)];
(color)
{
zbuffer[off]=z;
SCREENBUFFER[off]=LightTable[light][color];
}
}
aHx;
bHy;
cHz;

现在我们得到自己纹理映射！




3维明暗
计算法向量
计算叉乘
使用光线表

计算法向量
在3D数学教程里我们已经深入讨论了矢量和法向量这里我们给出些实现:
float VEC_DotProduct(_3D Vector1, _3D Vector2)
{
(Vector1.x*Vector2.x+Vector1.y*Vector2.y+Vector1.z*Vector2.z);
}

_3D VEC_CrossProduct(_3D Vector1, _3D Vector2)
{
P3D(Vector1.y*Vector2.z-Vector1.z*Vector2.y,Vector1.z*Vector2.x-Vector1.x*Vector2.z,Vector1.x*Vector2.y-Vector1.y*Vector2.x);
}
void VEC_Normalize(_3D * Vector)
{
float m=sqrt(Vector->x*Vector->x+Vector->y*Vector->y+Vector->z*Vector->z);
Vector->x/=m;
Vector->y/=m;
Vector->z/=m;
}

对于3D明暗需要向ENG3D_SetPlane增加:
//计算平面法向量
PlaneNormal=VEC_CrossProduct(P3D(x2-x1,y2-y1,z2-z1),P3D(x3-x1,y3-y1,z3-z1));
VEC_Normalize(&PlaneNormal);

计算叉积
正如在数学部分所说两个矢量间夹角等于他们点积(当他们归化后)
为发现到达平面光线我们简单地把环境光和归化光源世界坐标系叉积
和最大光强度乘积相加下面是代码:

全局变量定义:
WORD AmbientLight=20;
# MAXLIGHT 32
Vertex_t LightSource;
WORD light;

在SetPlane里:
//计算法向量和光源点积强度
light=MAXLIGHT*VEC_DotProduct(PlaneNormal,LightSource.World)+AmbientLight;
(light>MAXLIGHT)light=MAXLIGHT;
(light<1)light=1;


明显地我们需要化光源正如计算法向量顶点
//化光源
LightSource.Local=P3D(0,0,0);
MAT_Identity(matrix);
TR_Translate(matrix, 10,10,10);
TR_Rotate(matrix, 0,128-32,128);
VEC_MultMatrix(&LightSource.Local,matrix,&LightSource.World);
VEC_Normalize(&LightSource.World);

使用光线表

光线表是在基于调色板技术上使用光线强度种思路方法在每个强度上可以发现
最好颜色匹配Christopher Lampton在他幻想花园书中设计了大量光源表
发生器不幸是他使用是自己格式所以我们可以选择自己或他人光线表旦我们已经有了光线表旦我们有了广西表就可以在全局中加载它
BYTE LightTable[MAXLIGHT+1][256];
旦已经加载我们在TEX_HLine中改变如下:
screen[off]=LightTable[light][color];
我们得到了 3维明暗

Tags:  3d五行算法 3d图象 3d的算法 3d算法

延伸阅读

最新评论

发表评论