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. Th e encoding algorithm visits every triangle of the mesh in a depth-first ord er. The original decoding algorithm recreates the triangles in the same ord er they have been visited by the encoding algorithm and exhibits a worst ca se time complexity of O(n(2)). More recent work (Rossignac and Szymczak, 19 99) uses the same traversal order and improves the worst case to O(n). Howe ver, for meshes with handles multiple traversals are needed during both enc oding and decoding. We introduce here a simpler decoding technique that per forms a single traversal and recreates the triangles in reverse order. (C) 2001 Elsevier Science B.V. All rights reserved.