基于变分网格的曲面简化高效算法

基于变分网格的曲面简化高效算法

金勇, 吴庆标+, 刘利刚 (浙江大学数学系,浙江 杭州 310027)

∗

An Efficient Method for Surface Simplification Based On Variational Shape Approximation*

JIN Yong, WU Qing-biao+, LIU Li-gang

(Department of Mathematics, Zhejiang University, Hangzhou 310027, China) + Corresponding author: E-mail: qbwu@zju.edu.cn

Abstract: Providing fast and accurate simplification method for large polygon mesh is one of the most important research focuses in computer graphics. Approximating mesh model with a few polygons can improve the rendering speed, and reduce the storage of the model. The paper presents a local greedy algorithm to minimize the energy defined by variational shape approximation. The algorithm simplifies the mesh by controlling the number of the target polygons, while attempting to get ideal effect by adaptive seed triangles selection. The algorithm has intuitive geometric meaning. The method is efficient enough to be efficiently adopted in the geometric modeling system. Key words: Polygon mesh simplification; variational shape approximation; greedy algorithm; geometric modeling

摘要: 为大型的多边形网格模型提供快速、准确的简化算法是计算机图形学中的一个重要的研究方面.以较少的多边形逼近表示网格模型,能够提高模型的绘制速度,减小模型的存储空间.本文根据变分网格逼近表示所定义的全局误差能量,提出一种局部贪心优化算法,该算法通过控制目标网格分片数来简化网格,通过种子的自适应选取以达到理想的简化效果,具有直观的几何意义.本文方法计算量少,效率较高,能够有效应用于几何造型系统中.

关键词: 多边形网格简化;变分网格逼近;贪心算法;几何造型 中图法分类号: TP391 文献标识码: A

1 引言

三维多边形网格模型,包括三角形网格、四边形网格等,在计算机辅助几何设计、计算机动画、虚拟现实、计算机游戏和医学影像等领域有着大量的应用.随着三维扫描技术的发展,顶点数为数万的模型已经非常常见, ∗ Supported by the National Natural Science Foundation of China under Grant No. 10871178, 60776799 (国家自然科学基金);

Technology Department of Zhejiang Province Grant No. 2008C01048-3(浙江省重大科技创新项目)

作者简介: 金勇(1985－),男,上海人,博士研究生,主要研究领域为数字几何处理和计算机辅助几何设计;吴庆标(1963－),男, 浙江台州人,博士,教授,博士生导师,主要研究领域为图形与图像处理,数值计算方法,高性能并行计算和计算机模拟; 刘利刚(1975－),男,江西吉安人,博士,副教授,博士生导师,主要研究领域为数字几何处理,计算机辅助几何设计,计算机图形学和图像处理.

有的模型顶点数达到数十万甚至更多,所以在网格的多分辨率显示,加速网格着色,网格压缩等过程中需要快速的并且能够保持网格模型细节的网格简化算法.

已有的多边形网格简化技术主要分为以下几种:

(1) 删减(Decimation):Garland等[1]提出一种基于边缩减的网格简化算法,该方法采用网格的顶点到其相关平面的二次距离作为度量,进行边缩减的迭代直到达到目标网格边数为止.类似地,Hoppe等[2]、Klein等[3]、Garland等

[4]

对网格元素提出一种误差度量,其误差度量可以基于顶点坐标、颜色或是纹理坐标来建立,然后对网格元素进

行迭代缩减以简化网格.删减的方法虽然可以得到有效的网格简化效果,但是该类方法得到网格往往存在边度数非常高的顶点,并且由于操作网格的拓扑结构而比较耗时.

(2) 网格精炼(Mesh Refinement): Eck等[5]、Delingette等[6]、Lee等[7]都提出以一个粗网格来逼近表示原始网格模型,然后以各自的策略迭代地在局部进行精炼加密粗网格以达到能够准确表示原始网格模型的精度.

