loading...
A Divide and Conquer Algorithm for Triangle Mesh Connectivity Encoding
Tsinghua University, Beijing October 09-October 11
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/PCCGA.2002.116787310th Pacific Conference on Computer G ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Ioannis Ivrissimtzis, Max-Planck-Institut für Informatik
Christian Rössl, Max-Planck-Institut für Informatik
Hans-Peter Seidel, Max-Planck-Institut für Informatik
We propose a divide and conquer algorithm for the single resolution encoding of triangle mesh connectivity. Starting from a boundary edge we grow a zig-zag strip which divides the mesh into two submeshes which are encoded separately in a recursive process. We introduce a novel data structure for triangle mesh connectivity encoding, a binary tree with positive integer weights assigned to its nodes. The length of the initial strip is stored in the root of the binary tree, while the encoding of the left and right submesh are stored in the left and right subtree, respectively. We find a simple criterion determining which objects of this data structure correspond to triangle meshes. As the algorithm implicitly traverses the triangles of the mesh, it can be classified into the family of Edgebreaker like encoding schemes. Hence, the compression ratios, both in the form of theoretical upper bounds and practical results are similar to the Edgebreaker?s, while the simplicity and flexibility of the algorithm makes it particularly suitable for applications where the connectivity encoding is only a small part of the problem at hand.
Index Terms:
Connectivity Encoding, Recursive Algorithms, Binary Trees
Citation:
Ioannis Ivrissimtzis, Christian Rössl, Hans-Peter Seidel, "A Divide and Conquer Algorithm for Triangle Mesh Connectivity Encoding," pg, pp.294, 10th Pacific Conference on Computer Graphics and Applications (PG'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.