Piecewise-circular curves for geometric modeling

Modern solid modelers must be able to represent a wide class of objects, and must support Boolean operations on solids. These operations are very useful for defining solids, detecting interferences, and modeling fabrication processes. Computing the boundaries of solids defined through Boolean operations requires algorithms for surface/surface and curve/surface intersection. Many of the currently available modelers use closed-form parametric expressions for the curves of intersection of quadric surfaces, and compute intersections of these curves with other surfaces by finding the roots of low-degree polynomials. Because the curves that result from intersections involving tori or more complex surfaces generally cannot be expressed in closed form, modelers typically approximate these curves by cubic splines that interpolate points lying on the true intersections. Cubic splines exhibit second-degree continuity, but they are expensive to process in solid modeling computations. In this paper, we trade second-degree continuity for computational simplicity, and present a method for interpolating three-dimensional points and associated unit tangent vectors by smooth space curves composed of straight line segments and circular arcs. These curves are designated as PCCs (for piecewise-circular curves) and have continuous unit tangents. PCCs can be used in efficient algorithms for performing fundamental geometric computations, such as the evaluation of the minimal distance from a point to a curve or the intersection of a curve and a surface. Formulae and algorithms are presented for generating and processing PCCs in solid modelers. We also show that PCCs are useful for incorporating toroidal primitives, as well as sweeping, growing, shrinking, and blending operations in systems that model solids bounded by the natural quadric surfaces—planes, cylinders, cones, and spheres.