[Numerical Analysis] 4. Curve

Curve

 

Curves - Implicit Representation

Most curves can be represented implicity : $f(x,y) = 0$ in 2D, $f(x,y,z)=0$ in 3D

 

Curves - Parametric Representation

The value of each component $(x,y,z)$ depends on an idenpendent variable, $u$ ( the parameter ).

$x = x(u), y=y(u), z=z(u)$ , $ p(u) = \begin{bmatrix} x(u) \\ y(u) \\ z(u) \end{bmatrix} $, derivative

 

 

Criteria for choosing a representation

Parametric forms are not unique. Many different representations are possible for a single curve.

 

Criteria for a good representation

- Local control of shape

- Smoothness and continuity

- Ability to evaluate derivatives

- Stability

- Ease of Rendering

 

Parametric curves that are polynomials in $u$ satisfy many of these criteria

- $x(u) = c_0 + c_1 U + c_2 u^2 + \cdots + c_n u^n = \sum_{k=0}^n c_k u^k$

- $p(u) = \begin{bmatrix} x(u) \\ y(u) \\ z(u) \end{bmatrix} = \begin{bmatrix} \sum_{k=0}^n c_{xk} u^k \\ \sum_{k=0}^n c_{yk} u^k \\ \sum_{k=0}^n c_{zk} u^k \end{bmatrix} = \sum_{k=0}^n u^k \begin{bmatrix} c_{xk} \\ c_{yk} \\ c_{zk} \end{bmatrix} = \sum_{k=0}^n u^k c_k$

 

Degree of the Polynomial

what degree should our polynomial representation have?

- Tradeoff : 

    - High degree can have rapid changes and lots of turns, but it requires more computation and curve may not be as smooth.

    - Low degree means a smoother curve, but it may not fit the data as well

- Compromise :

    - Use low degree polynomials with short curve segments.

ex) Design Font : represent each curve with low degree polynomials

 

 

Multiple curve segements

We usually want to define a curve segment between two endpoints.

We define the curve between $u=0$ and $u=1$, so that : 

    - $p(0) = p_0$ and $p(1) p_1$ ( join point, Not smooth - discontinuous derivative or Smooth )

Longer curves are composed of multiple segments. We would like the connection between curves to be as smooth as possible

 

Cubic Representation

- $p(u) = c_0 + c_1u + c_2 u^2 + c_3 u^3 = u^T c$

- $c$ : 4x3 matrix

 

Interpolation

if one point provides 3 equations and 12 unknowns then 4 points provide 12 equations with 12 unknowns.

We can choose any value of $u$ of correspond to the 4 points, so we will choose th divide the interval 0 to 1 evenly

- $p(u) = u^Tc$ c : determine shape of curve

4 points : $p_i = p(u_i)$ -> 3 equations X 4 = 12 unknown values

$p_0, p_1, p_2, p_3$ -> uniformly divide, ( $u = 0, 1/3, 2/3, 1 $ )

 

 

Matrix Equations

Equations for 4 points:

- $p_0 = p(0) = c_0$

- $p_1 = p(1/3) = c_0 + c_1 (1/3) + c_2 (1/3)^2 + c_3 (1/3)^3$

- $p_2 = p(2/3) = c_0 + c_1 (2/3) + c_2 (2/3)^2 + c_3 (2/3)^3$

- $p_3 = p(1) = c_0 + c_1 + c_2 + c_3$

- $p = Ac$, $c = A^{-1}p$

Interpolating geometry matrix : $M = A^{-1}$

 

 

Blending Functions

We can express the desired curve in terms of a set of functions, known as blending functions.

$ p(u) = u^Tc = u^T (M_I p) = (u^T M_I) p = b(u)^T p  = b_0(u) p_0 + b_1(u) p_1 + b_2(u)p_2 + b_3(u) p_3$ : Weighted sum blended function $b(u)$

$b(u) = M_I^T u = \begin{bmatrix} b_0(u) \\ b_1(u) \\ b_2(u) \\ b_3(u) \end{bmatrix}$

$b(0) = p_0$, $b(1/3) = p_1$, $b(2/3) = p_2$, $b(1) = p_3$

 

With More Then 4 Points

When working with more than 4 points, we find curves for each group of 4.

1st curve : $p_0, p_1, p_2, p_3$

