Contents Previous Next

Java 3D API Specification


3D Geometry Compression

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 only use 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 only use the features explicitly specified in this document. Any features, fields, usage, etc. 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 case the data to be invalid.

B.1 Compression

First, 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.

Next 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.

These quantized bits are differenced between successive vertices, and the results are modified Huffman encoded into self-describing variable-bit-length data elements.

Finally, these variable-length elements are strung together using Java 3D's seven geometry instructions into a final compressed geometry block.

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 above 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 "star" triangle strip. 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 the incoming vertex becomes the newest. This corresponds to a triangle star or 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 "star" 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 clockwise vertex order after transformation (assuming a right-handed coordinate system). To support this, there are two flavors of restart: restart_clockwise and restart_counterclockwise. The vertex order is reversed after every replace_oldest, but remains the same after every replace_middle.

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 very 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.

The language of compressed geometry supports the four vertex replacement codes of generalized triangle strips (replace oldest, replace middle, restart clockwise, and restart counterclockwise), and adds another bit in each vertex header to indicate if this vertex should be pushed into the mesh buffer or not. The mesh buffer reference instruction has a four-bit field to indicate which old vertex should be re-referenced, along with the two-bit vertex replacement code. Mesh buffer reference instructions do not contain a mesh buffer push bit; old vertices can only be recycled once.

Geometry rarely is composed purely of positional data; generally a normal and/or color are also specified per vertex. Therefore, mesh buffer entries contain storage for all associated per-vertex information (specifically including normal and color).

