EdgeBreaker Data
Shells with the TKSH_CONNECTIVITY_COMPRESSION bit set have their vertex location and connectivity data combined into an encoding according to the algorithm presented by Jarek Rossignac in 1998. The remainder of this description will assume familiarity with that algorithm. Please see:
"Edgebreaker: Connectivity compression for triangle meshes", J. Rossignac. IEEE Transactions on Visualization and Computer Graphics, Vol. 5, No. 1, pp. 47-61, January - March 1999.
Overall Organization
Header |
Opcodes |
pad to 4-byte boundary |
MTable |
pad to 4-byte boundary |
Points |
pad to 4-byte boundary |
Normals |
The Header and MTable sections are relatively simple structures. The opcodes section is an array of enumerated types. The points section is described in detail in the notes section.
Headerbyte scheme, byte mtable_scheme, byte points_scheme, byte normals scheme, int opslen, int mtable length, int points length, int point count, int normals length
scheme | identification for the overall edgebreaker data format. Only one such format exists at this point, so this will be zero |
mtable_scheme | identification for the format of the mtable. Set to zero |
points_scheme | identification for the points format. Two formats currently exist, so this may be zero or one |
normals_scheme | Identification of the format for encoding normals. Only one such format currently exists, so this will always be set to zero. Prior to version 7.0, this was padding that was ignored. |
opslen | length, in bytes, of the opcodes section |
mtable length | length, in bytes, of the mtable |
points length | length, in bytes, of the points data |
point count | number of unique points, after handling patches and dummies (see notes) |
normals length | length, in bytes of the normals data. |
Opcodes:
1 | CASE_C |
2 | CASE_L |
3 | CASE_E |
4 | CASE_R |
5 | CASE_S |
6 | CASE_M (obsolete) |
7 | CASE_M2 (obsolete, known as M' in the paper) |
MTable
int mtable flags, [int mlengths count (obsolete) ] [int m2stackoffsets count (obsolete) ] [int dummies count ] [int patches count ] [array of ints mlengths (obsolete) ] [array of ints m2stackoffsets (obsolete) ] [array of ints dummies ] [array of ints patches ] [6*float bounding ] [3*int quantizations ] [3*int quantizations_normals ]
MTable flags | bit field to indicate the presence or absence of the other fields in MTable |
mlengths count | number of entries in the mlengths array |
m2stackoffsets | number of entries in the m2stackoffsets array |
dummies | number of entries in the dummies array |
patches | number of entries in the patches array (note that each entry consists of 2 integers) |
mlengths | encodes the lengths of loop encountered with CASE_M operations. Surface preprocessing makes this unnecessary and obsolete |
m2stackoffsets | necessary information to connect loop self-intersections encountered as a result of topological handles. Surface preprocessing makes this unnecessary and obsolete |
dummies | identifiers of vertices that are inserted to fill holes in the surface. Any triangle touching such a vertex is removed at the end (see notes) |
patches | pairs of vertex identifiers. See the notes section for details. This array is of size 2*patches*sizeof(int). |
bounding | axis-aligned bounding cuboid for the purpose of interpreting the quantized point location data |
quantizations | the number of bits to be used in the quantization in each direction of the point locations. If not present, default values of {11,11,11} will be used |
quantizations_normals | the number of bits to be used in the quantization in each direction of the vertex normals. If not present, default values of {11,11,11} will be used |
MTable Flags:
0x01 | MTABLE_HAS_LENGTHS |
0x02 | MTABLE_HAS_M2STACKOFFSETS (obsolete) |
0x04 | MTABLE_HAS_M2GATEOFFSETS (obsolete) |
0x08 | MTABLE_HAS_DUMMIES |
0x10 | MTABLE_HAS_PATCHES |
0x20 | MTABLE_HAS_BOUNDING |
0x40 | MTABLE_HAS_QUANTIZATION |
0x80 | MTABLE_HAS_NORMALS_QUANTIZATION |
Notes
Dummies and Patches
Both of these fields are instructions to post-process the pseudo-manifolds that were produced by the standard algorithm into a generalized shell. As described below in "points", these will also have interactions with vertex location reconstruction.
Dummy vertices, as well any triangles that touch them are removed. Patches are pairs of vertex id's. The first of each pair is the old vertex id. The second is the new vertex id. The pairs are sorted such that the first of each is monotonically increasing. In processing the patches, we replace the first vertex id with the second. The old vertex id's are relative, the new ones are absolute. In other words, the old vertex id's are encoded as differences from the last one seen.
These two postprocessing steps are what allow us to avoid the inherently unstable CASE_M and CASE_M2 operations.
Points
Points are encoded as positions relative to a "parallelogram completion" prediction scheme. Let N be an unknown vertex location introduced as part of a triangle that contains vertices {N,A,B}. Suppose further that there is another triangle {B,A,C} that shares edge {A,B} with triangle {N,A,B}. If vertices A, B, and C are all known, vertex location A is predicted to lie at location A+(B-C).
We must, however, account for the case where one or more of vertices A, B and/or C are also unknown. If that is the case, we use the first valid vertex found among A, B, and C, in order, as the predicted location. If all three are unknown (e.g. the very first vertex), the predicted location is the origin {0,0,0} (remember, though, that we're in integer space quantized to the axis-aligned bounding cuboid). These vertices could be unknown if it is part of the loop that begins a new set of triangles or if it is a "dummy" vertex (see "dummies and patches" above).
Points are quantized to a uniform grid along the axis-aligned bounding cuboid so that we may reap the compression benefits of using small integers (the better the prediction of parallelogram completion, the deeper the compression). The axis-aligned bounding cuboid is chopped into the number of buckets specified by mtable's three "quantizations" values. If points_scheme in the edgebreaker header is 0, these differences are signed 16-bit shorts left for the LZ postprocess. We found, however, that LZ required too much computation time to pack the 16-bit shorts. This was the motivation for points_scheme 1. If points_scheme is 1, we do the packing ourselves into a cascading sequence of progressively larger samples that each have one escape sequence. Each sample is of one of the following forms.
2 bits in range [-1,1] or |
0x3, 6 bits in range [-31,31] or |
0x3F, 10 bits in range [-511,511] or |
0x3FF, 14 bits in range [-8191,8191] or |
0x3FFF, 18 bits in range [-131071,131071] or |
0x3FFFF, 22 bits in range [-2097151,2097151] or |
0x3FFFFF, 26 bits in range [-33554431,33554431] or |
0x3FFFFFF, 31 bits in range [-1073741824,1073741824] |
New to 7.0: edgebreaker data may now be encoded completely without points, so that the TKE_Shell opcode may separately specify uncompressed floats after the end of the edgebreaker data.
Normals
New as of version 7.0, normals are encoded in much the same way as points. The same algorithm of parallelogram completion is used to predict the locations. The only difference is simply that for the purpose of encoding, normals are assumed to lie in the standard 2x2x2 bounding cube: {[-1,-1,-1],[1,1,1]}. The same table of cascading ranges used in points_scheme 1 is used to pack the bits in normals_scheme 0. There is currently only one valid scheme for normals, normals_scheme 0.
Within the context of edgebreaker, we allow only one normal per vertex, and every vertex must have a normal. The HSF opcode that uses the edgebreaker interface, TK_Shell, has a more general (though less compressed) encoding that allows some normals to be left undefined.