Unformatted text preview:

Lecture 24: Blending Functions:An Alternative Approach to Freeform Curves and SurfacesHe made also bases 2 Chronicles 4:141. Blending FunctionsTill now we have taken an algorithmic approach to freeform curves and surfaces: Neville’s algorithm for Lagrange interpolation, de Casteljau’s algorithm for Bezier approximation. In this lecture we are going to derive explicit formulas for these curve and surface schemes.Both Neville’s algorithm and de Casteljau’s algorithm have the generic triangular structure depicted in Figure 1: the control points are placed at the base of the triangle, and points on the curve emerge at the apex of the triangle. A simple inductive argument shows that the curve that emerges at the apex is an affine combination of the control points at the base. Thus if € D(t) is the curve that emerges at the apex of the triangle with the control points € P0,K,Pn, at the base, then there are functions € D0(t),K, Dn(t) such that€ D(t) = Dk(t)Pkk∑. (1.1)012D(t) = Dk(t)k∑Pk***P0P1P2P3**Figure 1: The generic up recurrence for evaluating points on a curve. The control points € P0,K,Pn are placed at the base of the diagram and points on the curve € D(t) = Dk(t)Pkk∑ emerge at the apex of the triangle. The functions € D0(t),K, Dn(t) that multiply the control points are the blending functions for the curve and depend on the labels along the arrows. To keep the algorithm generic, we have not specified these labels along the arrows. Here we illustrate the cubic case.The functions € D0(t),K, Dn(t) that multiply the control points are called blending functions because these functions blend together the control points to form a smooth curve. These blending functions depend only on the labels along the arrows and not on the particular control points. All the properties of a particular curve scheme can be derived by studying the properties of the associated blending functions. In this lecture we will derive the blending functions for the Lagrange and Bezier schemes, and we will show how the geometric properties of the corresponding curve and surface schemes depend on the algebraic properties of their associated blending functions.There are several ways to compute the blending functions € D0(t),K, Dn(t). Since the function € Dk(t) is the coefficient of the control point € Pk.€ Dk(t) = the sum over all paths from € Pk at the base to € D(t) at the apex of the triangle. (1.2)where a path means the product of the labels on all the arrows along the path. Though at first glance Equation (1.2) may appear daunting, in Section 2 we shall show how to apply this equation to compute explicit formulas for the blending functions of Lagrange and Bezier curves.Perhaps more naturally we can also compute € Dk(t) directly from the evaluation algorithm for € D(t) by setting € Pk=1 and € Pj= 0 for € j ≠ k, since in this case by Equation (1.1)€ D(t) = Dj(t)Pjj∑ = Dk(t).We illustrate this algorithm in Figure 2.012D1(t)***0100**Figure 2: The up recurrence for computing one of the blending functions. A one is placed at the kth position and zeros are placed everywhere else at the base of the triangle. Since € Dk(t) is the sum over all paths from € Pk at the base to € D(t) at the apex of the triangle, the function € Dk(t) emerges at the apex of the triangle. Here we illustrate the algorithm for computing € D1(t) in the cubic case. 2Alternatively, we can compute the blending functions by observing that the sum over all paths from the kth position at the base to the apex of the triangle is the same as the sum of all paths from the apex to the kth position at the base of the triangle. Thus€ Dk(t) = the sum over all paths from the apex to the kth position at the base of the triangle. (1.3)Therefore we can compute all the blending functions simultaneously by placing a 1 at the apex of the triangle and running the recurrence down instead of up by reversing all the arrows in the diagram. Since the kth blending function is the sum of all paths from the apex to the kth position at the base, all the blending functions emerge at the base of the triangle (see Figure 3).0121***D0(t)**D1(t)D2(t)D3(t)Figure 3: The down recurrence for the blending functions. Place 1 at the apex of the triangle and run the evaluation algorithm in reverse by reversing all the arrows. The blending functions € D0(t),K, Dn(t) now emerge at the base of the triangle. Again we illustrate the cubic case.The preceding algorithms work generically for any recursive curve scheme. With these general ideas in hand, we are now ready to find explicit formulas for the blending functions of Lagrange and Bezier curves and surfaces.2. The Lagrange and Bernstein Basis FunctionsSince both Lagrange and Bezier curves and surfaces are polynomial curves and surfaces, the blending functions for these schemes are polynomial functions. For a fixed degree n, these polynomial blending functions turn out to be polynomial bases -- they are linearly independent and they span the space of all polynomials of degree n. The blending functions for Lagrange interpolation are called the Lagrange basis functions, and the blending functions for Bezier approximation are called the Bernstein basis functions. Here we shall derive explicit formulas for each of these sets of basis functions. 32.1 Lagrange Basis Functions. Before we can derive explicit formulas for the Lagrange basis functions, we need to fix our notation. Let € Lkn(t | t0,...,tn) denote the kth Lagrange basis function of degree n for the nodes € t0,K,tn. (Recall that the nodes € t0,K,tn are the values of t where the interpolation occurs.) Since the nodes € t0,K,tn are fixed, the Lagrange basis functions € Lkn(t | t0,...,tn), € k = 0,K,n, are polynomial functions in the parameter t; the nodes are simply there to remind us that if we change the nodes, the functions € Lkn(t | t0,...,tn) will also change.We can use Equation (1.3) together with Neville’s algorithm to derive an explicit formula for € Lkn(t | t0,...,tn). By Equation (1.3) € Lkn(t | t0,...,tn) is the sum over all paths from the apex to the kth position at the


View Full Document

Rice COMP 360 - Lecture Notes

Documents in this Course
Radiosity

Radiosity

42 pages

Radiosity

Radiosity

22 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?