For maximum space efficiency, when a vertex is specified in the data stream, (per-vertex) 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 textures.

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, multiple 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 compactly represent the vertices. 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 postponed until later, where they can be discussed in the context of color and normal delta coding as well.

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 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 is used for color components as 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 perfectly 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 spreading out angles 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 about 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 only interested 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 greatly reduce the size of the table (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 only need 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 up 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 above could be used for the decompression look-up table. However, several additional constraints mandate a different choice of encoding:

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, and 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:

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

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 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.

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 sub-instruction 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.

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 only defined 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.

Table B-1 Sextant Neighbors
Sextant Left Neighbor Diagonal Neighbor Bottom Neighbor
sextant 000 sextant 100 sextant 010 flip octant y
sextant 001 sextant 101 sextant 011 flip octant x
sextant 010 sextant 011 sextant 000 flip octant z
sextant 011 sextant 010 sextant 001 flip octant z
sextant 100 sextant 000 sextant 101 flip octant y
sextant 101 sextant 001 sextant 100 flip octant x

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, and 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 are:

if + 0 , + 0, + + + 2n :

new + , new + ,

current sextant and octant unchanged.

if + < 0 , + 0, -( + ) + + 2n :

new -( + ), new + ,

current sextant updated from left edge rules in Table B-1, current octant unchanged.

if + 0 , + 0, + + + \> 2n :

new 2n - ( + ) , new 2n - ( + ) ,

current sextant updated from diagonal edge rules in Table B-1, current octant unchanged.

if + 0 , + < 0, + - ( + ) 2n :

new + , new -( + ) ,

current sextant unchanged, current octant 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 are generated that allow these symbols to be represented with a near-minimum total number of bits, 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.

Both absolute 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 will be seen in a later section, all instructions are broken up into an eight-bit header and a variable-length body. Sufficient information is present in the header to determine the length of the body. 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 sub-fields 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. This section 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.

The primary instruction is vertex. A vertex instruction always specifies a 3D position, two generalized triangle strip replacement bits (rep), and a mesh buffer push (mbp) bit, and 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.

The setState instruction updates the value of the three state bits. Two of these bits are the normal and color bundling bits; the other one will be described later.

mbr (meshBufferReference)
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.

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.

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 is required at the end of a compressed geometry block.

B.11 Bit Layout of Compressed Geometry Instructions

Figure B-6 shows the bit-level layout of the eight geometry decompression instructions. Each instruction has a unique opcode, and then some (possible variable) number of arguments. 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 delimits the size of the argument.

B.12 Compressed Geometry Instruction Bit Details

The following subsections describe the bit details of the compressed geometry instructions, and much of their associated semantics. Along with each instruction, its assembly (and disassembly) syntax is described.

B.12.1 nop

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

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 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 unbundled tag present for the same value in the same setState instruction.

B.12.3 setTable

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 two-bit table specifies for which of the three decompression tables this update is targeted:

00 Position
01 Color
10 Normal
11 Unused-reserved for future use

The seven-bit address/range field specifies which entries in the specified table are to be set to the values in the following fields.

Address/Range Semantics Implicit Tag
1a5a4a3a2a1a0 set table entry a5a4a3a2a1a0 6
01a5a4a3a2a1 set table entry a5a4a3a2a10 through a5a4a3a2a11 5
001a5a4a3a2 set table entry a5a4a3a200 through a5a4a3a211 4
0001a5a4a3 set table entry a5a4a3000 through a5a4a3111 3
00001a5a4 set table entry a5a40000 through a5a41111 2
000001a5 set table entry a500000 through a511111 1
0000001 set table entry 000000 through 111111 0

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 as 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. Note that for normals, absolute references will have an additional six leading bits describing the absolute octant and sextant.

B.12.4 mbr (meshBufferReference)

Assembly syntax: (mbr <rep> <index>)

Assembly syntax: <rep>:

RCW Restart clockwise
RCCW Restart counterclockwise
RMID Replace middle
ROLD Replace oldest

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:

0 0 Restart clockwise
0 1 Restart counterclockwise
1 0 Replace middle
1 1 Replace oldest

There is no mesh buffer re-push 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 original 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. A mbr instruction only access 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 a 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 is 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 a 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 Sub-instruction

Assembly syntax: (Position <Tag> <X> <Y> <Z>)

The position sub-instruction can only appear within a compressed geometry vertex instruction, and always as the first sub-instruction. 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 sub-instruction 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 only contain the tag, or the tag and some of the X field bits, or any subset up to the entire sub-instruction, if short enough. However, it is possible for the entire sub-instruction 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 gets forwarded ahead. 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 bits used for the entire sub-instruction is at least six. (Note that the expanded fields must be correctly described in the decompression table entry for the tag. On cannot simply add padding within a position sub-instruction to a field the 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 Sub-instruction

Assembly syntax: (Color <Tag> <R> <G> <B> {<>})

The color sub-instruction can appear within either a compressed geometry vertex instruction or 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 sub-instruction 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 sub-instruction 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 only contain the tag, or the tag and some of the R field bits, or any subset up to the entire sub-instruction, if short enough. However, it is possible for the entire sub-instruction 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 gets forwarded ahead. 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 bits used for the entire sub-instruction 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 Sub-instruction

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,6 (as specified in Figure B-3)

Assembly syntax: Table B-2 below shows the assembly format for specifying octants in the <octant> field of Normal sub-instructions (as well as setNormal instructions).

Table B-2 Syntax for Specifying Octants
Syntax Octant
+++ +X +Y +Z
++- +X +Y -Z
+-+ +X -Y +Z
+-- +X -Y -Z
-++ -X +Y +Z
-+- -X +Y -Z
--+ -X -Y +Z
--- -X -Y -Z

Assembly syntax: Table B-3 below shows the assembly syntax for specifying the special normals in the "Special" field of Normal sub-instructions (as well as setNormal instructions).

Table B-3 Syntax for Specifying Special Normals
Syntax Special NX NY NZ Comment
+00 0000 1.0 0.0 0.0 +X axis
-00 0010 -1.0 0.0 0.0 -X axis
0+0 0100 0.0 1.0 0.0 +Y axis
0-0 0110 0.0 -1.0 0.0 -Y axis
00+ 1000 0.0 0.0 1.0 +Z axis
00- 1010 0.0 0.0 -1.0 -Z axis
+++ 0001 +X +Y +Z
++- 0011 +X +Y -Z
+-+ 0101 +X -Y +Z
+-- 0111 +X -Y -Z
-++ 1001 -X +Y +Z
-+- 1011 -X +Y -Z
--+ 1101 -X -Y +Z
--- 1111 -X -Y -Z

The Normal sub-instruction can appear within either a compressed geometry vertex instruction or 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 sub-instruction 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 only contain the tag, or the tag and some of the other field bits, or any subset up to the entire sub-instruction, if short enough. However, in the case of relative normals, it is possible for the entire sub-instruction 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 gets forwarded ahead. 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 bits used for the entire sub-instruction is at least six.

A Normal sub-instruction 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 sub-instructions, the number of fields of a Normal instruction differ between the absolute and relative types.

When the sub-instruction 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 sub-instruction 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 range of valid angular coordinates within a sextant fills only half the square, plus the diagional. Formally, after shift normilization, 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 eaisest 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-4 lists the 14 special normals

Table B-4 The 14 Special Normals
Special NX NY NZ Comment
0000 1.0 0.0 0.0 +X axis
0010 -1.0 0.0 0.0 -X axis
0100 0.0 1.0 0.0 +Y axis
0110 0.0 -1.0 0.0 -Y axis
1000 0.0 0.0 1.0 +Z axis
1010 0.0 0.0 -1.0 -Z axis
0001 +X +Y +Z
0011 +X +Y -Z
0101 +X -Y +Z
0111 +X -Y -Z
1001 -X +Y +Z
1011 -X +Y -Z
1101 -X -Y +Z
1111 -X -Y -Z

Special normals are always absolute normals; they cannot be deltated to from a previous normal. Unlike ordinary absolute normals, delta normals have the additional restriction that they cannot be deltaed 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 avoiding ever landing on a special normal, when this purtibation of the data is does not negitively impact the visual apperance 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

Assembly syntax: (vertex <rep> {push}
<position sub-instruction>
{<normal sub-instruction>}
{<color sub-instruction>})

Assembly syntax: <rep>:

RCW Restart clockwise
RCCW Restart counterclockwise
RMID Replace middle
ROLD Replace oldest

The vertex instruction has a two-bit opcode, a position sub-instruction (always), a two-bit vertex replacement field, a mesh buffer push bit, and, optionally, a normal sub-instruction 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:

0 0 Restart clockwise
0 1 Restart counterclockwise
1 0 Replace middle
1 1 Replace oldest

The mesh buffer push bit indicates whether this vertex should be pushed into the mesh buffer so as to be eligible for later re-reference.

The Position, Normal, and Color sub-instructions have the semantics documented in their individual sections.

B.12.9 setNormal

Assembly syntax: absolute: (setNormal <Tag> <Sextant> <Octant>
> <>)

Assembly syntax: relative: (setNormal <Tag> <> <>)

Assembly syntax: special: (setNormal <Tag> <Special>)

Assembly syntax: <Sextant>, <Octant>, <Special>: same as for normal sub-instruction.

The setNormal instruction has a two-bit opcode, and a Normal sub-instruction.

The Normal sub-instruction has the semantics documented in Section B.12.7, "Normal Sub-instruction."

If a SetNormal instruction is present immediately before a 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

Assembly syntax: (setColor <Tag> <R> <G> <B> {<>})

The setColor instruction has a two-bit opcode, and a color sub-instruction. The color sub-instruction semantics are documented in Section B.12.6, "Color Sub-instruction."

If a setColor instruction is present immediately before a 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 sub-instructions). 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 sub-instructions), 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

