- Forward


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


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Review of our Discussion of Lines in 2D
Back SMYC Forward
  • 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?
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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:
    • curve-cubic
Bézier Curves (cont.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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\)
There's Always More to Learn
Back -