基于变分网格的曲面简化高效算法?
金勇, 吴庆标+, 刘利刚
(浙江大学数学系,浙江杭州 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@https://www.doczj.com/doc/889108140.html,
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－),男,江西吉安人,博士,副教授,博士生导师,主要研究领域为数字几何处理,计算机辅助几何设计,计算机图形学和图像处理.
2
有的模型顶点数达到数十万甚至更多,所以在网格的多分辨率显示,加速网格着色,网格压缩等过程中需要快速的并且能够保持网格模型细节的网格简化算法.
已有的多边形网格简化技术主要分为以下几种:
(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 为网格顶点的集合,为网格边的集合,为网格面的集合: ,}V E F E F 3{(,,)|1i i i i V V v x y z R i N ==∈≤≤}}F
12{{,},1,...,i i i E E e v v i N === (1) 123{{,,},1,...,}i i i i F F f v v v i N ===
变分网格逼近理论处理将原始网格的网格面片划分为边连通的近似平面簇集,ΜF {,1,...,}i C C F i N =?=C C N N <<的问题,其中1,...,C F C
i N =U ,,,j i j C C i ∩=??,C N 用以控制网格的简化比例,每
一簇i C 中的原始网格面i f C ∈相互关于边连通.当分簇完成后,每一个簇集可以用一个多边形表示,进而可以得到一个逼近原始网格的多边形简化网格.图1表明了变分网格逼近的流程.
(b) Be partioned into 100 clusters 3
由上述流程可知,怎样选择网格分簇的策略是变分网格逼近的关键,Cohen-Steiner 等
[15]
提出,使用与法向相
关的?
(2)
其中为点的单位法向量)指对向量的单位化操作运算.
望给出得每一的簇集特征向量最接近,这样各个簇集都各自目标分簇数全局能量作为网格分簇策略中所优化的能量,使得简化后的网格能够更好地逼近原始网格.
定义每一片簇集的特征法向量为该簇集最近似的平面的法向,可如下计算:
i C i C n ()i i
C v C n Unif n v dv ∈??
=?????∫,()n v v ,(Unif 希一种分簇策略,使个簇集中的所有点与其所对应最接近于平面.
给定网格{V Μ=,,}E F ,C N , 在对网格的分簇过程中,希望最小化如下度量:
(3)
其中单位法向量所属于式表与量与其所属于的簇集的特越接近,亦即每一个簇集越将法向相近的网格三角片归在一起.从图形的绘制上来分析,同一个簇集中的网格片格目标分簇数 (||()i
C v n v n dv ∈?∫, 2
)(,)||
v F
F C ε=
()n v 为v 点的的簇集,()i C v n 为(2)式定义的特征法向量.
,()i C v 为v 观察(3),特征法向量i C n 代该簇集最近似的平面的法向,将每一点的单位法向征法向量的方差的积分作为误差量,误差量越小,说明每一个簇集中的所有点与其所对应的簇集特征向量拥有相近法向则用有着相近的光照效果,有利于用一个多边形来表示一个簇集.
3 算法
给定网{,,}V E F Μ=,C N ,误差度量(,)F C ε,希望找到一个最优的划分使得
opt C ,(F ,)min{opt C (,)}F C εε,其中形式为连续积和误差度量=C 为该目标分簇数所对应的所有可能的划分.虽然(2) (3)式给出的簇集特征法向
分形式,但是最终希望得到的还是对于离散的三角形网格Μ的划分.因此,首先给i C 量和误差度量出特征向量n (,F C )ε的离散形式.
,然后给出详细的分簇算法(b) 模型分为100个簇集
(a) Original model of bunny, 69451 triangles (c)The simplified polygonal mesh ( chart rox (a) 原始bunny 模型,有69451个三角片
c) 由分簇得到的简化多边形网格
Fig. 1 Flow of variational shape app imation
图1 变分网格逼近流程图
4
量的离
注意到每个三角片3.1 误差度散和简化f F ∈的法向量可以代表该三角片中所有点的法向量,所以各簇集的单位特征法向量
i C n 可以离散表示为:
()n Unif n ?=?∫||||j i
i j i i j i
j j
T C C j j T C v C j j T C n v dv Unif n n ρρρ∈∈∈∈???==
?????????
∑∑∑ , (4) 其中j T 为属于簇集的所有三角片i C ,j n 为该三角片的单位法向量,j ρ为该三角片的面积. (,)F C ε由此,误差度量可以离散为:
2
()(,)||()||
i
C v v F
F C n v n dv ε∈=
?∫
2
10(,)||||C j i j i
j i j j N T C
d j j i T C j j T C n F C n n ρερρ?∈=∈∈????==?????????
∑∑∑∑ (5)
(,F C )d ε为(,)F C ε的离散形式,我们希望设计一(详细见在每一步的迭代过程中,我们需要考虑簇控制集边界变化以减小误差度量种基于迭代更新各个簇集边界以优化误差度量的算法
3.2节),(,)d F C ε的可能性,为
此,需要知道误差度量d (,)F C ε在簇集边界变化前后的值,如果以(5)式计算(,)d F C ε,其复杂度为O M ()N +(M 和N 为当前簇集边的两个簇集的三角片个数,这两个簇集对于误差度量的贡献由于特征法向量的变化
界相邻而会发生变化,需要重新计算),显然时间开销巨大.为此,分析(5)式,得到:
2
1
(,)j j C i
j i j i
j j j N C T C T C F C ερ?∈∈∈??=?????
?
∑∑
20
||||||||j j i
T d j
i T C j j n n n n ρρρ=∈????????∑∑∑ 22212
||j j C n ρ0||||||||2||||||||||C j i
j i j i j i j i j i j i
j i
j j j j j j j j j j j j j N T C T C T C T C T C T C T C i T n n n n n n ρρρρρρρ?∈∈∈∈∈∈∈=∈????+??=??????
∑∑∑∑∑∑∑∑∑ 120
||||2||||C j i
j i
j i
N j j j j i T C T C T C n n j ρρρ?=∈∈∈??=
?+????
∑∑∑∑ (6)
注意到则
j j ρ?
(7)
我们将可以看到(5)式具有直观的几何意义;重要的是,对于每一个簇集只需记录一个向量j i
i j j
T C N n ρ∈=
∑,||||1j j T n ?=,10
(,)22||||C j i
j i
N d j i T C T C F C n ερ?=∈∈?=????
?
∑∑∑
i C ,
5
和一个标量j i
i j T C S ρ∈=
∑,便可以在迭代更新簇集边界时,复杂度计算出误差能量以(1)O (,)d F C ε.
3.2 局部贪 根据提出一种迭代更新各个簇集贪心算法.假设网格边心算法
(7)式,我们边界的e E ∈,e i C 的两侧三角形为.
每一步迭考虑每一条簇集边变更以减,m n T T ,如果,m n T T 属于不同的簇集,那么称e 是一条簇集边界;所有簇集边界的集合为C E ,显然C E E ?代中,C e E ∈小(,)F C ε的可能性: 假设角形为所属l e ,m n T T ,的两侧三于的簇集分别.如图2可以考虑三种变更情况,可以得到三个不同的误差度量:
为,k l C C 况a)(,):init d F C ε原始情:,m k n T C T C ∈∈
c)
b)1(,):d F C ε 将三角片n T 并入到簇集k C 中,,m k k T C T C ∈∈ (8) 2,)F C 三角片n T 并入到簇集k C 中,,m l n l T C T C ∈∈
n (d ε:将将取三者之中误差度量d ε最小的作为最后的变更结果,然后更新簇集边集合C E .对于簇集边进行迭代更新,可以迭代地减小误差度量ε,直至所有簇集边的变更判断结果为C init 停止.由于每一步变更都缩小误差度量d ε,所以得到.为的连在实际迭代中使得破坏簇集的变更. 3.3 进一步每一个簇该算法的保证收敛性能够禁止此步优化
在实际的计算中,对了保证簇集通性,j i
T C 计算,如果簇集边的变更连通性,则集i C ,只需记录i j j N n ρ=
∈∑即可.
事实上的变更可能性时,只有其相关的所贡献的误差度量部分可能发生变化.由(7)式,
n (9)
ows,,当考虑∈k l C C U C e E 的簇集||??
C (b)k C gr ,k n k T C
m T ∈∈
(c)
l C grows,,m l n l T C T C ∈∈ :
,m k n l T C T C ∈∈
(a) 初l
(a)Initi (b)增长, k 始: ,m k T C al ,m k T C n T C ∈∈
,k l C C 2||||||j j j j j E n ρρρ=??∑∑∑U j k l j k j l
T C C T C T C ∈∈∈??
??
n T C ∈∈k C (c)增长l l C ,,m l T C n T C ∈∈
F .2 Analysis for mo ocal clus ig dification ter border
of l 图2 局部簇集边界变更分析
6
的三种簇集变更情况中边e ,
j k l
j T C C ρ∈∑U 在3.2节(8)中为常量,所以,只需考虑
||
||||||k l j k
C C j j j j T C j l
T C L n n ρρ∈=+∑∑U =1
∈2k l
j k l
T C C C C
j E ρ∈?
?
U
分别??
?
??∑U (10)
计算所对应的12,,init C C C 12,,init L L L 的值,取L 最大的变更情况(即对应误差度量最小)作为最后的变更
结果.L 越大对应应(7)式中所对的误差度量(,d F C )ε越小,L ,观(10)式察为各簇集三角片的面为的法向以积权量和的模,由向量和的性质:一簇相同模长的向量,方向越是相同其向量和越大;所以也可以由此得到优化(7)式即(10)式的几何意义:将具有相近法向量的三角片归于同一个簇集,从而同一簇集的三角片近似属于某一特征平面,这也正是分簇目的所在. 在得到最终的优化簇集划分后,将三个簇集以上的交点可以视为多边形网格顶点,便可以得到一个多边形网格模型,注意此处多边形不一定是平面多边形.如上构造出的多此可以选择性地对多边形网格作一步后处理:各边迭代细分修正.如果3.4多边形化和三角化
边形边可能无法很好地逼近该簇集的边界,由AB 为多边形网格的一条边,A 、B 为相,遍历边AB AB 距离最远的顶点P 和所对应簇集上的所有原始网格顶点,寻找出与边应多边形网格顶点边界细分为边AP 相应的距离如果d ,max /||||d AB Th >(max Th 为给定的容忍极限值),那么将边AB 和边PB .
我还可以将多边形网格分片为三角形Cohen-Stei 等[15]提出的多边形边校正方法优化和三角化该多边形网格,或是以经典的多边形三角化方法将简化的多边形网格转换为简化的三角形网格.
4 初始化
们网格,可以使用ner 3.2节给出了更新簇集边以优化误差度量(,)F C ε的局部贪心算法,要设计一个完整的分簇算法,需要一个3.2节的贪心算法优化误差度量(,)F C ε初始分簇划分,然后实施直到收敛为止.如果使用随机的簇集初值划分,不利该用较多的多应该用较少的2) 法向几乎相同的三角形应该属于同一个簇集,比如:一个平面应该只有一个簇集.
3) 相
使用Meyer 等[16]对于二维流形三角网格的高斯曲率的估计,对于网格顶点,其高斯曲率为:
其中于算法收敛的速度以及最终的效果,为此本文提出自适应的种子选取和簇集增长方式. 4.1 自适应的分簇初值
注意到以下几个事实:
1) 网格曲率越高的部分应边形去逼近表示,相对地,曲率较低的部分多边形去逼
近表示.
具有相近法向的三角形在最终分簇更有可能属于同一个簇集,给出一个将近法向的三角形归在同簇的
初始划分,可以加快3.2簇集边更新算法的收敛速度.
()
()(2)/j G j v Neighbour v v A θκπθ∈=?
∑, (11)
为顶点周围的顶角v ,v A 为顶点的Voronoi 区域的面积.三角片的高斯曲率v ()G i T κj θ近似取为其三顶点的高斯曲率绝对值和的平均值,用以反应该三角片曲率的高低.
考虑网格分簇问题:网格{,,}V E F Μ=,目标分簇数C N ,为了拥有高曲率的三角片的簇集将归并较少的三角片,拥有低曲率的三角片的簇集将归并较多的三角片.我们预测理想的分簇情况下,每一个簇集的高斯曲率总值应该接近于网格的平均值:
1
()D T ρκ=
∑ i i G i T F
C N ∈ (12)
4.2 分簇初值的算法
4.簇算建立每一个簇集时:随机取一个还未归属于任何一个簇集的三角片根据1节的分析,本节给出分初值的法:
i C seed T 角片以作为当前簇集的种子三角片,环地更新该簇集边还未归属于任何簇集并且与该簇集边相连的三i C 界将()j j j i T C ∈∑循T T n T Unif n ρ??
?????
为优先
级并入到停止并入三角.为了使几乎此簇集中,直到
片属于一个平面的三角片只归入一个簇集
当中,当簇集停止并入三角形后()j i
j G j T C T D ρκ∈>∑,仍然可以将()j j 7
j i T C ∈?T T n T Unif n dTh ρ??
?
∑很小)的入当前簇集
(dTh 三角片并C N 个簇集.至此,得到一个初始簇集划分,实际簇集数rC N 可能小于C N ,中.循环上述建立簇集的方法直到建立那么直接将C N 改为rC N .
得到初始的分簇划分后,可以实现 3.2的局部贪心算法:在每一步迭代中,遍历所有的簇集边界如果
将其归于另一三角片所属于的簇集;如果两三角片归于不同的我们将本文算法试验于多种网格模型,有着较好的视觉效果和较快的速度.与Cohen-Steiner 等[15]所提出
果相似或略好,模增加而愈加明显,本文同时给出本文算法的例子和一些Cohen-Steiner 等[15]算法的例子(Lloyd 算法).图3为将
Fandisk 模型以30个多边形逼近表示的例子,(a)、(b)为本文算法,(c)、(d)为Lloyd 算法,本文算法自适应的将底面分为了多个个簇集,需要出了较大模型Feline 和Amodilo 的例子,同样地,(a)、(b)为本文算法,(c)、(d)为Lloyd 算法,通过表1,可以看到算表1列出了所有示例的详细数据,包括收敛速度和度量误差C e E ∈,e 相邻的两三角片之一还未归于任何簇集,那么簇集,那么执行3.2中提出的变更判断,更新簇集边界C E ,直到所有簇集边的变更判断结果为C 停止.
5 实例
的Lloyd 算法相比,视觉效同时本文算法较Lloyd 算法有3-4倍的速度优势,且速度优势随模型规Fandisk 底面用一个簇集表示,而Lloyd 算法将后处理合并这三个簇集.图4图5给本文算法在大型模型上的速度较Lloyd 法有较大优势.
init ε(模型为归一化模型),可以看到本文的算法和算法最终得到的度量误差非常接近,同时本文算法具有较快的速度.(本文的计算在一台CPU: Intel
Core 2 Duo T7100 内存: 2GB 的PC 机上完成)
度量Lloyd
Table 1 Parameters of models and results of algorithm
(a) (d)
(b)(c)
Fig.4 Feline, which has roximated by 200 polygons
(a)(b): Algorithm of this paper; (c)(d): Lloyd algorithm
图4 Feline,99732个三角形,49864个顶点,以200个多边形逼近表示
(a)(b): 本文算法; (c)(d): Lloyd 算法
99732 triangles, 49864 vertices ,is app
(a) (b)(d)
(c)
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.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 算法
8
9
表1 模型参数和算法结果
模型
网格面数
顶点数
目标分簇数
算法
图号 时间(ms)
度量误差ε Bunny 69451 35947 100 本文算法图1 596
0.3898
Fandisk 12946 6475
30
本文算法
图3(a),(b)76 0.0968 Lloyd 算法图3(c),(d)181 0.3712 Feline 99732 49864 200
本文算法
图4(a),(b)696 0.4781 Lloyd 算法图4(c),(d)2357 0.4082 Amodilo
904 165954
本文算法
图,(b)2403 0.4092 5(a)331300Lloyd 算法
图5(c),(d)
8174 0.4172
6 结束语
本文提出变分网格逼近的参数.Lloyd 算法由于受到迭代次数的限制,速度比较慢,本文提出能量优化方式,通过离散基于法向的分簇能出自适和局部贪化算理想的分结果簇果都要优于.试本文的方法易于实现,效应用型系统中了全度量目标及数后,本文的方法和都不能证得到的度量最小,其分簇结果取决于分簇初值三角形的选取.本的可以有效地减少分的影响,在实际试验中,不同的分簇初值得到的分簇结和误都很接工作究更分簇度如曲离、曲氏距离为分簇度量等. References :
] 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.
Progressive Meshes. In: Rushmeier H, ed. Proceedings of ACM SIGGRAPH. New Orleans: Addison-Wesley
Professional, 1996. 99-108.
[3]
ck M, DeRose T, Duchamp T, Hoppe H, Lounsbery M, Stuetzle W. Multiresolution analysis of arbitrary meshes. In: Mair SG,
[7] er 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
ACM Press, 2002. 355-361.
的一种改效算法,以制模型简化比例进的高分簇数作为控完全不同于Lloyd 算法的一种量,提应的分簇初值选取心优法以得到,在视觉效和时间上Lloyd 算法.
通过大量验表明,,并且具有直观的几何意义可以有于几何造在定义局误差、划分簇集Lloyd 算法保全局误差文簇集种子自适应选取簇初值对结果果在视觉差度量上近.
未来的包括研有效的量,比率、测地距,或者以法向率、欧的组合作[1[2] Hoppe H. 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] E 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.
Lee AWF, Sweldens W, Schr?der P, Cowsar L, Dobkin D. Maps: Multiresolution adaptive parameterization of surfaces. In:
Machov Antonio: [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.
10
55 – 662.
n M. Variational Shape Approximation. In: Marks J, ed. Proceedings of ACM SIGGRAPH. Los
r Triangulated 2-manifolds. In: Hege HC,
[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. 6[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, Desbru Angeles: ACM Press, 2004. 905-914.
[16] Meyer M, Desbrun M, Schr?der P, Barr AH. Discrete Differential-geometry Operators fo Pothier K, eds. Proceedings of Visualization and Mathematics. Berlin-Dahlem: Springer, 2002. 34-57.
附中文参考文献:
[17] 孙家广. 计算机图形学. 第三版, 北京: 清华大学出版社, 1998.
有限元设计软件生成网格的PAVING算法 一、简介 使用有限元软件分析计算几何体的物理性质，其计算的过程可以划分为几个大的模块，输入几何体区域→为该区域生成一个网格→对生成的网格施加一个干扰→从受到干扰的网格开发分析数据→确定几何体的物理行为。分析计算流程图如图1所示。 图1 有限元分析的模块 在有限元分析的前处理模块中，网格生成时很重要的一个步骤。生成网格的质量会影响后处理计算结果的精度。当前，行业内流行多种网格生成的算法，各有各自的特点，该部分内容在本文国内外研究现状一节中已经详细阐述。其中paving算法健壮性良好，计算速度快，而且生成的网格质量好。本节主要阐述采用C++语言实现paving算法的实现过程。如图2所示，采用paving算法生成网格的算法流程图，从输入边界数据到最后输出划分好的网格，其中主要有生成新行，平滑处理，缝合处理，边界相交处理等几个子模块。
图2 Flow chart of paving algorithm 为了清晰理解上述paving算法的流程，以图3所示为例，图a当中为输入的原始外边界数 据，围成待划分网格的区域。选择边界上的一行节点为基础，添加生成一行新的浮动节点， 生成顺序为沿着外边界按逆时针方向进行。对新生成的浮动节点进行平滑处理， 使节点围成的单元的internal angle以及aspect ratio变得更为合理，单元更趋近于规则四边形。对剩余的待划分网格区域进行缝合，检查单元是否相交，对相交的单元进行处理，对单元进行调整，直到整个区域生成高质量的网格为止。 图3 paving算法铺筑单元示意图 依据图2所示流程图，生成相应的伪代码： Do Row choise While add row is not complete Add row portion Smooth row portion Seam boundary If intersection occurs then Connect overlaps Seam boundary End if Row adjustment
聚类分析算法解析 一、不相似矩阵计算 1.加载数据 data(iris) str(iris) 分类分析是无指导的分类，所以删除数据中的原分类变量。 iris$Species<-NULL 2. 不相似矩阵计算 不相似矩阵计算，也就是距离矩阵计算，在R中采用dist()函数，或者cluster包中的daisy()函数。dist()函数的基本形式是 dist(x, method = "euclidean", diag = FALSE, upper = FALSE, p = 2) 其中x是数据框（数据集），而方法可以指定为欧式距离"euclidean", 最大距离"maximum", 绝对值距离"manhattan", "canberra", 二进制距离非对称"binary" 和明氏距离"minkowski"。默认是计算欧式距离，所有的属性必须是相同的类型。比如都是连续类型，或者都是二值类型。 dd<-dist(iris) str(dd) 距离矩阵可以使用as.matrix()函数转化了矩阵的形式，方便显示。Iris数据共150例样本间距离矩阵为150行列的方阵。下面显示了1~5号样本间的欧式距离。 dd<-as.matrix(dd)
二、用hclust()进行谱系聚类法（层次聚类） 1.聚类函数 R中自带的聚类函数是hclust()，为谱系聚类法。基本的函数指令是 结果对象 <- hclust（距离对象, method=方法） hclust()可以使用的类间距离计算方法包含离差法"ward"，最短距离法"single"，最大距离法"complete"，平均距离法"average"，"mcquitty"，中位数法 "median" 和重心法"centroid"。下面采用平均距离法聚类。 hc <- hclust(dist(iris), method="ave") 2.聚类函数的结果 聚类结果对象包含很多聚类分析的结果，可以使用数据分量的方法列出相应的计算结果。 str(hc) 下面列出了聚类结果对象hc包含的merge和height结果值的前6个。其行编号表示聚类过程的步骤，X1，X2表示在该步合并的两类，该编号为负代表原始的样本序号，编号为正代表新合成的类；变量height表示合并时两类类间距离。比如第1步，合并的是样本102和143，其样本间距离是0.0，合并后的类则使用该步的步数编号代表，即样本-102和-143合并为1类。再如第6行表示样本11和49合并，该两个样本的类间距离是0.1，合并后的类称为6类。 head (hc$merge,hc$height)
广州有道资料网https://www.doczj.com/doc/889108140.html, ANSYS中简化模型和划分网格的方法 本文介绍了ANSYS中简化模型和划分网格的相关方法。 使在建立仿真模型时，经验是非常有助于用户决定哪些部件应该考虑因而必须建立在模型中，哪些部件不应该考虑因而不需建立到模型中，这就是所谓的模型简化。此外，网格划分也是影响分析精度的另外一个因素。本文将集中讨论如何简化模型以获得有效的仿真模型以及网格划分需要注意的一些问题。 理想情况下，用户都希望建立尽可能详细的仿真模型，而让仿真软件自己来决定哪些是主要的物理现象。然而，由于有限的计算机资源或算法限制，用户应该简化电磁仿真的模型。 模型简化 模型简化主要取决于结果参数及结构的电尺寸。例如，如果用户希望分析安装在某电大尺寸载体上的天线的远场方向图，那么模型上距离源区超过一个波长的一些小特征和孔径(最大尺度小于/50)就可以不考虑。另一方面，如果用户希望分析从源到用带有小孔的屏蔽面屏蔽的导线之间的耦合，那么必须对小孔、靠近源的屏蔽面以及导线进行精确建模。另外一个常用的简化是用无限薄的面来模拟有限厚度的导体面。一般而言，厚度小于/100的金属面都可以近似为无限薄的金属面。有限导电性和有限厚度的影响可以在SK卡中设置。对于比较厚的导体面，如果这种影响是次要的，那么用户仍然可以采取这种近似。例如，当建立大反射面天线的馈源喇叭模型时，喇叭壁的有限厚度对于反射面天线主波束的影响就是次要的。然而，如果喇叭天线用于校准标准时，那么喇叭壁的有限厚度就不能忽略。 网格划分 一般而言，网格划分的密度设置为最短波长的十分之一。然而，在电流或电荷梯度变化剧烈的区域，如源所在区域、曲面上的缝隙和曲面的棱边等，必须划分得更密。一个实用的指导原则是网格大小应该与结构间的间隔距离(d)相比拟(%26lt;=2d)。同样地，如果需要计算近场分布，那么网格大小应该同场点到源点间距离(d)相比拟。 总之，用户建立的几何模型应该抓住主要的物理现象，而网格划分则需要权衡输出结果相对于网格大小的收敛性。 广州有道资料网https://www.doczj.com/doc/889108140.html,
ansys教程之自适应网格划分 [摘要]：ANSYS程序提供了近似的技术自动估计特定分析类型中因为网格划分带来的误差。（误差估计在ANSYS Basic Analysis Procedures Guide第五章中讨论。）通过这种误差估计，程序可以确定网格是否足够细。如果不够的话，程序将自动细化网格以减少误差。这一自动估计网格划分误差并细化网格的过程就叫做自适应网格划分，然后通过一系列的求解过程使得误差低于用户指定的数值（或直到用户指定的最大求解次数）。 自适应网格划分的先决条件 ANSYS软件中包含一个预先写好的宏，ADAPT.MAC，完成自适应网格划分的功能。用户的模型在使用这个宏之前必须满足一些特定的条件。（在一些情况下，不满足要求的模型也可以用修正的过程完成自适应网格划分，下面还要讨论。）这些要求包括： 标准的ADAPT过程只适用于单次求解的线性静力结构分析和线性稳态热分析。 模型最好应该使用一种材料类型，因为误差计算是根据平均结点应力进行的，在不同材料过渡位置往往不能进行计算。而且单元的能量误差是受材料弹性模量影响的。因此，在两个相邻单元应力连续的情况下，其能量误差也可能由于材料特性不同而不一样。在模型中同样应该避免壳厚突变，这也可能造成在应力平均是发生问题。 模型必须使用支持误差计算的单元类型。（见表3－1） 模型必须是可以划分网格的：即模型中不能有引起网格划分出错的部分。 表3-1 自适应网格划分可用单元 2-D Structural Solids PLANE2 2-D 6-Node Triangular Solid PLANE25 Axisymmetric Harmonic Solid PLANE42 2-D 4-Node Isoparametric Solid PLANE82 2-D 8-Node Solid PLANE83 Axisymmetric Harmonic 8-Node Solid
基于变分网格的曲面简化高效算法? 金勇, 吴庆标+, 刘利刚 (浙江大学数学系,浙江杭州 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@https://www.doczj.com/doc/889108140.html, 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－),男,江西吉安人,博士,副教授,博士生导师,主要研究领域为数字几何处理,计算机辅助几何设计,计算机图形学和图像处理.
I 目录 1 概述 (1) 2 结构网格 (3) 2.1 贴体坐标法 (3) 2.2 块结构化网格 (11) 3 非结构网格 (16) 3.1 概述 (16) 3.2 阵面推进法 (16) 3.3 Delaunay三角划分 (19) 3.4 四叉树（2D）/八叉树（3D）方法 (21) 3.5 阵面推进法和Delaunay三角划分结合算法 (22) 4 其他网格生成技术 (23) 4.1 自适应网格 (23) 4.2 混合网格 (25) 4.3 动网格 (26) 4.4 曲面网格 (27) 4.5 重叠网格 (28) 5 网格生成软件 (29) 5.3 Gambit (29) 5.2 ICEM CFD (30) 5.1 TrueGrid (32) 5.2 Gridgen (34)
1 概述 计算流体力学作为计算机科学、流体力学、偏微分方程数学理论、计算几何、数值分析等学科的交叉融合，它的发展除依赖于这些学科的发展外，更直接表现于对网格生成技术、数值计算方法发展的依赖。 在计算流体力学中，按照一定规律分布于流场中的离散点的集合叫网格（Grid），分布这些网格节点的过程叫网格生成（Grid Generation）。网格生成是连接几何模型和数值算法的纽带，几何模型只有被划分成一定标准的网格才能对其进行数值求解，所以网格生成对CFD至关重要，直接关系到CFD计算问题的成败。一般而言，网格划分越密，得到的结果就越精确，但耗时也越多。1974年Thompson等提出采用求解椭圆型方程方法生成贴体网格，在网格生成技术的发展中起到了先河作用。随后Steger等又提出采用求解双曲型方程方法生成贴体网格。但直到20世纪80年代中期，相比于计算格式和方法的飞跃发展，网格生成技术未能与之保持同步。从这个时期开始，各国计算流体和工业界都十分重视网格生成技术的研究。上个世纪90年代以来迅速发展的非结构网格和自适应笛卡尔网格等方法，使复杂外形的网格生成技术呈现出了更加繁荣发展的局面。现在网格生成技术已经发展成为CFD的一个重要分支，它也是计算流体动力学近20年来一个取得较大进展的领域。也正是网格生成技术的迅速发展，才实现了流场解的高质量，使工业界能够将CFD的研究成果——求解Euler/NS方程方法应用于型号设计中。 随着CFD在实际工程设计中的深入应用，所面临的几何外形和流场变得越来越复杂，网格生成作为整个计算分析过程中的首要部分，也变得越来越困难，它所需的人力时间已达到一个计算任务全部人力时间的60%左右。在网格生成这一“瓶颈”没有消除之前，快速地对新外形进行流体力学分析，和对新模型的实验结果进行比较分析还无法实现。尽管现在已有一些比较先进的网格生成软件，如ICEM CFD、Gridgen、Gambit等，但是对一个复杂的新外形要生成一套比较合适的网格，需要的时间还是比较长，而对于设计新外形的工程人员来说，一两天是他们可以接受的对新外形进行一次分析的最大周期。要将CFD从专业的研究团体中脱离出来，并且能让工程设计人员应用到实际的设计中去，就必须首先解决网格生成的自动化和即时性问题，R.Consner等人在他们的一篇文章中，详细地讨论了这些方面的问题，并提出：CFD研究人员的关键问题是“你能把整个设计周期缩短多少天？”。而缩短设计周期的主要途径就是缩短网格生成时间和流场计算时间。因此，生成复杂外形网格的
ALE adaptive mesh单元： AC1D2, AC1D3, AC2D3, AC2D4, AC2D6, AC2D8, AC3D4, AC3D6, AC3D8, AC3D10, AC3D15, AC3D20, ACAX3, ACAX4, ACAX6, ACAX8 CPS4, CPS4T, CPS3 CPE4, CPE4H, CPE4T, CPE4HT, CPE4P, CPE4PH, CPE3, CPE3H CAX4, CAX4H, CAX4T, CAX4HT, CAX4P, CAX4PH, CAX3, CAX3H C3D8, C3D8R, C3D8H, C3D8RH, C3D8T, C3D8HT, C3D8RT, C3D8RHT, C3D8P, C3D8PH, C3D8RP, C3D8RPH 从列表来看，ALE自适应网格不适用于壳（S4、S4R等），另外对于实体单元也不适用于四面体（C3D4）。 问题1: The requested number of domains cannot be created due to restrictions in domain decomposition. 措施：job---Editjob---Parallelization---Number of domains: 设为1 问题2：ALE算法和CEL算法有什么区别？ 措施：①CEL只能用于explicit，AEL在implicit（声畴、冲蚀、磨损）和explicit都能用； ②ALE方法最初出现于数值模拟流体动力学问题的有限差分方法中。这种方法兼具 Lagrange方法和Euler方法二者的特长，即首先在结构边界运动的处理上它引进了 Larange方法的特点，因此能够有效的跟踪物质结构边界的运动；其次在内部网格 的划分上，它吸收了Euler的长处，即是使内部网格单元独立于物质实体而存在， 但它又不完全和Euler网格相同，网格可根据定义的参数在求解过程中适当调整 位置，使得网格不致出现严重的畸变。 CEL是欧拉-拉格朗日耦合，用于固体液体之间的耦合。 说法1：ALE是arbitary lagrange euler 算法 CEL couple lagrange euler 流固耦合的设置应该不属于算法的范畴 问题3：为什么odb转换输出坐标系后，只有S11等应力分量改变，而像Mises Equivalent 等都不变呢？ 措施：①看变量情况：S11指的是沿一方向的力，改了坐标系，值也会变。 但是如果是CPRESS，接触压力的话，它是指垂直于接触面上的力，与你的坐标没有关系，这样，你改了坐标系，自己它不会变。 其它的变量如mises等同理。
三维网格分割的经典方法 摘要：本文针对三维网格分割问题，提出一个经典的方法。该方法基于微分几何和测地距离。在算法中，将面片类型相同的顶点分割在一起。测地距离利用顶点之间的最短路径表示，这里可以利用一些经典的算法求最短路径，如Dijkstra 算法。但是当网格的数量很多时，Dijkstra 算法的效率很低。因此，此算法避免了在整个网格上应用最短路径算法，在局部网格中求最短路径，从而减少了计算量。 本文在人造物体的三维网格模型以及分子结构中验证了该方法的有效性。 关键字：几何算法 面片分割 测地距离 简介 3D 物体的三维网格表示法具有很多的应用。例如，在图像分析中，表示利用深度图像重建的物体表面。此外，在复杂物体和场景的建模和可视化中也有广泛的应用。在网格面片的分析中，网格分割已经成为一个关注的问题。网格分割也就是将网格上相互接近并且具有相似曲率的顶点分成一组。网格分割在很多方面具有重要的应用。特征提取，模型匹配等。 Mangan 和Whitaker 提出三维网格分割的分水岭算法。Razdan 和Bae 扩展了此算法，将基于点元（voxel-based ）和分水岭算法相结合，来分割三角网格。这两种方法在分割中都需要计算整个曲率，然后在局部曲率最小处建立初始分割。然而，在某些物体中，局部曲率的最小值是很难确定的。因此，在这里提出一个初始分割的新方法。 在该算法中，应用基于面片的类型信息的网格区域增长方法，对顶点进行初始分割。利用高斯曲率和平均曲率对顶点所在的面片进行分类。这里利用离散微分几何计算高斯曲率和平均曲率。通过本文提出的新方法来求得测地距离。 文章结构：第二部分，介绍网格面片的曲率分析和面片分类。第三部分，详述本文的分割算法。第四部分，实验以及其分割结果。第五部分，结论。 2 面片分析 在面片分析中，首先计算高斯曲率和平均曲率，然后利用它们进行面片分类。顶点P 0的高斯曲率K 的计算公式如下： ， A K θ ρ?= ，∑-=?i i 2θπθ ∑=i i A A ， A 为相邻三角形T i ( i =1，2，3，…)的面积总和。ρ为常量3。如图1所示。
基于映射法的六面体网格生成算法 王东风,翟建军,陈文亮 (南京航空航天大学机电学院,江苏南京 210016) 摘要:六面体网格划分技术是三维有限元仿真软件处理的关键环节之一,等参映射法既可适应特殊的区域边界形状,又可控制所生成单元的形状和密度。对基于等参映射法的六面体网格划分原理进行了深入研究,并在此研究基础上对等参映射法的计算过程进行了细致的分析,利用VC++开发了该算法的相应程序,最后给出了2个等参映射法具体的应用实例,计算结果表明该程序的计算精度已经达到了工程要求。 关键词:等参映射法;六面体网格;有限元 中图分类号:TP391 文献标识码:A 文章编号:1672-1616(2009)05-0025-03 在有限元仿真过程中,单元类型的选择对整个有限元仿真的计算效率、自动化程度、计算精度都将产生重要影响。六面体单元由于变形特性好、计算精度高等优点在三维有限元仿真领域中得到了广泛应用[1]。 映射法是三维网格划分中最早使用的方法,和扫略法、基于栅格法等其他方法相比,该方法生成网格速度快、生成的网格单元质量好、网格密度可控制[2～4]。映射法对复杂实体生成三维有限元网格有两大难点,一是子区域划分问题,二是子区域之间网格相容性问题。Price与Armstrong等提出中面法,将三维复杂区域分解成可映射子区域[5～7],但是该算法存在一些问题,特别是几何适应能力问题。李华和程耿东提出了三维组合式模板,一定条件下解决了子区域之间的网格相容性问题[2]。还有学者提出了Embedded Voronoi Graph[8]和BLOBs[9],对复杂实体利用映射法划分六面体网格。映射法在众多有限元分析软件中占有重要地位,美国Altair公司Hyper-Mesh软件中的Solid Mesh Panel就是利用映射法生成六面体网格。 本文对基于等参映射法的六面体网格划分技术进行了详细研究。通过形函数映射技术将物理域映射到参数空间域,对规则参数域进行网格剖分,将参数域的网格反向映射回物理空间,从而得到物理空间六面体网格。利用VC++实现了映射过程,在输入边界信息和划分信息后,即得到了六面体网格的节点信息和单元信息。 1 映射法生成四边形网格和六面体网格 本文主要讨论的是怎样在一个子区域中划分 六面体网格。这里的子区域指的是具有6个面12条边,每条边的特征点已知的区域。 求子区域六面体网格节点的步骤:(1)利用积累弦长参数化法对每条边进行参数化。(2)利用拉格朗日插值公式求边界函数。(3)利用边界函数,由双线性混合孔斯曲面片公式求曲面节点坐标。 (4)由孔斯线性混合插值公式求子区域节点坐标。 在计算的过程中要用到2种坐标系,即笛卡尔坐标系和自然坐标系。笛卡尔坐标系用x,y,z表示,自然坐标系用一组不超过1的无量纲参数r,s, t表示,边界点分别对应自然坐标等于1或0的点。如图1所示。 图1 自然坐标和笛卡尔坐标之间的变换 收稿日期:2008-08-08 作者简介:王东风(1979-),男,河南商丘人,南京航空航天大学硕士研究生,主要研究方向为CAD/CAM/CAE。
Computer Engineering and Applications 计算机工程与应用 2013，49（1）1引言降水粒子的智能识别，一直是大气探测领域的热门研究方向之一，降水粒子的有效识别和信息的提取，对于降水天气现象的自动化识别和数据分析至关重要。获取降水粒子的尺度谱和速度谱，并计算和统计降水强度、降水粒子总数、累积降水量以及雷达反射率因子等物理量，将为分析降水过程，了解地面雨滴谱微物理量变化提供基础资料[1]。对雨滴粒径的传统观测方法有面粉球法和吸水纸斑迹法等。面粉球法将雨滴收集在盛有面粉的容器中，当下降雨滴与面粉接触后，每个雨滴就产生一个小小的湿面球。每次测量都必须让面粉球在取样器中自然风干一天，然后放在烘箱内105℃条件下烘48h ，再用高精度电子天 平逐级称量，过程繁琐实时性差，且不适用于测量直径太小的雨滴。斑迹法是历史悠久、应用最广泛的一种雨滴粒径测量方法。该方法基于水滴在同一材料上形成的斑迹大小与水滴的粒径大小成正比的假定，通过实验测量预先设定好水滴粒径与斑迹粒径之间的比例关系，然后通过测量雨滴在相同材料上形成的斑迹大小推知相应的雨滴粒径；该方法雨滴粒径与斑迹粒径之间比例关系的确定以及滤纸和涂料的选取，对测量精度的影响都很大，并且无法避免雨滴溅射对观测结果的影响。虽然图像自动识别方法在利用斑迹法进行雨滴粒径观测中的应用能够减少资Snake 模型在雨滴边缘检测中的应用 卞真稳1，2，吕伟涛2，杨俊2，马颖2，马明1 BIAN Zhenwen 1，2,LV Weitao 2,YANG Jun 2,MA Ying 2,MA Ming 1 1.中国科学技术大学地球和空间科学学院，合肥230026 2.中国气象科学研究院大气探测研究所，北京100081 1.School of Earth and Space Sciences,University of Science and Technology of China,Hefei 230026,China 2.Institute of Atmospheric Sounding,Chinese Academy of Meteorological Sciences,Beijing 100081,China BIAN Zhenwen,LV Weitao,YANG Jun,et al.Application of snake model on raindrop edge https://www.doczj.com/doc/889108140.html,puter Engineering and Applications,2013,49（1）：186-190. Abstract ：Digital photography has very good application prospect in automatic observation of precipitation phenomenon,in which how to accurately detect the edge of precipitation particle from the digital image is a key technology.Snake model has the ability to merge prior knowledge and image processing algorithms,which can be used to accurately identify the outline of target.Considering the characteristics of raindrop image,an improved method to automatically select the initial contour of Snake model based on target shape heart automatic calibration method is presented,and the iteration processing of the greedy algorithm is used in the detection process.The raindrop detection method based on Snake model can be used to accurately detect the raindrop edge profile and has good https://www.doczj.com/doc/889108140.html,pared with the traditional edge detection operators,the proposed method has better edge detection effect. Key words ：raindrop image;edge detection;Snake model;greedy algorithm 摘要：数字摄像技术在降水粒子的自动观测中具有非常好的应用前景，如何在数字图像中准确地进行降水粒子的边缘检测是其中的一项关键技术。Snake 模型具有很好的融合图像上层知识和底层特征的能力，能够实现目标轮廓的准确定位。结合雨滴图像自身的特点，提出了目标形心的自动标定方法，在此基础上改进了Snake 模型初始轮廓点的选取方法，并通过贪婪算法进行迭代处理，实现了基于Snake 模型的雨滴边缘检测算法。算法能够准确地对数字图像中的雨滴边缘轮廓进行检测，且具有较好的稳定性。与传统的边缘检测算子相比，该方法对雨滴图像获得了更好的边缘检测效果。关键词：雨滴图像；边缘检测；Snake 模型；贪婪算法 文献标志码：A 中图分类号：TP391doi ：10.3778/j.issn.1002-8331.1112-0245 基金项目：国家科技部科研院所技术开发研究专项（No.NCSTE-2006-JKZX-303）。 作者简介：卞真稳（1982—），男，硕士研究生，主要研究领域：大气探测；吕伟涛，男，博士，研究员；杨俊，男，博士，副研究员；马颖，女，高级 工程师；马明，男，博士，副教授。E-mail ：zhwbian@https://www.doczj.com/doc/889108140.html, 收稿日期：2011-12-16修回日期：2012-02-10文章编号：1002-8331（2013）01-0186-05 CNKI 出版日期：2012-05-21https://www.doczj.com/doc/889108140.html,/kcms/detail/11.2127.TP.20120521.1142.058.html 186
!ANSYS命令流学习笔记12-自适应网格及其在WB中运用的对比 !学习重点： !1、网格收敛的重要性 由于应力集中（区别于应力奇异）的存在，在结构不连续处存在应力较大，而且随着网格质量数量的增加，应力值趋于收敛，据说收敛与否的应力差值可以很大，所以说重要细节结构的网格收敛十分重要。 !2、WorkBench中网格收敛的实现 WorkBench中在solution选项中设置网格循环次数，关键点网格优化系数，在求解结果选项下插入convergence，定义deformation或者stress的收敛系数。 计算前后的网格对比 虽然六面体网格变成四面体网格进行细分，但是初始网格划分的尺寸，对结果仍然有一定影响。而且优化的方式和APDL中也有一定差异，此例与APDL结果相同，是有一定运气成分。此处如果网格继续细化，肯定是fix处的尖角处应力奇异。（所以如何指定优化区域也是个问题） !3、APDL中网格收敛的实现 (1) 建模，注意不要划分网格，而且3D模型只能使用4面体单元网格； (2) 加载边界条件，由于没有网格，边界条件只好由面或者线确定； (3) 启动ADAPT宏命令，指定能量收敛误差，最大循环次数，网格优化系数；看起来很厉害的样子，但是使用方法和命令一样，只是输入命令框的不提示有此命令存在；. (4) 后处理查看结果。 !4、对网格收敛的一些疑问 (1) 宏命令调用：通过help文件查询到ADAPT的命令含义，但是不懂宏的内容，权且当做命令处理。 (2) ADAPT收敛误差：help中说是结构能量误差（SEPC），如果在热分析是热能量误差（TEPC），SEPC等效于应变能量误差（strain energy error ）。由于APDL和WorkBench收敛准则的不同，收敛结果无法对应，不明所以。 (3) 网格划分方式：实体单元只能采用非结构化网格形式，WB和APDL都是如此，WB 即使划分了结构和单元也会无效；但是APDL和WB指定网格初始尺寸有意义？；虽说非结
自动网格生成法 二维网格生成—Advancing Front方法 从概念上来讲，Advancing front方法是最简洁的方法之一。单位元素生成算法始于一个特殊边界条件所定义的“front”,此算法逐级地生成各个元素，同时“front”元素离散地前进，直至整个区域都被元素所覆盖。 网格生成过程包括三个主要步骤： 1、在边界上生成节点，形成一个离散的区域边界。 2、在离散区域边界内生成元素（亦或节点）。 3、强化节点形状以提高网格图形清晰度。 在介绍这个方法之前我们先介绍以下有关于二维空间地几何表示。 一、二维网格的几何特征 我们利用网格参数（一般是空间的函数）来表征网格的一些性质，诸如节点尺寸，节点形状和节点方向等等。网格参数包括两个相互正交的单位矢量a1和a2表示的方向参数，和由两个相互正交代表节点形状的矢量的模值h1和h2。前者表征网格节点伸展的方向，注意的是，只有在生成的是非各向同性的网格内，方向参数才有定义，否则方向矢量是常单位矢量，而尺寸参数有h1=h2，这样就定义了各向同性的平凡网格。 二、区域的几何表示 边界曲线的表示： 我们一般用组合参数样条线表示曲线边界单位，利用参数t，我们利用二维矢量函数表达出曲线边界： r t=x t,y t,0≤t≤1 一般来讲，一条组合样条曲线至少是C1连续的，以保证边界曲线平滑和算法要求的数学连续性。我们下面将要用厄米三阶样条线，当然还有许多就不一一举例了。 样条线的参数表达式如下： X t=H0t,H1t,G0t,G1t?x0,x1,x,t0,x,t1T,0≤t≤1 转置的前两项是曲线的两个端点，而后两项是它们对t求导现在端点处的值。另外G和H分别是四个三阶厄米多项式： H0t=1?3t2+2t3 ; H1t=3t2?2t3 G0t=t?2t2+t3 ; G1t=?t2+t3 此时，参数表达式可以通过一个系数矩阵来描述： X t=1,t,t2,t3M x0,x1,x,t0,x,t1T,0≤t≤1 其中M矩阵读者很容易写出，是一个4*4的方阵，而每一列是这些厄米多项式的系数排列而成。我们把这个表示称之为样本表示。每个边界都包含n个这样的数据点： x i,i=1,2,3,……,n 利用内插法可以构造出如下形式的关系式： X u=H0t x u i?1+H1t x u i+Δi G0t x,t u i?1+Δi G1t x,t u i 其中Δi是单位区间的长度。同时参数t也变为离散的取值是单位区间从原点到任意点所有的个数。如果参数的离散取值正好是i，那么u的表达式将简化为：
加密网格的话有两种参考标准一种是y+值，一种是y*值，一般来说，要加密网格主要是为了是y+值满足需求，具体的情况看楼主你的需要... 根据y+值来加密网格的步骤如下：运行fluent，导入cas and dat 文件后，点击adapt——Yplus/Ystar..。，之后出现选择界面，一般情况可以保持默认界面，当然也可以根据自己的需求选择选项，一般type项选择Yplus，然后点击compute，在min及max项会出现你的选择壁面的Y+值，在其下方，有minallowed 和maxallowed，输入你所需要的Y+值范围，点击Mark按钮，会标记出不符合要求的部分，然后点击adapt，就可以了，这部分区域的网格会加密，以适应你的要求 Y*的步骤也是这样的 但是前提是要知道你的计算的y+值范围，而这个值一般是估计值，且跟计算有关的，是个不确定量，所以一般只作参考用 希望能帮到你......另外，希望给加分啊，呵呵 追问 我点完adpat，Yplus/Ystar这个是灰的，不能点。。 回答 额，你计算了吗或者说你导入的是cas & dat 文件吗如果不是，你都没 有一个y+值的范围，怎么可能让软件给你加密网格...（这是基本条件）追问 当然计算了，我保存完再导入cas& dat也不行 回答 那你试试计算完，直接点adapt试试.....还真没遇到过你说的情况 追问 adapt都能点只是里面的Yplus/Ystar不能点，是灰色的 fluent里的常见问题（一） (2011-02-26 09:44:43) 1什么叫松弛因子松弛因子对计算结果有什么样的影响它对计算的收敛情况又有什么样的影响 1、亚松驰（Under Relaxation）：所谓亚松驰就是将本层次计算结果与上一层次结果的差值作适当缩减，以避免由于差值过大而引起非线性迭代过程的发散。用通用变量来写出时，为松驰因子（Relaxation Factors）。《数值传热学-214》 2、FLUENT中的亚松驰：由于FLUENT所解方程组的非线性，我们有必要控制的变化。一般用亚松驰方法来实现控制，该方法在每一部迭代中减少了的变化量。亚松驰最简单的形式为：单元内变量等于原来的值加上亚松驰因子a 与变化的积, 分离解算器使用亚松驰来控制每一步迭代中的计算变量的更新。这就意味着使用分离解算器解的方程，包括耦合解算器所解的非耦合方程（湍流和其他标量）都会有一个相关的亚松驰因子。在FLUENT中，所有变量的默认亚松驰因子都是对大多数问题的最优值。这个值适合于很多问题，但是对于一些特殊的非线性问题（如：某些湍流或者高Rayleigh数自然对流问题），在计算开始时要慎重减小亚松驰因子。使用默认的亚松驰因子开始计算是很好的习惯。
ANSYS自适应网格划分 (1) 何为网格自适应划分？ ANS YS程序提供了近似的技术自动估计特定分析类型中因为网格划分带来的误差。（误差估计在ANSYS Basic Analysis Procedures Gui第五章中讨论。）通过这种误差估计，程序可以确定网格是否足够细。如果不够的话，程序将自动细化网格以减少误差。这一自动估计网格划分误差并细化网格的过程就叫做自适应网格划分，然后通过一系列的求解过程使得误差低于用户指定的数值 （或直到用户指定的最大求解次数）。 自适应网格划分的先决条件 ANSYS软件中包含一个预先写好的宏，ADAPT.MAC完成自适应网格划分的功能。 用户的模型在使用这个宏之前必须满足一些特定的条件。（在一些情况下，不满足要求的模型也可以用修正的过程完成自适应网格划分，下面还要讨论。）这些要求包括： 标准的ADAPT过程只适用于单次求解的线性静力结构分析和线性稳态热分析。模型最好应该使用一种材料类型，因为误差计算是根据平均结点应力进行的，在不同材料过渡位置往往不能进行计算。而且单元的能量误差是受材料弹性模量影响的。因此，在两个相邻单元应力连续的情况下，其能量误差也可能由于材料特性不同而不一样。在模型中同样应该避免壳厚突变，这也可能造成在应力平均是发生问题。 模型必须使用支持误差计算的单元类型。 模型必须是可以划分网格的：即模型中不能有引起网格划分出错的部分。 自适应网格划分可用单元 2-D Structural Solids PLANE2 2-D 6-Node Triangular Solid PLANE25 Axisymmetric Harmonic Solid
1 网格分割的一般方法 在用Fluent 的并行求解器时，需要将网格细分割为几组单元，以便在分离处理器上求解将未分割的网格读入并行求解器里，可用系统默认的分割原则(推荐使用）还可以在连续求解器里或将mesh 文件读入并行求解器后自己分割。 在建立问题(定义模型、边界条件等)之前或之后分割网格都可以，不过，由于某些模型的特点(象非等形接触面、滑移网格、 shell-conduction encapsulation 的自适应)，最好是在建立问题后。!!如果case 文件含有滑移网格或非等形接触面，要在计算过程中进行自适应，因此要用连续求解器分割。 值得注意的是计算节点间的相关单元的分布在网格自适应时要保持不变，除非是非等形接触面，这样在自适应后就不必重新分割了。若在网格分割前用连续求解器建立问题，用于此项工作的计算机必须有足够大的内存来读入网格。如果网格太大，不能读进连续求解器，可将未分割的网格直接读入并行求解器里(使用所有被定义主机的内存)，然后让并行机自动分割。在这种情况下，你将在做一个初步网格分割后建立问题。如果必要可以手工再重新分割一次。 2 自动分割网格 在将case 文件读入并行求解器之前选用两分法或是其他网格分割方法来自动分割网格。对一些方法，可预览来确定是否为最佳的网格分割，注意case 文件中含有滑移网格或非等形接触面，在计算过程中要自适应，则需要在连续求解器中分割此文件，然后再把它读入并行求解器，在Auto Partition Grid 控制面板上选择Case File 选项。 并行求解器上自动网格分割的步骤如下： 1. (任选)在菜单栏上点Parallel Auto Partition...，弹出Auto Partition Grid 控制面板设置分割参数。 读入mesh 文件或case 文件时如果没有获取分割信息，那就保持Case File 选项开启，Fluent 会用Method 下拉菜单里的方法分割网格。 设置分割方法和相关选项的步骤如下： a) 关闭Case File 选项，就可选择控制面板上的其他选项。 b) 在Method 下拉菜单里选取两分方法。 c) 可为每个单元分别选取不同的网格分割方法，也可以利用Across Zones 让网格分割穿过区域边界。推荐不采用对单元进行单独分割(关闭Across Zones 按钮)，除非是溶解过程需要不同区域上的单元输出不同的计算信息(主区域包括固体和流体区域)。 d) 若选取Principal Axes 或Cartesian Axes 方法，可在实际分割之前对不同两分方向进行预测试以提高分割性能。用预检则开启Pre-Test 选项。 e) 点击OK。 如果case 文件已经网格分割，且网格分割的数量和计算节点数一样，那就可以在Auto Partition Grid 控制面板上默认选择Case File 选项，这会让Fluent 在case 文件中应用分割。 2. 读入case 文件，方法是在菜单栏上选File Read Case...。 自动分割过程的报告 当网格自动分割时，有关分割进程的信息就会被显示在控制窗口上。如果想需要额外信息，可在分割完成后，选Parallel Partition...，弹出Partition Grid 控制面板，打印报告。在Partition Grid 控制面板上点击Print Active Partitions 或Print Stored Partitions 时，Fluent 会在控制窗口里显示分割ID、单元数、面数、接触面数和每个活动或已储存分割的接触面曲率，还可以显示最小和最大的单元、面、接触面和面曲率变量 3 手动分割网格 在网格分割时推荐使用并行求解器上的自动分割，也可在连续求解器或并行求解器上手动分割。在自动或