Additional Output in MeshGL would be useful to me

[howardt]

Having just about completed the code to use Manifold in Blender, I found some things lacking in the MeshGL output, and had to write a fair amount of code to work around that. It's not a deal breaker, because I have now written that code, but it could be that future users of Manifold might run into the same needs, so I will list here some additional output that would have been useful to me.

The Problem

The missing things are all of the form: for output element X, what input element Y is that the output element is either identical to or a subset of (if any)? If there are multiple possible answers, any will do. If there are no answers for a particular output element, then that needs to be indicated too (e.g., by a -1 as the map value).

I need this for the element types: Vertex, Face, Edge (a separate element that can be shared between faces that go between the same two vertices), and Corner (Corner = a vertex but associated with a particular face that it is part of; so each vertex generates a number of corners).

Why do I need this? Because there are attributes associated with each of the element types, and those attributes need to be propagated to the output mesh as much as possible. The attribute data types are more than just floats/doubles: they can be booleans, integers of various sizes, floats, 2d and 3d vectors of ints or floats, strings, and transform matrices.

Current State

Face is decently handled by MeshGL now.

Vertex could be handled by using a float property for each vertex that is the vertex index (with some hack like multiple properties if the indices get bigger than the mantissa of a float can handle). But I tried this and it was enough slower than my workaround code that I decided not to use the Manifold properties. For the record, my workaround code goes through each output face, then for each vertex in that, goes through the corresponding input face looking for vertices with the exact same coordinates. (I know, this is fragile, hacky, and won't always work).

Corner could be handled by splitting each vertex into a number of copies equal to the number of triangles that meet at the vertex, and then using property method just described to keep track of corner indices. Given the performance hit for Vertex properties, I was reluctant to try this.

The biggest lack is for element type Edge. The workaround code I had to write for this was long enough and hacky enough that I would have loved not to have to write it. The workaround looks through output faces and then compares them to the original faces that they came from, looking either for identical edges or edges that start or end on same (when mapped) vertices but whose other end could be a new vertex, as long as the edges are in the same direction (to some tolerance). (I know, this is fragile, hacky, and won't always work. And doesn't handle the case of both ends being new vertices that are between two existing ones on an input edge.)

Desired State

Ideally, there would just be output_to_input maps for each of the 4 kinds of elements. For corners and edges you'd have to figure out some kind of indexing system, likely based on the input order of the input triangles. Something like the runs of OriginalID for faces could also work, but it needn't be that elaborate for the other types (which usually shouldn't have the capability of having the same id). I don't need any of the property management stuff that Manifold currently has (though I recognize that other users may like / need it).

Enabled Use Cases

Strictly speaking, there are no new uses cases enabled by this, since there are workarounds to this not being present. But it could be that the effort to write the workarounds is discouraging some adoption of the library?

However, I do think it is fair to say that the use case of edge attributes is something that might be regarded as a new use case, since it is so foreign to what Manifold handles right now. A 3D modeling program such as Blender finds it useful to let users assign properties to edges to say how they should be sharpened, creased, UV split, beveled, etc. After doing a Boolean operation, they would like those to properties to be preserved as much as possibly, even on edges that only partially survive into the output.

[pca006132]

I'm curious about the performance issue with vertex properties, I think it was not getting too much attention previously.

For edges, not sure what is the best way to do that. I think we should have the information required to compute that.

For the output to input mapping, I wonder if there is a way to store it internally without hurting performance, and users can query it alongside with the MeshGL.

[howardt]

For edges I would be a bit surprised if you have the data to do that. When you create new geometry by intersection, you create new edges that are (sometimes) pieces of edges of old triangles. I imagine the relation to the original edge is lost at that point unless you make a special effort to remember it. Of course, you will know which original triangle the new one is a part of, so you can compare the new triangle to the original one and suss out such relationships. That's what my "workaround" code does.

[pca006132]

Yeah, we probably need to somehow remember that when we perform linear interpolation to get the point...

[elalish]

Every input edge has a unique pair of faces, and we have a face mapping already. How about:

0. Generate a halfedge data structure where each edge points to two faces (as well as its usual two verts). We could potentially expose this since we use it internally, but it's also pretty easy to construct.
1. Make a hash map where the value is each input edge and the key is its pair of faces.
2. Look up the original two faces corresponding to the two current faces of your output edge.
3. Look up the input edge in your hash map using this face pair.

Corners are similar, since they are between a unique pair of edges. Ideally the vertex duplication that occurs in MeshGL already removes the need to handle corners specially, but maybe you have meshes where no corner properties are shared?

Are there practical problems with this approach? Am I misunderstanding anything?

[howardt]

I believe your approach to edges works. It is probably faster than my current approach, but would have to check to be sure. Having optional access to something like the halfedge structure afterwards would be great for another reason: right now I just use Blender's internal function to calculate the Blender "Edges" after creating a Blender Mesh from MeshGL. It was a pity to do that since the HalfEdge structure would make it easy for me to do so myself.

I may have an imperfect understanding how Manifold's "vertex duplication" would be used to solve the corner problem. I think what I would do is this: for every input vertex, check the corner attributes of all triangles that share that vertex. Partition thoee triangles into groups where each group has identical values for all corner attributes at the vertex in question. Then, for input to Manifold, split the original vertex into n copies where n is the number of groups in the partition. Set mergeFrom and mergeTo appropriately. For each copy of the original vertex, put in the corner attributes for the corresponding partition group as vertex properties. On output from Manifold, I should expect mergeFrom/mergeTo to be populated, but before doing that merge, I will have distinct output vertices for each output triangle that had a different copy of the input partition for that vertex, so the corner attribute values will be available. Is that right? Please correct me if I'm wrong. I have to say, this is a lot of work and coding compared to what I currently do. One particularly annoying part is that in our current Blender Mesh structure, we don't have which faces are connected to a particular vertex. This can be calculated and cached, but it isn't available by default. So it would be quite a lot easier for me to just make every "partition" above just be a single corner, regardless of whether or not the corner attributes all match.

For corners, the usual (and important) attribute is UV coordinates. There may be multiple UV maps. In the specific case of corner attributes, movated by the UV case, I have to also generate attribute values for newly generated corners. I do this by a special interpolation in the original face that the new vertex is in. I think you do interpolation for missing property values but I think (correct me if I'm wrong) that you just interpolate between the values of the properties at the ends of the edge that you split to get the new vertex, That is the same as the interpolation we do in that case, I think. But what do you do about properties that are for vertices creates in the middle of an existing face (e.g., when a triangle pierces the face of another triangle, forming a new line segment in the middle of that second triangle? Anyway, I probably still couldn't use it, because I want interpolation in the original face (not original triangle -- I have of course triangulated the original ngons before handing them to you). Due to the possibility of multiple UV maps, and the issue of interpolation, I'd prefer output->input corner map. There is also the issue, mentioned in an earlier post, that general handling of vertex properties in Manifold is slower than not using them and working around that.

[elalish]

Yes, you seem to have the correct understanding of everything. Interpolating UVs in the middle of a triangle is just as natural as on an edge - barycentric interpolation. We don't keep vertex to face info either; not sure why you'd need it. It really sounds like you're duplicating exactly what we do internally for properties. I'd encourage you to take another try at using our API instead of building it all again. If you can show us a perf problem with that, we can fix it.