Computer Science 115 - Section 1 Fall 1998

Bezier curves: recursive drawing algorithm

• P(t)= (a +b*t + c*t*t, d+e*t+f*t*t) is quadratic in parametric form
• curve goes through points P1 and P2 in the Cartesian plane
• variable t goes from 0 to 1
• P1=P(0)=(a,d)
• P2=P(1)=(a+b+c,d+e+f)
• control point is a third point Pc in the Cartesian plane which determines the slopes of the curve at P1 and P2
• The tangent lines through Pi (i= 1 or 2) intersect at Pc

• tangent to the curve P(t) varies linearly in t (derivative of a quadratic is linear)
• intersection of tangent to the curve P(t) with the lines between Pi (i= 1 or 2) and Pc varies linearly in t
• tangent to the curve P(t) at midpoint (t=0.5) intersects the lines between Pi (i= 1 or 2) and Pc at their midpoints
• P(.5) = 0.5*Pc + 0.25*(P1 + P2)
• reduced representation for the two halves of the curve
• P(.5) can be used as a new delimiting point for the two halves of the the curve
• the midpoint of the lines between Pi (i= 1 or 2) and Pc are new control points

• Bezier representation for two halves of the curve:
• (P1, 0.5*Pc+0.25*(P1+P2), 0.5*(P1+Pc))
• (0.5*Pc+0.25*(P1+P2), P2, 0.5*(Pc+P2))
• stop the recursion when the distance between P1 and P2 is less than some number, say tol, of pixels (i.e., stop when the distance-squared is less than tol squared))
• draw a straight line between P1 and P2

Programming/homework assignment

• Define abstract data types R2 (for points (x,y) in the Cartesian plane) and RGB (for colors), and re-write your procedure (draw-line P1 P2 color) to work with these data types. The constructors should be make-R2 and make-RGB . Accessors should include
  • for RGB: r-val, g-val, b-val
  • for R2: x-coord, y-coord
  Use this to draw lines in a recursive algorithm to draw a Bezier quadratic curve as discussed in class. This requires defining operators
  • plus, minus (from R2 x R2 --> R2) which add and subtract two vectors component-wise
  • scalar-mult (from R1 x R2 --> R2) which multiplies a real number (a.k.a. scalar) times a vector, component-wise
  • length-squared (from R2 --> R1) which computes the Euclidean length squared of a vector
  Test it with the points P1=(0,0), P1=(100,0) and Pc=(50,50) in green. Try this with tol equal to 10, 3 and 1.