1
1
第 17 卷 第 11 期
2005 年 11 月
计算机辅助设计与图形学学报
JOURNAL OF COMPU TER
AIDED DESIGN & COMPU TER GRAPHICS
Vol
17 , No
11
Nov
, 2005
三角网格曲面上离散曲率估算方法的比较与分析
方惠兰 王国瑾
(浙江大学计算机图像图形研究所 杭州 310027)
(浙江大学 CAD & CG 国家重点实验室 杭州 310027)
(wgj @math
zju
edu
cn)
摘 要 对国际上近几年提出的三角网格曲面上估算平均曲率的 7 种方法和估算高斯曲率的 4 种方法 ,进行了系统
的总结与大量的实验 ,并给出误差统计和分析比较 ,给出了对高斯曲率和平均曲率的估算效果最优的方法 ,以及较
稳定和误差较小的几个新公式
关键词 高斯曲率 ;平均曲率 ;主曲率 ;三角网格
中图法分类号 TP391
Comparison and Analysis of Discrete Curvatures Estimation Methods for Triangu
lar Meshes
Fang Huilan Wang Guojin
( I nstit ute of Com puter I m ages and Graphics , Zhejiang U niversity , Hangz hou 310027)
( S tate Key L aboratory of CA D & CG , Zhejiang U niversity , Hangz hou 310027)
Abstract The surface representation in discrete form and its differential computation are important issues
in computer graphics and geometric design
This paper gives a detailed review and systematic experimental
comparison of recent 7 mean curvature estimation met hods and 4 Gaussian curvature estimation met hods ,
t heir respective errors statistics are also obtained and analyzed
The best met hod for t he Gaussian and mean
curvature estimation is figured out as well as some new more stable and accurate estimation expressions
Key words Gaussian curvature ; mean curvature ; principal curvature ; triangular mesh
0 引 言
一般来说 ,曲面的一阶微分量是指曲面的切平
面方向和法向量 ,二阶微分量是指曲面的曲率等有
关量
它们作为重要的曲面信息度量指标 ,在计算
机图形学 ,机器人视觉和计算机辅助设计等领域发
挥了重要的作用
传统的曲面是连续形式的参数曲面和隐式曲
面 ,其微分量的计算已经有了较完备的方法
随着
激光测距扫描等三维数据采样技术和硬件设备的长
足进步 ,以及图形工业对任意拓扑结构光滑曲面造型
的需求日益迫切 ,离散形式的曲面 ———细分曲面、网
格曲面和点云曲面正在逐渐成为计算机图形学和几
于是 ,对这种离散形式的曲面如
何设计领域的新宠
何估算微分量 ,就成为一个紧迫的课题
利用近似的
高斯曲率简化网格曲面[1 ] ,利用近似的平均曲率指导
点云曲面去除噪声[2 ] ,就是这种课题重要性的明证
收稿日期 :2004 - 08 - 24 ;修回日期 :2005 - 03 - 17
基金项目 :国家自然科学基金 (60373033 ,60333010) ;国家重点基础研究发展规划项目 (2002CB312101)
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
1
1
1
11 期
Π
方惠兰等 :三角网格曲面上离散曲率估算方法的比较与分析
1052
在这些方法中 ,文献 [ 3
然而 ,经典微分几何并未为我们准备足够的理
论来完成这一课题
近几年来 ,众多学者发表了一
系列文章提出估算离散曲面微分量的新方法 ,其中
单就三角网格曲面而言 ,其离散平均曲率的估算方
法就多达 7 种以上 ;而离散高斯曲率的估算方法 ,多
4 ] 利用 4 次
达 4 种以上
PDE(偏微分方程) 方法 ;文献[ 5
Bel
trami 算子 ;文献[ 8 ]利用 Voronoi 元和有限元方法 ;
文献[ 9
11 ]利用 Normal cycle 理论计算曲面的第二
基本形式 ,在给定顶点的周围选取 1 个小的邻域求
平均值 ;文献[ 12 ]利用张量分析和矩阵特征向量分
析方法
各种方法的理论根据 、近似准则都不相同
文献[ 13 ]中虽对已有方法做了比较和分析 ,但只比
较了早期的几种方法 ,对各种新产生的方法还没有
一个很好的比较和误差分析 ,使得几何设计与图形
工作者面对一系列公式和复杂的三角网格无所适从
7 ]利用 Laplace
本文首先系统地论述了三角网格曲面上对离散
曲率进行估算的各种现有方法的数学思想与原理 ,
在此基础上 ,对估算平均曲率的 7 种方法和估算高斯
曲率的 4 种方法 ,进行了简要的总结与大量的实验 ,
并给出误差统计和分析比较 ;并按比较的结果把这些
方法进行优劣排序 ,指出了 2002 年 Meyer 等[8 ]提出
的 Voronoi 方法对高斯曲率和平均曲率的估算效果最
优 ;同时进一步用加权平均的思想给出了一些更合
理、更稳定以及误差更小的离散曲率估算法
1 离散曲率估算方法的评述
本节中针对近几年来国际上提出的对三角网格
曲面估算离散曲率的各种新方法 ,从数学思想与表
达形式等方面进行系统的归纳与总结
为叙述清楚
起见 ,引入统一的记号
j = 0 表示其 1
K 表示曲面的高斯曲率 , H 表示平均曲率 ,
k
表示法曲率 , k1 和 k2 表示主曲率 , n 表示法向量
考虑三角网格的顶点 pi , { pj} m - 1
邻域内
的顶点的集合 , N ( i) 表示其 1
邻域内顶点的下标
的集合 ,| N ( i) | 表示其顶点的度数 , { T pi
j = 0 表示
包含点 pi 的三角片的集合 , A ( pi ) 表示包含点 pi
的三角片的面积之和
1
1 Moreton 和 Sequin 的方法
j } m - 1
该方法[4 ]的基本思想是利用微分几何的欧拉
定理 ,建立曲面法曲率与曲面主曲率及主方向的关
取点 pi 周围三角面片的各法向量的平均值 , 将
系
其作为三角网格曲面在点 pi 处的法向量 , 记为 n
设 t j 为向量 pipj 在此网格曲面的切平面上的单位
投影 ,则曲面在点 pi 处沿 pipj 方向的法曲率
k j 可近
似地取为过点 pi 和 pj 且在点 pi 有切向 t j 的圆的曲
率 ,即
k j = 2
( pj - pi) ·n
( pj - pi) ·( pj - pi)
设 bx 和 by 为网格曲面的切平面上的一组基 ,
取 t j , x和 t j , y为向量 t j 关于此基的坐标 , ex 和 ey 为
主方向 e1 关于此基的坐标 ;则由欧拉定理 ,有
k j =
K =
T
t j , x
t j , y
·
K ·
t j , x
t j , y
,
ex ey
- ey ex
·
0
k1
0 k2
·
ex ey
- 1
- ey ex
取 i , j = 1 ,2 , …, m ,得到方程组 Ax = b ,其中
A =
x =
t 1 , xt 1 , y
t 2 , xt 2 , y
t 2
1 , x
t 2
2 , x
⁝ ⁝
t 2
m , x
t m , xt m , y
t 2
1 , y
t 2
2 , y
⁝
t 2
m , y
,
x 0
x 1
x 2
=
yk2
e2
xk1 + e2
2 exey ( k1 - k2)
e2
xk2 + e2
yk1
, b =
k1
k2
⁝
k m
因为 x 0 + x 2 = k1 + k2 , 2 x 0 x 2 -
以 H =
x 0 + x 2
2
, K = 2 x 0 x 2 -
x 2
1
2
1
2 对 Laplace
Beltrami 算子离散
x 2
1
2
= k1 k2 , 所
该方法的基本思想是引入了 Laplace
算子Δ = 2 Hn 和曲面的平均曲率流形
种方法离散 ,得到离散值 Δk
Beltrami
其中Δ 用各
M ( pi) ,简记为 Δ( k)
M , k =
Δ( k)
M ·n
2
1 ,2 ,3 ,4 ; 则相应的离散平均曲率为 H =
下面列出Δ 的 4 种离散方法
1
2
1 Taubin 方法
该方法[6 ]中
Δ(1)
j ∈N ( i)
j ∈N ( i)
w ij ( pj - pi)
w ij = 1 的权因子 w ij可由很
M = ∑
其中 ,满足关系式 ∑
多方法确定 ,最简单地可取 w ij = 1
w ij =φ( pi , pj ) ∑
所在的 2 个三角面片的面积和 ,也可以是边 pi pj 的
长度的某个范数 , 如 φ( pi , pj ) = ‖pi - pj ‖α
; 还
| N ( i) | ;也可取
φ( pi , pk) ,φ 可以是边 pi pj
k ∈N ( i)
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
1
2052
2
1
1
计算机辅助设计与图形学学报
1
2005 年
5
( cotαij + cotβij ) , αij , βij 分 别 为
1
2
可以取 w ij =
∠pi pj - 1 pj , ∠pi pj + 1 pj
1
2
2 Mayer 方法
设方 法[ 6 ] 的 基 本 思 想 是 利 用 Green 公 式 得
∫D
Δf ( x) d x =∫
f ( s) , d s 分别离散为
D
f ( s) ds ;将此公式中的∫D
Δf ( x) d x ,
Δf ( pi) A ( pi) ,
f ( pj) -
‖pj - pi ‖ 和
‖pj - 1 - pj ‖ + ‖pj +1 - pj ‖
;
f ( pi)
2
再取 f ( x ) = x ,就可以得到
Δ(2)
M =
1
A ( pi) ∑
j ∈N1 ( i)
‖pj - 1 - pj ‖+ ‖pj +1 - pj ‖
2
pj - pi
‖pj - pi ‖
2
1
3 Desbrun 等方法
该方法[7 ]的基本思想是对微分几何中的平均
=Δ 离散化 , 其中 A
曲率流形的公式 lim
为点 p 周围的一个小邻域的面积 ,Δ 为点 p 处的关
于点 ( x , y , z ) 的梯度算子
diam( A ) →0
3Δ A
2 A
即先求得面积
1
2 [ ‖pj - pi ‖2 ‖pj +1 - pi ‖2 -
A ( pi) = ∑
j ∈N ( i)
( pj - pi , pj +1 - pi) 2 ]
1
2 ;
从而
cotαij + cotβij
( pj - pi)
Δ(3)
M =
3
A ( pi) ∑
2
1
j ∈N ( i)
2
4 Meyer 等的 Voronoi 方法
该方法[8 ]的基本思想是把光滑曲面看作是一
族网格的极限或者线性逼近 , 把三角网格每个顶点
的度量性质看作是此空间网格在此点一个小邻域的
1
A∫∫A
Δd A
平均 度 量 Δ = 2 Hn =
对 面 积 A =
A M ( pi) 的离散取法是 :对锐角三角形 ,取三角形的外
心连接除点 pi 对边以外另两条边的中点 ,得到新的
面积 A acute ;对钝角三角形 ,是把钝角对应边的中点和
另两条边的中点相连 ,得到面积 A obtuse ;对任意的三
角网格 ,则是用以上 2 种方法求得整个的混合面积
A M
由 Laplace
Δu , vd ud v
Beltrami 算子的性质 ,有∫∫A M
再利用高斯定理 ,得∫∫A M
Δu , vd ud v =
Δd A =
Δ u , v ·nu , vd l
于是应用上面的面积定义和第
∫∫A M
∫
A M
1
2
1 节中αij和βij ,即可得到
Δ(4)
M =
1
A M ( pi) ∑
j ∈N ( i)
cotαij + cotβij
2
( pj - pi)
然后 ,用θj 表示边 pipj 与 pipj + 1的夹角 ,应用微分几
何中的 Gauss
Bonnet 定理 ,有∫∫A
Kd A = 2π - ∑
θj
j
于是 ,同样利用上述的离散方法 ,可得
2π - ∑
θj
j
A
K =
1
3 Dyn 和 Hormann 的方法
在三角网格中 , 定义两端点 pi 和 pj 的边 ej =
pj - pi ,两边 ej , ej + 1的夹角为 αj = ∠( ej , ej + 1) , 两
边 pi pj , pj pj + 1的夹角为λj ,两边 pi pj + 1 , pj pj + 1的夹
角为 γj
再记边 ej , ej + 1 所围成的三角形 pi , pj ,
×
pj + 1为 T j ,其单位法向量为 nj =
ej ×ej + 1
‖ej ×ej + 1 ‖
定
义 2 个相邻面片 T j - 1和 T j 的法向量之间的夹角为
βj = R ( nj - 1 , nj)
对具有公共边 ej 的每 2 个三角形 T j - 1 和 T j
作 1 个内切的小柱面 , 这样整个三角网格曲面就由
一系列小柱面拼成的光滑曲面来近似代替
因此 ,
直接由微分几何中的定理可得离散高斯曲率和离散
平均曲率的算式[9 ]
2π - ∑
αj
n
K =
A
j
, | H | =
1
4 A ∑
j = 1
‖ej ‖| βj |
其中 , A = ∑
锐角 ,右图 pi 为钝角
i
S pi , S pi 如图 1 所示 ,其中左图 pi 为
图 1 S pi为 △pi pj pj + 1中一小块面积
当 T j 为锐角三角形时 ,
S pi =
1
8 { ‖pi pj +1 ‖2cotλj + ‖pj pj +1 ‖2cot γj}
当αj 为钝角时 ,
1
8
S pi
‖pj pj +1 ‖2tanλj ,
S pj +1 =
1
8
‖pi pj ‖2tanγj ,
S pi = SΔpipjpj +1 - S pj - S pj +1
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
1
1
1
1
方惠兰等 :三角网格曲面上离散曲率估算方法的比较与分析
1
3052
1
11 期
1
4 Cohen
Steiner 和 Morvan 的方法
对网格上每个顶点 pi , 取 pi 周围的一个 Borel
集 B [10 ] ,定义
Epi ( B ) =
1
| B |
∑
β( e) ‖e ∩ B ‖
e T ·
e
e ∈β
其中 ,| B | 为 B 的面积 , e 为 B 中网格的边 ,
e 为 e
方向上的单位向量 ,β( e) 是以 e 为公共边的 2 个三
角形法向的夹角 , Epi ( B ) 的最小特征值的特征方向
可作为顶点 pi 处网格曲面的法向量的估计式
特
征值 k min和 k max可分别作为主曲率 k1 和 k2 ,于是平
均曲率和高斯曲率就可以直接由主曲率来求得
2 离散曲率估算方法的实验与比较
2
1 实验方案的设计思想
为了比较第 1 节中所列的各种离散曲率估算方
下面分 3 个
法的优劣 ,我们设计了一个实验方案
方面阐述方案的设计思想
1) 计算离散曲率的曲面模型的生成过程具有
离散成三角
常用连续型参数曲面; b
以下 3 步 :a
随机小扰动网格顶点得到一般三角网
网格曲面 ;c
格曲面
这里离散曲面的片数为 (10 n) ·(10 n) , n =
1 ,2 , …为离散的序号 , 即对原始曲面的 2 个参数区
间各细分为 10 n 份 , 以产生相应的三角网格 , 再变
动这一网格
这样做的理由是 :对连续性的参数曲
面 ,其高斯曲率或平均曲率可由微分几何中的标准
公式精确算得
随机小扰动参数曲面的离散网格顶
点以后 ,这些顶点已不在原参数曲面上 ,因而三角网
格曲面在其顶点处的离散曲率的理想值不等于扰动
前参数曲面在此点处的精确曲率
不过因扰动幅度
较小 ,两者数值应当相差不大
这样 , 对同一网格顶
点处离散曲率的 2 个估算方法而言 , 离散曲率与精
确曲率之间数值差别较小的那个估算方法较好
不
但如此 ,随着离散网格的密化 ,网格顶点扰动所产生
的位置误差将不断缩小 ,因而 ,由任一离散曲率估算
公式所得到的计算值将与原连续曲面在此点的精确
曲率值无限靠近
靠近速率越快 , 这个公式就越精
确
我们只要画出离散曲率的计算值对于离散序号
n 的函数曲线 ,就可比较各种估算方法的优劣
2) 原始连续型参数曲面的选取标准涵盖以下 3
类 : 抛物型 ,椭圆型 ,双曲型
离散曲率的各种估算方法产生于不同的数学背
景 ,因而对曲面上点的不同类型 ,其敏感程度是不一
换言之 , 某种估算方法对抛物型点的离散曲
样的
率估算可能误差较小 , 而对椭圆型点或双曲型点的
离散曲率估算误差却可能较大
因此 , 要分别选取
具有抛物点
双曲点的各类连续型参数曲面
作为原始曲面 ,对离散曲率的估算方法进行全面比
较 ,才不致有失偏颇
椭圆点
在本次实验中 ,我们选取了抛物型参数曲面 :
柱面 x 2 + y2 = 400
锥面 x 2 + y2 = 40 z 2
(1)
(2)
椭圆型参数曲面 :
球面 x 2 + y2 + z 2 = 400
椭圆抛物面 y2
16
双叶双曲面 8 x 2 + 3 y2 - ( z - 10) 2 = - 4
+ x 2
16
= z
(3)
(4)
(5)
(6)
双曲型参数曲面 :
单叶双曲面 x 2
8
-
+ z 2 = 40
y2
3
y2
8
-
x 2
4
(7)
双曲抛物面 z =
3) 网格顶点随机扰动的次数与效果
对网格顶点的扰动虽是随机的 , 但由一次偶然
的扰动所产生的相应估算结果却不足以真切地反映
该估算方法的实质
只有对网格顶点进行多次随机
扰动 ,把所产生的相应的离散曲率估算值加以平均 ,
才能体现该估算方法的效果
在本次实验中 ,我们把
每张原始曲面网格顶点的随机扰动次数取为 m = 8
2
2 实验方案的实施及结果
我们首先把每张原始连续型参数曲面都离散成
由(10 n) ·(10 n) 张三角面片所组成的三角网格曲
面 , n = 1 ,2 , …; 对每个固定的离散次数 n , 我们都
随机扰动其网格顶点 m ( m = 8) 次 , 把 8 次扰动所
产生的相应的离散曲率估算值的平均值作为离散曲
率估算值 ;对每张原始参数曲面的离散网格曲面 ,我
们都用估算平均曲率的 7 种方法和估算高斯曲率的
4 种方法进行计算
为节省篇幅 ,本文中省去了离散
曲率的计算值对于离散序号 n 的函数曲线 ,而代之
以某个固定网格点上离散曲率偏离精确曲率值的绝
对误差 (纵坐标) 对于离散序号 n (横坐标) 的各种误
差曲线 ,再把网格曲面上多个固定网格点的误差曲
线加以平均 ,分别画在同一张图上
需要说明的是 ,
本文画出的是绝对误差曲线 , 而不是可正可负的误
差曲线 ,只是为了眉目清楚便于比较 ,否则曲线犬牙
图 2~8 是估算离散平均曲率的误
交错 ,难以辨别
差曲线比较图
同样 , 我们可画出估算离散高斯曲
率的误差曲线比较图 , 为节省篇幅 , 此处从略
其中
每个图右边的曲线类型的数码系指对应的估算方法
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4052
计算机辅助设计与图形学学报
2005 年
为有确切的数量概念 , 表 1 和
所在的本文小节号
表 2 给出了每个曲面上取 2 万个采样点时各个方法
所对应的最大误差比较
1 节方法时 ,其权因
必须指出 ,本文使用第 1
2
| N ( i) | ;本文使用方
子的取法系应用公式 w ij = 1
4 时 ,其 Borel 集的取法 ,首先是取包含点 pi 的
法 1
所有三角形 ,再取往外辐射一周的所有三角形
在编
程实现时 ,使用了网格三角形的边的链表搜索方法
图 5 椭圆抛物面的离散平均曲率估算的误差比较
图 2 柱面的离散平均曲率估算的误差比较
图 6 双叶双曲面的离散平均曲率估算的误差比较
图 3 锥面的离散平均曲率估算的误差比较
图 7 单叶双曲面的离散平均曲率估算的误差比较
图 4 球面的离散平均曲率估算的误差比较
图 8 双曲抛物面的离散平均曲率估算的误差比较
表 1 估算离散平均曲率的各种方法的最大误差比较
%
抛物型
椭圆型
双曲型
(1) 柱面 (2) 锥面 (3) 球面 (4) 椭圆抛物面 (5) 双叶双曲面 (6) 单叶双曲面 (7) 双曲抛物面
0
8
1
3
3
6
22
9
26
7
30
5
51
4
0
9
3
4
4
8
8
9
9
0
38
1
45
2
0
4
4
8
8
7
12
4
8
4
60
4
1
1
0
12
0
78
3
46
18
2
13
1
64
7
0
19
2
9
5
8
10
2
31
7
23
9
59
8
10
6
3
7
4
9
10
7
20
9
16
1
86
1
0
88
5
3
7
9
32
8
15
6
75
3
184
6
131
4
方法
方法 1
2
4
方法 1
1
方法 1
2
3
方法 1
2
1
方法 1
2
2
方法 1
方法 1
4
3
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
1
1
1
1
1
1
11 期
1
1
v
方惠兰等 :三角网格曲面上离散曲率估算方法的比较与分析
表 2 估算离散高斯曲率的各种方法的最大误差比较
5052
%
方法
4
方法 1
方法 1
方法 1
方法 1
2
3
1
4
抛物型
椭圆型
双曲型
(1) 柱面 (2) 锥面 (3) 球面 (4) 椭圆抛物面 (5) 双叶双曲面 (6) 单叶双曲面 (7) 双曲抛物面
6
7
52
3
9
6
3
5
9
9
64
0
5
2
1
9
8
3
113
93
2
6
5
8
11
5
106
96
6
4
2
7
60
35
141
122
1
6
0
6
8
9
122
103
3
7
6
8
10
13
112
105
2
6
5
2
由图 2~8 与表 1 分析可知 ,估算平均曲率的 7
种方法 ,其精确程度由高到低的排序如表 3 所示 ;由
各方法相应的图与表 2 分析知 , 估算高斯曲率的 4
种方法 ,其精确程度由高到低的排序如表 4 所示
表 3 估算离散平均曲率的各种方法精确程度排序
曲面
方法 1
2
4 方法 1
1 方法 1
2
3 方法 1
2
1 方法 1
2
2 方法 1
4
方法 1
3
抛物型 (1) 柱面
(2) 锥面
椭圆型 (3) 球面
(4) 椭圆抛物面
(5) 双叶双曲面
双曲型 (6) 单叶双曲面
(7) 双曲抛物面
1
1
1
1
1
1
1
2
2
3
3
3
2
2
3
3
4
4
4
3
3
4
4
6
6
6
5
5
5
5
5
5
5
4
4
6
6
7
7
7
6
6
7
7
2
2
2
7
7
表 4 估算离散高斯曲率的各种方法精确程度排序
2
3 计算稳定且误差较小的新公式的提出
曲面
方法
1
2
4
方法
1
3
方法
1
1
方法
1
4
抛物型 (1) 柱面
(2) 锥面
椭圆型 (3) 球面
(4) 椭圆抛物面
(5) 双叶双曲面
双曲型 (6) 单叶双曲面
(7) 双曲抛物面
3
3
2
2
2
1
1
2
2
1
1
1
2
2
4
4
3
3
3
3
3
1
1
4
4
4
4
4
从表 3 可以看出 , 三角网格曲面的离散平均曲
率的误差有正有负 , 且在代表理想值的精确曲率值
的零误差曲线附近上下振荡
由数理统计理论可
知 ,各种估算方法所对应的绝对误差曲线其振荡的
波峰波谷必不同步 ,且振荡幅度互有参差 ;但若以加
权平均的方式进行迭加 , 则一般情况下波峰会被削
低 ,波谷会被填高 , 新误差曲线的振幅将会减小 , 且
振荡趋于稳定
所以 , 我们提出一些新公式来估算
平均曲率 ,这些公式将更精确且更稳定
总之 ,当用本文总结的方法估算三角网格曲面
的平均曲率时 ,各方法效果的优劣排序为
1
2
2
2
3 ;
1 ,1
4 ,1
2 ,1
3 ,1
4 ,1
2
3 节与第 1
2
4 节方法的效果最优
1 ,1
2
其中第 1
其次 , 当用本文
总结的方法估算三角网格曲面的高斯曲率时 , 对双
4 节的效果为最优 ;对椭圆型曲
曲型曲面 ,以第 1
4 节的方法的效果为最优
面 ,以第 1
4 节与第
(两者区别不大) ;对抛物型曲面 ,则以第 1
因此 ,
1
我们的结论是 :文献[8 ]的 Voronoi 方法对估算三角
网格曲面的各种曲率效果最优 , 这是一个普遍适用
的好方法
4 节的方法的效果最优 (两者区别不大)
2
2
( l)与 H (2)
k
本文前述的估算平均曲率的两种较好方法中 ,
假设其计算公式分别记为 H (1) 与 H (2) ,其曲率值对
于离 散 序 号 l = 1 , 2 , …, n 的 函 数 曲 线 分 别 为
H (1)
( l ) , 其中 k 为网格顶点的扰动序
k
号 , k = 1 ,2 , …, m , i ≠j , i , j = 1 , 2 , …, 7
例如 , 对
双曲型曲面 ,取 H (1)
1 节与
( l) 为第 1
2
k
第 1
3 节的离散曲率函数曲线 , 则由此 2 种方法
可生成一个新方法为
∑
( l) 与 H (2)
k
H (2) +
H =
( l)
2
m
n
H (1)
k
( l) + H (2)
k
H (2)
k
( l) + H (2)
k
( l)
( l)
( l)
H (1)
(8)
H (1)
k
k = 1
1
m n ∑
1
∑
m n ∑
l = 1
m
n
k = 1
l = 1
H (1)
k
或者
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
Π
Π
2
1
1
1
1
1
1
1
2
1
1
1
1
1
2
Π
1
1
2
2
2
2
2
2
2
1
1
1
1
计算机辅助设计与图形学学报
2005 年
6052
~ ~
H
=
n
n
0
( l) d l
∫
H (1)
k
( l) d l +∫
H (2)
k
∫
H (2)
k
( l) d l +∫
H (2)
k
( l) d l
0
0
n
n
0
H (2) +
( l) d l
H (1)
(9)
( l) d l
m
1
m ∑
k = 1
n
∫
H (1)
k
0
m
1
m ∑
k = 1
n
∫
H (1)
k
0
2
运用式 (8) 和式 (9) ,我们重新估算了几种曲面
的平均曲率 ,并与最好的第 1
4 节方法作了比较 ,
其结果如图 9~12 所示
从图中可看出 ,其误差更
小
同样 ,我们可提出对高斯曲率估算的改进公式
关于离散形式的曲面上曲率的估算 ,目前已出
15 ] 直接估计主曲
现一个新的趋势 ,即有文献 [ 14
率 ,而避开了高斯曲率或平均曲率的计算
但由于
篇幅所限 ,我们对此种研究将另文讨论 ,所采取的方
法将是把离散曲面的曲率线计算与主曲率估计合在
一起展开研究
图 9 单叶双曲面的离散平均曲率估算
方法改进前后的误差比较
图 12 柱面的离散平均曲率估算
方法改进前后的误差比较
参 考 文 献
[ 1 ] Garland M , Heckbert P S
Surface simplification using quadric
error metrics [ A ]
In : Computer Graphics Proceedings , Annual
Conference Series , ACM SIGGRAPH , Los Angeles , 1997
209~216
[ 2 ] Zhang Hao , Fiume E
Mesh smoothing with shape or feature
preservation [ A ]
In : Advances in Modelling , Animation and
Rendering , Bradford , 2002
Schneider R , Kobbelt L
[ 3 ]
167~182
Geometric fairing of irregular meshes
for free
form surface design [J ]
Design , 2001 , 18 (4) : 359~379
Computer
Aided Geometric
[ 4 ] Moreton H P , Sequin C H
Functional optimization for fair sur
face design [J ]
In : Computer Graphics Proceedings , Annual
Conference Series , ACM SIGGRAPH , Chicago , Illinois , 1992
167~176
Taubin G , Kobbelt L
Geometric signal processing on large
[ 5 ]
polygonal meshes [ A ]
In : Computer Graphics Proceedings ,
Annual Conference Series , ACM SIGGRAPH , Los Angeles ,
California , 2001
Course 17
[ 6 ] Mayer U F
three space dimensions [ OL ]
Numerical solutions for the surface diffusion flow in
~
http :/ / www
math
utah
edu
mayer
math
Mayer07
pdf , 2001
[ 7 ] Desbrun M , Meyer M , Schroder P , et al
Implicit fairing of ir
regular meshes using diffusion and curvature flow [ A ]
In :
Computer Graphics Proceedings , Annual Conference Series ,
317~324
Discrete differential
ACM SIGGRAPH , Los Angeles , California , 1999
[ 8 ] Desbrun M , Meyer M , Schroder P , et al
图 10 双曲抛物面的离散平均曲率估算
方法改进前后的误差比较
图 11 椭圆抛物面的离散平均曲率估算
方法改进前后的误差比较
geometry operators for triangulated 2
manifolds [ A ]
In : Visu
alization and Mathematics , Berlin , 2002
52~58
[ 9 ] Dyn N , Hormann K , Kim S J , et al
Optimizing 3D triangula
tions using discrete curvature analysis [ A ]
In : Applied Mathe
matics Series Archive Mathematical Methods for Curves and
Surfaces , Oslo , 2000
135~146
[ 10 ] Cohen
Steiner D , Morvan J M
Restricted Delaunay triangula
tions and normal cycle [ A ]
In : Proceedings of the 19th Confer
ence on Computational Geometry , San Diego , California , 2003 ,
53 : 312~321
[ 11 ] Alliez P , Cohen
Steiner D , Devillers O , et al
Anisotropic
polygonal
remeshing [J ]
2003 , 22 (3) : 485~493
ACM Transactions on Graphics ,
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
2
1
1
2
2
2
1
1
2
ΠΠ
1
1
1
1
1
方惠兰等 :三角网格曲面上离散曲率估算方法的比较与分析
7052
方惠兰 女 ,1981 年生 ,硕士 ,主要研
究方向为计算机图形 、计算机辅助几何设
计等
王国瑾 男 ,1944 年生 ,教授 ,博士生
导师 ,主要研究方向为计算机辅助几何设
计 、计算机图像图形 、数字几何处理 、离散
微分几何等
11 期
[ 12 ] Taubin G
Estimating the tensor of curvature of a surface from a
polyhedral approximation [ A ]
In : Proceedings of the 5th Inter
national Conference on Computer Vision , Washington , DC :
IEEE Computer Society , 1995. 52 : 902~907
[ 13 ] Tatiana S , Evegeny M , et al
A comparison of Gaussian and
mean curvatures estimation methods on triangular meshes [ A ]
In : Proceedings of the 2003 IEEE International Conference on
Robotics and Automation , Taipei , 2003
1021~1026
[ 14 ] Chi
Keung T , Gearard M
Curvature
augmented tensor voting
for shape inference from noisy 3D data [J ]
IEEE Transactions
on Pattern Analysis and Machine Intelligence , 2002 , 24 ( 6) :
858~864
Page D L , Koschan A , Sun Y , et al
Robust crease detection
[ 15 ]
and curvature estimation of piecewise smooth surfaces from tri
angle mesh approximations using normal voting [ A ]
In : Pro
ceedings of the International Conference on Computer Vision and
Pattern Recognition , Kauai , Hawaii
2001
162~167
全国第 17 届计算机科学与技术应用学术会议征文通知
( CACIS·2006 第一轮)
中国仪器仪表学会微型计算机应用学会 (简称 CACIS) 长期致力于计算机科学与技术的研究与应用推广工作 ,尤其致力
于计算机科学在仪器仪表中的应用 ,微机应用学会的工作年会已成为全国信息学科相关专业互相渗透和交流的重要平台
全
本届会议将聚集国内
国第 17 届计算机科学与技术应用学术会议 (CACIS·2006) 将于 2006 年 7 月 16 —20 号在山西太原举行
知名专家学者 ,交流有关计算机理论与应用的研究成果和实践经验 ,探讨仿真计算应用的领域重点和挑战性问题
会议一如
既往 ,由中国科学技术大学出版社正式出版《计算机技术与应用进展·2006》论文集 ,符合学报要求的参会论文将分别由《计算
机辅助设计与图形学学报》、《系统仿真学报》、《工程图学学报》年内正刊出版 ,欢迎新老朋友投稿 、参会
主办单位 :中国仪器仪表学会 (CIS)
中国仪器仪表学会微型计算机应用学会 (CACIS)
中国系统仿真学会复杂系统仿真与计算专业委员会筹备处 (CSSC)
承办单位 :太原科技大学 、合肥工业大学
协办单位 :《计算机辅助设计与图形学学报》、《系统仿真学报》、《工程图学学报》
会议地点 :山西 太原 太原科技大学
征文主题 : (包括但不局限于)
·仪器仪表及其应用 ·复杂系统仿真与计算 ·多媒体与图像处理
·数据库与系统集成
·人工智能与数据挖掘
·网络与安全
·可视化与虚拟现实
·其他相关理论与技术
出版论文 :《计算机技术与应用进展·2006》中国科技大学出版社出版
重要日期 : 截稿日期 :2006 年 2 月 15 日 (即日起接受投稿)
录用通知 :2006 年 3 月 15 日后陆续发出
会议日期 :2006 年 7 月 16 日报到 ,7 月 17 —20 日会议
注意事项 : 会议论文必须符合学报的规范要求 ,包含中英文标题 、作者 、单位 、摘要 、关键词等 ,文责自负
·软件工程
·计算机辅助设计与制造
为加速稿件处理
作者信息单独一页提供 ,包括论文题目 、作者全名 、所属单位 、邮政编码 、通信
速度 ,会议论文优先受理 MS
地址 、电话 、电子邮件及论文关键词
WORD 格式版本
论文中英文均可 ,字数原则上不超过 5000 字
com ;paper @ah163
com ;
mail :papers @ah163
提交方式 : E
业务咨询 :通信地址 :230009 合肥工业大学 52 信箱 微型计算机应用学会
联系电话 :0551
传 真 :0551
2901380 (杨孙梅 、李琳 、余烨) ; 0551
2904642 学会网址 :http :
2901701 (刘晓平)
cacis
hfut
edu
cn
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net