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

Similarly, a Bezier surface of degree $(n, m)$ is defined by $(n + 1)\times(m + 1)$ control points. It is a parametric surface based on two parameters $u$ and $v$, 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 $n$ (possibly intermediate) control points $p_1, …, p_n$ and the parameter $t$, we can use linear interpolation to compute the $n-1$ intermediate control points at the parameter $t$ in the next subdivision level, $p_1’, …, p_{n-1}’$, where

\[p_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 $t$.

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 $t$ in the next subdivision level. Note that the parameter $t$ 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 $t$ 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 \times n$ grid of original control points. controlPoints is of size $n$ and each inner std::vector, i.e., controlPoints[i], contains $n$ control points at the $i$th-row. For example, controlPoints[0] and controlPoints[n-1] each have $n$ 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 \times n$ grid of original control points, $P_{ij}$, where $i$ and $j$ are row and column index, and (2) the two parameters $u$ and $v$.

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

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 $t$. It outputs a std::vector of intermediate control points at the parameter $t$ in the next subdivision level.
  • BezierPatch::evaluate1D(...): This function takes as inputs a std::vector of 3D points and a parameter $t$. It outputs directly the final, single point that lies on the Bezier curve at the parameter $t$. 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 $u$ and $v$ and outputs the point that lies on the Bezier surface, defined by the $n \times n$ controlPoints, at the parameter $u$ and $v$. 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.