中文摘要：

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

英文摘要：

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.