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

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

基于三角片拼合的STL网格模型重建算法

采用三角片拼合的方法递增建立网格模型,新增三角片被归纳为5种类型.首先通过半边匹配确定新增三角片的类型;然后针对每一种类型使用不同的方法去除冗余顶点,并同时建立拓扑关系;最后通过顶点数组紧缩消除顶点空隙,将半边hash表转化为半边数组,完成网格模型的重建.该模型为改进的半边结构,具有完整的形状和拓扑信息,可以表示非流形边,是法矢调整、网格分块等后续处理的理想起点.实验结果表明,文中算法高效、鲁棒、可扩展.     

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

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

基于AVL树的STL模型快速拓扑重建算法

STL数据格式是目前广泛应用于CAD系统中进行数据交换的标准格式之一。使用三角面片表示实体表面信息。但STL数据格式具有数据冗余和缺乏拓扑信息的缺点,针对这一问题,本文采用半边数据结构,提出一种基于辅助AVL树的STL模型快速拓扑重建算法,能快速有效地去除冗余顶点及实现半边合并。     

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

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

基于STL三角网格的数据快速读取研究

STL格式文件用三角网格面来描述实体模型,实际应用如逆向工程中需要建立三角形、边和顶点的郐接拓扑关系,其中查找并去除重复顶点是建立拓扑结构的关键.着重讨论拓扑关系构建过程中数据查找的3种方法:线性表、平衡二叉树和三轴分块排序,通过实测数据对这3种方法的性能进行了分析和比较.     

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

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

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

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

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

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

基于2维流形的STL曲面网格重建算法

STL（stereo lithography）作为3D扫描数据和快速原型制造事实上的标准,其广泛应用于娱乐、制造业和Internet等领域.但随着3D模型越来越复杂,数据量越来越庞大,从STL文件难以快速获得完整拓扑关系以及其存在大量冗余信息的缺点,制约着STL网格模型的进一步优化处理与应用.为此,需要针对STL网格模型进行网格重建.本文针对2维流形的STL三角形曲面网格模型,提出了一种快速的网格重建方法.主要利用删除在重建过程中达到饱和的顶点,以便减少需要比对的顶点数,并结合STL文件数据的相关性来提高顶点搜索与比较的效率.对于非封闭的曲面网格,本文算法在提高曲面网格重建效率的同时,还能有效地提取曲面网格模型的边界信息.另外,重建的曲面网格数据文件大大地减少了存储空间,有效地去除了冗余数据.实验结果表明本文算法的高效性及鲁棒性.     

STL格式文件的快速拓扑重建算法

针对立体光刻(STL)文件所表示的图形要素之间缺乏必要的拓扑关系,对STL格式文件进行分析和读取,以哈希表作为查找表快速建立三维模型各要素间的拓扑关系,建立能表示要素关系的点表和面表,利用基于哈希表的拓扑重建算法实现了拓扑结构的快速建立, 算法时间复杂度仅为O(n), 空间复杂度为O(3n+(4+m)f+m)。最后,列举5个实例进行验证测试,实验结果显示,与直接算法和红黑树法相比,所提出的算法用时更少,在普通计算机上重建含有65万个三角面片模型的拓扑结构只需2.3s。     

梯形图转语句表的等效网络合并方法研究

目前常用梯形图转语句表方法有拓扑排序、二叉树、广义表、串并联归并等,但在梯形图编辑软件中难于直接同图形编辑的描述对应起来,编程难度也较大。为解决这些问题,提出了一种等效网络合并方法,采用一个矩阵和相关的PLC梯形图符号来描述一个梯形图,并用一种类似于电阻网络的合并算法来实现梯形图的合并,变成一个最简化的合并图,然后再从该合并图生成语句表。该方法在编辑软件中梯形图的描述与转语句表运算采用完全相同的数据结构,并可从编辑软件中动态绘制梯形的合并过程,具有直观、易于理解、易于编程等优点。     

Hash functions and triangular mesh reconstruction

Some applications use data formats (e.g. STL file format), where a set of triangles is used to represent the surface of a 3D object and it is necessary to reconstruct the triangular mesh with adjacency information. It is a lengthy process for large data sets as the time complexity of this process is O(N log N), where N is number of triangles. Triangular mesh reconstruction is a general problem and relevant algorithms can be used in GIS and DTM systems as well as in CAD/CAM systems. Many algorithms rely on space subdivision techniques while hash functions offer a more effective solution to the reconstruction problem. Hash data structures are widely used throughout the field of computer science. The hash table can be used to speed up the process of triangular mesh reconstruction but the speed strongly depends on hash function properties. Nevertheless the design or selection of the hash function for data sets with unknown properties is a serious problem. This paper describes a new hash function, presents the properties obtained for large data sets, and discusses validity of the reconstructed surface. Experimental results proved theoretical considerations and advantages of hash function use for mesh reconstruction.     

基于金字塔技术的STL模型数字水印算法

为了确保STL (Stereo lithography) 模型数据在网络传输过程中的安全、完整性,根据STL模型自身的特点, 对模型进行了拓扑重建,在主成分分析(Primary component analysis, PCA)预处理的基础上,提出了基于金字塔技术建立STL模型数据空间索引算法,对原始STL模型数据空间进行了划分和索引, 结合奇异值分解的相关原理,提出了基于B+ 树K近邻查询的STL模型数字水印嵌入与提取算法. 实验证明:本文算法不可见性较好,算法实现速度快,在盲检测下能够抵抗旋转、平移、均匀缩放、顶点重排序、简化、噪声、剪切等攻击,具有较好的鲁棒性.     

散乱点云的三角网格重构

基于增量扩散法的思想，提出并实现了一个散乱点云的三角网格重构算法，算法首先利用体素网格的散列表对散乱点进行组织，然后在确定了初始种子三角形的基础上，基于活动边扩展规则构造新的三角形，使网格不断向周围扩展直到活动边表空为止，最后算法合并棱边并计算每个三角形的顶点法矢，最终构造出散乱点云的三角网格。     

基于多分辨率模型的三角曲面特征线辨识技术

由于特征线在反求工程 CAD建模中具有非常重要的作用 ,因此利用图形图象处理中的多分辨率模型概念 ,通过研究三角曲面模型的特征线 ,提出了一种三角曲面特征线的计算方法 .将计算得到的初始特征线通过编辑、修改等手段进行处理 ,得到清晰的特征线 ,并将其作为进一步划分重构 B样条曲面边界的依据和参考 ,从而为实现基于三角曲面模型的 B样条曲面重构奠定了基础 .实验结果证明 ,该算法能够在三角曲面上提取出令人满意的特征线 ,并据此重构出拓扑划分合理的 B样条曲面 .