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$

check if convex hulls intersect
if not, no intersection
if both convex hulls can be approximated with a straight line (like in adaptive rendering), intersect lines and return intersection.
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.