Data compression of a (3D) shape, e.g. of TriMesh or a chemical molecule

[Jarek]

I wanted to propose a general thread about compression of shapes, especially in 3D, for example:

- triangle mesh (TriMesh) of 3D object - the current standards are extremely wasteful - how to design optimized dedicated compressors?

For example we could parametrize the 'triangle strip' like below - we need ~ 1 bit/trangle to encode the tree structure, 1 real value/triangle (e.g. length of edge on the left).
Then the decoder should do the bending:


discussion: https://github.com/google/brotli/issues/165

- lossy compression of shape of a chemical molecule, especially such that similar shapes get similar descriptors for the virtual screening stage of search for new drugs.

For example approximation below (surface) is described by 8 real values: length, strength of bending, and 6 coefficients describing evolution of ellipse in cross-section (single ellipse requires 3 coefficients):


preprint: http://arxiv.org/pdf/1509.09211
slides: https://dl.dropboxusercontent.com/u/.../shape_sem.pdf
Mathematica implementation: https://dl.dropboxusercontent.com/u/12405967/shape.nb

What other realistic applications could you think of?
How to realize them?
Interesting articles?

ps. this discussion on comp.compression (there is some activity):
https://groups.google.com/forum/#!to...on/9t0_fqeY3DQ

[willvarfar]

(I never took it any further but here's an old post by me: http://williamedwardscoder.tumblr.co...3d-game-models )

[Jarek]

Thanks, this Stripe seems something like this
http://www3.cs.stonybrook.edu/~stripe/stripev2.html
but there is not much information and it's 17 years old ...

The used naive standard is extremely wasteful:
- it uses floats,
- it directly stores all coordinates of veritces,
- but the worst is that it defines triangles by 3 e.g. 32bit labels ...

Regarding floats, all these coordinates are similar numbers - the exponent and high bits of float should be usually the same.
The basic improvement can be done by storing differences, use a fixed precision for them, and preferably an entropy coder for the more significant bits.

And generally there is much less information in such a mesh due to constraints - storing the triangle strip and then undending it by decoder, like in the animation above, says that there is sufficient:
- storing the stricture of the stripe - which can be chosen as a characteristic tree - we need ~ 1 bit/node ... instead of e.g. 3x32bits ...
- storing the distances - it is sufficient to store e.g. the length of the edge on the left of a triangle - then the edge on the right can be obtained from its neighbor.
Additionally, these are close to equilateral triangles - we should store the difference from the length of the base of the triangle, and use entropy coder for its most significant digits.

Finally, we should get really cheap ~20x dedicated compression comparing to the used standards ...

[willvarfar]

Thanks, this Stripe seems something like this
http://www3.cs.stonybrook.edu/~stripe/stripev2.html
but there is not much information and it's 17 years old ...

Yes. But its good.

- but the worst is that it defines triangles by 3 e.g. 32bit labels ...

This is what the GPU wants to eat. There is a vertex buffer and an index buffer. Instead of repeating the three coordinates of each point for each triangle (36 bytes) it prints three three indices into a separate vextex array (12 bytes per triangle, and most vertices are shared by several triangles). However you compress the model, you probably have to uncompress it back into a vertex buffer and an index buffer.

These days most character meshes are bone-based.

Although this can probably be lossy. And you have various bitmaps that go with the mesh e.g. texturing. On the one hand this complicates matters, as these texture coordinates need to be compressed too. But on the other hand this may also be interesting statistical input, as I suspect its fairly rare for the artist to stretch and distort texture coordinates. Maybe the artwork patches and looking for 'dead space' in the texture tells you something about the dimensions of the meshes it covers?

There are lots of academic work on compressing meshes. E.g. top of my google search is http://www.cc.gatech.edu/~jarek/papers/Compression.pdf

Mesh simplification is closely related (its basically lossy compression).

[nburns]

* deleted *