EdgeBreaker data
Shells with the TKSH_CONNECTIVITY_COMPRESSION bit set have their vertex locationand connectivity data combined into an encoding according to the algorithm presentedby Jarek Rossignac in 1998. The remainder of this description will assume familiaritywith 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.
Header byte 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) |
As in the paper, there are 5 basic operations that are used to describe connectivity, plus 2 extensions to take care of handles and holes. In our experience, the CASE_M and CASE_M2 extension operations were not sufficiently robust, so we rely on surface processing to make pseudomanifolds for which these two operations are unnecessary. These opcodes are left as unpacked 8-bit unsigned characters for HSF’s LZ postprocess to optimize.
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 |
The meaning of each of the bits should be obvious from the names that we have given them.
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 the next subsection on 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.
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]
Even though we still allow LZ to run on the output, the bad performance interactions were eliminated by the dramatic reduction in the redundancy of the point location data. We chose these lengths {2,6,10,14,18,22,26,31} for the samples based on statistical analysis of parallelogram prediction accuracy of several benchmark data sets. Although each sample’s range in this sequence ostensibly contains all of the previous ranges, those values should be treated as reserved for future expansion of the protocol.
New to 7.0: edgebreaker data may now be encoded completely without points, so that the TKE_Shell opcodemay 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.
