孙殿柱,朱昌志,李延瑞,牛宗伟

(山东理工大学机械工程学院,淄博 255091)

逆向工程中,为便于对三角网格模型进行编辑、造型,通常将 1个三角网格分为多个,即网格分割.现有的方法主要基于曲率对网格模型进行自适应分割[1-3],将曲率值相近的三角面片划为同一区域,该方法不能根据设计意图自由选取分割边界,适应性差.

文献[4]提出基于最短路径的三角网格交互式分割算法,由用户指定分割线的起点和终点,采用 Dijkstra算法在指定区域内计算 2个点间的最短路径,以该路径为分割线,对三角网格进行分割,对于型面特征复杂的三角网格,该算法难以快速有效地选择分割线所在区域,计算最短路径时,需遍历较多的三角面片,算法运行量大,且该方法在分割面处会产生锯齿现象,不能准确地表达分割后模型的边界信息.

针对上述问题,本文提出一种根据设计意图的三角网格模型自动分割算法,该算法采用 R*-tree(recangle*-tree)建立三角网格空间索引结构,基于该结构,采用深度优先遍历方法快速准确地查询与分割面相交的三角面片,对相交三角面片进行分割并重新剖分,实现三角网格模型不受曲率等条件限制的自动分割,该算法可对各种复杂型面三角网格进行分割,算法运行效率高,且能有效避免分割区域的锯齿现象.

1 三角网格空间索引结构

采用 R*-tree[5-7]建立三角网格空间索引结构,依据 MBR(m inimum bounding rectangle)体积增量衡量几何对象间的相似性,若局部三角面片平行于坐标平面分布,结点 MBR体积增量为 0,导致 R*-tree结点分裂失效,破坏了结点间的聚合性.针对上述问题,将三角面片及索引结点 MBR统一表示为四维点对象(x,y,z,r),其中,x,y,z为 MBR中心坐标,r为 MBR外接球半径值,采用 k-means算法[8]对 R*-tree各层结点进行空间聚类分簇,建立三角网格空间索引结构,实现三角网格的动态存取及相交三角面片的快速查询.

图1为维纳斯头部三角网格曲面模型的空间索引结构,该结构由 4种结点组成,最上层为根结点,最底层为数据结点,次底层为叶结点,其余为内部结点,每个数据结点存储 1个三角面片.

2 相交三角面片的查询

索引结点 MBR的顶点为 vi(1≤i≤8),q为分割面上任意点,n为分割面的法向量,采用式(1)判断索引结点与分割面的位置关系,即

图1 维纳斯头像网格模型的空间索引结构Fig.1 Spatialindexstructureoftriangularmesh

若 εi＜0,表示索引结点位于分割面负侧;若 εi＞0,表示索引结点位于分割面正侧.如图 2(a)所示,若索引结点 8个顶点的 εi值均为正(或负),则表示索引结点与分割面相离;如图 2(b)所示,若 εi值不全部为正(或负),表示索引结点与分割面相交.基于以上判断法则,获取分割面相交三角面片的具体步骤为:1)输入 R*-tree根结点;2)如果输入结点为数据结点,判断该结点与切片的位置关系,若相交,则执行步骤 3),否则执行步骤 4);3)依据三角面片的顶点与分割面的位置关系判断其是否与分割面相交,若相交,则将其添加到序列 L中;4)若结点为内部结点,则循环取当前结点的子结点,执行步骤 2).基于三角网格空间索引结构,采用深度优先遍历方法获取与分割面相交的三角面片,如图 3所示,其中,深色所示为与分割面相交的索引结点或三角面片,可以看出,本文算法只对少数三角面片进行相交判断,显著减小了数据处理量.

图2 索引结点与分割面的位置关系Fig.2 Therelationshipbetweenindexnodeandsliceplane

图3 相交三角面片的获取Fig.3 Acquireofintersectiontriangles

3 相交三角面片的剖分

针对图 4所示三角面片与分割面的位置关系,制定 5组方案对相交三角面片进行剖分,具体为:1)如图 4(a)所示,若 1个顶点位于分割面上,其余 2个顶点位于分割面同侧,则不对该三角面片进行剖分;2)如图 4(b)所示,若 1个顶点位于分割面上,其余 2个顶点位于分割面异侧,则将△ABC分为△ABD和△BCD;3)如图 4(c)所示,若三角形的 3个顶点分别位于分割面的两侧,则将其分为 3个三角形;4)如图4(d)所示,若三角面片有 2个顶点位于分割面上,则不对其进行剖分;5)如图 4(e)所示,若三角面片的 3个顶点均位于分割面上,即三角面片所在平面与分割面重合,则不对其进行剖分.

