design/beziers.tex

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