2nd curve : $p_3, p_4, p_5, p_6$ ( same last control point in 1st to first control point in 2nd )

- Note that the join won't necessarily be smooth. ( interpolation is independent each other )

 

 

Hermite Curves

- Problems with Interpolation :

    - Join points may not be smooth (may have discontinuous derivatives)

- Hermite Curves use the derivatives at the endpoints of the curves ( in place of the 2 internal data points.)

$p(u) = c_0 + c_1 u + c_2 u^2 + c_3 u^3$

$p'(u) = c_1 + 2c_2u + 3c_3 u^2$

Just 2 points -> 4 equations with derivatives

$p(0) = p_0 = c_0$, $p'(0) = c_1$, $p(1) = p_3 = c_0 + c_1 + c_2 + c_3$, $p'(1) = c_1 + 2c_2 + 3c_3$

 

$$q = \begin{bmatrix} p(0) \\ p(1) \\ p'(0) \\ p'(1)\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 2 & 3 \\ \end{bmatrix}\begin{bmatrix} c_0 \\ c_1 \\ c_2 \\ c_3 \end{bmatrix} $$

 

- Blending functions :

$p(u) = u^T M_H q = b(u)^T q $, where $ b(u) = \begin{bmatrix} 2u^3 - 3u^2 +1 \\ -2u^3+3u^2 \\ u^3-2u^2 + u \\ u^3 - u^2 \end{bmatrix} $

 

 

Bezier Curves

- Problem with Hermite Curves :

    - We may not know the derivative of the optimal curve. We may only have a set of data points.

- Bezier curves use data from a set of 4 data points, and approximate the derivatives using the difference between adjacent points.

- Bezier curves do not require the curve to pass through the middle pair of points. Instead they use these points to estimate the derivatives at the end points.

 

- Setting up the equations

Estimate Derivative from Points

-> $p'(0) = \frac{(p_1 - p_0)}{\frac{1}{3}} = 3(p_1 - p_0) $

-> $p'(1) = \frac{p_3 - p_2}{\frac{1}{3}} = 3(p_3 - p_2) $

$p'(0) = 3(p_1- p_0)  = c_1$, $p'(1) = 3(p_3 - p_2) = c_1 + 2c_2 + 3c_3$

$$ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ -3 & 3 & 0 & 0 \\ 0 & 0 & -3 & 3 \\ \end{bmatrix}\begin{bmatrix} p_0 \\ p_1 \\ p_2 \\ p_3 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 2 & 3 \\ \end{bmatrix}\begin{bmatrix} c_0 \\ c_1 \\ c_2 \\ c_3\end{bmatrix} $$

$ Ap = Bc$, $c = B^{-1}Ap = M_Bp$

$M_B = \begin{bmatrix} 1 & 0 & 0 & 0 \\ -3 & 3 & 0 & 0 \\ 3 & -6 & 3 & 0 \\ -1 & 3 & -3 & 1 \\
 \end{bmatrix}$

 

The Bezier Blending Functions

As before, we can write the equation for our curve in ters of blending functions : $p(u) = u^T M_B p = b(u)^T p$

$b(u) = \begin{bmatrix} (1-u)^3 \\ 3u(1-u)^2 \\ 3u^2(1-u) \\ u^3 \end{bmatrix} $

 

$b(u)$ are Bernstein polynomials

- $ \binom{d}{k}u^k(1-u)^{d-k} = \frac{d!}{k!(d-k)!}u^k(1-u)^{d-k} $

- Bernstein polynomials have zeros only at $u=0$ and $u=1$.

- The sum of all the polynomials equals 1.

- Therefore $p(u)$ is inside the convex hull formed by the control points.

- Bezier blending functions are smoother than interpolation functions.

Derivative 는 벡터에 의해서 결정되기 때문에, smooth 를 보장하진 않지만, 다음 point 를 적절히 설정하면 smooth 하게 만들 수 있다.

 

 

Levels of Continuity

- When joining two curve segments, we can have different levels of continuity.

- Parametric continuity :

    - $C^0$ continuity : The resulting curve is continuous at the join point (but not necessarily smooth.)

    - $C^1$ continuity : The resulting curve is continuous and the derivatives of two segments match at the join points.

    - $C^2$ continuity : The curve is continuous, the derivatives and the 2nd erivatives match at the join point.

