Spirale Reversi: Reverse decoding of the Edgebreaker encoding

Martin Isenburg           Jack Snoeyink

abstract:
We present a simple linear time algorithm for decoding Edgebreaker encoded triangle meshes in a single traversal. The Edgebreaker compression technique, introduced by Rossignac, encodes the topology of 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 by Szymczak and Rossignac 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 decompression technique that performs a single traversal and recreates the triangles in reverse order.

publication:

  • [is-sr-00.pdf slides] Martin Isenburg, Jack Snoeyink, Spirale Reversi: Reverse decoding of the Edgebreaker encoding, Canadian Conference on Computational Geometry 2000, 247-256, August 2000.
    ---> appeared as a journal version in Computational Geometry, Volume 20, Issue 1-2, pages 39-52, October 2001.
  • related publications:

  • [is-ff-00.pdf slides] Martin Isenburg, Jack Snoeyink, Face Fixer: Compressing Polygon Meshes with Properties, Proceedings of SIGGRAPH 2000, pages 263-270, July 2000.
  • [i-tsc-00.pdf slides] Martin Isenburg, Triangle Strip Compression, Proceedings of Graphics Interface 2000, pages 197-204, May 2000.
    ---> appeared as a journal version in Computer Graphics Forum, Volume 20, Issue 2, pages 91-101, June 2001.
  • [i-tf-00.pdf] Martin Isenburg, Triangle Fixer: Edge-based Connectivity Compression, European Workshop on Computational Geometry 2000, pages 18-23, March 2000.
  • downloads:

  • slides: sr.ppt