三角网格模型的动态空间索引结构_第1页
三角网格模型的动态空间索引结构_第2页
三角网格模型的动态空间索引结构_第3页
三角网格模型的动态空间索引结构_第4页
三角网格模型的动态空间索引结构_第5页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

三角网格模型的动态空间索引结构

三角网格模型可以快速准确地重建基于产品形状采样数据的云平面模型。现在,它被广泛应用于产品的逆向工程中。利用反向工程系统生成的三角网格模型进行统计,可以切割和连接网格曲线的模型,并构建复杂的网格模型。文献提出一种可靠的多面体布尔运算算法,采用多面体一致关系的判断和推理方法,根据顶点坐标判断多面体位置关系,实现网格模型的布尔运算.该算法虽然保证了形状规则、数据量少的网格模型布尔运算的可靠性,但对形状复杂、数据量大的网格模型其几何推理过程将耗费大量时间.文献采用邻接表作为网格模型数据结构,建立曲面模型中三角面片的包围盒,遍历包围盒获取相交的三角面片并计算其交线段,将所有交线段排序获取2个模型交线,根据交线剖分网格模型,实现网格模型的布尔运算.但该算法三角面片邻接表的建立及维护过程烦琐,需重复遍历邻接表计算交线段,算法运行效率低.文献采用非正则精确模型作为几何对象数据结构,基于该模型进行数据对象的层次求交,实现网格模型的布尔运算.该算法虽然避免了由于计算误差引起的裂纹以及拓扑生成的不一致,但非正则精确模型结构复杂,获取网格模型交线过程烦琐,求交速度慢.本文针对以上算法存在的不足,建立了三角网格模型的动态空间索引结构,并基于该结构快速获取2个三角网格模型的相交区域;求解相交区域内网格模型的离散交线段,并对其进行排序获取交线;根据交线细分相交三角面片,将三角网格模型沿交线分割成2个子网格模型,通过合并不同子网格模型实现三角网格模型的布尔运算.实例结果证明,本文算法可准确地定位三角网格模型中相交的三角面片,能够快速、准确地求解2个三角网格模型交线,可实现数据密集、形状复杂三角网格模型的布尔运算,有效地提高了网格模型的布尔运算效率.1基于r#-东北部的动态空间索引为了精确地表示复杂拓扑曲面,三角网格模型通常由大规模密集三角面片组成,为其建立合理的数据结构是高效实现网格模型中三角面片查找、求交、分割,以及合并等运算的先决条件.本文采用R*-tree动态空间索引结构并对其进行改进,建立三角网格模型的动态空间索引结构,有效地解决了三角网格模型数据结构的创建及动态维护等问题.1.1基于r#-to-b的结论聚类分簇算法R*-tree结点插入算法采用结点(minimumboundingrectangle,MBR)增量作为结点聚类分簇的判定条件.该算法应用于三角面片集合的空间聚类分簇时,若三角面片平行于坐标平面,结点MBR将由三维退化为二维,导致R*-tree结点插入失效,破坏了R*-tree结点的聚合性.为解决该问题,本文将三角面片及索引结点MBR统一表示为四维点对象(x,y,z,r),其中x,y,z为MBR中心坐标,r为MBR外接球半径值.1.2基于r#-toh-n-n-r#-zi,ri分簇中心本文采用k-means算法实现三角面片集合的空间聚类分簇.在选取初始分簇中心时,为减少k-means迭代次数,将结点中心距离最远的一对结点MBR中心作为初始分簇中心.确定初始分簇中心后,将数据对象添加到中心距其最近的分簇中.为使结点MBR均匀,避免出现结点MBR奇异,根据R*-tree定义,当分裂所得结点的子结点数k小于R*-tree最小子结点数m时,将另一簇中距离当前簇较近的m-k个结点插入到当前簇中,并调整分裂结果.采用k-means对R*-tree索引结点进行聚类分簇时,需要迭代定位最终的分簇中心.对于同簇结点中的N个索引结点,其四维标准化坐标为pi(xi,yi,zi,ri),i=1,…,N,分簇中心坐标(x¯,y¯,z¯,r¯)(x¯,y¯,z¯,r¯)由⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪x¯=∑i=1Nxi⋅ri∑i=1Nriy¯=∑i=1Nyi⋅ri∑i=1Nriz¯=∑i=1Nzi⋅ri∑i=1Nrir¯=∑i=1NriN(1){x¯=∑i=1Νxi⋅ri∑i=1Νriy¯=∑i=1Νyi⋅ri∑i=1Νriz¯=∑i=1Νzi⋅ri∑i=1Νrir¯=∑i=1ΝriΝ(1)计算.各索引结点至聚类分簇中心的距离d=[(xi−x¯)2+(yi−y¯)2+(zi−z¯)2+(ri−r¯)2]12(2)d=[(xi-x¯)2+(yi-y¯)2+(zi-z¯)2+(ri-r¯)2]12(2)图1所示为基于四维点表示的三角网格模型空间聚类分簇效果.2获得三角形网格模型的交线数据2.1交通流量不对称设参与布尔运算的2个三角网格模型为S1和S2,根据S1动态空间索引结构判断S2动态空间索引结构中结点MBR与S1的相交关系,若不相交,则不对S1和S2进行布尔运算;否则,继续比较S2子结点MBR与S1的相交关系,直至获取与S1相交的数据结点,该数据结点中存储的三角面片即为与目标三角网格模型相交的三角面片.图2所示为2个三角网格模型获取相交三角面片的过程.图2b~2d中实体显示部分分别为2个三角网格模型动态空间索引结构相交的第一层结点、叶结点和数据结点MBR.2.22个三角形所在平面的交线获取2个三角网格模型动态空间索引结构相交数据结点中存储的三角面片,将其求交获取交线段.为提高三角面片交线求解速度,将空间三角面片位置关系划分为以下3种情况.情况1.三角面片的3个顶点均在另一三角面片所在平面的同侧.情况2.2个三角面片共面.情况3.2个三角面片均与另一三角面片所在平面相交.若为情况1,表示2个三角形不相交,不进行求交运算;若为情况2,利用三角面片的3条边与另一三角面片求交获取2个三角面片交线段,将各交点平均值作为交点;若为情况3,计算2个三角形所在平面的交线l,通过l和2个三角面片求交获取交线段,确定交线段的端点对应于l上的参数值为t00,t01,t10和t11,其位置关系如图3所示.若t01≤t10或t11≤t00,则表示2个三角面片没有交线,如图3a所示;若t01>t10或t11>t00,则表示2个三角面片相交,如图3b所示.根据参数值分布求解2个三角面片交线段,令交线段的起点和终点对应直线l上的参数值分别为t0和t1,即t0={t10,t00≤t10t00,t00>t10(3)t1={t01,t01≤t11t11,t01>t11(4)t0={t10,t00≤t10t00,t00>t10(3)t1={t01,t01≤t11t11,t01>t11(4)2.32到起始段某终点距离为0的数据基点相交三角面片求交所获取的交线数据是一组杂乱无序的线段,需对其进行排序以形成完整的交线.本文采用改进后的R*-tree建立所获取的离散交线数据动态空间索引结构,并基于该索引结构各层结点的空间邻近关系实现交线数据邻近排序.步骤如下:Step1.以任一交线段为起始线段,查询离散交线数据动态空间索引结构中到起始线段某端点距离为0的数据结点.Step2.获取该数据结点中存储的交线段,连接该交线段与起始线段组成新的起始线段.Step3.查询离散交线数据动态空间索引结构中到新起始线段某端点距离为0的数据结点.若存在距离为0的数据结点,转Step2;否则,执行下一步.Step4.对当前交线数据排序完成后,输出2个三角网格模型一条交线.由于2个复杂三角网格模型交线不止一条,需重复执行上述步骤获取多条交线,最终生成2个网格模型交线.图4所示为2个三角网格模型交线的求解过程.步骤如下:Step1.线段E0为起始线段,查询R*-tree索引结构中到E0端点P0距离为0的数据结点MBR1,获取MBR1中存储交线段E1.Step2.连接E0与E1,并查询R*-tree索引结构中到E1端点P1距离为0的数据结点MBR2,获取MBR2中存储交线段E2.Step3.连接E1与E2,迭代查询R*-tree索引结构中数据结点,直至查询到所有交线段,最终生成2个网格模型一条交线.3角网格模型的建立基于交线将相交三角面片进行三角网格划分,可保证三角网格模型沿交线分成2个子网格模型,通过合并2个三角网格模型的指定子网格模型,实现两者的布尔运算.3.1角网格划分将交线段在三角面片内部的端点作为细分点,对三角面片进行三角细分.由于相交三角面片的空间位置是任意的,进行三维三角网格划分比较复杂.本文采用文献算法将三维三角网格划分问题转化到二维,对所有相交三角面片进行约束Delaunay细分,约束边界为交线段和三角面片的3条边.图5所示为相交三角面片的三角网格划分.3.2角网格模型的分割将细分后的三角面片添加到三角网格模型动态空间索引结构中,重新建立三角网格模型动态空间索引结构.以交线为公共边界的三角面片位于交线的两侧,遍历三角网格模型动态空间索引结构,自适应地扩张查找位于交线两侧的三角面片;以交线为分界线将网格模型分成2个子网格模型,实现三角网格模型的分割.三角网格模型分割步骤如下:Step1.以三角网格模型中位于交线上的任一三角面片为初始迭代面片.Step2.查找三角网格模型中包含初始迭代面片非交线边的三角面片.Step3.判断查找到的三角面片是否以交线为边界,若存在交线边界,则停止查找交线边方向上的三角面片;若三角网格模型查找完毕,执行下一步;否则,查找三角网格模型中包含其他边界的三角面片,重复Step3.Step4.若2个网格模型只有一条交线,执行下一步;若2个网格模型存在多条交线,提取下一条交线,转Step1.Step5.将查找到的三角面片从三角网格模型中分割出来,实现沿交线将网格模型分成2个子网格模型.如图6a所示,三角面片T1为初始迭代面片,由T1查找到三角面片T2和T3,由T2查找到三角面片T4和T5,由T3查找到三角面片T6,由T4查找到三角面片T7和T8;图6b所示为网格模型的分割结果.3.3s1e-s13.3设2个三角网格模型为S1和S2,交线将S1分成2个子网格模型,分别为位于S2内部的网格模型和位于S2外部的网格模型,交线同样将S2分成2个子网格模型,则S1和S2布尔运算公式为S1∩S2=S1inS2+S2inS1‚S1∪S2=S1outS2+S2outS1‚S1−S2=S1outS2+S2inS1‚S2−S1=S2outS1+S1inS2.S1∩S2=S1inS2+S2inS1‚S1∪S2=S1outS2+S2outS1‚S1-S2=S1outS2+S2inS1‚S2-S1=S2outS1+S1inS2.其中,S1inS2和S1outS2分别表示S1位于S2内部和外部的子网格模型,S2inS1和S2outS1分别表示S2位于S1内部和外部的子网格模型.三角网格模型的交运算是将S1中的S1inS2与S2中的S2inS1合并组成一张曲面;并运算是将S1中的S1outS2与S2中的S2outS1合并组成一张曲面;差运算是将S1中的S1outS2与S2中的S2inS1合并组成一张曲面,或将S2中的S2outS1与S1中的S1inS2合并组成一张曲面.4实际模型测试采用本文算法和文献算法对图7a,7b所示的网格模型进行布尔运算,图7c~7f所示分别为通过网格交线分割出的4个子网格模型,对所生成的子网格模型进行布尔交、并、差运算的结果如图7g~7j所示.表1所示为采用本文算法和文献算法对图7a,7b模型进行布尔运算的算法时间比较,可以看出,本文算法交线求解效率比文献算法提高1~6倍,布尔运算效率提高约11倍.图8所示为采用本文算法和文献算法对数据量依次递增的多组网格模型的布尔运算效率进行对比分析,可以看出,随着三角网格模型数据量的递增,本文算法效率明显优于文

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论