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

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

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

三维网格模型数据流压缩算法研究

当前的网格压缩算法在编码顶点和连通信息之前,需要按照某种顺序遍历网格模型,而且需要构造支持拓扑结构访问的临时数据结构,不利于处理大型网格模型.从根源上抛弃了传统网格数据组织形式,给出了一种新的网格顶点和连通信息交错的网格数据组织方法,提出了以网格数据读入顺序渐进编码算法.实验结果表明,算法的处理速度和所占用的内存空间都优于传统的压缩方法.     

基于半边结构和√3细分的渐进网格生成方法

渐进网格可以满足生成多分辨率模型的需求.在现有渐进网格生成方法中,一个顶点的简化往往关联四个以上的相邻顶点.并且,现有方法多采用网格的点面列表结构表示.本文采用√3细分预测方法生成渐进网格,每个顶点的存储仅关联三个相邻顶点.同时也使用半边数据结构替代网格的点面列表表示形式,加快了邻接信息查询.实验结果表明,本方法提升渐进网格的空间效率,缩短渐进网格的生成时间.     

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

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

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

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

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

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