刘新国
论文题目：三维几何压缩
作者简介：刘新国，男，1972年10月出生，1997年09月师从于浙江大学彭群生教授，于2001年08月获博士学位。
摘 要
计算机图形学，从它的诞生到现在，已经在许多领域扮演着越来越重要的角色。包括科学探索、工程设计、机械制造、模拟仿真、医药卫生、城市规划、环境保护、文物修复、教育培训、艺术创造、以及游戏娱乐等许多方面。这些应用都涉及对复杂场景的造型，涉及对表示复杂景物外形、颜色、纹理等海量三维几何数据的保存和实时处理。
近年来，随着各种高级造型工具的不断涌现和三维外形扫描数据技术的日益成熟，在很多应用中，人们对几何数据的精度和细节都提出了更高的要求，导致上述三维几何数据的规模和复杂程度急剧增长。庞大的几何数据量对现有的三维图形引擎的处理能力和速度提出了巨大的挑战。此外，随着网络图形学的发展，越来越多地需要通过网络，特别是国际互联网，来存取那些贮放在异地的三维几何数据。这使得本来已经十分有限的网络带宽变得更加紧张。要解决这些由于三维几何数据规模和复杂度的急剧增长所带来的问题，仅仅依靠提高三维图形引擎的处理速度和能力，以及增加网络带宽等硬件方面的措施是不够的。因此，研究新的占用空间小、绘制速度快，适合于计算机网络传输的三维几何数据表示方法具有十分重要的意义。
三维几何数据的常规表示形式是多边形网格，即附着若干属性的多边形的集合。这些属性包括位置坐标、颜色、法线向量以及纹理坐标等。作为一种原始的数据格式，多边形网格可以用几张表格来描述，其中的每一张表格对应着上面的一种属性。虽然那些通用的压缩算法和工具也可以用来减少存放三维几何的数据量，但是效率并不理想，而且通用压缩算法的压缩格式有时候对一些特定的应用来说是不合适的。因此需要为三维几何数据研究专用的压缩算法。
在本文中，一个多边形网格的数据被分割为两部分：第一部分叫做拓扑信息，指多边形网格顶点之间的连接关系；第二部分叫做几何信息，指多边形网格坐标、颜色、法向以及纹理坐标等几何属性。相应地，几何压缩算法也包含两个主要内容：1）拓扑编码；2）几何编码。本文在研究几何压缩算法方面的主要贡献有：
l
以区域增长的方式对网格进行遍历，同时将它分解为一些基本层结构。这些基本层结构很简单，易于进行十分有效地编码。
l
利用几何连贯性，实现对网格坐标的有效压缩。
l
结合已有算法的长处，为任意的三角形网格设计了一个通用的编码算法，该算法可以很容易用来处理多边形网格。
l
设计了两种渐进式的几何传输格式，用于在网络上，特别地在国际互联网上有效地传输和存取三维几何数据。
l
基于光顺思想的顶点预测算法。
l
在本文的渐进式几何传输格式中，要求使用几何模型的多分辨率的表示。为了建立几何模型的这种多分辨率的表示，本文为所提出的两种传输格式分别设计了两个不同的算法：
l
基于体积准则的几何模型简化算法。
l
基于拓扑信息的几何模型简化算法。
几何简化是一个已经研究得相当广泛和深入的课题。有些算法速度非常快，但是简化后的模型并不理想；相反有些算法的简化结果很好，然而速度又太慢。本文所提出的基于体积准则的几何简化算法则处在这两种极端类型的简化算法之间：简化效果相当好，速度也相当快。因此可以将它应用其他的一些领域，如实时显示、细节的多层次控制、多分辨率分析、多分辨率几何编辑/造型等等。
几何光顺是和几何压缩密切相关的研究分支。本文最后在几何光顺方面介绍了三个新算法，而且对几何压缩和几何光顺提出了一个统一研究框架作为未来的研究工作。
关键词：图形学、几何压缩、实体造型、几何光顺、曲面、网格、多分辨率分析、调和分析、几何简化、绘制、数据传输、编码算法。
Abstract
During last decade, computer graphics played an increasingly important role in many fields
including science, engineering, design, manufacturing, medicine, simulation,
environmental protection, training, art and entertainment. These applications
usually involve modeling of complex scene, necessitating huge amount of three-dimensional
geometric data to be manipulated and reserved for various purposes.
Recently, following the rapid development of 3D data acquisition
techniques, in many applications the amount and complexity of three-dimensional
geometric data are growing tremendously due to the need for high accuracy and
rich details in realistic scene modeling. This huge amount of geometric data
put a great challenge on the speed
and efficiency of current graphics engines. On the other hand, there is an increasing
demand of immediately accessing remotely located three-dimensional geometry
data sets through network, the internet in particular, in the development of
Internet Graphics. To meet both the growth in complexity and popularity of three-dimensional
data sets, it will not suffice to only anticipate enhancements in graphics
engines and network bandwidth. Consequently, it is important to develop more efficient
representations for rendering and transmitting three-dimensional geometry data.
In the most common form, three-dimensional geometry data sets are
represented as polygonal meshes, i.e. collections of polygons with their
associated properties, such as location, color, normal vectors, and texture
coordinates. In their raw formats, polygonal meshes are described as data
tables. Each table corresponds to one of the associated properties. Although
general compression algorithms may be used to reduce the amount of bits needed
to represent a polygonal mesh, this reduction is not sufficient enough, and may
not be well suited for some particular applications of computer graphics.
Consequently it is necessary to study in particular the compression algorithms
for three-dimensional geometry data sets.
In the geometry compression approaches presented in this thesis, the
representation of a polygonal mesh is divided into two parts: namely the
topology information, which refers to the connectivity of the vertices in the
mesh; and the geometry information, which refers to the vertex locations and other
attributes including color, normal, texture coordinates etc. Accordingly, our
geometry compression algorithms consist of two major phases: 1) topology
encoding, 2) geometry encoding. The principal contributions on geometry
compression by this thesis include:
l
Traversing the mesh in a region growing
way, and decomposing the topology into layers that are simple enough for
efficient encoding.
l
Exploiting the geometry coherence for
efficient vertex location compression.
l
Two encoding algorithms for general
polygonal meshes, developed by combining successful previous works.
l
A scheme for progressive geometry
transmission over networks, the internet in particular.
In the progressive geometry transmission scheme, a multi-resolution
representation for the transmitted geometry is required. As additional
contributions, two multi-resolution representation construction algorithms are
proposed in this thesis:
l
A volume-based simplification
algorithm.
l
A connectivity-based simplification
algorithm.
Additionally, the volume-based automatic simplification technique provides
an effective compromise between the fastest algorithms, which often produce
poor quality results, and the highest quality algorithms, which are generally
very slow. Many other applications, such as real time display with level-of-detail
control, multi-resolution analysis and geometry modeling may benefit from it.
Fair geometry design and geometry compression are two closely related
research fields in computer graphics. This thesis furthermore describes three
new algorithms on geometry fairing and editing. And a uniform framework for
geometry compression and geometry fairing is proposed as future work.
Keywords: Graphics, Geometry Compression, Solid Modeling, Geometry Fairing, Surface, Mesh, Multi-resolution Analysis, Harmonic Analysis, Geometry Simplification, Rendering, Data Transmission, Encoding Algorithm.
