论文部分内容阅读
近年来,随着三维模型采集设备精度的提高,从现实世界获取的三维模型质量也不断提高。这些高质量的三维模型可以高度真实地保留原物体的全部细节,在文物保护、数字化图书馆、虚拟人计划以及电影游戏等领域得到了广泛应用。但是这些规模急剧增长的三维模型,给绘制、编辑、传输和存储等方面带来了许多新的难题和挑战。三维模型简化是一个减少模型复杂度的有效方法。但是传统的模型简化算法一般需要将要处理的模型完全调入内存,无法直接应用于大型三维模型。为解决该问题,研究者们提出了大型三维模型的外存简化技术(out-of-core simplification),该领域也成为计算机图形学的研究热点之一。现有基于迭代收缩的大型模型简化算法能获得高质量的简化模型,但是其所需的辅助数据结构复杂,计算开销大,简化效率低(以每秒简化的面片个数衡量)。基于点聚类的简化算法简化速度快,更适合大型三维模型。本文采用点聚类简化算法,实现并改进三个基于点聚类的模型简化算法和一个基于视点的多分辨率构建和绘制算法。一、分析、比较了常规模型的简化算法,实现了一个简单高效的基于点聚类的内存(in-core)简化算法。该算法对模型包围盒进行均匀网格划分,采用保持体积的二次误差度量矩阵求取每个格子的最优代表点。该算法的实现为后续大型三维模型简化算法的研究奠定了基础。二、分析、比较了大型模型的简化算法,实现了一种内存容量不依赖于输入模型大小的简化算法,即OoCS算法。但是该算法的输出模型大小依赖于内存容量,如果简化后的模型仍然需要保持比较高的复杂度,则此算法无法满足。为解决这一问题,参照OoCSx算法,本文实现了输入和输出模型大小均不依赖于内存容量的外存简化算法。三、本文设计并实现了一种大型模型的多分辨率构建与绘制算法。该算法基于八叉树空间划分,通过内外存映射技术,构建外存多分辨率层次结构。基于该多分辨率表示,实现了依赖视点的细节层次(LOD)选择和绘制,包括基于视锥的绘制算法、基于背面剔除的绘制算法、基于屏幕覆盖率的绘制算法和基于模型轮廓的绘制算法。我们改进的简化算法提高了简化模型的质量,可以达到每秒50-300k个三角形的简化速度,并且输入和输出模型大小均不依赖于内存容量。实现的基于视点的多分辨率构建和绘制算法,可以满足在普通通用计算机上实时绘制大型三维模型的需求。