第28卷 第2期 计算机辅助设计与图形学学报Vol. 28 No.2 2016年2月Journal of Computer-Aided Design & Computer GraphicsFeb. 2016收稿日期: 2015-02-06; 修回日期:2015-04-07. 基金项目: 国家自然科学基金(51375069). 张应中(1961—), 男, 博士, 副教授,主要研究方向为数字化设计与智能设计、可持续设计制造; 谢馥香(1989—), 女, 硕士研究生, 主要研究方向为数字网格形状感知; 罗晓芳(1961—), 女, 硕士, 副教授, 主要研究方向为CAD&CG; 王钦瑞(1991—), 男, 硕士研究生, 主要研究方向为数字网格分割及特征重构.采用半边编码的三角网格拓扑数据结构张应中, 谢馥香, 罗晓芳, 王钦瑞(大连理工大学机械工程学院 大连 116024) (zhangyz@)摘 要: 为了更紧凑地表示三角网格的几何和拓扑信息, 充分利用三角网格中的面、顶点和半边之间的语义关系和隐含信息, 提出一个采用半边编码的三角网格拓扑数据结构. 首先建立以顶点序列表示的三角面对象, 并存放在动态数组中; 将半边表示为所属三角面在数组中的下标和顶点连线顺序隐式关系的二元组, 并且编码为一个无符号长整型数; 在顶点对象中设置外出半边属性, 在三角面对象中设置相邻面的3个反向半边属性; 通过对设置的半边信息进行解码, 实现拓扑信息查询. 基于该数据结构开展了STL 三角网格数据的拓扑重建实验, 在对内存空间需求、重建效率和拓扑信息处理能力等方面, 与目前广泛使用的半边数据结构进行了比较,表明需求内存空间大为减少.关键词：三角网格; 拓扑信息; 半边数据结构; STL 拓扑重建 中图法分类号：TP391.41A Topological Data Structure Using Coding of Half-edges for Triangle MeshesZhang Yingzhong, Xie Fuxiang, Luo Xiaofang, and Wang Qinrui(School of Mechanical Engineering, Dalian University of Technology, Dalian 116024)Abstract: In order to get a more compact representation of the geometric and topological information for triangle meshes, a topological data structure using coding of half-edges is proposed, which makes full use of the implied information and semantic relationships among triangular facets, vertices and half-edges. In the proposed data structure, a triangular face object is stored in a dynamic array. A half-edge is represented as a two-tuple consisting of an array index of the incident face and an order number of linking vertexes, and then is encoded into an un-signed long integer. In the vertex object, an attribute representing an outgoing half-edge is set. In the face object, three attributes representing adjacent opposite half-edges are set. The topology information of the triangle mesh can be efficiently queried by decoding the related half-edges. Based on the proposed data structure, a topological reconstruction experiment for the STL mesh data has been carried out. Finally, a comparison with the commonly used half-edge data structure on the memory footprint and reconstruction efficiency is provided, which demon-strates the memory footprint of the presented data structure is reduced greatly.Key words: triangle mesh; topological information; half-edge data structure; STL topological reconstruction 随着数字几何技术的发展, 越来越多物体的数字几何模型采用三角网格几何表示, 测量获取的点云数据也通常被处理成三角网格数据输出[1]. 在几何网格应用中, 网格数据需要进行大量几何信息处理, 如网格简化、网格分割、特征识别和重构、网格模型布尔运算等. 因此, 一个能完整表达和管理网格几何和拓扑信息、存储优化和高效几何信息处理的网格几何表示模型是非常重要的.第2期张应中, 等: 采用半边编码的三角网格拓扑数据结构 329几何网格技术已经发展多年, 也出现各种表示多边形网格的数据结构和表示模型, 主要分为基于面和基于边的数据结构. 基于面的网格数据结构主要包括点和面的几何信息, 不能提供获取点或面相邻的拓扑信息, 数据结构简单, 易于读取, 主要用于形体显示、渲染和网格数据交换文件格式. 基于边的数据结构是将几何元素相邻的拓扑信息保存在边或者半边中, 边能够更好地表达网格几何元素之间的邻接关系, 是目前网格几何表示的主要数据结构. 著名的基于边的数据结构有翼边结构[2]和半边结构[3]. 翼边结构是最早表达多面体实体拓扑信息的数据结构, 但在遍历查找三角网格信息方面需要条件判断, 效率较低; 目前三角网格模型普遍采用的是半边数据结构, 该数据结构设计巧妙, 经过不断的改进[4]能很简洁地描述三角网格几何元素间的拓扑联系, 遍历查找三角网格信息效率高, 一环邻域查找不需任何条件判断. 存在的问题是, 对每一条边需要构建2个半边, 消耗内存资源. 对于具有几万、几十万个三角形的网格模型, 内存消耗是一个很重要的问题, 也是半边数据结构需要改进的方向. 因此, 国外开展了很多关于网格几何数据紧凑表示的研究, 主要的数据结构有: 1) 有向边结构[5]. 该结构平衡内存需求和计算时间; 2) Zipper[6]. 一个紧凑连接的三角网格数据结构, 占用空间小,但缺乏灵活性和扩展性; 3) 显式基于数组的紧凑数据结构[7]. 该数据结构使用图论中的最小施奈德树林编码, 能紧凑表示半边数据结构. 相比较而言, 国内这方面的研究较少, 主要应用目前流行的半边数据结构开展STL网格数据重构及相关方面的研究[8-10].实际上, 在三角网格中三角面承载更多的几何信息, 边承担联系各几何元素的角色. 本文在深入分析当前的半边数据结构基础上, 提出和实现一个采用半边编码的三角网格拓扑数据结构, 利用面、顶点和半边的隐含关系实现一个网格几何和拓扑信息的紧凑表示, 不仅能提供高效的网格几何信息查找和处理, 同时比当前的半边数据结构减少了大量的内存消耗. 通过对STL文件网格数据读入, 实现了STL网格数据的拓扑重建, 验证了该数据模型的可行性和有效性.1三角网格几何表示1.1 三角网格在几何造型中, 三角网格可被表示为一个三元组(V, E, F)组成的单纯复形[11]. 其中, V={v1, v2, …, v n}, 表示顶点集合, 确定了网格在三维欧氏空间中的几何形状和位置; E={e1, e2, …, e m}, e i∈V×V, 表示2个顶点连接的边的集合; F={f1, f2, …, f k}, f i∈V×V×V, 表示由3个顶点连接的三角面的集合.一个封闭和相互连接的流形三角网格的点、边和面的个数存在一个欧拉关系[11]: V－E＋F = 2. 其中V, E和F分别是顶点、边和面的个数. 根据这一关系, 可以得出如下统计数据[11]:1) 三角面个数约等于顶点数2倍, F≈2V;2) 边的条数约等于顶点数3倍, E≈3V;3) 平均顶点键数(入射边数)是6.1.2网格几何表示模型要求网格几何表示的主要目的是为了后续对网格模型开展的各种应用, 如网格简化、网格分割、网格特征识别和重构、网格布尔运算等. 这些应用对网格几何模型提出至少3个功能要求:1) 网格求值. 能完成对网格的各种几何求值计算, 如重心、相交、法矢量和曲率计算等.2) 网格查询. 包括空间几何查询和拓扑查询. 拓扑查询就是通过网格几何元素的连接关系, 能够遍历网格几何元素(面、边和点), 主要的要求包括能够快速查询每一个几何元素相邻元素, 能够快速查询每一个点的K邻域信息, 遍历一环邻域等.3) 网格修改. 一个三角网格模型可能根据几何要求修改, 如网格曲面变形等; 也可能根据拓扑修改, 如网格元素合并、删除和修剪等.一个形体的网格模型是由数量十分庞大的离散三角面组成, 占用大量的内存资源. 因此, 评价一个网格几何表示模型优劣的标准除了能够完成上述功能外, 还有4个重要指标[4]: 1) 构造模型的时间; 2) 回答特定查询的时间; 3) 执行特定修改操作的时间; 4) 内存消耗和数据冗余.1.3半边数据结构在几何网格中, 几何元素之间的连接性主要依赖于边, 表达网格拓扑关系的数据结构主要基于边结构. 如前面所述, 半边数据结构能很简洁地描述三角网格几何元素间的拓扑联系, 是目前普遍采用的表达三角网格拓扑关系的数据结构, 一个典型的半边数据结构如图1所示[4]. 在该数据结构中, 每条三角形边用2条对称的有向半边表示, 以法矢为正方向右手螺旋方向一致的半边属于当前三角面, 每个面由3条有向半边组成, 面与面的330 计算机辅助设计与图形学学报第28卷图1 半边数据结构邻接关系通过相邻反向半边建立.从图1可以看出, 一个半边数据结构包括指向5个对象的索引或者指针: 半边终点、下一条顺序连接的半边、前一条顺序连接的半边、所属面和相邻反向半边. 在32位操作系统中, 通常一个指针占用4个字节. 因此, 每个半边将占用20个字节. 由于边的个数约等于顶点数的3倍, 同时每一条边需要构造2个半边, 因此对于一个顶点个数很多的网格模型, 消耗的内存资源是十分可观的.2 采用半边编码的网格拓扑数据结构2.1 半边二元组表示在三角网格单纯复形中, 每个三角面由3条有向边形成环, 按逆时针方向包围而成. 第1节给出一个目前普遍采用的网格半边数据结构的半边表示, 它采用5个(至少4个)指针或数组下标, 显式地表示半边与顶点、所属面、邻接半边及前后半边几何元素之间的关联关系及半边的方向. 尽管经历多次的优化, 仍然存在较大的信息冗余.实际上, 在三角网格中三角面承载更多的几何信息. 一个三角面包括3个顶点, 顶点决定了它的空间位置和方向; 2个顶点连线构成一条三角面的边, 边用于分隔不同的三角面, 同时承担面与面、顶点与顶点之间连接关系的角色. 不同的顶点连线组合和顺序构成不同的方向边, 因此三角面中的一条边可以用顶点连线的序号(1,2,3)隐式表示. 如图2所示, 顶点v1, v2, v3, v1按照逆时针顺序连线构成面f1, 相应连线形成的半边为e1, e2, e3; 顶点v2, v4, v3, v2连线构成面f2; 相应连线形成的半边为h1, h2, h3. 实际上, 存放顶点的顺序隐式地表示了连线边的顺序, 不需要显式记录; 通过连线边的顺序可以从存放顶点的数组顺序中获取顶点. 因此, 可以将面标志和连线序号作为有向半边的标志, 即三角网格中的任何一条半边都可表示为一个二元组: h =〈F id, I sn〉. F id是一个面的标志, 可以是面指针或者面数组下标; I sn是顶点连线序号. 例如图2中的半边e2可以表示为〈f1, 2〉, 半边h3可以表示为〈f2, 3〉.图2 面、顶点和半边的排列关系2.2邻接关系三角网格几何元素之间拓扑关系主要包括邻接关系和所属关系. 邻接关系包括顶点与顶点、半边与半边、面与面之间的邻接关系; 所属关系(例如顶点所属的面)可以显式地在数据结构中定义. 下面主要讨论几何元素之间的邻接关系.顶点与顶点的邻接关系通过半边定义, 也可以通过在面数据结构中顶点的排放顺序隐式地表达这种邻接关系. 如图2中, 面f1定义的顶点序列为v1, v2, v3, 则隐式地表示v1与v2相连, v2与v3相连, v3与v1相连.同属一个面的半边与半边的邻接关系可以通过连线序号表示. 如图2中, 半边e2的连线序号是2, 则连接e2的下一条边就是3, 上一条边是1. 因此, 如果当前半边的序号是I, 则连接下一条边序号是: I next = mod(I, 3)＋1, 连接上一条边序号是: I pre = mod(I+1, 3)＋1.面与面的邻接关系可以通过边联系, 例如翼边结构中边设置了左面和右面属性. 但在上述介绍的半边表示中只有一个所属面信息, 需要增加信息. 由半边性质可知, 一条半边在相邻面一定存在一个对称的反向半边, 通过建立它们之间的相互映射关系, 就可以从一条半边过渡到它的反向半边, 从而实现面与面的连接, 还可以实现从一个面上的半边连接到另一个面上的半边. 半边之间映射关系可以在三角网格构造过程中显式定义, 例如图2中, 半边e2与半边h3的映射关系为〈f1, 2〉 〈f2, 3〉.2.3半边信息编码2.1节给出了半边信息的二元组表示, 表示一条第2期张应中, 等: 采用半边编码的三角网格拓扑数据结构 331半边需要2个变量: 面标志和连线序号. 面标志是访问面对象的地址, 一般有2种形式: 一是采用面对象指针, 指针变量需要4个字节; 二是采用数组下标, 将构造的面对象存放在一个一维动态数组中, 通过数组下标访问面对象指针. 本文中的数据结构采用数组下标作为面标志.但是, 一个复杂的网格模型中三角面片可能达到上百万个, 下标需要一个能表示范围较大的数, 需要一个4字节的长整型数. 另一方面, 连线序号一般只有3个数(1, 2, 3)或4个数(对应四边形), 由于计算机存储的对齐模式, 如果采用结构类型单独定义将造成很大浪费. 因此, 本文采用对半边信息的二元组进行编码, 将一个二元组编码为一个无符号长整型数(4字节32位)表示, 将面下标数存储在长整型数的前30位, 后2位存储连线序号, 如图3所示. 例如, 一个半边所属三角面的数组下标是23 458, 顶点连线顺序是3, 则该半边的二元组表示为〈23458, 3〉, 编码结果为一个长整数93 835.图3 半边编码存储格式编码方式就是通过对面数组下标数左移2位, 然后和连线顺序数做“或”操作, 得到编码结果数. 解码就是通过对半边编码数和3做“与”操作, 获得连线顺序数; 然后对半边编码数右移2位, 获得面数组下标数. 2.4基于半边信息编码的网格拓扑数据结构通过上面分析和半边编码定义, 综合考虑效率和空间需求, 本文提出如下基于半边编码的三角网格拓扑数据结构, 如图4所示. 三角网格的几何信息通过顶点和三角面描述, 拓扑信息隐含在半边信息中, 半边信息编码为一个无符号长整型数, 作为半边标志, 定义在三角面和顶点类中.1) 顶点类(class CVertex). 顶点数据包括顶点位置坐标和一个外出方向的半边.2) 三角面类(class CFace). 面数据包括3个顶点指针, 采用一维数组存放; 此外, 还有由顶点连线形成的半边与其所对应的反向半边映射表. 如图4所示, 面中的3个顶点依次存放在一维数组单元0, 1, 2中, 0单元的顶点与1单元的顶点连线, 形成半边h1, 但h1不显式地保存在面中, 而是将h1对应的反向伙伴半边保存在映射表的0单元中. 其余2个半边按相同设置, 构成该面3个半边与反向半边的映射表.3) 半边编码类(class CHalfedgeCode). 半边编码类是一个对半边信息进行编码和解码及相关信息查询的操作类. 定义如下函数:a. 输入所属面数组下标和连线序号, 返回一个半边的编码;b. 输入半边编码, 返回该半边所属的三角面对象指针;c. 输入半边编码, 返回该半边的反向伙伴半边编码;d. 输入半边编码, 返回连接该半边的下一半边编码;e. 输入半边编码, 返回连接该半边的上一半图4 基于半边编码的数据结构332 计算机辅助设计与图形学学报第28卷边编码;f. 输入半边编码, 返回该半边的起始顶点;g. 输入半边编码, 返回该半边的终止顶点.从上述分析和图4可以看出, 本文所提出的基于半边编码的拓扑数据结构充分考虑和利用三角网格中的面、顶点和半边之间的语义关系, 许多隐含信息不需要显式定义和保存, 使得数据结构设计的简练和有效.2.5几何信息查询和处理能力建立拓扑数据结构的主要目的是能够高效查询和检索网格几何信息, 查询和处理的能力是评价一个数据结构的一个重要指标. 下面选取3个不同方面展示上述数据结构在几何查询和处理方面的能力.1) 一般几何遍历查询已知一个三角面, 遍历所有其他三角形面; 已知一条边遍历所有其他的边. 遍历所有三角形面操作的伪代码如下:输入. 网格上任一参考面F ref.while F ref是一个未被遍历的面 do对F ref做遍历标记;i←0;while i<3 doC h←F ref 中的OppositeHEdge[i];F n←对C h解码获得一个邻接面;if F n未被遍历thenF ref←F n;break;end ifend whileend while2) 一环邻域查询一环邻域查询在网格几何处理中有广泛的应用. 通过数据结构实现直接存取操作能提高查询效率, 本文提出的数据结构可以容易地实现一环邻域直接查询, 不需要条件判断, 实现操作的伪代码如下:输入. 网格上一个查询顶点V q.输出. 一环邻域查询结果V t.C h←顶点V q的外出半边编码;h←解码C h;h stop←h, N←0;repeatV t[N]←半边h的顶点;h o←半边h的反向半边;h←h o连接的下一条半边;N←N+1;until h = h stopreturn V t;3) 网格修改在网格几何处理中, 经常需要对网格进行编辑修改, 如网格布尔运算等, 这就要求网格拓扑数据结构能够易于修改和重构. 下面以在网格细化处理中常用的插入顶点操作为例, 展示本文提出的网格拓扑数据结构的重构能力.如图5所示, 在三角面f中间插入一个顶点, 按照三角剖分算法, f被剖分为f1, f2和f3. 这时需要对已有的三角网格数据模型进行修改重构, 修改实现步骤如下:Step1. 通过三角面f的映射表查找相邻的3个面, 并将相邻面的映射表数组中对应位置的半边设置为0.Step2. 获取三角面f的面容器数组下标f id, 将其设为当前面容器数组下标.Step3. 插入新剖分的三角网格面f1, 再将当前面容器数组下标指针复原.Step4. 依次插入新剖分的后2个三角网格面f2和f3. 网格插入算法见3.2节详细介绍.Step5. 删除三角面f对象.图5 网格中插入一个顶点3面向STL的网格几何模型构建在逆向工程中, STL是一种三角网格数据交换文件格式,是目前测量设备数据输出的主要文件格式之一, 由于其数据格式简单易读, 易于信息处理, 已被广泛使用. 然而, STL格式只是单个列出三角片的几何信息, 造成了数据的大量冗余; 并且缺乏点、边和三角面片之间的拓扑关系信息. 因此需要对STL网格模型进行拓扑重建, 消除信息冗余, 建立一个新的易于信息查找和高效存储的网格几何表达模型[8-9]. 本文通过对STL网格数据分析, 基于上述网格拓扑数据结构, 实现了一个面向STL网格数据的拓扑重建方法, 验证本文提出网格拓扑数据结构的有效性.3.1 STL网格数据STL格式文件通过三角面片离散地表示实体的表面信息, 其中一个三角面片的数据包括该三角第2期张应中, 等: 采用半边编码的三角网格拓扑数据结构 333面片的外法矢量和按右手螺旋规则排列的3个顶点[12]. STL 文件格式简单、容易读取和显示, 主要有2个缺陷: 一是STL列出的三角面之间没有任何的联系, 即缺乏拓扑关系; 二是三角面的顶点坐标被重复地列出, 造成很大的信息冗余.STL分为ASCII 码和二进制2种格式. ASCII 码格式逐行给出三角面片的几何信息, 包括面法矢量和三个顶点坐标值, 本文采用这种格式.3.2 STL网格数据拓扑重建由上面分析可知, STL数据格式是逐行给出三角面片的3个顶点坐标信息, 并且3个顶点按逆时针排列包围三角面; 同时, 本文提出融合面和半边的数据结构将主要信息构建在面中. 因此, 很容易实现将STL网格数据拓扑重建为本文提出的数据结构中, 主要涉及2个操作:1) 顶点查找对给出的顶点空间几何位置数据, 需要对已创建的顶点集合进行遍历搜索, 判断是否有顶点与该点位置重合. 如果有重合顶点, 则将该顶点返回; 否则, 创建一个新的顶点. 对于顶点数很多的复杂网格, 顶点查找的效率是很重要的.人们也提出很多方法以提高查找顶点的效率, 如平衡二叉树法、八叉树法和哈希表法等. 二叉树法的查找时间取决于树的高度, 在均衡的情况下, 二叉查找树的查找时间为O(log n); 哈希表法查找效率最高, 它使用哈希函数将关键字与内存地址(或地址范围)之间建立关系, 可以直接在一个较小的范围进行顶点比较, 但关键是要选择合适的哈希映射函数, 本文采用哈希表法查找.2) 网格插入网格插入的功能就是对输入的3个顶点坐标在网格拓扑数据结构模型中构建一个三角面, 同时建立与该三角面相邻三角面之间的邻接(拓扑)关系. 网格插入步骤如下:Step1. 获取当前三角面数组下标变量, 设为N id;Step2. 输入3个顶点, 构造一个三角面对象, 记为f new. 在三角面对象构造中, 就输入的3个顶点v1, v2, v3进行上述顶点查找操作, 对新构建的顶点作新创建标记, 保存在顶点表容器中; 将3个顶点对象指针按照输入的顺序保存在f new中的顶点数组中.Step3. 对每一个新创建的顶点构建一条源于该顶点的外出半边. 外出半边的面标志为N id, 半边序号为该顶点在输入3个顶点序列中位置, 例如, 第一个位置在顶点数组中0单元, 则为 1. 将面标志和半边序号编码, 得到外出半边标志.Step4. 对顶点数组, 从0~2进行两点配对. 数组0单元与1单元, 配对序号为1; 数组1单元与2单元, 配对序号为2; 数组2单元与0单元, 配对序号为3. 检查每对顶点, 如果2个顶点都是旧点, 则一定存在一条反向边, 执行下一步.Step5. 设第i对的2个顶点都是旧点, 可以从这2个顶点的外出半边中比较, 选择其中一条作为反向半边, 并将其保存在映射表中, 同时完善反向半边所属的三角面对应的映射表设置. 反向半边的选择过程如下: 将第i对的两个顶点交换, 设得到起始顶点为V start, 终止顶点为V end; 对顶点V start做一环邻域遍历, 如果获得的顶点等于V end, 则该半边为选择的反向半边, 结束遍历.Step6. 保存f new到下标变量为N id的三角面数组容器单元中, 结束网格插入.定义了上述2个操作后, STL网格数据拓扑重建流程就是逐行读取STL文件记录, 每行记录一个三角面3个顶点坐标, 执行顶点查找和网格插入. 从上述重建步骤可以看出, STL重建算法简单, 效率较高, 并且可以重用于网格编辑.3.3构建实例和讨论上述数据结构和STL拓扑重建方法已经通过Visual C++ 2010和OpenGL开发平台编程实现. 同时, 对文献[4]给出的Surface_mesh半边数据结构和本文提出的数据结构进行3个STL网格模型的拓扑重建实验, 实验环境为Windows7操作系统, 主频2.6 GHz, 2.0 GB内存. 获得同一个三角网格模型在2个数据结构下的内存消耗和重建时间. 表1所示为这3个物体的STL模型的构建时间和内存资源占用数据.实际上, 从数据结构定义中也可以计算出它们不同的内存消耗. Surface_mesh半边数据结构是一个经优化后的基于边的半边数据结构, 在表达拓扑信息方面需要如下数据[4]: 顶点需要1个外向半边指针, 三角面需要1个参考半边指针, 半边结构中定义了指向目标点指针、下一半边指针、上一半边指针和所属面指针, 反向半边指针通过数组下标偏移获得(但需要连续存储), 这样一条半边需要4个指针变量, 每个指针变量占用4个字节. 如果一个网格模型中有n个顶点, 根据前面介绍的顶点、面和边的关系, 可以计算出总需要的内存为M1=4×(n+2n+24n)=108n字节. 而本文提出的基于半边编码数据结构为: 顶点需要1个外向半边标识,占1个4字节, 三角面需要3个顶点指针、3个反向半边标识, 共计6个4字节, 总需要的内存为M2= 4×(n+12n)=52n字节. 可以看出, 本文提出的数据。