(3) 网格重构(Remeshing):Alliez等[8,9],Gu等[10]提出能够控制目标网格顶点数的网格重构方法,但是这些方法都受限制于网格的参数化,包括大量的计算和数值不稳定性.Valette等[11,12],通过局部的的贪心算法构造近似的 Centroidal Voronoi Diagrams,然后构造CVD的对偶图作为目标简化网格,由于CVD的对偶图是Delaunay三角剖分,所以该方法简化的网格有非常理想的质量,并且该方法不需要对网格进行参数化操作.

(4) 全局优化(Global optimization):Hoppe等[13]提出将网格简化问题视作全局优化问题.以一个能量函数来度量原始网格,同时通过控制网格的顶点数,顶点坐标,和拓扑连接关系以优化定义的能量函数,可以得到保持原始网格模型细节和曲率简化效果.此种方法被推广到同时使用与图像有关的度量来设计能量函数,能量函数不只是和模型的几何性质有关(Lindstorm[14]).

Cohen-Steiner等[15]提出变分网格逼近方法,该方法将原始网格分为目标数量的近似平面簇集,使用与法向有关的能量来度量平面簇集,以Lloyd算法来得到优化的网格分簇,最后每一片分簇以一个多边形表示以得到最终的简化网格.该方法直观有效,简化后的网格模型能够有效保持原始网格的细节,且该算法由于不涉及网格拓扑的修改,使得算法简洁并且有着较好的稳定性.

Cohen-Steiner等[15]提出的变分网格逼近方法有比较理想的视觉效果,然而速度局限于Lloyd算法的迭代次数,Lloyd算法也无法保证得到一个全局最优的结果,并且需要后期处理(合并法向几乎一致的平面簇集)以达到理想的效果.本文主要优化一个与各近似平面簇集的特征法向相关的全局能量,通过离散该全局能量,使得能够使用局部的贪心算法优化该能量;通过初值种子点的自适应选取,可以得到比Lloyd算法更好的效果,本文算法在时间上优于Cohen-Steiner等[15]使用的Lloyd算法,并且不需要后期的近似平面簇集合并处理.

2 变分网格逼近问题

由于三角形网格的广泛应用性,本文基于三角形网格表述算法,该算法可以非常容易的推广到多边形网格.本节约定一些术语并且介绍变分网格逼近的概念.

三角形网格M可以表示为{V,E,F},其中V为网格顶点的集合,E为网格边的集合,F为网格面的集合: V={vi=(xi,yi,zi)∈R3|1≤i≤NV}

E={ei={vi1,vi2},i=1,...,NE} (1) F={fi={vi1,vi2,vi3},i=1,...,NF}

变分网格逼近理论处理将原始网格Μ的网格面片F划分为边连通的近似平面簇集C={Ci⊂F,i=1,...,NC},NC<1,...,NC

一簇Ci中的原始网格面f∈Ci相互关于边连通.当分簇完成后,每一个簇集可以用一个多边形表示,进而可以得到一个逼近原始网格的多边形简化网格.图1表明了变分网格逼近的流程.

2

(a) Original model of bunny, 69451 triangles (a) 原始bunny模型,有69451个三角片

(b) Be partioned into 100 clusters (b) 模型分为100个簇集

(c)The simplified polygonal mesh (c) 由分簇得到的简化多边形网格

Fig. 1 Flow chart of variational shape approximation

图1 变分网格逼近流程图

由上述流程可知,怎样选择网格分簇的策略是变分网格逼近的关键,Cohen-Steiner等

[15]

提出,使用与法向相

关的全局能量作为网格分簇策略中所优化的能量,使得简化后的网格能够更好地逼近原始网格.

定义每一片簇集Ci的特征法向量nCi为该簇集最近似的平面的法向,可如下计算:

⎛⎞

nCi=Unif⎜n(v)dv⎟∫⎜v∈C⎟,

⎠⎝i

其中n(v)为v点的单位法向量,Unif()指对向量的单位化操作运算.

(2)

希望给出一种分簇策略,使得每一个簇集中的所有点与其所对应的簇集特征向量最接近,这样各个簇集都各自最接近于平面.

给定网格Μ={V,E,F},目标分簇数NC, 在对网格的分簇过程中,希望最小化如下度量:

