search

google / draco

Draco is a library for compressing and decompressing 3D geometric meshes and point clouds. It is intended to improve the storage and transmission of 3D graphics.
https://google.github.io/draco/
Apache License 2.0
6.53k stars 967 forks source link

"Canonical" ordering of vertices / indices? #933

Open bubnikv opened 2 years ago

bubnikv commented 2 years ago

I am representing Prusa Research at 3MF consortium. I hope @ondys will enjoy the following discussion because of spending years on 3D printing research :-) Also greeting to a Czech Technical University alumni college.

The 3MF consortium https://3mf.io/ https://github.com/3mfconsortium is responsible for standardizing file format 3MF as a container for various 3D printing tasks. Currently meshes are stored into a 3MF file as indexed triangle sets, XML encoded.

3MF consortium members are investigating various forms of encoding and compression. Draco is a candidate due to its maturity and high compression rates. However high compression rates are only achieved with quantization and edge breaker encoding enabled.

To make Draco useful for CAD world, one has to be able to save / load a mesh in exactly the same form. To most customers it is acceptable to perform quantization and reordering of geometry when importing into the 3MF format. After such adjustment, the mesh should better persist in that quantized and reordered state for various reasons. One reason is sensitivity of computational geometry algorithms to slight mesh geometry and topology modifications, another reason is the option to reference mesh vertices / indices from other parts of a 3MF file.

Is it guaranteed that a mesh once compressed by Draco for the first time produces binary equal decompressed mesh after multiple round trips of decompression and compression? I propose to name the quantized mesh with vertices and indices reordered by the edge breaker a "canonical" form. Does Draco support such concept?

If Draco supports a "canonical" form, would it be possible to add an API to perform transformation into the "canonical" (that means quantization and reordering) without having to do the compression and decompression round trip? Would it be possible for the "cannonization" tool to return a map of vertex / index reordering and merging?

I have an impression from reading the issue tracker, that a "canonical" form could be a solution to many issues, for example: https://github.com/google/draco/issues/720 https://github.com/google/draco/issues/584

Thanks, Vojtech Bubnik Prusa Research

ondys commented 2 years ago

Hi Vojtech. Let me address both quantized vertices and indices separately:

  1. Draco can handle pre-quantized vertices which can be used for lossless encoding of attribute values. Basically, all attributes can be quantized before they are sent to the encoder, setting their internal data type to DT_INT32 (or possibly other integer representation). The encoder would then skip built-in quantization and proceed directly to the lossless compression.

  2. Reordering indices is a bit more tricky and I would need to investigate if it is even possible (for our implementation of the edgebreaker). One issue I'm worried about is that our edgebreaker decoding works in the reverse order vs encoding. That is, the mesh is decoded from the "back" (basically the same way as described here). This is more efficient decoding but the side-effect is that the order of decoded faces is in the reverse order vs the order in which they were encoded which basically means the order is not going to be preserved. What could be potentially done is to re-order the faces/indices after the decoding to match the order that would be obtained via "forward" decoding. I would need to look into that how feasible that would be though.