CSCE 645/VIZA 675: Geometric Modeling
Assignment 1: Smooth Curves [100 points]
Due 9/30
Purpose:
This assignment will introduce you to methods for representing and manipulating smooth 2D curves.
Description:
In this assignment you will implement four different algorithms we discussed for representing smooth curves: lagrange interpolation, bezier curves, b-splines, and Catmull-Rom curves. You should allow the user to add points by clicking the mouse on the screen. Once the user presses the 'e' key, no more control points may be added; however, the user should be able to select points on the screen and drag them around to modify the curves. When the user presses '1', you should display the curves defined by Lagrange interpolation. When the user presses '2', you should display the Bezier curves defined by the control points. When the user presses '3', you should display the B-spline curves defined by the control points. Finally, '4' should display the Catmull-Rom curves defined by the control points.
For Lagrange interpolation, the user should be able to increase or decrease the degree of the interpolated curve by pressing '+' or '-' respectively. Start with a degree 1 curve. If the degree is currently d, then each consecutive set of d+1 control points should be interpreted as a single Lagrange curve. For example, if the current degree is 3 and the number of control points is 9, points 0-3 and 4-7 should be interpreted as two separate curves. Any extra control points should be ignored. You may assume that the parameter values (i.e. knots) are evenly spaced.
For Bezier curves, your program should behave similar to Lagrange interpolation. '+' and '-' should increase or decrease the degree of the Bezier curves. The degree should be 1 to start with. Each set of d+1 control points should be interpreted as a single Bezier curve of degree d. Furthermore, if the user presses the 'i' key, you should find the intersection (if any) of the current Bezier curves on the screen and highlight the intersection with a point marking those locations. To determine the intersection between two Bezier curves, we discussed an algorithm based on the convex hull in class. You do not need to implement a convex hull computation. Instead, compute the axis-aligned bounding boxes of the two curves and their intersection to determine if you recur in the algorithm or not. If both control polygons can be approximated by a straight line (all control points within epsilon from the line defined by the first and last control point), then intersect the two lines.
For B-spline curves, you should render a single B-spline curve of degree d. Again, the user should be able to control the degree of the curve using the '+', '-' keys.
For Catmull-Rom curves, you should render a single Catmull-Rom curve. The user should be able to increase or decrease the smoothness of the curves by pressing '+' or '-' respectively. Start with smoothness d = 0. Given a smoothness level d, each consecutive set of 2(d+1) control points should be interpreted as a single Catmull-Rom segment.
You may cap the maximum degree of the curves at 8 and the minimum degree should be 1. A simple starting place could be the example code here. You are not required to use this code though.
Note that implementing the assignment as specified will only provide 80 out of 100 points. To receive full credit, you must go above and beyond the basic requirements. You might add code to create a more full-function curve editor. You could write code to draw simple SVG files (a vector graphics format using Bezier curves) or fonts. You might use your program to create your own piece of art (hopefully with save/load features). These are only some suggestions. The idea is to be creative.
Grading:
[1] Ability to add points with mouse click
[2] Correct transition ability from editing to point manipulation with the 'e' key
[5] Ability to modify the points by dragging them around on the screen and suitable display to indicate the positions of the control points on the screen
[2] Correct degree raising/lowering behavior for all four curves with '+'/'-' keys
[15] Correct display of Lagrange curves of all degree when user presses '1'
[15] Correct display of Bezier curves of all degree when user presses '2'
[15] Correct display of B-spline curves of all degree when user presses '3'
[15] Correct display of Catmull-Rom curves of all degree when user presses '4'
[10] Bezier intersection performed properly
[20] Extend the basic requirements