Additional per-element information

[jimy-byerley]

For my project I need to keep trace of what operation has created which vertices, faces or halfedges.
The problem is that knowing which face will be kept in the result during a complex mesh operations (such as boolean) is as complex as doing the operation itself.
So I think it could be usefull to put element-associated informations inside the mesh itself.

So to put additional datas to halfedges, there is 3 options:

• use a generic type for the mesh definition Mesh<T> and ConnectivityInfo<T>, HalfEdge<T>
  The use will have to specify T at the Mesh declaration.
  But this way is painful because it require to many Mesh methods just to add the genericity.

• use a Vec<u32> for each hafedge, therefore each halfedge would store and integer for each group of halfedges it belongs to.
  This way is not memory-efficient.

• use a Vec<HalfEdgeID> for each halfedge group
  This way is not very interesting since it makes it harder to find the group a halfedge belongs to.

• use a u32 each Halfedge
  This way make it impossible to get the same halfedge in several groups, but it doesn't matter since we can interpret this int after. But it would be very memory efficient, and it would make it very simpl to implement (the u32 would a field of Halfedge and thus be copied with it).

I want to make a PR to implement it, I think the last option would be the best ?

[asny]

This is a classic problem. What you need is a flag for each primitive (you say each halfedge but I guess you can do with one for each face), but another use-case could be saving a normal per primitive or uv-coordinates etc. I haven't seen a really good solution to this, but there are some alternatives:

• Adding generic data to the mesh (option 1) is problematic because you don't know what should happen when you for example split a face. What should the value be for the new faces, the same as the original face or one third of it or what? And also it is going to be a lot of code to support this as you also points out.
• Another option is to be explicit (option 4), so design the data structure to a specific use-case and with the data types associated with the primitives that that use-case need. This is definitely a good approach but that means you have to do it in your fork, otherwise, other people will not find tri-mesh useful.
• The best solution I have seen is to keep the data outside of the mesh in maps from primitive id to whatever data you want. This means it is generic, you can choose exactly what data you want to store and for how long, but it does not intrude into the crate. The downside is of course that you need to keep the maps up-to-date, but you also have to do that if you put the data in tri-mesh. The map functionality itself could be part of tri-mesh (basically the functionality is already there in the IDMap, so you just need functionality to remove deleted and add new primitives from a map) but it could also be outside.

What do you think?

[jimy-byerley]

In fact I was hoping you would have a better idea than mine ;)

I agree that option 1 is very close to a specific use case. That's why I thought to put the flag to halfedges would be better that to faces for genericity (even If I only need a flag for each face in my own case). I wonder if one can ask more that one information each halfedge for any kind of purpose.

The goal of that flag would be to allow tracking primitives through operations, and as you said, I need to keep the map up-to-date.
The problem is that with only the IDMaps of a Mesh, I can't know which primitive has been changed during the last operation since IDs are reassigned when some primitives are discarded. The only way would be to clone the Mesh before each operation, then to compare the result with the operands (and that would yet be complex with multiple mesh as operands). So I can't see how to efficently update the map after the operation occured.

Do you think the primitive tracking purpose is too specific for tri-mesh ?

[asny]

Is it really necessary to keep track of which operation created what? No matter which solution, it requires a lot of bookkeeping. Also, no matter what, you will have problems with an operation which created some part of the mesh which was then altered by another operation which again was deleted by yet another operation.

The problem is that with only the IDMaps of a Mesh, I can't know which primitive has been changed during the last operation since IDs are reassigned when some primitives are discarded.

Yes, you need clean-up functionality which takes an IDMap and removes all dead primitives and add a value for all new primitives and you need to call that functionality regularly. If necessary, we could avoid reusing primitive ids until we run out of numbers, this way it would be unlikely that a primitive was both removed and created in the same operation.

Do you think the primitive tracking purpose is too specific for tri-mesh ?

Yes.

[jimy-byerley]

Yes I'ts very important for a CAD usage to know which operation created what. Take the example of a user selection tool, it requires something to say for the clicked face, which function has created it, and maybe get informations about it (radius and axis for cylinder surfaces for example, but that's not the concen).

With cleanup functionnality, it can't see how to track primitives for very intrinsic operations such as merge. Even with IDs not reused, the merge_overlaping_primitives decides which primitive to keep, so currently there is no direct matching between the new inserted IDs and the former IDs, (there is holes in the matching that need to be predicted that the merge algorithm is known).
The solution here would be to determine the new IDs with only the former ones and the size of the mesh to merge into, but that would be a big change for tri-mesh.

Also with unique and predictable IDs, we would loose the benefit of flat buffers you added to IDMap.

[asny]

Yes I'ts very important for a CAD usage to know which operation created what.

Ok, that is fair, just needed to make sure.

With cleanup functionnality, it can't see how to track primitives for very intrinsic operations such as merge.

I have a hard time figuring out how to track primitives in a merge operation, no matter which solution?

Have you experimented with something? I think it is a very difficult problem, so I think the best solution is to try something out and see what works for you and maybe we can generalise that solution and merge into tri-mesh and maybe we can't. What do you think about that?

Also I will reply faster, I promise :)