题目：大规模三角网格模型处理技术研究

随着3D扫描技术的发展，三维网格模型正成为继声音、图像和视频之后的第四代多媒体数据类型。与此同时，来自娱乐和制造等行业对高分辨率模型的需求导致了大规模网格模型的产生，从而对三维模型处理算法提出了新的要求。近年来，研究者们提出了很多关于大模型处理算法，但这些算法大多面向简化和显示等具体的应用。尽管这些算法很好地满足了某种特定的需求，但我们仍然缺乏一种统一高效的解决方案。大规模网格模型处理算法要解决的是数据量与内存容量严重不匹配的矛盾。在模型处理的任何时候，仅有模型的一部分位于内存中，因此如何快速地获取处理过程中所需要的几何信息和连接信息是外存处理算法的关键问题。本文提出了一个大规模三角网格模型的外存处理框架(Out-of-core Processing Framework, OPF)。OPF的基本思想是按模型元素被处理的顺序，预先在外存中排序，然后再将模型读入内存进行处理。在处理过程中的任何时刻，只有正在被处理的模型元素处于内存中，经过处理不再被用到的元素被清退出内存。对于需要动态改变处理顺序的处理任务，则利用B-树数据结构把模型元素保存到外存，以实现模型元素的查找和调配。OPF的实现主要包含外存排序、拓扑重构、流形辨识和内外存数据交换四个模块。这样，很多大规模网格模型的处理应用都可以在OPF下实现。此外，本文的贡献还包括 利用OPF对大规模三角网格模型进行了分割。三维模型的分割是近年兴起的研究热点之一，出现了众多的算法。但目前几乎所有的算法只能处理中小规模的模型，而对于内存容纳不下的大规模模型则无能为力。鉴于计算机图形学、CAD和计算机视觉等研究领域对模型分割的日益增长的需要，我们在OPF的架构下对外存模型的分割进行了尝试。 为了提高基于点簇聚合的网格简化的质量，研究了点簇聚合的目标顶点位置的计算问题。当计算过程中得到的目标顶点不在小单元之内，或者虽然在小单元之内，但目标顶点的位置不能唯一确定时，则将求解目标顶点的问题转化为求解带约束的二次优化问题。此二次优化问题的解既能保证目标顶点位于小单元之内，在位置上又最接近该点簇的重心。这种方法随后被结合进大规模网格的点簇聚合简化中，用以确定目标顶点的位置。 在OPF的架构下实现了对大规模三角网格模型的简化。为了满足不同简化精度的要求，我们分别采用了边折叠和点簇聚合两种简化方法。由于基于点簇聚合的简化过程仅依赖于几何属性，因此我们只对原模型的元素依空间位置进行排序，然后通过这一顺序引导简化过程。与此不同的是，基于边折叠操作的简化过程依赖于待折叠的边的代价，因此我们在实施简化操作之前先计算边的折叠代价，以折叠代价为关键字排序后，将模型保存到外存，简化的过程实际上是模型元素依照折叠代价的顺序流经内存接受处理的过程。 开发了一个大规模网格模型处理原型系统。该系统在为本论文的实验验证工作提供强大支持的同时，也为我们以后开发真正实用的大规模网格模型处理系统提供了基础。