ε(F,C)=

v∈F

∫||n(v)−nC(v)||

i

2

dv, (3)

其中n(v)为v点的单位法向量,Ci(v)为v所属于的簇集,nCi(v)为(2)式定义的特征法向量.

观察(3)式,特征法向量nCi代表与该簇集最近似的平面的法向,将每一点的单位法向量与其所属于的簇集的特征法向量的方差的积分作为误差量,误差量越小,说明每一个簇集中的所有点与其所对应的簇集特征向量越接近,亦即每一个簇集越将法向相近的网格三角片归在一起.从图形的绘制上来分析,同一个簇集中的网格片拥有相近法向则用有着相近的光照效果,有利于用一个多边形来表示一个簇集.

3 算法

给定网格Μ={V,E,F},目标分簇数NC,误差度量ε(F,C),希望找到一个最优的划分Copt,使得

ε(F,Copt)=min{ε(F,C)},其中C为该目标分簇数所对应的所有可能的划分.虽然(2) (3)式给出的簇集特征法向

量和误差度量形式为连续积分形式,但是最终希望得到的还是对于离散的三角形网格Μ的划分.因此,首先给出特征向量nCi和误差度量ε(F,C)的离散形式,然后给出详细的分簇算法.

3

3.1 误差度量的离散和简化

注意到每个三角片f∈F的法向量可以代表该三角片中所有点的法向量,所以各簇集的单位特征法向量

nCi可以离散表示为:

∑ρjnj

⎛⎞⎛⎞Tj∈Ci

nCi=Unif⎜ , (4) ⎜∫n(v)dv⎟⎟=Unif⎜∑ρjnj⎟=

⎝Tj∈Ci⎠||∑ρjnj||⎝v∈Ci⎠

Tj∈Ci

其中Tj为属于簇集Ci的所有三角片,nj为该三角片的单位法向量,ρj为该三角片的面积. 由此,误差度量ε(F,C)可以离散为:

ε(F,C)=

v∈F

∫||n(v)−nC(v)||

i

2

dv

2

⎛⎞ρn∑jjNC−1⎜⎟T∈C

=εd(F,C)=∑⎜∑ρjnj−ji⎟ (5)

||∑ρjnj||⎟i=0⎜Tj∈Ci

⎜⎟Tj∈Ci⎝⎠

εd(F,C)为ε(F,C)的离散形式,我们希望设计一种基于迭代更新各个簇集边界以优化误差度量的算法

(详细见3.2节),在每一步的迭代过程中,我们需要考虑簇控制集边界变化以减小误差度量εd(F,C)的可能性,为

此,需要知道误差度量εd(F,C)在簇集边界变化前后的值,如果以(5)式计算εd(F,C),其复杂度为O(M+N)(M和N为当前簇集边界相邻的两个簇集的三角片个数,这两个簇集对于误差度量的贡献由于特征法向量的变化而会发生变化,需要重新计算),显然时间开销巨大.为此,分析(5)式,得到:

⎛⎜||∑ρjnj||⋅nj−∑ρjnjNC−1

Tj∈Ci⎜Tj∈Ci

εd(F,C)=∑⎜∑ρj

||∑ρjnj||2i=0

⎜Tj∈Ci

Tj∈Ci

⎜⎝

2

⎞⎟⎟⎟ ⎟⎟⎠

⎛∑ρj||∑ρjnj||2||nj||2−2||∑ρjnj||∑ρjnj⋅∑ρjnj+∑ρj||∑ρjnj||2⎞⎜T∈C⎟Tj∈CiTj∈CiTj∈CiTj∈CiTj∈CiTj∈Ci

=∑⎜ji

⎟ 2

||ρn||i=0∑jj⎜⎟Tj∈Ci

⎝⎠

NC−1NC−1i=0

=

∑⎜∑ρj||nj||2−2||∑ρjnj||+∑ρj⎟ (6)

⎝Tj∈Ci

Tj∈Ci

Tj∈Ci

⎛⎞⎠

