Surfaces in Computer Graphics (Geometric Modeling) Part 7

B-spline Interpolation

Algorithms for finding surfaces that interpolate some given data depend on the structure of the data. If the data consists of a rectangular array of points, the algorithm for finding an interpolating B-spline surface is based on the corresponding algorithm for B-spline curves. We shall outline the steps for one form of bicubic B-spline surface interpolation.

The Bicubic B-spline Interpolation Problem. Given parameter values withfind

a bicubic B-spline surface p(u,v) with the ui and vj as the n-knots and v-knots, respectively, and control points

To motivate the solution to the interpolation problem note that an interpolating B-spline surface of the form shown in equation (12.46) would satisfy

where

Equation (12.60a) shows that for fixed j theare the control points of a spline that interpolates the column of pointsand    equation (12.60b) shows that for fixed i theare the control points of a spline that interpolates the row of points This means that our interpolation problem can be solved in two stages using results from Section 11.5.5.

(1) First, solve the curve interpolation problem for each column of the array of pointsThis will give us cubic B-spline curveswith knots vj and control points Note that the solutions are based on the same tridiagonal matrix shown in equation (11.111), which means that the LU-decomposition of that matrix which is used to solve that system of equations is done only once.

(2) Next, do a curve interpolation on the rows of the array of points rsj to get the desired control points qst.

Of course, like in the curve case, one is not given the knots in practice. Unfortunately, things get more complicated here because we have to produce one set of knots u; for all of the curves p(u,vj) with fixed vj, j = 0, . . . n, and similarly for the vj. One typically uses some sort of averaging process, but that may not work very well if our data is not well spaced. See [PieT95] or [Fari97] for a much more thorough discussion. [PieT95] also discusses of interpolation of curve networks.

Data sets are not always rectangular. For example, one might have gotten rows of unequal number of data points from a sampling of slices of an object. One approach for this case is to use spline curves that interpolate the rows and then use a skinning surface (see Section 14.7) for these curves for our interpolating surface. One potential problem is that the number of column control points might get very large. An approach that alleviates this problem can be found in [PieT00].

Cyclide Surfaces

This section discusses one final class of surfaces that can be defined by equations, namely, the cyclides. See Figure 12.21. Interest in cyclides has waxed and waned over time. In 1982 R.R. Martin ([Mart82]) showed that they were useful in CAGD and since then interest in these surfaces has revived. They have proved especially useful for certain blending operations. We shall describe a few such applications in Section 15.6. In this section we shall discuss a few of their properties relevant to CAGD. We can only present a brief overview. More details can be found in [ChDH89], [Prat90], and [Boeh90]. Another good reference is [KraM00]. Throughout this section, the term “cyclide” will mean “Dupin cyclide.” Only at the end will we make a few comments about a more general related class of surfaces also called cyclides.

Cyclides are defined in Section 9.13 in [AgoM04] by means of geometric constructions that make it easier to deduce some of their geometric properties, but for computation purposes it is useful to have both a parametric and an implicit definition. We give such definitions for central cyclides whose spine curves are an ellipse and hyperbola and which are in standard position as shown in Figure 12.22. More precisely, we assume that the ellipse E and hyperbola H with branches H1 and H2 are defined by equations

Figure 12.21. A central ring cyclide.

Figure 12.22. A central cyclide in standard position.

Figure 12.23. Projections of the central cyclide in Figure 12.22.

and

respectively. In Figure 12.22 the cyclide is then the set of points traced out by the end B of a taut string of fixed lengththat    is tied to the focus A of the

ellipse and touches the ellipse at its points P. The line L through P and B would meet the hyperbola in a point Q. Let us write the length L in the formThen the intersection of the cyclide with the two planes z = 0 and y = 0 is shown in Figure 12.23. In both cases we get two circles with radii that are simple functions of a, c, and k. Another way of thinking of the cyclide is as the envelope of spheres with centers on the two conics. Looking again at Figure 12.22, the spheres in question would have radius PB if the sphere is centered on a point P of the ellipse and radius QB if it is centered on a point Q of the hyperbola.

Theorem. The central cyclide with the curves defined in (12.61) as its focal curves has a parameterization

where

and is defined by the equation

Proof. See [Fors12]. We shall only sketch a derivation of the parameterization in (12.62), which can also be found in [Gray98] or [Boeh90]. Let us parameterize the points P on the ellipse E and points Q on the hyperbola H by

One shows that

In fact, the signed quantities a and β are such that B can be expressed in barycentric form as

If we express all the variables in this representation of B in terms of Θ and ψ, we will get the formulain equation (12.62).

Theorem 12.13.1 makes it easy to work with a ring central cyclide. Its intersection with the planes z = 0 and y = 0 determine it completely. Therefore, one can use these cross-sections to visualize the surface and manipulating it is simply a matter of changing the values of a, c, and k. Also, equation (12.63) shows that the central cyclide is a fourth-degree surface. Parabolic cyclides are surfaces of degree three.

