nodist/saiot.tex

   1 \documentclass{scrartcl}
   2 \usepackage{amsmath,amssymb,mathtools}
   3 \usepackage[english]{babel}
   4
   5 % Allow to build the PDF with either lualatex (preferred) or pdflatex
   6 \usepackage{iftex}
   7 \ifLuaTeX
   8     \usepackage{luatextra}
   9 \else
  10     \usepackage[T1]{fontenc}
  11     \usepackage[utf8]{inputenc}
  12     \usepackage{lmodern}
  13 \fi
  14
  15 \title{S.A.I.O.T.}
  16 \subtitle{Second Attempt to Improve the Offset Theory}
  17 \author{Giandomenico Rossi \and Nicola Fontana}
  18 \date{Oct 29, 2014}
  19
  20 \DeclarePairedDelimiter\abs{\lvert}{\rvert}%
  21 \DeclarePairedDelimiter\norm{\lVert}{\rVert}%
  22
  23 \setlength\parindent{0pt}
  24 \setlength\parskip{6pt}
  25
  26 \newcommand\V[1]{\vec{#1}}
  27 \newcommand\D[1]{\dot{#1}}
  28 \newcommand\DV[1]{\D{\V{#1}}}
  29 \newcommand\SP[2]{\langle #1, #2 \rangle}
  30
  31 \begin{document}
  32
  33 \maketitle
  34
  35 \begin{abstract}
  36 The results given by the BAIOCA algorithm in offsetting Bézier cubic
  37 curves are clearly suboptimal. The fact that it minimizes the mean
  38 square error between the original curve and the offset curve at the same
  39 time value poses an artifical constraint (that \textbf{same time value}
  40 thingy) that invalidate the whole theory. The optimal offset curve does
  41 not necessarily need to have its own offset points at the same time
  42 value of the original curve, and the fact that increasing the number of
  43 samples decreases the quality of the approximation given by BAIOCA seems
  44 to confirm that this is rarely the case.
  45
  46 This algorithm explores a new way to solve the system that uses
  47 constraints not tied to the same time value.
  48 \end{abstract}
  49
  50 \section{Mathematic}
  51
  52 The generic formula for a cubic Bézier curve is
  53 \begin{equation*}
  54     \V{B}(t) =
  55         (1-t)^3 \V{B}_0 +
  56         3t (1-t)^2 \V{B}_1 +
  57         3t^2 (1-t) \V{B}_2 +
  58         t^3 \V{B}_3,
  59     \qquad t \in [ 0,1 ]
  60 \end{equation*}
  61 where $\V{B}_i \equiv ( B_{ix}, B_{iy} ) \in \mathbb{R} |_{i = 0,1,2,3}$
  62 are known terms.
  63
  64 Let's call $\V{C}(t)$ the function that returns the offset of
  65 $\V{B}(t)$ at the specific distance $R$, that is
  66 \begin{equation}\label{eq:C}
  67 \V{C}(t) = \V{B}(t) + R
  68     \frac{(\D{B}(t)_y, -\D{B}(t)_x)}{\sqrt{\D{B}(t)_x^2 + \D{B}(t)_y^2}},
  69     \qquad t \in [ 0,1 ]
  70 \end{equation}
  71 where $\DV{B}(t) \equiv ( \D{B}(t)_x, \D{B}(t)_y ) \equiv \left( \frac{d}{dt}
  72 B_x(t), \frac{d}{dt} B_y(t) \right)$.
  73
  74 We must find a Bézier curve
  75 \begin{equation}\label{eq:Q}
  76     \V{Q}(t) =
  77         (1-t)^3 \V{Q}_0 +
  78         3t (1-t)^2 \V{Q}_1 +
  79         3t^2 (1-t) \V{Q}_2 +
  80         t^3 \V{Q}_3
  81 \end{equation}
  82 where $\V{Q}_i \equiv ( Q_{ix}, Q_{iy} ) \in \mathbb{R} |_{i = 0,1,2,3}$
  83 are the terms that must be found.
  84
  85 The offset curve must respect the constraints described in the abstract
  86 of the BAIOCA algorithm, that is
  87 \begin{enumerate}
  88 \item $\V{Q}(0) = \V{C}(0)$ and $\V{Q}(1) = \V{C}(1)$ (interpolation);
  89 \item $\DV{Q}(0) = \DV{B}(0)$ and $\DV{Q}(1) = \DV{B}(1)$ (tangents),
  90 where $\DV{Q}(t) \equiv \frac{d}{dt} \V{Q}(t)$.
  91 \end{enumerate}
  92
  93 \medskip
  94 Condition 1 implies that $\V{Q}_0$ and $\V{Q}_3$ can be calculated by
  95 directly using \eqref{eq:C}.
  96
  97 Condition 2 implies that $\DV{Q}_0 = \DV{B}_0$ and
  98 $\DV{Q}_3 = \DV{B}_3$. Imposing by convention
  99 \begin{equation}\label{eq:pi}
 100     \V{P}_i = \V{B}_{i+1} - \V{B}_i, \qquad i = 0, 1, 2
 101 \end{equation}
 102 we can calculate $\DV{B}_0$ and $\DV{B}_3$ directly from the hodograph
 103 of $\V{B}(t)$:
 104 \begin{align*}
 105     \DV{B}(t) &= 3 \left[ (1-t)^2 \V{P}_0 + 2t(1-t) \V{P}_1 + t^2 \V{P}_2 \right]; \\
 106     \DV{B}(0) &= 3 \V{P}_0 \equiv \DV{B}_0 = \DV{Q}_0 \\
 107     \DV{B}(1) &= 3 \V{P}_2 \equiv \DV{B}_3 = \DV{Q}_3.
 108 \end{align*}
 109 Knowing that one of the properties of a Bézier curve is the start of the
 110 curve is tangent to the first section of the control polygon and the end
 111 is tangent to the last section, condition 2 is hence equivalent to:
 112 \begin{equation*}
 113 \begin{aligned}[t]
 114     \V{Q}_1 &= \V{Q}_0 + \frac{r}{3} \DV{Q}_0 = \V{Q}_0 + r \V{P}_0, \\
 115     \V{Q}_2 &= \V{Q}_3 + \frac{s}{3} \DV{Q}_3 = \V{Q}_3 + s \V{P}_2.
 116 \end{aligned}
 117 \qquad r, s \in \mathbb{R}
 118 \end{equation*}
 119
 120 Substituting in \eqref{eq:Q} we get
 121 \begin{equation}\label{eq:QQ}
 122     \V{Q}(t) =
 123         (1-t)^3 \V{Q}_0 +
 124         3t (1-t)^2 ( \V{Q}_0 + r \V{P}_0 ) +
 125         3t^2 (1-t) ( \V{Q}_3 + s \V{P}_2 ) +
 126         t^3\V{Q}_3.
 127 \end{equation}
 128
 129 The hodograph of $\V{Q}(t)$ is then
 130 \begin{equation}\label{eq:QD}
 131     \DV{Q}(t) = 3 \left[
 132         (1-t)^2 r \V{P}_0 +
 133         2t(1-t) (\V{Q}_3 + s \V{P}_2 - \V{Q}_0 - r \V{P}_0) -
 134         t^2 s \V{P}_2
 135     \right].
 136 \end{equation}
 137
 138 We must find a couple of values for $r$ and $s$ that gives us a decent
 139 offset curve in most situations. Put in other words, we need to impose
 140 some additional constraint to be able to solve the system.
 141
 142 Let consider a generic point in $\V{B}(t)$ at $t=m$ (where $m$ is chosen
 143 in some manner, typically $0.5$). Let impose that the offset curve passes
 144 throught $\V{C}(m)$ and let call $u$ the $t$ value\footnote{$m \neq u$
 145 is the original assumption that supposedly gives better results than the
 146 BAIOCA algorithm.} in which $\V{Q}(t) = \V{C}(m)$. Then, let impose the
 147 derivative in $\V{Q}(u)$ is equal to the derivative in $\V{B}(m)$.
 148
 149 The above constraints can be expressed by the following system with 4
 150 equations and 3 variables ($r$, $s$ and $u$).
 151 \begin{equation*}
 152 \begin{dcases}
 153     \V{Q}(u) = \V{B}(m)\\
 154     \DV{Q}(u) = \DV{B}(m).
 155 \end{dcases}
 156 \end{equation*}
 157
 158 The second condition, according to \eqref{eq:QD}, is equivalent to
 159 \begin{equation*}
 160 \begin{aligned}
 161     (1-u)^2 r \V{P}_0 +
 162         2u(1-u) (\V{Q}_3 + s \V{P}_2 - \V{Q}_0 - r \V{P}_0) -
 163         u^2 s \V{P}_2 =
 164         \frac{\DV{B}(m)}{3}; \\
 165     3 \V{P}_0 (1-u)(1-3u) r + 3 \V{P}_2 u(2-3u) s =
 166         \DV{B}(m) - 6u(1-u) (\V{Q}_3 - \V{Q}_0).
 167 \end{aligned}
 168 \end{equation*}
 169
 170 By developing the system in $x$ and $y$
 171 \begin{equation*}
 172 \begin{dcases}
 173     3 P_{0x} (1-u) (1-3u) r + 3 P_{2x} u (2-3u) s = \D{B}_x(m) - 6u (1-u) (Q_{3x} - Q_{0x}) \\
 174     3 P_{0y} (1-u) (1-3u) r + 3 P_{2y} u (2-3u) s = \D{B}_y(m) - 6u (1-u) (Q_{3y} - Q_{0y})
 175 \end{dcases}
 176 \end{equation*}
 177 we can find $r$ and $s$ in $u$:
 178 \begin{equation*}
 179 \begin{dcases}
 180     r &= \frac{\D{B}_x(m) P_{2y} - \D{B}_y(m) P_{2x} + 6u (1-u) [ P_{2x} (Q_{3y} - Q_{0y}) - P_{2y} (Q_{3x} - Q_{0x}) ]}
 181         {3 (1-u) (1-3u) ( P_{0x} P_{2y} - P_{2x} P_{0y} )} \\
 182     s &= \frac{\D{B}_y(m) P_{0x} - \D{B}_x(m) P_{0y} + 6u (1-u) [ P_{0y} (Q_{3x} - Q_{0x}) - P_{0x} (Q_{3y} - Q_{0y}) ]}
 183         {3u (2-3u) ( P_{0x} P_{2y} - P_{2x} P_{0y} )}
 184 \end{dcases}
 185 \end{equation*}
 186 from which we derive the following known terms:
 187 \begin{equation}\label{eq:terms}
 188 \begin{aligned}[t]
 189     A_1 &= P_{0x} P_{2y} - P_{2x} P_{0y}; \\
 190     A_2 &= \D{B}_x(m) P_{2y} - \D{B}_y(m) P_{2x}; \\
 191     A_3 &= 6 [ P_{2x} (Q_{3y} - Q_{0y}) - P_{2y} (Q_{3x} - Q_{0x}) ]; \\
 192     A_4 &= \D{B}_y(m) P_{0x} - \D{B}_x(m) P_{0y}; \\
 193     A_5 &= 6 [ P_{0y} (Q_{3x} - Q_{0x}) - P_{0x} (Q_{3y} - Q_{0y}) ].
 194 \end{aligned}
 195 \end{equation}
 196
 197 The above system can hence be rewritten as
 198 \begin{equation}\label{eq:rs}
 199 \begin{dcases}
 200     r &= \frac{A_2 + A_3 u (1-u)}{3 A_1 (1-u) (1-3u)} \\
 201     s &= \frac{A_4 + A_5 u (1-u)}{3 A_1 u (2-3u)}
 202 \end{dcases}
 203 \end{equation}
 204
 205 Now to calculate $u$ we can apply one equation from the first condition.
 206
 207 From \eqref{eq:QQ} we know that
 208 \begin{equation*}
 209     \V{Q}(u) =
 210         (1-u)^3 \V{Q}_0 +
 211         3u (1-u)^2 \V{Q}_0 +
 212         3u^2 (1-u) \V{Q}_3 +
 213         u^3 \V{Q}_3 +
 214         3u (1-u)^2 \V{P}_0 r +
 215         3u^2 (1-u) \V{P}_2 s.
 216 \end{equation*}
 217
 218 Substituting $r$ and $s$ from \eqref{eq:rs} brings us to
 219 \begin{equation*}
 220 \begin{split}
 221     \V{Q}(u) &= (1-u)^3 \V{Q}_0 + 3u (1-u)^2 \V{Q}_0 + u^3 \V{Q}_3 + 3u^2 (1-u) \V{Q}_3 \\
 222      & \quad + u (1-u) \V{P}_0 \frac{A_2 + A_3 u (1-u)}{A_1 (1-3u)}
 223         + u (1-u) \V{P}_2 \frac{A_4 + A_5 u (u-1)}{A_1 (2-3u)}.
 224 \end{split}
 225 \end{equation*}
 226
 227 \end{document}