注意到∀Tj,||nj||=1,则

NC−1i=0

εd(F,C)=∑⎜2∑ρj−2||∑ρjnj||⎟

⎝

Tj∈Ci

Tj∈Ci

⎛⎞

(7)

⎠

我们将可以看到(5)式具有直观的几何意义;重要的是,对于每一个簇集Ci,只需记录一个向量Ni=

Tj∈Ci

∑ρjnj

4

和一个标量Si=

Tj∈Ci

∑ρj,便可以在迭代更新簇集边界时,以O(1)复杂度计算出误差能量εd(F,C).

3.2 局部贪心算法

根据(7)式,我们提出一种迭代更新各个簇集Ci边界的贪心算法.假设网格边e∈E,e的两侧三角形为Tm,Tn,如果Tm,Tn属于不同的簇集,那么称e是一条簇集边界;所有簇集边界的集合为EC,显然EC⊂E.

每一步迭代中,考虑每一条簇集边e∈EC变更以减小ε(F,C)的可能性: 假设e的两侧三角形为Tm,Tn,所属于的簇集分别为Ck,Cl.如图2可以考虑三种变更情况,可以得到三个不同的误差度量:

a)εd(F,Cinit):原始情况:Tm∈Ck,Tn∈Cl

b)εd(F,C1): 将三角片Tn并入到簇集Ck中,Tm∈Ck,Tn∈Ck (8) c)εd(F,C2):将将三角片Tn并入到簇集Ck中,Tm∈Cl,Tn∈Cl

Tm∈Ck,Tn∈Cl

(a) 初始: Tm∈Ck,Tn∈Cl

(a)Initial :

(b)Ckgrows,

Tm∈Ck,Tn∈Ck

(b)Ck增长, Tm∈Ck,Tn∈Ck

(c)

Cl grows,Tm∈Cl,Tn∈Cl (c) Cl 增长,Tm∈Cl,Tn∈Cl

Fig.2 Analysis for modification of local cluster border

图2 局部簇集边界变更分析

取三者之中误差度量εd最小的作为最后的变更结果,然后更新簇集边集合EC.对于簇集边进行迭代更新,可以迭代地减小误差度量ε,直至所有簇集边的变更判断结果为Cinit停止.由于每一步变更都缩小误差度量εd,所以该算法的收敛性能够得到保证.为了保证簇集的连通性,在实际迭代计算中,如果簇集边的变更使得破坏簇集的连通性,则禁止此步变更. 3.3 进一步优化

在实际的计算中,对每一个簇集Ci,只需记录Ni=

Tj∈Ci

∑ρjnj即可.

事实上,当考虑e∈EC的变更可能性时,只有其相关的簇集Ck,Cl的所贡献的误差度量部分可能发生变化.由(7)式,

⎛⎞

ECkUCl=2⎜∑ρj−||∑ρjnj||−||∑ρjnj||⎟

Tj∈CkTj∈Cl

⎝Tj∈CkUCl⎠

(9)

5

在3.2节(8)中的三种簇集边e变更情况中,

Tj∈CkUCl

∑ρj为常量,所以,只需考虑

−

LCkUCl= ||

Tj∈Ck

1

∑ρjnj||+||∑ρjnj||=2⎜ECUC

Tj∈Cl

⎛⎝

kl

Tj∈CkUCl

∑ρj⎟ (10)

⎠

⎞

分别计算Cinit,C1,C2所对应的Linit,L1,L2的值,取L最大的变更情况(即对应误差度量最小)作为最后的变更

结果.L越大对应(7)式中所对应的误差度量εd(F,C)越小,观察(10)式,L为各簇集三角片的以面积为权的法向量和的模,由向量和的性质:一簇相同模长的向量,方向越是相同其向量和越大;所以也可以由此得到优化(7)式即(10)式的几何意义:将具有相近法向量的三角片归于同一个簇集,从而同一簇集的三角片近似属于某一特征平面,这也正是分簇目的所在. 3.4多边形化和三角化

