The base code for meshy descends from a very crude mesh slicing visualizer I wrote to get in the mood for a job interview (based on this here paper); this thing imported STL files, turned them into slices, and did nothing else. Thus, the STL format originally informed the internal data structure.
v, you can do
var vp = v;, so now
vp will reference the same object. When I say “duplicated vertices” in the following, I mean distinct
THREE.Vector3 objects with the same coordinate values. You can manually diplicate
A binary STL file, as detailed on Wikipedia, is little more than an array of binary
vertex blocks - four 3-vectors, each made of 32-bit floats. A given vertex will be repeated for each face that contains it - this is a wee bit inefficient, but it makes for a simple format. In terms of importing an STL file into an application, I ended up with an array of
Triangle objects, each with a normal and three vertices (again, repeated).
OBJ, meanwhile, is a much more complicated ASCII format. Just for geometry, it goes something like:
# vertex coords v 0 0 0 v 0.1 0.2 0.3 v 5 4 3 #... # these are normals, but they don't even have to be normalized # note that these are per-vertex, not per-face vn 0 1 0 vn 0.7 0.7 0 #... # face indices; the "/..." are additional fields for texture coord and normal indices f 1 2 3 f 4/... 5/... 6/... #...
So the vertices are specified uniquely, as are the faces, which are just indices into the vertex array (notably, the indices are 1-based). Now, for our purposes, we’re ignoring texture coords, “parameter space vertices”, and everything that’s not specified above.
(To make matters more confusing, OBJs allow n-gons by specifying more than three vertex indices per face. I threw in the towel and said that I’m not allowing n-gons above quads. And I’m triangulating the quads.)
Now, importing this into the “repeating triangle soup” thing I had is straightforward - make a list of vertex objects first, then duplicate them when making a new face. (You couldn’t get away with not duplicating them because every algorithm assumed duplicated vertices - e.g., the translation function iterated through the faces, then shifted all the vertices for each face.)
Exporting to STL works trivially; the problem arises when trying to export as OBJ. To start, we need a list of unqiue vertices - but you might have a million of them, and iterating through the faces, each with repeated coords, building a list of unique vertices, is an problem because you need to check for membership in the list of vertices so far. We clearly need some kind of hashing scheme.
But Grandma, why repeat vertices?
Indeed, why do that? It took a bit of effort, but I reworked the whole project to basically follow the OBJ scheme instead - now our geometry is stored as an array of unique vertices, plus an array of
Triangle objects, each of which has three indices into the vertex array, a normal, and some
Triangle-specific methods like calculating volumes and such.
So now importing OBJ works trivially, plus we don’t need to duplicate vertex objects anymore. Importing STL? This is now where we need to do the hash table thing. Exporting STL and OBJ works straight up.
I think some improvements (or, more accurately, reasonable tradeoffs) could be made to how meshy stores geometry. The vertices are stored as a list of
Vector3 objects, which are irreducible. The faces, though, I store as a list of
Triangle objects, which do have some storage overhead. All they really need is three integer indices and a
Vector3 for the normal, but currently they also store the triangle bounds (
xmax, etc.), a surface area, and a signed volume. These are all cached for subsequent calculations, but these calculations are fairly discrete and I’d want to experiment to see what kind of performance impact eliminating this internal storage will have.