Filling N-Sided Regions by Quad Meshes for Subdivision Surfaces

Abstract

Given an n-sided region bounded by a loop of n polylines, we present a general algorithm to fill such a region by a quad mesh suitable for a subdivision scheme. Typically, the approach consists of two phases: the topological phase and the geometrical phase. In the first part, the connectivity of the mesh is based on determining a partitioning of the region into rectangular subregions across which regular grid could be constructed. The geometrical phase generalizes discrete Coon s patches to position the vertices in the 3D space. The generated mesh could be taken as input to any quad-based subdivision scheme, such as that of Catmull-Clark or Doo-Sabin to generate the corresponding limit surface. The goal of the algorithm is to generate smooth meshes with minimum number and less valence of extraordinary vertices deemed undesirable in such subdivision schemes.