JAVA 3D allows programmers to specify geometry using a binary compressed geometry format. This compression format is used with APIs other than just Java 3D and can be used both as a runtime in-memory format for describing geometry, as well as a storage and network format. Eventually the full specification of the compressed geometry format described in this section will be part of its own stand-alone specification, but for completeness it is included as an appendix to the early specification of the Java 3D API.
Java 3D uses a compressed geometry format that allows 3D geometry to be represented in an order of magnitude less space than most traditional 3D representations, with very little loss in object quality. The compression is achieved through several layers of techniques.
For a binary format to be useful as an interchange format, it is essential that the format be thoroughly and unambiguously documented. This appendix attempts to completely specify all the details of the compressed geometry format. To ensure current and future compatibility, it is essential to use only the features explicitly specified in this document. For a binary format to be useful as an interchange format, it is essential that the format be thoroughly and unambiguously documented. This appendix attempts to completely specify all the details of the compressed geometry format. To insure current and future compatibility, it is essential to use only the features explicitly specified in this document. Any features, fields, usage, and so on. not specified in the document should be considered illegal, and their usage would result in invalid compressed geometry data. "Invalid" means that using such a construct will be incompatible with current implementations or will break future implementations. This document will point out many of the constructs that would cause the data to be invalid.
B.1 Compression
The process of geometry compression is as follows:
1. The geometry to be compressed is converted into a generalized mesh form, which allows a triangle to be, on average, specified by 0.80 vertices.
2. The data for each vertex component of the geometry is converted to the most efficient representation format for its type and then quantized to as few bits as possible.
3. These quantized bits are differenced between successive vertices, and the results are modified Huffman-encoded into self-describing variable-bit-length data elements.
4. These variable-length elements are strung together into a final compressed geometry block using compressed geometry's seven geometry instructions.
B.2 Decompression
For pure software implementations, upon receipt, compressed geometry blocks are decompressed into the local host's preferred geometry format by reversing the compression process. This decompression can be performed in a lazy manner, avoiding full expansion into memory until the geometry is needed for rendering.
B.3 Appendix Organization
Before the bit details of the compression can be specified, several of the concepts used in compressed geometry need elaboration. The first several sections are an expansion of our SIGGRAPH '95 paper on compressed geometry.1
B.4 Generalized Triangle Strip
A generalized triangle strip is a generalization of the concept of a "zig-zag" and triangle fan. It is a sequence of vertices in which each vertex contains a two-bit replacement code. This replacement code defines how the present vertex is to be combined with previous vertices to form the next triangle. The replacement bits can also be thought of as a generalization of the "move/draw" bit used for lines.
A stack of the last three vertices used to form a triangle is kept. The three vertices are labeled oldest, middle, and newest. An incoming vertex of type replace_oldest causes the oldest vertex to be replaced by the middle, the middle to be replaced by the newest, and the incoming vertex to become the newest. This corresponds to a PHIGS PLUS triangle strip (sometimes called a "zig-zag" strip). The replacement type replace_middle leaves the oldest vertex unchanged, replaces the middle vertex by the newest, and makes the incoming vertex become the newest. This corresponds to a triangle fan.
The replacement type restart marks the oldest and middle vertices as invalid, and the incoming vertex becomes the newest. Generalized triangle strips must always start with this code. A triangle will be output only when a replacement operation results in three valid vertices.
Restart corresponds to a "move" operation in polylines and allows multiple, unconnected, variable-length triangle strips to be described by a single data structure passed in by the user, greatly reducing the overhead. The generalized triangle strip's ability to effectively change from "strip" to "fan" mode in the middle of a strip allows more complex geometry to be represented compactly and requires less input data bandwidth. The restart capability allows several pieces of disconnected geometry to be passed as one data block. Figure B-1 shows a single generalized triangle strip and the associated replacement codes.
Triangles are normalized such that the front face is always defined by a counterclockwise vertex order after transformation (assuming a right-handed coordinate system). To support this, there are two flavors of restart: restart (counterclockwise and restart_reverse (clockwise). The vertex order is reversed after every replace_oldest but remains the same after every replace_middle.
Figure B-1 
A Generalized Triangle Strip
B.5 Generalized Triangle Mesh
The first stage of compressed geometry is to convert triangle data into an efficient linear strip form: the generalized triangle mesh. This is a near-optimal representation of triangle data, given fixed storage.
The existing concept of a generalized triangle strip structure allows for compact representation of geometry while maintaining a linear data structure. That is, the geometry can be extracted by a single monotonic scan over the vertex array data structure. This is very important for pipelined hardware implementations. A data format that requires random access back to main memory during processing is problematic.
However, by confining itself to linear strips, the generalized triangle strip format leaves a potential factor of two (in space) on the table. Consider the geometry in Figure B-2.
While it can be represented by one triangle strip, many of the interior vertices appear twice in the strip. This is inherent in any approach wishing to avoid references to old data. Some systems have tried using a simple regular mesh buffer to support reuse of old vertices, but there is a problem with this approach in practice: In general, geometry does not come in a perfectly regular rectangular mesh structure.
The generalized technique employed by compressed geometry addresses this problem. Old vertices are explicitly pushed into a queue and then explicitly referenced in the future when the old vertex is desired again. This fine control supports irregular meshes of nearly any shape. Any viable technique must recognize that storage is finite; thus, the maximum queue length is fixed at 16, requiring a four-bit index. We refer to this queue as the mesh buffer. The combination of generalized triangle strips and mesh buffer references is referred to as a generalized triangle mesh.
The fixed mesh buffer size requires all tessellators or restripifiers for compressed geometry to break up any runs longer than 16 unique references. Since compressed geometry is not meant to be programmed directly at the user level, but rather by sophisticated tessellators or reformatters, this is not too onerous a restriction. Sixteen old vertices allow up to 94 percent of the redundant geometry to avoid being respecified. Figure B-2 also contains an example of a general mesh buffer representation of the surface geometry.
Figure B-2 A Generalized Triangle Mesh
The language of compressed geometry supports the four vertex replacement codes of generalized triangle strips (replace oldest, replace middle, restart, and restart reverse) and adds another bit in each vertex header to indicate if this vertex should be pushed into the mesh buffer. The mesh buffer reference instruction has a four-bit field to indicate which old vertex should be rereferenced, along with the two-bit vertex replacement code. The semantics of a mesh buffer reference is that they do not have an option to repush their data into the mesh buffer; old vertices can be recycled only once.
Geometry rarely is composed purely of positional data; generally a normal and/or color are also specified per vertex. Therefore, mesh buffer entries are required to contain storage for all associated per-vertex information (specifically including normals, and colors.
For maximum space efficiency, when a vertex is specified in the data stream, (pervertex) normal and/or color information should be directly bundled with the position information. This bundling is controlled by two state bits: bundle normals with vertices (bnv) and bundle colors with vertices (bcv). When a vertex is pushed into the mesh buffer, these bits control whether its bundled normal and/or color are pushed as well. During a mesh buffer reference instruction, this process is reversed. The two bits specify if a normal and/or color should be inherited from the mesh buffer storage or inherited from the current normal or current color.
There are explicit instructions for setting these two current values. An important exception to this rule occurs when an explicit "set current normal" instruction is followed by a mesh buffer reference, with the bnv state bit active. In this case, the former overrides the mesh buffer normal. This allows compact representation of hard edges in surface geometry. The analogous semantics are also defined for colors, allowing compact representation of hard edges in images embedded as geometry.
B.6 Position Representation and Quantization
The 8-bit exponent of 32-bit IEEE floating-point numbers allows positions literally to span the known universe: from a scale of 100 billion light years down to the radius of subatomic particles. However, for any given tessellated object the exponent is really specified just once by the current modeling matrix; within a given modeling space, the object geometry is effectively described with only the 24-bit fixed-point mantissa. Visually, in many cases far fewer bits are needed; thus the language of compressed geometry supports variable quantization of position data down to as little as one bit. The maximum number of bits supported is at most 16 bits of precision per component of position.
We still assume that the position and scale of the local modeling spaces are specified by full 32-bit or 64-bit floating-point coordinates. If sufficient numerical care is taken, several such modeling spaces can be stitched together without cracks, forming seamless geometry coordinate systems with much greater than 16-bit positional precision.
Most geometry is local, so within the 16-bit (or less) modeling space (of each object), the delta difference between one vertex and the next in the generalized mesh buffer stream is very likely to be less than 16 bits in significance. Indeed, one can histogram the bit length of neighboring position deltas in a batch of geometry and, based on this histogram, assign a variable-length code to represent the vertices compactly. The typical coding used in many other similar situations is customized Huffman code; this is the case for compressed geometry. The details of the coding of position deltas will be discussed later, in the context of color and normal delta coding.
B.7 Color Representation and Quantization
We treat colors similar to positions, but without using negative values. Thus RGB
color data is first quantized to 15-bit unsigned fraction components, and a zero sign bit is added to form a 16-bit signed number. These are absolute linear reflectivity values, with 1.0 representing 100 percent reflectivity. An additional parameter allows color data to be quantized effectively to any amount less than 16 bits; that is, the colors can all be within a 5-5-5 RGB color space. (The field is optional, controlled by the color alpha present (cap) state bit.) Note that this decision does not necessarily cause mach banding on the final rendered image; individual pixel colors are still interpolated between these quantized vertex colors, and vertices also are subject to lighting.
The same delta coding used for color components is used for positions. Compression of color data is where compressed geometry and traditional image compression face the most similar problem. However, many of the more advanced techniques for image compression were rejected for geometry color compression because of the difference in focus.
Image compression makes several assumptions about the viewing of the decompressed data that cannot be made for compressed geometry. In image compression, it is known a priori that the pixels appear in a perfect rectangular array, and that when viewed, each pixel subtends a narrow range of visual angles. In compressed geometry, one has almost no idea what the relationship between the viewer and the rasterized geometry will be.
In image compression, it is known that the spatial frequency of the displayed pixels on the viewer's eyes is likely higher than the human visual system's color acuity. This is why colors are usually converted to yuv space, so that the uv color components can be represented at a lower spatial frequency than the y (intensity) component.
Usually the digital bits representing the subsampled uv components are split up among two or more pixels. Compressed geometry cannot take advantage of this because the display scale of the geometry relative to the viewer's eye is not fixed. Also, given that compressed triangle vertices are connected to four to eight or more other vertices in the generalized triangle mesh, there is no consistent way of sharing "half" the color information across vertices.
Similar arguments apply for the more sophisticated transforms used in traditional image compression, such as the discrete cosine transform. These transforms assume a regular (rectangular) sampling of pixel values and require a large amount of random access during decompression.
B.8 Normal Representation and Quantization
Probably the most innovative concept in compressed geometry is the method of compressing surface normals. Traditionally, 96-bit normals (three 32-bit IEEE floating-point numbers) are used in calculations to determine 8-bit color intensities. Theoretically, 96 bits of information could be used to represent 296 different normals, spread evenly over the surface of a unit sphere. This is a normal every 2-46 radians in any direction. Such angles are so exact that by spreading angles out evenly in every direction from earth, you could point out any rock on Mars with subcentimeter accuracy.
But for normalized normals, the exponent bits are effectively unused. Given the constraint |N| = 1, at least one of Nx, Ny, or Nz must be in the range of 0.5 to 1.0. During rendering, this normal will be transformed by a composite modeling orientation matrix T: N' = N · T.
Assuming the typical implementation in which lighting is performed in world coordinates, the view transform is not involved in the processing of normals. If the normals have been pre-normalized, then to avoid redundant renormalization of the normals, the composite modeling transformation matrix T is typically pre-normalized to divide out any scale changes, and thus
- T0,02 + T1,02 + T2,02 = 1, etc.
During the normal transformation, floating-point arithmetic hardware effectively truncates all additive arguments to the accuracy of the largest component. The result is that for a normalized normal being transformed by a scale-preserving modeling orientation matrix, the numerical accuracy of the transformed normal value is reduced to no more than 24-bit fixed-point accuracy in all but a few special cases.
Even 24-bit normal components are still much higher in angular accuracy than the (repaired) Hubble space telescope. After empirical tests, it was determined that an angular density of 0.01 radians between normals gave results that were not visually distinguishable from finer representations. This works out to approximately 100,000 normals distributed over the unit sphere. In rectilinear space, these normals still require high accuracy of representation; we chose to use 16-bit components that include one sign and one guard bit.
This still requires 48 bits to represent a normal. But since we are interested only in 100,000 specific normals, in theory a single 17-bit index could denote any of these normals. The next section shows how it is possible to take advantage of this observation.
B.8.1 Normals as Indices
The most obvious hardware implementation for converting an index of a normal on the unit sphere back into an Nx Ny Nz value is by table look-up. The problem is the size of the table. Fortunately, several symmetry tricks can be applied to reduce the size of the table greatly (by a factor of 48).
First, the unit sphere is symmetrical in the eight quadrants by sign bits. In other words, if we let three of the normal representation bits be the three sign bits of the XYZ components of the normal, then we need only to find a way to represent one eighth of the unit sphere. The all positive sign bit octant of the unit sphere is shown in bold outline on the left half of Figure B-3. This 000 sign bit octant will be referred to as the prime octant.
Second, each octant of the unit sphere can be split into six identical pieces by folding about the planes X = Y, X = Z, and Y = Z. Such a division of the prime octant is shown in Figure B-3. The six possible sextants are encoded with another three bits. Now only 1/48 of the sphere remains to be represented.
This reduces the 100,000-entry look-up table by a factor of 48, requiring only about 2,000 entries, small enough to fit into an on-chip ROM look-up table. This table needs 11 address bits to index into it, so including our previous two 3-bit fields, the result is a grand total of 17 bits for all three normal components.
Representing a finite set of unit normals is equivalent to positioning points on the surface of the unit sphere. While no perfectly equal angular density distribution exists for large numbers of points, many near-optimal distributions exist. Thus in theory one of these with the same sort of 48-way symmetry described earlier could be used for the decompression look-up table. However, several additional constraints mandate a different choice of encoding:
Figure B-3 Encoding of the Six Sextants of Each Octant of a Sphere
For all these reasons, we decided to use a regular grid in the angular space within one sextant as our distribution. Thus, rather than a monolithic 11-bit index, all normals within a sextant are much more conveniently represented as two 6-bit orthogonal angular addresses, revising our grand total to 18 bits. Just as for positions and colors, if more quantization of normals is acceptable, then these 6-bit indices can be reduced to fewer bits; thus absolute normals can be represented using anywhere from 18 to as few as 6 bits. But as will be seen, we can delta-encode this space, further reducing the number of bits required for high-quality representation of normals.
B.8.2 Normal Encoding Parameterization
Points on a unit radius sphere are parameterized by two angles, 
and 
, using spherical coordinates. is the angle about the Y-axis; is the longitudinal angle from the y = 0 plane. The mapping between rectangular and spherical coordinates is as follows:
 |
(Eq. B.1) |
Note that many different incompatible definitions of spherical coordinates exist within mathematics and engineering. For the purposes of compressed geometry, spherical coordinates used are those defined by equation B.1.
Points on the sphere are folded, first by octant and then by sort order of xyz into one of six sextants. All the table encoding takes place in the positive octant, in the region bounded by the half spaces:
-
This triangular-shaped patch runs from 0 to 
/4 radians in , and from 0 to as much as 0.615479709 radians in : max.
Quantized angles are represented by two n-bit integers 
and 
, where n is in the range of 0 to 6. The sextant coordinate system defined by these parameters is shown in Figure B-4, for the case of n = 6. For a given n, the relationship between these indices and is
 |
(Eq. B.2) |
These two equations show how values of 
and 
can be converted to spherical coordinates and , which in turn can be converted to rectilinear normal coordinate components via equation B.1.
To reverse the process, for example, to encode a given normal n into 
and 
, one cannot just invert equation B.2. Instead, the n must first be folded into the canonical octant and sextant, resulting in n'. Then n' must be dotted with all quantized normals in the sextant. For a fixed n, the values of 
and 
that result in the largest (nearest unity) dot product define the proper encoding of n.
Now the complete bit format of absolute normals can be given. The uppermost three bits specify the sextant, the next three bits specify the octant, and finally two n-bit fields specify 
and 
. The three-bit sextant field takes on one of six values, the binary codes for which are shown in Figure B-3.
Figure B-4 Sextant Coordinates
This discussion has ignored some details. In particular, the three normals at the corners of the canonical patch are multiply represented (6, 8, and 12 times). By employing the two unused values of the sextant field, these normals can be uniquely encoded as special normals. The normal subinstruction describes the special encoding used for two of these corner cases (14 total special normals).
This representation of normals is amenable to delta encoding. Within a given sextant, the delta code between two normals is simply the difference in 
and 
: 
and 
.
B.8.3 Special Warping Rules for Delta Normals
With some additional work, this can be extended to sextants that share a common edge. First we must define how sextants border each other. Consider the three edges of the sextant coordinate system as defined in Figure B-4, and also examine Figure B-3 to see the sextant connectivity within an octant and between octants. The three possible neighbors of a sextant are shown schematically in Figure B-5.
Figure B-5 Sextant Neighbors and Their Relationships
The left edge of a sextant will always be another sextant within the same octant, as will be the diagonal edge of a sextant. Note that the coordinate system of a sextant is defined only for coordinate values in the triangular region of the sextant.
For a given value of n (in the range of 1 to 6), where n is the number of bits of quantization of the sextant coordinates, the valid coordinates are bounded by 
0, 
0, and 
+
2n. For any given sextant number, the left and diagonal neighbors of that sextant are explicitly known. The bottom edge of a sextant will be the same sextant number, but in a different octant. The octant will differ from the current octant by the flip of exactly one of the sign bits. Which octant sign bit will be flipped is also explicitly known. The rules for finding each edge neighbor for any sextant are given in Table B-1.
In compressed geometry, all component delta fields and all component absolute fields (except component absolute normal fields) are represented by signed numbers. For each different coordinate component type, there are different wrap rules for what happens when a delta component overflows the absolute representation range. For positions, both positive and negative component values are legal, and overflowing past the largest positive component value is explicitly defined to wrap the coordinate to negative values while overflowing the most negative component value wraps to the positive values. For colors, negative component values are illegal, and wrapping out of the positive component values is illegal. For normals, special wrapping rules allow delta values to change the current sextant or octant in certain cases without explicitly specifying the new sextant or octant.
The special rules for wrapping during normal deltas follow:
- if
+ 
0 , 
+ 
0, 
+ 
+ 
+ 
2n :
- new
+ 
, new 
+ 
,
- current sextant and octant are unchanged.
- if
+ 
< 0 , 
+ 
0, -(
+ 
) + 
+ 
2n :
- new
-(
+ 
), new 
+ 
,
- current sextant is updated from left edge rules in Table B-1 and current octant is unchanged.
- if
+ 
0 , 
+ 
0, 
+ 
+ 
+ 
> 2n :
- new
2n - (
+ 
) , new 
2n - (
+ 
) ,
- current sextant is updated from diagonal edge rules in Table B-1 and current octant is unchanged.
- if
+ 
0 , 
+ 
< 0, 
+ 
- (
+ 
) 2n :
- new
+ 
, new 
-(
+ 
) ,
- current sextant is unchanged, and current octant is updated from bottom edge rules in Table B-1.
Any wrap that does not fall into one of these categories is an illegal delta and is not allowed within a valid compressed geometry stream.
(Note that while the wrapping is defined here in terms of a given normal component quantization value n, in most implementations the wrapping would be applied after the current component values and delta values have been normalized into the greatest allowed values, e.g., n = 6.)
B.9 Modified Huffman Encoding
There are many techniques known for minimally representing variable-length bit fields. For compressed geometry, we have chosen a variation of the conventional Huffman technique.
The Huffman compression algorithm takes in a set of symbols to be represented, along with frequency of occurrence statistics (histograms) of those symbols. From this, variable-length, uniquely identifiable bit patterns that allow these symbols to be represented with a near-minimum total number of bits are generated, assuming that symbols do occur at the frequencies specified.
Many compression techniques, including JPEG, create unique symbols as tags to indicate the length of a variable-length data field that follows. This data field is typically a specific-length delta value. Thus the final binary stream consists of (self-describing length) variable-length tag symbols, each immediately followed by a data field whose length is associated with that unique tag symbol.
The binary format for compressed geometry uses this technique to represent position, normal, and color data fields. For compressed geometry, these <tag, data> fields are immediately preceded by (a more conventional computer instruction set) opcode field. These fields, plus potential additional operand bits, are referred to as geometry instructions (see Figure B-6).
Traditionally, each value to be compressed is assigned its own associated label; for example, an xyz delta position would be represented by three tag/value pairs. However, the delta xyz values are not uncorrelated, and we can get both a denser and simpler representation by taking advantage of this fact.
In general, the xyz deltas statistically point equally in all directions in space. This means that if the number of bits to represent the largest of these deltas is n, then statistically the other two delta values require an average of n - 1.4 bits for their representation. Thus we made the decision to use a single field-length tag to indicate the bit length of 
x, y, and z.
This also means that we cannot take advantage of another Huffman technique that saves somewhat less than one more bit per component, but our bit savings by not having to specify two additional tag fields (for y and z) outweigh this. A single tag field also means that a hardware decompression engine can decompress all three fields in parallel, if desired.
Similar arguments hold for deltas of RGB values, and so here also a single field-length tag indicates the bit-length of the R, G, B, and (if present) fields.
Figure B-6 Bit Layout of Compressed Geometry Instructions
The u v index fields of both absolute normals and delta normals are also parameterized by a single value (n), which can be specified by a single tag.
We chose to limit the length of the Huffman tag field to the relatively small value of six bits. This was done to facilitate high-speed, low-cost hardware implementations. (A 64-entry tag look-up table allows decoding of tags in one clock cycle.) Three such tables exist: one each for positions, normals, and colors. The tables contain the length of the tag field, the length of the data field(s), a data normalization coefficient (the up-shift), and an absolute/relative bit.
The tag field can be 0 to 6 bits in length. Zero-length tags are used when every entry in the table is identical: same data length, same up-shift, and same absolute/relative bit. The tag becomes irrelevant because there is nothing to differentiate. In general, there are only a few specialized cases where zero-length tags are useful.
One additional complication was required to enable reasonable hardware implementations. As seen in a later section, all instructions are broken up into an eight-bit header and a variable-length body. Sufficient information to determine the length of the body is present in the header. But to give the hardware time to process the header information, the header of one instruction must be placed in the stream before the body of the previous instruction. Thus the sequence ... B0 H1B1 H2B2 H3 
has to be encoded as follows:
-
H1 B0 H2 B1 H3 B2 
This header forwarding is applied to all instructions. The vertex instruction optionally had one or two subfields that need forwarded headers. In these special cases the headers are only six bits in length, because no opcode is present.
B.10 Compressed Geometry Instructions
Java 3D's compressed geometry protocol defines seven instructions to be used in specifying 3D geometry and certain affiliated attributes. Table B-2 gives a brief overview of these instructions and some of their semantics. More detail of these instructions, including their bit layout, is given in the following sections.
B.11 Bit Layout of Compressed Geometry Instructions
Figure B-6 shows the bit-level layout of the seven geometry decompression instructions. Each instruction has a unique opcode and then some (usually fixed number of) arguments. In the case of the setColor instruction, the number of arguments can be either three or four, depending on the current setting of the cap bit (set by the setState instruction). In the case of the vertex instruction, the number of arguments also varies by the current setting of the setState instruction.
Table B-2 Compressed Geometry Instructions
|
Instruction
|
Description
|
|---|
|
vertex |
The primary instruction is vertex. A vertex instruction always specifies a 3D position, two generalized triangle strip replacement bits (rep), a mesh buffer push (mbp) bit, and it may optionally specify a normal and/or a color. The presence of normal or color data within a vertex instruction is controlled by two state bits known as the bundling bits: bnv and bcv, respectively.
|
setNormal,
setColor |
There are also two stand-alone instructions for specifying normals and colors: setNormal and setColor. These instructions may be freely interspersed with vertex instructions and semantically have (nearly) the same effect as normals or colors bundled directly with a normal. Once a color or normal value is specified, either directly or bundled with a vertex instruction, that color or normal will remain in effect as the current color or normal until a new value is specified. In this fashion, for example, a constant material color may be specified to apply to a forthcoming sequence of non-color-bundled vertices.
|
|
setState |
The setState instruction updates the value of the three state bits. Two of these bits are the normal and color bundling bits; the third is color alpha bundling.
|
|
mbr |
Mesh buffer reference. The mbr instruction allows any of the 16 vertices most recently pushed into the mesh buffer to be reused in place of a vertex instruction at this point. Two vertex replacement bits are also present.
|
|
setTable |
The setTable instruction allows a range of entries in one of the three Huffman decompression tables, all to be set to the same new value.
|
|
nop |
The variable length no-operation nop instruction allows the compression bit stream to be padded by a specified number of bits. This allows portions of the compression data to be 32-bit aligned when desired, as required at the end of a compressed geometry block.
|
The actual bit length of many of the components may vary, and, if so, a unique (dynamic) Huffman tag at the very start of any variable-length argument indirectly specifies the size of the argument.
B.12 Compressed Geometry Instruction Bit Details
The following subsections describe the bit details of the compressed geometry instructions as well as much of their associated semantics. Along with each instruction, its assembly (and disassembly) syntax is described.
B.12.1 nop Instruction
Assembly syntax: (nop <Bit count>)
The variable length no-operation (nop) instruction has an 8-bit opcode, a 5-bit count field, and a 0- to 31-bit field of zeros. The total length of the variable-length no-operation instruction is between 13 and 44 bits.
The variable-length nop instruction's primary use is to align compressed geometry instructions to word boundaries, when desired. This is useful if one wishes to "patch" a compressed geometry instruction in the middle of a stream without having to bit-align the patch.
B.12.2 setState Instruction
Assembly syntax: (setState {normalsBundled}
{colorsBundled} {alphaBundled})
The setState instruction has a 7-bit opcode, 3 bits of state to be set, and a spare, for a total length of 11 bits. The first and second state bits indicate if normals and/or colors will be bundled with vertex instructions, respectively. The third state bit indicates if colors will contain an alpha value, in addition to the standard RGB. The final state bit is unused and reserved for future use.
In the assembly syntax, the specific unbundling of a value is indicated by three unbundling tags: {normalsUnbundled}, {colorsUnbundled}, {alphaUnbundled}. The six possible bundling tags can be combined in almost any order. If a tag is not present for either bundling or unbundling a value, then the value is implicitly unbundled. It is an error to have both a bundled and an unbundled tag present for the same value in the same setState instruction.
B.12.3 setTable Instruction
Assembly syntax: (setTable <Table> <start fill>-<end fill>
<Data Length> <Up-shift> <A/R>)
The setTable instruction has a 5-bit op code, a 2-bit table field, a 7-bit address/range field, a 4-bit data length field, an absolute/relative bit, and a 4-bit up-shift field. The total instruction length is fixed at 23 bits. The table and address/range fields specify which decompression table entries to update; the remaining fields comprise the values to which to update the table entries.
The 2-bit table specifies for which of the three decompression tables this update is targeted:
The 7-bit address/range field specifies which entries in the specified table are to be set to the values in the following fields.
The idea is that table settings are made in aligned power-of-two ranges. The position of the first `1' bit in the address/range field indicates how many entries are to be consecutively set; the remaining bits after the first `1' are the upper address bits of the base of the table entries to be set. This also sets the length of the "tag" that this entry defines as equal to the number of address bits (if any) after the first `1' bit.
The data length specifies how large the delta values to be associated with this tag are; a data length of 12 implies that the upper 4 bits are to be sign extensions of the incoming delta value. Note that the data length describes not the length of the delta value coming in, but the final position of the delta value for reconstruction. In other words, the data length field is the sum of the actual delta bits to be read in plus the up-shift amount. For the position and color tables, the data length values of 1 to 15 correspond to lengths of 1 to 15, but the data length value of 0 encodes an actual length of 16, as a length of 0 makes no sense for positions and colors. For normals, a length of 0 is sometimes appropriate, and the maximum length needed is only 7. Thus for normals, the values 0 to 7 map through 0 to 7, and 8 to 15 are not used.
The up-shift value is the number of bits that the delta values described by these tags will be shifted up before being added to the current value. The up-shift is useful for quantizing the data to save space; it cannot be used to extend the range of the data represented. You are still limited to 16 bits (less for normals) for the resultant data even with a large up-shift value. The up-shift amount is essentially the number of low bits that you don't need to specify in the incoming data since they will always be zero. It is illegal for the up-shift to be greater than or equal to the data length.
So, there are three portions of the resultant data: the sign extension, the incoming data, and the up-shift. For example, if you have a position with a data length of 12 and an up-shift of 4, then the resultant data is made up of 4 sign extension bits in the high bits, 8 bits of incoming data, and 4 bits of zero in the low bits, for the up-shift.
The absolute/relative flag indicates whether this table entry describes values that are to be interpreted as an absolute reference or a relative delta-a 0 value indicates relative, a 1 value indicates absolute. Note that for normals, absolute references will have an additional six leading bits that describe the absolute octant and sextant.
B.12.4 mbr (meshBufferReference) Instruction
Assembly syntax: (mbr <rep> <index>)
Assembly syntax: <rep>:
The mbr (meshBufferReference) instruction has a 3-bit opcode, a 4-bit mesh buffer index field, and a 2-bit vertex replacement field, for a total length of nine bits.
The index specifies which element of the mesh buffer should be used to define the current vertex. A value of 0 indicates to use the most recent vertex that has been pushed into the mesh buffer (before this instruction). Larger values indicate successively less recent pushes. Only the most recent 16 pushes are addressable.
The two-bit vertex replacement field has the same triangle semantics as it does within the vertex instruction:
There is no mesh buffer repush bit; mesh buffer contents may be referenced multiple times until 16 newer vertices have been pushed: if a vertex is still needed, it must be resent.
In general, the semantics of executing a mesh buffer reference instruction is nearly the same as executing a vertex instruction with data fields identical to those contained at the indicated mesh buffer location. There are, however, several subtle differences. First, as previously indicated, a mesh buffer reference never causes new values to appear in the mesh buffer, nor does it cause any mesh buffer values to go away.
Second, the effects of any intervening setState instructions changing the bundling bits need to be considered. If normals were bundled when the vertex was originally pushed into the mesh buffer, but normals are not bundled when the mbr instruction is executed, the old normal value does not replace the current normal value. Instead, the mbr instruction will use the current setting of the normal value. The same logic applies to colors and alpha. An mbr instruction accesses only the mesh buffer for those vertex components that are currently bundled.
The inverse case is considered an error: If normals were not bundled at the time the vertex instruction pushed a vertex into the mesh buffer, but normals are bundled at the time of execution of the mbr instruction, the normal value will be undefined. Such a sequence will result in an invalid Compressed Geometry object. Once again, the same logic applies for colors. A push in a vertex instruction causes only the currently bundled vertex components to be stored into the mesh buffer.
There is one more special case: when normals are bundled, if a setNormal instruction was executed before an mbr instruction and the instructions executed between these two do not include any vertex or setState (or mbr) instructions, the semantics of normal override apply. The semantics are that rather than inheriting all the data fields of the vertex from the stored mesh buffer values, the normal value is instead taken from the current normal value, as set by the setNormal instruction. This is to allow for hard edges in otherwise shared geometry. The idea is that otherwise there is no logical reason for a setNormal instruction that would have been invalidated by the inheritance within the mbr instruction. Once again, a similar logic applies to setColor instructions and the generation of a color override condition. This supports hard edges in colors. Note that any overrides are invalidated by setState or vertex instructions and also are no longer in effect after an mbr instruction is encountered.
Another effect of overrides is to override the invalidity of normals or colors having not been bundled with vertices at the time of vertices being pushed into the mesh buffer.
B.12.5 Position Subinstruction
Assembly syntax: (Position <Tag> <X> <Y> <Z>)
The position subinstruction can appear only within a compressed geometry vertex instruction and always as the first subinstruction. The tag field can be between 0 and 6 bits in length; all three delta (or absolute) fields will have the same length, between 1 and 16 bits, for a range of lengths between 3 and 54 bits.
As usual, the first six bits of the subinstruction are actually forwarded ahead of the rest of the instruction. Depending on the length of the tag and delta fields, the first 6 bits might contain only the tag or the tag and some of the X field bits or any subset up to the entire subinstruction, if short enough. However, it is possible for the entire subinstruction to be too short. It is not allowed for the tag together with the X, Y, and Z fields to be smaller than the six bits that get forwarded. There can be no "empty" bits in the forwarded header. If necessary, the tag and/or delta (or absolute) fields must be expanded so that the total number of bits used for the entire subinstruction is at least six. (Note that the expanded fields must be correctly described in the decompression table entry for the tag. One cannot simply add padding within a position subinstruction to a field that was previously specified with a shorter length in a setTable instruction.)
For clarity, because it is by far the most typical case, the three coordinate bit fields are labeled X Y Z, though more properly they are X, Y, and Z fields; their actual interpretation is absolute or relative depending on the setting of that bit in the decompression table entry corresponding to the tag field. In both cases the fields are signed two's-complement numbers.
You must always specify at least one absolute position before using any relative positions. It is illegal to have a relative position before the first absolute position.
It appears that, depending on the current position, half of the possible delta values are illegal. (For ease of understanding these examples, we will treat positions as integers.) For instance, going +10,000 from 30,000 will wrap past the positive limit of 32,767 for signed 16-bit two's-complement arithmetic. However, this turns out to be very useful. For example, if your current X position is -20,000 and the next X position is 30,000 then the difference that you'd like to use as a delta is +50,000, which is not directly representable. When you compute that difference using 16-bit arithmetic, the value wraps to -15,536, which can be represented as a delta. When -15,536 is added back to -20,000 on decompression, instead of getting -35,536, again the 16-bit arithmetic wraps and we get 30,000, which is the desired result.
B.12.6 Color Subinstruction
Assembly syntax: (Color <Tag> <R> <G> <B> {<>})
The color subinstruction can appear within either a compressed geometry vertex instruction or a setColor instruction. The tag field can be between 0 and 6 bits in length; all three (or four) delta (or absolute) fields will have the same length, between 1 and 16 bits, for a range of lengths between 3 and 54 (or 70) bits. As usual, any subinstruction with a total length of less than 6 bits has trailing zeros added to pad the length to a minimum of 6 bits.
As usual, the first six bits of the subinstruction are actually forwarded ahead of the rest of the instruction. Depending on the length of the tag and delta fields, the first six bits might containonly the tag or the tag and some of the R field bits or any subset up to the entire subinstruction, if short enough. However, it is possible for the entire subinstruction to be too short. It is not allowed for the tag together with the R, G, and B (and ) fields to be smaller than the six bits that get forwarded. There can be no "empty" bits in the forwarded header. If necessary, the tag and/or delta (or absolute) fields must be expanded so that the total number of bits used for the entire subinstruction is at least six.
For clarity, because it is by far the most typical case, the color component bit-fields are labeled R G B (), though more properly they are R, G, and B fields: their actual interpretation is absolute or relative depending on the setting of that bit in the decompression table entry corresponding to the tag field. In both cases the fields are signed two's-complement numbers. A sign bit is required for absolute color components. Negative color components make no sense and are ill-defined, so the sign bit on absolute components should always be zero. Similarly for delta color components, a negative result from adding a delta component to the current component makes no sense, and so negative results are also ill-defined.
If the most recent setting of the cap bit by a setState instruction is zero, then no fourth (alpha) field will be expected and must not be present. If the cap bit was set, then the alpha field will be processed and must be present.
You must always specify at least one absolute color before using any relative colors. It is illegal to have a relative color before the first absolute color.
The rest of the graphics pipeline and frame buffer following the geometry decompression stage may choose not to use all (up to) 16 bits of color component information; in this case, it is acceptable to truncate the trailing bits during decompression. What the geometry decompression format does require is that color setting of any size up to 16 bits be supported, even if all the bits are not used. Typically, implementations may use just 12 bits, 8 bits, or even 5 bits from each color component.
B.12.7 Normal Subinstruction
Assembly syntax: absolute: (Normal <Tag><Sextant><Octant><
><
>)
Assembly syntax: relative: (Normal <Tag> <
> <
>)
Assembly syntax: special: (Normal <Tag> <Special>)
Assembly syntax: <Sextant>: 0,1,2,3,4,5 (as specified in Figure B-3)
Assembly syntax: Table B-3 shows the assembly format for specifying octants in the <octant> field of Normal subinstructions (as well as setNormal instructions).
Assembly syntax: Table B-4 shows the assembly syntax for specifying the special normals in the "Special" field of Normal subinstructions (as well as setNormal instructions).
The Normal subinstruction can appear within either a compressed geometry vertex instruction or a setNormal instruction. The tag field can be between 0 and 6 bits in length; the last two angle fields will have the same length, between 0 and 7 bits for deltas and between 0 and 6 bits for absolutes. Six more bits are always present for absolute normals. The range of sizes for a relative normal can be from 6 to 20 bits, and an absolute normal can be from 6 to 24 bits.
As usual, the first six bits of the subinstruction are actually forwarded ahead of the rest of the instruction. Depending on the length of the tag and delta fields, the first six bits might contain only the tag or the tag and some of the other field bits or any subset up to the entire subinstruction, if short enough. However, in the case of relative normals, it is possible for the entire subinstruction to be too short. It is not allowed for the tag together with the delta angle fields to be smaller than the six bits that get forwarded. There can be no "empty" bits in the forwarded header. If necessary, the tag and/or delta angle fields must be expanded so that the total number of bits used for the entire subinstruction is at least six.
A Normal subinstruction is interpreted as relative or absolute depending on the current setting of that bit in the decompression table entry corresponding to the tag field. Unlike the Position and Color subinstructions, the number of fields of a Normal instruction differs between the absolute and relative types.
When the subinstruction is relative, there are two delta angle fields after the tag field, both of the same length, up to seven bits. These two fields are signed two's-complement numbers. If, after delta addition, the resulting angle is outside the current sextant or octant, the sextant/octant wrapping rules (described elsewhere) apply. If zero-length angle fields are specified, this is equivalent to specifying a zero value for both fields, i.e., no change from the previous normal. It may be easier to use this method rather than turning off normal bundling for a small number of identical normals.
When the subinstruction is absolute, four bit fields follow the tag. The first is a three-bit (fixed-length) absolute sextant field, indicating in which of six sextants of an octant of the unit sphere this normal resides. The second field is also fixed at three bits, and indicates in which octant of the unit sphere the normal resides. The last two fields are absolute angles within the sextant and are unsigned positive numbers, up to six bits in length. If zero-length angle fields are specified, this is equivalent to specifying a zero for both fields.
At least one absolute normal must be specified before using any relative normals. It is an error to have any relative normals before the first absolute normal.
Note that sextants are triangular in shape; thus the range of valid angular coordinates within a sextant fills only half the square, plus the diagonal. Formally, after shift normalization, angular coordinates in ordinary absolute normals must obey the rule:
-
A number of normals lie on the edges or corners where sextants meet (e.g., at 
= 0 and 
= 0). These normals do not have a unique encoding; the same normal can be specified using different sextants or octants. All of these encodings are legal; usually the choice of encoding is decided by using the one that makes it the easiest to compute deltas from the previous and/or to the following normal.
Fourteen special absolute normals are encoded by the unused two settings within the three sextant bits. This is indicated by specifying the angle fields to have a length of zero (not present) and the first two bits of the sextant field to both have a value of 1. Table B-5 lists the 14 special normals
Special normals are always absolute normals; they cannot be delta'd to from a previous normal. Unlike ordinary absolute normals, delta normals have the additional restriction that they cannot be delta'd from. Thus, the next normal after any special normal must always be an absolute normal (ordinary or special). In some cases, this overhead can be avoided by never landing on a special normal, when this perturbation of the data does not negatively impact the visual appearance of the object.
The rest of the graphics pipeline and frame buffer following the geometry decompression stage may choose not to use all (up to) 16 bits of normal component information; in this case it is acceptable to truncate the trailing bits during decompression. What the compressed geometry format does require is that normal settings of any size up to 18-bit absolute normals be supported, even if all the decompressed bits are not used.
B.12.8 vertex Instruction
Assembly syntax: (vertex <rep> {push}
<position subinstruction>
{<normal subinstruction>}
{<color subinstruction>})
Assembly syntax: <rep>:
The vertex instruction has a two-bit opcode, a position subinstruction (always), a two-bit vertex replacement field, a mesh buffer push bit, and, optionally, a normal subinstruction and/or a color instruction, depending on the current setting of the state bundling bits. The two-bit vertex replacement field has the same triangle semantics as it does within the mbr instruction:
The mesh buffer push bit indicates whether this vertex should be pushed into the mesh buffer so as to be eligible for later rereference.
The Position, Normal, and Color subinstructions have the semantics documented in their individual sections.
B.12.9 setNormal Instruction
Assembly syntax: absolute: (setNormal <Tag> <Sextant> <Octant>
<
> <
>)
Assembly syntax: relative: (setNormal <Tag> <
> <
>)
Assembly syntax: absolute special: (setNormal <Tag> <Special>)
Assembly syntax: <Sextant>, <Octant>, <Special>: same as for normal subinstruction.
The setNormal instruction has a two-bit opcode and a Normal subinstruction.
The Normal subinstruction has the semantics documented in Section B.12.7, "Normal Subinstruction."
If a SetNormal instruction is present immediately before an mbr instruction, then the new normal value overrides the normal data present in the mesh buffer for that particular mesh buffer reference.
B.12.10 setColor Instruction
Assembly syntax: (setColor <Tag> <R> <G> <B> {<>})
The setColor instruction has a two-bit opcode, and a color subinstruction. The color subinstruction semantics are documented in Section B.12.6, "Color Subinstruction."
If a setColor instruction is present immediately before an mbr (meshBufferReference) instruction, then the new color value overrides the color data present in the mesh buffer for that particular mesh buffer reference.
B.13 Semantics of Compressed Geometry Instructions
The formal semantics of the compressed geometry format is best described by a state description of the decompression process. It must be emphasized that these state descriptions are given to show the formal semantics, not an efficient implementation.
The next few sections will present such a state description. While this description is intended to be a complete and unambiguous description of the compressed geometry format and decompression semantics, in practice studying both the compression process and the decompression process, and studying code examples for both, is a better approach for the human understanding process.
B.13.1 Header and Body to Variable-Length Instruction
Compressed geometry instructions have a minimum length of eight bits (six bits for subinstructions). This allows all geometry decompression instructions to be split into two physically separate bit sequences within the compressed stream. The first bit sequence is always of eight bits in length (six for subinstructions); the second bit sequence contains the remaining bits of the instruction (if any). Thus a logical stream of N compressed geometry instructions, where each instruction is split into two bit sequences Hi and Bi (i being from 0 to N - 1), is physically represented as
- H0 B-1 H1 B0 H2 B1 ... Hn-1 Bn-2 Hn Bn-1
Okay, so what is this "B-1"? All compressed geometry sequences have an implied (not physically present) H-1 of a nop opcode, thus B-1 is always present (starting at the eighth bit of the stream) as any valid variable-length nop body. (Just five zeros, the minimum-length nop, is a good default.) Thus the implied nop opcode "jump starts" the header-forwarded decompression process. This process is reversed at the end of the stream. Hn is a nop opcode, but no body is present, as Bn-1 is the last bits of the stream. (As will be described, Bn-1 must end on a 32-bit aligned boundary.)
This is viable because all compressed geometry streams are presented along with a total bit length of their contents, so no explicit end-of-stream marker is needed. Streams must be rounded up to the nearest full 64-bit word multiple by use of additional variable-length nop instructions of appropriate lengths (within the body of the stream, that is, their headers appear before Hn). This implies that Hn-1 is usually a nop instruction used to force alignment.
This "header-forwarding" shuffled representation is necessary for hardware decompressors to operate efficiently. While this is not an issue for purely software-based decompressor implementations, in order to have one canonical format for both hard and soft decompressors, all decompressors must operate only on the header-forwarded representation; this is the only "official" compression bit-format specified. For a software decompressor, the extra unshuffling adds only slightly to the overall overhead of decompression; for hardware, it is essential.
Thus the first stage in the decompression process is to put the two separate bit sequences for each instruction back together. The next paragraph describes the flavor of this process, going around the loop approximately one and one-half times. The actual process is more accurately described in state machine semantics.
First, the fixed-length eight- (or six-) bit header for the next full instruction (or subinstruction) to be processed is detached from the current head of the compressed stream. Next, the variable-length body bits for the previous instruction (or subinstruction) are detached from the compressed stream and combined with the already extracted header for the previous instruction; the previous instruction is complete and can be processed. Now the fixed-length header for the instruction after the next is detached from the bit stream and then finally the variable-length body for the next full instruction can be detached; the next instruction is now complete and can be processed.
// pseudocode for converting bitstream into sequences of
// instructions
decompress(stream) {
current_header <- nop
while (not_empty(stream)) {
next_header <- get_header_bits(stream)
current_body <- get_n_bits(stream,
body_length(previous_header))
process_instruction(current_header, current_body)
current_header <- next_header
}
}
One slight complexity: The get_header_bits() extracts only six bits of header for color or normal subinstructions of a vertex instruction. It extracts a full eight bits of header in all other cases.
B.13.2 Variable-Length Instruction to Instruction
The three decompression tables contain entries for each different numeric tag describing whether the value in the stream is absolute or relative, and length and shift constants describing how to convert the variable-length bit field back into a fixed-length value. The fixed-length value for position and color components is 16 bits in length (sign, unit, 14 fraction); the fields for normal angles are 7 bits (signed) and 3 each for sextant and octant (if present).
B.13.3 Delta Position to Position
absolute_position(x, y, z):
cur_x x, cur_y y, cur_z z
relative_position(x, y, z):
cur_x cur_x + x, cur_y cur_y + y, cur_z cur_z + z
B.13.4 Delta Color to Color
absolute_color(r, g, b {, }):
cur_r r, cur_g g, cur_b b, {cur_ }
relative_color(r, g, b {, }):
cur_r cur_r + r, cur_g cur_g + g, cur_b cur_b + b,
{cur_ cur_ + }
B.13.5 Encoded Delta Normal to Encoded Normal
State: cur_oct, cur_sex, cur_u, cur_v
absolute_normal(oct, sex, u, v):
cur_oct oct, cur_sex sex, cur_u u, cur_v v
relative_normal(u, v):
cur_u cur_u + u, cur_v cur_v + v,
if (cur_u < 0)
cur_u -cur_u, cur_sex flip_u[cur_sex]
else if (cur_v < 0)
cur_v -cur_v, cur_oct cur_oct <xor> flip_v[cur_sex]
else if (cur_u + cur_v > 64)
cur_u 64 - cur_u, cur_v 64 - cur_v,
cur_sex flip_uv[cur_sex]
flip_u[6] = { 4, 5, 3, 2, 0, 1 }
flip_v[6] = { 2, 4, 1, 1, 2, 4 }
flip_uv[6] = { 2, 3, 0, 1, 5, 4 }
B.13.6 Encoded Normal to Rectilinear Normal
nx norms[v,u].nx, ny norms[v,u].ny, nz norms[v,u].nz,
if (cur_sex & 4) t nx, nx nz, nz t
if (cur_sex & 2) t ny, ny nz, nz t
if (cur_sex & 1) t nx, nx ny, ny t
if (cur_oct & 1) nz -nz
if (cur_oct & 2) ny -ny
if (cur_oct & 4) nx -nx
The contents of the norms[] table is exactly specified, and the next revision of this specification will contain an exact listing of the values.
B.14 Semantics of Vertices
The formal semantics of the vertex processing is best described by a state description of the decompression process. Once again it must be emphasized that these state descriptions are given to show the formal semantics, not an efficient implementation.
B.14.1 Instruction to Vertex
This section describes the state change semantics caused by each instruction to generate the next output vertex, prior to assembly into triangles. The internal state consists of the three bundling bits, a current normal and current color, normal_override and color_override bits, the 16 mesh buffer vertices, and a current internal-cycling mesh buffer index.
normal(n):
current_normal n, normal_override 1
color(c):
current_color c, color_override 1
vertex(rep, mbp, p {, n} {, c}):
current_position p,
if (bnv) current_normal n,
if (bcv) current_color c,
output_vertex(rep, current_position, current_normal,
current_color)
if (push) mesh_buffer[mesh_index].position p
if (push && bnv) mesh_buffer[mesh_index].normal n
if (push && bcv) mesh_buffer[mesh_index].color c
if (push) mesh_index (mesh_index+1) & 15
normal_override 0, color_override 0
mesh buffer reference(rep, i):
current_position
mesh_buffer[(mesh_index - i - 1) & 15].position
if (bnv && !normal_override)
current_color mesh_buffer[(mesh_index - i - 1) & 15].color
if (bcv && !color_override)
current_color mesh_buffer[(mesh_index - i - 1) & 15].color
normal_override 0, color_override 0
output_vertex(rep, current_position, current_normal,
current_color)
set state(new_bnv, new_bcv, new_cap):
bnv new_bnv,
bcv new_bcv,
cap new_cap,
normal_override 0, color_override 0
set table(address, range, entry):
...
nop(length):
(null)
B.14.2 Vertex to Intermediate Triangle
This section describes the formal semantics of assembling vertices with replacement instructions into nearly finished triangles: the semantics of generalized triangle strips.
output_vertex(restart_reverse, newv):
newest newv, number_of_vertices 1, rev = 1
output_vertex(restart, newv):
newest newv, number_of_vertices 1, rev = 0
output_vertex(replace_middle, newv):
if (number_of_vertices < 2)
middle newest, newest newv, number_of_vertices++
else if (number_of_vertices < 3)
oldest middle, middle newest, newest newv,
number_of_vertices++,
intermediate_triangle(restart, oldest, middle, newest)
else if (number_of_vertices == 3)
middle newest, newest newv,
intermediate_triangle(restart, oldest, middle, newest)
output_vertex(replace_oldest, newv):
if (number_of_vertices < 2)
middle newest, newest newv, number_of_vertices++
else if (number_of_vertices < 3)
oldest middle, middle newest, newest newv,
number_of_vertices++,
intermediate_triangle(restart, oldest, middle, newest)
else if (number_of_vertices == 3)
oldest middle, middle newest, newest newv,
rev = 1 - rev,
intermediate_triangle(restart, oldest, middle, newest)
B.14.3 Intermediate Triangle to Final Triangle
The final stage is to take into account the current reverse bit. This bit controls the order in which the vertices are output to ensure they all face the correct way.
intermediate_triangle(rev, v1, v2, v3):
if (!rev)
final_triangle(v1.position, v1.normal, v1.color,
v2.position, v2.normal, v2.color,
v3.position, v3.normal, v3.color)
else if (rev)
final_triangle(v2.position, v2.normal, v2.color,
v1.position, v1.normal, v1.color,
v3.position, v3.normal, v3.color)
B.15 Outline of Geometry Process
Java 3D formally defines only the compressed geometry format and the decompression semantics. Authoring tools are free to employ whatever compressed geometry algorithms they choose, as long as the results adhere to the specifications described in the previous sections.
However, to further document the semantics of the compressed geometry format, an overview of one particular compressed geometry algorithm is given here.
B.15.1 Compressing Geometry Data
Group the geometry to be compressed into separate rigid objects. Typically such objects will be individually culled during rendering, so you should not join objects too extensively prior to compression. In optimized systems, the granularity of object splitting will be computed by an algorithm that takes culling optimization into account (both frustum and occlusion culling).
B.15.2 Convert to Generalized Mesh Format
Once a group of geometry has been identified, it is next converted into generalized mesh format. This is a complex step, and a number of topological analysis-based algorithms have been applied to it. Note that to reduce compression time, when space is a less important issue than time, a compressor might only stripify, not meshify. Alternatively, the triangles have to have come from somewhere, and that in many cases is a tessellator of higher order surfaces. Such a tessellator will implicitly know the mesh connectivity and may be able to generate the triangle data directly in the generalized mesh format.
The next step is the quantization of the geometry positions, colors, and/or normals. All these quantizations can be varied within the geometry, but for simplicity a single fixed quantization of each is assumed here.
B.15.3 Position
Normalize the position data.
The containing bounding box for the object is computed. This is the minimal box such that all geometry vertices are contained within it. The vertices are then all normalized to be contained within this bounding box by first subtracting the XYZ location of the bounding box center from the vertex XYZ and then dividing all the XYZ vertex values by the half length of the longest side of the bounding box. Thus all normalized positions will be within the ±1 unit cube. A constant matrix transform corresponding to an offset to the center of the bounding box and an inverse scale by the half length of the longest side of the bounding box are created as a prologue for the geometry data. Note that in practice a little more care must be taken. The greatest positive value is actually 
, when positions are quantized to n bits. By symmetry, the smallest negative value allowed is 
. The value -1 (only sign bit set, all other bits 0) is explicitly not allowed. Thus when computing the scale factor (and center) that will normalize the geometry, the actual representation range needs to be taken into account.
Quantize the position data.
Assuming that position data is to be quantized to n bits, each vertex position component should be multiplied by the value of 2n and then rounded down to the nearest integer. If rounded to the nearest integer, or rounded up, the value may overflow the representation. Once again the goal is to take numbers from a given floating point range and represent all of them within an n-bit fixed point range.
B.15.4 Normals
Normalize the normals.
Each normal should be normalized to unit length.
Quantize the XYZ components of the normal to 14 bits accuracy.
Each normal component should be multiplied by 214, rounded to the nearest integer, and then converted back to floating-point representation and divided by 214.
Fold the XYZ components of the normal to the positive (prime) octant.
If an XYZ component of the normal is negative, invert it and save the original sign bits as a three-bit octant value. It is important when compressing always to strip the sign bits off first before applying sextant folding and to reverse the process when decompressing. Note that the octant bits read left to right: the upper bit is for the x-axis, the middle for the y-axis, and the lowermost is for the z-axis.
oct = 0;
if(nx < 0.0) oct |= 4, nx = -nx
if(ny < 0.0) oct |= 2, ny = -ny
if(nz < 0.0) oct |= 1, nz = -nz
Fold the normal to the nX nZ nY sextant.
Check (in exactly the following order):
sex = 0;
if (nx < ny) t = nx, nx = ny, ny = t, sex |= 1
if (nz < ny) t = ny, ny = nz, nz = t, sex |= 2
if (nx < nz) t = nx, nx = nz, nz = t, sex |= 4
Match the nearest quantized normal representation.
Take the dot product of the normal with each of the quantized reference normals in the table for the specified number of quantized normal bits. That u,v normal index for the reference normal that gives the greatest (nearest unity) dot product result is the new quantized normal representation (along with the octant and sextant representation). (There are more efficient ways to compute the same results.) At this point there are no specific tie-breaking rules when two (or more) reference normals produce the same candidate dot product results. Technically this is purely a compressor internal issue.
Check for special normals.
The u,v normal index generated by the previous stage will generally be in the full 7-bit range of the normal grid space. In this space, the two classes of special normals occur when u = 64, v = 0, and when u = 0, v = 64. When this is detected, the sextant and octant bits must be examined to produce the proper special normal encoding:
if (u == 64 && v == 0) { /* Six coordinate axis case */
if (sex == 0 || sex == 2) /* +/- x-axis */
special = ((oct & 4)?0x2:0);
else if (sex == 3 || sex == 1) /* +/- y-axis */
special = 4 | ((oct & 2)?0x2:0);
else if (sex == 5 || sex == 4) /* +/- z-axis */
special = 0x8 | ((oct & 1)?0x2:0);
} else
if (u == 0 && v == 64) /* Eight mid point case */
special = (oct<<1) | 1;
B.15.5 Colors
To begin with, the colors are assumed to be in a 0.0 to 0.9 representation.
Quantize the color values.
Assuming that color data is to be quantized to n bits, each vertex color component (R, G, B, and optionally ) should be multiplied by the value of 2n and then rounded down to the nearest integer. Just as with positions, there is no true representation of positive unity.
B.15.6 Collect Delta Code Statistics
Make a pass in generalized mesh order through all vertices in the geometry. For each successive pair of vertices, compute the difference between their component values, compute the bit length of this (signed) difference, and histogram this bit length. Specifics for each component type are detailed in the following sections.
B.15.7 Position Delta Code Statistics
Compute X, Y, and Z. Determine which of these has the greatest magnitude. Compute the number of bits for this component, including one sign bit. This is the length to be histogrammed for positions.
B.15.8 Color Delta Code Statistics
Compute R, G, B, and (if present). Determine which of these has the greatest magnitude. Compute the number of bits for this component, including one sign bit. This is the length to be histogrammed for colors.
B.15.9 Normal Delta Code Statistics
For a given pair of normals, check to see if they have the same octant and sextant, and that neither is a special normal. If so, compute U and V. Determine which of these has the greatest magnitude. Compute the number of bits for this component, including one sign bit. This is the length to be histogrammed for this pair of normals.
If the normals have different sextants and/or octants, but neither is a special normal, check to see if their sextants share an edge. If so, the special normal wrapping rules from Section B.8.3, "Special Warping Rules for Delta Normals," can be applied. Depending on what type of edge they share, the delta including the change in edges is encoded in one of three ways: U + U < 0, V + V < 0, and U + U + V + V > 64. Each case is discussed in the following paragraphs. The sextant numbers are from the binary codes shown in Figure B-3.
Sextants 0 and 4, 1 and 5, and 2 and 3 share the U = 0 edge. When crossing this boundary, U becomes ~U - last_u. This will generate a negative cur_u value during decompression, which causes the decompressor to invert cur_u and look up the new sextant in a table.
Sextants 0 and 2, 1 and 3, and 4 and 5 share the U + V = 64 edge. U becomes 64 - U - last_u, and V becomes 64 - V - last_v. When cur_u + cur_v > 64, the decompressor sets cur_u = 64 - cur_u and cur_v = 64 - cur_v, and a table lookup determines the new sextant.
Each sextant shares the V = 0 edge with its corresponding sextant in another octant. When in sextants 1 or 5, the normal moves across the X-axis, across the Y-axis for sextants 0 or 4, and across the Z-axis for sextants 2 or 3. V becomes ~V - last_v. The decompressor inverts a negative cur_v and performs a table lookup for a mask to exclusive-OR with the current octant value.
Note: When using the normal wrapping rules, a subtle bug can be introduced due to the ambiguity of normals on a shared edge between two sextants. The normal encoding rules have unambiguous tie-breaking rules to determine which octant and sextant a given normal resides in. However, the wrapping rules assume by default that a delta'd normal is in the same sextant and octant as its predecessor if the delta landed only on an edge. This is subtly different than the sextant and octant that the encoding rules might have suggested. The proper procedure is to keep track of which octant and sextant a decompressor would believe that the normals being generated would lie in. When the normal to delta to lands on an edge of this region, change its sextant and octant from what the encoding rules suggest are the same as where it is now delta-ing from. This change in default encoding is permissible because the rectilinear normal encoded by values on a sextant edge is identical no, matter which sextant claims ownership.
Otherwise the normals cannot be delta encoded, and so the second (target) normal must be represented by an absolute reference to its three octant, three sextant, and 2 n-bit u, v addresses. This is the length to be histogrammed for this pair of normals.
Note: Slightly higher compression density can be achieved at a slight expense in representation accuracy by avoiding special normals when delta and wrapping differences are generating compact results. Instead of generating the special normal, a near-by nonspecial normal can be generated allowing for compact deltas. As with any compression technique that intentionally further modifies or distorts the input data, doing this normal perturbation must be a policy choice of the compressor itself and subject to quality constraints of the user.
B.15.10 Assign Huffman Tags
Encode data into variable-bit length compressed geometry instructions.
One can use an algorithm similar to the one used by the JPEG image compression standard. The main differences are how codes are reassigned when their lengths exceed the maximum code length, how the data bits are encoded in the compressed data stream, and also how they support additional attributes for codes (relative/absolute, how many bits of left shift).
The frequencies of the data lengths are used as leaf nodes in a binary tree. The algorithm used to generate the tree places the less-frequent codes deeper in the tree. After the tree is built, the traversal path to a leaf node becomes its Huffman code, and the depth in the tree becomes its code length.
Codes generated with a length greater than six, the maximum code length, must be shortened. These nodes are merged with more frequent nodes by increasing the number of sign bits included with the smaller data length.
B.15.11 Assemble the Pieces into a Bit Stream
Given the sequence of variable-bit-length compressed geometry instructions, shuffle the first eight (six) bits of each instruction ahead of its predecessor's body.
B.16 Compressed Geometry Assembly Syntax
This section describes the assembly syntax for both the input to an assembler for compressed geometry, and for the output of a disassembler of compressed geometry.
The concept of a verbose ASCII assembly syntax for a compressed binary format may seem like an oxymoron, but in fact a well-defined assembly format is an invaluable aid to debugging both compressors and decompressors. The ASCII assembly format is not meant to be a representation used for the transport of compressed geometry; rather, it is a debugging aid for those involved in programming compressors and decompressors and building hardware decompressors. The assembly format is also useful for generating and understanding test vectors. Both an assembler and a disassembler are available as stand-alone C programs as tools. For generating compressed geometry programmatically, a number of C- and Java-based low-level compression tools are also available. With the possible exception of test vectors, software-based compressors should use these direct binary output routines; having a compressor generate an intermediate ASCII file representation only then to be assembled into binary is needlessly inefficient. If there is a need to examine the output of a compressor in a human readable form, a binary compressed geometry file can always be disassembled into ASCII by the disassembler when needed.
Because compressed geometry is a tightly encoded binary format, to make dissembled output more understandable, it is appropriate to perform some partial decompression optionally before generating the text output. Thus the compressed geometry disassembler supports multiple levels of decompression during disassembly. On the other hand, the compressed geometry assembler is not a compressor and thus supports as input the only lowest level syntax. There are five layers of successively more decompressed disassembly, with each level printed using either decimal or hex numbers. The five layers and two numeric formats are expressed as ten different levels of disassembly (with every other level just indicating that hex output for integer fields):
1. Nearly raw. After a symbolic opcode, decimal (or optionally, hex) numbers are printed for the modified Huffman tag field and for all data fields without any additional interpretation, scaling, or un-delta-ing, except that proper signed/unsigned semantics are followed. The only processing is to parse the incoming bit stream into bit fields and to undo the effects of header forwarding. The modified Huffman tag is used only to determine the length of the tag field and the following data fields. The opcode has no trailing letter modifiers (as documented below); this indicates level 1.
2. Same as level 1, but printed using hex numbers (preceded with a 0x suffix).
3. Modified Huffman tag expanded. The properties of the modified Huffman tag are shown in line: the length of the tag, the length of the data fields, and the left normalization shift for the field. The absolute/relative bit value is shown by appending the letter `A' or `R' to the opcode (or `S' for absolute `special' normals).
4. Same as level 3, but printed using hex numbers (preceded with the 0x suffix).
5. Normalized. The left normalization shift is applied to the data fields, and the specific properties of the modified Huffman tag are no longer shown. To differentiate from level 2, the letter `N' is appended to the opcode name after the absolute/relative/special letter.
6. Same as level 5, but printed using hex numbers (preceded with the 0x suffix).
7. Un-delta'd. Like level 3, but relative values have had the running total added to them to show what the current full value is. Absolute values are unchanged from level 3. To differentiate from level 4, an `A' suffix is added to the lengthening opcode name.
8. Same as level 7, but printed using hex numbers (preceded with the 0x suffix).
9. Floating point. While up to now all values have been subsets of 16-bit integers, before conversion to integer and quantization, most values were floating-point numbers in the 0 to 1.0 or -1.0 to 1.0 range. Level 5 shows the values as floating-point numbers, but it must be cautioned that these data fields, while similar to the input uncompressed unquantized values, will usually be slightly different in value than the original data. This floating-point output format is primarily included as a convenience when a user wants to understand the data closer to the original space.
10. Same as level 9, but non-floating-point numbers are printed using hex numbers (preceded with the 0x suffix).
Once again while the dissembler supports all 10 levels of output options, the assembler supports only levels 1 and 2.
The syntax is fairly simple. Because the setting Colors or Normals can be either standalone instructions or components of a vertex instruction, parenthetic instruction grouping (lisp style) is used to make the ownership of arguments clear.
As an example, following is the disassembly (print level 1) of a four-sided pyramid:
(nop 0)
(setTable Position 32-47 2 4 Rel)
(setTable Position 56-63 3 4 Rel)
(setTable Position 0-31 12 4 Rel)
(setTable Position 48-55 12 4 Abs)
(setTable Normal 0-31 5 0 Rel)
(setTable Normal 32-63 6 0 Abs)
(setTable Color 32-63 2 8 Rel)
(setTable Color 0-31 8 8 Abs)
(setState normalsBundled colorsUnbundled alphaUnbundled)
(setState normalsBundled colorsUnbundled alphaUnbundled)
(setColor 0 127 51 12)
(setState normalsBundled colorsUnbundled alphaUnbundled)
(setColor 32 0 0 0)
(vertex RST (Position 48 -2047 -2047 -205)
(Normal 32 4 --+ 44 0))
(vertex RMID (Position 0 2047 -2 0)
(Normal 32 5 +++ 44 0))
(vertex ROLD (Position 0 0 -2047 409)
(Normal 0 14 0))
(vertex ROLD (Position 0 2047 -2047 -409)
(Normal 32 4 +-+ 44 0))
(vertex ROLD (Position 56 2 0 0)
(Normal 32 4 --+ 44 0))
(vertex RST (Position 0 2047 -2 0)
(Normal 32 00-))
(vertex RMID (Position 0 -2047 2 0)
(Normal 32 00-))
(vertex ROLD (Position 32 -2 0 0)
(Normal 32 00-))
(nop 19)
(nop 29)
B.17 Compressed Geometry Instruction Verifier
This section describes the rules for determining if a given binary sequence is a valid compressed geometry block. These rules have been programmatically implemented in a compressed geometry verifier, a stand-alone C program that can validate a given file containing a Compressed Geometry object. The verifier is also available in a utility package in both C and Java for use within larger systems.
In theory, every producer of compressed geometry should run such a verifier on its output as a final check, and every consumer of compressed geometry should run such a verifier on any input as an initial check. In practice, for well-debugged programs and hardware implementations with error detection, a separate verification pass may not always be necessary, but it should always be available as an option. (It is also important to note that just passing the verifier is not sufficient to indicate that a compressed geometry compressor is functioning properly; the output must also be examined visually for other types of error.)
When the stand-alone verifier finds a violation, an appropriate error message is printed out. This is quite useful when debugging compressors. The implementation of the verifier is effectively an augmented decompressor, in which the uninitialized state is kept track of and additional error checking is applied.
For a Compressed Geometry object to be valid, it must adhere to at least the following rules, along with the restrictions described in the rest of this document:
Rule 1: Size, Alignment and Byte Order
- Every compressed geometry is a sequence of binary data a multiple of four 8-bit bytes in size, starting on an aligned 32-bit boundary, represented in network byte order.
Rule 2: Beginnings
- Every compressed geometry sequence starts with the body field of a nop instruction. Initial process proceeds as if a forwarded header of a nop instruction had just been seen. The length field of this nop instruction body can be of any legal length, though usually by convention the length field is 0; thus the first body consists of five zeros.
Rule 3: Endings
- The last header in a compressed geometry sequence is a nop. This is followed by the body of the next-to-last instruction. This preceding instruction can be any instruction, and its body can be of any valid length for that instruction type, but the body must end on a four byte 32-bit word aligned boundary. To achieve this, usually the next-to-last and possibly the next-to-next-to-last instruction(s) are also nops, with lengths chosen to satisfy the ending requirement. Note that the body for the last instruction (the nop) is not present in the compressed geometry sequence. The end of the compressed geometry is determined from a separately specified size outside of the compressed geometry proper. Note that this ending convention is symmetrical with the starting convention; the sequential concatenation of two valid Compressed Geometry objects is also a valid Compressed Geometry object. For hardware, after a valid Compressed Geometry object has been executed, another valid compressed geometry can be executed without any pipeline flushes if desired.
Rule 4: Reserved Bits
- Any bits or bit fields described as reserved in a compressed geometry instruction must be filled with zeros.
Rule 5: Valid Opcodes
- Only the seven defined instruction opcodes may be present in a valid Compressed Geometry object.
Rule 6: No Defaults
- All state used in the processing of compressed geometry must be defined before it is used; there are no implicit defaults for any of the state. The state includes the contents of the decompression tables as defined by the setTable instruction; the three bundling bits as defined by the setState instruction; the contents of the mesh buffer as defined by vertex instructions with push enabled; and the current position, normal, and color (and alpha), as defined by absolute settings in vertex instructions, setNormal instructions, and setColor instructions. Note that this does not mean that all possible state needs to be defined within a Compressed Geometry object. For example, only those portions of the decompression tables actually referenced by a vertex or setNormal or setColor instruction need be initialized first. The bits specified by setState always need to be referenced, unless there are no vertex instructions, which would occur only in a geometry-less Compressed Geometry object. Mesh buffer elements need only be defined if they are accessed by mesh buffer reference instructions. The current normal and the current color (and alpha) are special cases; if they are not used within a Compressed Geometry object, they may not need to be initialized, depending on the semantics of the outer incorporating graphics API.
- Specifically in a valid compressed geometry sequence, no relative values for positions, normals, colors (or alpha) may appear in a vertex or setNormal or setColor instruction until after an absolute value has appeared for that particular item. There is no inheritance between different Compressed Geometry objects, each must be entirely standalone when it comes to state.
Rule 7: State Changes Immediately
- State changed by setState and setTable instructions is in force and available as of next instruction. (This specifically disallows pipelined hardware implementations from changing the semantics to force user-visible delay slots.)
Rule 8: Valid XYZ Positions
- Executing the position field of a vertex instruction will always result in a signed 16-bit fixed-point value for the current x, y, and z position state. All possible bit values are valid for these fields.
Rule 9: Valid Sextant Octant u v Normals
- Executing a setNormal instruction, or executing (when present) the normal subinstruction of a vertex instruction, will result in updated sextant, octant, u and v fields. The wrapping semantics described earlier define the subset of valid values and delta operations allowed for these fields. If these fields are valid, then a valid conversion back to a rectilinear Nx, Ny, Nz value is defined.
Rule 10: Valid RGB{} Color
- Executing a setColor instruction, or executing (when present) the color subinstruction of a vertex instruction, will always result in a signed 16-bit fixed point value for the current R, G, B (and sometimes ) color state. Only positive values are valid for these fields.
Rule 11: What Is Outside the Scope of These Rules
- The results of executing a sequence of compressed geometry instructions in a valid Compressed Geometry object is a sequence of specific vertex values and connectivity information for triangles (or lines or points). What further processing this output stream is subject to, and the semantics of this processing is outside the scope of the specification of compressed geometry. For example, the semantics of transformation, lighting, and shading are not specified by compressed geometry. Note that even the semantic interpretation of what type of color parameter the "color" values generated by compressed geometry is left undefined by the Compressed Geometry specification; this is up to the lighting equation (or for realistic rendering systems, more generally the programmable shader) of the outer incorporating graphics API. Specifically no implication is made as to whether the "color" value is an ambient color, a diffuse color, a specular color, an emissive color, some combination thereof, or a more generalized value used by a programmable shader. This, of course, also applies to any interpretation of the value, which may or may not be an opacity value.
As described earlier, for a Compressed Geometry object to be valid, it must follow these rules plus adhere to the other constraints on individual compressed geometry instructions described in the rest of this document.
B
