Piecewise Curves

interpolate - to alter or corrupt by the insertion of new or foreign matter

Definition 2.1   A stroke is said to be scale independent if it still appears to be smooth after its scale is changed.

Our stated goal is to reproduce an image with a set of strokes approximating the original edges in the source. Further, we would like to do this in a way that is scale independent. This means that any solution where an inherently curved stroke is approximated with straight lines is unacceptable. We need a reasonable way to use real curves to represent strokes.

Definition 2.2   A curve is a mapping

$$\phi:\mathbb{R} \rightarrow \mathbb{R}^{n},$$   where$$\ \phi(t) = (\phi_1(t), \hdots, \phi_n(t))$$

One can think about a curve as a straight line which has been stretched and deformed by the curve function $\phi$. Each component $\phi_i(t)$ of the curve function is typically (and this thesis is no exception) a polynomial of the form $a_{m}t^{m} + \hdots + a_{1}t+a_{0}$. Further, since each component can be dealt with independently, this chapter deals only with curves in $\mathbb{R}$. The discussion generalizes to higher dimensions.

With extremely high-order polynomials it is possible to interpolate every single point in the stroke we'd like to draw. This is a bad idea for a couple of reasons. First, these polynomials can be difficult to work with; changing one part of the curve will have a large impact on the shape of the rest of the curve. Second, interpolation of every single edge pixel isn't going to give nice looking strokes. Instead, interpolating each edge pixel would result in strokes that take many turns -- it won't look nice. Figure 2.1 shows what might happen as a result of trying to interpolate every point.

A different approach, commonly taken in computer graphics applications, is to represent smooth curving paths with small degree polynomial segments. Each polynomial is defined to exist for values of $t$ on the interval $[0,1]$. Where one polynomial segment stops another one begins. It is standard practice to work with cubic polynomials. These polynomials are the smallest polynomial functions capable of being $\mathcal{C}^2$ and yet they are still relatively easy to work with.

Figure 2.1: A set of edge pixels interpolated perfectly. The picture on the left is displayed at 10x magnification.

center

        

Bezier Curves

curve - trick, deception

Figure 2.2: A Bezier curve.

center

Cubic polynomials are of order four, so that four values, $a_3$, $a_2$, $a_1$, and $a_0$, define a unique cubic polynomial $\alpha_{i,j}(t) = a_3t^3+a_2t^2+a_1t+a_0$, where $\alpha_{i,j}(t):[0,1]\rightarrow\mathbb{R}$ is the $j$'th segment of $\phi_i(t)$. This isn't very useful because the $a_i$'s don't have any obvious relation to the points we're trying to represent in a stroke. The parametric function $\alpha_{i,j}$ can be written as

$$\alpha_{i,j}(t) = [ t^3 \ t^2 \ t \ 1 ] \left[ \begin{matrix}a_3 \\ a_2 \\ a_1 \\ a_0 \end{matrix} \right] \qquad \alpha_{i,k}'(t) = [ 3t^2 \ 2t \ 1 \ 0 ] \left[ \begin{matrix}a_3 \\ a_2 \\ a_1 \\ a_0 \end{matrix} \right]$$ (1)

Bezier proposed that instead of specifying the four $a_i$ values directly, we should instead choose four control points, denoted $p_0$, $p_1$, $p_2$, and $p_3$, to specify the end points of the curve segment ($p_0$ and $p_3$) and the tangent at the end points ($p_1$ and $p_2$, combined with $p_0$ and $p_3$ respectively). Then for any cubic function, we can write our four control points $p_0 \hdots p_3$ as the following system of equations.

$$p_0 = a_0$$

$$3(p_1 - p_0) = a_1$$

$$3(p_3 - p_2) = a_1 + 2a_2 + 3a_3$$

$$p_3 = a_0 + a_1 + a_2 + a_3$$

Let $P = \left[ p_0 \ p_1 \ p_2 \ p_3 \right]^T$, and let $A$ denote the column vector of coefficients $a_0 \hdots a_3$. Given the above system of equations and a little bit of algebra, $P$ can be written in the form $P = MA$ as follows.

