tests: add basic curve offset testing
[adg.git] / nodist / saiot.tex
blob7f9fd3cd6286b550cb3c9b7eaeb0084d7e407c79
1 \documentclass{scrartcl}
2 \usepackage{amsmath,amssymb,mathtools}
3 \usepackage[english]{babel}
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
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}
20 \DeclarePairedDelimiter\abs{\lvert}{\rvert}%
21 \DeclarePairedDelimiter\norm{\lVert}{\rVert}%
23 \setlength\parindent{0pt}
24 \setlength\parskip{6pt}
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}
31 \begin{document}
33 \maketitle
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.
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}
50 \section{Mathematic}
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.
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)$.
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.
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}
93 \medskip
94 Condition 1 implies that $\V{Q}_0$ and $\V{Q}_3$ can be calculated by
95 directly using \eqref{eq:C}.
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*}
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}
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}
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.
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)$.
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*}
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*}
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}
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}
205 Now to calculate $u$ we can apply one equation from the first condition.
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*}
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*}
227 \end{document}