- Geometric continuity : 

    - $G^0$ : The same as $C^0$

    - $G^1$ : The curve is continuous. The derivatives have the same direction, but may have different magnitudes.

 

Continuity of Curves

- Interpolation 

    - Continuous, but not necessarily smooth : $C^0$

- Hermite

    - Can make derivatives match at join point : $C^1$

- Bezier

    - The derivative might not match at the join point : $C^0$

- We would like a method that :

    - Provides smooth continuity at the join points. (Hermite curves)

    - Uses a data from a set of points ( Bezier curves )

- Splines

    - Provide both, and provide $C^2$ continuity

 

 

Splines

Splines use a set of 4 control points to create a curve interpolated between the middle pair of points.

Splines do not require that the curve pass through any of the control points -- only that it comes close to them.

Given the points $p_{i-2}, p_{i-1}, p_i, p_{i+1}$, we create a curve for $0 \leq u \leq 1$ between the points $p_{i-1}$ and $p_i$

 

- Joining the Segments

We can create an adjoining segment by adding one data point, $p_{i+2}$ and using the points ( $i-1, i,i+1,i+2$ ) to create the segment between $p_i$ and $p_{i+1}$

Similarly, the previous segment uses $p_{i-3}, p_{i-2}, p_{i-1}, p_i$ to create the curve between $p_{i-2}$ and $p_{i-1}$

We develop the equations so that the join point between segments is continuous and smooth.

 

- Gemerating the spine equations

Two curve segments : $q$ and $p$, each defined for $0 \leq u \leq 1$, $q : p_{i-2} \cdots p_{i+1}$, $p:p_{i-1}\cdots p_{i+2}$

    - Continuity : $q(1) = p(0) = \frac{1}{6} (p_{i-1} + 4p_4 + p_{i+1})$, Choose weighted function between control points

    - Smoothness : $q'(1) = p'(0) = \frac{1}{2}(p_{i+1} - p_{i-1})$

    - These are not unique choices, but they work well. By symmetry, choose equations for $p(1)$ and $p'(1)$ :

      - $p(1) = \frac{1}{6}(p_i + 4p_{i+1}  + p_{p+2}$, $p'(1) = \frac{1}{2}(p_{i+2} - p_1)$

 

- The B-spine Geometry Matrix

Recall that $p(u) = c_0 + c_1 u + c_2 u^2 + c_3 u^3$, $p'(u) = c_1 2c_2 u + 3c_3 u^2$

For 4 points $ p_0, p_1, p_2, p_3$ we have : 

    - $p(0) = c_0 = \frac{1}{6}(p_0 + 4p_1 + p_2)$

    - $p'(0) = c_1 = \frac{1}{2}(p_2 - p_0$

    - $p(1) = c_0 + c_1+c_2+c_3 = \frac{1}{6}(p_1 + 4p_2 + p_3)$

    - $p'(1) = c_1 + 2c_2 + 3c_3 = \frac{1}{2}(p_3 - p_1)$

Solving for $c_i$ in terms of p gives :

    - $c = M_S p$

    - $M_S = \frac{1}{6}\begin{bmatrix} 1 & 4 & 1 & 0 \\ -3 & 0 & 3 & 0 \\ 3 & -6 & 3 & 0 \\ -1 & 3 & -3 & 1 \\ \end{bmatrix}$

    - $p(u) = u^Tc = u^T M_S P$

 

- Spine Blending Functions

As with the other methods, we can write the spline equations in terms of blending functions

    - $p(u) = u^TM_Sp = b(u)^T p$

    - $b(u) = \frac{1}{6}\begin{bmatrix} (1-u)^3 \\ 4-6u^2+3u^3 \\ 1+3u+3u^2-3u^3 \\ u^3\end{bmatrix}$

    - $b'(u) = \frac{1}{6}\begin{bmatrix} -3(1-u)^2 \\ -12u+9u^2 \\ 3+6u-9u^2 \\ 3u^2 \end{bmatrix}$

    - $b''(u) = \begin{bmatrix} 1-u \\ -2+3u \\ 1-3u \\ u \end{bmatrix}$

    - $p_0''(1) = b''(1)^T p = p_1-2p_2+p_3 = p_1''(0) = b''(0)^Tp = p_1 - 2p_2 + p_3$

Splines requires more computation than Bezier curves because each segment only spans 2 points ( instead of 4).