文档介绍：摘 要
近年来，随着三维模型采集设备精度的提高，从现实世界获取
的三维模型质量也不断提高。这些高质量的三维模型可以高度真实
地保留原物体的全部细节，在文物保护、数字化图书馆、虚拟人计
划以及电影游戏等领域得到了广泛应用。但是这些规模急剧增长的
三维模型，给绘制、编辑、传输和存储等方面带来了许多新的难题
和挑战。三维模型简化是一个减少模型复杂度的有效方法。但是传
统的模型简化算法一般需要将要处理的模型完全调入内存，无法直
接应用于大型三维模型。为解决该问题，研究者们提出了大型三维
模型的外存简化技术（out-of-core simplification），该领域也成为计
算机图形学的研究热点之一。
现有基于迭代收缩的大型模型简化算法能获得高质量的简化模
型，但是其所需的辅助数据结构复杂，计算开销大，简化效率低（以
每秒简化的面片个数衡量）。基于点聚类的简化算法简化速度快，更
适合大型三维模型。本文采用点聚类简化算法，实现并改进三个基
于点聚类的模型简化算法和一个基于视点的多分辨率构建和绘制算
法。
一、 分析、比较了常规模型的简化算法，实现了一个简单高效
的基于点聚类的内存（in-core）简化算法。该算法对模型包围盒进
行均匀网格划分，采用保持体积的二次误差度量矩阵求取每个格子
的最优代表点。该算法的实现为后续大型三维模型简化算法的研究
奠定了基础。
二、 分析、比较了大型模型的简化算法，实现了一种内存容量
不依赖于输入模型大小的简化算法，即 OoCS 算法。但是该算法的
输出模型大小依赖于内存容量，如果简化后的模型仍然需要保持比
较高的复杂度，则此算法无法满足。为解决这一问题，参照 OoCSx
算法，本文实现了输入和输出模型大小均不依赖于内存容量的外存
简化算法。
三、 本文设计并实现了一种大型模型的多分辨率构建与绘制算
法。该算法基于八叉树空间划分，通过内外存映射技术，构建外存
多分辨率层次结构。基于该多分辨率表示，实现了依赖视点的细节
层次（LOD）选择和绘制，包括基于视锥的绘制算法、基于背面剔
除的绘制算法、基于屏幕覆盖率的绘制算法和基于模型轮廓的绘制
I
算法。
我们改进的简化算法提高了简化模型的质量，可以达到每秒
50-300k 个三角形的简化速度，并且输入和输出模型大小均不依赖于
内存容量。实现的基于视点的多分辨率构建和绘制算法，可以满足
在普通通用计算机上实时绘制大型三维模型的需求。
关键字：大型三维网格模型、点聚类、模型简化、外存处理技术、细
节层次化、多分辨率建模、基于视点的绘制
II
Abstract
There has been an fast improvement in the complexity of 3D meshes during
recent years, in part due to the drastic improvements in resolution and accuracy
of data acquisition devices. Because of the extremely high fidelity of these
gigantic meshes, they are applicable in many fields, such as culture heritage
protection, digital museum , virtual human project, movies and video games,
etc. However, rendering, transmitting, editing and storing these gigantic
meshes bring great challenges. An efficient solution to these problems is to
simplify these complex 3D meshes. Traditional mesh simplification methods
are not suitable for these gigantic meshes, because they need to load the whole
original mesh into the main mem