DirectX Graphics 8.1中的Mesh优化

网络技术是从1990年代中期发展起来的新技术，它把互联网上分散的资源融为有机整体，实现资源的全面共享和有机协作，使人们能够透明地使用资源的整体能力并按需获取信息。资源包括高性能计算机、存储资源、数据资源、信息资源、知识资源、专家资源、大型数据库、网络、传感器等。当前的互联网只限于信息共享，网络则被认为是互联网发展的第三阶段。优化是程序员常挂在嘴边的两个字。有经验的程序员更是把程序的优化看得十分重要。初学编程的人却经常忽视这个问题，认为把程序写完，能完成要求的功能就行了（尤其是在做课设的时候:P）。如果你也是个初学编程的人，你也许会问：优化真的那么重要吗？好吧，让我们在这篇文章中探讨一下这个问题，等到最后，你就会知道答案。
本文的主要目的是探讨程序的优化。但是本文为了探讨这个问题，使用了一个DirectX 程序作为研究的对象这是因为在这个程序中出现了比较典型的优化和未优化之间的差异。所以说，本文更适于那些正在研究DirectX技术的初学者。当然，本文所讨论的问题并非仅限于DirectX中的内容。因为优化是一个涉及编程领域中很广泛的范围的话题。
没有研究的对象，我们所说的一切都跟空谈没什么区别。所以，首先让我来介绍一下本文用来探讨优化问题所用到的程序。
这个程序很简单，是一个模拟“第一人称射击游戏”的程序，确实很简单——简单到简陋的程度（至少我是这么认为地）——没有碰撞检测，没有光照，没有LightMap，没有BSP树，没有敌人（也就没有AI），没有武器：天那，什么也没有！整个程序除了显示一张这种游戏的场景并让游戏者在其中自由运动之外，什么也不干。（知道为什么“第一人称射击”要加引号了吧 :D）是我用不到两天的时间写着消磨时间的。下面是这个程序的一些截图：

文章插图
【DirectX Graphics 8.1中的Mesh优化】

文章插图

文章插图
怎么样，还有那么一点意思吧。那么，这个程序又是怎么跟优化产生联系的呢？为了说明这个问题，我不得不首先介绍一下DirectX 8.1中用到的ID3DXMESH接口。这个接口通过封装以下成分而提供了基本的网格模型操作函数(注意是网格模型不是网络模型:) ) 。
一个顶点缓冲(vertex buffer)，包含了网格模型上所有的顶点。
一个索引缓冲(index buffer)，包含了构成网格模型的所有三角形的三个顶点在顶点缓冲中的位置。
每个三角形的属性编号(attribute ID) 。是一个32位的整数，通过它，你可以把网格模型的三角形分成若干组（每个组的成员具有相同的Attribute ID）。不同的组具有不同的贴图或材质，可以分别绘制。我们所说的优化，就和这种机制有关。（注：之所以按照贴图和材质进行分组绘制，是因为在3D程序中切换当前的材质或贴图是十分耗费时间的,所以最好一次绘制具有相同材质或贴图的所有三角形。）
通常状况下，当从文件中读取一个网格模型后，所有的三角形在内存里都是属性杂乱放置的，就像下面的样子：

