|
|
《论简化三维流水线和逼近真实流水线》
—— 王志鹏
实验目的：通过简化流水线可以在相当短的实践周期内逼近真实流水线。
实验场所：厦门市同安区
实验工具：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==-1)
{
i+=2;
continue;
}
VMove(hMemDC,vertex[triang[i-2]]*m);
VLineTo(hMemDC,vertex[triang[i-1]]*m);
VLineTo(hMemDC,vertex[triang]*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;
代码所示的是这样一个矩阵：
 。
矩阵乘法法则：
用于乘于三维向量的3*3矩阵每行可以理解为转换后的基向量。初始基向量为 ，分别对应x、y、z轴的标准向量。转换后的基向量为 ，这为我们利用变换后形态逆向构造变换矩阵提供了可能性。
以下列出绕一个轴旋转的代码，及其矩阵形式：
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、排序后的渲染结果
经过排序后的渲染形体得于正常显示
(更新中...光照部分未完成) |
|
发表于 2007-9-2 03:56:00
楼主