Bezier Curves

A Bézier curve is a method for representing curves popularized by the French engineer Pierre Bézier in the 1960's. Bézier used the curves in the design automobiles. The curves are still popular today in drawing and animation applications because they offer an intuitive control over curve shape. Bézier curves can also be approximated very easily using a recursive algorithm developed by another Frenchman, Paul de Casteljau. You are going to create a program that allows users to draw a Bézier curve.

Setup

Create a directory assignment5 under assignments in your cs170 directory. All code for the assignment should be stored in this directory. 

cd ~/cs170/assignments
mkdir assignment5
cd assignment5

Details

The program should display a window that adds small circles where ever the mouse is clicked. Each circle in the window is a control point for a Bézier curve. Each time a control point is added the display should redraw the Bézier curve to include the new control point.

In order to draw a Bézier curve, you need to calculate a series of points on the curve. The program should use a recursive function that implements the de Casteljau algorithm to calculate a fixed number of evenly spaced points on the curve. Then, draw lines between each pair of consecutive points, to draw the curve. The program does not need to draw the control structure, just the control points and the curve.

The de Casteljau algorithm can be expressed recursively using the following equations: 

dC(⟨p1⟩, t) = p1
dC(⟨p1, p2, … pn⟩, t) =
    dC(⟨interp(p1, p2, t), interp(p2, p3, t), …, interp(pn-1, pn, t)⟩, t)

Where t is the is a floating point value in the range [0, 1] representing the parametric distance, interp finds the point at the specified parametric distance between two points, and the angle brackets, ⟨⟩, specify a list of points.

Pseudo Code

Linear Interpolation

We have not talked about linear interpolation this semester, although you have indirectly been using it in a handful of programs. You are given two real numbers x1 and x2, and a parametric distance t in the range [0, 1]. You need to find the real value x3 that is t% between x1 and x2.

For Monday, Feb. 24th, I want you to turn in (on paper!) pseudo code for the linear interpolation function, with 2 test cases that demonstrate that you understand how the code should operate.

Submission

You are required to submit a tar file to http://cseval.roanoke.edu/. On cseval, there is a link for Assignment 5. You can create a tar file by issuing the following commands: 

cd ~/cs170/assignments
tar czvf assignment5.tgz assignment5/

"Hacker" Prompt

  1. Movable Control Points: Add the ability to modify a Bézier curve after it has been drawn by dragging its control points. When the user is dragging a control point, the Bézier curve should be redrawn every time the mouse drag call-back function is called.

  2. de Casteljau Slider: One of the interesting things about the de Casteljau algorithm is the "recursive descent" that occurs in order to find a particular point on the true curve. While you likely were able to create the Bézier without having a good visualization of how it works. The actual process that is going on, however, is pretty cool looking.

    Create an additional panel to your tk window, that has a tk.Checkbutton and a tk.Scale widget. If the check button is selected, you should display the control structure of the Bézier curve. You should use the slider to pick the parametric distance t. This control structure should display how the tth point of the curve was generated.

Last modified: Fri Feb 21 12:26:00 EST 2014