8

I am looking for a method / algorithm that will allow me to merge several adjacent coplanar faces on a 3d mesh into a single face. I am hoping that this will optimize my mesh generation program, because right now it generates many 'little' triangles. When I look at the final 3d object on the screen, I can see that they all are oriented in the same direction and they could be replaced with one bigger triangle that encompasses the whole lot! I hope that is clear what I am trying to do. Thanks for your help.

Ross Oliver
  • 1,075
  • 1
  • 11
  • 15
  • It sounds like you're looking for a mesh simplification algorithm. There are many out there, I don't know enough about them off the top of my head to give you any recommendations, but that's the google term you're looking for.. "Mesh simplification algorithm". (Note: I know you're not looking to simplify the overall mesh so much as merge adjacent triangles, but I suspect those algorithms will do that work along the way, and all you'll need to do is keep your tolerances low to retain the vast majority of the detail in your mesh.) – hexist Jan 12 '13 at 05:05
  • Yip thanks for that - but there are many ways you can simplify a mesh. For example - merging (or welding) vertices that are situated close together. Merging of coplanar faces is just one piece of simplification that I need. Also I don't want to change the shape of the object in any way by reducing the resolution of the mesh. merging coplanar faces will not do that. – Ross Oliver Jan 12 '13 at 05:41
  • A naive approach would involve calculating the normals of each triangle (take the cross product of two edges and normalize it), and merge adjacent triangles with the same normal (or with a tolerably small difference). Have you tried that? –  Jan 12 '13 at 12:59
  • yip, i am putting together some code that does just that. however i am trying to get my head around the merge process. ie which vertices do i collapse down into 1, and how to remove one of the triangles from the face list. Still working on it. – Ross Oliver Jan 12 '13 at 23:54
  • I have a similar problem in this space. In particular, I _know_ certain vertices are coplanar, but I need to decimate to the outer most ring . . . – meawoppl Jan 28 '13 at 06:46
  • This helps too: http://stackoverflow.com/questions/14108553/get-border-edges-of-mesh-in-winding-order – meawoppl Jan 28 '13 at 07:03
  • Yes. That is my own answer to my own question. regarding how to find boundary edges. I have shown the code there. This question is different. I have made it a little bit further on how to merge coplanar faces. "Mesh Simplification" is too broader term for what needs to be done here. You have to perform a "retesselation" operation where you merge similar fragments in the same plane together. Following that you use a "canonicalization" operation to 'weld' verticies together that reside in close proximity to each other. When I figure out how to retesselate I'll post the code to learn from. – Ross Oliver Jan 30 '13 at 09:32

2 Answers2

2

I would suggest you project the faces in a single plane and than apply an algorithm for polygon uninon a plane. After that "unproject" and that's it. Always try to reduce dimensions when possible.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • Typically a mesh of 3D object is significantly not-planar (especially if the mesh is closed and the object contains some handles), so there is no single plane where it can be projected without self-intersections. – Fedor Nov 06 '22 at 18:18
1

Your task is a special case of mesh simplification (or decimation), where the algorithm is only allowed to reduce some mesh elements without introducing any error in object's shape. And probably the most famous algorithm here is Surface Simplification Using Quadric Error Metrics.

It searches for edges in the mesh that can be contracted in a single vertex (which position is automatically selected for each edge) so that it minimizes quadratic error associated with that contraction (in your case the error is zero).

Let us consider a simple example of cube's face subdivided in 8 triangles:

Mesh simplification

  • Left: magenta edge is selected for contraction, remaining vertex will be located in the bottom point of the edge.
  • Center: after the first contraction, next magenta edge is selected, after contraction it will become a vertex in cube's corner.
  • Right: the final result of simplification (after contractions on other cube's faces as well), where no more coplanar triangles can be merged (at least in larger triangles).

The illustration above was prepared in MeshInspector application.

Fedor
  • 17,146
  • 13
  • 40
  • 131