The ZigZag Encoder?
- Dominant language
- JavaScript
- Stars
- 15.7k
- Forks
- 3.9k
- Avg merge
- 4d 6h
- Merged PRs (30d)
- 34
Description
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](http://neurocline.github.io/dev/2015/09/17/zig-zag-encoding.html)
```c
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(*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](https://github.com/AnalyticalGraphicsInc/cesium/blob/master/Source/Core/AttributeCompression.js#L353) and used in [CesiumTerrainProvider](https://github.com/AnalyticalGraphicsInc/cesium/blob/master/Source/Core/CesiumTerrainProvider.js#L457) and a bunch of places in `Vector3DTiles`. It is also improperly described in cesium's implementation details of [quantized-mesh](https://github.com/AnalyticalGraphicsInc/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](https://github.com/chrisdickinson/varint) is a good javascript implementation if we wanted a more effective zigzag encoding.
Contributor guide
Research direction
Start with AttributeCompression.js and CesiumTerrainProvider.js, then inspect the Vector3DTiles uses and the quantized-mesh implementation details linked in the issue. Compare Cesium's signed-to-unsigned conversion with the referenced varint example and determine whether byte packing is expected; done should clarify the behavior and identify any required implementation or documentation change.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- javascript
- Domain
- computer-graphics
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100