Curves in 2 or 3 Dimensions (Plane or Space Curves)

Curves in 2 or 3 Dimensions (Plane or Space Curves)
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Review of our Discussion of Lines in 2D

Explict Form [\(y=f(x)\)]:
- \(p_2(p_1) = m p_1 + b\)
Implict Form [\(f(x,y)=0\)]:
- \(\bs{n} \cdot \bs{p} + b = 0\)
Parametric Form [\(x=f(\lambda), y=g(\lambda)\)]:
- \(\bs{p}(\lambda) = \lambda \bs{r} + (1 - \lambda) \bs{s}\)

What About Curves?

Explicit Form:
- Explict representations often don't exist (e.g., a circle around the origin with radius \(r\) requires two functions, \(y = \sqrt{r^2 - x^2}\) and \(y = -\sqrt{r^2 - x^2}\), and they only hold when \(0 \leq |x| \leq r\))
Implicit Form:
- We can use implicit representations (e.g., a circle around the origin with radius \(r\) can be represented as \(x^2 + y^2 - r^2 = 0\))
- But, we must use a scanning algorithm (i.e., check each point to see if it is on the curve)
- In addition, curves in 3D are difficult to represent in implicit form (it is possible to use the intersection of surfaces but it is difficult)

Parametric Polynomial Curves

A Curve of Degree \(n\):
- \(\bs{p}(\lambda) = \sum_{k=0}^{n} \bs{c_k} \lambda^k \)
Be Careful:
- \(\bs{c_k}\) has as many components as \(\bs{p}\). That is, \(\bs{c_k} = [ c_{k1} \;\; c_{k2} \;\; c_{k3} ]^T\)

Parametric Cubic Polynomial Curves

The Representation:
- \(\bs{p}(\lambda) = \bs{c_0} + \bs{c_1} \lambda + \bs{c_2} \lambda^2 + \bs{c_3} \lambda^3 \)
A Cubic in Matrix Form:
- \(\bs{C} = \left[ \begin{array}{r r r} c_{01} && c_{11} && c_{21} && c_{31} \\ c_{02} && c_{12} && c_{22} && c_{32} \\ c_{03} && c_{13} && c_{23} && c_{33} \\ \end{array}\right]\)
- \(\bs{\lambda} = \left[ \begin{array}{r}1 \\ \lambda \\ \lambda^2 \\ \lambda^3 \end{array}\right]\)
- \(\bs{p} = \bs{C} \bs{\lambda}\)

Parametric Cubic Polynomial Curves (cont.)

The Interpolating Polynomial:
- Given four points (i.e., 12 independent variables), we can find the coefficients, \(\bs{C}\), of a cubic polynomial curve that pass through them
Other Related Approaches:
- Hermite curves
- Parabolic blending

Bézier Curves

The Idea:
- Use four points, \(\bs{q}_0, \bs{q}_1, \bs{q}_2, \bs{q}_3, \), but don't have the curve pass through all of them
- Use two, \(\bs{q}_0, \bs{q}_3, \), as the end points and two, \(\bs{q}_1, \bs{q}_2\), to approximate the tangents at the end points
A Visualization:

Bézier Curves (cont.)

Recall:
- \(\bs{p}(\lambda) = \bs{c_0} + \bs{c_1} \lambda + \bs{c_2} \lambda^2 + \bs{c_3} \lambda^3 \)
The Obvious Conditions:
- \(\bs{p}(0) = \bs{q}_0 \Rightarrow \bs{c_0} = \bs{q}_0\)
- \(\bs{p}(1) = \bs{q}_3 \Rightarrow \bs{c_0} + \bs{c_1} + \bs{c_2} + \bs{c_3} = \bs{q}_3\)
Linear Approximations of the Tangents:
- Assuming that the points are evenly spaced, they correspond to \(\lambda=0\), \(\lambda=1/3\), \(\lambda=2/3\), and \(\lambda=1\). So:
- An approximation of the tangent at \(\lambda=0\) is given by \(\frac{\bs{q}_1 - \bs{q}_0}{1/3}\) (or, equivalently, \(3(\bs{q}_1 - \bs{q}_0)\))
- An approximation of the tangent at \(\lambda=1\) is given by \(\frac{\bs{q}_3 - \bs{q}_2}{1/3}\) (or, equivalently, \(3(\bs{q}_3 - \bs{q}_2)\))
The Derivative:
- \(\frac{d \bs{p}(\lambda)}{d \lambda} = \bs{c_1} + 2 \bs{c_2} \lambda + 3 \bs{c_3} \lambda^2\)
The Tangency Conditions:
- \(\left.\frac{d \bs{p}(\lambda)}{d \lambda}\right|_{\lambda = 0} = 3 \bs{q}_1 - 3 \bs{q}_0 \Rightarrow \bs{c_1} = 3 \bs{q}_1 - 3 \bs{q}_0\)
- \(\left.\frac{d \bs{p}(\lambda)}{d \lambda}\right|_{\lambda = 1} = 3 \bs{q}_3 - 3 \bs{q}_2 \Rightarrow \bs{c_1} + 2 \bs{c_2} + 3 \bs{c_3} = 3 \bs{q}_3 - 3 \bs{q}_2\)

