2022年采用R_tree的三角网格曲面非均匀精简算法参考 .pdf

第 42 卷 第 9 期2008 年 9 月 西 安 交 通 大 学 学 报JOU RNALOF XIAN JIAO TON G UN IV ERSIT YVol. 42 9Sep. 2008采用R32tree的三角网格曲面非均匀精简算法孙殿柱 , 李心成 , 范志先 , 田中朝(山东理工大学机械工程学院, 255091 ,山东淄博)摘要 : 提出了一种三角网格曲面非均匀精简算法. 该算法采用R32tree 组织三角网格曲面的空间拓扑结构 ,实现了三角面片拓扑邻域的快速查询.结合三角网格曲面模型的曲率分布状况,对三角网格曲面进行聚类分簇处理,通过对分簇网格进行局部精简,实现了三角网格曲面模型的整体保形性精简 .与同类精简算法的对比实验表明,该算法的数据适应性强,有效地保留了三角网格曲面的型面特征 ,精简后的网格模型与原网格模型的面片偏差降低了20 %45 % ,精简时间减少了10 %35 %.关键词 : R32tree ;三角网格曲面;非均匀精简中图分类号: TP391172 文献标志码: A 文章编号 : 02532987X(2008)0921179205Simplif ied AlgorithmforTriangularMesh Surface Based on R32treeSUN Dianzhu , L I Xincheng , FAN Zhixian , TIANZhongchao(School of MechanicalEngineering , Shandong Universityof Technology , Zibo , Shandong 255091 , China)Abstract : A new simplifiedalgorit hm for triangularmesh surface is proposed , which organizest he topologicalstruct ure of the triangular mesh surface based on R32tree spacial index struct ure toinquire the topologicalneighborhoods of the triangularmesh surface.Then the triangularmeshsurface is discreted into many clusters by the triangularmesh surface feat ures , and t he triangularmesh surface is ununiformlysimplified throughout t he clusters.The stronger adaptabilityis veri2fied and thefeat ures of the triangularmesh surface is remained effectively.It is found that the de2viation is reduced by 20 %245 % , and the computing period is subtracted by 10 %235 % comparedwit h the existing algorit hms.Keywords: R32tree; triangularmesh surface ; ununiformsimplification在逆向工程技术中,产品的数字化模型常由测量原型获得,三角网格曲面因其快速灵活、 拓扑适应能力强而被经常采用. 随着扫描设备的发展,表示产品的三角网格曲面越来越复杂,包含三角面片的数量十分庞大,这样的三角网格曲面在绘制、 显示 、 编辑时相当困难,因此对三角网格曲面进行精简,可有效降低冗余度,提高数据预处理的效率. 目前 ,常用的三角网格曲面精简算法有顶点聚类法、 折叠边法 、折叠面法 、 删除面法及包络网格法,其中顶点聚类精简方法又分为空间聚类精简和拓扑聚类精简. 文献1 采用空间栅格来划分三角网格曲面的模型,通过合并栅格内的三角网格实现了均匀精简.文献 2采用八叉树划分三角网格曲面的模型,通过合并八叉树叶结点内的三角网格实现了均匀精简.这2种方法均属于空间聚类精简算法,其精简过程仅依赖于原模型三角面片的空间位置信息,与三角面片之间的拓扑信息无关,因此精简结果不能有效保留原模型的型面特征. 拓扑聚类精简算法 324 采用 Lawson三角形表 (L TL ) 数据结构 5来组织三角网格曲面的拓扑结构,将拓扑邻域三角面片聚类做了精简.该方收稿日期: 2007212228.作者简介:孙殿柱( 1956 - ) ,男,教授.基金项目:国家高技术研究发展计划资助项目(2006AA04Z105) .名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 法可有效保留原模型的型面特征,实现非均匀精简,但算法却耗费大量的系统资源,运行效率也较低.针对以上算法的不足,本文采用R32tree 实现了三角网格曲面数据的索引及存储结构,基于该结构能够快速获取三角面片的拓扑邻域. 结合三角网格曲面模型的曲率分布状况,对三角网格曲面进行聚类分簇处理,再通过对分簇网格进行局部均匀精简 ,实现了三角网格曲面模型的整体保形性精简. 该算法在保留模型细节特征的基础上,可快速有效地去除三角网格曲面模型中的冗余信息.1三角网格曲面空间拓扑结构的建立本文将 R32tree 由二维数据索引结构6扩展为三维数据索引结构,建立了三角网格曲面动态空间存取模型,由此可快速获取三角面片的拓扑邻域.R32tree 有内部结点、 叶结点和数据结点,指定内部结点和叶结点存储元素的最小个数m和最大个数M ,且mM+ 12.内部结点的元素采用其所有子结点的最小包围矩形(MBR)来表示,所有叶结点在树的同一层(见图 1) .A、B、C、D、E、F、X、H、I、Y、K、W、J、P、Q、O、R:数据集结点图1R32tree空间索引结构采用数据点标识网格曲面中的三角面片,将数据标识点作为R32tree 数据结点,建立了三角网格曲面的空间拓扑结构:新建根结点,将数据结点插入叶结点;若叶结点中子结点个数大于M (结点溢出) ,则分裂该结点;判断分裂结点的上层结点是否溢出,若溢出则进行分裂操作.向 R32tree 插入数据结点时,可能会导致所在的一系列结点的MBR 发生变化,此时从 MBR 最先发生变化的结点开始,向上调整所有MBR 变化的结点,使 MBR 恰好包含所有子结点(见图 2) .采用深度优先遍历算法,快速定位数据结点所在的叶结点,再将空心球动态扩张算法应用于k近(a)标识点 (b)第2层结点 (c)第3层结点 (d)叶结点图2维纳斯头像空间索引结构邻查询算法7,获取 R32tree 叶结点内k个近邻数据结点,从而得到拓扑邻域三角面片,并为三角网格曲面的分簇处理提供了拓扑邻域.设查询数据结点为x , k个近邻点存于集合kn中,L为x所在叶结点的集合,则算法步骤如下.步骤 1 初始化kn,L为空,采用深度优先遍历算法确定x的所在叶结点.步骤 2 计算x所在叶结点的外接球半径r和空心球外径r2= rkM1/2(1)初始化内径r1为 0,球心为x.步骤 3 获取落入r2内的叶结点,并添加到L中.步骤 4 如L中有值,则对其中数据结点按其到x的距离排序,得到L,而L 中包含数据结点的个数为n.步骤 5 升序输出L 中落入空心球区域的数据结点,存入kn中,若kn中数据个数为k ,则返回kn,否则执行步骤6.步骤 6 更新r1=r2,根据下式计算r2的新值,即r2= r1k -nn+11/2(2)并执行步骤3.2三角网格曲面的分簇处理211 三角面片分簇邻域的获取采用空心球动态扩张算法,获取采样面片的拓扑邻域.根据采样面片偏离邻域几何中心的程度,将其分为边界邻域和内部邻域,如图 3 所示,图中的加(a)边界邻域( b)内部邻域 图3 边界邻域和内部邻域示意图0811西 安 交 通 大 学 学 报 第42卷 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 粗三角面片为采样面片.计算采样面片偏离邻域几何中心的程度= d/ r(3)式中: d为采样面片到m的距离.根据 将内部邻域作为采样面片的分簇邻域,其具体步骤如下:获取kn,计算kn的几何中心和半径;计算采样面片标识点到m的距离,根据式(3)计算 ;获取偏离度阈值,若 小于偏离度阈值,将集合kn分为一分簇邻域,在 R32tree 中删除kn标识点,否则执行步骤 ;清空kn,如算法结束,执行步骤,否则查询下一采样面片标识点的k近邻,执行步骤 ;查询游离面片,将其添加到距离最近的分簇邻域中.212 三角面片的分簇通过三角面片的分簇,识别三角网格曲面中曲率变化大的区域,如拐角 、 棱边 、 过渡边等区域.设三角面片 的顶点 为v1( x1, y1, z1) , v2( x2, y2, z2) ,v3(x3, y3, z3),其法矢=ijkx2-x1y2-y1z2-z1x3-x1y3-y1z3-z1(4)拓扑相邻的2 个三角面片的法矢为1(A1, B1, C1)和2(A2, B2, C2) ,两者的夹角=arccos|A1A2+ B1B2+ C1C2|( A21+ B21+ C21)1/2( A22+ B22+ C22)1/2(5)如图 4 所示,采样面片与其分簇邻域三角面片法矢的夹角可有效地反映局部型面的曲率变化情况.如图 4a 所示的区域a型面较为平坦,曲率变化小,采样面片与其分簇邻域三角面片的法矢夹角;区域c型面特征复杂,曲率变化大,采样面片与其两侧分簇邻域三角面片的法矢夹角.根据分簇邻域三角面片的法矢夹角来确定三角网格曲面的局部型面特征,将型面特征复杂的分簇邻域划分为若干簇,以保留三角网格曲面的型面特征.采用三角面片自适应扩张算法将法矢夹角大于的分簇邻域分为若干簇,其算法流程如图5 所示.以采样面片为中心,自适应扩张查询邻域三角面片,计算采样面片的法矢夹角,将夹角大于的三角面片进行自适应分簇;以分簇后三角面簇中位于几何中心的三角面片为采样面片,求出与面簇内其他三角面片的法矢夹角,并迭代自适应分簇.如图 4b 所(a)分簇邻域型面特征(b)型面特征的自适应分簇、:法矢夹角; a、b、c:分簇邻域图4自适应分簇示意示 ,区域 a分为一簇,区域 b 分为两簇,区域 c 分为三簇 ,通过三角面簇的自适应分簇,三角网格曲面曲率变化小的区域三角面簇数量少,曲率变化大的区域三角面簇数量多.图5三角面片自适应扩张算法的流程3三角面簇的精简311 三角面簇顶点均值的计算设三角面簇中三角面片的个数为n,三角面片的顶点坐标为( xi, yi, zi) (1 in) ,面簇顶点的坐标均值的计算式为x =ni = 1xi/ n,y =ni =1yi/ n,z =ni =1zi/ n(6)312 面片的形状控制为避免三角面簇精简过程中生成狭长三角面片,采用单位面积形状控制法8来控制面片形状.以单位面积的等边三角形为参考对象,计算其周长为41559 014 113 9 mm,并将周长作为比例常数k.设任意形状三角形的面积为s,周长为p ,根据下式可确定形状因子1811第9期 孙殿柱,等:采用R32tree的三角网格曲面非均匀精简算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - q = k( s1/2/ p)(7)由此知,等边三角形的形状因子为1,非等边三角形的形状因子均小于1,而且三角形越狭长形状因子越小.313 三角面簇精简算法流程如图6所示,将v1v3按照逆时针的顺序连接生成三角面片t ,根据式(7)计算q,指定的形状阈值为Q,生成的三角网格曲面为s.如果生成三角面片的形状因子小于Q ,采用加点法调整三角面片,将t最长边的中点与不共边的顶点相连,得到 2 个新三角面片,再分别计算这2 个三角面片的形状因子,若计算结果小于Q则继续加中点调整.图6三角网格曲面精简算法流程通过三角面簇的精简,使三角网格曲面型面平坦的区域保留的三角面片数量少,而型面复杂的区域保留的三角面片数量多,这样在精简掉大量冗余三角面片的基础上,有效地保留了三角网格曲面的型面特征.4应用实例在硬件环境为Intel P4,CPU 为 2 GHz ,内存为256 MB 的 PC机上,应用文献1、 文献3和本文算法分别对米老鼠和维纳斯网格模型进行了测试,图 7图 10 为应用这些算法对2 种模型精简55 %和 40 %的效果比较.可以看出,文献1算法在精简的同时丢失了一些重要的型面特征,如图 8a 中米老鼠的眼眶特征,图 8b 中维纳斯的眼睛和嘴部特征.文献3算法基本保留了原网格模型的型面特征,但型面特征变化不大的区域却保留了大量的冗余面片,如图 9a 中米老鼠眼睛周围的区域,图 9b 维纳斯的前额和面颊区域.图 10 为采用本文算法实现表 1 精简时间和面片偏差的比较模型原始面片个数精简后面片个数精简算法面片偏差/ mm精简时间/ s米文献 101205 021421 3老40 5452 277文献 301260 231050 7鼠本文01152 621050 3维文献 101065 521374 3纳39 6792 301文献 301081 021820 5斯本文01040 311830 4(a)米老鼠模型(b)维纳斯模型图7 原始模型(a)米老鼠模型(b)维纳斯模型图8文献 1算法的精简效果(a)米老鼠模型(b)维纳斯模型图9文献 3算法的精简效果2811西 安 交 通 大 学 学 报 第42卷 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 的米老鼠和维纳斯模型的非均匀精简,在维纳斯模型的前额和面颊等型面平坦的区域精简了较多的三角面片,在维纳斯模型和米老鼠模型的眼睛、 嘴部等型面特征复杂的区域,精简了较少的三角面片.表 1为上述 3 种算法对米老鼠模型精简94138 %,以及对维纳斯模型精简9412 %时的面片偏差和时间比较.从表中可以看出,本文算法与文献1和文献3算法相比,精简后的网格模型的面片偏差最小且精简速度最快.(a)米老鼠模型(b)维纳斯模型图10本文算法的精简效果5结 论本文算法与相关算法相比,具有以下优点.(1) 采用R32tree 组织三角网格曲面的空间拓扑结构 ,不仅实现了三角面片拓扑邻域的快速查询,而且对于型面复杂的三角网格曲面具有比较强的适应性 .(2) 根据三角网格曲面的曲率变化来过滤三角面簇 ,可有效地保留三角网格曲面的型面特征,并实现了三角网格曲面的非均匀精简,精简后的网格模型比原网格模型的面片偏差降低了20 %45 %.(3) 采用 R32tree 深度优先遍历机制,可快速查询三角面片的拓扑邻域,并且将精简时间减少了10 %35 %.参考文献 : 1ROSSIGNACJ ,BORRELP. Multi2resolution3D ap2proximationforrenderingcomplex scenes M Falci2dieno B , KuniiT L. Modelingin ComputerGraphics.NewYork :Springer2Verlag ,1993 :4552465. 2周昆,潘志庆,石教英,等.一种新的基于顶点聚类的网格简化算法J .自动化学报,1999 ,25 (1) :128.ZHOUKun ,PANZhiqing ,SHIJiaoying.A new meshsimplificationalgorithmbased onvertexclusteringJ . Acta AutomaticaSinica ,1999 ,25 (1) :128. 3ISENBU R G M ,L INDSTROMP , GUM HOLDS,et al.Largemesh simplificationusing processingsequences CProceedings of IEEEVisualization.Piscataway ,NJ , USA : IEEE ,2003 :4652472. 4WU Jianhua , KOBB EL T L.A stream algorithmforthe decimationof massive meshes CProceedings ofGraphicsInterface.Halifax,Canada : NovaScotia ,2003 :1852192. 5田怀文,王金诺.表面重建中的三角网格简化方法J .西南交通大学学报,2002 ,37 (2) :1502153.TIANHuaiwen ,WANG Jinnuo.Simplificationmethodfortriangulationnetinsurfacereconstruction J .Journal of SouthwestJiaotongUniversity,2002 ,37 (2) :1502153. 6刘宇,朱仲英,施颂椒.空间k近邻查询的新策略J .上海交通大学学报,2001 ,35 (9) :129821302.L IU Yu ,ZHUZhongying,SHISongshu. Novelstrate2gy forspatialk2nn query J . Journalof Shanghai Jiao2tong University,2001 ,35(9) :129821302. 7BEC KMANNN , KRIEGELH P , SCHN EIDERR ,etal. The R32tree :an efficientand robustaccess methodfor pointsand rectangles CProceedings of Sigmod.NewYork , USA :ACM,1990 :3222331. 8LoS H. Delaunaytriangulationof non2convexplanardomains J .InternationalJournalforNumericalMethodsin Engineering,1989 ,28 (11) :269522707.(编辑 管咏梅 )本刊在线稿件处理系统正式开通运行,实行在线投稿 、在线审稿 、 在线查询和全文免费阅读.http :www. jdxb. cn3811第9期 孙殿柱,等:采用R32tree的三角网格曲面非均匀精简算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -