Results 1 to 5 of 5

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

  1. #1
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts

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

    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
    Last edited by Jarek; 9th October 2015 at 10:57.

  2. The Following 2 Users Say Thank You to Jarek For This Useful Post:

    Cyan (12th October 2015),willvarfar (9th October 2015)

  3. #2
    Member
    Join Date
    Feb 2010
    Location
    Nordic
    Posts
    200
    Thanks
    41
    Thanked 36 Times in 12 Posts
    (I never took it any further but here's an old post by me: http://williamedwardscoder.tumblr.co...3d-game-models )

  4. The Following User Says Thank You to willvarfar For This Useful Post:

    Jarek (9th October 2015)

  5. #3
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts
    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 ...
    Last edited by Jarek; 12th October 2015 at 09:02.

  6. #4
    Member
    Join Date
    Feb 2010
    Location
    Nordic
    Posts
    200
    Thanks
    41
    Thanked 36 Times in 12 Posts
    Quote Originally Posted by Jarek View Post
    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).

  7. The Following User Says Thank You to willvarfar For This Useful Post:

    Jarek (11th October 2015)

  8. #5
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 71 Times in 55 Posts
    * deleted *
    Last edited by nburns; 13th October 2015 at 02:50.

Similar Threads

  1. loseless data compression method for all digital data type
    By rarkyan in forum Data Compression
    Replies: 157
    Last Post: 9th July 2019, 17:28
  2. Data Compression PC
    By encode in forum The Off-Topic Lounge
    Replies: 202
    Last Post: 3rd January 2019, 23:28
  3. lossless data compression
    By SLS in forum Data Compression
    Replies: 21
    Last Post: 15th March 2011, 11:35
  4. Sensor Data Compression
    By mmhn97 in forum Data Compression
    Replies: 11
    Last Post: 21st December 2010, 06:21
  5. Data Compression Evolution
    By encode in forum Forum Archive
    Replies: 3
    Last Post: 11th February 2007, 15:33

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •