采用半边编码的三角网格拓扑数据结构

为了更紧凑地表示三角网格的几何和拓扑信息,充分利用三角网格中的面、顶点和半边之间的语义关系和隐含信息,提出一个采用半边编码的三角网格拓扑数据结构.首先建立以顶点序列表示的三角面对象,并存放在动态数组中;将半边表示为所属三角面在数组中的下标和顶点连线顺序隐式关系的二元组,并且编码为一个无符号长整型数;在顶点对象中设置外出半边属性,在三角面对象中设置相邻面的3个反向半边属性;通过对设置的半边信息进行解码,实现拓扑信息查询.基于该数据结构开展了STL三角网格数据的拓扑重建实验,在对内存空间需求、重建效率和拓扑信息处理能力等方面,与目前广泛使用的半边数据结构进行了比较,表明需求内存空间大为减少.     

在机检测中三角网格拓扑重建方法的研究

对STL（Stereo Lithographic）模型中三角面片进行拓扑重建是解决在机检测系统中对零件模型表面进行曲面划分的前提条件之一。在建立点-边拓扑关系的基础上,将原有基于顶点坐标值浮点数比较的半边匹配结构转化为基于索引值的整型数匹配,并提出了基于关联-散列结构三角网格拓扑重建方法。该方法采用散列结构为辅助数据结构来减少STL模型顶点归并和边界归并的计算量,利用STL模型相邻网格单元数据相关性降低哈希函数的构建难度并提高冲突处理效率,在滤除冗余数据的同时完成拓扑关系的建立。计算实例验证了该算法的高效性和有效性。     

一种基于XML的三角网格存贮方法

为了实现不同逆向工程系统之间数据的共享,定义了三角网格存贮格式,并采用XML语言实现了三角网格的存贮和调用.主要是利用ID号区别不同的网格顶点与非网格顶点,并通过记录测量数据点坐标信息、边界点标记、边的顶点拓扑关系、三角形的顶点拓扑关系,实现网格存贮.通过XML实例代码,详细说明了非网格数据顶点、网格顶点、边、三角形的存贮格式,并给出了三角网格调用的简单描述.从而利用XML的自定义性和可扩展性,为不同系统提供了统一的数据存贮接口,使不同系统的用户均能使用三角网格数据,实现网格数据的共享和自由传递.该方法已在实验中得到验证.     

曲面三角网格模型顶点法矢计算与交互式分割

本文给出一种三角网格模型顶点法矢计算公式,该公式采用网格模型中三角片面积与顶角角度综合加权,其计算精度高于现有的面积加权计算方法．另外,本文还提出了一种简便灵活的任意拓扑曲面三角网格模型交互式分割方法．利用该方法,可有效地将任意拓扑三角网格模型分割为几个与盘形拓扑同胚的区域,为后续处理提供方便。     

STL数据快速拓扑重建关键算法

在反求工程中,散乱数据点云的曲面重构常采用三角网格模型,建立三角网格之间拓扑关系的速度是影响曲面重建效率的关键因素之一．本文提出了基于V—F结构的平衡二叉树（AVL）顶点聚合算法,简化数据文件的存储容量至原来的18％～25％,并有效地去除了大量冗余数据点;采用虚AVL的快速邻边搜索优化算法,实现了相邻半边的快速搜索,高效地构建半边拓扑结构,最后通过各种零件重建速度的比较说明本文方法是高效的、可扩展的．     

三维虚拟植物中非流形结构的紧凑表达

构建紧凑的网格数据结构是高效交互式操控虚拟植物的重要前提.根据虚拟植物的拓扑结构特点,提出一种适用于虚拟植物中非流形结构的紧凑表达方法.在半边结构的基础上,利用顶点的外出半边获得与该半边相对应的反向半边,将该半边和反向半边分别存放在对方的反向半边列表中;通过反向半边列表判别虚拟植物拓扑结构的类型,实现拓扑信息查询.对虚拟植物实例进行三角网格的数据结构重建的实验结果表明,与传统半边和基于半边的数据结构相比,该方法所需内存空间减少,且更便于几何和拓扑信息处理.     

支持STL数据源的网格曲面动态空间索引