$$\left[ \begin{matrix} p_0 \\ p_1 \\ p_2 \\ p_3 \end{matrix}\right... ...ix}\right] \left[ \begin{matrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{matrix}\right]$$

By inverting $M$, (from now on, $M^{-1}$ will be denoted $M_B$, the Bezier control matrix) we can now solve for the coefficients $\{ a_i \}$ in terms of the control points $\{p_i \}$.

$$\left[ \begin{matrix} \hphantom{-}1 & \hphantom{-}0 & \hphantom{-... ...x}\right] = \left[ \begin{matrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{matrix}\right]$$

Based on this result, the cubic polynomial can be written as follows.

$$\begin{split} \alpha_{i,j}(t) &= p_0(1-t)^3 + p_1(3t -6t^2+3... ..._2) t^2 + 9 (p_0 \cdot p_1 \cdot p_2 \cdot p_3) t^3 \end{split}$$

While it is true that every cubic polynomial is $\mathcal{C}^2$, curves consisting of cubic Bezier segments are not guaranteed to have this property at places where the curve pieces join. At these points, the only guarantee is that of $\mathcal{C}^0$ continuity -- that is to say that the curve is continuous but not differentiable. One way to have $\mathcal{C}^2$ continuity everywhere is to use a single Bezier segment for the entire stroke. Unfortunately, four control points (i.e. a single segment of a cubic curve) do not provide a realistic amount of flexibility. It is possible to do a little bit better by remembering that two of the control points in each segment are dedicated to tangent information at the endpoints. Figure 2.3 shows how to obtain $\mathcal{C}^1$ continuity at join points -- if two curves are defined by $p_0,\hdots, p_3$ and $p_3, \hdots, p_6$ and joined at $p_3$, then the tangent at $p_3$ needs to be the same in both directions. This can be accomplished by making $p_2$, $p_3$, and $p_4$ colinear. Likewise, piecewise curves composed of Bezier segments can be forced to have $\mathcal{C}^2$ continuity everywhere if $p_1, \hdots, p_5$ are colinear. Unfortunately, this leaves very little flexibility for defining curve segments -- unless the original goal was a set of connected piecewise cubic line segments which gets mildly interesting near the endpoints. One possibility for achieving $\mathcal{C}^2$ continuity everywhere is to use polynomials of higher degree. A more common solution is described in the next section.

Figure 2.3: Two Bezier segments joined at $p_3$.

B-Splines

spline - a key that is fixed to one of two connected mechanical parts and fits into a keyway in the other

By starting over and choosing a different set of criteria for blending functions, it is possible to achieve $\mathcal{C}^2$ continuity even at the points where cubic curve segments join. A standard approach in computer graphics is the cubic B-Spline. As in the case of Bezier curves, each curve piece is defined by four control points. The difference this time is that any two connected segments share three of these control points. For example, a two-segment B-Spline consists of five control points, $\{ p_0, \hdots, p_4 \}$. In general, if deg $(\alpha_{i,j})$ is the degree of the curve, then an $n$-segment B-Spline is defined by deg$(\alpha_{i,j}) + n$ points.

There is one major drawback to using B-Splines over Bezier segments. While Bezier curves interpolate $p_0$ and $p_3$, B-Splines interpolate neither. In fact, it is much closer to the truth to say that the B-Spline segment determined by points $p_{i-2}, \hdots, p_{i+1}$ is only defined on some interval ``between'' $p_{i-1}$ and $p_i$. This is slightly unclear but hopefully Figure 2.4 will provide a reasonable illustration.

Figure 2.4: A B-Spline segment and its control points.

The most popular relations between the $\{ p_{i-2},\hdots,p_{i+1} \}$ and $\{a_0, \hdots, a_3 \}$ can be derived as follows. Given two curve segments $c_1(t)$ and $c_2(t)$ which join ``near'' $p_{i-1}$, not only must $c_1(1)=c_2(0)$, but also $c_1'(1) = c_2'(0)$. Further, because $c_1(t)$ and $c_2(t)$ share only the control points $p_{i-2}$, $p_{i-1}$, and $p_{i}$, any condition at $c_1(1)$ must be strictly dependent on only these three control points. As Angel [1] puts it, ``two conditions that satisfy this symmetry condition are''

$$c_1(1) = c_2(0) = a_0 = \frac{1}{6}(p_{i-2} + 4p_{i-1} + p_{i})$$

$$c_1'(1) = c_2'(0) = a_1 = \frac{1}{2}(p_{i} - p_{i-2})$$

Because a very similar set of conditions must also apply at $c_2(1)$, we can say that

$$c_2(1) = a_0 + a_1 + a_2 + a_3 = \frac{1}{6}(p_{i-1} + 4p_{i} + p_{i+1})$$

$$c_2'(1) = a_1 + 2a_2 + 3a_3 = \frac{1}{2}(p_{i+1} - p_{i-1})$$

These two sets of conditions give the following B-Spline control matrix, $M_S$.

$$M_S = \frac{1}{6} \left[ \begin{matrix} \hphantom{-}1 & \hphanto... ... \hphantom{-}0 \\ -1 & \hphantom{-}3 & -3 & \hphantom{-}1 \end{matrix}\right]$$

Figure 2.5: The four column vectors from $M_S$ expressed as functions.

Drawing Curves

Now that we know a little bit about these piecewise curves, we can talk about how to draw them. First note that any Bezier segment can be split into two at $\alpha_{i,j}(\frac{1}{2})$. Appropriate new control points can be found for each segment in order to rescale the parameter of the curve function so that each part is defined on $[0,1]$. Each of these new Bezier segments can then be divided into two smaller segments. By repeating this process the control points for the small segments begin to look more and more colinear. When the points are sufficiently colinear, the curve segment can be approximated with a line segment. This process is illustrated in Figure 2.6. In the illustration, a curve piece defined by $\{ p_0,\hdots,p_3 \}$ is split into two pieces with new control points $\{ p_0, \hdots, p_6 \}$.

Figure 2.6: One Bezier segment is divided into two.

The process of rendering B-Spline segments is similar. Due to the computational simplicity of recursive subdivision, it is most common to first convert each B-Spline segment to a Bezier segment. Finding the Bezier control points for a B-Spline segment is done as follows. Recall that $P = [ p_0 \ p_1 \ p_2 \ p_3 ]^T$ and that $A = [ a_0 \ a_1 \ a_2 \ a_3 ]^T$. Also recall that $M_B$ is the Bezier control matrix. Let $P_S$ be the column vector of B-Spline control points and let $P_B$ be the column vector of Bezier control points. Given $P_S$ and $P_B$ we have

$$M_{S} P_{S} = A = M_{B} P_{B} \implies M_{B}^{-1} M_{S} P_{S} = P_{B}$$

This equation states that a set of Bezier control coordinates can be produced by multiplying the column vector of B-Spline control points by the matrix $M_{B}^{-1}M_{S}$ as above.