Question: Write short note on B-Spline curves.
0

Subject: Computer Graphics

Topic: Three Dimensional Object Representations,Geometric Transformations and 3D Viewing

Difficulty: High

cg(14) • 3.5k views
 modified 10 months ago  • written 2.0 years ago by vbadbe • 70
0
• A B-spline of order n is a piecewise polynomial function of degree $\lt n$ in a variable x. It is defined over a domain t 0 ≤ x ≤ tm, m = n.
• The points where x = t j are known as knots or break-points. The number of internal knots is equal to the degree of the polynomial if there are no knot multiplicities.
• The knots must be in ascending order. The number of knots is the minimum for the degree of the B-spline, which has a non-zero value only in the range between the first and last knot.
• Each piece of the function is a polynomial of degree $\lt n$ between and including adjacent knots. A B-spline is a continuous function at the knots. When all internal knots are distinct, its derivatives are also continuous up to the derivative of degree n-1.
• If internal knots are coincident at a given value of x, the continuity of derivative order is reduced by 1 for each additional knot.

For any given set of knots, the B-spline is unique, hence the name, B being short for Basis. The usefulness of B-splines lies in the fact that any spline function of order n on a given set of knots can be expressed as a linear combination of B-splines:

$S_{n,t}(x) = \sum_i a_i B_{i,n} (x)$

This follows from the fact that all pieces have the same continuity properties, within their individual range of support, at the knots.[3] Expressions for the polynomial pieces can be derived by means of the Cox-de Boor recursion formula

$B_{i,1}(x) :=\begin{cases} 1 & if \hspace{0.2cm} t_i \leq x \lt t_{i + 1} \\ \ 0 & \text{otherwise}\end{cases} \\ B_{i,k}(x) := \frac{x - t_i}{t_{i =k-1}} B_{i, k-1}(x) + \frac{t_{i+k}-x}{t_{i+k}-t_{i+1}} B_{i+1, k-1}(x)$

That is, $B_{j,1}(x)$ is piecewise constant one or zero indicating which knot span x is in (zero if knot span j is repeated). The recursion equation is in two parts:

$\frac{x - t_i}{t_{i+k-1} - t_{i}}$

ramps from zero to one as x goes from $t_i$ to $t_{i+k-1}$ and

$\frac{t_{i+k} - x}{t_{i+k} - t_{i+1}}$

ramps from one to zero as x goes from ti+1 to $t{i+k}$ . The corresponding Bs are zero outside those respective ranges. For example, Bi, 2(x) is a triangular function that is zero below x=ti, ramps to one at $x=t_{i+1}$ and back to zero at and beyond $x=t_{i+2}$. However, because B-spline basis functions have local support, B – splines are typically computed by algorithms that do not need to evaluate basis functions where they are zero, such as de Boor’s algorithms.

 modified 2.0 years ago by Juilee ♦ 2.1k written 2.0 years ago by vbadbe • 70
0

B-Spline curves:-

Spline Representation:-

To produce a smooth curve through a designated set of points, a flexible strip called spline is used. Such a spline curve can be mathematically described with a piecewise cubic polynomial function whose first and second derivatives are continuous across the various curve sections. We can specify a spline curve by giving a set of coordinate positions, called control points, which indicates the general shape of the curve. When polynomial sections are fitted so that the curve passes through all control points, as shown in the Fig. 18 (a), the resulting curve is said to interpolate the set of control points. On the other hand, when the Polynomials are fitted to the path which is not necessarily passing through all control points, the resulting curve is said to approximate the set of control points. This is illustrated in the Fig. 18 (b).

Spline Specifications:-

There are three basic ways of specifying spline curves:

• we can state the set of boundary conditions that are imposed on the spline

• we can state the matrix that characteristics thy spline or

• we can state the set of blending functions that calculate the positions along the curve path by specifying combination of geometric constraints on the curve.

A curve generated by using the vertices(control points) of a defining Polygon is dependent on some interpolation or approximation scheme to establish the relationship between the curve and the polygon. This scheme is provided by the choice of basis function. The Bezier curve produced by the Bernstein basis function has a limited flexibility. First the number of specified polygon vertices fixes the order of the resulting Polynomial which defines the curve. The second limiting characteristic is that the value of the blending function is nonzero for all parameter values over the entire curve. Due to this change in one vertex, changes the entire curve and this eliminates the ability to produce a local change within a Curve.

There is another basis function, called the B-spline basis, which contains the Bernstein basis as a special case. The B-spline basis is nonglobal. It is nonglobal because each vertex Bi is associated with a unique basis function. Thus, each vertex affects the shape of the curve only over a range of parameter values where its associated basis function is nonzero. The B-spline basis also allows the order of the basis function and hence the degree of the resulting curve is independent on the number of vertices. It is possible to change the degree of the resulting curve without changing the number of vertices of the defining polygon.

If P(u) be the position vectors along the curve as a function of the parameter u, a B-spline curve is given by

where the Bi are the position vectors of the n + 1 defining polygon vertices and the N i, k are the normalized B-spline basis functions for the ith normalized B-spline basis function of order k, the basis function Ni, k(u) are defined as

The values of xi are the elements of a knot vector satisfying the relation Xi ≤ Xi +1.The parameter u varies from to umin to umax, along the curve P(u). The choice of knot vector has a significant influence on the B-spline basis functions Ni, k(u) and hence on the resulting B-spline curve. There are three types or knot vector uniform, open uniform and nonuniform. In a uniform knot vector, individual knot values are evenly spaced. For example,

[0 1 2 3 4 ]

For a given order k, uniform knot vectors give periodic uniform basis functions for which

An open uniform knot vector has multiplicity of knot values at the ends equal to the order k of the B-spline basis function. Internal knot values are evenly spaced. Examples are,

k = 2[0 0 1 2 3 3]

k = 3[0 0 0 1 2 3 3 3]

k = 4[0 0 0 0 1 2 2 2 2]

Generally, an open uniform knot vector is given by,

Xi = 0 1 ≤ i ≤ k

Xi = i – k k+1 ≤ i ≤ n+1

Xi = n – k + 2 n+2 ≤ i ≤ n+k+1

The curves resulted by the use of open uniform basis function are nearly like Bezier curves. In fact, when the number of defining polygon vertices is equal to the order of the B-spline basis and an open uniform knot vector is used, the B-spline basis reduces to the Bernstein basis. Hence, the resulting B-spline curve is a Bezier curve.

Properties of B-spline curve:-

1. The sum of the 13-spline basis functions for any parameter value u is 1.

1. Each basis function is positive or zero for all parameter values, i.e., N i ,k ≥ 0.

2. Except for k = 1 each basis function has precisely one maximum value.

3. The maximum order of the curve is equal to the number of vertices of defining polygon.

4. The degree of B-spline polynomial is independent on the number of vertices of defining polygon (with certain limitations).

5. B-spline allows local control over the curve surface because each vertex affects the shape of a curve only over a range of parameter values where its associated basis function is nonzero.

6. The curve exhibits the variation diminishing property. Thus the curve does not oscillate about any straight line move often than its defining polygon.

7. The curve generally follows the shape of defining polygon.

8. Any affine transformation can be applied to the curve by applying it to the vertices of defining polygon.

9. The curve line within the convex hull of its defining polygon.