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

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

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

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

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

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

散乱点云的三角网格重构

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

基于STL三角网格模型简化的研究

针对STL三角网格模型简化中的相关问题进行了研究,并设计出了相应的算法.三角网格的简化过程包括网格删除和网格重建两个过程,在网格的删除中,根据设定的三角形的权重阚值选择删除被删除的三角形区域.在网格重建中,任意选择重建区域的一个顶点,通过渐进收缩的方式,将新生成的三角形边构造一个平衡二叉树,再以三角网格的适应度和平滑度为依据,找出所有二又树中最佳的分支,使重建的三角网格最优化.对两个实例进行探讨,实现对不同STL三角网格的验证,并以原始网格模型与简化后的网格模型进行对比,表明研究所得的简化网格模型既有效地实现了STL网格模型的简化,又保持了原有STL网格模型的基本特征,达到令人满意的结果.     

基于高斯曲率的三角网格模型简化的研究

针对三角网格模型简化中的相关问题进行了研究并设计出了相应的算法。三角网格的简化过程包括网格删除和网格重建两个过程。在网格的删除中,通过顶点的高斯曲率对其分类,如果三角形的三个顶点属于同一类,则对该三角形及其邻接三角形进行删除。在网格重建中,重点是新顶点的定位。首先,将新顶点定位在该三角形的重心上,然后,通过它的邻接点对其定位进行优化,最后,以两个实例进行探讨,实现对不同三角网格的验证,并以原始网格模型与简化后的网格模型进行对比说明本研究所得的简化网格模型即有效地实现了三角网格模型的简化,又保持了原有三角网格模型的基本特征,达到了令人满意的结果。     

基于重新划分的三角形网格简化的一种改进算法

基于重新划分的三角形网格简化方法能自动生成多细节层次模型，它的基本思想是:根据三角形网格的局部几何和拓扑特征将一定数量的点分布到原网格上,生成一个中间网格,移去中间网格中的老顶点,并对产生的多边形区域进行局部三角化,最后形成以新点为顶点的三角形网格.本文在已有算法的基础上,提出了一种分布新点的算法,从而克服了原有方法的局限性.它利用三角形顶点的曲率和三角形的面积两个因素来反映网格在每个三角形处的特征.文中给出的一组实例说明了算法的有效性.     

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

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

多边形网格的非流形封闭三角形网格正则化

为了提高基于网格模型的算法与应用的效率和稳定性,提出一种将任意多边形网格模型转化为正则三角网格模型的算法.首先对输入多边形网格模型中非三角形的面片进行三角剖分,然后查找并移除模型中的重合或重叠元素,再通过模型内部三角形求交对模型进行边和面的分割,从而修正模型的拓扑结构;在求交的过程中,根据边和三角形的位置关系对共面求交进行细致的分类处理,减少了求交次数,提高了算法的稳定性;最后循环搜索在网格模型中可以确定法向的种子三角形,通过拓扑结构调整与之相邻的三角形的法向,最终构成一个或多个法向确定的闭合曲面.实验结果表明,该算法能够将多边形网格转化为正则三角形网格模型.     

基于边顶点重要度的网格简化算法及应用

基于三角形网格边折叠简化思想，提出一种基于边顶点重要度简化算法，采用一种改进的三角形网格数据结构，在预处理中利用二叉树对顶点重要度进行快速排序并记录三角形合并关系，得到所需分辨率下的近似网格模型。     

三角网格模型的补洞算法研究

提出了一种三角网格模型的空间孔洞修补算法.首先根据网格中的点、边和三角形之间的关系提取孔洞边界,然后根据孔洞区域的夹角的顺序在空间中依次填补三角形直至修补完全,接着对新增加的高度弯曲的三角形进行细分,最后对修补后的孔洞网格进行几何形态调整,光顺化整个孔洞曲面.实验结果证明,该算法简单、有效,孔洞修补效果好.     

基于检测球控制的网格模型简化算法研究

在逆向工程、计算机图形学等应用领域中,经常采用多边形网格模型(多为三角形网格)来描述几何形体,但网格中三角片数目往往非常庞大.为了保证对模型的后续操作能有效地进行,有必要在满足一定精度的条件下对其进行简化.提出了一种基于检测球控制简化精度的网格模型简化算法.该算法运行速度快,简化效果好.     

基于贪心优化策略的网格排布算法

