目录
一、研究背景
二、三维模型的网格简化算法
1、分片简化
2、使用外部数据结构
3、网格批处理
4、流式简化
三、论文的主要内容及章节安排
四、基于点分片的三维模型的网格简化
五、三维模型的网格简化
六、基于八叉树单形分割的并行等值面生成
七、结 论
八、参考文献
一、研究背景
在图形学应用中，有很多产生网格的途径，比如从点云、CSG模型、体数据等进行生成。随着计算机技术的不断发展，这些方法生成的网格越来越大，有些甚至超出了普通PC机内存的装载能力。它们中间比较著名的有斯坦福和IBM实验室对米开朗基罗的雕塑进行扫描与重建所得到的模型。这些模型能够提供非常精细的细节，但普通PC机内存无法装载和渲染，因此需要对这些模型进行简化。本文针对以上问题，提出了三种不同应用场景下的简化算法。
大规模等值面的即时简化是针对三维模型数据生成的等值面过大、甚至超过了内存的装载能力、难以处理，而提出的生成一部分就进行简化的方法。它不需要生成全部等值面，因此避免了耗时的基于外存的等值面生成和out-of-core简化。
本章接下来将对网格简化与等值面自适应生成做一个简短的综述。由于内存简化算法是大规模简化算法的基础，因此本章将首先对内存网格简化算法做以综述。
二、三维模型的网格简化算法
1、分片简化
Hoppe最早提出了分片简化的思想，他将其基于内存的“渐进网格”数据结构扩展到大规模高度场数据的简化中。作者首先将原始的高度场网格数据按照其坐标沿x、y轴平均分割成几个矩形的分片，并保证这几个分片能放入内存中。对三角形分片之后，由于某些点和边在边界之上，故不能做简化，只能保持。算法随后对分片内部的点采用边收缩将每个分片简化到一定程度。由于分片边界被保留，使得整体网格密度变得不均匀，因此作者再将分片简化之后的网格（保证这个网格一定能装载进内存）重新进行一次内存简化，进而使最终简化的效果令人满意。
2、使用外部数据结构
Paolo Cignoni等提出了一种基于八叉树的外存网格数据结构（OEMM）来对大规模网格进行简化。它提供对复杂大型网格的外存数据管理功能，支持动态地将需要的网格数据从外存装载入内存，并能够维护在对网格局部区域进行修改时的数据一致性。有了这样的数据结构，很多对大型网格的复杂操作（如简化，细节保持，网格编辑，可视化以及网格分析）等就可以在普通PC机上实现，而且其时间耗费是可以忍受的。
3、网格批处理
Peter Lindstrom提出了一种对三角面片进行批处理的算法。这种被称为OOC顶点聚类的方法与早期Rossignac提出的网格聚类方法类似。算法在最初获得网格的包围盒。这个包围盒可以由用户指定也可以通过一次扫描算出，而作者则假设包围盒已经给定。在已知算法的包围盒之后，算法根据用户的输入对包围盒的x、y、z方向平均分成几个等份，因此组成一个大小相同的立方体集合。然后对于每个三角形的顶点，判断其落在那个立方体之内，并将其加入到立方体之中。作者对原顶点聚类的一个优化是在计算每个聚类中的代表顶点的时候，使用类似论文中的方法，保存落在这个聚类中的所有的面片的二次误差矩阵的和。由于二次误差矩阵乘以某个顶点代表的是这个顶点到集合中所有平面距离的平方和，所以对这个矩阵求最小值既能得到一个最优的代表顶点。
4、流式简化
流式简化基于对网格移动工作集的处理。移动工作集是指大规模网格载入内存中的一部分数据，这些数据会随着处理的不断进行而向网格的其他部分移动。流式算法跟随移动工作集的移动而一部分一部分地处理网格数据。由于移动工作集是无缝地逐步扫描过整个网格，整个过程就好像“流”过网格一样，因此被称为流式算法。流式算法需要解决的一个问题是何时能够对网格的元素（顶点或者边等）进行消除或者修改。流式算法载入内存的是网格的一部分，因此产生了内存部分与外存部分的边界。就像分片简化中的保持边界不简化一样，流式简化也需要保持这些边界不被简化，以防止出现拓扑结构不一致性的情况。
三、论文的主要内容及章节安排
三维模型的网格简化算法提出了挑战，很多不同的技术都试图在大数据的外存访问效率和网格的简化质量中间取得平衡，有的方法只顾及了一方面，有的能做到两者兼顾。本论文在原先串行单形分割算法的基础上，对分割方法做了简化以减少体数据函数近似产生的误差，并对它做了并行的改进。本论文算法的主要贡献是提供了一套完整的基于GPU并行的八叉树建立与最小边查找方法。它自顶向下分层建立八叉树，并在查找最小边的时候，将当前一层边的分割结果与当前一层八叉树节点所展开的新边、当前一层面分割所引入的新边一起加入到下一层待分割的边中。在实际测试中，本论文的算法能够产生流形且无自交的自适应等值面，并在处理大规模数据时获得了相对于串行算法较高的加速比。
