nodist/handcraft.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{Handcraft algorithm}
  16 \subtitle{A disjointed algorithm for offsetting cubic Bézier curves}
  17 \author{Nicola Fontana}
  18 \date{February 25, 2009}
  19
  20 \setlength\parindent{0pt}
  21 \setlength\parskip{6pt}
  22
  23 \begin{document}
  24
  25 \maketitle
  26
  27 \begin{abstract}
  28 This is basically the transcription of the algorithm used by the
  29 ADG canvas on its early development phases. This algorithm has been
  30 superseded in recent releases by BAIOCA. It is included here for
  31 completeness and historical reasons.
  32 \end{abstract}
  33
  34 Given a cubic Bézier primitive, it must be found the approximated
  35 Bézier curve parallel to the original one at a specific distance
  36 (the so called "offset curve"). The four points needed to build
  37 the new curve must be returned.
  38
  39 To solve the offset problem, a custom algorithm is used. First, the
  40 resulting curve MUST have the same slope at the start and end point.
  41 These constraints are not sufficient to resolve the system, so I let
  42 the curve pass thought a given point (r, known and got from the
  43 original curve) at a given time (m, now hardcoded to 0.5).
  44
  45 Firstly, some useful variables are defined:
  46
  47 \begin{equation*}
  48 \begin{split}
  49     v_0 &= \text{unitvector}(\text{p[1]} - \text{p[0]}) \times \text{offset} \\
  50     v_3 &= \text{unitvector}(\text{p[3]} - \text{p[2]}) \times \text{offset} \\
  51     p_0 &= \text{p[0]} + \text{normal}(v_0) \\
  52     p_3 &= \text{p[3]} + \text{normal}(v_3) \\
  53 \end{split}
  54 \end{equation*}
  55
  56 The resulting curve must have the same slopes than the original
  57 one at the start and end points. Forcing the same slopes means:
  58
  59 \begin{equation*}
  60 p_1 = p_0 + k_0 v_0.
  61 \end{equation*}
  62
  63 where $k_0$ is an arbitrary factor. Decomposing for $x$ and $y$:
  64
  65 \begin{equation*}
  66 \begin{dcases}
  67     p_{1x} = p_{0x} + k_0 v_{0x} \\
  68     p_{1y} = p_{0y} + k_0 v_{0y} \\
  69 \end{dcases}
  70 \end{equation*}
  71
  72 and doing the same for the end point:
  73
  74 \begin{equation*}
  75 \begin{dcases}
  76     p_{2x} = p_{3x} + k_3 v_{3x} \\
  77     p_{2y} = p_{3y} + k_3 v_{3y} \\
  78 \end{dcases}
  79 \end{equation*}
  80
  81 This does not give a resolvable system though. The curve will be
  82 interpolated by forcing its path to pass through $r$ when
  83 \textit{time} is $m$, where $0 \leq m \leq 1$. Knowing the function of
  84 the cubic Bézier:
  85
  86 \begin{equation*}
  87 C(t) = (1-t)^3p_0 + 3t(1-t)^2p_1 + 3t^2(1-t)p_2 + t^3p_3.
  88 \end{equation*}
  89
  90 and forcing $t = m$ and $C(t) = r$:
  91
  92 \begin{equation*}
  93 \begin{split}
  94     r &= (1-m)^3 p_0 + 3m(1-m)^2 p_1 + 3m^2 (1-m) p_2 + m^3 p_3 \\
  95     (1-m) p_1 + m p_2 &= \frac{r - (1-m)^3p_0 - m^3p_3}{3m (1-m)} \\
  96 \end{split}
  97 \end{equation*}
  98
  99 brings to the final system:
 100
 101 \begin{equation*}
 102 \begin{dcases}
 103     p_{1x} = p_{0x} + k_0 v_{0x} \\
 104     p_{1y} = p_{0y} + k_0 v_{0y} \\
 105     p_{2x} = p_{3x} + k_3 v_{3x} \\
 106     p_{2y} = p_{3y} + k_3 v_{3y} \\
 107     (1-m) p_{1x} + m p_{2x} = \frac{r_x - (1-m)^3 p_{0x} - m^3 p_{3x}}{3m (1-m)} \\
 108     (1-m) p_{1y} + m p_{2y} = \frac{r_y - (1-m)^3 p_{0y} - m^3 p_{3y}}{3m (1-m)} \\
 109 \end{dcases}
 110 \end{equation*}
 111
 112 Substituting and resolving for $k_0$ and $k_3$:
 113
 114 \begin{equation*}
 115 \begin{dcases}
 116     (1-m) k_0 v_{0x} + m k_3 v_{3x} = \frac{r_x - (1-m)^3 p_{0x} - m^3 p_{3x}}{3m (1-m)} - (1-m) p_{0x} - m p_{3x} \\
 117     (1-m) k_0 v_{0y} + m k_3 v_{3y} = \frac{r_y - (1-m)^3 p_{0y} - m^3 p_{3y}}{3m (1-m)} - (1-m) p_{0y} - m p_{3y} \\
 118 \end{dcases}
 119 \end{equation*}
 120
 121 \begin{equation*}
 122 \begin{dcases}
 123     (1-m) k_0 v_{0x} + m k_3 v_{3x} = \frac{r_x - (1-m)^2 (1+2m) p_{0x} - m^2 (3-2m) p_{3x}}{3m (1-m)} \\
 124     (1-m) k_0 v_{0y} + m k_3 v_{3y} = \frac{r_y - (1-m)^2 (1+2m) p_{0y} - m^2 (3-2m) p_{3y}}{3m (1-m)} \\
 125 \end{dcases}
 126 \end{equation*}
 127
 128 Letting:
 129
 130 \begin{equation*}
 131     s = \frac{r - (1-m)^2(1+2m) p_0 - m^2(3-2m) p_3}{3m (1 - m)}
 132 \end{equation*}
 133
 134 reduces the above to this final equations:
 135
 136 \begin{equation*}
 137 \begin{dcases}
 138     s_x = (1-m) k_0 v_{0x} + m k_3 v_{3x} \\
 139     s_y = (1-m) k_0 v_{0y} + m k_3 v_{3y} \\
 140 \end{dcases}
 141 \end{equation*}
 142
 143 If $v_{0x} \ne; 0$, the system can be resolved for $k_0$ and $k_3$
 144 calculated accordingly:
 145
 146 \begin{equation*}
 147 \begin{dcases}
 148     k_0 = \frac{s_x - m k_3 v_{3x}}{(1-m) v_{0x}} \\
 149     s_y = \frac{(s_x - m k_3 v_{3x}) v_{0y}}{v_{0x}} + m k_3 v_{3y} \\
 150 \end{dcases}
 151 \end{equation*}
 152
 153 \begin{equation*}
 154 \begin{dcases}
 155     k_0 = \frac{s_x - m k_3 v_{3x}}{(1-m) v_{0x}} \\
 156     s_y - \frac{s_x v_{0y}}{v_{0x}} = k_3 m (v_{3y} - \frac{v_{3x} v_{0y}}{v_{0x}}) \\
 157 \end{dcases}
 158 \end{equation*}
 159
 160 \begin{equation*}
 161 \begin{dcases}
 162     k_0 = \frac{s_x - m k_3 v_{3x}}{(1-m) v_{0x}} \\
 163     k_3 = \frac{s_y - s_x \frac{v_{0y}}{v_{0x}}}{m (v_{3y} - v_{3x} \frac{v_{0y}}{v_{0x}})} \\
 164 \end{dcases}
 165 \end{equation*}
 166
 167 Otherwise, if $v_{3x} \ne 0$, the system can be solved for $k_3$ and $k_0$
 168 calculated accordingly:
 169
 170 \begin{equation*}
 171 \begin{dcases}
 172     k_3 = \frac{s_x - (1-m) k_0 v_{0x}}{m v_{3x}} \\
 173     s_y = (1-m) k_0 v_{0y} + \frac{[s_x - (1-m) k_0 v_{0x}] v_{3y}}{v_{3x}} \\
 174 \end{dcases}
 175 \end{equation*}
 176
 177 \begin{equation*}
 178 \begin{dcases}
 179     k_3 = \frac{s_x - (1-m) k_0 v_{0x}}{m v_{3x}} \\
 180     k_0 (1-m) (v_{0y} - k_0 v_{0x} \frac{v_{3y}}{v_{3x}}) = s_y - s_x \frac{v_{3y}}{v_{3x}} \\
 181 \end{dcases}
 182 \end{equation*}
 183
 184 \begin{equation*}
 185 \begin{dcases}
 186     k_3 = \frac{s_x - (1-m) k_0 v_{0x}}{m v_{3x}} \\
 187     k_0 = \frac{s_y - s_x \frac{v_{3y}}{v_{3x}}}{(1-m) (v_{0y} - v_{0x} \frac{v_{3y}}{v_{3x}})} \\
 188 \end{dcases}
 189 \end{equation*}
 190
 191 The whole process must be guarded against division by 0 exceptions.
 192 If either $v_{0x}$ and $v_{3x}$ are 0, the first equation will be
 193 inconsistent. More in general, the
 194 $v_{0x} \times v_{3y} = v_{3x} \times v_{3y}$ condition must be avoided. This is
 195 the first situation to avoid, in which case an alternative approach
 196 should be used.
 197
 198 \end{document}