图4 三角面片与分割面的位置关系Fig.4 The relationshipbetween triangle and section plane

4 应用实例

制定 2组方案对本文算法进行验证:

方案 1中,采用文献[4]算法及本文算法对图 5(a)所示摩托车油箱三角网格模型进行分割,该模型的三角面片数为 10111,从图 5中可以看出,文献[4]算法以相交三角面片的边作为相交边界,分割后的模型在分割面处出现了锯齿现象,边界特征不明显,本文算法对相交三角面片进行分割与重构,有效避免了此问题.

图5 摩托车油箱模型的分割效果Fig.5 Partition result of oil box

方案 2中,采用文献[4]算法及本文算法对图 6所示三角网格模型进行分割,模型的三角面片数分别为 9412、56 459、69 474、1765388,运行时间如表 1所示.从表 1中可以看出,本文算法的运行效率明显高于文献[4]算法,平均提高 2～3倍.

图6 三角网格模型Fig.6 Triangularmesh models

表1 2种算法的运行时间比较Tab le 1 Running time of different algorithms s

5 结论

1)基于 R*-tree建立三角网格模型动态空间索引结构,可对各种复杂型面三角网格模型进行分割,算法适应性强;

2)基于三角网格空间索引结构,采用深度优先遍历方法可快速准确地获取与分割面相交的三角面片,提高了算法运行效率,平均提高 2～3倍;

3)对分割面相交三角面片进行剖分与重构,避免了分割面处的锯齿现象.

[1]吕汉明,王扬.采用混合策略的三角网格模型区域划分算法[J].华中科技大学学报:自然科学版,2007,35(增刊):54-57.LÜHan-ming,WANG Yang.Using hybrid strategy to partition trianglemeshes[J].Journal of Huazhong University of Science and Technology:Nature Science Edition,2007,35(Supp.):54-57.(in Chinese)

[2]孟敏,计忠平,刘利刚.基于保特征调和场的交互式网格分片[J].计算机辅助设计与图形学学报,2008,20(9):1146-1152.MENG Min,JI Zhong-ping,LIU Li-gang.Interactive mesh segmentation based on feature preserving harmonic field[J].Journalof Computer-Aided Design＆Computer Graphics,2008,20(9):1146-1152.(in Chinese)

[3]VANCO M,BRUNNETT G.Towards automatic segmentation in reverse engineering[C]//Proceeding of the International Symposium on Cyberworlds.Tokyo:[s.n.],2002:24-32.

[4]神会存,周来水,安鲁陵,等.曲面三角网格模型顶点法矢计算与交互式分割[J].计算机辅助设计与图形学学报,2005,17(5):1030-1033.SHEN Hui-cun,ZHOU Lai-shui,AN Lu-ling.Vertex normal calculation and interactive segmentation of triangle mesh[J].Journal of Computer-Aided Design＆Computer Graphics,2005,17(5):1030-1033.(in Chinese)

[5]孙殿柱,李心成,范志先,等.采用R*-tree的三角网格曲面非均匀精简算法[J].西安交通大学学报,2008,42(9):1179-1183.SUN Dian-zhu,LIXin-cheng,FAN Zhi-xian,etal.Research on simplification algorithm for triangularmesh surface based on R*-tree[J].Academic Journalof Xi'an Jiaotong University,2008,42(9):1179-1183.(in Chinese)

[6]郭薇,郭菁,胡志勇.空间数据库索引技术[M].上海:上海交通大学出版社,2006:237-243.

[7]BECKMANN N,KRIEGEL H P,SCHNEIDER R,et al.The R*-tree:an efficient and robust accessmethod for points and rectangles[J].ACM SIGMOD Record,1990,19(2):322-331.

[8]BRAKATSOULAS S,PFOSER D,THEODORIDIS Y.Revisiting R-tree construction principles[C]//ADBIS.Bratislava,Slovakia:[s.n.],2002:149-162.