Loserwang保留版权，转载请注明出处：http://hi.baidu.com/loserwang
电子邮件:dreamcasttop   at163.com

《简化三维流水线和逼近真实流水线》

目的：通过简化流水线可以在相当短的实践周期内逼近真实流水线。
工具：VC7.1、DirextX、几何画板、MathType公式编辑器、科学计算器、3DS MAX 7.0、MilkShape 3D演示版等
周期：2007年8月23日至2007年8月28日
日期：2007年8月29日

图示：在实验中用到的真实流水线绘制的人物头部线框模型和简单渲染

本材料并不是一份入门参考，主要用于交流和提高，并且阐述一些比较值得关注的观点。

第一部分、基础设施
一、提出问题：怎样找到一种简单的工具来验证三维空间的真相
大概是1年多前，2005年11月的时候，因为对图像渲染的速度要求，放弃了当时正在使用的.Net设计平台而转入VC图形开发。对于二维图形来说，高中的代数和几何知识已经足够了，所以当时并没有多少障碍就能够成熟地驾驭二维世界。对于这种“不合时宜”的做法并没有持续很久，开始将目光投入三维图形世界。
这一去就是1年多，这个阶段并没有累积图形学方面的任何成功经验，甚至连基本的DirectX应用程序都没有写过。仅在Windows API、Standard C++、COM、WinSocket、MFC等程序设计方面有一定的积累。在实践中，依靠成功的程序设计能力并不总是很有效，我们总是被各种实际运算的问题所困扰。
进入三维世界，如果不是马上能够在实践中演练，那要实现它几乎不可想象，因为它包含的各种内容都有一定的抽象高度，比如说矩阵这种实用工具。矩阵真实的面目是什么？行列里的若干数字？没有应用它们是不可能体会到的：

图1、一个矩阵

困扰的一个直接问题是，三维图形的呈现有一个渲染流水线，没有经过这个流水线而直接表达出三维图形，比如说用约定的方式，有没有这样的一种可能？所有的三维图形学书籍都迫不及待地开始了他们的理论长征，最终再简要地给出流水线的构造步骤。或者换个角度讲，这些书籍并没有用一种简单的模型让我们马上在实践当中理解和应用大多数的理论基础。比如说，仅仅是要呈现三维空间中的一个线段，并且初学者对三维空间理论的匮乏也仅仅能提出类似的要求。不幸的是，这些书籍都把呈现放在了真实的三维渲染流水线的模型中。在接触到这个真实流水线之前，所有的呈现和实践任务看起来是做不到了。而不能理解和应用这些前提要素，构造一个真实流水线的机会便变得更加遥遥无期。典型的克服这种问题的做法有二：1、纯粹理论探讨，列出所有的数学公式并推导他们，这种方法被所有的大学教学系统所采纳，但学习者必须付出2年的时间和接受极可能出现的失败命运。2、在商业三维流水线系统内完成，如Direct3D和OpenGL，这种书籍充斥了广泛的市场并且打造了大量肤浅的劣质的玩具。

D3DXMATRIX Rx, Ry;
// 构建绕x轴旋转的矩阵，一个定值45度
D3DXMatrixRotationX(&Rx, 3.14f / 4.0f);
// 变化的绕y轴旋转的矩阵
static float y = 3.14f / 8.0f;
D3DXMatrixRotationY(&Ry, y);
y += timeDelta;
// 标准化弧度值
if( y >= 6.28f )
y = 0.0f;
// 组合矩阵
D3DXMATRIX p = Rx * Ry;
// 旋转了世界坐标而不是物体
Device->SetTransform(D3DTS_WORLD, &p);

如上在Direct3D中利用矩阵工具来表达三维物体的转换是非常清晰和简洁的。对于类似的任务，实验中用到的代码段：

static float angle=0;
angle+=1;
MATRIX m=MI; //对象变换矩阵
MATRIX o=MI; //流水线变换矩阵
//旋转运动y
m=m*rotationy(angle);
//旋转运动x
m=m*rotationx(-30);
…
m=m*o;
v0=v0*m;

这时候问题又来了，矩阵是什么？它们的乘法定义又该是如何的？能够使对象旋转的矩阵是怎样工作的？当学习者问起这些问题的时候，通常的答复就是对它们合理解释一遍，如此往复。但是要幸运地遇到这样的提问者和遇到回答者一样困难。在盲目的实践中追求理论的解答总是不够利索和片面。

二、迫不及待地要在三维空间呈现，怎么做？
实践证明，三角学、解析几何、立体几何、线性代数是有效的，它们是通往三维图形学真理方向的唯一路途。在朝空间几何和三维图形学的城堡迈进之前，我先详细地回顾了这些知识，大约是2007年3月到8月间，我所作的一切事情就是它们。当然还包含了数学分析的函数、极限、微积分初步等。以至到后来，我几乎认定整个高中数学课程就是为三维数学作准备的。比如选读部分的矩阵行列式。其实在数学描述方面，三维数学和工程、电子等学科有着密不可分的联系。它们几乎可以用同一套数学描述系统来解决各种实际问题。

图2、空间中的点A，表现为xy二维平面上的点A’在z维度上的位移

如上图所示，我们可以把z方向的位移特殊处理，比如说按和x轴一定的倾斜方向表示出来，这是我们在二维图形上直观表示z纵深的方式。其实，这就是我们的简化流水线的基本模型。公式如下：

公式1、简化模型

它们几乎就是简化流水线的全部生命。当然，为了使图形具备空间感，还需要为图形添置对应坐标系。
这是一个非常简单的流水线模型，但是它可以完成的任务比我们想象的要多更多。因为我们可以对三维空间中的点或向量做一系列操作，然后利用这个模型投射出结果，这样我们就可以了解这一系列操作达到的目的以及它们是否正确。

三、GDI或者DirectDraw，基础图形描述工具。
Windows API提供一系列实用函数用于绘制图形，GDI是抽象图形设备接口，负责直接和硬件打交道。

图3、从窗口图形设备创建兼容设备，并附加指定大小位图以便绘制图形

为了呈现动画效果，是不能直接在窗口的抽象设备作图的，这样会产生闪烁现象。因为计算机用户会看到GDI在窗口上绘图的全过程。这里用到了一个概念——内存兼容设备。它允许我们在内存中画好一桢图形，然后一次性写入到窗口中。

HDC hDC=GetDC(hWnd);
HDC hMemDC=CreateCompatibleDC(hDC);
HBITMAP hBmp=CreateCompatibleBitmap(hDC,800,600);
SelectBitmap(hMemDC,hBmp);
ReleaseDC(hWnd,hDC);

上面代码表示了兼容设备创建的过程。之后就可以相当于利用窗口设备的方式操作它，只是没有立即显示而已。

