# Curves ## Motivation We have been studying the rendering pipeline by which a 3D geometry is projected onto a 2D screen and converted into pixels. But how are the 3D geometry described in the first place? That's why we are studying curves next. Although all the discussion will be w.r.t. 2D curves, but they can be used to create 3D geometries using, e.g., revolution and lofting. ***Splines*** will be our first encounter with defining a smooth curve with a polynomial ([YouTube video](https://www.youtube.com/watch?v=YMl25iCCRew) for a quick introduction). Next, we'll study ***Bezier curves***, ***deCasteljau's algorithm***, ***polar form labelling***, and **B-splines** in detail. - We've seen that splines are created by interpolating between ***control points*** to form a piece-wise polynomial function. One nice property of doing so is that we get to specify exactly though which points the curve should pass. However, the down sides are that 1) we have no control over the curves shape between control points, and that 2) it has poor continuity at knots (i.e. where polynomial pieces join). - Such drawbacks motivates *Bezier curves* and *B-splines*. They **approximate** control points (instead of passing through them directly as spline does) for better control over the curve's local behavior. ## Bezier Curves - **Pros**: Affine transformation on control points preserve curve shape. Easy to subdivide, hence easy to draw - **Cons**: Moving 1 control point affects the whole curve, meaning there's still no precise control over local curve behavior. This is something to be addressed by ***B-splines***. Let's define a few terms for ease of articulation later: - **Order** (of a bezier curve): $n=\text{Number of control points}$ - **Degree** (of a bezier curve): $d=n-1$ - **Control polygon**: The polygon formed by connecting control points ### Problem setup ![[5_curves 2023-02-07 10.07.30.excalidraw.svg]] **(Case1: Linear)** Let's start with the simple case where we only have two control points $p_1, p_2$ i.e. order $n=2$. We define [***affine interpolation***](https://sites.math.washington.edu/~king/java/gsp/affine%20interpolation.html) $F(u)$ that maps $u\in [0,1]$ onto the line segment $p_0p_1$, and that $F(0)=p_0, F(1)=p_1$ (recall [[4_shading#Gouraud Shading (Vertex shader)|scan-line]]): $F(u)=(1-u)p_0+up_1$ **(Case2: Quadratic)** Now we need to generalize the above interpolation to order $n=3$. We want to preserve the property that $F(0)=p_0, F(1)=p_2$ (still, $p\in[0,1]$). This is when the the ***de Casteljau's pyramid*** (in the figure above, the inverted "tree" structure with $p_0,p_1,p_2$ as 'leafs') comes in handy. This [UT Austin slides](https://www.cs.utexas.edu/users/fussell/courses/cs384g/lectures/lecture16.pdf) has awesome explanation for the ***de Casteljau's algorithm***. Also check out [this post](https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/de-casteljau.html). The algorithm boils down to understanding the de Casteljau's triangle and recursive linear interpolation, which we'll see in the following problem. We start from the leafs and traverse down: $\begin{align*} \text{1st interpolation}&: F_{01}=(1-u)p_0+up_1, \; F_{12}=(1-u)p_1+up_2\\ \text{2nd interpolation}&: (1-u)F_{01}+uF_{02}\\ \rightarrow F&=(1-u)^2 p_0+2 u(1-u)p_1+u^2p_2 \end{align*}$ **(Case3: Cubic)** Now we generalize to order $n=4$ without much effort. Similar to the quadratic case, we just interpolate recursively by traversing the pyramid: $F(u)=(1-u)^3p_0+ 3u(1-u)^2 p_1+ u^2(1-u)p_2+u^3p_3$ (**Case4: Arbitrary Order**): Binomial expansion over $((1-u)+u)^n$ $\begin{align*} F(u)&=\sum_k p_kB_k^n(u), \text{such that } \sum_kB_k^n(u)=1\\ B_k^n(u) &\coloneqq\frac{n!}{k!(n-k)!}(1-u)^{n-k}u^k \;\; \text{ (Bernstein-Bezier polynomials)} \end{align*}$ To recap and get more geometric intuition, let's see this awesome [YouTube video](https://www.youtube.com/watch?v=aVwxzDHniEw) on Bezier curve. ### de Casteljau's Algorithm We can use this algorithm to calculate point location on Bezier curve: - *Input*: Control points $C_i, (0\leq i\leq d)$ where $d$ is the degree. - *Output*: $f(u)$ where $u$ is the parameter for evaluation ![[Pasted image 20230207101557.png|400]] ```python ''' !! Not tested. Use with caution !! We can optimize the above alogrithm to eliminate additional storage for the 1-layer-above control points. ''' def de_casteljau(u:float, ctrl_pts:list) -> float: n, d = len(ctrl_pts), len(ctrl_pts)-1 ctrl_interpolated = [ci for ci in ctrl_pts] # Initial control points for level in range(d,-1,-1): # d, d-1, ..., 0 for i in range(level+1): p[i]= (1-u)*p[i] + u*p[i+1] return ctrl_interpolated[0] ``` The above algorithm is more numerically stable than the explicit formulation, so it's recommended to use the algorithm. ### $4\times4$ Matrix for Cubic Bezier Curve Turns out the cubic bezier curve is the most widely used. We can write them in matrix form (as we can for any polynomial). This is sometimes called the **basis matrix**: $\begin{align*} F(u)&=(1-u)^3p_0+ 3u(1-u)^2 p_1+ u^2(1-u)p_2+u^3p_3\\ &=\vec{u}^TM\vec{p}\\ &=[u^3\;u^2\;u\;1]\underset{M}{\underbrace{\begin{bmatrix}-1&3&-3&1\\3&-6&3&0\\-3&3&0&0\\1&0&0&0\end{bmatrix}}}\begin{bmatrix}p_0\\p_1\\p_2\\p_3\end{bmatrix} \end{align*}$ > If the above 'linear-algebraic' way of interpreting polynomials looks strange to you, check out this [YouTube video about polynomial vector space](https://www.youtube.com/watch?v=SzZaQnzstfE) for a linear algebra refresher. ## Blossom & Polar Form Checkout [note by Prof. Albert Chern](https://cseweb.ucsd.edu/~alchern/teaching/cse167_2021/6-2Splines3.pdf) We need a way to mnemonic ***label*** points to interpolate in de Casteljau algorithm and to subdivide Bezier curve for recursive drawing. ***Cubic blossom*** and ***polar form*** help us achieve said goal. ### Problem Setup ![[Pasted image 20221223100259.png|600]] **(Quadratic)** We already have $F(u)$ that defines the Bezier curve. Now we define an auxiliary function $f(u_1,u_2)$ s.t. points on the curve have $u_1=u_2$, i.e. $F(u)=f(u,u)$. Then we label control points that are not on the curve with appropriate values of $(u_1,u_2)$. Function $f$ needs to satisfy the following rules: - **Diagonal**: $F(u)=f(u,u)$ - **Symmetric**: $f(u_1,u_2)=f(u_2,u_1)=a+b(u_1+u_2)+cu_1u_2$. (order of argument doesn't matter) - Only interpolate (linearly) btw. points with 1 arg different. E.g. $f(0,u)=(1-u)f(0,0)+uf(0,1)$ **(Cubic)** Now we generalize to the cubic case. This is called ***polar form labelling***. ### Subdivision & Recursive Drawing [slides](https://cseweb.ucsd.edu//~viscomp/classes/cse167/wi23/slides/lecture10.pdf) ![[5_curves 2023-02-09 09.56.56.excalidraw.svg|600]] ![[Pasted image 20221223102307.png|500]] ## B-Splines ![[Pasted image 20221224090909.png|500]] B-Splines give us **local control**, which Bezier curves lack. A curve represented by B-spline**s** (i.e. a B-spline curve) is a linear combination of B-splines. Each B-spline is a 'basis' **spline** defined by a set (size $d+1$) of polynomial of degree $d=n-1$. We will focus our discussion on **cubic** **B-Spline curves** only. - **Knots**: Where 2 B-splines join. It can be uniform or non-uniform Similar to Bezier curves, we are also interested in **polar form**, **deCasteljau** and the **matrix form** for B-splines. ### Polar Form for Cubic B-Splines We generalize the interpolation for Bezier curve to get the polar form for B-splines. More specifically: we generalize the length of the line segment for interpolation from 1 to arbitrary (in our case, 1, 2, or 3), and we generalize the end points of the line segment, such that it doesn't necessarily locate at 0. ![[5_curves 2023-02-09 10.33.05.excalidraw.svg|500]] ### Matrix Form of Cubic B-Splines $\begin{align*} F(u)=[u^3\;u^2\;u\;1]M\begin{bmatrix}p_0\\p_1\\p_2\\p_3\end{bmatrix}, \;M = \frac{1}{6}\begin{bmatrix}-1&3&-3&1\\3&-6&3&0\\-3&0&3&0\\1&4&1&0\end{bmatrix}\end{align*}$