1.3.5 Algorithms for Bézier curves

Next: 1.3.6 Bézier surfaces Up: 1.3 Bézier curves and Previous: 1.3.4 Definition of Bézier Contents Index

1.3.5 Algorithms for Bézier curves

Evaluation and subdivision algorithm: A Bézier curve can be evaluated at a specific parameter value

and the curve can be split at that value using the de Casteljau algorithm [175], where the following equation

$\displaystyle {\bf b}_i^k(t_0) = (1-t_0){\bf b}_{i-1}^{k-1} + t_0{\bf b}_i^{k-1}, \;\;\;k=1,2,\ldots,n,\;\;\;i=k,\ldots,n\;,$

(1.44)

is applied recursively to obtain the new control points. The algorithm is illustrated in Fig. 1.6, and has the following properties:

The values ${\bf b}_i^0$ are the original control points of the curve.
The value of the curve at parameter value is ${\bf b}_n^n$ .
The curve is split at parameter value and can be represented as two curves, with control points $({\bf b}_0^0$ , ${\bf b}_1^1$ , $\ldots$ , ${\bf b}_n^n)$ and $({\bf b}_n^n,\;{\bf b}_n^{n-1}, \ldots,\;{\bf b}_n^0)$ .

**Figure 1.6:** The de Casteljau algorithm
$\begin{figure}\hspace{0.8cm} \centerline{\psfig{figure=fig/deCast.ps,height=2.3... ...ne{\psfig{figure=fig/decas_graph.eps,height=3.0in}} \vspace{-2cm}\end{figure}$

Continuity algorithm: Bézier curves can represent complex curves by increasing the degree and thus the number of control points. Alternatively, complex curves can be represented using composite curves, which can be formed by joining several Bézier curves end to end. If this method is adopted, the continuity between consecutive curves must be addressed.

One set of continuity conditions are the geometric continuity conditions, designated by the letter with an integer exponent. Position continuity, or continuity, requires the endpoints of the two curves to coincide,

$\displaystyle {\bf r}^{a}(1) = {\bf r}^{b}(0)\;.$

(1.45)

The superscripts denote the first and second curves. Tangent continuity, or

continuity, requires

continuity and in addition the tangents of the curves to be in the same direction,

$\displaystyle \dot{\bf r}^{a}(1) = \alpha_1{\bf t}\;,$			(1.46)
$\displaystyle \dot{\bf r}^{b}(0) = \alpha_2{\bf t}\;,$			(1.47)

where ${\bf t}$ is the common unit tangent vector and $\alpha_1$ , $\alpha_2$ are the magnitude of $\dot{\bf r}^{a}(1)$ and $\dot{\bf r}^{b}(0)$ .

continuity is important in minimizing stress concentrations in physical solids loaded with external forces and in helping prevent flow separation in fluids.

Curvature continuity, or continuity, requires continuity and in addition the center of curvature to move continuously past the connection point [116],

$\displaystyle \ddot{\bf r}^{b}(0) = \left(\frac{\alpha_2}{\alpha_1}\right)^2\ddot{\bf r}^{a}(1) + \mu \dot{\bf r}^{a}(1)\;,$

(1.48)

where $\mu$ is an arbitrary constant.

continuity is important for aesthetic reasons and also for helping prevent fluid flow separation.

More stringent continuity conditions are the parametric continuity conditions, where continuity requires the th derivative (and all lower derivatives) of each curve to be equal at the joining point. In other words,

$\displaystyle \frac{d^k{\bf r}^{a}(1)}{dt^k} = \frac{d^k{\bf r}^{b}(0)}{dt^k}\;.$

(1.49)

Let us assume that the global parameter , associated with the - segment of a composite degree Bézier curve with local parameter ( $0\leq u_i \leq 1$ ), runs over the interval , $t_{i+1}]$ . Then the - segment of a composite Bézier curve is given by:

$\displaystyle {\bf r}_i(t) = \sum^n_{j=0}{\bf b}_{ni+j}B_{j,n}(u_i)\;,$

(1.50)

where the global parameter

and the local parameter

are related by,

$\displaystyle 0\leq u_i = \frac{t-t_i}{t_{i+1} - t_i}\leq 1\;.$

(1.51)

If we denote $h_i = t_{i+1} - t_i$ , the

and

continuity conditions for the

-th and

+1-th segments of the composite Bézier curve can be stated as [455,175]:

$\displaystyle h_{i+1}\left({\bf b}_{ni}-{\bf b}_{ni-1}\right) = h_{i}\left({\bf b}_{ni+1}-{\bf b}_{ni}\right)\;,$

(1.52)

and

$\displaystyle {\bf b}_{ni-1}+\frac{h_{i+1}}{h_i}({\bf b}_{ni-1}-{\bf b}_{ni-2}) = {\bf b}_{ni+1}+\frac{h_i}{h_{i+1}}({\bf b}_{ni+1}-{\bf b}_{ni+2})\;.$
$\displaystyle \;$			(1.53)

Figure 1.7 illustrates the connection of two cubic Bézier curve segments at $t=t_{i+1}$ .

Degree elevation: The degree elevation algorithm permits us to increase the degree of a Bézier curve from

and the number of control points from

without changing the shape of the curve. The new control points ${\bf b}_i^{n+1}$ of the degree

curve are given by

$\displaystyle {\bf b}_i^{n+1}= \frac{i}{n+1}{\bf b}_{i-1}^n + \left(1-\frac{i}{n+1}\right){\bf b}_{i}^n, \;\;\;i=0,\ldots, n+1\;,$

(1.54)

where ${\bf b}_{-1}^n={\bf b}_{n+1}^n= {\bf0}$ . The degree elevation algorithm for a Bézier curve from degree

is given by [106]:

$\displaystyle {\bf b}_{i}^{n+r} = \sum_{j=max(0,i-r)}^{min(n,i)}\frac{\begin{pm... ...in{pmatrix}n+r \cr i \cr\end{pmatrix}}{\bf b}_{j}^n,\quad i = 0,1,\cdots,n+r\;.$

(1.55)

**Figure 1.7:** Continuity conditions
$\begin{figure}\centerline{\psfig{figure=fig/continuity.ps,height=2.3in}}\end{figure}$

Next: 1.3.6 Bézier surfaces Up: 1.3 Bézier curves and Previous: 1.3.4 Definition of Bézier Contents Index

December 2009