论文部分内容阅读
近年来，伴随着超高精度的输入设备如三维扫描仪、CT/MRI等的飞速发展，从现实世界中获得的三维模型的规模出现爆炸性增长，甚至远远超出了当前的通用计算机的内存容量，使得运算时无法一次装载进内存，我们称这类超大规模三维模型为海量三维型，或外存模型。由于海量三维模型可以高度真实地保留原物体的全部细节，在很多方面有很强的应用需求，比如文物保护、数字化虚拟博物馆、虚拟人计划等。然而，海量三维模型的巨大规模也给整个图形处理流水线带来了前所未有的挑战。现有的大部分图形处理技术通常需要将所处理的模型一次性地装入内存，所以不能用来处理海量三维模型。因此我们必须研究可以有效地处理海量三维模型的技术。另一方面，不同层次的存储介质(CPU缓存、内存以及硬盘)之间读取速度的差异却在进一步加大，使得数据的输入输出成为超大规模数据处理的最主要瓶颈之一，这就要求所采用的数据处理技术必须针对数据访问的继承性进行优化。这些都促使海量三维模型的外存处理技术(out-of-coretechniquesforgiganticmeshes)成为当今国际图形学界倍受关注的热点研究方向之一。
为了可以在普通计算机上处理任意规模的模型，海量三维模型的外存处理技术必须做到如下两点：保证所需的内存与输入模型规模无关；针对数据的输入输出进行优化，保证数据访问的继承性。实际上，这类技术并不仅限于处理海量三维模型，而是可以适用于任何要求内存消耗尽量少、数据输入输出尽量优化的处理场合。
本文针对海量三维模型的外存处理技术展开深入研究，主要贡献和创新点表现为如下工作：
1.完成了高效的外存表面细节分析算法。已有的依赖于恢复模型连接关系的表面细节分析工具无法有效地处理海量三维模型。本文提出了两种高效的外存表面细节分析工具——细节椭球和交错聚类，均基于统计方式工作，顺序扫描一遍外存模型就可以得到其表面细节分布情况。模型表面由此被划分为角点、细节边、过渡和平坦区域四种类型。
2.完成了高效的自适应空间聚类外存简化算法，既保证了简化结果的高质量，又保持了空间聚类算法的高效性，是国际上最早提出的同类算法之一。空间聚类算法是最高效的外存简化策略之一，但其缺点是简化结果质量相对不高，尤其是基于均匀采样的方法。我们通过自适应采样来解决这个问题。基于表面细节分析结果，对于细节(包括角点、细节边)区域和平坦区域，我们分别提出了高效的进一步细化和进一步简化策略来完成基于空间聚类的自适应外存简化。
3.完成了保流形的高效外存简化算法，既保证简化结果的流形性质，又保持了空间聚类算法的高效性，首次解决了空间聚类算法产生的非流形现象。空间聚类算法不能保证简化结果的流形性质，而大部分后续的处理算法都要求输入模型是流形。我们的解决方法是将空间聚类算法产生的简化结果中的非流形部分分为三类，并且对每一类都提出简单高效的方法转化为流形，从而确保基于空间聚类算法的外存简化技术都可以得到流形的简化结果。
4.完成了首个渐进式外存压缩算法，并且其压缩率已经可以和最好的内存压缩算法相媲美、优于单一分辨率的外存压缩算法。已有的外存压缩算法均是单一分辨率的，渐进式外存压缩技术是一个尚待解决的问题。我们的解决方法是对于海量三维模型进行基于MarchingCubes的重组，对于重组结果基于分块处理方式、用多层次八叉树结构进行层次化组织，而后广度优先遍历该树结构完成外存渐进压缩。
5.探讨了不同的数据读入和内存分配策略对于外存处理技术效率的影响，并给出了对这两种操作的用户透明的动态优化方法。给出的优化方法可以使不同配置的机器都能自动自适应地选用优化的数据读入和内存分配策略，从而进一步提高外存处理技术的效率，具有很强的实用意义。