OK, 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 below, 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 nop instructions of appropriate lengths (within the body of the stream, that is, their headers appear before Hn).

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 sub-instruction) to be processed is detached from the current head of the compressed stream. Next, the variable-length body bits for the previous instruction (or sub-instruction) are detached from the compressed stream and combined with the already extracted header for the previous instruction; the previous instruction is now 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) {
    previous_header <- nop
    while (not_empty(stream)) {
        current_header <- get_8_bits(stream)
        previous_body <- get_n_bits(stream,
        process_instruction(previous_header, previous_body)
        previous_header <- current_header

One slight complexity: the get_8_bits() only extracts six bits of header for color or normal sub-instructions 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.

current_normal  n, normal_override  1
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 (mbp) mesh_buffer[mesh_index].position p if (mbp && bnv) mesh_buffer[mesh_index].normal n if (mbp && bcv) mesh_buffer[mesh_index].color c if (mbp) mesh_index (mesh_index+1) & 15
normal_override  0, color_override  0

mesh buffer reference(rep, i):

            mesh_buffer[(mesh_index - i - 1) & 15].position
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,

set state(new_bnv, new_bcv, new_cap):

bnv new_bnv,
bcv  new_bcv,
cap  new_cap,

set table(address, range, entry):

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 clockwise, newv):
newest  newv, number_of_vertices  1, ccw = 0
output_vertex(restart counterclockwise, newv):
newest  newv, number_of_vertices  1, ccw = 1
output_vertex(replace_middle, newv):

if (number_of_vertices < 2)
    midlest  newest, newest  newv, number_of_vertices++
else if (number_of_vertices < 3)
    oldest  midlest, midlest  newest, newest  newv,
    intermediate_triangle(ccw, oldest, midlest, newest)
else if (number_of_vertices == 3)
    midlest  newest, newest  newv,
    intermediate_triangle(ccw, oldest, midlest, newest)

output_vertex(replace_oldest, newv):

if (number_of_vertices < 2)
    midlest  newest, newest  newv, number_of_vertices++
else if (number_of_vertices < 3)
    oldest  midlest, midlest  newest, newest  newv,
    intermediate_triangle(ccw, oldest, midlest, newest)
else if (number_of_vertices == 3)
    oldest  midlest, midlest  newest, newest  newv,
    ccw = 1 - ccw,
    intermediate_triangle(ccw, oldest, midlest, newest)

B.14.3 Intermediate Triangle to Final Triangle

The final stage is to take into account the current counterclockwise bit; thus, the final triangles can always be assumed to be front facing when their vertices appear in counterclockwise order.

intermediate_triangle(ccw, v1, v2, v3):

if (ccw)
    final_triangle(v1.position, v1.normal, v1.color,
                     v2.position, v2.normal, v2.color,
                     v3.position, v3.normal, v3.color)
else if (!ccw)
    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 only formally defines 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.

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; Compressed Geometry can always represent -1, but the greatest positive value is actually , when positions are quantized to n bits. 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 to always 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 of the three 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 UV 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 was to compute this 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

The colors are assumed to be in a 0.0 to 0.9 representation to begin with.

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 next 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 paragraphs below. 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-ed normal is in the same sextant and octant as its predecessor if the delta only landed 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, and when the normal to delta to lands on an edge of this region, change its sextant and octant from the what the encoding rules suggested to be 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 are 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 non-special normal can be generated allowing for compact deltas. As with any compression technique that intentionally further modifies / 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 and how the data bits are encoded in the compressed data stream.

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 a representation ever 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 to then be assembled into binary is needlessly inefficient. If these 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 optionally perform some partial decompression 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 only supports as input the lowest level syntax. There are five layers 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):

Once again while the dissembler supports all 10 levels of output options, the assembler only supports levels 1 and 2.

The syntax is fairly simple. Because the setting Colors or Normals can either be stand-alone instructions, or components of a vertex instruction, parenthetic instruction grouping (lisp style) are used to make the ownership of arguments clear.

As an example, below 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 RCCW (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 RCCW (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 sections describes the rules for determining if a given binary sequence is a valid Compressed Geometry block or not. 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 a 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 the 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, and 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 un-initialized 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 and Alignment and Indianian-ness
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, and 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 next to last 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 possible 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 that 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 include 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 only occur 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 stand-alone when it comes to state.

Rule 7: State Changes Immediate
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 sixteen 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 sub-instruction 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 values is defined.

Rule 10: Valid RGB{} Color
Executing a setColor instruction, or executing (when present) the color sub-instruction of a vertex instruction will always result in a signed sixteen 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 if 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 a opacity value.

As described above, for a Compressed Geometry object to be valid, it must follow these rules plus adhere to the other constraints describing individual Compressed Geometry instructions described in the rest of this document.

Contents Previous Next

Java 3D API Specification

1 Deering, Michael. "Geometry Compression." Computer Graphics Proceedings, Annual Conference Series, 1995, ACM SIGGRAPH, pp 13-19.
Copyright © 1999, Sun Microsystems, Inc. All rights reserved.