针对STL文件格式存在网格顶点数据冗余以及缺乏面片邻接信息等缺陷,提出一种基于多维动态空间索引的显式曲面拓扑重建算法,在消除网格顶点数据复本的过程中逐步构建网格曲面顶点的KD树,通过该索引提高顶点数据复本消除效率,并基于KD树叶节点层数据存储的开放性融入半边数据结构,实现曲面拓扑结构的快速重建。最后,对6个不同规模的数据模型进行实验:与采用R^*-Tree、数组、散列表作为索引等方法相比,所提出的KD树与半边结构融合的动态空间索引在处理近百万面片的数据文件时,去除冗余顶点用时11.93 s,拓扑重建仅仅需要2.87 s,大大减少了冗余顶点的去除时间和拓扑重建时间,并且有效支持网格曲面拓扑邻域信息的快速查询,查询时间在1 ms之内,远小于对比算法所用时间。实验结果表明:所提算法能够提高网格曲面冗余顶点去除效率和拓扑重建效率,实现网格曲面拓扑邻域信息的快速查询。     

三维网格模型的快速拓扑重建算法

为了提高重建三维网格模型拓扑的速度,选择半边结构作为表示实体模型拓扑关系的结构模型,设计了新的用于加快顶点合并的索引方法。在顶点合并时直接定位到欲查找的顶点位置上,无须借助AVL等辅助查找表。拓扑重建的时间复杂度由原来的O(n log n)降低至O(n)。通过SMF格式文件进行的测试结果表明,在普通PC上重建含有10万个三角面片模型的拓扑结构也只需1s。     

三角网格模型的基本群分割

提出一种有效的三角网格模型分割方法。用Dijkstra算法求出三角网格模型上任意给定一个基点到其余顶点的最短路径树;求出该模型对偶图的最大生成树,且对偶图的边与该最短路径树的边不相交;找出该模型上所有既不属于最短路径树也不和最大生成树相交的边,这些边分别与最短路径树组成的最短环集合就是给定基点处的基本群,沿着这些最短环就可以把网格分割成一个拓扑同胚于圆盘的区域。实验结果表明,该分割方法可以快速、有效地实现网格的分割。     

基于场对齐质心Voronoi划分的四边网格生成

为了生成高质量的四边网格,提出一种基于场对齐质心Voronoi划分(centroidal Voronoi tessellation,CVT)优化的四边网格生成方法.首先通过优化CVT能量函数将输出网格顶点均匀地分布在输入网格表面;然后利用场对齐CVT优化得到网格边与输入方向场对齐的三角网格;再通过网格边-场方向匹配初步提取四边网格,并基于拓扑模式进行奇异点的识别与消除;最后利用三角形配对得到准四边网格.实验结果表明,该方法能够生成对齐方向场且质量较高的准四边网格.     

面向CAE 的STL 模型三角网格均匀化

提出了一种基于STL数据的有限元网格再生成算法,该算法主要用于CAE工程分析.鉴于CAD模型的网格特征形态不匀称,分布不均匀的特点,对CAD模型进行网格再生成,使其符合CAE工程分析的要求.算法主要由拓扑建立、网格聚类、网格重采样和三角化四部分组成.实验表明该算法能够有效降低三角网格最长边和最短边的比值,使得模型的网格特征形态趋于均匀.     

基于STL文件的曲面网格重建算法

利用STL文件的数据相关性以及平衡二叉(AVL)树的数据搜索效率仅与树的高度相关的特性,提出一种高效的三角形曲面网格模型重建算法。该算法可以解决STL文件存在大量的冗余、使用效率不高等问题。实验结果证明,与基于AVL树的顶点快速聚合算法相比,该算法的重建效率更高。     

基于三角形折叠的网格简化算法

在计算机图形学中，物体常常用三角形网格模型来描述。本文提出了一种新的基于三角形折叠的网格简化算法。该网格简化算法不仅能减少模型中的三角形数目而且能保持模型拓扑结构。算法给出了一种基于点到平面距离的有效的误差控制方法，并能在用户指定的误差范围内通过使原始网格中的三角形折叠达到大量简化的目的。该算法实现简单并且速度快。另外为了有效地支持多分辨率模型的表示以及相邻层次模型间的连续过渡，本文还给出了一种基     