针对由存储带宽和数据访问速度导致的复杂数据集绘制性能低下等问题,提出了一种基于贪心优化策略的三角形排布算法,通过对绘制数据集进行重排以改善数据的空间局部性和时间局部性。该算法首先将顶点分为三类,根据改进的代价函数选择代价度量最小的顶点作为活动顶点;然后绘制（即输出）其所有未绘制的邻接三角形,并将相邻顶点压入缓存,算法迭代执行直到所有顶点的邻接三角形都绘制完成,得到重新排列后的三角形序列。实验结果表明,该算法不仅具备较高的顶点缓存命中率,还提高了渲染速度,减少了排序的时间,有效地解决了图形处理器的处理速度不断提升而数据访问速度严重滞后的问题。     

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

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

Edgebreaker: connectivity compression for triangle meshes

Edgebreaker is a simple scheme for compressing the triangle/vertex incidence graphs (sometimes called connectivity or topology) of three-dimensional triangle meshes. Edgebreaker improves upon the storage required by previously reported schemes, most of which can guarantee only an O(t log(t)) storage cost for the incidence graph of a mesh of t triangles. Edgebreaker requires at most 2t bits for any mesh homeomorphic to a sphere and supports fully general meshes by using additional storage per handle and hole. For large meshes, entropy coding yields less than 1.5 bits per triangle. Edgebreaker's compression and decompression processes perform identical traversals of the mesh from one triangle to an adjacent one. At each stage, compression produces an op-code describing the topological relation between the current triangle and the boundary of the remaining part of the mesh. Decompression uses these op-codes to reconstruct the entire incidence graph. Because Edgebreaker's compression and decompression are independent of the vertex locations, they may be combined with a variety of vertex-compressing techniques that exploit topological information about the mesh to better estimate vertex locations. Edgebreaker may be used to compress the connectivity of an entire mesh bounding a 3D polyhedron or the connectivity of a triangulated surface patch whose boundary need not be encoded. The paper also offers a comparative survey of the rapidly growing field of geometric compression     

一种改进的MC算法

为了对等值面与子等值面进行提取和分组,在MC算法原理的基础上,提出了一种改进的等值面提取与子等值面分组算法。该算法首先将数据场分解为点、棱边、面与体元的拓扑结构;然后在整个数据场范围内求所有棱边与等值面的交点,并在面内连接交点形成面与等值面的交线,交线在体元内连接生成空间多边形;接着通过三角化各个体元内的空间多边形得到由顶点表与三角形表组成的等值面数据;最后根据三角形在顶点处的连接关系,采用种子算法对属于同一子等值面的三角形与顶点进行标记,属于同一子等值面的顶点与三角形将被存放在独立的顶点表与三角形表中。实验结果表明,该算法可以高效地实现等值面提取与子等值面的分组。     

基于Hamiltonian三角剖分的三角网格多分辨率表示

三角网格模型的多分辨率表示是几何模型绘制与传输的基础，本文通过三角形之间的拓扑相邻关系将三角网格划分为广义三角形带的集合，然后利用Hamiltonian三角剖分的性质构造三角网格的多分辨率表示。该方法统一了单分辨率网格和多分辨率网格的表示方法，当模型有c个不同分辨率表示时，其编码效率为（logc＋5）bit／vertex。     

散乱点云的快速增量网格重建算法

散乱数据的网格重建是数字几何处理的基础性技术之一.本文提出一种快速增量式散乱点云网格重建算法,运用波前( Wave Front)方法渐进地由点云数据生成物体表面的网格模型.该算法以一个”种子”三角形初始化搜索队列,以逐渐生成的新边为搜索元素,借助Kd-树空间划分技术和搜索约束条件,快速完成优化点的评估及三角面片重建,可在保证网格质量的同时,过滤部分对重建效果意义不大的点.实验表明,该算法能够高效、可靠地生成具有不同几何复杂度的原始曲面二维流形三角网格逼近,适用于海量数据点的网格重建.     

基于三角形连接的有限元网格划分

文中创新地提出了三角形连接的有限元网格划分的算法,但是三角形并不是有限元计算的基本单元,而是根据已经生成的三角形生成较为规整的四边形。在实际的项目过程中,创新地提出了三种有效的算法,并利用C＋＋面向对象的MFC程序设计和编写。本程序可以从模型文件读取边界以及点约束和线约束特征数据,程序自动计算出一个较为合理的边界间距值,并且根据需要人工或自动选择一种划分算法,从而自动完成高质量的四边形网格划分。三种算法皆可以处理大量数据点和线,并且划分速度较为高效。本程序模块成功应用于有限元计算软件中。