Partitioning Surfaces into Quadrilateral Patches: A Survey

The efficient and practical representation and processing of geometrically or topologically complex shapes often demands a partitioning into simpler patches. Possibilities range from unstructured arrangements of arbitrarily shaped patches on the one end, to highly structured conforming networks of all-quadrilateral patches on the other end of the spectrum. Due to its regularity, this latter extreme of conforming partitions with quadrilateral patches, called quad layouts, is most beneficial in many application scenarios, for instance enabling the use of tensor-product representations based on NURBS or Bézier patches, grid-based multiresolution techniques, and discrete pixel-based map representations. However, this type of partition is also most complicated to create due to the strict inherent structural restrictions. Traditionally often performed manually in a tedious and demanding process, research in computer graphics and geometry processing has led to a number of computer-assisted, semi- automatic, as well as fully automatic approaches to address this problem more efficiently. This survey provides a detailed discussion of this range of methods, treats their strengths and weaknesses, and outlines open problems in this field of research.