High-quality quad-mesh generation for self-intersecting parametric surfaces

Abstract We propose a method for the high-quality quadrangulation of an input self-intersecting parametric surface. We first compute the algebraic representation of self-intersecting curves and cusp curves of the surface by the moving plane method. Sampling points are then generated on the singular curves and the boundary over the parameter domain. In order to ensure the correctness of mesh intersection topology, we compute feature points and the pair-points of the curve sampling points, which are fixed strictly throughout our method. A triangle mesh is generated over the domain with the singular curves as constraint lines, which is the input of quadrilateral mesh generation. We compute a cross-field aligned with the feature lines and construct a coarse layout of quad patches relying on the cross-field. As T-junctions are allowed in the layout, we solve an Integer Linear Program (ILP) problem to determine the number of edges, thereby ensuring that the generated mesh is conforming. Feature lines are preserved perfectly throughout the pipeline by imposing constraints. In conclusion, our method guarantees the neighborhood coordination of mesh intersections, while still producing high-quality quadrilateral meshes.