Store list of unique vertices and reference vertices from facets via array indices

[bdtaylor]

Since STL files are intended to define a 3D surface mesh, many of the vertices will be identical between different facets. Rather than storing the vertex coordinates with each facet, it is much more efficient to build an array of unique vertices and store the array index of each vertex with each facet. The current implementation in FOSSIL requires (nfacets * 3 * 3 * 8 bytes = nfacets * 72 bytes) to store vertex coordinates, where nfacets is the number of facets. Assuming 4 byte integers are used for array indices, the suggested implementation requires (nfacets * 3 * 4 bytes = nfacets * 12 bytes) to store vertex indices for the facets and (nvertices * 3 * 8 bytes = nvertices * 24 bytes) to store the vertex coordinates, where nvertices is the number of unique vertices. The proposed implementation thus requires less storage than the current implementation if nvertices < 2.5 * nfacets, which is true for all practical STL files; typically, nvertices << nfacets.

Implementing the above would substantially decrease FOSSIL's storage requirements, would simplify some operations such as checking that a model is water tight, and would likely reduce execution time for many mesh operations.

[szaghi]

@bdtaylor

Totally agree, but currently, I am very busy. I do not know when I can try to implement the new, more efficient data model.