Quadrilateral layout generation and optimization using equivalence classes of integral curves: theory and application to surfaces with boundaries

Extracting quadrilateral layouts from surface triangulations is an important step in texture mapping, semi-structured quadrilateral meshing for traditional analysis and spline reconstruction for isogeometric analysis. Current methods struggle to yield high-quality layouts with appropriate connectivity between singular nodes (known as "extraordinary points"for spline representations) without resorting to either mixed-integer optimization or manual constraint prescription. The first of these is computationally expensive and comes with no guarantees, while the second is laborious and error-prone. In this work, we rigorously characterize curves in a quadrilateral layout up to homotopy type and use this information to quickly define high-quality connectivity constraints between singular nodes. The mathematical theory is accompanied by appropriate computational algorithms. The efficacy of the proposed method is demonstrated in generating quadrilateral layouts on the United States Army's DEVCOM Generic Hull vehicle and parts of a bilinear quadrilateral finite element mesh (with some linear triangles) of a 1996 Dodge Neon.