Kallmann and Thalmann present a new data structure, called the “star-vertex,” for storing and accessing planar polygonal meshes. The most common representation used for polygon meshes is the polygon or triangle list (indexed face set), which consists of a list of x,y,z vertices followed by a set of polygons specified by indexing into the vertex list. While this representation is compact, it does not inherently contain adjacency information, such as which polygons bound a particular edge, or which edges emanate from a particular vertex. These types of queries are necessary for computational geometry and computer graphics applications. However, with increases in mesh size, it is important to store the adjacency information in as compact a way as possible. The star-vertex is a “compact” and general adjacency data structure. The data structure and some basic traversal algorithms are described using C++.

The paper is very well written, and a sample mesh is shown that illustrates the data structure and traversals clearly (the basic implementation is available online). More compact versions of the original data structure are discussed with the associated algorithmic tradeoffs. The different forms of the star-vertex data structure were compared with existing adjacency data structures such as the Directed-Edge and Quad-Edge, within an incremental Delaunay triangulation program. Although the star-vertex is not always the fastest or most compact structure, it is more general than others, since it can handle all types of polygonal meshes.