How do I convert a 2D mesh of triangles into quadrilaterals?

Question

How do I convert a 2D mesh of triangles into quadrilaterals? Is this the best approach or it is even possible to generate a 2D quadrilateral mesh from scratch?

Answer 1

As part of their paper on Quad Mesh Simplification, Tarini et al. present a section on Tri to Quad mesh conversion (Section 6 to be precise).
You can find the paper on the author's website here: "Practical quad mesh simplification" (PDF).

This has been published at:
Computer Graphics Forum (Special Issue of Eurographics 2010 Conference), Volume 29, Number 2, page 407-418 - 2010
DOI: 10.1111/j.1467-8659.2009.01610.x

The Open Source implementation should be available as part of MeshLab.