在得到最终的优化簇集划分后,将三个簇集以上的交点可以视为多边形网格顶点,便可以得到一个多边形网格模型,注意此处多边形不一定是平面多边形.如上构造出的多边形边可能无法很好地逼近该簇集的边界,由此可以选择性地对多边形网格作一步后处理:各边迭代细分修正.如果AB为多边形网格的一条边,A、B为相应多边形网格顶点,遍历边AB所对应簇集边界上的所有原始网格顶点,寻找出与边AB距离最远的顶点P和相应的距离d,如果d/||AB||>Thmax(Thmax为给定的容忍极限值),那么将边AB细分为边AP和边PB.

我们还可以将多边形网格分片为三角形网格,可以使用Cohen-Steiner等[15]提出的多边形边校正方法优化和三角化该多边形网格,或是以经典的多边形三角化方法将简化的多边形网格转换为简化的三角形网格.

4 初始化

3.2节给出了更新簇集边以优化误差度量ε(F,C)的局部贪心算法,要设计一个完整的分簇算法,需要一个初始分簇划分,然后实施3.2节的贪心算法优化误差度量ε(F,C)直到收敛为止.如果使用随机的簇集初值划分,不利于算法收敛的速度以及最终的效果,为此本文提出自适应的种子选取和簇集增长方式. 4.1 自适应的分簇初值

注意到以下几个事实:

1) 网格曲率越高的部分应该用较多的多边形去逼近表示,相对地,曲率较低的部分应该用较少的多边形去逼

近表示.

2) 法向几乎相同的三角形应该属于同一个簇集,比如:一个平面应该只有一个簇集.

3) 具有相近法向的三角形在最终分簇更有可能属于同一个簇集,给出一个将相近法向的三角形归在同簇的

初始划分,可以加快3.2簇集边更新算法的收敛速度.

使用Meyer 等[16]对于二维流形三角网格的高斯曲率的估计,对于网格顶点,其高斯曲率为:

κG(v)=(2π−

θj∈Neighbour(v)

∑θj)/Av, (11)

其中θj为顶点v周围的顶角,Av为顶点v的Voronoi区域的面积.三角片的高斯曲率κG(Ti)近似取为其三顶点的高斯曲率绝对值和的平均值,用以反应该三角片曲率的高低.

6

考虑网格分簇问题:网格Μ={V,E,F},目标分簇数NC,为了拥有高曲率的三角片的簇集将归并较少的三角片,拥有低曲率的三角片的簇集将归并较多的三角片.我们预测理想的分簇情况下,每一个簇集的高斯曲率总值应该接近于网格的平均值:

D=

1

∑ρiκG(Ti) NCTi∈F

(12)

4.2 分簇初值的算法

根据4.1节的分析,本节给出分簇初值的算法:

建立每一个簇集Ci时:随机取一个还未归属于任何一个簇集的三角片Tseed作为当前簇集Ci的种子三角片,⎛⎞

循环地更新该簇集边界将还未归属于任何簇集并且与该簇集边相连的三角片以n(T)−Unif⎜∑ρTjnTj⎟为优先

⎝Tj∈Ci⎠

级并入到此簇集中,直到

Tj∈Ci

∑ρjκG(Tj)>D停止并入三角片.为了使几乎属于一个平面的三角片只归入一个簇集

⎛⎞

当中,当簇集停止并入三角形后,仍然可以将n(T)−Unif⎜∑ρTjnTj⎟⎝Tj∈Ci⎠

中.循环上述建立簇集的方法直到建立NC个簇集.至此,得到一个初始簇集划分,实际簇集数NrC可能小于NC,那么直接将NC改为NrC.

得到初始的分簇划分后,可以实现3.2的局部贪心算法:在每一步迭代中,遍历所有的簇集边界e∈EC,如果

e相邻的两三角片之一还未归于任何簇集,那么将其归于另一三角片所属于的簇集;如果两三角片归于不同的簇集,那么执行3.2中提出的变更判断,更新簇集边界EC,直到所有簇集边的变更判断结果为Cinit停止.

5 实例

