Choosing Corners

Choosing Corners of Rectangles for Mapped Meshing

Center for Computing Research


Consider mapping a regular i x j quadrilateral mesh of a rectangle onto a surface. The quality of the mapped mesh of the surface depends heavily on which vertices of the surface correspond to corners of the rectangle. Our problem is, given an n-sided surface, choose as corners four vertices such that the surface resembles a rectangle with corners at those vertices. Note that n could be quite large, and the length and width of the rectangle, i and j, are not prespecified. In general, there is either a goal number or a prescribed number of mesh edges for each bounding curve of the surface. The goals affect the quality of the mesh, and the prescribed edges may make finding a feasible set of corners difficult. The algorithm need only work for surfaces that are roughly rectangular, particularly those without large reflex angles, as otherwise an unstructured meshing algorithm is used instead. We report on the theory and implementation of algorithms for this problem.

We also give an overview of a solution to a related problem called interval assignment: Given a complex of surfaces sharing curves, globally assign the number of mesh edges or intervals for each curve such that it is possible to mesh each surface according to its prescribed quadrilateral meshing algorithm, and assigned and user- prescribed boundary mesh edges and corners. We also note a practical, constructive technique that relies on interval assignment that can generate a quadrilateral mesh of a complex of surfaces such that a compatible hexahedral mesh of the enclosed volume exists.


Scott A. Mitchell, "Choosing Corners of Rectangles for Mapped Meshing" ACM Press, in proc. 13th Annual Symposium on Computational Geometry, June 4-6 1997, pp 87-93.