With the increase in complexity of graphics scenes, data structures have become a key element in computer geometry and graphics. Depending on the effectiveness of the structure organization and the richness of the data contained, geometry engines will be able to traverse the structure for swift or slow rendering.

The authors propose a compact representation of general planar meshes, called star-vertex. They review previous work in this area from between 1972 and 1999, and dive quickly into the organization, advantages, and specific aspects of their proposed representation. The structure organization offers a very compact way of storing the actual geometry data, avoiding some of the expensive point/vertex repetition often found in quad meshes or triangle strips data structures. Several sets of pointers or indices are associated with the vertices to traverse the structure, offering more flexibility than in the traditional fixed representation associated with common planar meshes structures. A set of C++ operators to help in manipulating the structure in a high-level programming environment is also proposed.

In their performance tests, the authors traverse star-vertex structures at the application level and use OpenGL for the actual geometry interpretation and rendering. This standard graphics library offers many advantages, but may not offer the absolute best performance, as the star-vertex structure will eventually end up as “duplicated” and stored as standard triangle strips or quad meshes in OpenGL display lists. The use of an immediate mode rendering package would prevent this duplication, and assuming the star-vertex structure is implemented as one of the native graphics primitives, would offer the best possible performance by taking full advantage of the structure’s special characteristics.

The paper concentrates on the compactness/traversal time ratio. This is an important metric when dealing with huge graphics data structures, since the time it takes to find and interpret data generally grows faster than the size of the data, due to the increased complexity. Empirical evidence shows that the star-vertex structure provides a proportional behavior between size and traversal performance; for example, a gain of 45 percent in the structure size results in an increase of 44 percent in the traversal time.

With the star-vertex structure, the authors propose a new way of storing and representing data at the application level. The programmer or user can balance data compactness and traversal performance. More effort is needed to investigate the possibilities that a native implementation in an immediate mode library would offer.