论文部分内容阅读
逆向工程中R*-树动态空间索引的引入有效提高了产品逆向工程中各环节数据处理的效率和质量,索引结构的优劣直接影响建模的效率与精度。通过对动态空间索引及其在网格曲面处理方面的应用进行深入系统的研究,提出了一种基于改进的R*-树(R*S-树)与半边结构的网格曲面动态空间索引构建算法,并基于该算法所构建的网格曲面动态空间索引高效实现了三角网格的简化、求交以及布尔运算。主要研究内容与研究成果如下:1)提出一种网格曲面动态空间索引构建算法。选择半边结构作为网格曲面的底层数据结构,通过将原始网格曲面转化为半边结构对网格顶点、边、面片进行组织,并在其过程中将面片作为数据对象插入R*S-树中,实现R*S-树的构建并获得半边结构与R*S-树相融合的网格曲面动态空间索引,利用该索引进行网格单元的快速拓扑邻域查询,并以STL数据所表示的网格曲面为例对算法的效率进行实例验证。实验结果表明,该算法可快速进行曲面拓扑重建,且所构建的索引可支持网格顶点的快速定位并在常数时间内实现目标单元的邻域查询。2)提出一种三角网格曲面简化算法。基于融合的网格曲面动态空间索引快速获取三角面片拓扑邻域,通过计算三角面片法矢夹角获取三角网格曲面曲率分布信息,并以此作为三角面片分簇依据进行邻域三角面片分簇,对分簇后的每簇三角面片采用一种顶点聚类简化算法进行三角面片简化,并对三角面片的形状进行有效控制,实现三角网格简化的同时保持网格型面特征。实验证明,该算法可快速实现三角网格的非均匀简化,且具有良好的网格保形性。3)改进现有的三角网格曲面求交与布尔运算算法。将本文所提出的网格曲面动态空间索引构建算法运用于三角网格曲面求交及布尔运算过程中,通过与R*S-树进行逐层结点相交检测快速获取三角网格曲面相交区域,采用扩展空心球算法快速缩小空间近邻查询范围对相交包围盒进行排序,求解排序后相交三角面片的交线段并首尾连接以获取交线,为三角剖分后的三角网格构建融合的网格曲面动态空间索引,基于该索引加速三角网格曲面分割过程,显著提高了其布尔运算效率。