Supposing I have applied delaunay triangulation on a convex mesh, and I have all information (edges, vertices etc.) I would like to transform the triangles to quads

I was reading that inverse process, quad to triangle, one takes the vertices like:

quad 1 2 3 4
triangle 1 2 3
triangle 3 4 1

each time we read a quad (4 vertices), we transform it to 2 triangles using these 4 vertices.

What would be the best approach to do triangles to quad?

I was thinking on pairing together adjacent triangular elements, and converting them into quadrilateral elements by eliminating their shared edges enter image description here

Do you know any sample code, would be best in c#

  • 1
    \$\begingroup\$ Is this for an arbitrary triangle mesh (as your diagram implies)? Or for a mesh that was originally quads? And what is the intended purpose? Are there any restrictions on the end result? Fewest quads? Most square-ish quads? etc... \$\endgroup\$ – Andrew Russell May 11 '14 at 3:38
  • \$\begingroup\$ Also, for anyone interested, there's a cross-post on Stack Overflow here. \$\endgroup\$ – Andrew Russell May 11 '14 at 3:39
  • \$\begingroup\$ The mesh is the result of delaunay triangulization, however I would like to substitute at least 2 triangles by one quad whenever possible \$\endgroup\$ – edgarmtze May 11 '14 at 3:55
  • \$\begingroup\$ @cMinor: What for do you want quads exactly? \$\endgroup\$ – Kromster May 14 '14 at 12:56

Any 2 triangles that share an edge and have identical normals (or are very close) can be candidates for turning into a quad. The pseudo code for something like this would be: List triangleList; List quadList;

foreach(Triangle currentTriangle in triangleList) { foreach(Triangle checkTriangle in triangleList) { if (currentTriangle != checkTriangle && currentTriangle.sharesEdge(checkTriangle) == true && currentTriangle.normal.dotProduct(checkTriangle.normal) > 0.99) { quadList.add(makeQuad(currentTriangle, checkTriangle)); triangleList.remove(currentTriangle); triangleList.remove(checkTriangle); break; } } }

This solution wouldn't give you the ideal list of quads, but it will be good enough in most cases. Where this solution would give a less than ideal solution would be in the case below:

Triangle strip

I've numbered the triangles here. Assuming they are all co-planar, you could certainly end up with a quad consisting of triangles 2 & 3, and then 2 triangles that can't be turned into quads with 1 & 4. The ideal solution of course would be 1 & 2 being a quad and 3 & 4 being another quad. I haven't done the math to prove it, but I think your worst case would be in a completely flat plane, you could end up with half quads and half triangles when the whole thing could be quads. Either way, it's a difficult problem to solve and the performance implications are likely to be negligible, so it's probably best to not bother optimizing.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.