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 nn is defined by (n+1)(n + 1) control points. It is a parametric curve based on a single parameter tt, ranging between 0 and 1.

Similarly, a Bezier surface of degree (n,m)(n, m) is defined by (n+1)×(m+1)(n + 1)\times(m + 1) control points. It is a parametric surface based on two parameters uu and vv, 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.

Bezier spline.

Part 1: Bezier Curves with 1D de Casteljau Subdivision

Relevant lecture: 7

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: A std::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 nn (possibly intermediate) control points p1,,pnp_1, …, p_n and the parameter tt, we can use linear interpolation to compute the n1n-1 intermediate control points at the parameter tt in the next subdivision level, p1,,pn1p_1’, …, p_{n-1}’, where

pi=lerp(pi,pi+1,t)=(1t)pi+tpi+1p_i' = lerp(p_i, p_{i+1}, t) = (1 - t)p_i + tp_{i+1}

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 tt.

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 tt in the next subdivision level. Note that the parameter tt 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 tt via mouse scrolling.

Part 2: Bezier Surfaces with Separable 1D de Casteljau

Relevant lecture: 7

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 2D std::vector that has n×nn \times n grid of original control points. controlPoints is of size nn and each inner std::vector, i.e., controlPoints[i], contains nn control points at the iith-row. For example, controlPoints[0] and controlPoints[n-1] each have nn 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 n×nn \times n grid of original control points, PijP_{ij}, where ii and jj are row and column index, and (2) the two parameters uu and vv.

We first consider that each row of nn control points, Pi0,,Pi(n1)P_{i0}, …, P_{i(n-1)}, define a Bezier curve parameterized by uu. Just as in Part 1, we can use the recursive step to evaluate the final, single point PiP_i on this Bezier curve at the parameter uu. We then consider that PiP_i for all nn rows define a Bezier curve parameterized by vv. (These nn 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 PP on this Bezier curve at the parameter vv. This point PP, in fact, lies on the Bezier surface at the given parameter uu and vv.

You need to implement the following functions in student_code.cpp:

  • BezierPatch::evaluateStep(...): Very similar to BezierCurve::evaluateStep(...) in Part 1, this recursive function takes as inputs a std::vector of 3D points and a parameter tt. It outputs a std::vector of intermediate control points at the parameter tt in the next subdivision level.
  • BezierPatch::evaluate1D(...): This function takes as inputs a std::vector of 3D points and a parameter tt. It outputs directly the final, single point that lies on the Bezier curve at the parameter tt. This function does not output intermediate control points. You may want to call BezierPatch::evaluateStep(...) inside this function.
  • BezierPatch::evaluate(...): This function takes as inputs the parameter uu and vv and outputs the point that lies on the Bezier surface, defined by the n×nn \times n controlPoints, at the parameter uu and vv. Note that controlPoints is a member variable of the BezierPatch 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.