Topological Surgery Encoding Improvements Based on Adaptive Bit Allocation and DFSVQ

Presented by

Scott Musler

Multimedia Communications and Visualization Laboratory

Department of Computer Engineering and Computer Science

University of Missouri - Columbia

• The present discussion is concerned with improving the so-called Topological Surgery (TS) method to compress 3D models
• Polygonal models, especially those defined by triangles, are the primary 3D representation in industry, entertainment, manufacturing, and architecture
• They consist of V vertices and F triangles, with one or more property arrays (normals, colors and textures)
• Yet, the current ASCII representation of polygonal models is hampered, due to limited bandwidth for transmission, and large file sizes (due to 32-bit accuracy and redundancy of information)
• The TS scheme achieves compression ratios of up to 50:1
• In the TS scheme, there is no loss of polygon connectivity, and it is claimed that there are visually imperceptible changes in model appearance due to slight losses in geometry position information (due to quantization of vertex positions)

• Polygonal meshes are the most common way to represent 3D objects in today’s world
• The TS scheme is limited to triangles, which will be focused on
• For a triangular polygonal mesh, usually there are twice as many triangles as vertices
• For 3D meshes, there are 3 vertices per triangle, each with an x-, y-, and z-position (so » 6 references total per vertex (2 x-, y- and z-references))
• Michael Deering proposed a method (using generalized triangle strips of width no greater than 16, and quantization of vertex positions based on a single ancestor) to obtain 11 bits/vertex
• TS method obtains 2-3 times better compression ratios and, as a by-product, generates long triangle strips
• The objective is to find a good algorithm to generate these triangle strips

• One must construct a structure for good quantization of vertex positions
• This is achieved by constructing a vertex tree (VTREE) and quantizating vertex positions using a linear predictor to get vertex corrections (VCOR)
• This computation is considered NP-complete, due to its similarity to the Hamiltonian path (an optimal tree using each vertex once and only once, with no cycles) problem
• Also, one must construct a structure for triangle reconstruction
• This is achieved by constructing a triangle tree (TTREE) and the marching pattern
• In order to construct VTREE and TTREE, one must have a method to facilitate the building of these structures
• To do this, one layers the triangles of the mesh (see Figure 1)
• A vertex is chosen as the start vertex and all triangles incident to it are the first layer
• Subsequently, all triangles incident to triangles of layer N compose triangle layer N+1
• This will lead to breaking the mesh up into cut edges (edges that will be part of VTREE) and marching edges (those not of VTREE)

• The layering of the mesh helps determine the vertex tree, because layering divides the mesh up into near-circular rings (for the most part)
• Most of those edges which divide the layer boundaries are cut edges
• Cut edges amount to the path that the vertex tree takes (see Figure 2)
• The "rings" are traversed in a counter-clockwise fashion until all vertices have been used
• This constitutes a tree structure for the compression of vertex positions
• Each run in the vertex tree has 3 values associated with it (run length, last bit, leaf bit)
• Run length is the length of the current run
• Last bit indicates that this is the last run from a current (branching) vertex
• Leaf bit indicates that the current run ends in a leaf vertex

• Once each run is accounted for, the vertex positions are quantized using a linear predictor (a method to predict a vertex position based on its K ancestors)
• The actual vertex positions are not compressed
• Using a linear predictor, the errors between predicted vertex positions (based upon 2, 3, or 4 ancestors) and actual positions are encoded instead of actual positions
• The linear predictor attempts to reduce the square of the errors

• Vertex positions are comprised of a 3-tuple (x-, y-, z-position)
• Initially each are 32-bit floating point values (much too large)
• First reduce the accuracy of the positions to 8-16 bits
• Then compute a predicted position for each vertex, compute the error (as it is of fewer bits) between actual and predicted position, and encode it using an entropy (lossless) coding technique (such as Huffman)
• The form is:

v _n = S _{(i=1 … P)} a _i * w _n-I , and Î _n = w _n - v _n

where v _n = predicted vertex position

a _i = linear predictor parameters

w _n = actual vertex position

P = number of ancestors to use

Î _n = error for a vertex position

• These corrections are termed the vertex corrections (VCOR)

• Then the bounding loop is constructed (a pre-order traversal of the VTREE of size (2V-2)) to help with the triangle tree and determination of the marching pattern
• The bounding loop "forms" the path the triangle tree takes

• The bounding loop provides a pathway for traversal of the triangles
• Edges that are not part of the vertex tree are the marching edges
• The marching edges are the edges that connect triangles within a run
• One "walks" around the mesh in a counter-clockwise fashion, picking up triangles and adding them to the triangle tree, using the bounding loop as a guide (ie: right or left moves along the bounding loop) to determine which vertex is added to the strip
• Adjacent triangles must share 2 vertices, so the two triangles differ by 1 vertex reference

