华南理工大学学报(自然科学版)第35卷第12期Journa l o f South C hina U niversity o f Techno l o g y
V o.l 35 N o .122007年12月
(N atura l Science Editi o n)
D ece m ber 2007
文章编号:1000-565X (2007)12-0051-05
收稿日期:2006-11-18
*基金项目:江苏省创新人才培养基金项目(BK 2001408);航空科学基金项目(03H 52059)
作者简介:顾步云(1979-),男,博士生,主要从事逆向工程、CAD /CAM 研究.E -m ai:l gubuyun @https://www.doczj.com/doc/1413417752.html,
基于网格模型的光滑B 样条曲面重建算法
*
顾步云1
周来水1
刘胜兰1
孙秀慧
2
(1.南京航空航天大学机电学院,江苏南京210016;2.中兴通讯公司上海研发中心,上海200233)
摘 要:提出并实现了一种基于网格模型的光滑B 样条曲面重建方法.首先研究并实现
了网格模型上特征线的定义和优化方法,在此基础上提供了多种交互式编辑工具,使用户可以方便地构建出符合原始设计意图的四边界区域拓扑模型;最后在综合考虑拟合精度、光顺性和连续性等条件下实现了B 样条曲面的光滑拟合.实验证明算法的效率和曲面拟合质量都能较好地满足反求工程的要求.
关键词:反求工程;光滑B 样条曲面重建;网格模型;特征线;四边界区域划分中图分类号:TP391 文献标识码:A
B 样条曲面是目前CAD /
C AM 系统中广泛采用的曲面表达形式.基于测量数据的参数化和B 样条曲
面重建是反求工程中的关键问题和研究热点之一[1]
.
随着测量技术的发展,获得实物的整体三角网格模型已变得越来越容易,但对于绝大多数的网格模型来说,用单张B 样条曲面来拟合是非常困难的,通常的做法是将其划分为多个具有矩形拓扑的区域后,用分片B 样条曲面进行光滑拟合.K rish -na m urth 等[2]
首先利用D ij k stra 算法得到由网格线构成的初始特征线,然后将其光滑为直线,进而根据用户绘制的空间B 样条曲线对当前直线的吸引得到光滑的特征曲线,这种方法操作很不方便.E ck 等[3]和Zhou 等[4]
通过构造网格模型的Vorono i 图,对偶地得到基础De launay 三角域,然后采用匹配算法实现四边界区域的自动划分.张丽艳[5]
首先计算出网格简化模型上两点之间的最短距离,实现了网格模型的三边界区域划分,然后自动匹配为四边界
区域.Shen 等[6]
首先计算出网格曲面拉普拉斯算子矩阵的特征向量,然后利用M orse 理论抽取其M orse -S m ale 复形实现四边界区域的自动划分.这一类自动算法存在诸多问题:计算复杂且效率较低,稳
定性较差,更突出的问题是划分结构很难准确地反映样件的原始设计意图,区域边界线无法精确逼近
模型的特征轮廓.另外,M a 等[7]
提出了一种散乱数据点的参数化方法,通过将其向基曲面投影得到数
据点的参数值;Lai 等[8]
提出了一种基于特征敏感的参数化方法,在此基础上实现了曲面拟合;W eiss 等[9]
首先通过将数据点投影到基曲面上得到初始参数值,然后通过迭代策略得到精度和光顺性都较好的拟合曲面.这些算法主要研究了曲面整体拟合中的参数化以及节点插入等问题,没有具体讨论四边界区域划分的算法,而且在拟合中仅考虑了精度、光顺性以及连续性中的某个或其中两个方面.
因此,本研究提出了一种网格模型的光滑B 样条曲面重建方法:首先研究并实现了网格模型上初始特征线的定义与优化方法;然后提供了丰富的特征线编辑和四边界区域划分工具,用户可以快速地得到符合样件构型的四边界区域分片模型;最后重点研究了综合考虑拟合精度、光滑性、以及连续性等条件下的光滑B 样条曲面拟合方法.结果表明,本算法的计算效率和曲面拟合质量均能较好地满足反求建模的工程需要.
1 四边界区域划分
1.1 初始特征线定义
通过在靠近模型特征位置处选取多个特征点来定义特征曲线是目前在复杂曲面重建中广泛采用的
一种方法.网格上的初始特征线可以表示为一条离散形式的Snake[10],它采用网格模型上的离散点p i 和两个相邻点之间的线段l i来表示:
Snake={p1,p2,,,p n,l1,l2,,,l n-1}(1) (l i=p i p i+1,i=1,2,,,n-1)
设p1,p n是用户在网格模型上选取的两个点,为了确定上式所表达的初始特征线,就是要计算出网格模型上p2,p3,,,p n-1的位置,本研究采用了一种基于投影追踪的方法[11];实验表明,该方法计算效率高,易于实现.
1.2特征线优化
通常还需要对初始特征先进行优化,使之尽可能地光滑并逼近模型的特征位置.式(1)中的Snake 能量方程[10]可以表示为
E Sn ake=w t E t+w b E b+w m E m(2)其中:E t,E b和E m分别表示拉伸能、弯曲能和三维网格特征能;w t,w b和w m为对应的权值.通过使其能量E Snake最小可以优化特征线.本文借鉴文献[10]的方法来确定离散点p i的Snake能量最小位置,但三维网格特征能采用网格曲面在该点的法矢n i与相邻三角片的法矢n f之间夹角余弦的最小值来表示:
E mesh(p i)=m i n(n i*n f)(3)
1.3四边界区域生成
本文提出的四边界区域的划分方法分为3个基本过程:一是通过定义特征线生成域边,将模型转化为初始的N边界区域,或者定义初始的小四边界区域初始结构;二是对初始的N边界区域进行进一步划分生成四边界区域拓扑结构,或对初始的小四边界区域初始结构进行扩展生成最终的四边界区域拓扑模型;三是提供了多种编辑手段对已生成的四边界区域模型进一步修改,最终生成符合样件构型的四边界区域分片拓扑模型.
四边界区域的初步划分方法:针对无内环的开边界模型,可在网格边界上选取一系列边界点,算法以相邻两个边界点为端点在网格上自动投影,快速地生成域边.通过多次操作,可以得到n条顺序首尾相连的封闭域边界线,即生成边界区域,然后对其进一步细分,生成四边界区域分片模型.对于封闭模型或含有内边界的模型,采取如下方法初步划分区域:首先在靠近模型特征处生成一个小的四边界域,然后以该小四边界区域为基础在模型上不断扩展,直至扩展到整个模型,形成整个模型的初始四边界域模型.要在给定的初始小四边界区域基础上扩展为多个四边界域,可以分为3种情况处理:(1)由一条域边和两个域顶点生成一个四边界区域:选择一个已存在的域边、拾取两个点作为新的域顶点,通过计算该域边的两个域顶点分别到两个新的域顶点的距离,生成一个新的四边界域;(2)由两条域边和一个域顶点生成一个四边界区域:选取两个已存在的相邻域边、拾取一个点作为新的域顶点,生成一个新的四边界域;(3)由三条域边构造一个四边界区域:拾取三个已存在的首尾相接的域边,也可生成一个新的四边界域.通过前面三种情况进行不断地扩展生成新的四边界区域,直到得到整个模型的四边界分片拓扑结构.
通常,还需要进一步调整由上述方法构造的初始四边界区域拓扑结构,使之更加符合样件的构造特点,为此本文提供了多种编辑工具,实现了域顶点的增加、删除、合并和移动;域边的修改和优化;域面的合并和细化等功能.对于每一种编辑操作后,都要对相应的数据结构进行及时更新,保持正确的域点、域边和域面的拓扑关系.通过上述方法,可以较方便地得到符合样件构型的四边界区域拓扑结构.
2光滑B样条曲面重建
2.1数据点参数化
对于四边界区域内散乱分布的空间网格点,本文采用投影参数化法[7]计算其对应的参数值:首先对四边界区域进行粗略采样,插值拟合B样条曲面作为基曲面;然后将域内的网格点向该基曲面投影,将投影点的参数值作为空间网格顶点的参数值.设某个给定的四边界区域含有m+1个数据点p i(i= 1,2,,,m),参数化后的参数域D(u,v)中与数据点p i 对应的参数点为p i(u i,v i).
2.2节点矢量计算
令{(u i,v i)i=0,1,,,m}为四边界区域内网格点对应的非递减参数序列.u,v方向的节点矢量采用平均节点法计算,该方法可以保证单方向上每个节点区间至少包含一个参数点,但并不能确保每个二维的节点区间内至少存在一个参数点.因此,本文提出一种解决方法:首先找到不含参数点的节点区间(u i,v j),并按下式插入参数点(u*,v*),这样就可以有效地避免方程组求解中的奇异值问题.
u*=(u i+u i+1)/2,v*=(v j+v j+1)/2(4)
图1为节点矢量的计算结果,其中黑色细点为四边界区域内的网格顶点,网格线为节点矢量线,5个黑色粗点为按照本文方法插入的参数点.从图中可以看出节点矢量线较好地反映了数据点的分布情况,而且不存在无参数点的节点区间.
52华南理工大学学报(自然科学版)第35卷
图1均匀节点矢量线与在无参数点的节点区间内插入参数值
F ig.1A v erage kno t v ector li nes and i nserting para m e ters in t he
kno t sec t o rs w ithout para m eter po i n ts
2.3分片B样条曲面拟合
2.3.1建立最小二乘函数
首先建立B样条曲面拟合的距离最小二乘函数如下所示:
F lst(x)=E m i=0E n j=0d j N j(u i,v i)-P i=
(N*d-P)2F(5)其中:p0,p1,,,p m为四边界区域内的网格顶点,F lst 表示所有的网格顶点到待拟合B样条曲面的最小二乘距离,(u i,v i)是数据点p i对应的参数值,N*为m+1行(n+1)@(n+1)列基函数矩阵,d j为待拟合曲面的控制顶点,d为待拟合曲面的控制顶点矩阵,F表示矩阵的F-范数,x为k=(m+1)@(n+
1)个控制网格顶点列向量.
2.3.2确定控制顶点个数
控制顶点个数的选取应在保证矩阵N*T N*正则以及拟合曲面波动较小的条件下尽量多取,本文将每一方向的控制顶点个数均取为n=i n t(sqrt(m/ 2)).实验表明,控制点个数的确定还需要根据数据点分布的均匀程度进行适当的调整.
2.4光顺性约束
为了减少逼近误差,通常会选取数量较多的控制顶点,这样也会带来较大的曲面波动,无法满足光顺性要求.许多文献[7,9]均采用曲面的弯曲能量作为光顺约束函数,但这种方法需要通过高斯积分法计算曲面的刚度矩阵,计算量较大.本文给出一种简单的光顺约束函数,通过控制网格的分布比较规则来提高曲面的光顺性,实验表明本文方法的光顺效果与弯曲能量法基本相同,但计算更简单,效率提高了近20%.光顺约束函数如下所示:
F s mooth(x)=1
2
E n-1
i=0
E n-2
j=0
d i+1,j-d i,j2+
1 2E n-1
i=0
E n-2
j=0
d i,j+1-d i,j2(6)
其中:x k=d i(k),j(k),i(k)=?k/n8,j(k)=k%n.图2
是计算B样条曲面控制网格的结果,控制顶点取为12@12,光顺权因子取010004.图2(a)为没有施加光顺约的结果,其控制网格线很不规则,图2(b)为施加了光顺约束后的结果,其控制网格规则了很多,但拟合误差也有一定的增大.
图2施加光顺约束前后得到的控制网格及拟合误差
F i g.2Contro l ne t and fitti ng error w ith and w ithout add i ng
s m ooth constraint
2.5边界连续性约束
为了使曲面片之间光滑过渡,本文引入了边界连续性约束函数[12],并将满足边界连续性约束的B 样条曲面最小二乘拟合问题转化为约束最优化问题,利用L-M算法[13]求解得到控制顶点向量,进而完成了光滑B样条曲面拟合.图3为施加不同边界约束下两个曲面片连接的效果图,其中图(a)表示在没有加边界连续条件时,曲面片之间位置不连续;图(b)表示在施加了切矢连续的约束条件时,两曲面片连接处光滑过渡.
图3相邻两个四边界曲面片拟合结果
F i g.3F itti ng results of t wo ne i ghboring quadril ate ra l paches 3计算实例
应用本文提出的曲面重建方法,完成了某型飞机部分后机身网格模型的光滑B样条曲面重建.图4(a)
53
第12期顾步云等:基于网格模型的光滑B样条曲面重建算法
图4某型飞机部分后机身网格模型的光滑B样条曲面重建过程
F ig.4Smoo t h B-spli ne surface reconstruc ti on pro cess of pa rt o f
som e p l ane back body p s tr i angular m odel 为某型飞机部分后机身网格模型,共包含13208个网格顶点;图4(b)是定义边界特征线后所构建的初始N边界区域模型;图4(c)是四边界区域划分的某个中间结果;图4(d)是经过编辑、优化后得到的最终四边界区域拓扑模型,共有四边界区域50个;图4(e)为拟合得到的光滑B样条曲面,光顺因子取为010003;图4(f)为分片计算散乱点到对应曲面片之间的距离,即为曲面拟合的误差值,并采用线性插值法显示误差云图.在P4118G/256M机器上反算控制顶点的时间约105s,曲面重建时间大约为6m i n,经过统计,绝对大数点的误差值都在0105mm以内,误差值在1mm以上的部分测量点本身就是非正常点,仅占总数据点数的0118%左右.
4结论
本文提出了一种基于网格模型的光滑B样条曲面重建方法,算法具有如下特点:
(1)算法在反求建模策略、计算效率以及拟合曲面的质量都能较好地满足反求工程的实际要求.
(2)综合考虑了曲面拟合中的精度、光顺性和连续性等三大因素,这是大多数其他曲面拟合方法所不具备的优点,并给出了一种简单的光顺约束函数,提高了计算效率.
(3)提供了较完善的特征线定义、编辑以及四边界区域划分工具,用户可以较方便地得到符合样件构造特征的四边界区域分片拓扑结构,为后续拟合高质量的曲面提供了良好的基础.
参考文献:
[1]V arady T,M a rti n R R,Cox J.R everse eng ineer i ng of geo-
m e tric m ode ls)))an i ntroducti on[J].Compu ter-A ided
D esi gn,1997,29(4):255-268.
[2]K r i shnamurthy V,Levoy M.F itti ng s m oo th surfaces to
dense po l ygon m eshes[C]M Compu ter G raph i cs
(SI GGRAPH p96P ro ceedings).N ew O r l eans:A C M SI G-
GRA P H,1996,30:313-324.
[3]E ck M,H oppe H.Au t om atic reconstruction of B-Spli ne
surfaces o f arb itrary topo l og ical type[C]M Compu ter
G raphics(SI GGRAPH p96P ro ceedings).N e w O r l eans:
AC M SI GGRAPH,1996,30:325-333.
[4]Zhou Ru-rong,Zhang L-i yan,P ang X i u-feng,et a.l S m ooth
piece w i se spli ne sur f aces fitti ng to arb i tra ry con tro l po l y-
hedron[J].Chi nese Journa l of A eronautics,2001,14
(1):57-64.
周儒荣,张丽艳,庞秀峰,等.给定任意拓扑控制多面
54华南理工大学学报(自然科学版)第35卷
体的分片光滑样条曲面拟合[J].中国航空学报,2001,14(1):57-64.
[5] 张丽艳.逆向工程中模型重建关键技术研究[D ].南
京:南京航空航天大学机电学院,2001.[6]
Shen D ong ,Peer -T i m o Bre m er ,M i chae l G arland ,e t a.l Spectra l surface quadrangu lati on [C ]M T o appear i n SI GGRAPH,2006.Boston ,M assachussets :AC M SIG -GRA P H,2006.
[7] M a W,K rut h J P.Para m etrization of random ly m easured
po i n ts f o r least squares fitti ng o fB-Spli ne curves and sur -f aces [J].Co m pute r -A i ded D es i gn ,1995,27(9):663-675.
[8] La i Yu -kun ,H u Sh-i m i n ,H e l m u t Po tt m ann .Surface fitti ng
based on a feature sensitive para m etrization [J].Com -puter -A i ded D esi gn ,2006,38(7):800-807.
[9] W e iss V o lker ,A ndo r Laszl o ,R enne r G abo r ,et a.l A d -vanced surface fitti ng techn i ques [J ].Co m put A i ded
G eom D esi gn ,2002,19(1):19-42.
[10] M ilroy M J ,Brad ley C ,V ickers G W.Seg m entati on o f a
w rap -a round m ode l us i ng an active contour [J].Co m-puter -A ided D esi gn ,1997,29(4):299-320.
[11] 刘胜兰,周儒荣,张丽艳.用主动轮廓模型优化网格
曲面上的特征线[J].计算机辅助设计与图形学学报,2004,36(4):339-443.
L i u Shen -lan ,Zhou R u -rong ,Zhang L -i yan .F eature li ne opti m izati on on triangu lar surfaces usi ng acti ve contour m ode l [J].Journa l o f Co m puter -A i ded D esi gn &Co m-pu ter G raph i cs ,2004,36(4):339-443.
[12] 朱心雄.自由曲线曲面造型技术[M ].北京:科学出
版社,2000.
[13] P ress W,T euko l sky S A,F lanne ry B P .N u m er i ca l rec-i
pes i n c [M ].Ca m bridge :C a mbr i dg e U niversity P ress ,1992.
A l gorit h m for S m oot h
B -Spline Surface Reconstruction
Base d on M es h M odel
Gu Bu-y un 1
Zhou Lai -shui 1
L iu Sheng-lan 1
Sun X iu-hui
2
(1.Coll ege o fM echanical and E l ectr i cal Eng i neer i ng ,N anji ng Un i v .of A eronautics and A stronauti cs ,N an ji ng 210016,Ji angsu ,Ch i na ;
2.ZTE Corporati on Shangha iR &D Institute ,Shanghai 200233,China)
Abst ract :Th is paper proposes and i m p le m ents an appr oach to s m ooth B -Sp line surface reconstructi o n based on the m esh m ode.l I n the i n vesti g ation ,a m ethod to define and opti m ize the feature li n es o f the m esh m odel is studied and i m ple m ented .Then ,a set of i n teractive ed iting too ls are prov i d ed for users to free ly construct the fi n al quadr-i latera l patch topo logy m odelwh ich su its the or i g i n al design i n ten.t Fina ll y ,a s mooth B -spli n e surface is reconstruc -ted by synthetically consi d er i n g the fitti n g accuracy ,the s m oothness and the continuousness .Experi m ental results de m onstrate that the proposed a l g orithm m eets the requ ire m ents for reconstructi o n efficiency and surface fitting qua -lity i n reverse engineeri n g .
K ey w ords :reverse eng i n eering ;s m ooth B -spli n e surface reconstructi o n ;m esh m ode;l feature line ;quadrilatera l patch seg m en tation
55
第12期顾步云等:基于网格模型的光滑B 样条曲面重建算法
有限元设计软件生成网格的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
广州有道资料网https://www.doczj.com/doc/1413417752.html, ANSYS中简化模型和划分网格的方法 本文介绍了ANSYS中简化模型和划分网格的相关方法。 使在建立仿真模型时，经验是非常有助于用户决定哪些部件应该考虑因而必须建立在模型中，哪些部件不应该考虑因而不需建立到模型中，这就是所谓的模型简化。此外，网格划分也是影响分析精度的另外一个因素。本文将集中讨论如何简化模型以获得有效的仿真模型以及网格划分需要注意的一些问题。 理想情况下，用户都希望建立尽可能详细的仿真模型，而让仿真软件自己来决定哪些是主要的物理现象。然而，由于有限的计算机资源或算法限制，用户应该简化电磁仿真的模型。 模型简化 模型简化主要取决于结果参数及结构的电尺寸。例如，如果用户希望分析安装在某电大尺寸载体上的天线的远场方向图，那么模型上距离源区超过一个波长的一些小特征和孔径(最大尺度小于/50)就可以不考虑。另一方面，如果用户希望分析从源到用带有小孔的屏蔽面屏蔽的导线之间的耦合，那么必须对小孔、靠近源的屏蔽面以及导线进行精确建模。另外一个常用的简化是用无限薄的面来模拟有限厚度的导体面。一般而言，厚度小于/100的金属面都可以近似为无限薄的金属面。有限导电性和有限厚度的影响可以在SK卡中设置。对于比较厚的导体面，如果这种影响是次要的，那么用户仍然可以采取这种近似。例如，当建立大反射面天线的馈源喇叭模型时，喇叭壁的有限厚度对于反射面天线主波束的影响就是次要的。然而，如果喇叭天线用于校准标准时，那么喇叭壁的有限厚度就不能忽略。 网格划分 一般而言，网格划分的密度设置为最短波长的十分之一。然而，在电流或电荷梯度变化剧烈的区域，如源所在区域、曲面上的缝隙和曲面的棱边等，必须划分得更密。一个实用的指导原则是网格大小应该与结构间的间隔距离(d)相比拟(%26lt;=2d)。同样地，如果需要计算近场分布，那么网格大小应该同场点到源点间距离(d)相比拟。 总之，用户建立的几何模型应该抓住主要的物理现象，而网格划分则需要权衡输出结果相对于网格大小的收敛性。 广州有道资料网https://www.doczj.com/doc/1413417752.html,
实验二曲线曲面的拼接贝塞尔曲线的拼接 P=[-1 2 3.5 4 4.5 6 7;7 5 6 6.5 7 3 9;2 6 4 4.5 5 11 9]; plot3(P(1,1:4),P(2,1:4),P(3,1:4),'o') hold on plot3(P(1,4:7),P(2,4:7),P(3,4:7),'+'); hold on B=[-1 3 -3 1;3 -6 3 0;-3 3 0 0;1 0 0 0]; for t=0:0.05:1 T=[t^3 t^2 t 1]; P1=T*B*P(1,1:4)'; P2=T*B*P(2,1:4)'; P3=T*B*P(3,1:4)'; plot3(P1,P2,P3,'r.') hold on Q1=T*B*P(1,4:7)'; Q2=T*B*P(2,4:7)'; Q3=T*B*P(3,4:7)'; plot3(Q1,Q2,Q3,'b*') end title('贝塞尔曲线的拼接'); xlabel('x');ylabel('y');zlabel('z');
B样条曲线的拼接 P=[1 2 3 4 5;1.5 7 6 6.5 7;3 1.5 3.5 5.5 4.5]; plot3(P(1,1:4),P(2,1:4),P(3,1:4),'o') hold on plot3(P(1,2:5),P(2,2:5),P(3,2:5),'+') hold on B=[-1 3 -3 1;3 -6 3 0;-3 0 3 0;1 4 1 0]; for t=0:0.05:1 T=[t^3 t^2 t 1]; P1=1/6*T*B*P(1,1:4)'; P2=1/6*T*B*P(2,1:4)'; P3=1/6*T*B*P(3,1:4)'; plot3(P1,P2,P3,'r.') hold on Q1=1/6*T*B*P(1,2:5)'; Q2=1/6*T*B*P(2,2:5)'; Q3=1/6*T*B*P(3,2:5)'; plot3(Q1,Q2,Q3,'b*'); end title('B样条曲线的拼接'); xlabel('x');ylabel('y');zlabel('z');
基于变分网格的曲面简化高效算法? 金勇, 吴庆标+, 刘利刚 (浙江大学数学系,浙江杭州 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/1413417752.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研究人员的关键问题是“你能把整个设计周期缩短多少天？”。而缩短设计周期的主要途径就是缩短网格生成时间和流场计算时间。因此，生成复杂外形网格的
基于映射法的六面体网格生成算法 王东风,翟建军,陈文亮 (南京航空航天大学机电学院,江苏南京 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。
学习小结：前面学习了Bezier 曲线，B 样条基函数和B 样条曲线的一些基础知识。掌握关键问题是一条B 样条曲线间的多段曲线的光滑连接。因为现在是用多段Bezier 曲线来描绘一条B 样条曲线，所以问题变为两段Bezier 曲线间光滑连接。两段Bezier 曲线段（3次）B1和B2光滑连接的条件： （1）.要求B1和B2有共同的连接点，即G 0 连续。 （2）.要求B1和B2在连接点处有成比例的一阶导数，即G 1 连续。由端点处的一阶导数 )(3)0(2),(3)1(10123Q Q B P P B -='-=',为实现G 1连续，则有： )1(1)0(2B B '=' 即：2301P P Q Q -=- 这也表明，1032),(,Q Q P P 三点共线。如下图表示了一条3次B 样条曲线的所有控制多边形： 1 ) P 2 P 3 P 4 (P 11 12 ) P 5 P 10 0 P 6 P 9 7 P 8 图5.3次B 样条曲线和所有控制多边形 图5中，P0至P6为原始3次B 样条曲线控制多边形顶点，P 0至P 12 是计算后最终形成B 样条曲线控制多边形顶点。 图6.双二次（2x2）B 样条曲面 6.B 样条曲线曲面和NURBS 曲线曲面的C 语言实现算法源程序 #ifndef _mynurbs_h #ifndef _MYNURBS_H
#include "gl\gl.h" #include "math.h" //*-*-*-*-*-*-*-*-*-*-*-*-*-*-* B样条基函数计算部分 *-*-*-*-*-*-*-*-*-*-*-*-*-* //确定参数u所在的节点区间下标 //n=m-p-1 //m为节点矢量U[]的最大下标 //p为B样条函数次数 int FindSource(int n,int p,float u,float U[]) { int low,high,mid; if(u==U[n+1])//特殊情况 return n; //进行二分搜索 low=p; high=n+1; mid=(int)(low+high)/2; while(u 自动网格生成法 二维网格生成—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的表达式将简化为： 四、B 样条曲线与曲面 Bezier 曲线具有很多优越性，但有二点不足： 1）特征多边形顶点数决定了它的阶次数，当n 较大时，不仅计算量增大，稳定性降低，且控制顶点对曲线的形状控制减弱； 2）不具有局部性，即修改一控制点对曲线产生全局性影响。 1972年Gordon 等用B 样条基代替Bernstein 基函数，从而改进上述缺点。 Ｂ样条曲线的数学表达式为： ∑=+?= n k n k k i n i u N P u P 0 ,,) ()( 在上式中，0 ≤ u ≤ 1； i= 0, 1, 2, …, m 所以可以看出：Ｂ样条曲线是分段定义的。如果给定 m+n+1 个顶点 Pi ( i=0, 1, 2,…, m+n)，则可定义 m+1 段 n 次的参数曲线。 在以上表达式中： N k,n (u) 为 n 次B 样条基函数，也称Ｂ样条分段混合函数。其表达式为： ∑ -=+--+??-=k n j n j n j n k j k n u C n u N 0 1,)()1(!1)( 式中：0 ≤ u ≤1 k = 0, 1, 2, …, n 1．均匀B 样条曲线 1 一次均匀B 样条曲线的矩阵表示 空间n+1个顶点 i P （i = 0，1，…，n ）定义n 段一次（k ＝0,1，n=1）均匀B 样条曲线，即每 相邻两个点可构造一曲线段P i （u ），其定义表达为： []10 ;,...,1 0111 1)(1≤≤=??? ?????????-=-u n i u u P i i i P P ＝（1－u ）P i －1 ＋ u P i ＝ N 0，1（u ）P i －1 ＋ N 1，1（u ）P i 第i 段曲线端点位置矢量：i i i i P P P P ==-)1(,)0(1，且一次均匀B 样条曲线就是控制多边 形。 关键字：柴油机有限元网格 在计算机交互辅助设计中常常要进行多方案的结构有限元对比分析计算，三维有限元实体网格的划分及修改是一项极为繁琐的工作.目前的有限元软件对复杂柴油机的零部件，如活塞、机体、缸盖等结构的前处理功能有一定局限［1］，本研究以几种典型的柴油机的零部件为例讨论三维有限元网格生成算法，通过采用这些方法可进行三维有限元网格辅助生成修改工作. 1轴对称结构模型的有限元网格自动生成 轴对称结构也是工程设计中常用的零件结构，在柴油机中活塞可视为轴对称结构.图 1 为轴对称结构体有限元三维网格沿着z轴旋转，即可形成轴对称结构体的三维有限元网格。这一三维有限元网格自动生成算法简单、实用，可用于完成大多数轴对称结构有限元网格的自动生成.图 2 为6108 型柴油机活塞的三维网格模型（四分之一模型）.低散热气缸盖的气道口及气门座镶圈等部分也可用这一算法自动生成. 图1轴对称结构体（缸套）三维网格.模型的自动生成 图2活塞的三维网格模型 2特殊形状零件的有限元网格自动生成 由于柴油机零件的形状千差万别，不同形状零件要求采用不同的算法对其生成网格，下面以气缸盖排气道为例，叙述特殊形状零件的网格生成算法.排气道是气缸盖中最复杂的部分之一，低散热气缸盖又增加了陶瓷隔热层和耐热钢衬套，陶瓷的厚度仅0.7～1.5mm,结构更为复杂，无论是手工划分还是计算机生成都较为困难.为了采用计算机辅助生成陶瓷隔热层三维网格，首先需对气道表面进行表面网格划分，形成类似于边界元分析的表面网格，作为三维网格生成的基础，然后再进一步生成三维网格. 2.1计算机辅助三维网格生成算法 由表面网格生成三维网格，要向表面a内侧法向量n方向、距离为L （气道壁厚）处增加一个新表面从而形成三维网格［2，3］.已知平面法矢量n(i,j,k) 和平面上任一点r(x0, y0, z0)，原平面方程为 (x-x0)i+(y-y0)j+(z-z0)k=0, 即n(r-r0)=0.平面沿n方向平移L，平面上一点r(x0, y0 ,z0) 的新坐标为，则新平面方程为： (x-x1)i+(y-y1)j+(z-z1)k=0. 由于新的表面各节点位置已经改变（即新表面位置已知，但四个节点位置未知），问题的关键即转化为求新的节点.为找出新的节点，可将与单元相邻的各单元新表面找出，若相交则可得交线，交线相交得交点，即为所求新表面的节点，见图 3.其中节点的坐标(x,y,z) 可由 第一章介绍 ICEM CFD 工程 Tutorials目录中每个工程是一个次级子目录。每个工程的目录下有下列子目录：import, parts, domains, mesh, 和transfer。他们分别代表： ? import/: 要导入到ICEMCFD中的集合模型交换文件，比如igs，STL等； ? parts/: CAD模型 ? domains/: 非结构六面体网格文件(hex.unstruct), 结构六面体网格分区文件(domain.n), 非结构四面体网格文件(cut_domain.1) ? mesh/: 边界条件文件(family_boco, boco)，结构网格的拓扑定义文件(family_topo, topo_mulcad_out), 和Tetin几何文件(tetin1). ? transfer/: 求解器输入文件(star.elem), 用于Mom3d.的分析数据 mesh目录中Tetin文件代表将要划分网格的几何体。包含B-spline曲面定义和曲线信息，以及分组定义 Replay 文件是六面体网格划分的分块的脚本 鼠标和键盘操作 第二章ICEM CFD Mesh Editor界面 The Mesh Editor, 创建修改网格的集成环境，包含三个窗口 ? The ICEM CFD 主窗口 ? 显示窗口 ? The ICEM CFD 消息窗口 主窗口 主窗口中除了图形显示区域，外，还有6个radio按钮：File, Geometry, Meshing, Edit Mesh and Output. The File Menu The File menu 包含 ? Open, Save, Save as, Close, Quit, Project dir, Tetin file, Domain file, B.C file, Import geo, Export geo, Options, Utilities, Scripting, Annotations, Import mesh, DDN part. B样条曲线曲面的性质及其生成算法的研究 XXX （XXX学院数学与信息科学学院05级信本（2）班） 摘要 从B样条曲线曲面的定义入手，阐述了B样条曲线曲面的性质，在生成算法中提出了一个扩展B样条曲线曲面的新方法.扩展B样条曲线曲面的关键是为新增加的点确定节点值.生成算法的基本思想是:首先，B样条曲线和扩展部分在连接点处满足2 GC连续，用能量极小化方法确定扩展部分的曲线形状，通过对曲线重新参数化使两部分曲线满足2 C连续，进而确定新增加点的节点值.文章还讨论了运用该方法进行B样条曲面扩展，且以实例对新方法与其它方法进行了比较. 关键词：B样条曲线; B样条曲面;参数化;曲线扩展 Research On The Nature Of B-spline Curves And Surfaces And Their Generation Algorithm Yongning Zhang College of Mathematics and Information Science , Xianyang Normal University , Information Class 05(2) Abstract First, the definitions of B-spline curves and surfaces are introduced, and then the nature of B-spline curves and surfaces are studied. On the final, a new generation algorithm on expansion of B-spline curves and surfaces is proposed. The key thought of expansion of B-spline curves and surfaces is to determine the value of the new points. The basic idea of generation algorithm is: First of all, B-spline curve and the extension of the connecting points in a row to meet with the energy minimization method to determine the extension of the curve shape of the curve through re-parameterized so that the two parts meet the continuous curve, and then determine the new value of the node points. The article also discussed the use of the method of B-spline surfaces expansion, and compared an example of the new method with other methods. Keywords: B-spline curve; B-spline surfaces; parameter; curve extension B样条曲面的算法生成及研究 本文由天空乐园大学生旅游网整理分享 摘要 本文主要介绍B样条曲面的性质、算法、以及应用，让我们对B样条曲面有一个全面的了解。Ｂ样条曲面不仅在保留了Bézier曲面的优点的同时克服了由于整体表示带来的不具有局部性质的特点，而且成功地解决了样条函数的局部控制问题，轻而易举地在参数连续性上解决了贝奇尔方法的连接问题，是最广泛流行的形状数学描述的主流方法之一。B样条曲面中均匀双三次B样条曲面又是各种B 样条曲面中应用最多的一种之一，它避免了B 样条递推定义的繁琐算法，只要给出的空间型值点大致均匀，即可生成空间任何形状的曲面。而非均匀有理B样条曲面( NU RBS ) 是曲面构造的常用工具, 是目前工业界曲面曲线表示的数学标准。B-样条曲面是一种特殊NU RBS , 在实际应用中是首选形式。在本文中我们主要介绍了均匀双三次B样条曲面。 关键词：B样条曲面非均匀B样条曲面双三次均匀B样条曲面 B样条基函数 1 引言 计算机运用技术的不断发展使得CAD/CAM技术日益提高和完善,为实现工业生产过程自动化展示了光明的前景。目前,利用程序系统对某一产品实现机辅设计和数控加工的自动化过程已经开始。然而在实际生产中,数控机床的使用还很不普遍,大部分数控机床仍靠手工编程来实现单一加工。这除了数控设备价格昂贵之外,控制程序系统的设计难度较大也是重要原因之一。譬如,对数控铣削加工控制程序系统的设计,尤其是在数控铣床上加工任意形状曲面的程序系统设计, 目前还处于探讨摸索之中。随着汽车、船舶、航空工业的发展，对于工业产品的形状描述也就提出了越来越高的要求。工业产品的形状大致可以分为两类：一类是仅有初等解析曲面，例如平面、圆柱面、圆锥面、球面以及它们组合而成的规则曲面；另一类是不能由任何解析表达的自由型曲面。汽车、船舶、飞机的外部零件基本上都是自由曲面。而自由曲面不能由画法几何与机械制图表达清楚，成为摆在工程师面前首要解决的问题。De Boor（德布尔）与1971年给出了关于B 样条的一套标准算法。美国通用公司的戈登和里森费尔德于1974年将B样条理论应用于形状描述，提出了B样条曲线曲面。它将成功地解决了样条函数的局部控制问题，又轻而易举地在参数连续性上解决了贝奇尔方法的连接问题，是最广泛流行的形状数学描述的主流方法之一。该算法能显著提高效率。现在提出了B 样条曲面等测投影的建立方法，讨论用高性能的动态数组和Excel 软件存储任意数量控制点的实现方法等关键技术。采用Visual C++6.0 为编程工具开发软件系统，实现了任意数量控制点的双三次B 样条曲面生成。B 样条曲面在保留了Bezier 曲面的优点的同时，又克服了由于整体表示带来的不具有局部性质的特点，是目前工程中应用最多的一种曲面，有人甚至称之为“统一当代的B 样条曲面”。而均匀双三次B 样条曲面又是各种B 样条曲面中应用最多的一种之一，它避免了B 样条递推定义的繁琐算法，只要给出的空间型值点大致均匀，即可生成空间任何形状的曲面。随着B 样条方法，NURBS，的产生和发展,曲面的样条表示形式逐渐被引入到曲面设计中，较早的有Bloor 等使用B 样条作为双调和方程的解. 后来, Terzopoulos 等[提出了一种动态NURBS方法,其用一个二阶微分方 程来决定DNURBS 的演化,但该方程不是几何内蕴的,且无法获得NURBS片的 G1光滑拼接.最近,徐国良[12 ] 提出一种新的方法,通过整合B样条曲面和一般形 有限元网格自动生成的并行区域划分算法 作者：呙嘉妮胡久乡卢正鼎 摘要：提出了一种基于网格生成递归法的并行区域划分算法，该算法依据网格生成代价的估算分析，采用迭代分解法对区域进行并行划分。在曙光1000A 系统上的运行结果表明，该网格算法的效率和加速比均优于串行递归算法。 关键词：有限元网格；并行区域划分算法；网格生成代价；迭代分解法 基于网络生成递归法［1～3］，本文提出了一种并行区域划分算法，该算法满足以下四个基本原则：a. 任务平衡性原则。能生成平衡的子区域集，即在各子区域中生成网格的时间大致相等。b. 边界最简原则。子区域的边界结构简单，边界处理所需时间短，处理器间消息传递的费用低。c. 网格均匀原则。并行生成的最终网格形状均匀，无奇异单元。d. 区域划分代价最小原则。区域划分算法本身的代价尽可能小。 1、基本思想及相关算法 在网格生成递归法中，如果每个子区域都包含相同的单元数，就比较容易实现任务平衡。因此，首先按照单元数估算待处理区域的网格生成代价，然后根据当前参与并行处理的处理器数N对区域进行分解，并对分解所得子区域进行边界处理，最终获得相互之间既平衡又独立的N个并行子任务。 1.1网格生成代价的估算算法 网格生成代价与分布于待处理区域中的单元数目紧密相关，而单元数目是由该区域的总面积S和区域内单元分布密度决定的。估算公式如下： G=S/Stri，（1） Stri=［L2/(2M2)］sin60°，（2） M=Σ2li/(di1+di2) (i=1，2，…，n)，（3） 式中，G表示三维平面区域(含有n条边) 的网格生成代价；S表示该区域的面积；Stri 是 实验四：B 样条曲面 一.实验目的 用多个B 样条曲线画出一个曲面，并能实现鼠标球滚动。 二.算法思想 B 样条曲面是B 样条曲线的拓广。一块m ?n 次B 样条曲面片的数学表示式：)()(),(,,00 w F u F P w u P n j m i m i n j ij ∑∑=== w u , ∈［０，１］ 式中，ij P （i =0,1,2，…..,m; j =0,1,2,…..n ）是定义此曲面片的顶点位置向量矩阵，共计（m+1） （n+1）个顶点。)()(,,w F u F n j m i 为B 样条基底函数，w u ,为参数。显然，m 与n 不一定相等，如m=n=3,则由4?4个顶点构成特征多面体，其相应的B 样条曲面片称为双三次 B 样条曲面片。其中： m i m i m k k m i k i m u c m u F )()1(!1 )(10 ,--+-= +-=∑ )! 1(!)!1(1i m i m C i m -++= +其中： 展开三次B 样条曲面数学表达式并写成矩阵 ()()( ) () T T s T s W M w w w w F w F w F w F UM u u u u F u F u F u F w F w F w F w F p p p p p p p p p p p p p p p p u F u F u F u F w u Q =?????? ? ??????????????----= =????? ???????----=????????????????????? ???=100 1 13334063133161)() ()() (01 4 1 03030 3631331611 )() ()() ()()()()()() ()() (),(2343212 3 432143213332 31 30 2322212013121110 030201004321其中： 三.程序主要代码 #include 图6.双二次（2x2）B 样条曲面 6.B 样条曲线曲面和 NURBS 曲线曲面的C 语言实现算法源程序 #ifndef _mynu rbs_h #ifndef MYNURBS H 学习小结：前面学习了 Bezier 曲线，B 样条基函数和 B 样条曲线的一些基础知识。掌握关 键问题是一条B 样条曲线间的多段曲线的光滑连接。因为现在是用多段 Bezier 曲线来描绘 一条B 样条曲线，所以问题变为两段 Bezier 曲线间光滑连接。两段 Bezier 曲线段（3次） B1和B2光滑连接的条件： （1） .要求B1和B2有共同的连接点，即 &连续。 （2） .要求B1和B2在连接点处有成比例的一阶导数，即 G 连续。由端点处的一阶导数 1 B1(1) 3(F 3 P 2), B 2(0) 3(Q i Q 。) ，为实现 G 连续，则有: B 2(0) B1(1) 即: Q 1 Q o R P 2 这也表明，P 2, B （Q o ）,Q 三点共线。如下图表示了一条 3次B 样条曲线的所有控制多边形: E(P 1) P2 (P / P 用P 0 10 P4 图5.3次B 样条曲线和所有控制多边形 图5中，P0至P6为原始3次B 样条曲线控制多边形顶点， P 0至P 12是计算后最终形成 样条曲线控制多边形顶 点。 #include "gl\gl.h" #include "math.h" //* ************* B样条基函数计算部分************** // 确定参数u 所在的节点区间下标 //n=m-p-1 //m 为节点矢量U[] 的最大下标 //p 为B 样条函数次数 int FindSource(int n,int p,float u,float U[]) { int low,high,mid; if(u==U[n+1])// 特殊情况return n; // 进行二分搜索 low=p; high=n+1; mid=(int)(low+high)/2; while(u自动网格生成法
B样条曲线与曲面
有限元网格自动生成及修改方法
计算流体力学ICEM CFD 网格生成基础教程
B样条曲线曲面的性质及其生成算法的研究
b样条曲面
有限元网格自动生成的并行区域划分算法
b样条曲面
B样条曲线曲面和NURBS曲线曲面C语言算法源程序
相关主题
文本预览