Section I: Bezier Curves and Surfaces
In computer graphics, Bezier curves and surfaces are frequently used to model smooth and infinitely scalable curves and surfaces, such as in Adobe Illustrator (a curve drawing program) and in Blender (a surface modeling program).
A Bezier curve of degree is defined by control points. It is a parametric curve based on a single parameter , ranging between 0 and 1.
Similarly, a Bezier surface of degree is defined by control points. It is a parametric surface based on two parameters and , both ranging between 0 and 1.
In Section 1, you will use de Casteljau algorithm to evaluate Bezier curves and surfaces for any given set of control points and parameters, such as the Beizer curve below. In the image, white squares are the given control points, blue squares are the intermediate control points evaluated at the given parameter by de Casteljau algorithm, and the red square is the final evaluated point that lies on the Bezier curve.
Part 1: Bezier Curves with 1D de Casteljau Subdivision
In Part 1, you will implement Bezier curves. To get started, take a look at bezierCurve.h
and examine the member variables defined in the class. Specifically, you will primarily be working with the following:
std::vector<Vector2D> controlPoints
: Astd::vector
of original control points that define the Bezier curve, initialized from input Bezier curve file (.bzc
).float t
: A parameter at which to evaluate the Bezier curve, ranging between 0 to 1.
Recall from lecture that de Casteljau algorithm gives us the recursive step below:
Given (possibly intermediate) control points and the parameter , we can use linear interpolation to compute the intermediate control points at the parameter in the next subdivision level, , where
By applying this step recursively, we eventually arrive at a final, single point and this point, in fact, lies on the Bezier curve at the given parameter .
You need to implement this recursive step within BezierCurve::evaluateStep(...)
in student_code.cpp
. This function takes as input a std::vector
of 2D points and outputs a std::vector
of intermediate control points at the parameter in the next subdivision level. Note that the parameter is a member variable of the BezierCurve
class, which you have access to within the function. Each call to this function should performs only one step of the algorithm, i.e., one level of subdivision.
Implementation Notes
std::vector
is similar to Java’s ArrayList
class. You should use the push_back(...)
method to add elements to a std::vector
. This is analogous to the append(...)
method of ArrayList
. You can view this page for more information on push_back(...)
.
Sanity Check
To check if your implementation is likely correct, you can run meshedit
with a Bezier curve file (.bzc
) and view the generated Bezier curve on screen. Refer back here for a list of controls only for Section I Part 1.
For example, you can run the following command:
./meshedit ../bzc/curve1.bzc
where bzc/curve1.bzc
is a cubic Bezier curve. The provided bzc/curve2.bzc
is a degree-4 Bezier curve. Feel free to create your own .bzc
files and explore other Bezier curves.
Functions to Modify: Part 1
BezierCurve::evaluateStep(...)
For Your Write-Up: Part 1
For Homework 2, you can use your native screenshotting systems (there is no hotkey for screenshotting).
- Briefly explain de Casteljau’s algorithm and how you implemented it in order to evaluate Bezier curves.
- Take a look at the provided
.bzc
files and create your own Bezier curve with 6 control points of your choosing. Use this Bezier curve for your screenshots below. - Show screenshots of each step / level of the evaluation from the original control points down to the final evaluated point. Press E to step through. Toggle C to show the completed Bezier curve as well.
- Show a screenshot of a slightly different Bezier curve by moving the original control points around and modifying the parameter via mouse scrolling.
Part 2: Bezier Surfaces with Separable 1D de Casteljau
In Part 2, you will adapt what you have implemented for Bezier curves to Bezier surfaces. To get started, take a look at bezierPatch.h
and examine the member variables defined in the class. Specifically, you will primarily be working with the following:
std::vector<std::vector<Vector3D>> controlPoints
: A 2Dstd::vector
that has grid of original control points.controlPoints
is of size and each innerstd::vector
, i.e.,controlPoints[i]
, contains control points at the th-row. For example,controlPoints[0]
andcontrolPoints[n-1]
each have control points at the bottom row and the top row, respectively.
Recall from lecture that separable 1D de Casteljau algorithm works as the following:
The inputs to the algorithm are (1) a grid of original control points, , where and are row and column index, and (2) the two parameters and .
We first consider that each row of control points, , define a Bezier curve parameterized by . Just as in Part 1, we can use the recursive step to evaluate the final, single point on this Bezier curve at the parameter . We then consider that for all rows define a Bezier curve parameterized by . (These points lie roughly along a column. This lecture slide may help you visualize.) We can again use the recursive step from Part 1 to evaluate the final, single point on this Bezier curve at the parameter . This point , in fact, lies on the Bezier surface at the given parameter and .
You need to implement the following functions in student_code.cpp
:
BezierPatch::evaluateStep(...)
: Very similar toBezierCurve::evaluateStep(...)
in Part 1, this recursive function takes as inputs astd::vector
of 3D points and a parameter . It outputs astd::vector
of intermediate control points at the parameter in the next subdivision level.BezierPatch::evaluate1D(...)
: This function takes as inputs astd::vector
of 3D points and a parameter . It outputs directly the final, single point that lies on the Bezier curve at the parameter . This function does not output intermediate control points. You may want to callBezierPatch::evaluateStep(...)
inside this function.BezierPatch::evaluate(...)
: This function takes as inputs the parameter and and outputs the point that lies on the Bezier surface, defined by thecontrolPoints
, at the parameter and . Note thatcontrolPoints
is a member variable of theBezierPatch
class, which you have access to within this function.
Sanity Check
To check if your implementation is likely correct, you can run meshedit
with a Bezier surface file (.bez) and view the generated Bezier surface on screen.
For example, you can run the following command and you should see a teapot:
./meshedit ../bez/teapot.bez
Functions to Modify: Part 2
BezierPatch::evaluateStep(...)
BezierPatch::evaluate1D(...)
BezierPatch::evaluate(...)
For Your Write-Up: Part 2
For Homework 2, you can use your native screenshotting systems (there is no hotkey for screenshotting).
- Briefly explain how de Casteljau algorithm extends to Bezier surfaces and how you implemented it in order to evaluate Bezier surfaces.
- Show a screenshot of
bez/teapot.bez
(not.dae
) evaluated by your implementation.