FractalFir / tmf

Tight Model format is an experimental lossy 3D model format focused on reducing file size as much as posible without decreasing visual quality of the viewed model or read speeds.
MIT License
100 stars 6 forks source link

Delta encoding [FEATURE] #15

Closed FractalFir closed 1 year ago

FractalFir commented 1 year ago

Currently, indices are by far the biggest (size-wise) parts of the final file(60%). While previously attempted remedies(e.g. splitting index arrays to allow lower indices to be saved with fewer bits) to help, the issue still persists. Potential good solution would be delta encoding, modified to better fit this particular use case.

A potential approach could look something like that:

  1. Delta-encoding gets assigned a compression-type (marked in the segment header).
  2. A delta encoded segment will start with the following: 2.a. A field describing the amount of elements in a segment(u64). 2.b. Raw data precision bits(u8). 2.c. Delta precision bits(u8) 2.d. Delta min/max (UBA field, size of Raw data precision bits bits). IMPORTANT: preceded by sign!
  3. After that, a continus array of indices, encoded as follows: 3.a DeltaOrRaw (u1) - marks if next item is delta encoded(0) or raw(1) 3.b.0 If delta, a Delta precision bits long number will be encoded, containing a number between Delta min and Delta max. This number should be added to the value of the last number. 3.b.1 If Raw, a Raw data precision bits long number, encoding the value of the index.

This compression type will be selected during encoding, if it is beneficial and TMFPrecisonInfo field allow_delta_encoing is not set to false.

Possible issues:

  1. This relies on neighbouring indices being mostly very similar, which is the case for most meshes (not all!).
  2. May increase decode time. How much? At worst, I expect it to be ~2x slower than normal encoding. There is a slim chance it will be faster. But it is planned to be opt-out during encode, so eventual performance issues should not be a problem.
FractalFir commented 1 year ago

Improvements provided by delta encoding are not significant enough.