文章插图
图中的黄色表代表内存中的一系列三角形结构记录，每个格是一个三角形结构所占的空间。格里的数字代表各三角形的属性值。当调用ID3DXMESH::DrawSubset()函数绘制网格模型的各三角形组时，如果三角形是这样放置的，在绘制一组三角形时，就需要遍历整个网格模型的所有三角形，并判断该三角形的属性值是否和当前绘制组的属性值相同。如果相同，就绘制；否则跳过，判断下一三角形。例如，我们要画所有ID为1的三角形，就需要从头开始遍历：第一个三角形ID = 2，不画；第二个三角形ID = 4，不画；第三个三角形ID = 1，画；以此类推，在遍历到第8个三角形时，ID = 1，画。一值遍历到最后一个三角形，没有ID = 1的，说明所有ID为1的三角形都已画完。如果这时又要画ID = 2的所有三角形，就得照这样再来一遍。这样的话，由m个三角形，分成n组的网格模型，绘制一次就需要判断m*n个三角形。像图中这种具有9个组的网格模型，完整地绘制一次需要遍历所有的三角形9次。虽然在这里数据少看不出有太大的开销，但是在多边形数量很多，同时分组又很多时是十分耗费时间的。本文所说的那个小程序显示的场景网格模型大约有4500个三角形，并大致上分成7组。这样，每绘制一帧画面，就需要遍历约 4500*7 = 31500个三角形。而其中有6/7的三角形是不需要绘制的——在这种情况下，此程序在我的机器上跑起来也就3-5帧/秒，完全是一格一格的跳(我用的是赛扬466CPU + 320MB内存 + TNT2Pro 32M显卡) 。这已经足以使你对自己的机器失去信心，叹到：又该升级了......而不知道你的机器是被冤枉的(CPU：本来一帧只需要画4500个三角形嘛，你让我做31500次判断，不慢才怪哩！:( )，实际上这是低效的程序捣的鬼。
那么，怎样进行优化呢？有的人可能提出这样的方法：把每次遍历过的三角形做一个标记，在绘制下一组的时候可以不判断这些三角形。你同意这种方法吗？呵呵:D 只要稍微想一想，这样做实际上是“背着抱着一边沉”——判断多边形的ID也是判断，判断多边形是否被标记过也是判断。这种方法根本没有减少判断的次数，反而增加了用于标记多边形的内存空间和标记多边形的操作所带来的时间上的浪费。(:P希望你没有中计。)
那么，到底怎样进行优化呢？你一定也已经想到了。把内存中所有的三角形按照下面的样子放置：

文章插图
Attribute table(s,e):{
{0,0},{1,2},{3,5},{6,7},{8,11}, //数字表示具有相同ID的一组三角形
{12,13},{14,14},{15,15},{16,16} //的起始位置和结束位置。
}
图中，s代表开始(start)，e代表结束(end) 。这样，把所有具有同样属性值的三角形放在一起，并在另一个缓冲中记录下每一组的起始位置(s)和结束位置(e) 。这个缓冲称为属性表(Attribute table) 。由于只需记录起始和结束两个值，所以属性表是非常小的。别小看这个小小的变化——简单的变化——它使程序的效率成倍增长！每次绘制一个组时，再也不必把整个网格模型上所有的三角形遍历一遍进行无谓的比较了，而是从要绘制的组的起始位置的三角形开始画，一直到结束位置的三角形为止。如果要画第一组，起始为0，结束为0，所以只画第0个三角形；画第二组，起始1，结束2，只需画第1、2个三角形；第三组，起始3，结束5，只需从第三个三角形开始画到第五个三角形。以此类推，当按照Attribute table绘制所有的组后，整个网个模型就被绘制了一遍。这样，在绘制整个网格模型的时候，每个三角形保证只被访问1次。对于本文讨论的程序而言，它使效率起码提高了7倍(少判断了27000个三角形) 。再除去原来对所有冗余的三角形做的操作，效率提升了绝不仅仅是7倍。
实际上，ID3DXMESH接口提供了两个做这种优化的函数：ID3DXMESH::Optimize()和ID3DXMESH::OptimizeInPlace() 。它们的区别就是前者会复制出一个新的经过优化的网格模型，而后者是在原来的模型上进行优化。另外，这两个函数除了作上述的优化之外，还可以做一些额外的工作使得顶点Cache的命中率升高，进一步提升程序的效率。但是很多初学者都不信任它们，认为花费时间调用这两个函数完全没必要。然而使用了这两个函数之一后，再次运行上面的程序，给人的感觉就是两个字：流畅！帧数起码在60以上，再也不是一帧帧的跳了，优化效果相当明显。所以，如果你在研究Direct3D，如果你是个初学者，如果你对这两个函数没有什么印象，请你从现在开始分一些注意力给它们。
好了，跟这个程序有关的部分就告一段落了。下面我们回到普遍的问题上来，那就是——优化重要吗？相信你已经知道答案了。实际上，好的程序员都应该把自己的程序进行有效的优化。在这方面做的最为显著的就是Id公司的编程人员们。如果你看过《图形人员编程指南》，你就会深有体会。书中提出了一句很经典的话：“最好的编译优化器是编程人员的大脑。”一个程序在面临大量的数据操作的时候，经过优化和没有经过优化是相当不同的。面对同样的工作，你的软件需要一刻钟，而别人的软件只需一分钟就能完成，那么，客户会买谁的软件呢？所以，我觉得，初学者在学习编程的过程中不能仅仅满足于把程序写完就完了，还应该着重练习一下对程序的优化。
（责任编辑: 9PC TEL：010-68476606)