0
\$\begingroup\$

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#

\$\endgroup\$
4
  • 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\$ May 11, 2014 at 3:38
  • \$\begingroup\$ Also, for anyone interested, there's a cross-post on Stack Overflow here. \$\endgroup\$ May 11, 2014 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, 2014 at 3:55
  • \$\begingroup\$ @cMinor: What for do you want quads exactly? \$\endgroup\$
    – Kromster
    May 14, 2014 at 12:56

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .