Next: Bernstein Basis Functions Up: Splines Previous: Splines

# Constructing Curve Segments

Linear blend:
• Line segment from an affine combination of points

• Quadratic segment from an affine combination of line segments

Cubic blend:
• Cubic segment from an affine combination of quadratic segments

• The pattern should be evident for higher degrees.

Geometric view (deCasteljau Algorithm):
• Join the points by line segments
• Join the t : (1-t) points of those line segments by line segments
• Repeat as necessary
• The t : (1-t) point on the final line segment is a point on the curve
• The final line segment is tangent to the curve at t

Expanding Terms (Basis Polynomials):
• The original points appear as coefficients of Bernstein polynomials

• The Bernstein polynomials of degree n form a basis for the space of all degree-n polynomials

Recursive evaluation schemes:
• To obtain curve points:

• The generated points are the deCasteljau points
• To obtain basis polynomials:

where when r<0 or r>s

Recursive triangle diagrams (upward):
Computing deCasteljau points
• Each node gets the affine combination of the two nodes entering from below
• Leaf nodes have the value of their respective points

• Each node gets the sum of the path products entering from below

Recursive triangle diagrams (downward):
Computing Bernstein (basis) polynomials
• Each node gets the affine combination of the two nodes entering from above
• Root node has value 1
• For other nodes, missing entries above count as zero
• Each node gets the sum of the path products entering from above

Next: Bernstein Basis Functions Up: Splines Previous: Splines

CS488/688: Introduction to Interactive Computer Graphics
University of Waterloo
Computer Graphics Lab

cs488@cgl.uwaterloo.ca