• If the differing vertex is "right" along the bounding loop, it is a right move (see Figure 3); otherwise it is a left move
• Each right move is stored as a 1 and left moves are stored as 0’s
• These right/left constitute the marching pattern for each triangle run
• Each run in the triangle tree has 2 entries (run length, leaf bit)
• Run length is the length of the run, and leaf bit indicates if the current run ends in a leaf triangle
• Each run is considered a triangle strip
• Each run is stored as (run length, leaf bit, marching pattern (size (run length – 1))
• Branching triangles connect 3 runs in the triangle tree, and the rest of the triangles only connect 1 run in the triangle tree

1 4 3 1 (moved right)

1 5 4 1

2 5 1 0 (moved left)

2 6 5 1

2 7 6 1

2 8 7 1

3 8 2 0

3 9 8 1

3 10 9 1

4 10 3 0

4 11 10 1

4 12 11 1

5 12 4 0

5 13 12 1

6 13 5 0

• Construct the vertex spanning tree and bounding loop
• Determine vertex position errors by using the linear predictor (the user specifies the number of ancestors to use, and the number of bits to represent the vertices)
• Determine the triangle tree
• Compute the marching pattern
• Encode the vertex spanning tree, triangle spanning tree, vertex position errors, the marching pattern, and any fixed-size information (such as the size of these structures, and accuracy of the vertex positions, the linear prediction parameters, etc.)

• Obtain size of structures, accuracy information, number of ancestors to use in linear predictor, and linear predictor parameters
• Obtain and reconstruct vertex tree structure
• Reconstruct vertex positions
• Construct the bounding loop
• Obtain and reconstruct triangle tree structure
• Reconstruct the triangles, using the bounding loop, TTREE, and marching pattern

• Normals, colors and textures are compressed in the same manner as the vertex positions
• They are first quantized to the desired accuracy (generally using the same accuracy as the vertex positions, i.e. 8-16 bits)
• They are encoded in the same order that the vertex positions were encoded, and also may use the linear prediction "method"

Vertices = V (4) Triangles (4) Ancestors = A (1)

X_param₁ … X_param_A (4 each)

Y_param₁ … Y_param_A (4 each)

Z_param₁ … Z_param_A (4 each)

Accuracy (1) March_Cnt = M (4)

Vertex_Run_Cnt = R (1) V_accuracy = VA (1)

V_len (VA bits) V_leaf (1 bit) V_last (1 bit) } R of them

Triangle_Run_Cnt = R (1) T_accuracy = TA (1)

T_len (TA bits) T_leaf (1 bit) } T of them

March_Pattern } M bits

VCOR’s } V-1 of them, entropy encoded

• Currently, Taubin uses a fixed size number of bits to encode the Vertex run lengths in the VTREE
• Assume the following lengths, leaf and last values in VTREE with 5 runs
• (300, 0, 1) (109, 1, 0) (4, 0, 1) (3, 1, 0) (1, 1, 1)
• The largest run length (300) fixes the size of the bits used to encode the run lengths (in this case, 10 bits)
• They would then be encoded as: (0100101100 01) (0001101101 10) (0000000100 01) (0000000011 10) and (0000000001 11)
• Proposed solution reduces the run length values, mainly for short runs
• If a run length is less than the number of bits used to encode the largest run length, it consists of a sequence of (length - 1) zeros, and then a 1 bit
• Also must indicate if the run is encoded using the "fixed" size, or the alternate method, so 1 bit is used
• The result would be 3 bits (encoding method, leaf bit, last bit) followed by the bit stream for the run length

• A 0 indicates use "fixed length", and 1 indicates use adaptive method
• This is termed the adaptive bit allocation method
• Result would be encoded as follows:
• 001 (0100101100) 010 (0001101101) 101 (0001) 110 (001) and 111 (1)
• The same encoding scheme would be done for TTREE, without the last bit
• Results for two models are below

(bits) (bits) (bits)

Proposed 14,941 459 15,400

Proposed 7,592 976 8,568

• Authors use Dynamic Finite State Vector Quantization (DFSVQ) for vector quantization and correction storage
• They claim it achieves smaller distortion, and better visual quality than conventional methods
• Basic structure is depicted in figure 3
• When vector Vn is input, a subcodebook Sn is constructed from a supercodebook through next-state function f in reordering procedure

S_n = f (V_n-1, …, V_n-k)

• V_n-1, …, V_n-k are k ancestor vectors which are reconstructed from the neighboring blocks
• Next-state function f uses the previous reconstructed vectors to predict the current subcodebook
• Then V_n-1 is encoded to a vector that has the least error to V_n in the subcodebook S_n
• In the encoder, mapping function j is given by

I_n = j (V_n, S_n)

• It encodes vector V_n into I_n in subcodebook S_n, where I_n is the index of code vector that is the closes to input vector V_n
• In the decoder, mapping function j , is given by

V_n = j (S_n, I_n)

• It indexes the same subcodebook as the encoder and reproduces code vector V_n
• To measure distortion between V_n and V_n, Euclidean distance is used
• Distortion is defined as follows

D = sqrt ( (x_n - x_n)² + (y_n - y_n)² +(z_n - z_n)² )

• (x_n , y_n , z_n) are the actual position of vector V_n, and (x_n , y_n , z_n) are the coordinates of reproduced vector V_n
• Results are on the subsequent page

Bits/Vertex Distortion Bits/Vertex Distortion

(LP method) 12.00 225.64 12.00 520.34

10.40 16.95 10.38 388.92

J. Woo Park, K. Woen Song, H. Young Lee, J. Yeal Nam, and Y. Ha, "Topological Surgery Encoding Improvements Based on Adaptive Bit Allocation and DFSVQ", "IEEE Transactions on Circuits and Systems for Video Technology", Volume 9, No. 2, March 1999, pp. 370-377.