koobas.hobune.stream
Merge mesh triangles into polygons: need help with vertex ordering
I’ve got an algorithm that takes triangular based meshes and creates a polygon based “mesh” from it. It seems to be working well except for one point.
When I do merge triangles or polygons(previously merged triangles) together (they must lie on the same plane and share an edge to be merged) into a poly, the points are no longer in “counterclockwise” order.
What I have been doing is, given poly1 and poly2: Remove the shared vertices from poly2, and then append the remaining vertices to poly1.
While this does get all the points I need into the polygon, it also, sometimes, messes up the order of the points. (even for a simple cube!)
This method also does NOT get rid of all unneeded points: consider a pie-slice-like, pentagon of triangles. Once I add the last triangle of the pentagon, the center vertex should be eliminated. But I have no idea how to check for such a condition.
QUESTIONS: How can ensure my polygons vertex order is correct (ideally WHILE merging two polys)?
How can I detect if particular vertex points need to be eliminated (like the center of the pie-slices)?
Thoughts: I was considering the following solution, but it won’t work for concave polygons, nor will it help with that center vertex removal I exampled above: Randomly select an interior point. Compute the angle between that point and each vertex. Sort vertices based on that angle.
I’ve researched this a bit, and found some good stuff, but nothing that has really helped with this particular minutiae of the algorithm. My initial research also failed to find an open-source-library which does this algorithm already, which was surprising, until I remembered I’m totally awful at searches.
UPDATE: progress so far... we know merging polys shared at least 2 vertices(flush).. so:
Rather than APPEND the vertices from one poly to another when merging, we must INSERT the vertices from one poly BETWEEN the two shared vertices of the other.
Furthermore, if we are merging a triangle and a poly, if we have 3 shared vertices, we REMOVE the middle shared vertex from the poly. (to get rid of the vertex in the center of the pie)
Working better now, but sill having a few issues (though it may just be a bug in my implementation of the above).
Update2: I managed to get an implementation going that creates an EDGE rather than a polygon, on triangles that are FLUSH , but NOT parallel (edge is created between the two shared vertices-"flush"). this seems to work for closed surface meshes only.
Update3: OK, getting REALLY close now. The ONLY issue remaining is one I though I had solved, but haven't. When combining two polys that share THREE vertices, this means I am "CLOSING" the polygon. I will need to insert all the vertices (except those shared), from poly A, between two of the three shared vertices of poly B, and remove the last shared vertex (the interior point) from the final poly. I remain unable to figure out which two points to insert between, and which point to remove. My intuition tells me it has to do the the number of vertices listed BETWEEN the three vertices in question, but I don't see it yet.
Is this mesh going to be visible?
$$anonymous$$erging collision meshes is pretty trivial, as you won't care about UVs. If that's not the case, merging is a lot harder. Remember, the standard cube has 24 verts, not 8, as each corner needs different UVs.
No, it will not be visible. UV, normal, and color information is all discarded. (Because of your point about the cube vertices: at the very beginning of the routine, I check each vertex's position and if any others have the same position, I merge them into a single vertex.)
Actually, I'm NOT trying to merge meshes, I'm triangle to merge the TRIANGLES that make up a mesh, into a polygon based mesh data structure(basically, a list of polygons, where Polygon is just a list of vertex indexes). One I have this data, I can then use this to draw objects between vertices for a wire-frame like effect, or animate transform between vertices to get a cool effect. (But that's only a couple of examples of what I would like to do with these polygon meshes.)
$$anonymous$$any thanks for the input!
Dear Glurth, I am working on similar problem where I am trying to merge 3D polygon on same plane. I faced same issue where I messed up order of points. I would like to know 1) What is complexity of your algorithm ? 2) I haven't got enough documents on internet, if possible can you please share some links.
Thanks,
I eventually found a solution, here is the psudo-code:
Merge poly A into B
Find first TWO or THREE shared verticies
If we find exactly 3 shared verticies:
-We compute the different between every shared vertex-index in B with every other shared-vertex in B
-The differences that has a value of "2" specifies which of the two indices have the third BETWEEN them.
-This third, between point, is the one we will want to discard.
Once that point is discarded we insert all the verticies from the second poly (excluding any shared points) in exactly the same order as the original. NOTE: This last part ASSUMES the two polygons are facing the same direction, vertex order-wise, before merging.
-If our two points straddle the end or the vertex list, we insert at the end of the vertex list.