我们将本文算法试验于多种网格模型,有着较好的视觉效果和较快的速度.与Cohen-Steiner等[15]所提出

的Lloyd算法相比,视觉效果相似或略好,同时本文算法较Lloyd算法有3-4倍的速度优势,且速度优势随模型规模增加而愈加明显,本文同时给出本文算法的例子和一些Cohen-Steiner等[15]算法的例子(Lloyd算法).图3为将

Fandisk模型以30个多边形逼近表示的例子,(a)、(b)为本文算法,(c)、(d)为Lloyd算法,本文算法自适应的将Fandisk底面用一个簇集表示,而Lloyd算法将底面分为了多个个簇集,需要后处理合并这三个簇集.图4图5给出了较大模型Feline和Amodilo的例子,同样地,(a)、(b)为本文算法,(c)、(d)为Lloyd算法,通过表1,可以看到本文算法在大型模型上的速度较Lloyd算法有较大优势.

表1列出了所有示例的详细数据,包括收敛速度和度量误差ε(模型为归一化模型),可以看到本文的算法和度量Lloyd算法最终得到的度量误差非常接近,同时本文算法具有较快的速度.(本文的计算在一台CPU: Intel

Core 2 Duo T7100 内存: 2GB的PC机上完成)

7

(a) (b)(c) (d) Fig.3 Fandisk, which has 12946 triangles, 6475 vertices ,is approximated by 30 polygons;

(a)(b): Algorithm of this paper; (c)(d): Lloyd algorithm

图3 Fandisk,12946个三角形,6475个顶点,以30个多边形逼近表示;

(a)(b): 本文算法; (c)(d): Lloyd 算法

(a) (b)(c) (d)

Fig.4 Feline, which has 99732 triangles, 49864 vertices ,is approximated by 200 polygons

(a)(b): Algorithm of this paper; (c)(d): Lloyd algorithm

图4 Feline,99732个三角形,49864个顶点,以200个多边形逼近表示

(a)(b): 本文算法; (c)(d): Lloyd 算法

(a) (b)(c) (d)

Fig.5 Amodilo, which has 331904 triangles, 165954 vertices ,is approximated by 300 polygons

(a)(b): Algorithm of this paper; (c)(d): Lloyd algorithm

图5 Amodilo,331904个三角形,165954个顶点.以300个多边形逼近表示

(a)(b): 本文算法; (c)(d): Lloyd 算法

Table 1 Parameters of models and results of algorithm

8

表1 模型参数和算法结果

模型

网格面数

顶点数

目标分簇数

算法

图号 图1 图3(a),(b)图3(c),(d)图4(a),(b)图4(c),(d)图5(a),(b)图5(c),(d)

时间(ms)

Bunny Fandisk Feline Amodilo

69451 35947 100 本文算法12946 6475 30 本文算法

596

度量误差ε 0.3898

76 0.0968 181 0.3712 696 0.4781 2357 0.4082 2403 0.4092 8174 0.4172 Lloyd算法本文算法

99732 49864 200 Lloyd算法本文算法

331904 165954300

Lloyd算法

6 结束语

本文提出变分网格逼近的一种改进的高效算法,以分簇数作为控制模型简化比例的参数.Lloyd算法由于受到迭代次数的限制,速度比较慢,本文提出完全不同于Lloyd算法的一种能量优化方式,通过离散基于法向的分簇能量,提出自适应的分簇初值选取和局部贪心优化算法以得到理想的分结果簇,在视觉效果和时间上都要优于Lloyd算法.通过大量试验表明,本文的方法易于实现,并且具有直观的几何意义,可以有效应用于几何造型系统中.

在定义了全局误差度量、划分目标及簇集数后,本文的方法和Lloyd算法都不能保证得到的全局误差度量最小,其分簇结果取决于分簇初值三角形的选取.本文簇集种子的自适应选取可以有效地减少分簇初值对结果的影响,在实际试验中,不同的分簇初值得到的分簇结果在视觉和误差度量上都很接近.

未来的工作包括研究更有效的分簇度量,比如曲率、测地距离,或者以法向、曲率、欧氏距离的组合作为分簇度量等. References:

