Creating volume models from edge-vertex graphs

Abstract

The design of complex geometric models has been and will continue to be one of the limiting factors in computer graphics. A careful enumeration of the properties of topologically correct models, so that they may be automatically enforced, can greatly speed this process. An example of the problems inherent in these methods is the “wire frame” problem, the automatic generation of a volume model from an edge-vertex graph. The solution to this problem has many useful applications in geometric modelling and scene recognition. This paper shows that the “wire frame” problem is equivalent to finding the embedding of a graph on a closed orientable surface. Such an embedding satisfies all the topological properties of physical volumes. Unfortunately graphical embeddings are not necessarily unique. But when we restrict the embedding surface so that it is equivalent to a sphere, and require that the input graph be three-connected, the resulting object is unique. Given these restrictions there exists a linear time algorithm to automatically convert the “wire frame” to the winged edge representation, a very powerful data structure. Applications of this algorithm are discussed and several examples shown.