Mesh triangulation algorithm fine tuning

[xxpy02]

I've been struggling to generate a exact copy of the MeshStructure.FaceEdgeArray. For some reason I can't find the proper triangulation algorithm when picking an index from the EdgePointArray when there are multiple matches for the same vertex.

For instance, when you look into the the body01.bs and group its FaceEdgeArray by faces (by using the MeshStructure.FaceLengthArray), you'll see something like this between faces 77 and 79:

[378, 235, 369, 375]
[380, 351, 382, 365]
[371, 381, 363, 384]

This is what my script generates right now at the same face positions:

[378, 235, 369, 371]
[380, 351, 382, 365]
[375, 381, 363, 384]

Both 375 and 371 (in blue) point to the same vertex in the end, but at different positions in the EdgePointArray. This happens everywhere in the array, its quite common.
When looking at the original bodies, it seems that the algorithm sometimes will pick the first or the second index, but I could not figure out what's the criteria for it.
I've tried different things, but if I change something to fix one in particular I'll get others swapped somewhere else.

In the end it doesn't really matter if they are swapped or not as they will always point to the same vertices regardless. But I really wanted to get a perfect optimization algo for this.
Does anyone have the smallest clue that could help with this?

[vi363R]

10 hours ago, xxpy02 said:

I've been struggling to generate a exact copy of the MeshStructure.FaceEdgeArray. For some reason I can't find the proper triangulation algorithm when picking an index from the EdgePointArray when there are multiple matches for the same vertex.

For instance, when you look into the the body01.bs and group its FaceEdgeArray by faces (by using the MeshStructure.FaceLengthArray), you'll see something like this between faces 77 and 79:

[378, 235, 369, 375]
[380, 351, 382, 365]
[371, 381, 363, 384]

This is what my script generates right now at the same face positions:

[378, 235, 369, 371]
[380, 351, 382, 365]
[375, 381, 363, 384]

Both 375 and 371 (in blue) point to the same vertex in the end, but at different positions in the EdgePointArray. This happens everywhere in the array, its quite common.
When looking at the original bodies, it seems that the algorithm sometimes will pick the first or the second index, but I could not figure out what's the criteria for it.
I've tried different things, but if I change something to fix one in particular I'll get others swapped somewhere else.

In the end it doesn't really matter if they are swapped or not as they will always point to the same vertices regardless. But I really wanted to get a perfect optimization algo for this.
Does anyone have the smallest clue that could help with this?

Did you already prompt an AI about the problem? I've found that in many cases it can really help, even in my professional life. Perhaps not the answer directly, but at least good array of options to experiment with.

[hfg2]

Most probably is Mikk algorithm. http://www.mikktspace.com/

Or something simple, like if you have a quad face and you need to triangulate, there are only two diagonals and you pick the shortest one, if the diagonals are equal or approximately equal you can then compare at the uvs face diagonals.

But the beauty of this mess is that you don't need to triangulate at all, you can keep all quads and the game will do the triangulation (and subdivision) for you anyway. My custom bodies comes from daz, all quads baby, and just look awesome. Let the game engine do that for you.

[xxpy02]

@vi363R I never used AI before (not even for code suggestion/copilot), but the biggest issue might be finding one that can interpret the current code and make suggestions on it - mostly because a good amount of input data is required for the algorithm to run. But it makes sense, I should give it a try at some point.

@hfg2 you mean that the algorithm may be using the face normals (that could be generated by the mikktspace algo) for sorting the vertices? So probably by taking the dot product between the face normals and choosing the vertex from the face that more closely points towards the same direction? The idea on using the UV diagonals/seams could work too.

I don't really mean to turn quads into tris actually, I am keeping whatever comes. "Triangulation" was probably a poor choice of word to describe the scenario at hand, but I am not a native english speaker thus I often lack the vocabulary to clearly communicate. What I am trying to accomplish is finding the correct surveying algorithm (position/proximity triangulation). I really meant to assess neigboring faces/edges and find what shared vertex index to pick for a given face.

In the original meshes two identical edges are collapsed into one. Given you could have multiple faces sharing the same vertex N, this vertex N will have multiple different indexes in the EdgePointArray; at most one for each edge. My issue was trying to come up with a common factor by which to "survey/triangulate" the other faces (and find some "proximity" factor) to sort the vertices and pick the one that is closer to the current one. But your suggestions are good candidates for this regardless, I'll give them both a try.

[xxpy02]

@hfg2 I was a bit lazy to go straight for face normals/uv coords and tried my luck with the adjacent vertex and well, it worked. If it wasn't for your suggestions, I wouldn't have done it.

Being able to output data optimized exactly like the originals...

[hfg2]

Is great if you got it working the way you wanted.