From 7e2f33dd65096a7b28dd753fc2d8d1c12ee3efbc Mon Sep 17 00:00:00 2001 From: Nicola Fontana Date: Sun, 19 Oct 2014 09:25:12 +0200 Subject: [PATCH] doc: correct and simplify baioca algorithm There was a sign error somewhere: I changed and simplified the formulae anyway and the error went away. --- nodist/baioca.tex | 91 +++++++++++++++++++++++++++---------------------------- 1 file changed, 45 insertions(+), 46 deletions(-) diff --git a/nodist/baioca.tex b/nodist/baioca.tex index 073346ee..14e27a26 100644 --- a/nodist/baioca.tex +++ b/nodist/baioca.tex @@ -93,42 +93,41 @@ where $\DV{Q} \equiv \frac{d}{dt} \V{Q}(t)$. Condition 1 implies that \begin{equation}\label{eq:q03} \begin{aligned}[t] - \V{Q}_0 &= \V{B}_0 + R \frac{\D{B}_{0y}, -\D{B}_{0x}} + \V{Q}_0 &= \V{B}_0 + R \frac{(\D{B}_{0y}, -\D{B}_{0x})} {\| \DV{B}_0 \|};\\ - \V{Q}_3 &= \V{B}_3 + R \frac{\D{B}_{3y}, -\D{B}_{3x}} + \V{Q}_3 &= \V{B}_3 + R \frac{(\D{B}_{3y}, -\D{B}_{3x})} {\| \DV{B}_3 \|}. \end{aligned} \qquad\| \DV{B}_i \| \equiv \sqrt{\D{B}_{ix}^2 + \D{B}_{iy}^2} \end{equation} -Condition 2 implies that $\DV{Q}(0) \parallel \DV{B}(0)$ and that -$\DV{Q}(1) \parallel \DV{B}(1)$. -Given that -\begin{equation} -\begin{aligned}[t] - \DV{B}(t) &= 3 \left[ - g_0(t) \Delta \V{B}_0 + - g_1(t) \Delta \V{B}_1 + - g_2(t) \Delta \V{B}_2 - \right]; \\ - \DV{Q}(0) &= 3 ( \V{Q}_1 - \V{Q}_0 ) = 3 \Delta{\V{B}_0}; \\ - \DV{Q}(1) &= 3 ( \V{Q}_2 - \V{Q}_3 ) = -3 \Delta{\V{B}_2}; -\end{aligned} -\qquad\Delta \V{B}_i \equiv \V{B}_{i+1} - \V{B}_i +Condition 2 implies that $\DV{Q}_0 = \DV{B}_0$ and +$\DV{Q}_3 = \DV{B}_3$. Imposing by convention +\begin{equation}\label{eq:pi} + \V{P}_i = \V{B}_{i+1} - \V{B}_i; \qquad i = 0, 1, 2; \end{equation} -condition 2 is hence equivalent to +we can calculate $\DV{B}_0$ and $\DV{B}_3$ directly from the hodograph +of $\V{B}(t)$: +\begin{align*} + \DV{B}(t) &= 3 \left[ (1-t) \V{P}_0 + 2t(1-t) \V{P}_1 + t \V{P}_2 \right]; \\ + \DV{B}(0) &= 3 \V{P}_0 \equiv \DV{B}_0 = \DV{Q}_0; \\ + \DV{B}(1) &= 3 \V{P}_2 \equiv \DV{B}_3 = \DV{Q}_3. +\end{align*} +Knowing that one of the properties of a Bézier curve is the start of the +curve is tangent to the first section of the control polygon and the end +is tangent to the last section, condition 2 is hence equivalent to: \begin{equation}\label{eq:q12} \begin{aligned}[t] - \V{Q}_1 &= \V{Q}_0 + r \Delta \V{B}_0; \\ - \V{Q}_2 &= \V{Q}_3 - s \Delta \V{B}_2. + \V{Q}_1 &= \V{Q}_0 + \frac{r}{3} \DV{Q}_0 = \V{Q}_0 + r \V{P}_0; \\ + \V{Q}_2 &= \V{Q}_3 + \frac{s}{3} \DV{Q}_3 = \V{Q}_3 + s \V{P}_2. \end{aligned} \qquad r, s \in \mathbb{R} \end{equation} Substituting \eqref{eq:q12} in \eqref{eq:q} we get \begin{equation*} -\V{Q}(t) = b_0(t) \V{Q}_0 + b_1(t) \V{Q}_0 + b_1(t) r \Delta \V{B}_0 + -b_2(t) \V{Q}_3 - b_2(t) s \Delta \V{B}_2 + b_3(t) \V{Q}_3. +\V{Q}(t) = b_0(t) \V{Q}_0 + b_1(t) \V{Q}_0 + b_1(t) r \V{P}_0 + +b_2(t) \V{Q}_3 + b_2(t) s \V{P}_2 + b_3(t) \V{Q}_3. \end{equation*} Determine the value of $r$ and $s$ that minimizes the quantity @@ -141,27 +140,29 @@ solve the system \end{dcases} \end{equation*} -Now, given the shortcuts $\sum \equiv \sum_{i=0}^{n} $ and $b_j \equiv -b_j(t_i)$, we can write $\phi$ as +Now, given the shortcuts\footnote{Either $C_0$ and $C_n$ are not +considered because they have been already used as $Q_0$ and $Q_3$ by the +interpolation constraint.} $\sum \equiv \sum_{i=1}^{n-1}$ and +$b_j \equiv b_j(t_i)$, we can write $\phi$ as \begin{equation*} \phi(r, s) = \sum \left[ \V{C}_i - b_0 \V{Q}_0 - b_1 \V{Q}_0 - - r b_1 \Delta \V{B}_0 - b_2 \V{Q}_3 + s b_2 \Delta \V{B}_2 - b_3 \V{Q}_3 \right]^2; + r b_1 \V{P}_0 - b_2 \V{Q}_3 - s b_2 \V{P}_2 - b_3 \V{Q}_3 \right]^2; \end{equation*} that, applied to the previous system, bring us to the following linear system \begin{equation*} \begin{dcases} - 2 \sum \left( - \V{C}_i - b_0 \V{Q}_0 - b_1 \V{Q}_0 - r b_1 \Delta \V{B}_0 - - b_2 \V{Q}_3 + s b_2 \Delta \V{B}_2 - b_3 \V{Q}_3 - \right) \left( b_1 \Delta \V{B}_0 \right) &= 0; \\ - 2 \sum \left( - \V{C}_i - b_0 \V{Q}_0 - b_1 \V{Q}_0 - r b_1 \Delta \V{B}_0 - - b_2 \V{Q}_3 + s b_2 \Delta \V{B}_2 - b_3 \V{Q}_3 - \right) \left( -b_2 \Delta \V{B}_2 \right) &= 0; \\ + \sum \left( + \V{C}_i - b_0 \V{Q}_0 - b_1 \V{Q}_0 - r b_1 \V{P}_0 - + b_2 \V{Q}_3 - s b_2 \V{P}_2 - b_3 \V{Q}_3 + \right) \left( -2 b_1 \V{P}_0 \right) &= 0; \\ + \sum \left( + \V{C}_i - b_0 \V{Q}_0 - b_1 \V{Q}_0 - r b_1 \V{P}_0 - + b_2 \V{Q}_3 - s b_2 \V{P}_2 - b_3 \V{Q}_3 + \right) \left( -2 b_2 \V{P}_2 \right) &= 0; \\ \end{dcases} \end{equation*} -from which, considering $\V{P}_i \equiv \Delta \V{B}_i$, we get +from which we get \begin{equation*} \begin{dcases} \sum \left( @@ -170,7 +171,7 @@ from which, considering $\V{P}_i \equiv \Delta \V{B}_i$, we get b_0 b_1 \SP{\V{Q}_0}{\V{P}_0} - b_1 b_1 \SP{\V{Q}_0}{\V{P}_0} - r b_1 b_1 \SP{\V{P}_0}{\V{P}_0} \\ - - b_1 b_2 \SP{\V{Q}_3}{\V{P}_0} + + b_1 b_2 \SP{\V{Q}_3}{\V{P}_0} - s b_1 b_2 \SP{\V{P}_2}{\V{P}_0} - b_1 b_3 \SP{\V{Q}_3}{\V{P}_0} \end{split} @@ -181,7 +182,7 @@ from which, considering $\V{P}_i \equiv \Delta \V{B}_i$, we get b_0 b_2 \SP{\V{Q}_0}{\V{P}_2} - b_1 b_2 \SP{\V{Q}_0}{\V{P}_2} - r b_1 b_2 \SP{\V{P}_0}{\V{P}_2} \\ - - b_2 b_2 \SP{\V{Q}_3}{\V{P}_2} + + b_2 b_2 \SP{\V{Q}_3}{\V{P}_2} - s b_2 b_2 \SP{\V{P}_2}{\V{P}_2} - b_2 b_3 \SP{\V{Q}_3}{\V{P}_2} \end{split} @@ -204,7 +205,7 @@ we can substitute to get D_0 - E_{01} \SP{\V{Q}_0}{\V{P}_0} - E_{11} \SP{\V{Q}_0}{\V{P}_0} - r E_{11} \SP{\V{P}_0}{\V{P}_0} - - E_{12} \SP{\V{Q}_3}{\V{P}_0} \\ + + E_{12} \SP{\V{Q}_3}{\V{P}_0} \\ - s E_{12} \SP{\V{P}_2}{\V{P}_0} - E_{13} \SP{\V{Q}_3}{\V{P}_0} &= 0; \end{split} \\ @@ -212,7 +213,7 @@ we can substitute to get D_2 - E_{02} \SP{\V{Q}_0}{\V{P}_2} - E_{12} \SP{\V{Q}_0}{\V{P}_2} - r E_{12} \SP{\V{P}_0}{\V{P}_2} - - E_{22} \SP{\V{Q}_3}{\V{P}_2} \\ + + E_{22} \SP{\V{Q}_3}{\V{P}_2} \\ - s E_{22} \SP{\V{P}_2}{\V{P}_2} - E_{23} \SP{\V{Q}_3}{\V{P}_2} &= 0; \end{split} \\ @@ -221,11 +222,9 @@ we can substitute to get and derive the following known terms \begin{equation}\label{eq:ACD} \begin{aligned}[t] -A_1 &= D_0 - - \SP{\V{Q}_0}{\V{P}_0} (E_{01} + E_{11}) - +A_1 &= D_0 - \SP{\V{Q}_0}{\V{P}_0} (E_{01} + E_{11}) - \SP{\V{Q}_3}{\V{P}_0} (E_{12} + E_{13}); \\ -A_2 &= D_2 - - \SP{\V{Q}_0}{\V{P}_2} (E_{02} + E_{12}) - +A_2 &= D_2 - \SP{\V{Q}_0}{\V{P}_2} (E_{02} + E_{12}) - \SP{\V{Q}_3}{\V{P}_2} (E_{22} + E_{23}); \\ A_3 &= \SP{\V{P}_0}{\V{P}_0} E_{11}; \\ A_4 &= \SP{\V{P}_0}{\V{P}_2} E_{12}; \\ @@ -236,15 +235,15 @@ A_5 &= \SP{\V{P}_2}{\V{P}_2} E_{22}. \\ The system is hence reduced to \begin{equation*} \begin{dcases} - s A_4 - r A_3 &= A_1; \\ - s A_5 - r A_4 &= A_2; \\ + r A_3 + s A_4 &= A_1; \\ + r A_4 + s A_5 &= A_2; \\ \end{dcases} \end{equation*} from which we can calculate $r$ and $s$ \begin{equation}\label{eq:rs} \begin{aligned}[t] - r &= \frac{A_2 A_4 - A_1 A_5}{A_3 A_5 - A_4 A_4}; \\ - s &= \frac{A_2 A_3 - A_1 A_4}{A_3 A_5 - A_4 A_4}. \\ + r &= \frac{A_1 A_5 - A_4 A_2}{A_3 A_5 - A_4 A_4}; \\ + s &= \frac{A_3 A_2 - A_1 A_4}{A_3 A_5 - A_4 A_4}. \\ \end{aligned} \end{equation} @@ -253,7 +252,7 @@ from which we can calculate $r$ and $s$ \begin{enumerate} \item Select $\{t_i\}_{i=0}^n$ as shown in section~\ref{sec:ti}; \item get $\V{Q}_0$ and $\V{Q}_3$ from \eqref{eq:q03}; - \item calculate $\V{P}_0$ and $\V{P}_2$; + \item calculate $\V{P}_0$ and $\V{P}_2$ with \eqref{eq:pi}; \item compute $\{\V{C}_i\}_{i=0}^n$ with \eqref{eq:Ci}; \item calculate $D_0$, $D_2$, $E_{01}$, $E_{02}$, $E_{11}$, $E_{12}$, $E_{13}$, $E_{22}$ and $E_{23}$ with \eqref{eq:DE}; -- 2.11.4.GIT