A tessellation algorithm for the representation of trimmed NURBS surfaces with arbitrary trimming curves

Computer-Aided Design, Elsevier, Vol 28, Num 6, pp.461-472, 1996

MESHING
RESEARCH
CORNER

Bernd Hamann
Department of Computer Science, University of California, Davis, CA 95616-8562, USA
Po-Yu Tsai
NSF Engineering Research Center for Computational Field Sirnulation, Mississippi State University, PO Box 6176, Mississippi State, MS 39762, USA

Abstract
In most CAD systems, a trimmed parametric surface is defined by two things: the control information of the surface itself and the control information of its trimming curves, which are usually defined as parametric curves in the parameter space of the surface. Often, trimmed parametric surfaces cause problems in the context of data exchange between CAD systems, surface evaluation/rendering, and grid/mesh generation. This paper describes a new approach for representing a trimmed surface. The approach is based on the idea of decomposing the valid part of the parameter space of a trimmed surface by a set of planar, ruled surfaces, which are defined in parameter space and whose union defines the entire valid part. A generalized Voronoi diagram is constructed for the set of trimming curves in parameter space. This diagram defines tiles around each trimming curve, which are further tessellated by utilizing a scan line technique for identifying and filling the interior of polygons. Here, the scan line technique is used to extract non- horizontal segments of the given trimming curves. Pairs of these segments are then linearly interpolated in horizontal parameter direction, thus defining a set of planar, ruled surfaces. The set of an these planar, ruled surfaces defines the entire valid part of a trimmed surface exactly.