nodist/baioca.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{B.A.I.O.C.A.}
  16 \subtitle{Bare Attempt to Improve Offset Curve Algorithm}
  17 \author{Giandomenico Rossi \and Nicola Fontana}
  18 \date{April 16, 2013}
  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 Computer Aided Design (CAD) and related software is often based on cubic
  37 Bézier curves: the Postscript language and consecuentely the PDF file
  38 format are two widespread examples of such software. Defining an optimal
  39 algorithm for approximating a Bézier curve parallel to the original one
  40 at a specific distance (the so called ``offset curve'') is a big
  41 requirement in CAD drafting: it is heavily used while constructing
  42 derived entities (e.g., a fillet) or to express machining allowance.
  43
  44 This document describes an algorithm suitable for CAD purposes. In those
  45 cases, the starting and ending points of the offset curve \textbf{must}
  46 have coordinates and slopes coincident with the perfect solution, so the
  47 continuity with previous and next offseted entity is preserved.
  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) = b_0(t)\V{B}_0 + b_1(t)\V{B}_1 + b_2(t)\V{B}_2 + b_3(t)\V{B}_3
  55 \end{equation*}
  56 where
  57 \begin{equation*}
  58 \begin{aligned}[t]
  59 \V{B}_i &\equiv ( B^i_x, B^i_y ) \in \mathbb{R}; \\
  60 b_i(t)  &\equiv \binom{3}{i} t^i (1-t)^{3-i}. \\
  61 \end{aligned}
  62 \qquad i = 0,1,2,3
  63 \end{equation*}
  64
  65 Given in $\{t_i\}_{i=0}^n$ a set of values for $t$ chosen in some
  66 manner with $t_0=0, t_n=1$ and in $R$ the required distance of the offset
  67 curve,
  68 \begin{equation}\label{eq:Ci}
  69 \V{C}_i = \V{B}(t_i) + R \left.
  70 \frac{\D{B}_y, -\D{B}_x}{\sqrt{\D{B}_x^2 + \D{B}_y^2}}
  71     \,\right|_{t=t_i} \forall t_i
  72 \end{equation}
  73 is the equation of the offset curve that has in $\{\V{C}_i\}_{i=0}^n$ the
  74 set of its points and where $\DV{B} \equiv ( \D{B}_x, \D{B}_y ) \equiv
  75 \left( \frac{d}{dt} B_x(t), \frac{d}{dt} B_y(t) \right)$.
  76
  77 We must find the Bézier curve
  78 \begin{equation}\label{eq:q}
  79 \V{Q}(t) = b_0(t) \V{Q}_0 + b_1(t) \V{Q}_1 + b_2(t) \V{Q}_2 + b_3(t) \V{Q}_3
  80 \end{equation}
  81 where
  82 \begin{equation*}
  83 \V{Q}_i \equiv ( Q^i_x, Q^i_y ) \in \mathbb{R} \qquad i = 0,1,2,3
  84 \end{equation*}
  85 which best fits \eqref{eq:Ci} within the needed constraints, that is:
  86 \begin{enumerate}
  87 \item $\V{Q}(0) = \V{C}_0$ and $\V{Q}(1) = \V{C}_n$ (interpolation);
  88 \item $\DV{Q}(0) = \DV{B}(0)$ and $\DV{Q}(1) = \DV{B}(1)$ (tangents),
  89 where $\DV{Q} \equiv \frac{d}{dt} \V{Q}(t)$.
  90 \end{enumerate}
  91
  92 \medskip
  93 Condition 1 implies that $\V{Q}_0 = \V{C}_1$ and $\V{Q}_3 = \V{C}_n$.
  94
  95 Condition 2 implies that $\DV{Q}_0 = \DV{B}_0$ and
  96 $\DV{Q}_3 = \DV{B}_3$. Imposing by convention
  97 \begin{equation}\label{eq:pi}
  98     \V{P}_i = \V{B}_{i+1} - \V{B}_i; \qquad i = 0, 1, 2;
  99 \end{equation}
 100 we can calculate $\DV{B}_0$ and $\DV{B}_3$ directly from the hodograph
 101 of $\V{B}(t)$:
 102 \begin{align*}
 103     \DV{B}(t) &= 3 \left[ (1-t)^2 \V{P}_0 + 2t(1-t) \V{P}_1 + t^2 \V{P}_2 \right]; \\
 104     \DV{B}(0) &= 3 \V{P}_0 \equiv \DV{B}_0 = \DV{Q}_0; \\
 105     \DV{B}(1) &= 3 \V{P}_2 \equiv \DV{B}_3 = \DV{Q}_3.
 106 \end{align*}
 107 Knowing that one of the properties of a Bézier curve is the start of the
 108 curve is tangent to the first section of the control polygon and the end
 109 is tangent to the last section, condition 2 is hence equivalent to:
 110 \begin{equation}\label{eq:q12}
 111 \begin{aligned}[t]
 112     \V{Q}_1 &= \V{Q}_0 + \frac{r}{3} \DV{Q}_0 = \V{Q}_0 + r \V{P}_0; \\
 113     \V{Q}_2 &= \V{Q}_3 + \frac{s}{3} \DV{Q}_3 = \V{Q}_3 + s \V{P}_2.
 114 \end{aligned}
 115 \qquad r, s \in \mathbb{R}
 116 \end{equation}
 117
 118 Substituting \eqref{eq:q12} in \eqref{eq:q} we get
 119 \begin{equation*}
 120 \V{Q}(t) = b_0(t) \V{Q}_0 + b_1(t) \V{Q}_0 + b_1(t) r \V{P}_0 +
 121 b_2(t) \V{Q}_3 + b_2(t) s \V{P}_2 + b_3(t) \V{Q}_3.
 122 \end{equation*}
 123
 124 Determine the value of $r$ and $s$ that minimizes the quantity
 125 $\phi = \sum \left[ \V{C}_i - \V{Q}(t_i) \right]^2$, equivalent to
 126 solve the system
 127 \begin{equation*}
 128 \begin{dcases}
 129 \frac{\delta\phi}{\delta r} = 0;\\
 130 \frac{\delta\phi}{\delta s} = 0.
 131 \end{dcases}
 132 \end{equation*}
 133
 134 Now, given the shortcuts\footnote{Either $i = 0$ and $i = n$ are not
 135 considered because $\V{C}_0$ and $\V{C}_n$ have been already used as
 136 $\V{Q}_0$ and $\V{Q}_3$ by the interpolation constraint.} $\sum \equiv
 137 \sum_{i=1}^{n-1}$ and $b_j \equiv b_j(t_i)$, we can write $\phi$ as
 138 \begin{equation*}
 139     \phi(r, s) = \sum \left[ \V{C}_i - b_0 \V{Q}_0 - b_1 \V{Q}_0 -
 140     r b_1 \V{P}_0 - b_2 \V{Q}_3 - s b_2 \V{P}_2 - b_3 \V{Q}_3 \right]^2;
 141 \end{equation*}
 142
 143 that, applied to the previous system, bring us to the following linear system
 144 \begin{equation*}
 145 \begin{dcases}
 146     \sum \left(
 147         \V{C}_i - b_0 \V{Q}_0 - b_1 \V{Q}_0 - r b_1 \V{P}_0 -
 148         b_2 \V{Q}_3 - s b_2 \V{P}_2 - b_3 \V{Q}_3
 149     \right) \left( -2 b_1 \V{P}_0 \right) &= 0; \\
 150     \sum \left(
 151         \V{C}_i - b_0 \V{Q}_0 - b_1 \V{Q}_0 - r b_1 \V{P}_0 -
 152         b_2 \V{Q}_3 - s b_2 \V{P}_2 - b_3 \V{Q}_3
 153     \right) \left( -2 b_2 \V{P}_2 \right) &= 0; \\
 154 \end{dcases}
 155 \end{equation*}
 156 from which we get
 157 \begin{equation*}
 158 \begin{dcases}
 159     \sum \left(
 160     \begin{split}
 161         b_1       \SP{\V{C}_i}{\V{P}_0} -
 162         b_0 b_1   \SP{\V{Q}_0}{\V{P}_0} -
 163         b_1 b_1   \SP{\V{Q}_0}{\V{P}_0} -
 164         r b_1 b_1 \SP{\V{P}_0}{\V{P}_0} \\ -
 165         b_1 b_2   \SP{\V{Q}_3}{\V{P}_0} -
 166         s b_1 b_2 \SP{\V{P}_2}{\V{P}_0} -
 167         b_1 b_3   \SP{\V{Q}_3}{\V{P}_0}
 168     \end{split}
 169     \right) &= 0; \\
 170     \sum \left(
 171     \begin{split}
 172         b_2       \SP{\V{C}_i}{\V{P}_2} -
 173         b_0 b_2   \SP{\V{Q}_0}{\V{P}_2} -
 174         b_1 b_2   \SP{\V{Q}_0}{\V{P}_2} -
 175         r b_1 b_2 \SP{\V{P}_0}{\V{P}_2} \\ -
 176         b_2 b_2   \SP{\V{Q}_3}{\V{P}_2} -
 177         s b_2 b_2 \SP{\V{P}_2}{\V{P}_2} -
 178         b_2 b_3   \SP{\V{Q}_3}{\V{P}_2}
 179     \end{split}
 180     \right) &= 0. \\
 181 \end{dcases}
 182 \end{equation*}
 183
 184 Given the additional conventions
 185 \begin{equation}\label{eq:DE}
 186 \begin{aligned}[t]
 187     D_0 &\equiv \sum b_1 \SP{\V{C}_i}{\V{P}_0}; \\
 188     D_2 &\equiv \sum b_2 \SP{\V{C}_i}{\V{P}_2}; \\
 189     E_{jk} &\equiv \sum b_j b_k;
 190 \end{aligned}
 191 \end{equation}
 192 we can substitute to get
 193 \begin{equation*}
 194 \begin{dcases}
 195 \begin{split}
 196     D_0 - E_{01}   \SP{\V{Q}_0}{\V{P}_0} -
 197           E_{11}   \SP{\V{Q}_0}{\V{P}_0} -
 198           r E_{11} \SP{\V{P}_0}{\V{P}_0} -
 199           E_{12}   \SP{\V{Q}_3}{\V{P}_0} \\ -
 200           s E_{12} \SP{\V{P}_2}{\V{P}_0} -
 201           E_{13}   \SP{\V{Q}_3}{\V{P}_0} &= 0;
 202 \end{split} \\
 203 \begin{split}
 204     D_2 - E_{02}   \SP{\V{Q}_0}{\V{P}_2} -
 205           E_{12}   \SP{\V{Q}_0}{\V{P}_2} -
 206           r E_{12} \SP{\V{P}_0}{\V{P}_2} -
 207           E_{22}   \SP{\V{Q}_3}{\V{P}_2} \\ -
 208           s E_{22} \SP{\V{P}_2}{\V{P}_2} -
 209           E_{23}   \SP{\V{Q}_3}{\V{P}_2} &= 0;
 210 \end{split} \\
 211 \end{dcases}
 212 \end{equation*}
 213 and derive the following known terms
 214 \begin{equation}\label{eq:ACD}
 215 \begin{aligned}[t]
 216 A_1 &= D_0 - \SP{\V{Q}_0}{\V{P}_0} (E_{01} + E_{11}) -
 217     \SP{\V{Q}_3}{\V{P}_0} (E_{12} + E_{13}); \\
 218 A_2 &= D_2 - \SP{\V{Q}_0}{\V{P}_2} (E_{02} + E_{12}) -
 219     \SP{\V{Q}_3}{\V{P}_2} (E_{22} + E_{23}); \\
 220 A_3 &= \SP{\V{P}_0}{\V{P}_0} E_{11}; \\
 221 A_4 &= \SP{\V{P}_0}{\V{P}_2} E_{12}; \\
 222 A_5 &= \SP{\V{P}_2}{\V{P}_2} E_{22}. \\
 223 \end{aligned}
 224 \end{equation}
 225
 226 The system is hence reduced to
 227 \begin{equation*}
 228 \begin{dcases}
 229     r A_3 + s A_4 &= A_1; \\
 230     r A_4 + s A_5 &= A_2; \\
 231 \end{dcases}
 232 \end{equation*}
 233 from which we can calculate $r$ and $s$
 234 \begin{equation}\label{eq:rs}
 235 \begin{aligned}[t]
 236     r &= \frac{A_1 A_5 - A_4 A_2}{A_3 A_5 - A_4 A_4}; \\
 237     s &= \frac{A_3 A_2 - A_1 A_4}{A_3 A_5 - A_4 A_4}. \\
 238 \end{aligned}
 239 \end{equation}
 240
 241 \section{Algorithm}
 242
 243 \begin{enumerate}
 244     \item Select $\{t_i\}_{i=0}^n$ as shown in section~\ref{sec:ti};
 245     \item compute $\{\V{C}_i\}_{i=0}^n$ with \eqref{eq:Ci}:
 246         $\V{Q}_0 = \V{C}_0$ and $\V{Q}_3 = \V{C}_n$;
 247     \item calculate $\V{P}_0$ and $\V{P}_2$ with \eqref{eq:pi};
 248     \item calculate $D_0$, $D_2$, $E_{01}$, $E_{02}$, $E_{11}$,
 249         $E_{12}$, $E_{13}$, $E_{22}$ and $E_{23}$ with \eqref{eq:DE};
 250     \item calculate $A_1$, $A_2$, $A_3$, $A_4$ and $A_5$ with
 251         \eqref{eq:ACD};
 252     \item calculate $r$ and $s$ with \eqref{eq:rs};
 253     \item get $\V{Q}_1$ and $\V{Q}_2$ from \eqref{eq:q12}.
 254 \end{enumerate}
 255
 256 $\V{Q}_0$ and $\V{Q}_3$ are respectively the starting and ending
 257 points of the offset Bézier curve while $\V{Q}_1$ and $\V{Q}_2$ are
 258 its control points.
 259
 260 \clearpage
 261 \section{Choosing $t_i$\label{sec:ti}}
 262
 263 To select the $\{t_i\}_{i=0}^n$ set of values for $t$ needed by
 264 the offsetting algorithm, we can use different methods. Here are some
 265 basic ones: no further research is performed to check the quality of
 266 the results.
 267
 268 \subsection{Method 1: too lazy to think}
 269
 270 The most obvious method is to directly use evenly spaced time values:
 271
 272 \begin{equation*}
 273     t_i = \frac{i}{n}.
 274 \end{equation*}
 275
 276 \subsection{Method 2: squared distances}
 277
 278 Let's select some $\{\V{F}_i\}_{i=0}^n$ points on $\V{B}(t)$, for
 279 instance by resolving the $t$ values got from the lazy method. The
 280 following formula will partition the Bézier curve proportionally to
 281 their squared distances:
 282
 283 \begin{equation*}
 284 \begin{aligned}[t]
 285     t_0 &= 0; \\
 286     t_i &= t_{i-1} + \frac{\left( \V{F}_i - \V{F}_{i-1} \right)^2}{f}.
 287 \end{aligned}
 288 \qquad f = \sum_{i=1}^n \left( \V{F}_i - \V{F}_{i-1} \right)^2
 289 \end{equation*}
 290
 291 \subsection{Method 3: distances}
 292
 293 A variant of the previous method that uses distances instead of squared
 294 distances. This is computationally more intensive because the norm of
 295 a vector $\| \V{F} \| \equiv \sqrt{F_x^2 + F_y^2}$ requires a square
 296 root.
 297
 298 \begin{equation*}
 299 \begin{aligned}[t]
 300     t_0 &= 0; \\
 301     t_i &= t_{i-1} + \frac{\| \V{F}_i - \V{F}_{i-1} \|}{f}.
 302 \end{aligned}
 303 \qquad f = \sum_{i=1}^n \| \V{F}_i - \V{F}_{i-1} \|
 304 \end{equation*}
 305
 306 \end{document}