//以下函数用于带缩放地写入目标窗口设备
StretchBlt(
destHDC, //目标设备
destRC.left, //目标设备区域
destRC.top,
destRC.right,
destRC.bottom,
srcHDC, //内存设备
srcRC.left, //内存设备区域
srcRC.top,
srcRC.right,
srcRC.bottom,
SRCCOPY //传送模式);

DirectDraw用了类似的手段来完成图形呈现，但是它具备更佳的速度表现。但因为它的广泛和实用性，加入了大量的结构用于描述各种参数和进行对应参数或者行为的操作函数而造成一定的使用难度。究其原理是相当简单的。一份合适的DirectDraw程序样本足够帮我们节省很多的思考时间。我们只要能够创建两个表面，进行表面复制，构造一些画点画线乃至写文本函数就可以满足需求了。

//lpsurmain是主表面指针，lpsurback是副表面指针
lpsurmain->Blt(&rectmain,lpsurback,&rectback,DDBLT_WAIT,NULL);

//DirectDraw包含有GDI模拟接口，可以像操作GDI那样操作这个接口
int VDText(int x,int y,TCHAR* buf)
{
lpsurback->GetDC(&hMemDC);
SetBkMode(hMemDC,TRANSPARENT);
SetTextColor(hMemDC,0x00FF00);
TextOut(hMemDC,x,y,buf,(int)_tcslen(buf));
lpsurback->ReleaseDC(hMemDC);
return 0;
}

至此，我们找到了2个工具都可以帮我们完成创建绘图表面和绘制像素。

四、开始绘制经过正交投影的线框图形

图4、简化模型

上图是利用简化模型呈现的向量直观图，包含两个三维向量，以及它们的法线和一个向量到另一个向量的投影线，当然，还包括坐标轴。
原理正如公式所表述的。它的真实代码如下：

//以窗口中心为原点，memrc.right/(2*d)是通用的缩放因子，在真实的流水线中，输出的图形往往不是正常屏幕大小的，这跟相机设定的投影面z=d有关系。根据90度的视角来说，投影面大小的一半正等于
POINT V(VECTOR3 vector3)
{
POINT pt;
VECTOR3 v=vector3;
v.x=v.x/v.w;
v.y=v.y/v.w;
v.z=v.z/v.w;

pt.x=(long int)(memrc.right/2+(v.x+v.z*cos(AngToRad(x_z_angle)))*memrc.right/(2*d));
pt.y=(long int)(memrc.bottom/2-(v.y+v.z*sin(AngToRad(x_z_angle)))*memrc.right/(2*d));
return pt;
}

视口的大小是受D影响的，为了“还原”屏幕的真实尺寸，必须计算出屏幕尺寸跟当前D值的缩放比。

图5、利用相似三角形表现透视投影中投影面和d的关系

回到简化模型的讨论，计算出合适的x跟y值之后，就可以利用GDI或者DirectDraw的相关描点画线函数来表达。呈现的结果如图4所示。
接下来我们将引入一个更为有意义的图形线框模型。

typedef struct
{
float x;
float y;
float z;
float w;
}VECTOR3;

上面的结构表现一个三维向量或点。其中的w分量我们先不考虑，只要知道它为1。

//顶点列表
static VECTOR3 vertex[]=
{
{0,0,0,1},
{10,0,0,1},
{10,10,0,1},
{0,10,0,1},
{0,0,10,1},
{10,0,10,1},
{10,10,10,1},
{0,10,10,1},

{12,0,0,1},
{20,0,0,1},
{16,0,6,1},
{16,5,3,1}
};
//三角形列表
int triang[]={0,3,7,6,4,5,0,1,3,2,6,5,-1,8,10,9,11,8,10};

我们用顶点索引列表来表达三角形带，这里我用了一个小技巧，-1区隔不同的三角形带。当然可以对三角形带进行分组，甚至把它们切割为彼此独立的三角形组。使用什么策略就看实际情况。例如这边的顶点索引并不是很多。

定义了顶点，接下来就要定义它们的传输带了。

//对顶点进行枚举
for(int i=2;i<sizeof(triang)/sizeof(int);i++)
{
if(triang[i]==-1)
{
         i+=2;
         continue;
}
VMove(hMemDC,vertex[triang[i-2]]*m);
VLineTo(hMemDC,vertex[triang[i-1]]*m);
VLineTo(hMemDC,vertex[triang[i]]*m);
VLineTo(hMemDC,vertex[triang[i-2]]*m);
}

传输带和线框存放结构是有适应关系的。
VMove函数和VlineTo函数获取一个三维数据，通过简化模型将他们转化为合适的坐标之后调用GDI的MoveToEx和LineTo函数来执行对应操作。
结果如下（我在例程中对它们作了一定的旋转操作）：

图6、通过简化模型也能够表达复杂的物体

你会很快发现它并不具备透视特性，没错，这正是我们想要的。
五、点积公式的证明

图7、转移坐标，使U和x平行

 

六、矩阵——真实流水线的生命
假如世界上从来不曾存在过矩阵，我们的生活会是怎样？对矩阵的溢美之词可以写一本专著。但是我们现在不打算立即描述它在三维流水线所发挥的作用。立刻就可以开始把它用于变换物体的空间位置和形变等。

typedef struct
{
float _11;float _12;float _13;float _14;
float _21;float _22;float _23;float _24;
float _31;float _32;float _33;float _34;
float _41;float _42;float _43;float _44;
}MATRIX;

代码所示的是这样一个矩阵：

MATRIX rotationz(float angle)
{
MATRIX m;
initmatrix(m);
m._11=cos(AngToRad(angle));
m._12=sin(AngToRad(angle));
m._21=-sin(AngToRad(angle));
m._22=cos(AngToRad(angle));
m._33=1;
return m;
}

图7、绕z旋转的矩阵形式

由以上式子可以验证“用于乘于三维向量的3*3矩阵每行可以理解为转换后的基向量”这样的结论。这里列出的关于矩阵的实用操作技巧只是很少的一部分。但不论如何，通过一定的矩阵形式变换物体坐标系里的点坐标则一点问题都没有。这意味着经过变换的依然是有效的三维向量数据。但是它确实产生了一定的旋转、平移、镜像、切变等线性变化。我们的简化模型则对此一点也不关心。因为所有的数据变化都是在输入到流水线之前的。

图8、旋转等操作都是在进入流水线之前的事

七、传说的延续，在简化模型之上构建真实流水线，第一步是讨论方位
要逼近真实流水线，就是在去除所有约定元素之后，重新把它们构建起来。下一步可以假设整个物体空间就是世界的原点，然后对其进行透视投影。或者可以假设立体空间看到的物体就像简化模型表现的那样，然后对其进行物体到世界坐标系的转换。这个转换过程涉及到一个问题，就是物体的方位，所谓方位就是表示物体的三个坐标轴的面向的方向。
核心问题是对欧拉角（Euler）的正确理解和它是如何转化为矩阵并最终更新物体在惯性坐标系中的朝向的。
注意欧拉角的定义：它包含3个方位信息，Heading、Patch、Bank，物体一开始位于和惯性坐标一致的方位。并分别绕自身的y、x、z轴作HPB旋转。这相当于在惯性坐标系中改变物体坐标系的方位。其旋转的角度和物体旋转的角度相反。

图9、物体在惯性坐标系中绕自身坐标系分别做了HPB旋转

欧拉角的直观性在于贴近人类观察和描述事物的方式，实际上真正理解它并不是很轻松，尤其是用数值表示出来。
（理解1）首先，假设物体始终是不动的，这样它对于惯性坐标系或者物体坐标系来说都是不变的，根据欧拉角，定义，使物体分别绕物体坐标系旋转一定角度，为了保持物体本身和惯性坐标系之间的不变性，以及物体和物体坐标系之间的变化关系，可以直接旋转物体坐标系，这样，物体和物体坐标系的相对位置改变了，但是物体和惯性坐标系的相对位置没有改变。即，坐标系进行了HPB旋转，而实际我们需要的是点的旋转。即(H-)(P-)(B-)，这样便得到惯性坐标系到物体坐标系的改变。
（理解2）上面的理解有些牵强，因为并不符合我们思考的习惯。欧拉角是依据人对物体所在区域方位的认知，故对欧拉角的定义无法单独在物体坐标系或者惯性坐标系中讨论。定义中，欧拉角HPB的旋转均依据自身物体坐标系的轴向改变。用点的角度理解欧拉角：
  

以上是物体到惯性坐标系方位进行变换的推导过程。而惯性坐标系到物体坐标系的变化就是，跟理解1的结论一致，但显然要合理得多。
八、三维世界的语言，三角形——顶点列表和顶点索引
九、对视平面的定义以及视平面到屏幕空间的缩放因子

图10、视场大小和缩放的关系

图11、维持屏幕宽高比的视平面调整

  

十、Z深度排序算法以及相关优化——索引拷贝、顶点拷贝以及内置排序。
排序算法测试结果：
1、 顶点拷贝

图10、顶点拷贝二叉树排序

采用二叉树进行快速排序，但因为这种排序是位于vector之上进行的，没有得到很好的速度支持。
2、内置排序算法以及一次性流水线（而不是每次开关GDI状态）优化

图11、内置排序

采用编译器环境内置的排序算法qsort，它的速度可以得到很好地发挥。不过只能传递数组进去，这意味着数组大小要预先设置、引擎一个常数量的资源占用，所支持的最大多边形的大小以及速度之间的取舍。

测试结果是内置排序比架构于vector之上的快速排序快了5倍左右。
。
qsort(&trianglist,index+1,sizeof(TRIANGLE),tricompare);

int tricompare(const void* a,const void* b)
{
TRIANGLE t0=*((TRIANGLE*)a);
TRIANGLE t1=*((TRIANGLE*)b);
float z0avg=0.33333f*(t0.v0.z+t0.v1.z+t0.v2.z);
float z1avg=0.33333f*(t1.v0.z+t1.v1.z+t1.v2.z);
if(z0avg>z1avg)
         return -1;
if(z0avg<z1avg)
         return 1;
if(z0avg>z1avg)
         return 0;
}

图12a、排序前的渲染结果

图12b、排序后的渲染结果

经过排序后的渲染形体得于正常显示。

 

第二部分、光照和Gouraud着色

图2-1、执行了光照运算和Gouraud着色的示例

一、 灯光类型
点光源：具有颜色、位置、强度。并且随着距离变化二次反比衰减。我在模拟模型中使用一次反比衰减和固定衰减一次常量。

typedef struct
{
VECTOR3 P; //position
COLORF C; //color
float I; //intensity
}POINTLIGHT;

平行光：具有颜色、方向、强度。没有衰减距离。强度始终为常量。

typedef struct
{
VECTOR3 V; //vector
COLORF C; //color
float I; //intensity
}INFINITELIGHT;

环境光：具有颜色、强度，没有方向和衰减距离。强度始终为常量。

typedef struct
{
COLORF C; //color
float I; //intensity
}GLOBALLIGHT;

聚光灯：具有平行光的方向和点光源的距离衰减，以及根据照射方向发生的角度衰减。（没有实现）

灯光列表：和多边形流水线同级别的结构体，用于存储有关的灯光信息。

typedef struct
{
vector<POINTLIGHT> ptls;
vector<INFINITELIGHT> infls;
GLOBALLIGHT global;
}LIGHTS;

环境光只有一盏，可以这样理解，所谓的环境光是某区域场景的混色光线的简单模拟。

二、光线加法、光线调制、Alpha混合、线性插值
光线具有红绿蓝三个分量。GDI对分量的存储是蓝绿红分量排序。这不符合广泛的约定。因此对颜色重新定义如下：

Typedef DWORD COLORREF3;
#define RGB3(r,g,b) ((DWORD) (((r) << 16) | ((g) << 8) | (b)))
typedef struct
{
float r;
float g;
float b;
}COLORF;

以上添置了标记“3”以示区别。接下来描述的结构体用于存储浮点类型的颜色分量。取值从0.0f到1.0f，之所以取这个范围是当分量之间进行乘法运算时，颜色值始终不会越界。这使得颜色乘法有意义。类似的有镜面反射区域的余弦值的指数运算。正方向的余弦值始终在0到1之间，无论进行多少次次方运算都不会越界。
可以对光线分量简单累加，这普遍适用于同性质颜色复合（如都是光线或者都是材质，注意光线和材质相加没有意义，不过对材质的加法是假设材质信息即将被作为光线处理，如自发光的材质等）的多数情况，当颜色值越界时简单地截断，因为设备无法表现更宽广的亮度值域。如果是光线对某种材质进行照射的情况，因为材质是对光线的影响情况，而不是自发射的光源，所以没有可以累加的量，这时候调制运算就可以获得有效的数据。浅色系的物体材质对光线的反射能力更强，进行调制乘法的结果也正说明这一点。
对颜色三个分量同时乘于一个相同的标量，这会改变颜色亮度。如果一个固定配额。数个颜色根据该配额比进行调制，最后累加，得出的结果是物体呈现透明化。这就是Alpha混合。
线性插值，即在一个指定的着色区域，从一种颜色变化到另一种颜色，需要对每个步进值计算颜色变化率。平滑着色和纹理仿射等均使用了线性插值算法。

三、物体材质
我们理解的物体色，是指物体表面反射白色光线后呈现的颜色。具有以下几个分量：
环境光反射：材质的环境光反射分量决定了环境光对物体的影响程度。经常使用灰度值表示。
散射：即漫反射，物体的漫发射光线值不随观察角度变化。但是和光线射入方向和物体表面朝向关系密切。

图2-2、散射强度受光线照射方向和法向量夹角影响

镜面反射：镜面反射是受物体表面朝向、观察者视线、光线入射方向三方面影响的。当观察者视线位于光线反射方向上时，镜面反射强度最强，并依次余弦递减。典型的Blinn算法是根据这样的事实：当观察者位于光线反射方向上，观察者视线方向跟光线入射方向的中间量为表面法线，并依次按中间值的偏移递减。计算两个向量的中间量的运算量要比计算投影线直到计算出反射方向的运算量少。缺点是变化率和准确的Phong模型并不一致。但看上去足够可信。
另外镜面反射材质还有一个镜面反射率的指数位标记。越大的反射率，对夹角余弦的次方运算更为高次，衰减的速度快速下降，这样将会得到一个足够集中的反射区域，正如我们在现实生活中感受的那样。

图2-2a、k=13

自发光：和环境光线类似，不过实现要更加简单，只是一个物体发射光的参照量，如前所述，对于实体光线，需要做的运算就是光线加法。

typedef struct
{
float r;
float g;
float b;
float a;
}AMBIENT;
typedef struct
{
float r;
float g;
float b;
float a;
}DIFFUSE;
typedef struct
{
float r;
float g;
float b;
float k;
float a;
}SPECULAR;
typedef struct
{
float r;
float g;
float b;
float a;
}EMISSIVE;

Ambient：环境光反射、Diffuse：散射、Specular：镜面反射、Emissive：自发光。

光照计算公式：

公式2、光照计算

对光照的理解重点在于对光线加法和调制等操作的实际使用上。当然，对向量运算的背景知识是必须的，这不是问题，不是吗？最后，用不多的几个光源进行合理搭配，就可以创造出良好的游戏氛围。

 

图2-3、镜面反射模型

   

图2-4a、打开了环境光

图2-4b、打开了平行光

图2-4c、加入了点光源

四、执行程序结构
在讨论丰富的渲染模式之前，有必要对程序的结构有一个整体清晰的认识。并且，对着色、插值、纹理、光栅化、裁剪、深度缓冲等问题的讨论将不再允许有时间对这方面的问题做一个全面而具体的阐述。

图2-5、程序执行框图

主程序承载窗口和调度各个部件的协作。引擎负责像素级图形数据的绘制和呈现工作。流水线因为其重要性，所以从主引擎结构中独立出来，当然主观上我们依然可以认为它们是一体的。流水线处理线上的数据，并最终转化为可用的多边形和色彩值，调用引擎的绘制函数写入后备缓存。最后，主程序调用引擎的呈现功能，把内存中的图像拷贝到屏幕上。

初始化：
相机储存有裁剪面、视场角等信息
typedef struct
{
EULER E;
VECTOR3 pos;
float nearclip;
float farclip;
float portang;
}CAMERA;

这些信息被用于设定相机坐标转换相关矩阵和屏幕缩放因子。
物体模型信息是通过外部文件导入的，存在着各种各样的文件格式。我们目前对文件格式有如下需求：1、ASCII形式存储，因为我们有时候需要打开修改数据。2、材质描述，这在光照和着色渲染的时候必须用到。3、可选的顶点法线，因为顶点法线可以在模型载入的时候再计算，对于有限的多边形数，这种开销是值得的，所以顶点法线不是必须的。4、嵌入的或者引用的纹理信息。在ASCII文本中嵌入二进制信息是可行的。幸运的是，我第一次接触存储文件的时候，使用的msh支持以上各种情况。

MSHX1
GROUPS 1
MATERIAL 1      ; Cube
NONORMAL
GEOM 20 12
-2.060000 2.040001 2.033892 0.000000 0.000000
…
0 1 2
…
MATERIALS 1
White Matte
MATERIAL White Matte
0.941177 0.941177 0.941177 1.000000
0.745098 0.745098 0.745098 1.000000
1.000000 1.000000 1.000000 1.000000 1.280000
0.000000 0.000000 0.000000 1.000000
TEXTURES 0

该种文件格式可以在MilkShape 3D的导出功能中找到，另外，它不支持顶点色和线框色，颜色是在材质中描述的。我写了这种文件格式的加载函数，读取了有关的顶点材质信息，以及预先计算了顶点法线。并存放在OBJ结构体中。（我已经尽量避免了大量的代码引用，但是这些结构体信息是必须的）

typedef struct
{
AMBIENT ambient;
DIFFUSE diffuse;
SPECULAR specular;
EMISSIVE emissive;
}MATERIAL;

typedef struct
{
vector<VECTOR3> vbuf; //顶点列表
vector<VECTOR3> nbuf; //法线列表
vector<COLORF> cbuf; //法线光照
vector<int> ibuf; //顶点索引
MATERIAL material; //材质
}MODEL;

typedef struct
{
vector<MODEL> models;
EULER E;
VECTOR3 pos;
MATRIX m;
}OBJ;

上面列出了物体、模型组、材质等的结构体。值得注意的是：1、法线光照会存入-1.0f，直到该法线被计算的时候才被填充有意义的数值，这样每次流水线周期，法线光照都应该仅计算一次。2、物体的变换矩阵MATRIX m，之所以使用这个矩阵的理由是：无论如何这个矩阵都会被计算一次，在进入流水线之前可以对这个自变换矩阵进行操作，而不是实际数据，在流水线的开始点处该矩阵就会被执行。这样，修改的将是流水线上拷贝的物体数据而不是原始的数据。因为整个流水线环节主程序是无权干涉的，因此，传入这个矩阵是有意义的。
流水线：

typedef struct
{
vector<POINTLIGHT> ptls;
vector<INFINITELIGHT> infls;
GLOBALLIGHT global;
}LIGHTS;
typedef struct
{
vector<OBJ> objects;
TRIANGLE trianglist[30000];
}PIPELINE;

当前不支持聚光灯，所以灯光列表没有这个项目。流水线结构体放置了物体列表和多边形数组。这是可以理解的，因为数组排序速度更快。

SetPos(teapot.pos,0,0,20);
SetEuler(teapot.E,0,-10,0);
teapot.m=MI*rotationy(angle);
pipeline.objects.push_back(teapot);

这是放置物体到流水线的示例

POINTLIGHT ptl;
EMISSIVE& emi=ball.models[0].material.emissive;
COLORF c={emi.r,emi.g,emi.b};
ptl.C=c;
ptl.I=30.0f;
ptl.P=ball.pos;
lights.ptls.push_back(ptl);

放置点光源到光源表的示例。其中较为有趣的部分是：我读取了场景中一个自发光球体的自发光信息，并把它用于光源上，球体的位置信息也被用来描述点光源的位置，这样，我们得到了一个“真正发光”的自发光体，至少看起来是：

图2-6、运动的球体“发射”了光线

最后用一段流水线代码来结束程序结构的讨论，用语言完整描述它们的方式是很糟糕的。

int pipelinerender(const CAMERA& cam)
{
    MATRIX cm=MI; //相机变换矩阵
    VECTOR3 campos=cam.pos;
    cm=cm*translation(-campos.x,-campos.y,-campos.z);
    cm=cm*MT(objecttoinertial(cam.E));
    //透视投影
    cm=cm*cameratoview();

    VECTOR3 v0,v1,v2,u,v,n,vavg,normal0,normal1,normal2;
    VERTEX a,b,c;
    COLORF color0,color1,color2;
    MATRIX m; //物体到世界变换矩阵
    MATRIX mi=MI; //物体到惯性变换矩阵
    MATRIX mw=MI; //惯性到世界变换矩阵
    int index=0;
    for(int p=0;p<pipeline.objects.size();p++)
    {
     OBJ& obj=pipeline.objects[p];
     vector<MODEL>& models=obj.models;
     //物体自变换和转换到世界坐标
     mi=obj.m*objecttoinertial(obj.E);
     mw=translation(obj.pos);
     m=mi*mw;
     for(int g=0;g<obj.models.size();g++)
     {
      for(int i=0;i<models[g].ibuf.size();i+=3)
      {

       v0=models[g].vbuf[models[g].ibuf[i]]*m;
       v1=models[g].vbuf[models[g].ibuf[i+1]]*m;
       v2=models[g].vbuf[models[g].ibuf[i+2]]*m;
       u=v1-v0;
       v=v2-v0;
       n=VCross(u,v);
       n=VNormal(n);
       //背面消除
       if(backfaceclear(n,v0,cam.pos))
        continue;
       //对法向向量只旋转,不位移
       normal0=models[g].nbuf[models[g].ibuf[i]]*mi;
       normal1=models[g].nbuf[models[g].ibuf[i+1]]*mi;
       normal2=models[g].nbuf[models[g].ibuf[i+2]]*mi;
       //执行光照
       /*
       vavg=(v0+v1+v2)/3;
       color0=GetFaceColor(n,vavg,cam.pos,models[g].material,lights);
       color1=GetFaceColor(n,vavg,cam.pos,models[g].material,lights);
       color2=GetFaceColor(n,vavg,cam.pos,models[g].material,lights);
       */
       if(models[g].cbuf[models[g].ibuf[i]].r==-1.0f)
        models[g].cbuf[models[g].ibuf[i]]=GetFaceColor(normal0,v0,cam.pos,models[g].material,lights);
       if(models[g].cbuf[models[g].ibuf[i+1]].r==-1.0f)
        models[g].cbuf[models[g].ibuf[i+1]]=GetFaceColor(normal1,v1,cam.pos,models[g].material,lights);
       if(models[g].cbuf[models[g].ibuf[i+2]].r==-1.0f)
        models[g].cbuf[models[g].ibuf[i+2]]=GetFaceColor(normal2,v2,cam.pos,models[g].material,lights);
       color0=models[g].cbuf[models[g].ibuf[i]];
       color1=models[g].cbuf[models[g].ibuf[i+1]];
       color2=models[g].cbuf[models[g].ibuf[i+2]];
       //到相机坐标的转换
       v0=v0*cm;
       v1=v1*cm;
       v2=v2*cm;
       //相机空间裁剪,这步操作可以提前到光照计算之前,但需要保留变换前向量
       if(cliptriangle(v0,v1,v2))
        continue;
       pipeline.trianglist[index].v0.v=v0;
       pipeline.trianglist[index].v1.v=v1;
       pipeline.trianglist[index].v2.v=v2;
       pipeline.trianglist[index].v0.color=color0;
       pipeline.trianglist[index].v1.color=color1;
       pipeline.trianglist[index].v2.color=color2;
       index++;
      }
     }
    }
    //排序
    qsort(&pipeline.trianglist,index,sizeof(TRIANGLE),tricompare);
    LockSurface();
    for(int i=0;i<index;i++)
    {
     a.v=pipeline.trianglist[i].v0.v;
     b.v=pipeline.trianglist[i].v1.v;
     c.v=pipeline.trianglist[i].v2.v;
     a.color=pipeline.trianglist[i].v0.color;
     b.color=pipeline.trianglist[i].v1.color;
     c.color=pipeline.trianglist[i].v2.color;
     VDTriang(a,b,c);
     drawcount++;
    }
    UnlockSurface();
    return index;
}
int tricompare(const void* a,const void* b)
{
    TRIANGLE t0=*((TRIANGLE*)a);
    TRIANGLE t1=*((TRIANGLE*)b);
    float z0avg=0.33333f*(t0.v0.v.z+t0.v1.v.z+t0.v2.v.z);
    float z1avg=0.33333f*(t1.v0.v.z+t1.v1.v.z+t1.v2.v.z);
    if(z0avg>z1avg)
     return -1;
    if(z0avg<z1avg)
     return 1;
    if(z0avg>z1avg)
     return 0;
}

五、平滑着色，Phong或者Gouraud
最近我一直在考虑一个问题，如果把平滑着色的代码粘贴到文档编辑器中，它将占据几页的篇幅？答案是13页。我花了几天时间慢慢完整这个算法。第一步我使用浮点斜率和Alpha混合插值，每秒可以执行62000多个多边形。第二步我修改了多边形横向插值的内循环算法。使它不必执行乘法运算，而仅进行光线加法。为此必须给它指定浮点颜色值。每秒计算的多边形量提高很有限，仅为63000个。第三步我放弃了浮点颜色增量，而采用类似Bresenham画线算法的误差累积量修正。对于颜色值大于步进值的计算我置入了循环累加。这次表现得很不错，有90000个多边形。后来我对浮点的斜率修正很不满意，决定用类似的做法修改它，于是第四步我完成了整个函数的定点值计算，它处理了102000个多边行。我还发现了一些优化的地方，显存位置可以通过累加计算获得，对特殊多边形区别处理。

图2-7、对顶点色进行插值计算

我打算对这种算法起了一个别名，uvw三角形光栅化算法。因为整个过程都是围绕三角形三个顶点的位置关系来进行的。除此以外都是标准的插值算法。我总是假定U是最上端的顶点。V和W的位置关系在进行x横向颜色插值的时候起作用，我们总是从x值较小的位置开始光栅化，但是较大的V侧的x值使得我们必须从W侧的颜色开始插值。
Bresenham画线算法测试x、y方向的步进距离，并以较大的步进方向作为累加误差的轴向，而误差值和较小的步进方向关联起来。

图2-8、利用x和y的步进值计算误差

如图所示，我们在x方向上持续画点，初始y方向的值为0，每在x方向上绘制一个像素，采用一个误差值存储y步进量的累计值，当误差值大于x步进值，y方向的数值增加1个像素单位，并扣除。这样，当我们绘制完x方向的全过程,在y方向也进行了等比例的长度修正。可能是如下的代码：

if(lx>=ly){
err=0;
for(i=0;i<=lx;i++){
    DrawPixel(curx,cury,0x000000);
    if(err>=ly){
     err-=lx;
     cury+=y_inc;}
    err+=ly;
    curx+=x_inc;}}

图2-9、y步进值比x步进值大的情况

考虑这样一种情况，如果y方向的步进值大于x方向的步进值，这时候需要对y方向执行步进操作，利用误差值修正x方向的值。在画线任务中，这不是问题。但是在光栅化三角形的时候，情况有什么变化？

图2-10、光栅化三角形需要顾及V侧和W侧的斜率变化

我们可以使用类似的算法完成U到W的x方向偏移，因为x方向步进量相对于y方向的要小。但是U到V的斜率变化则超出了我们的预计，每移动y方向一个像素，x方向都会有几个单位像素的变化。可以逆向思考，如果在x方向偏移了这几个像素，导致了y发生一个像素的偏移，则可以置入内循环来叠加误差，并在误差达到y发生偏移的量度之前退出，如此往复。代码可能如下：

if(Vloop==false)
{
if(Verr>Ylen1)
{
    xV+=Vinc;
    Verr-=Ylen1;
}
Verr+=Vstep_;
}
else
{
while(Verr<Vstep_)
{
    xV+=Vinc;
    Verr+=Ylen1;
}
Verr-=Vstep_;
}

前半段是典型的Bresenham算法，后半段使用了一小段的Bresenham算法倒置。循环的条件不再是主动轴的跨度，而是引起被动轴发生修正的主动轴跨度。当然这个内置的倒置算法的主被动关系是相反的。即主动轴依然是y轴而不是Bresenham算法认为的x轴。
在进行这个光栅化算法的完善过程中，遇到的唯一障碍是，当V侧或者W侧发生斜率变化时，x的当前点已经可能产生了1个像素的误差，若对该x值再进行计算，则以下的点均可能往某个方向偏移了一个像素。其导致的实际效应如图所示：

图2-11、糟糕的像素误差

我相信每个或多或少遇到此类问题的人都会马上取消他们的周末行程。因为对于误差的出现我们已经熟视无睹了，特别是定点运算。但是有时候多边形最终呈现的结果很小，几个像素大小而已，这种误差必须避免。唯一的做法就是使用斜率变化处的顶点坐标作为起点坐标。并清除之前的偏移误差量。

if(minY==Yuv)
{
xV=v.x;
Ylen1=abs(Yvw);
Vstep=Xvw;
Vstep_=abs(Vstep);
Vinc=Vstep>0?1:-1;
Vloop=false;
Verr=0;
if(Vstep_>Ylen1)
    Vloop=true;
}

我将此称为“xV=v.x”启示。

图2-12、xV=v.x启示的结局

颜色插值有一致的算法，差别只是，xV到xW的变化量为主动轴向，像素色的变化为被动轴向。像素色分量从0到FF，每个像素增量单位为1，对应每个颜色的增量单位1，并进行轴向长度比较。
了解了基本的插值算法后，应该开始了解Gouraud如何在多边形渲染中工作的了。
如前所述，Gouraud采用顶点颜色插值。这需要我们计算顶点的颜色值。有一个问题是，一个顶点通常被几个多边形共用，而多边形经常是不共面的，因此顶点处的法向量应该是共点的几个多边形平面的面法线的均值，这样才能返回可信的光照结果。
向量的位置没有意义，只有它的方向才有意义。当然，所谓的方向固定意味着向量起点和终点之间位置关系的不变性。因此，事先计算各个顶点的法向量，在流水线周期内，利用旋转变换矩阵对法向量进行操作，便可以送入光照管道。光照的位置信息是和顶点相对坐标原点的位移联系的。这就提出了一个要求，光照管道内的所有向量信息都应该是归一化的。

图2-13、顶点法线受周围多边形面法线影响

用于计算顶点法线的代码段（Code Section）：

vector<VECTOR3> normals;
VECTOR3 u,v,n,v0,v1,v2;
COLORF c;
for(int i=0;i<model.vbuf.size();i++)
{
normals.clear();
//寻找具备该顶点的多边形
for(int j=0;j<model.ibuf.size();j+=3)
{
    if((model.ibuf[j]!=i)&&(model.ibuf[j+1]!=i)&&(model.ibuf[j+2]!=i))
     continue;
    //计算多边形面法线
    v0=model.vbuf[model.ibuf[j]];
    v1=model.vbuf[model.ibuf[j+1]];
    v2=model.vbuf[model.ibuf[j+2]];
    u=v1-v0;
    v=v2-v0;
    n=VCross(u,v);
    normals.push_back(n);
}
//所有法线相加
for(int j=0;j<normals.size();j++)
    n=n+normals[j];
n=VNormal(n/normals.size());
model.nbuf.push_back(n);
SetColorf(c,-1.0f,-1.0f,-1.0f);
model.cbuf.push_back(c);
}

最后说明的一个原则是：在设计算法的时候，如果有进行迭代，应在迭代数据产生增量前使用数据，在使用数据前计算溢出和裁剪。次序上的混乱经常是未知错误的根源。如上面的斜率变化应该属于溢出状态，即y扫描线已经到达了限界，必须在使用数据前修改部分数据。而进行增量前使用数据则容易理解。我们不应该在0扫描线未绘制的情况下把扫描线移动到了1，这样我们将缺乏0扫描线和增加了n+1扫描线。

 

图2-14、在没有纹理贴图参与的情况下，人物外形已经很逼真了

六、一个示例代码
使用为数不多的自定义代码可以创建高效灵活的执行程序，这是引擎的主要功用。它提供了大量的按约定模式组织的重用代码段和函数集。特别是，经过封装，可以利用显见的和容易理解的主程序逻辑来驱动引擎，达到预想的效果。
示例代码仅提供这些必须的信息：模型文件位置、相机信息、环境灯光，渲染器则提供：物体位置，光源信息。此外的一切任务全部在引擎中执行。在使代码简约、可读性强以及格式命名等方面进行了各种权衡和取舍。为了使结构体名尽量简单，我几乎都是使用它们直接的明文形式，这可能会导致重名问题，在某种必要的情况下，可以加入名称空间（Namespace）。

CAMERA cam;
OBJ wall,robit;
OBJ ball;
OBJ ball1;

int CustomInit(HWND hWnd)
{
//设定欧拉相机位置
SetPos(cam.pos,0,50,-90);
//设定欧拉相机方位
SetEuler(cam.E,0,30,0);
cam.nearclip=20;
cam.farclip=300;
cam.portang=90;
SetCamera(cam);
Load_msh(_T("彩色墙面.msh"),wall);
Load_msh(_T("机器人-武器.msh"),robit);
Load_msh(_T("ball.msh"),ball);
Load_msh(_T("ball1.msh"),ball1);
//设定环境光
setupgloballight(rgb3tofloat(0xFFFFFF),0.42f);
return 0;
}
int CustomRender(HWND hWnd)
{
static float starttime=(float)GetTickCount();
static float timedelta=0.0f;
timedelta=GetTickCount()-starttime;

//变换角度
static float angle=0;
angle=ANormal(timedelta/1000.0f*100.0f);

SetPos(wall.pos,0,0,0);
SetEuler(wall.E,0,0,0);
wall.m=MI*rotationy(-5);
pipeline.objects.push_back(wall);

SetPos(robit.pos,0,10,0);
robit.m=MI*rotationy(-angle);
SetEuler(robit.E,0,0,0);
pipeline.objects.push_back(robit);

SetPos(ball.pos,0,0,0);
SetPos(ball1.pos,0,0,0);
ball.pos=ball.pos*translation(30,0,0)*rotationy(angle);
ball1.pos=ball1.pos*translation(0,30,0)*rotationx(angle)*translation(0,8,0);
SetEuler(ball.E,0,0,0);
SetEuler(ball1.E,0,0,0);
ball.m=MI;
ball1.m=MI;
pipeline.objects.push_back(ball);
pipeline.objects.push_back(ball1);

POINTLIGHT ptl;
EMISSIVE& emi=ball.models[0].material.emissive;
COLORF c={emi.r,emi.g,emi.b};
ptl.C=c;
ptl.I=80.0f;
ptl.P=ball.pos;
lights.ptls.push_back(ptl);

EMISSIVE& emi1=ball1.models[0].material.emissive;
COLORF c1={emi1.r,emi1.g,emi1.b};
ptl.C=c1;
ptl.I=80.0f;
ptl.P=ball1.pos;
lights.ptls.push_back(ptl);

INFINITELIGHT infl;
infl.V=VSet(0.0f,0.0f,1.0f);
SetColorf(infl.C,1.0f,1.0f,1.0f);
infl.I=0.3f;
lights.infls.push_back(infl);

int trianglecount=pipelinerender(cam);
VDEnterGDI();
TCHAR buf[55];
_stprintf(buf,_T("%.3fFPS"),ShowFps());
VDText(50,50,buf);
_stprintf(buf,_T("多边形:%d"),trianglecount);
VDText(50,70,buf);
_stprintf(buf,_T("每秒多边形:%d"),drawcountpersecond);
VDText(50,90,buf);
VDLeaveGDI();
return 0;
}

七、对示例代码的维护
随着理解程度的深入和内容的持续扩充，之前一些演示代码的格式可能过时的，最简单的做法是，每个阶段的引擎系统和相关演示对应，并作为一个整体存储。这样就不必为了修改那些过时的结构体和编写风格而写了很多不必要的维护代码。事实证明这是合理而必要的。在进行最新内容的扩充时将尽量避免对结构体的改变，若不得不这样做则将在阶段代码中统一维护。

八、实用的工具集合
三维建模、格式转换：MilkShape 3D 1.710
几何图形绘制：几何画板4.07
电子书制作：pdfFactory Pro 3.17
图标制作：Microangelo Toolset 6
VC助手（提供完整的智能提示）：Visual AssistX 10.1.1418
公式编辑：MathType 5.2
以上工具均可在网络上获取。

 

第三部分、UV仿射贴图、材质混合、文件操作

图3-1、将光照和贴图进行了材质混合

图3-2、使用z缓冲来执行像素级排序,使物体得于正确渲染

目前还没有涉及裁剪，因此对于一些离相机过近以至发生负投影的多边形被简单地剔除了。视景体的其它5个面则被简单地利用光栅化函数过滤了。这类似于硬件的工作模式，因为它足够简单并且可以假设我们可以在以后事先执行了裁剪，这样光栅化函数只是提供了判断的开销，这对于不执行这样的任务的灾难性后果来讲是值得的。
一、Bmp位图格式和读取位图信息
为了把贴图放置到网格上，首先要解决的问题是使用什么图像格式和定义它的内存镜像格式。当前最简单的图像格式是bmp。我使用了它的8位和24位版本。8位因为信息量不足（仅仅256个定义长度），所以引入了调色板的形式。而24位色版本则提供了全部的RGB信息。执行贴图运算的时候，为了要立即得到有用的RGB信息，调色板索引应该在读取位图之后进行转换，和24位色版本一致。这是当前的硬件条件所允许和显示模式所决定的。因此，所有的各种图像格式最终都要转化成一致的内存镜像格式。
对于文件操作，我使用了fstream流，这是C++的标准文件IO操作流，是STL（标准模板库）的一部分，现代编程需要程序员更快地解决问题，模板化为这一切作了大量的工作，C++并不意味着总是使用类结构，事实上，模板化范型编程正在成为C++编程的事实标准。设想，一个数组可能是包容字符的或者是浮点类型的数据集，而vector则替代了数组，没有指针操作，它使用了迭代器。原始的C++语言对于类内部类型是严格定义好的，假设有一个Cvector类，它可能只接受整型数据，但是vector接受任何你想要存放的类型，使用vector<type>作为类型符号。并且可以使用和指针相同的偏移模式进行迭代，它的size()子函数提供迭代限制。

fstream f;
f.open(filename.c_str(),ios_base::in|ios_base::binary);
if(!f)
{
f.close();
return -1;
}
//读取文件头
f.read((char*)&bmf.bmfh,sizeof(BITMAPFILEHEADER));
f.close();

ios_base枚举了fstream可能会用到的各种限定符，open()第二个参数需要指定打开类型，有一些有用的枚举：
ios_base::in 读操作    ios_base::out 写操作 ios_base::app 追加写入
ios_base::ate 添入 ios_base::binary 二进制 ios_base::trunc 截断
读写操作子函数：
write() 写数据     read()读数据     get() 获取字符/字符串
getline() 获取一行字符串

位图格式：Bitmap File Format
1、镜像文件：
#define PALETTEENTRYS 256
typedef struct
{
BITMAPFILEHEADER bmfh;
BITMAPINFOHEADER bmih;
PALETTEENTRY palette[PALETTEENTRYS];
BYTE* bits;
int size;
int width;
int height;
int bitcount;
int bpp;
int pitch;
}BITMAPFILE;

真实文件数据不包含BYTE* bits后面的数据，那是为了访问方便而人为加上的。
2、文件头BITMAPFILEHEADER

typedef struct tagBITMAPFILEHEADER {
          WORD      bfType;
          DWORD     bfSize;
          WORD      bfReserved1;
          WORD      bfReserved2;
          DWORD     bfOffBits;
} BITMAPFILEHEADER, FAR *LPBITMAPFILEHEADER, *PBITMAPFILEHEADER;

有用的数据是bfType，应该为0x4d42，即“BM”，bfSize，指出文件头结构大小，bfOffBits：缓冲区数据的起始处相对于文件开头的偏移量
3、文件信息BITMAPINFOHEADER

typedef struct tagBITMAPINFOHEADER{
          DWORD        biSize;
          LONG         biWidth;
          LONG         biHeight;
          WORD         biPlanes;
          WORD         biBitCount;
          DWORD        biCompression;
          DWORD        biSizeImage;
          LONG         biXPelsPerMeter;
          LONG         biYPelsPerMeter;
          DWORD        biClrUsed;
          DWORD        biClrImportant;
} BITMAPINFOHEADER, FAR *LPBITMAPINFOHEADER, *PBITMAPINFOHEADER;

biSize：该结构的大小，用于指出当前结构版本，biWidth：图像宽度，biHeight：图像高度，biPlanes：包含的调色板数，biBitCount：色深度，biSizeImage：图像数据区长度，biClrUsed：使用的调色板色数。biClrImportant：主要调色板色数。

4、调色板单元PALETTEENTRY结构

typedef struct tagPALETTEENTRY {
      BYTE          peRed;
      BYTE          peGreen;
      BYTE          peBlue;
      BYTE          peFlags;
} PALETTEENTRY, *PPALETTEENTRY, FAR *LPPALETTEENTRY;

peRed、peGreen、peBlue，8位长度的RGB信息，因为约定的关系，以上信息跟GDI的RGB次序是一致的，但是和显示屏RGB次序颠倒，为了使用方便，需要调整R和B的位置。最后一个标志符是向系统提示调色板的使用方式：

#define PC_RESERVED       0x01      /* palette index used for animation */
#define PC_EXPLICIT       0x02      /* palette index is explicit to device */
#define PC_NOCOLLAPSE     0x04      /* do not match color to system palette */

以上三个标志符分别指定为：可变的、系统默认、自定义。基本上，我们总是使用自定义调色板。这个标志字符文件没有给出，作为保留段。所以由导入函数指定。
缓冲区没有什么好神秘的，不同的位深的图像有不一致的像素占位。8位图像占据1个位长度用于指定调色板索引。24位图像占据3个位长度。主要的问题在于，由于历史原因，很多图像的y方向扫描线是颠倒的，也就是图像是自底向上指定的。

图3-3、图像自底向上指定

当图像文件内定的高度信息是正值，便声明为以上形式，反之亦然。

//翻转位图
if(bmf.height==Abs(bmf.height))
{
BYTE* buf=(BYTE*)malloc(bmf.size);
memcpy(buf,bmf.bits,bmf.size);
memset(bmf.bits,0,bmf.size);
for(int y=0;y<bmf.height;y++)
    memcpy(&bmf.bits[y*bmf.pitch],&buf[(bmf.height-y-1)*bmf.pitch],bmf.pitch);
free(buf);
}

图3-4、图像最终呈现在窗口上

二、仿射纹理贴图
对物体网格表面进行贴图可以简化成对单个多边形执行贴图的任务，附图呈现的是一个多边形，使用的采样对象的坐标值均转化为0-1的浮点数值，这意味着我们可以使用任何尺寸的位图作为采样对象，因为多边形使用的采样对象坐标都是一致的。当然，在最终光栅化阶段，我们需要对事实上的坐标进行插值。这一切对于网格操作和图像选取任务都是透明的。

图3-5、使用归一化坐标进行纹理采样

当前考虑的是图像空间的采样，因此标准的插值算法是有效的。该插值过程和Gouraud着色渲染插值同步进行，我几乎是将Gouraud的插值代码重新拷贝了一遍，它就开始正常工作了，当然了，我修改了变量名，以便于它同采样点对应起来。注意，光栅化阶段的采样使用的并非归一化坐标，而是事实坐标，这样才能有足够的定点数进行插值。并且避免正式采样的时候还要转化一次坐标。
仿射纹理映射和Gouraud着色的插值计算存在的同样一个问题是，插值过程是在图像空间进行的，而事实上，图像空间上的坐标点是经过透视变换的，在图像空间线性变化的数值，在实际相机空间中受z方向的数值变化影响而呈非线性变化，变换如图所示：

图3-6、透视变换中，z值得区别使得在视平面线性变化的点在实际空间非线性变化

图形学有一句至理名言“如果它看起来是，那它就是了”。而事实上，这种情况是可以得到更正的，根据公式y=y’(d/z’)，我们可以对d/z’进行插值计算，这样就能够得到y值变化在图像空间“扭曲的”而在相机视景体空间是线性的插值过程。后面将会接触到的z缓冲算法的一个变种就是基于这样的事实。
尽管如此，目前我仍然使用了看起来笨拙但是更容易实现和高效的图像空间插值。当多边形在深度上相对于视平面平行面的跨度并不是很大，即多边形平面和视平面的倾斜夹角较小时，插值过程越精确。

图3-7、进行仿射纹理映射的结果图，就如我们在示意图假想的那样

还有其它问题，第一、起点误差，这是扩展Bresenham算法引入的起点误差计算，我现在要处理的事情是如此之多，因此我一直没有对它进行额外编码。第二、双线性过滤，对纹理采样的时候，为了避免锯齿现象，应当在2D空间对当前采样点的周边进行加权计算以确定最终像素色值，很明显，这会占用处理周期。

三、流水线层次结构
基本层次结构：

对应关系：

其中，若法线和顶点列表同步，而不是独立到多边形面序列，则通过顶点索引访问法线列表和光照列表。最终权衡，我决定放弃对3DS MAX的法线多边形面序列的兼容，对顶点法线做统一处理，使得每个顶点的光照只需计算一次来提高效率。

修改的对应关系：

上例中将法线和光照和顶点列表对齐，这样每个顶点光照将只计算一次。但这种格式需要对多边形网格有一个约定，对于由平面组成的图形，需要分割位置一致但法向量不一致的顶点。
四、Alpha混合查找策略
在讨论光线调制和Alpha混合的时候，我曾经提到，0-1的浮点取值使得光线乘法有意义并且不会导致越界。事实上，浮点运算有时候并不是我们想要的，而且，RGB的分量只有256的精度范围，在32位色格式中的A值也是使用了8位存储，使用浮点计算显然有些夸张。实践证明，光线乘法并不是单纯的乘法计算，而是一种类似将信息置入载波的调制过程。在对0-1的取值进行计算的时候隐含了除于1的降0位操作。由此可知，当对两个8位数值进行调制运算时，需要对其进行降8位操作，结果数值范围保持在8位以内。

如上式所示，一种更容易理解的方式是，将分量转化成0-1的浮点数值，再将它逆乘，得到调制的结果RGB显示格式:
R=(int)(((float)R1/(float)0xFF)*((float)R2/(float)0xFF)*(float)0xFF)=R1*R2/0xFF
显然，得出的结论一致，但是0-1浮点数值的相关运算是基于先验性的假设，这是一种不确定的推导。

for(int i=0;i<=0xFF;i++)
for(int j=0;j<=0xFF;j++)
    alphatable[i][j]=i*j>>8;

上述查找表将用于支持Alpha混合计算。例如，讨论纹理映射的时候，我忽略了这样一个细节，如何将光照的结果同贴图色混合起来。下面就是使用该查找表进行混合的实例代码：

bmpB=alphatable[bmpB][Bbase];
bmpG=alphatable[bmpG][Gbase];
bmpR=alphatable[bmpR][Rbase];

五、ASCII网格存储结构，msh和ase
Msh是从MilkShape 3D导出的一种简易而高效的文本存储格式，但是它并不支持动画网格和骨骼。而MilkShape 3D的默认文本导出格式则支持。另外，3DS MAX导出的3DS格式导入到MilkShape 3D的时候，会出现坐标系错误，支持的顶点数有限，贴图坐标破坏以及其它未发现的问题，再者，直接使用3DS MAX的一些特性选项有时候会成为一种需求，总之，有必要直接从3DS MAX导出的文件中读取信息。
但是3DS MAX导出的ASE文件有几个问题，第一，它仅支持三角形面级别的法线和贴图坐标，而通常我们均把法线、顶点光照、贴图坐标等同顶点列表对齐，这个问题在上面讨论流水线层次结构的时候已经提到。第二，它使用标签描述格式而非流格式，当然我们可以使用流格式的处理手段来读取它，但是这意味着随着对此格式文件的内部信息的需求的增加，将使得代码越来越混乱，最终我考虑了这样的策略，开发一种自定义的二进制文件版本，用于支持对任意输入格式的导出和文件级缓存工作，甚至到后来直接作为外部工具对所有开发包使用到的模型进行转换。这可以极大缓解处理ASE格式文本信息低效的现状。在实现上它应当没有问题，因为这种二进制格式是我们任意给定的，为了完成这项任务，它将同流水线的层次结构对齐起来，实现广泛的兼容性。这意味着，任何导入格式在这种二进制格式没有体现出来的特性，在流水线层次结构中也没有对应元素。一旦确定需要某种元素，这种特性立刻就会在流水线层次结构和二进制文本格式中同步更新。这样，我们使用了所有我们要求的外部信息而没有降低处理速度。另一方面，即使为了速度考虑而优化了ASE等文本格式的导入工作，上述的开发依然是必须的。只不过我们把它提前了，以便于我们不必在文本格式的低效性上大费脑筋。
Msh文件结构：

关于这种格式，优点是简单易行，缺点是它没有支持更多的特性。当然，对于场景编辑，这种格式已经可以满足需求，而桢动画则使用多文件或者单文件多段存储，如果坚持要使用这种文件格式的话。
3DS MAX标准文本导出格式ASE的文件结构：

如果你正在寻找它的几何体存放在哪的话，事实上，这不是描述具体信息层级关系的图示，而是类似XML的一种存储规范，它具有独立标签和嵌套标签，独立标签有名称和值表，而嵌套标签不仅可以嵌套子标签，还可以嵌套“子嵌套标签”，如此递归下去。这种格式固然带来很大的灵活性，但是非常浪费时间。需要对它们全部解套然后利用一致的算法，提供一个匹配标签名进行标签取出和迭代。
*3DSMAX_ASCIIEXPORT 200
*COMMENT "AsciiExport 版本    2.00 - Wed Sep 19 22:16:39 2007"
*SCENE {
*SCENE_FILENAME "box.max"
*SCENE_FIRSTFRAME 0
*SCENE_LASTFRAME 100
*SCENE_FRAMESPEED 30
*SCENE_TICKSPERFRAME 160
*SCENE_BACKGROUND_STATIC 0.00000000 0.00000000 0.00000000
*SCENE_AMBIENT_STATIC 0.00000000 0.00000000 0.00000000
}
第二行使用了双引号对值进行了限定，避免被分割成子单元。我们可以假设*SCENE块还可以内嵌子块，假如存在，便可将此子块作为独立单元进行递归分解。直到所有嵌套子块全部被遍历。
算法很优雅，优雅的代价是慢。我可以开发一种不太优雅的较为快速的流式提取法，但是最后我决定使用文件级缓存和转换工具。在没有转换的情况下对所有导入格式进行二进制文件级缓存。缓存尽量写在当前文件夹的某个子文件夹中，仅当子文件夹不可访问的时候才写入系统临时文件夹。
但是目前我还是把该解析算法列出来。作为一种参考和改进的基础。

元素定义：

typedef struct
{
string name;
vector<string> values;
string itembody;
}ASEITEM;

struct ASEBLOCK
{
string tag;
vector<string> values;
vector<ASEBLOCK> blocks;
vector<ASEITEM> items;
vector<string> blockbody;
};

进行数据递归分解：

ASEBLOCK ase_getblock(const vector<string>& lines)
{
ASEBLOCK block;
ASEBLOCK subblock;
ASEITEM item;
vector<string> strs;
vector<string> inlinebody;
int step=0;
bool bracket=false;
bool headerline=false;
vector<string> headerinfo;
for(int i=0;i<lines.size();i++)
{
    strs=split_space(lines[i]);
    //检查行类型
    //单元模式
    if(step==0&&strs[strs.size()-1]!=_T("{"))
    {
     item.values.clear();
     item.itembody=lines[i];
     for(int j=0;j<strs.size();j++)
     {
      if(j==0)
       item.name=strs[0];
      else
       item.values.push_back(trimquot(strs[j]));
     }
     block.items.push_back(item);
    }
    //块模式
    headerline=false;
    if(strs[strs.size()-1]==_T("{"))
    {
     if(step==0)
     {
      headerline=true;
      headerinfo=strs;
     }
     bracket=true;
     step++;
    }
    if(strs[strs.size()-1]==_T("}"))
    {
     bracket=true;
     step--;
     if(step==0)
     {
      //subblock=ase_getblock(inlinebody);
      subblock.blockbody=inlinebody;
      for(int j=0;j<headerinfo.size();j++)
      {
       if(j==0)
        subblock.tag=headerinfo[0];
       if(j>0&&j!=headerinfo.size()-1)
        subblock.values.push_back(headerinfo[j]);
      }
      block.blocks.push_back(subblock);
      inlinebody.clear();
      bracket=false;
     }
    }
    if(bracket&&(!headerline))
     inlinebody.push_back(lines[i]);
}
return block;
}

六、自定义二进制储存格式

typedef struct
{
TCHAR sourcefile[64];
int modelcount;
int materialcount;
int texturecount;
}LOSFILEHEADER;

typedef struct
{
TCHAR modelname[64];
int vertexcount;
int indexcount;
int tvertexcount;
int tindexcount;
int textureindex;
int materialindex;
}LOSMODELINFO;

这是一种非常紧凑的储存格式，并涵盖了每个阶段引擎所需的任何细节，因为它和OBJ结构体的描述基本上保持一一对应的关系。导出和导入工作都可以非常快速而简洁地完成。

性能测试比较