The ZigZag Encoder?

[ProjectBarks]

So I was recently trying implement Vector3DTileContent into one of my applications when it came to my attention cesium uses ZigZag Encoding.

What is Zig Zag Encoding?

ZigZag encoding has two basic principles. Mapping signed integers to unsigned integers, and then packing that integer into a variable amount of bits. The motivation behind removing the sign is reducing computational overhead and other complications. For instance, with a fixed length integer you can use two's complement but it becomes impossible to tell the difference between a large positive number and small negative number. ZigZag encoding becomes valuable with the introduction of varints as are 7 bits per byte and 0 is used to mark the beginning of a new integer. For example, a line may exist in 3D space at 439295, 329495, 294959 but the next position is only 30m away, and the one after that is only 70m away. By using varints each number is not stored in a 32 bit integer but rather only the space they require.

Source and Example

So I found a really good example about how the encoding should work here

void to_zigzag(int64 n, unsigned char* buf)
{
    uint64 z = (n << 1) ^ (n >> (BIT_WIDTH - 1)); // where the actual "zig-zag" occurs
    while (z > 127)
    {
        *buf++ = (z & 0x7F) | 0x80;
        z >>= 7;
    }
    *buf = z;
}

int64 from_zigzag(unsigned char* buf)
{
    uint64 z = 0;
    int shift = 0;
    while (*buf & x80)
    {
        z |= static_cast<uint64>(*buf++ & 0x7F) << shift;
        shift += 7;
    }
    z |= *buf << shift;
    return (z & 1) ? (z >> 1) ^ -1 : (z >> 1);
}

Cesium's implementation and source

I haven't done a complete investigation about how often zigzag encoding is used. But it is implemented in AttributeCompression and used in CesiumTerrainProvider and a bunch of places in Vector3DTiles. It is also improperly described in cesium's implementation details of quantized-mesh

Whats wrong?

So from my understanding it appears that cesium is only doing 1/2 of the zig-zag encoding. The values are being properly switched between signed and unsigned integer; however, there never appears to be any byte packing. This means that there is a bunch of computation to switch values but there is actually no value add to doing this. I want to note I could be wrong and be missing something completely obvious but I just thought it might be something good to bring up. Here is a good javascript implementation if we wanted a more effective zigzag encoding.

[kring]

Hi @ProjectBarks,

I would argue that "zig-zag encoding" only covers the process of mapping signed to unsigned integers in such a way that small positive and negative values are both encoded as small integers. From some of your links, it looks like Protocol Buffers have a thing they call zig-zag encoding which also represents smaller numbers with fewer bits, but I would describe that as a separate technique from zig-zag encoding. In quantized-mesh and 3D Tiles, we use GZIP to encode smaller values with fewer bits rather than a custom algorith. Zig-zag encoding makes GZIP better able to do its job, so it's far from useless.

[ProjectBarks]

@kring So I hear what you are saying but I would argue you are not really benefiting from the zig-zag component of the encoder. What cesium encodes is the delta between the currently element and the previous element. Which in turn reduces the amount of bits used, assuming that distance between the points is somewhat constant, ie: 10, 20, 30, 40, 50. Since gzip is a slightly modified version of the DEFLATE algorithm it thrives when there is a repetition of bits.

Lets consider the example of 10, 20, 30, 40, 50. With the delta we get:

Base	10	20	30	40	50
Binary Raw	00001010	00010100	00011110	00101000	00110010
Binary of Delta	00001010	00001010	00001010	00001010	00001010

With the delta alone we get the same savings, with less computational overhead. I made a quick script to test my theory. (Afterwards I ran gzip -9 *) The legend is number of elements in the array. As you can see there is savings when using some form of delta but little gain of zigzag. From my results zigzag preformed better but I would say that is within margin of error.

[kring]

You may very well be right! Our approach to mesh compression was heavily influenced by the approach used for Google Body and described in Chapter 30 of OpenGL Insights (https://books.google.com.au/books?id=0bTMBQAAQBAJ&pg=PA446&lpg=PA446&dq=google+body+zig+zag+encoding&source=bl&ots=byAw0TZeQB&sig=vJ2ku0R8AtDwbEoi-4vVO0bk774&hl=en&sa=X&ved=2ahUKEwi0z777nL_cAhUCjLwKHZmsAycQ6AEwCXoECAQQAQ#v=onepage&q=google%20body%20zig%20zag%20encoding&f=false). But in Google Body, the data was UTF8 encoded rather than gzipped. With UTF8 encoding, it's more obviously important to end up with small integers because those can be encoded in a single byte in UTF8.

I don't think I'm concerned about the computational overhead of the zig-zag encoding; the cost should be dwarfed by the cost of accessing the attributes in memory in the first place anyway. And your results do show a small benefit.

But it would be interesting to see how much we would benefit from the Protocol Buffer-like variable-length encoding prior to - or instead of - GZIP. If you're up for it, you could grab a few terrain tiles from Cesium World Terrain in a mountainous area and recompress them.

Thanks for raising the issue!

[ProjectBarks]

@kring I agree with your assessment, although I would note that having the current zig-zag encoding only adds un-needed ambiguity to the data which in turn is harder to debug for someone interested in implementing the format.

I will take a look into adding variable length encoding to some of the formats and the added benefits of this encoding type.

[haxtibal]

Would it be possible to add a short statement to the quantized-mesh-1.0 spec, explaining the reasoning for using zigzag encoding without VLQ? Something like "gives (very) minor size reduction when gzipping". I'd agree with @ProjectBarks, and it kept me searching quite some time because of that bad "I must be missing something" feeling.

[carrino]

I agree with @haxtibal, put it in the spec. I spent about 2 hours before finding this thread trying to figure out why it's doing the zigzag, but the underlying data size is always 16 bits.