design/beziers.tex

   1 \documentclass{article}
   2 \usepackage{amsmath}
   3 \usepackage{array}
   4 \usepackage{graphicx}
   5 \newcommand{\sign}{\operatorname{sign}}
   6
   7 \begin{document}
   8
   9 \section{B\'ezier curves with prescribed tangent directions and curvatures at the endpoints}
  10
  11 % <<<
  12 Parameterization of the B\'ezier curve, for $x(t)$ and $y(t)$ equivalently,
  13 %
  14 \begin{align}
  15   x(t) &= x_0(1-t)^3 + 3x_1t(1-t)^2 + 3x_2t^2(1-t) + x_3 t^3\\
  16   \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) \\
  17   \ddot x(t) &= 6(x_0 - 2x_1 + x_2)(1-t) + 6(x_1-2x_2+x_3) t \\
  18   \dddot x(t) &= 6(x_3-x_0) + 18(x_1-x_2)
  19 \end{align}
  20 %
  21 The curvature is
  22 \begin{equation}
  23   \kappa(t) = \frac{\dot x\ddot y - \ddot x\dot y}{[\dot x^2 + \dot y^2]^{3/2}}
  24 \end{equation}
  25 %
  26 with the sign
  27 %
  28 \begin{equation}
  29   \begin{aligned}
  30     \sign\kappa &> 0 \quad\text{for left bendings}\\
  31     \sign\kappa &< 0 \quad\text{for right bendings.}
  32   \end{aligned}
  33 \end{equation}
  34 %
  35 At the endpoints we can summarize:
  36 %
  37 \begin{align}
  38   \dot x(0)  &= 3(x_1 - x_0) \\
  39   \dot x(1)  &= 3(x_3 - x_2) \\
  40   \ddot x(0) &= 6(x_0 - 2x_1 + x_2) = -4\dot x(0) - 2\dot x(1) + 6(x_3 - x_0) \\
  41   \ddot x(1) &= 6(x_1 - 2x_2 + x_3) = +4\dot x(1) + 2\dot x(0) - 6(x_3 - x_0)
  42 \end{align}
  43 %
  44 and the same for the $y$ coordinates.
  45 The equations for the $\ddot x$ contain a convenient parameterization for this
  46 problem, with given endpoints and tangent directions. We now introduce two
  47 parameters for the distances between the first and the last pair of control
  48 points:
  49 %
  50 \begin{align}
  51   \left(\begin{array}{cc}
  52     x_1-x_0 \\ y_1-y_0
  53   \end{array}\right)
  54   &= \frac{1}{3}
  55   \left(\begin{array}{cc}
  56     \dot x(0) \\ \dot y(0)
  57   \end{array}\right)
  58   =: \alpha
  59   \left(\begin{array}{cc}
  60     t_x(0) \\ t_y(0)
  61   \end{array}\right) \\
  62   \left(\begin{array}{cc}
  63     x_3-x_2 \\ y_3-y_2
  64   \end{array}\right)
  65   &= \frac{1}{3}
  66   \left(\begin{array}{cc}
  67     \dot x(1) \\ \dot y(1)
  68   \end{array}\right)
  69   =: \beta
  70   \left(\begin{array}{cc}
  71     t_x(1) \\ t_y(1)
  72   \end{array}\right) \qquad
  73 \end{align}
  74 %
  75 Here, the externally prescribed tangent vectors are expected to be parallel to
  76 the tangent vectors of the parameterization and normalized to 1. This implies
  77 $\alpha>0$ and $\beta>0$ are the distances between the endpoints and their
  78 corresponding control points.
  79
  80 The problem to now to find proper parameters $\alpha>0$ and $\beta>0$ for a given set of
  81 endpoints $(x_0,y_0)$, $(x_3, y_3)$,
  82 normalized tangent vectors $\mathbf{t}(0)$, $\mathbf{t}(1)$ and of
  83 curvatures $\kappa(0), \kappa(1)$.
  84 The rest of the control points is then given by
  85 %
  86 \begin{equation}
  87   x_1 = x_0 + \alpha t_x(0) \quad\text{and}\quad
  88   x_2 = x_3 - \beta  t_x(1).
  89 \end{equation}
  90 %
  91 For the curvatures at the endpoints we get a nonlinear equation,
  92 %
  93 \begin{align}
  94   \kappa(0) (\dot x^2(0) + \dot y^2(0))^{3/2}
  95   &= \dot x(0) \ddot y(0) - \ddot x(0) \dot y(0) \\
  96   = 27 \kappa(0) |\alpha|^3
  97   &= \begin{aligned}[t]
  98       &+\dot x(0) \bigl[- 4\dot y(0) - 2\dot y(1) + 6(y_3-y_0)\bigr] \\
  99       &-\dot y(0) \bigl[- 4\dot x(0) - 2\dot x(1) + 6(x_3-x_0)\bigr]
 100      \end{aligned}\\
 101   &= \begin{aligned}[t]
 102       &-2 \bigl[\dot x(0) \dot y(1) - \dot y(0)\dot x(1)\bigr] \\
 103       &+6 \bigl[\dot x(0) (y_3-y_0) - \dot y(0) (x_3-x_0)\bigr]
 104      \end{aligned}\\
 105   &= \begin{aligned}[t]
 106       &-18 \alpha\beta \bigl[t_x(0)t_y(1) - t_y(0)t_x(1)\bigr] \\
 107       &+18 \alpha \bigl[t_x(0) (y_3-y_0) - t_y(0) (x_3-x_0)\bigr]
 108      \end{aligned}
 109 \end{align}
 110 %
 111 And short,
 112 %
 113 \begin{equation}
 114   0 = \frac{3}{2}\kappa(0) \alpha^2 \sign(\alpha)
 115     + \beta \bigl[t_x(0)t_y(1) - t_y(0)t_x(1)\bigr]
 116     - \bigl[t_x(0) (y_3-y_0) - t_y(0) (x_3-x_0)\bigr]
 117 \end{equation}
 118 %
 119 A similar calculation can be done for the end curvature,
 120 %
 121 \begin{align}
 122   \kappa(1) (\dot x^2(1) + \dot y^2(1))^{3/2}
 123   &= \dot x(1) \ddot y(1) - \ddot x(1) \dot y(1) \\
 124   = 27 \kappa(1) |\beta|^3
 125   &= \begin{aligned}[t]
 126        &+\dot x(1) \bigl[ 4\dot y(1) + 2\dot y(0) - 6(y_3-y_1)\bigr] \\
 127        &-\dot y(1) \bigl[ 4\dot x(1) + 2\dot x(0) - 6(x_3-x_1)\bigr]
 128      \end{aligned}\\
 129   &= \begin{aligned}[t]
 130        &-2 \bigl[\dot x(0) \dot y(1) - \dot y(0)\dot x(1)\bigr] \\
 131        &-6 \bigl[\dot x(1) (y_3-y_1) - \dot y(1) (x_3-x_1)\bigr]
 132      \end{aligned}\\
 133   &= \begin{aligned}[t]
 134        &-18 \alpha\beta \bigl[t_x(0)t_y(1) - t_y(0)t_x(1)\bigr] \\
 135        &-18 \beta \bigl[t_x(1) (y_3-y_1) - t_y(1) (x_3-x_1)\bigr]
 136      \end{aligned}
 137 \end{align}
 138 \begin{equation}
 139   0 = \frac{3}{2}\kappa(1) \beta^2 \sign(\beta)
 140     + \alpha \bigl[t_x(0)t_y(1) - t_y(0)t_x(1)\bigr]
 141     + \bigl[t_x(1) (y_3-y_1) - t_y(1) (x_3-x_1)\bigr]
 142 \end{equation}
 143 %
 144 Alltogether, we find the system of equations that is to be solved.
 145 %
 146 \begin{gather}
 147   \begin{aligned}
 148     0 &= \frac{3}{2} \kappa(0) \alpha^2 \sign(\alpha) + \beta T - D \\
 149     0 &= \frac{3}{2} \kappa(1) \beta^2 \sign(\beta) + \alpha T - E
 150   \end{aligned}\\[\medskipamount]
 151   \begin{aligned}
 152     T &:= t_x(0)t_y(1) - t_y(0)t_x(1) \\
 153     D &:= \bigl[t_x(0) (y_3-y_0) - t_y(0) (x_3-x_0)\bigr]\\
 154     E &:= \bigl[t_x(1) (y_0-y_3) - t_y(1) (x_0-x_3)\bigr]
 155   \end{aligned}
 156 \end{gather}
 157 %
 158 Decoupling the two equations causes problems with the absolute values,
 159 %
 160 \begin{align}
 161   \alpha = \frac{1}{T}\left(E - \frac{3}{2}\kappa(1)\beta |\beta |\right)\quad\text{and}\quad
 162   \beta  = \frac{1}{T}\left(D - \frac{3}{2}\kappa(0)\alpha|\alpha|\right)
 163 \end{align}
 164 %
 165 Thus, for $\alpha>0$ and $\beta>0$ we need also
 166 %
 167 \begin{align}
 168   \frac{1}{T}\left(E - \frac{3}{2}\kappa(1)\beta |\beta |\right) > 0\quad\text{and}\quad
 169   \frac{1}{T}\left(D - \frac{3}{2}\kappa(0)\alpha|\alpha|\right) > 0
 170 \end{align}
 171 %
 172 which is not always guaranteed. E.g. the combination
 173 %
 174 \begin{equation}
 175   T>0,\quad E<0\quad\text{and}\quad \kappa(1)>0
 176 \end{equation}
 177 %
 178 is not compatible with a positive value of $\beta$. Under what circumstances do
 179 we get such geometrically invalid results? Tests show that even allowing
 180 arbitrary signs of the curvatures $\kappa(0)$~and $\kappa(1)$ does not help in
 181 all cases.
 182
 183 Only when all the signs are correct, we can construct the solution by
 184 decoupling the equations,
 185 %
 186 \begin{align}
 187   0 &= \frac{27}{8} \kappa(0)^2\kappa(1) \alpha^4
 188      - \frac{9}{2}D\kappa(0)\kappa(1)\alpha^2
 189      + T^3 \alpha
 190      - E T^2 + \frac{3}{2}\kappa(1) D^2 \\
 191    0 &= \frac{27}{8} \kappa(0)\kappa(1)^2\beta^4
 192      - \frac{9}{2}E\kappa(0)\kappa(1)\beta^2
 193      + T^3 \beta
 194      - D T^2 + \frac{3}{2}\kappa(0) E^2
 195 \end{align}
 196 %
 197 % >>>
 198
 199 \section{Bounding boxes for B\'ezier curves}
 200
 201 % <<<
 202 The bounding box is defined by the minimal and maximal values of a
 203 curve. Hence the problem decouples for the two coordintes $x$ and $y$.
 204 We can search for the minima and maxima within the valid range for the
 205 parameter $t$ together with taking into account the values at the
 206 boundaries at $t=0$ and $t=1$.
 207
 208 For the $x$ coordinate we have:
 209 \begin{align}
 210   x(t) & = x_0(1-t)^3 + 3x_1t(1-t)^2 + 3x_2t^2(1-t) + x_3 t^3\\
 211        & = (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\\
 212        & = a\,t^3 + \frac{3}{2}\,b\,t^2 + 3\,c\,t + x_0
 213 \end{align}
 214 %
 215 The constants $a$, $b$, and $c$ are
 216 %
 217 \begin{align}
 218   a & = x_3-3x_2+3x_1-x_0 \\
 219   b & = 2x_0-4x_1+2x_2 \\
 220   c & = x_1-x_0
 221 \end{align}
 222 %
 223 Now $\dot x(t)$ is
 224 %
 225 \begin{equation}
 226   \dot x(t) = 3\left[\,a\,t^2 + b\,t + c\,\right]
 227 \end{equation}
 228 %
 229 For a numerically stable calculation of the roots of the function, we
 230 first compute
 231 %
 232 \begin{equation}
 233   q = -\frac{1}{2}\left[\,b+\mathrm{sgn}(b)\sqrt{b^2-4ac}\right]\, .
 234 \end{equation}
 235 %
 236 In case the square root is negative, we only need to take into account
 237 the values at the boundaries. Otherwise we need to take into account
 238 the two solutions
 239 %
 240 \begin{equation}
 241   t_1 = \frac{q}{a} \quad\text{and}\quad t_2 = \frac{c}{q}
 242 \end{equation}
 243 %
 244 Again, for numerical failures (divisions by zero), we just need to skip
 245 the particular solution. The minima and maxima for $x(t)$ can now
 246 occur at $t=0$, $t=t_1$, $t=t_2$ and $t=1$.
 247
 248 % >>>
 249
 250 \section{Replacing B\'ezier curves by straight lines}
 251
 252 % <<<
 253 \begin{figure}
 254 \centerline{\includegraphics{beziertoline}}
 255 \caption{Example for a replacement of a B\'ezier curve by a straight
 256 line.}
 257 \label{fig:beziertoline}
 258 \end{figure}
 259
 260 To solve certain geometrical tasks like measuring the length of a
 261 path or finding intersection points between paths, B\'ezier curves
 262 are recusively reduced to smaller B\'ezier curves by splitting the
 263 curves at the parameter value 0.5 until the parts become almost
 264 straight. Using the notation shown in fig.~\ref{fig:beziertoline} the
 265 straightness is expressed by a length measurement summing up the
 266 distances $\overline{AB}=l_1$, $\overline{BC}=l_2$ and
 267 $\overline{CD}=l_3$ and comparing this to the direct connection
 268 $\overline{AD}$. When the difference becomes smaller than a threshold
 269 $\epsilon$, the curve is adequately expressed by a straight line
 270 either because the curve is almost straight or it is very short.
 271
 272 However, although the geometric changes are limited to distances of
 273 $\epsilon$, the parametrization $t$ of the B\'ezier curve might be
 274 mistakenly represented by the straight line on a much larger scale.
 275 In the shown example, the point $X$ on the straight line and $Y$ on
 276 the B\'ezier curve are both taken at the parameter value $t=0.5$, but
 277 clearly are more separated from each other than one would expect from
 278 the geometric distance of the two paths. While the parametrization on
 279 a line is proportional to the arc length, a non-linear behaviour is
 280 found on a B\'ezier curve. This non-linearity has is originated in
 281 considerably different lengths $l_1$, $l_2$ and $l_3$ and the mapping
 282 of the non-linear parameter to a linear parametrization (in terms of
 283 the arc length) can be reduced to a one-dimensional problem upon an
 284 error $\epsilon$:
 285 %
 286 \begin{equation}
 287   x_0(1-t')+x_3t' = x_0(1-t)^3 + 3x_1t(1-t)^2 + 3x_2t^2(1-t) + x_3 t^3\,.
 288 \end{equation}
 289 %
 290 In this one-dimensional approximation the parameter $t'$ performs a
 291 linear mapping as for any straight line while $t$ represents the usual
 292 B\'ezier curve parametrization. It now becomes a matter of expression
 293 $t$ by $t'$. The polynomial in $t$ to be solved is:
 294 %
 295 \begin{equation}
 296   0 = at^3+bt^2+ct+d
 297 \end{equation}
 298 %
 299 with
 300 %
 301 \begin{align}
 302   a & = x_3-3x_2+3x_1-x_0 = l_1-2l_2+l_3 \\
 303   b & = 3x_0-6x_1+3x_2 = -3l_1+3l_2 \\
 304   c & = 3x_1-3x_0 = 3l_1 \\
 305   d & = t'(x_0-x_3) = -t'(l_1+l_2+l_3)\,.
 306 \end{align}
 307 %
 308 For $0\le t'\le1$ there will be at least one solution $0\le t\le1$.
 309 Several solutions are possible as well, although they should be close
 310 to each other since otherwise the straight line approximation would
 311 not be valid at all.
 312 % >>>
 313
 314 \end{document}
 315
 316 % vim:foldmethod=marker:foldmarker=<<<,>>>