Topological Data Structure for Computer Graphics

Abstract

This research is motivated by the following well-known contradiction. In computer-aided design or modeling tasks, we generally represent surfaces using edge-based data structures as winged edge [Bau75], half-edge [MP78] [CP98], or quad-edge [GS85]. In contrast, real-time computer graphics represents surfaces with face-vertex meshes, since for surface rendering, there is no need for the explicit representation of edges. In this research we introduce a novel data structure for representation of triangle meshes. Our representation is based on the concept of face-vertex meshes with adjacencies, but we use some extra information and new ideas that greatly simplify the implementation of algorithms.