快速成型中一种改进的轮廓线生成算法

在对STL模型分层求交线过程中,针对三角面片的边与切平面很接近时,浮点运算引起的精度损失可能导致的错误交线问题,提出一种基于STL模型局部拓扑的分层算法。将所有可能引起错误交线的三角面片提取出来,建立拓扑结构,以接近切平面的边在切平面的投影替代交线,消除了由于浮点运算误差导致的轮廓线缺边和重边的错误。实验结果表明,该算法在计算出交线段集后不需要再进行修复,简单连接后就能得出正确的切片轮廓线。     

基于逆 Loop 细分的半正则网格简化算法

摘 要：三维网格简化是在保留目标物体几何形状信息的前提下尽量减小精细化三维模型 中的点数和面数的一种操作,对提高三维网格数据的存取和网络传输速度、编辑和渲染效率具 有十分重要的作用。针对大多网格简化算法在简化过程中未考虑网格拓扑结构与视觉质量的问 题,提出了一种基于逆 Loop 细分的半正则网格简化算法。首先根据邻域质心偏移量进行特征 点检测,随后随机选取种子三角形,以边扩展方式获取正则区域并执行逆 Loop 细分进行简化。 最后,以向内分割方式进行边缘拼接,获取最终的简化模型。与经典算法在公开数据集上进行 实验对比,结果表明,该算法能够在简化的同时有效地保持网格特征,尽可能保留与原始网格 一致的规则的拓扑结构,并且在视觉质量上优于边折叠以及聚类简化算法。     

基于医学图像序列面绘制的骨组织快速成型方法

针对人工骨组织快速成型中轮廓线轨迹生成复杂、分层效率低的问题,提出了一种简化三角片模型分层过程的方法。应用移动立方块（MC）算法对医学图像序列进行面绘制重建,根据重建过程的顺序对三角片集合分组,然后采用对边追踪的方法计算切平面与其对应三角片数组的交点轮廓线数据。简化后的分层效率相对于三角网格文件（STL）模型分层平均提高了4.65%。实验结果表明,所提方法可以直接从人体骨组织医学图像序列生成可供3D打印的轮廓线数据,从而实现骨组织的快速成型。     

STL文件错误的快速修复*

为了修复使用的STL文件中的一些错误,首先根据错误的特点进行分类,然后利用半边数据结构快速建立STL文件的实体模型。以边的检测作为STL文件错误检测的基础,建立了导入STL文件、无结构网格、流行网格、错误检测、错误修复、更新错误信息等基本修复步骤。二叉平衡树的使用加快了算法的遍历速度。实例验证了该算法的有效性。该方法可作为预处理模块运用于快速成型和逆向工程等领域。     

STL面片邻接拓扑关系重构及其应用

STL文件描述的是一种离散的实体表面三角面片模型,在实际处理中一般需要重新构造其邻接拓扑关系(包括面片的邻接面、顶点的邻接面、邻接顶点等关系）。而剔除STL面片数据中的冗余顶点是重构的关键,该算法已经成功应用于三维真实感注塑模流动模拟软件的3D图形处理。     

保持拓扑和尖角特征的网格简化算法

提出了一种有效的保持拓扑和尖角特征的网格简化算法。由于曲率刻画了模型的尖角特征，该文利用顶点曲率的高斯加权函数对经典边折叠算法的二次误差测度矩阵进行了修正，增强了尖角点对新点位置的影响。鉴于网格的拓扑保持具有重要的工程应用，论述了网格简化中各种可能的拓扑错误，并给出了相应的解决措施。平衡二叉树和半边匹配数据结构的引入，提高了拓扑信息重建的速度。最后，几个网格简化实例显示了该文算法的有效性。     

结合网格分割和边折叠的网格简化算法

传统网格简化算法简化效率较低,且在大幅度简化时难以保持网格模型的外形特征。为此,提出一种结合网格分割和边折叠的网格简化算法。采用分水岭算法对网格模型进行分割,以提高网格模型的简化效率。在Garland算法折叠代价函数的基础上,加入三角形形状和相邻曲面弯曲程度的相关因子,从而更好地保持网格模型的外形特征。实验结果表明,该算法在网格模型的简化速度和外形特征保持方面性能较好。