CSCE 441 Lecture 30

« previous | Friday, April 4, 2014 | next »

Pyramid Algorithm for Bezier Curves

p0
     (1-t)*p0 + t*p1
p1                    (1-t)*((1-t)*p0 + t*p1) + t*((1-t)*p1 + t*p2)
     (1-t)*p1 + t*p2                                                 (1-t)*((1-t)*((1-t)*p0 + t*p1) + t*((1-t)*p1 + t*p2)) + t*((1-t)*((1-t)*p1 + t*p2) + t*((1-t)*p2 + t*p3))
p2                    (1-t)*((1-t)*p1 + t*p2) + t*((1-t)*p2 + t*p3)
     (1-t)*p2 + t*p3
p3

def bezier(pts, t)
  if pts.length == 1
    return pts[0]
  newPts = []
  for i in (0..pts.length)
    newPts << (1-t)*pts[i] + t*pts[i+1]
 
  // ...

Subdividing Bezier Curves

Divide a bezier curve into two curves such that the union of the two curves is equal to the total curve.

• Take left side of pyramid algorithm for left curve
• Take right side of pyramid algorithm for right curve

Let $t=\frac{1}{2}$, then pyramid just averages points! The last remaining point represents the middle point on curve.

Adaptive Rendering =

• If control polygon is close to a line, draw control polygon
• otherwise, subdivide and recur

Applications: Intersection

Given two Bezier curves, determine if and where they intersect

Better than newton's method in that it will find all intersection points between parameter values for $t$

1. check if convex hulls intersect
2. if not, no intersection
3. if both convex hulls can be approximated with a straight line (like in adaptive rendering), intersect lines and return intersection.
4. Otherwise, subdivide and recur.

Application: Font Rendering

On-curve points: whenever curve should be sharp or a point that should be on the curve Off-curve points: helps with smoothing

• Put On-curve point between every pair of off-curve point
• Put Off-curve point between every pair of on-curve point

Define bezier curve between On-Off-on triples

B-Spline Curves

Collection of polynomials that meet together smoothly

Local control: changing a single point doesn't affect the entire curve

Represented as a list of points

Lane-Reisenfeld Subdivision Algorithm

• Linearly subdivide the curve by inserting the midpoint on each edge.
• Perform averaging by replacing each new edge by its midpoint $d$ times (throwing away the original endpoints)

$d$ represents degree of resulting polynomial

Subdividing repeatedly causes edges to converge to

Smoothness rating (C + degree of polynomial)

• C0: discontinuities at polynomail junctions
• C1: 1st derivative continuous
• C2: preferred smoothness: normals will also be smooth

Properties

• Curve lies within convex hull of control points
• Variation diminishing: Curve wiggles no more than control polygon (also a property of Bezier curves, but not of Lagrange curves)
• Influence of one control point is bounded.
• Degree of curve increases by one with each averaging step.
• Smoothness increases by one with each step.