Local specification of surface subdivision algorithms

Colin Smith, Przemyslaw Prusinkiewicz, and Faramarz Samavati
Department of Computer Science, University of Calgary
Calgary, Alberta, Canada T2N 1N4


Many polygon mesh algorithms operate in a local manner, yet are formally specified using global indexing schemes. This obscures the essence of these algorithms and makes their specification unnecessarily complex, especially if the mesh topology is modified dynamically. We address these problems by defining a set of local operations on polygon meshes represented by graph rotation systems. We also introduce the vv programming language, which makes it possible to express these operations in a machine-readable form. The usefulness of the vv language is illustrated by the application examples, in which we concentrate on subdivision algorithms for the geometric modeling of surfaces. The algorithms are specified as short, intuitive vv programs, directly executable by the corresponding modeling software.


C. Smith, P. Prusinkiewicz, F. Samavati: Relational specification of subdivision algorithms. Applications of Graph Transformations with Industrial Relevance (AGTIVE 2003): Lecture Notes in Computer Science 3062, pp. 313-327

Download PDF here (258 kb), or download from the publisher's site.

Back to Publications