Spirale Reversi: Reverse decoding of the Edgebreaker encoding

We present a simple linear time algorithm for decoding Edgebreaker encoded triangle meshes in a single traversal. The Edgebreaker encoding technique, introduced by Rossignac (1999), encodes the connectivity of triangle meshes homeomorphic to a sphere with a guaranteed 2 bits per triangle or less. The encoding algorithm visits every triangle of the mesh in a depth-first order. The original decoding algorithm recreates the triangles in the same order they have been visited by the encoding algorithm and exhibits a worst case time complexity of O(n(2)). More recent work (Rossignac and Szymczak, 1999) uses the same traversal order and improves the worst case to O(n). However, for meshes with handles multiple traversals are needed during both encoding and decoding. We introduce here a simpler decoding technique that performs a single traversal and recreates the triangles in reverse order. (C) 2001 Elsevier Science B.V. All rights reserved.