# Convert triangles to quads of a Mesh

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

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

• 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... – Andrew Russell May 11 '14 at 3:38
• Also, for anyone interested, there's a cross-post on Stack Overflow here. – Andrew Russell May 11 '14 at 3:39
• The mesh is the result of delaunay triangulization, however I would like to substitute at least 2 triangles by one quad whenever possible – edgarmtze May 11 '14 at 3:55
• @cMinor: What for do you want quads exactly? – 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; } } }