Directed Edges - A Scalable Representation For Triangle Meshes

In a broad range of computer graphics applications the representation of geometric shape is based on triangle meshes. General purpose data structures for polygonal meshes typically provide fast access to geometric objects (e.g. points) and topologic entities (e.g. neighborhood relation) but the memory requirements are rather high due to the many special configurations. In this paper we present a new data structure which is specifically designed for triangle meshes. The data structure enables to trade memory for access time by either storing internal references explicitly or by locally reconstructing them on demand. The trade-off can be hidden from the programmer by an object-oriented API and automatically adapts to the available hardware resources or the complexity of the mesh (scalability).