Submitted to CAD, October 2003, Revised May 2004 1 Fair, G2- and C2-Continuous Circle Splines for the Interpolation of Sparse Data Points Carlo H. Séquin, Kiha Lee, Jane YenABSTRACTThis paper presents a carefully chosen curve blending scheme between circles, which is based on angles, rather than point positions. The result is a class of circle-splines that robustly produce fair-looking G2-continuous curves without any cusps or kinks, even through rather challenging, sparse sets of interpolation points. With a simple reparameterization the curves can also be made C2-continuous. The same method is usable in the plane, on the sphere, and in 3D space. Keywords CAD, circle-splines, curves & surfaces, geometric modeling, sparse data interpolation. 1. INTRODUCTION, MOTIVATION Fair, interpolatory spline curves are useful constructs for many application domains and design environments, ranging from the construction of ship hulls and aerodynamic profiles, through key-frame animation, to smooth camera motions for flying around objects of interests. For certain applications, such as aesthetic designs or camera paths, smooth, nicely rounded paths – free of cusps and abrupt hairpin turns – are more important than the property of affine invariance. In these situations, schemes based on circles can more easily satisfy such demands than polynomial splines. A few blending schemes have been developed that aim to accommodate circular arcs whenever possible. Biarcs generate segments of the overall curve with pairs of circular arcs connected with tangent continuity [2][15][9][16][8]. Other schemes use a gradual blending between corresponding points on two circular arcs; they can achieve smooth looking paths with G1- or G2-continuity, depending on the exact blending procedure used [18][6][14]. The most ambitious approaches involve global curve optimization, such as the Minimum Energy Curve (MEC) [4], or the Minimum Variation Curve (MVC) [7] [10], in which circles result as the zero-cost solution whenever permitted by the constraints. (a) (b)Submitted to CAD, October 2003, Revised May 2004 2 Figure 1: (a) A circle spline and its control polygon on a sphere; (b) a sculpture model derived from a sweep along such circle spline. The original motivation for the development of circle splines [11] was to provide smooth, pleasing curves embedded in the surface of a sphere, either for a special class of geometrical sculpture (Fig.1), or for the definition of a camera path that flies around a stationary object approximating a Grand Tour [1], looking inward to inspect that object from “all sides.” However, the new robust solution presented in this paper gives equally good results in the plane and for space curves in three- or higher-dimensional Euclidean space. The primary goal still is to define aesthetically pleasing curves with just a few “fix-points.” Artists often like to construct a well-rounded fair curve, with a “natural” look such as the shape of a stiff steel wire, confined in space at only a few points, but with the additional capability to adjust its length locally so as to give each loop an optimal bulge that leads to the smoothest possible transitions in curvature. Currently such shapes seem to be realizable only in the virtual world of a good CAD environment. Our goal for these curves was to achieve as much of the behavior of a MVC as possible, but with a strictly local support domain. The result is a new class of interpolating circle splines that not only achieve the desired goal on the sphere, but also improve the properties of the circle-blending schemes previously described in 2- or 3-dimensional Euclidean space. 2. BACKGROUND, PREVIOUS WORK The simplest circle spline schemes look at four consecutive points Pi-1, Pi, Pi+1, Pi+2 to calculate the curve segment between points Pi and Pi+1. These points alone determine the shape of that segment. Thus, these curves have tightly limited local support. For the special case where all but one interpolation point, Pi, lie on a straight line (Fig.2), only four curve segments will deviate from a perfect straight line. In the special case depicted in Figure 3, where all the interpolation points lie on two circular arcs, only the single transition segment will deviate from a perfect circular arc. Figure 2: Influence zone of point Pi. Figure 3: Zones of perfect circles. In general, the curve segment between points Pi and Pi+1 is formed by first fitting a circular arc, arci, through points Pi-1, Pi, Pi+1, in sequence, and a second arc, arci+1, through points Pi, Pi+1, and Pi+2 (Fig.4). Then, in the region between Pi and Pi+1 the two circular arcs are blended together by gradually shifting the weight from arci to arci+1, as the parametric curve point moves from Pi to Pi+1. The crucial question is, how exactly should one perform this blending operation?Submitted to CAD, October 2003, Revised May 2004 3 Figure 4: Generic blending approach using four consecutive data points. Wenz [18] achieves this blending operation by performing a linear positional interpolation between corresponding points on the two base arcs that have the same parameter values. The two arcs, arci(u) and arci+1(u) , are parameterized so that they are traced from Pi to Pi+1 as the parameter u goes from 0 to 1. Using a simple linear blending scheme (Fig.5a), the new parametric curve point is then found as: P(u) = (1-u) * arci(u) + u * arci+1(u). (1) Szilvasi-Nagi and Vendel [14] improved on that scheme, by replacing the linear interpolation function with a trigonometrically weighted blending function (Fig.5b): P(u) = cos2(u π/2) * arci(u) + sin2(u π/2) * arci+1(u). (2) This has the effect that the blend curve clings more strongly to the base arcs near the end points Pi and Pi+1, and thereby picks up the curvature of the base arcs in addition to their tangents at Pi and Pi+1, respectively. This guarantees that the individually generated blend segments will join with G2-continuity across all the interpolation points. Figure 5: Blending functions: (a) linear and (b) trigonometric. However, both these schemes can produce undesirable loops or even cusps, when the control polygon through the sequence of given data points shows large turning angles at some point (Fig.6). The main problem is that the straight parameter lines that