Adaptive polygonization of geometrically constrained surfaces

Abstract

Many surfaces in geometric and solid modeling, including offsets and blends, are naturally defined from given surfaces subject to geometric constraints. Surfaces that are geometrically constrained can be uniformly defined as the projection of two-dimensional manifolds (2-surfaces) in n-dimensional space, where n>3. This definition can be used for given surfaces that are implicit or parametric. This paper presents a robust, adaptive polygonization algorithm for evaluating and visualizing geometrically constrained surfaces. Let F be the constrained surface, a 2-surface in n-space, and let pi(F) be its projection into the subspace spanned by the first three coordinates. Our polygonization algorithm computes pi(F). The method works directly with the n-space representation, but performs all major computations in 3-space. Techniques for triangulation, polygon decimation, and local refinement are also presented.