Bézier Curves (cont.)

On Way to Proceed:
- Solve this system of equations
Another Way to Proceed:
- Recognize that this is an application of Bernstein polynomials
- \( B_{i,n}(\lambda) = \left( \begin{array}{c c} n \\ i \end{array} \right) (1 - \lambda)^{n-i} \lambda^i \)

Bézier Curves (cont.)

Bernstein Representation:
- An \(n\)th-order Bézier curve can be written in terms of \(n+1\) points, \(\bs{q}_0, \ldots, \bs{q}_n\), as follows
- \(\bs{p}(\lambda) = \sum_{i=0}^{n} B_{i,n}(\lambda) \bs{q}_i\)
Cubic Bézier Curves Revisited:
- \( \bs{p}(\lambda) = B_{0,3}(\lambda) \bs{q}_0 + B_{1,3}(\lambda) \bs{q}_1 + B_{2,3}(\lambda) \bs{q}_2 + B_{3,3}(\lambda) \bs{q}_3 \)
- where
- \( B_{0,3}(\lambda) = -\lambda^3 + 3\lambda^2 - 3\lambda + 1 \)
- \( B_{1,3}(\lambda) = 3\lambda^3 - 6\lambda^2 + 3\lambda \)
- \( B_{2,3}(\lambda) = -3\lambda^3 + 3\lambda^2 \)
- \( B_{3,3}(\lambda) = \lambda^3 \)

Cubic Bézier Curves

Expanding:
- \( \bs{p}(\lambda) = ( -\lambda^3 + 3\lambda^2 - 3\lambda + 1) \bs{q}_0 + ( 3\lambda^3 - 6\lambda^2 + 3\lambda) \bs{q}_1 + (-3\lambda^3 + 3\lambda^2) \bs{q}_2 + ( \lambda^3) \bs{q}_3 \)
Collecting Terms:
- \( \bs{p}(\lambda) = (- \bs{q}_0 + 3 \bs{q}_1 - 3 \bs{q}_2 + \bs{q}_3) \lambda^3 + (3 \bs{q}_0 - 6 \bs{q}_1 + 3 \bs{q}_2) \lambda^2 + (-3 \bs{q}_0 + 3 \bs{q}_1) \lambda + (\bs{q}_0) 1 \)
Matrix Notation:
- \( \bs{p}(\lambda) = \left[ \begin{array}{l l l l} q_{01} & q_{11} & q_{21} & q_{31} \\ q_{02} & q_{12} & q_{22} & q_{32} \\ q_{03} & q_{13} & q_{23} & q_{33} \\ \end{array} \right] \left[ \begin{array}{r r r r} -1 & 3 & -3 & 1 \\ 3 & -6 & 3 & 0 \\ -3 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ \end{array} \right] \left[ \begin{array}{l} \lambda^3 \\ \lambda^2 \\ \lambda \\ 1 \\ \end{array} \right] \)

Bézier Curves (cont.)

Some Interesting Observations:
- \( B_{i,n}(\lambda) \in (0, 1] \)
- \( \sum_{i=1}^{n} B_{i,n}(\lambda) = 1 \)
The Implications:
- \(\bs{p}(\lambda) = \sum_{i=0}^{n} B_{i,n}(\lambda) \bs{q}_i\) is a convex combination of \(\bs{q}_0, \ldots, \bs{q}_n\)
- The curve is in the convex hull formed by \(\bs{q}_0, \ldots, \bs{q}_n\)