[1] Garland M, Heckbert PS. Surface Simplification Using Quadric Error Metrics. In: Whitted T, ed. Proceedings of ACM SIGGRAPH.

Los Angeles: ACM Press, 1997. 209-216.

[2] Hoppe H. Progressive Meshes. In: Rushmeier H, ed. Proceedings of ACM SIGGRAPH. New Orleans: Addison-Wesley

Professional, 1996. 99-108.

[3] Klein R, Liebich G, Straßer W. Mesh Reduction with Error Control. In: Yagel R, Nielson GM, eds. Proceedings of IEEE

Visualization. San Francisco: IEEE Computer Society Press, 1996. 311-318.

[4] Garland M, Heckbert PS. Simplifying Surfaces with Color and Texture using Quadric Error Metrics. In: Ebert DS, Rushmeier H,

Hagen H, eds. Proceedings of IEEE Visulaization. Washington: IEEE Computer Society Press, 1998. 263-269.

[5] Eck M, DeRose T, Duchamp T, Hoppe H, Lounsbery M, Stuetzle W. Multiresolution analysis of arbitrary meshes. In: Mair SG,

Cook R, eds. Proceedings of ACM SIGGRAPH. Los Angeles: ACM Press, 1995. 173-182.

[6] Delingette H, Herbert M, Ikeuchi K. Shape representation and image segmentation using deformable surfaces. Image and Vision

Computing, 1992,10(3):132-144.

[7] Lee AWF, Sweldens W, Schröder P, Cowsar L, Dobkin D. Maps: Multiresolution adaptive parameterization of surfaces. In:

Machover C, ed. Proceedings of ACM SIGGRAPH. Orlando: ACM Press, 1998. 95-104.

[8] Alliez P, Meyer M, Desbrun M. Interactive Geometry Remeshing. In: Appolloni T, ed. Proceedings of ACM SIGGRAPH. San

Antonio: ACM Press, 2002. 355-361.

[9] Alliez P, Cohen-Steiner D, Devillers O, Levy B, Desbrun M. Anisotropic Polygonal Remeshing. In: RockWood AP, ed.

Proceedings of ACM SIGGRAPH. San Diego: ACM Press, 2003. 485-493.

9

[10] Gu X., Gortler S, Hoppe H. Geometry Images. In: Appolloni T, ed. Proceedings of ACM SIGGRAPH. San Antonio: ACM Press,

2002. 363-374.

[11] Valette S, Chassery J-M. Approximated Centroidal Voronoi Diagrams for Uniform Polygonal Mesh Coarsening. Computer

Graphics Forum(Proc. Eurographics), 2004,23(3):381-389.

[12] Valette S, Kompatsiaris I, Chassery J-M. Adaptive Polygonal Mesh Simplification With Discrete Centroidal Voronoi Diagrams. In:

Lazzari G, Pianesi F, Crowley JL, Mase Kenji, Oviatt SL, eds. Proceedings of ICMI. Trento: ACM Press, 2005. 655 – 662.

[13] Hoppe H, DeRose T, Duchamp T, McDonald J, Stuetzle W. Mesh Optimization. In: James TK, ed. Proceedings of ACM SIGGRAPH.

Anaheim: ACM Press, 1993. 19-26.

[14] Lindstorm P, Turk G. Image-driven simplification. ACM Transactions on Graphics, 2000,19(3):204-241.

[15] Cohen-Steiner D, Alliez P, Desbrun M. Variational Shape Approximation. In: Marks J, ed. Proceedings of ACM SIGGRAPH. Los

Angeles: ACM Press, 2004. 905-914.

[16] Meyer M, Desbrun M, Schröder P, Barr AH. Discrete Differential-geometry Operators for Triangulated 2-manifolds. In: Hege HC,

Pothier K, eds. Proceedings of Visualization and Mathematics. Berlin-Dahlem: Springer, 2002. 34-57.

附中文参考文献:

[17] 孙家广. 计算机图形学. 第三版, 北京: 清华大学出版社, 1998.

10