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 of 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.
Create a directory assignment6 under assignments in your cs170 directory. All code for the assignment should be stored in this directory.
cd ~/cs170/assignments mkdir assignment6 cd assignment6
The program should display a window that adds small circles whereever 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.
The de Casteljau algorithm can be used to generate a single point that exists on the bezier curve. It is a recursive algorithm takes two parameters: A list of control points and a floating point value \(t\) in the range [0, 1]. The de Casteljau algorithm returns the point that is \(t \%\) along the bezier curve. To draw the entire curve, you will compute a fixed amount of evenly spaced points on the curve (which are computed by varying the value of \(t\) provided to the algorithm). You will then connect consecutive points along the curve using straight lines. By default, your program does not need to draw the control structure.
The de Casteljau algorithm can be expressed recursively using the following equations:
\[ \begin{eqnarray} de\_casteljau([ p_1 ], t) &=& p1\\ de\_casteljau([ p_1, \ldots, p_n ], t) &=& de\_casteljau([ linear\_interpolate(p_1, p_2, t), linear\_interpolate(p_2, p_3, t), \ldots, linear\_interpolate(p_{n-1}, p_{n}, t) ], t) \end{eqnarray} \]
Where t is the is a floating point value in the range [0, 1] representing the parametric distance, linear_interpolate finds the point at the specified parametric distance between two points, and the square brackets specify a list of points.
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 \(x_1\) and \(x_2\), and a parametric distance \(t\) in the range [0, 1]. You need to find the real value \(x_3\) that is \(t \%\) between \(x_1\) and \(x_2\).
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.
You are required to submit a tar file to http://inquire.roanoke.edu/. On inquire, there is a link for Assignment 6. You can create a tar file by issuing the following commands:
cd ~/cs170/assignments tar czvf assignment6.tgz assignment6/
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.
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.