A Topological Data Structure Using Coding of Half-edges for Triangle Meshes

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 unsigned 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 demonstrates the memory footprint of the presented data structure is reduced greatly.