design/beziers.tex

   1 \documentclass{article}
   2 \usepackage{amsmath}
   3 \newcommand{\sign}{\operatorname{sign}}
   4 \begin{document}
   5 \section{Bezier curves with prescribed tangent directions and curvatures at the endpoints}
   6
   7 Parameterization of the Bezier curve, for $x(t)$ and $y(t)$ equivalently,
   8 %
   9 \begin{align}
  10   x(t) &= x_0(1-t)^3 + 3x_1t(1-t)^2 + 3x_2t^2(1-t) + x_3 t^3\\
  11   \dot x(t) &= 3(x_1-x_0)(1-t)^2 + 3(x_3-x_2)t^2 + 6(x_2-x_1)t(1-t) \\
  12   \ddot x(t) &= 6(x_0 - 2x_1 + x_2)(1-t) + 6(x_1-2x_2+x_3) t \\
  13   \dddot x(t) &= 6(x_3-x_0) + 18(x_1-x_2)
  14 \end{align}
  15 %
  16 The curvature is
  17 \begin{equation}
  18   \kappa(t) = \frac{\dot x\ddot y - \ddot x\dot y}{[\dot x^2 + \dot y^2]^{3/2}}
  19 \end{equation}
  20 %
  21 with the sign
  22 %
  23 \begin{equation}
  24   \begin{aligned}
  25     \sign\kappa &> 0 \quad\text{for left bendings}\\
  26     \sign\kappa &< 0 \quad\text{for right bendings.}
  27   \end{aligned}
  28 \end{equation}
  29 %
  30 At the endpoints we can summarize:
  31 %
  32 \begin{align}
  33   \dot x(0)  &= 3(x_1 - x_0) \\
  34   \dot x(1)  &= 3(x_3 - x_2) \\
  35   \ddot x(0) &= 6(x_0 - 2x_1 + x_2) = -4\dot x(0) - 2\dot x(1) + 6(x_3 - x_0) \\
  36   \ddot x(1) &= 6(x_1 - 2x_2 + x_3) = +4\dot x(1) + 2\dot x(0) - 6(x_3 - x_0)
  37 \end{align}
  38 %
  39 and the same for the $y$ coordinates.
  40 The equations for the $\ddot x$ contain a convenient parameterization for this
  41 problem, with given endpoints and tangent directions. We now introduce two
  42 parameters for the distances between the first and the last pair of control
  43 points:
  44 %
  45 \begin{align}
  46   \left(\begin{array}{cc}
  47     x_1-x_0 \\ y_1-y_0
  48   \end{array}\right)
  49   &= \frac{1}{3}
  50   \left(\begin{array}{cc}
  51     \dot x(0) \\ \dot y(0)
  52   \end{array}\right)
  53   =: \alpha
  54   \left(\begin{array}{cc}
  55     t_x(0) \\ t_y(0)
  56   \end{array}\right) \\
  57   \left(\begin{array}{cc}
  58     x_3-x_2 \\ y_3-y_2
  59   \end{array}\right)
  60   &= \frac{1}{3}
  61   \left(\begin{array}{cc}
  62     \dot x(1) \\ \dot y(1)
  63   \end{array}\right)
  64   =: \beta
  65   \left(\begin{array}{cc}
  66     t_x(1) \\ t_y(1)
  67   \end{array}\right) \qquad
  68 \end{align}
  69 %
  70 Here, the externally prescribed tangent vectors are expected to be parallel to
  71 the tangent vectors of the parameterization and normalized to 1. This implies
  72 $\alpha>0$ and $\beta>0$ are the distances between the endpoints and their
  73 corresponding control points.
  74
  75 The problem to now to find proper parameters $\alpha>0$ and $\beta>0$ for a given set of
  76 endpoints $(x_0,y_0)$, $(x_3, y_3)$,
  77 normalized tangent vectors $\mathbf{t}(0)$, $\mathbf{t}(1)$ and of
  78 curvatures $\kappa(0), \kappa(1)$.
  79 The rest of the control points is then given by
  80 %
  81 \begin{equation}
  82   x_1 = x_0 + \alpha t_x(0) \quad\text{and}\quad
  83   x_2 = x_3 - \beta  t_x(1).
  84 \end{equation}
  85 %
  86 For the curvatures at the endpoints we get a nonlinear equation,
  87 %
  88 \begin{align}
  89   \kappa(0) (\dot x^2(0) + \dot y^2(0))^{3/2}
  90   &= \dot x(0) \ddot y(0) - \ddot x(0) \dot y(0) \\
  91   = 27 \kappa(0) |\alpha|^3
  92   &= \begin{aligned}[t]
  93       &+\dot x(0) \bigl[- 4\dot y(0) - 2\dot y(1) + 6(y_3-y_0)\bigr] \\
  94       &-\dot y(0) \bigl[- 4\dot x(0) - 2\dot x(1) + 6(x_3-x_0)\bigr]
  95      \end{aligned}\\
  96   &= \begin{aligned}[t]
  97       &-2 \bigl[\dot x(0) \dot y(1) - \dot y(0)\dot x(1)\bigr] \\
  98       &+6 \bigl[\dot x(0) (y_3-y_0) - \dot y(0) (x_3-x_0)\bigr]
  99      \end{aligned}\\
 100   &= \begin{aligned}[t]
 101       &-18 \alpha\beta \bigl[t_x(0)t_y(1) - t_y(0)t_x(1)\bigr] \\
 102       &+18 \alpha \bigl[t_x(0) (y_3-y_0) - t_y(0) (x_3-x_0)\bigr]
 103      \end{aligned}
 104 \end{align}
 105 %
 106 And short,
 107 %
 108 \begin{equation}
 109   0 = \frac{3}{2}\kappa(0) \alpha^2 \sign(\alpha)
 110     + \beta \bigl[t_x(0)t_y(1) - t_y(0)t_x(1)\bigr]
 111     - \bigl[t_x(0) (y_3-y_0) - t_y(0) (x_3-x_0)\bigr]
 112 \end{equation}
 113 %
 114 A similar calculation can be done for the end curvature,
 115 %
 116 \begin{align}
 117   \kappa(1) (\dot x^2(1) + \dot y^2(1))^{3/2}
 118   &= \dot x(1) \ddot y(1) - \ddot x(1) \dot y(1) \\
 119   = 27 \kappa(1) |\beta|^3
 120   &= \begin{aligned}[t]
 121        &+\dot x(1) \bigl[ 4\dot y(1) + 2\dot y(0) - 6(y_3-y_1)\bigr] \\
 122        &-\dot y(1) \bigl[ 4\dot x(1) + 2\dot x(0) - 6(x_3-x_1)\bigr]
 123      \end{aligned}\\
 124   &= \begin{aligned}[t]
 125        &-2 \bigl[\dot x(0) \dot y(1) - \dot y(0)\dot x(1)\bigr] \\
 126        &-6 \bigl[\dot x(1) (y_3-y_1) - \dot y(1) (x_3-x_1)\bigr]
 127      \end{aligned}\\
 128   &= \begin{aligned}[t]
 129        &-18 \alpha\beta \bigl[t_x(0)t_y(1) - t_y(0)t_x(1)\bigr] \\
 130        &-18 \beta \bigl[t_x(1) (y_3-y_1) - t_y(1) (x_3-x_1)\bigr]
 131      \end{aligned}
 132 \end{align}
 133 \begin{equation}
 134   0 = \frac{3}{2}\kappa(1) \beta^2 \sign(\beta)
 135     + \alpha \bigl[t_x(0)t_y(1) - t_y(0)t_x(1)\bigr]
 136     + \bigl[t_x(1) (y_3-y_1) - t_y(1) (x_3-x_1)\bigr]
 137 \end{equation}
 138 %
 139 Alltogether, we find the system of equations that is to be solved.
 140 %
 141 \begin{gather}
 142   \begin{aligned}
 143     0 &= \frac{3}{2} \kappa(0) \alpha^2 \sign(\alpha) + \beta T - D \\
 144     0 &= \frac{3}{2} \kappa(1) \beta^2 \sign(\beta) + \alpha T + E
 145   \end{aligned}\\[\medskipamount]
 146   \begin{aligned}
 147     T &:= t_x(0)t_y(1) - t_y(0)t_x(1) \\
 148     D &:= \bigl[t_x(0) (y_3-y_0) - t_y(0) (x_3-x_0)\bigr]\\
 149     E &:= \bigl[t_x(1) (y_3-y_0) - t_y(1) (x_3-x_0)\bigr]
 150   \end{aligned}
 151 \end{gather}
 152 %
 153 Decoupled, we get two equations of fourth order,
 154 %
 155 \begin{align}
 156   0 &= \frac{27}{8} \kappa(0)^2\kappa(1) \alpha^4
 157      - \frac{9}{2}D\kappa(0)\kappa(1)\alpha^2
 158      + T^3 \alpha
 159      + E T^2 + \frac{3}{2}\kappa(1) D^2 \\
 160    0 &= \frac{27}{8} \kappa(0)\kappa(1)^2\beta^4
 161      + \frac{9}{2}E\kappa(0)\kappa(1)\beta^2
 162      + T^3 \beta
 163      - D T^2 + \frac{3}{2}\kappa(0) E^2
 164 \end{align}
 165 %
 166
 167 \section{Bounding boxes for bezier curves}
 168
 169 The bounding box is defined by the minimal and maximal values of a
 170 curve. Hence the problem decouples for the two coordintes $x$ and $y$.
 171 We can search for the minima and maxima within the valid range for the
 172 parameter $t$ together with taking into account the values at the
 173 boundaries at $t=0$ and $t=1$.
 174
 175 For the $x$ coordinate we have:
 176 \begin{align}
 177   x(t) & = x_0(1-t)^3 + 3x_1t(1-t)^2 + 3x_2t^2(1-t) + x_3 t^3\\
 178        & = (x_3-3x_2+3x_1-x_0)t^3 + (3x_0-6x_1+3x_2)t^2 + (3x_1-3x_0)t + x_0\\
 179        & = a\,t^3 + \frac{3}{2}\,b\,t^2 + 3\,c\,t + x_0
 180 \end{align}
 181 %
 182 The constants $a$, $b$, and $c$ are
 183 %
 184 \begin{align}
 185   a & = x_3-3x_2+3x_1-x_0 \\
 186   b & = 2x_0-4x_1+2x_2 \\
 187   c & = x_1-x_0
 188 \end{align}
 189 %
 190 Now $\dot x(t)$ is
 191 %
 192 \begin{equation}
 193   \dot x(t) = 3\left[\,a\,t^2 + b\,t + c\,\right]
 194 \end{equation}
 195 %
 196 For a numerically stable calculation of the roots of the function, we
 197 first compute
 198 %
 199 \begin{equation}
 200   q = -\frac{1}{2}\left[\,b+\mathrm{sgn}(b)\sqrt{b^2-4ac}\right]
 201 \end{equation}
 202 %
 203 In case the square root is negative, we only need to take into account
 204 the values at the boundaries. Otherwise we need to take into account
 205 the two solutions
 206 %
 207 \begin{equation}
 208   t_1 = \frac{q}{a} \quad\text{and}\quad t_2 = \frac{c}{q}
 209 \end{equation}
 210 %
 211 Again, for numerical failures (divisions by zero) just need to skip
 212 the particular solution. The minima and maxima for $x(t)$ can now
 213 occure at $t=0$, $t=t_1$, $t=t_2$ and $t=1$.
 214
 215 \end{document}