Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm

Many applications deal with the rendering of trimmed surfaces and the generation of grids for trimmed surfaces. Usually, a structured or unstructured grid must be constructed in the parameter space of the trimmed surface. Trimmed surfaces not only cause problems in the context of grid generation but also when exchanging data between different CAD systems. This paper describes a new approach for decomposing the valid part of the parameter space of a trimmed surface into a set of four-sided surfaces. The boundaries of these four-sided surfaces are line segments, segments of the trimming curves themselves, and segments of bisecting curves that are defined by a generalized Voronoi diagram implied by the trimming curves in parameter space. We use a triangular background mesh for the computation of the bisecting curves of the generalized Voronoi diagram.