Here are a few more details about cyclides. There is a natural two-level geometric classification of cyclides (see [Boeh90] and [ChDH89]). At the top level there is the division of cyclides into central, parabolic, revolute, or degenerate cyclides depending on whether their spines are central conics, parabolas, straight lines and circles, or degenerate conics. Each of these types of cyclides can be further subdivided into three subtypes. We describe that subdivision in the case of central cyclides. Assume that the coordinate system is again chosen so that the cyclide is in standard position as shown in Figure 12.22.

Definition. The central cyclide is called a ring cyclide ifIt is called a

horned cyclide ifIt is called a spindle cyclide

Visually, a horned cyclide looks like two crescent-shaped solids that meet at their pinched points. A spindle cyclide has two pinch points at which the two parts of the entire surface meet with one part looking like a spindle inside the other. Ring cyclides, such as the one shown in Figure 12.21, are the easiest to draw because they do not have any of these degeneracies. Another way to describe these subtypes is in terms of two important values

Let Ls be the line in the x-y plane that is parallel to the y-axis and passes through the point (s,0,0) on the x-axis. Let Lt be the line in the x-z plane that is parallel to the z-axis and passes through the point (t,0,0) on the x-axis. We will have a ring cyclide if Ls does not intersect the focal ellipse E and Lt does not intersect the focal hyperbola H. We will have a horned cyclide if Ls intersects the ellipse E and a spindle cyclide if Lt intersects the hyperbola H. The lines Ls and Lt are called the characteristic lines of the cyclide ([ChDH89]).

Some properties of cyclides that make them attractive to CAGD are (see [Prat90]):

(1)  Each curvature line is a circle and cyclides are the only fourth-degree surfaces whose curvature lines are circles. The curvature lines split into two families similar to what happens in the case of a torus.

(2) The planes of each family of curvature lines meet in a line.

(3) One gets offset surfaces for a cyclide by changing the parameter k. Furthermore, the offset of a cyclide is a cyclide.

(4) For each curvature line, the angle between the principal normal of that curve and the surface normal is constant. Hence there is a right circular cone tangent to any circular curvature line of the cyclide.

(5)The inversion in a sphere of a cyclide with respect to a point not on it is again a cyclide.

One can show that the change of parameters

produces a rational biquadratic parameterization of the cyclide. The lines of constant u and v correspond to lines of curvature, namely circles. If we call a region in a cyclide bounded by lines of curvature a principal cyclide patch, then we can use the rational parameterization in u and v to define a Bezier parameterization for such a patch. See [Mart82], [MaPS86], [Prat90], [Boeh90], [DuMP93], [Prat95], and [KraM00]. This is very useful for representing cyclides in a CAGD program. One factor restricts the principal cyclide patch, namely, its four corners lie on a circle. This means that once one has picked two adjacent sides of a patch one has only one degree of freedom to pick the fourth corner since it must lie on the circle determined by the other three. One can also define triangular Bezier patches ([AlbD97]). Conditions for obtaining composite cyclide patches that join with G1 continuity are discussed in [KraM00].

For cyclide intersections see [MaPS86] and [John93].

We already mentioned at the beginning of this section that cyclides are useful in blending. They are also useful in controlling the fairness of a surface. The advantage of cyclides is that they provide a manageable representation of a larger piece of a surface. Tensor product Bezier or B-spline patches deal with smaller pieces. This has led to a search for other general fourth-degree algebraic surfaces that might be useful in CAGD. One such class of surfaces are the supercyclides that are projective images of Dupin cyclides. These are special cases of so-called double-Blutel surfaces. For more on these generalizations see [Dege94], [Prat96], and [Prat97]. A unified theory of supercyclides is described in [Dege98].

Subdivision of Surfaces

Like in the case of curves, being able to subdivide surfaces is important in a variety of applications. Subdivision problems come in two flavors. In one case we have a parametric surface and in the other we have no parameterization but simply a polygonal surface defined by an arbitrary (not necessarily rectangular) grid of points. This section makes a few comments about the first case. The second is dealt with in Section 12.17.

At one level, subdividing a parametric surface simply amounts to subdividing its domain. On the other hand, if we are dealing with a surface defined by control points or control points and knots, then the more interesting question is how one can add new control points or knots. The tensor product surface case is quite straightforward and reduces to subdividing curves in the u- and v-direction and hence is basically a onedimensional problem. The triangular surface case is more involved. Blossoms come in very handy here. One way to subdivide a triangle is shown in Figure 12.24. We add new vertices at the midpoints of the edges. The four new triangles give rise to four new triangular nets. The main issue is to do computations with respect to the smaller triangles as efficiently as possible by judicious use of the de Casteljau algorithm. We refer the interested reader to [Gall00]. There are other ways to subdivide triangles and [Fili86] suggests that the choice of subdivision should be made adaptively.

Figure 12.24. Subdividing triangular domains.