%$Header$ \chapter[\cdtazeroshorttitle{}]{\cdtazerolongtitle{}} \label{cdta0} \beginchapterquote{``Under construction!''} {Under construction!} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} %Section tag: INT0 \label{cdta0:sint0} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section[Fixed-Period Process Scheduling] {Load Balancing For Fixed-Period Process Scheduling Using Integer Counting} %Section tag: PSI0 \label{cdta0:spsi0} \index{process scheduling!using integer counting}It happens in a variety of contexts in small microcontroller work that one schedules processes (which may be implemented as subroutines or functions) with a fixed period using integer counting. Such scheduling tends to take the form of the code snippet in Figure \ref{fig:cdta0:spsi0:01}. Typically a ``master'' scheduling function is called at a periodic rate, and the scheduled functions are called once every $T_i$ invocations of the master scheduling function ($T_i$ is defined later). Note in the figure that every scheduled function is called with perfect periodicity, but that the invocation sequence can be staggered. Note also in the figure that the comments assume that the scheduling function is called every 10ms (which is typical in microcontroller work). \begin{figure} \begin{small} \begin{verbatim} /* The following "stagger" values are what we are attempting to ** analytically determine at compile-time so as to minimize the ** maximum CPU time used in the worst-case tick. */ #define P1_STAGGER (0) #define P2_STAGGER (0) #define P3_STAGGER (0) /* The periods are fixed and not subject to change. The periods ** are input to any compile-time algorithm employed. */ #define P1_PERIOD (2) /* Every 20ms. */ #define P2_PERIOD (5) /* Every 100ms. */ #define P3_PERIOD (100) /* Every 1000ms = 1 second. */ /* These are the integer counters. Their initial load values, which ** determine the staggering, are the parameters we seek to ** determine. */ static unsigned char p1_ctr = P1_STAGGER; static unsigned char p2_ctr = P2_STAGGER; static unsigned char p3_ctr = P3_STAGGER; /* This is the master scheduling function called every 10ms. It ** calls the periodic functions. Note that this is an integer ** counting problem. */ void master_scheduling_function(void) { p1_ctr++; if (p1_ctr >= P1_PERIOD) { Process_1(); /* Call the process. */ p1_ctr = 0; /* Reset the counter. */ } p2_ctr++; if (p2_ctr >= P2_PERIOD) { Process_2(); /* Call the process. */ p2_ctr = 0; /* Reset the counter. */ } p3_ctr++; if (p3_ctr >= P3_PERIOD) { Process_3(); /* Call the process. */ p3_ctr = 0; /* Reset the counter. */ } } \end{verbatim} \end{small} \caption{Code Snippet Illustrating Fixed-Period Integer Counter Process Scheduling (3 Processes)} \label{fig:cdta0:spsi0:01} \end{figure} It is easy to see from Figure \ref{fig:cdta0:spsi0:01} that it may happen on a single invocation of the master scheduling function that several or all of the processes are scheduled. If the scheduling of the processes is not staggered, this will happen for the first time on the invocation (or ``tick'') corresponding to the least common multiple of all of the periods. In the case of Figure \ref{fig:cdta0:spsi0:01}, $LCM(2,5,100) = 100$, and so on the hundredth invocation of the master scheduling function, all three processes will run. It may be undesirable to run all three processes on the same invocation of the master scheduling function, because this may require a large amount of CPU time. The general question to which we seek an answer is: \emph{How should the stagger values be chosen so as to minimize the maximum amount of CPU time taken on any invocation of the master scheduling function?} We denote the set of $N$ processes that we must schedule by $\{ P_1, P_2, \ldots , P_N \}$. Process $P_i$ has period $T_i$ (measured in invocations or ``ticks'' of the master scheduling function, or ``ticks''). Note that $T_i$ is dimensionless. Each process $P_i$ also has cost $\tau_i$ (the cost is usually the execution time of the function, but could in principle represent any property of interest). Note that there is no required relationship between $\{ T_i \}$ and $\{ \tau_i \}$, as we are not determining schedulability. Thus $\{ \tau_i \}$ may be specified in any time unit, or it may not represent time at all. We agree that each invocation of the master scheduling function is one ``tick'' in discrete time, and that the first invocation of the master scheduling function is denoted $t_1$ or $t=1$. With no staggering ($z_i = 0$) each process $P_i$ will run whenever \begin{equation} \label{eq:cdta0:spsi0:01} t \bmod T_i = 0 . \end{equation} We may modify the invocation sequence of a process $P_i$ by varying a stagger value, which we denote $z_i$. The stagger value specifies by how many ticks we will advance the invocation of $P_i$. When considering stagger values, each process $P_i$ will run whenever \begin{equation} \label{eq:cdta0:spsi0:02} (t + z_i) \bmod T_i = 0 . \end{equation} At each tick, each process $P_i$ is either scheduled to run or not scheduled to run. We define an infinite row vector, called the \emph{uncosted invocation sequence} (or simply the \emph{invocation sequence}) and denoted $\rho_i(z_i)$, which contains a `1' in each column corresponding to a tick when the process $P_i$ run or `0' if it does not run. For example, if $T_1 = 3$, \begin{eqnarray} \nonumber \rho_1 = \rho_1(0) & = & [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] \\ \label{eq:cdta0:spsi0:03} \rho_1(1) & = & [ \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; \ldots \; ] \\ \nonumber \rho_1(2) & = & [ \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; \ldots \; ] \\ \nonumber \rho_1(3) & = & [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] \end{eqnarray} \noindent{}We define but avoid using stagger values $z_i \geq T_i$, but as (\ref{eq:cdta0:spsi0:03}) shows, when it is necessary we define these so that $\rho_i(z_i) = \rho_i(z_i \bmod T_i)$. Also as shown in (\ref{eq:cdta0:spsi0:03}), we use that notation that $\rho_i = \rho_i(0)$. We define the \emph{costed invocation sequence}, denoted $\overline{\rho_i}(z_i)$, as the infinite row vector similar to (\ref{eq:cdta0:spsi0:03}) but where the cost $\tau_i$ is used in place of `1' when a process $P_i$ runs. For example, if $T_1=3$ and $\tau_i = 5$, \begin{eqnarray} \nonumber \overline{\rho_1} = \overline{\rho_1}(0) & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ] \\ \label{eq:cdta0:spsi0:04} \overline{\rho_1}(1) & = & [ \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; \ldots \; ] \\ \nonumber \overline{\rho_1}(2) & = & [ \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; \ldots \; ] \\ \nonumber \overline{\rho_1}(3) & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ] \end{eqnarray} We define the \emph{cost calculation matrix} as the matrix formed by vertically concatenating, in order, the first $LCM(T_1, \ldots , T_N)$ columns of either the uncosted invocation sequence $\rho_i(z_i)$ or the costed invocation sequence $\overline{\rho_i}(z_i)$ of every process in the system; and then appending to this as a row vector the sums of each column. We choose only the first $LCM(T_1, \ldots , T_N)$ columns because the contents of these columns repeat in subsequent columns forever. We denote the cost calculation matrix as $\xi(\mathbf{z})$ (in the case of the uncosted invocation sequences) or as $\overline{\xi}(\mathbf{z})$ (in the case of the costed invocation sequences); where $\mathbf{z}$ is the column vector consisting of all of the staggers $z_i$. Finally, we define the \emph{cost}, denoted $\xi$, as the maximum element from the last row of the cost calculation matrix (it is $\xi$ that we seek to minimize by choosing $\mathbf{z}$). These definitions are illustrated in the following example. \begin{vworkexamplestatement} \label{ex:cdta0:spsi0:01} For the system of 3 processes ($P_1$, $P_2$, and $P_3$) with $T_1=6$, $T_2=4$, $T_3=3$, $\tau_1=2$, $\tau_2=7$, $\tau_3=5$, $z_1 = 2$, $z_2 = 1$, and $z_3 = 0$, form the uncosted and costed invocation sequences, the cost calculation matrices, and the costs. \end{vworkexamplestatement} \begin{vworkexampleparsection}{Solution} We first handle the uncosted case in full, followed by the costed case in full. \textbf{(Uncosted Case):} With $T_1=6$ and $z_1=2$, the first invocation of $P_1$ will occur when $(t + 2) \bmod 6 = 0$ (see Eq. \ref{eq:cdta0:spsi0:02}), at $t=4$, and then repeat with periodicity 6. Thus \begin{equation} \label{eq:ex:cdta0:spsi0:01:01} \rho_1(2) = [ \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 0 \; 0 \; 1 \; 0 \; \ldots \; ] . \end{equation} \noindent{}Applying the same definition for $P_2$ and $P_3$ yields \begin{equation} \label{eq:ex:cdta0:spsi0:01:02} \rho_2(1) = [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] \end{equation} \noindent{}and \begin{equation} \label{eq:ex:cdta0:spsi0:01:03} \rho_3(0) = \rho_3 = [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] . \end{equation} We note that the column vector $\mathbf{z}$ is \begin{equation} \label{eq:ex:cdta0:spsi0:01:04} \mathbf{z} = \left[\begin{array}{c}z_1\\z_2\\z_3\end{array}\right] = \left[\begin{array}{c}2\\1\\0\end{array}\right] . \end{equation} $LCM(T_1, T_2, T_3) = LCM(6, 4, 3) = 12$, and so the cost calculation matrix can be constructed with only 12 columns, since the columns repeat with periodicity 12: \begin{equation} \label{eq:ex:cdta0:spsi0:01:05} \xi(\mathbf{z}) = \xi\left(\left[\begin{array}{c}2\\1\\0\end{array}\right]\right) = \left[ \begin{array}{rrrrrrrrrrrr} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 2 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \end{array} \right] . \end{equation} Note in (\ref{eq:ex:cdta0:spsi0:01:05}) that the last row is the column-wise sum of the rows above it. Note also that the last row gives, on a per tick basis, the number of processes that run. The cost $\xi$ is the maximum of the last row of (\ref{eq:ex:cdta0:spsi0:01:05}), and by inspection $\xi = 2$. \textbf{(Costed Case):} The costed invocation sequences are simply (\ref{eq:ex:cdta0:spsi0:01:01}), (\ref{eq:ex:cdta0:spsi0:01:02}), and (\ref{eq:ex:cdta0:spsi0:01:02}) with 1's replaced by the cost appropriate to the process being considered; $\tau_1$, $\tau_2$, or $\tau_3$: \begin{eqnarray} \nonumber \overline{\rho_1}(2) & = & [ \; 0 \; 0 \; 0 \; 2 \; 0 \; 0 \; 0 \; 0 \; 0 \; 2 \; 0 \; 0 \; 0 \; 0 \; 0 \; 2 \; 0 \; \ldots \; ] \\ \label{eq:ex:cdta0:spsi0:01:06} \overline{\rho_2}(1) & = & [ \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; \ldots \; ] \\ \nonumber \overline{\rho_3}(0) = \overline{\rho_3} & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ] \end{eqnarray} The cost calculation matrix in the costed case is formed by vertically concatenating the first 12 columns of the rows of (\ref{eq:ex:cdta0:spsi0:01:06}), with the final row containing columnwise sums: \begin{equation} \label{eq:ex:cdta0:spsi0:01:07} \overline{\xi}(\mathbf{z}) = \overline{\xi}\left(\left[\begin{array}{c}2\\1\\0\end{array}\right]\right) = \left[ \begin{array}{rrrrrrrrrrrr} 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 7 & 0 & 0 & 0 & 7 & 0 & 0 & 0 & 7 & 0 \\ 0 & 0 & 5 & 0 & 0 & 5 & 0 & 0 & 5 & 0 & 0 & 5 \\ 0 & 0 & 12 & 2 & 0 & 5 & 7 & 0 & 5 & 2 & 7 & 5 \end{array} \right] . \end{equation} The cost $\overline{\xi}$ is the maximum of the last row of (\ref{eq:ex:cdta0:spsi0:01:07}), and by inspection $\overline{\xi} = 12$. \end{vworkexampleparsection} \vworkexamplefooter{} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Sine And Cosine} %Section tag: sco0 \label{cdta0:ssco0} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Rotational Transformations In 2 Dimensions} %Section tag: RTR2 \label{cdta0:srtr2} \index{rotation!2-D}It occurs often in microcontroller work that one needs to rotate coordinates in 2 dimensions (Figure \ref{fig:cdta0:srtr2:01}). In this section, the most economical algorithms known for 2-dimensional rotation are discussed. We assume that the point $\mathbf{p}$ to be rotated is specified in rectangular coordinates $\mathbf{p} = (p_x, p_y)$ rather than polar coordinates $\mathbf{p} = (r, \theta)$; since if $\mathbf{p}$ is specified in polar coordinates rotation involves only addition to $\theta$ modulo $2\pi$. We denote the point to be rotated $\mathbf{p} = (p_x, p_y) = \left[\begin{array}{c}p_x\\p_y\end{array}\right]$ and the result of the rotation $\mathbf{q} = (q_x, q_y) = \left[\begin{array}{c}q_x\\q_y\end{array}\right]$. We denote the length of the vector represented by $\mathbf{p}$ or $\mathbf{q}$ by $r$, and note that $r = |\mathbf{p}| = \sqrt{p_x^2 + p_y^2} = |\mathbf{q}| = \sqrt{q_x^2 + q_y^2}$. Because low-cost microcontrollers are used, we assume that $p_x, p_y, q_x, q_y \in \vworkintset$. We denote the desired amount of counter-clockwise rotation by $\delta$ (in radians). \begin{figure} \begin{huge} \begin{center} Reserved \end{center} \end{huge} \caption{Rotation In 2 Dimensions} \label{fig:cdta0:srtr2:01} \end{figure} A particularly na\"{\i}ve algorithm to use in microcontroller work is to convert $\mathbf{p} = (p_x, p_y)$ to polar coordinates $\mathbf{p} = (r, \theta)$, rotate to obtain $\mathbf{q} = (r, (\theta + \delta) \bmod 2\pi)$, and then convert back to rectangular coordinates $\mathbf{q} = (q_x, q_y)$. This algorithm is na\"{\i}ve because trigonometric and inverse trigonometric functions are required, which are not economical to implement on microcontrollers. We seek if possible algorithms which operate exclusively in rectangular coordinates and which require little or no evaluation of trigonometric and inverse trigonometric functions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Matrix Rotation In 2 Dimensions} %Section tag: MRT0 \label{cdta0:srtr2:smrt2} Assume we wish to rotate the vector \begin{equation} \label{eq:cdta0:srtr2:smrt2:01} \mathbf{p} = (p_x, p_y) = \left[\begin{array}{c}p_x\\p_y\end{array}\right] = (r \cos \theta, r \sin \theta) = \left[\begin{array}{c}r \cos \theta\\r \sin \theta\end{array}\right] \end{equation} \noindent{}by an angle of $\delta$ to give the vector \begin{eqnarray} \label{eq:cdta0:srtr2:smrt2:02} \mathbf{q} & = & (q_x, q_y) = \left[\begin{array}{c}q_x\\q_y\end{array}\right] \\ \nonumber & = & (r \cos (\theta + \delta), r \sin (\theta + \delta)) = \left[\begin{array}{c}r \cos (\theta + \delta)\\r \sin (\theta+\delta)\end{array}\right]. \end{eqnarray} \noindent{}Recall from standard trigonometry identities that for sines and cosines of sums of angles that \begin{eqnarray} \label{eq:cdta0:srtr2:smrt2:03} \left[\begin{array}{c}r \cos (\theta + \delta)\\r \sin (\theta+\delta)\end{array}\right] & = & \left[\begin{array}{c}r \cos \theta \cos \delta - r \sin \theta \sin \delta \\ r \sin \theta \cos \delta + r \cos \theta \sin \delta \end{array}\right] \\ \label{eq:cdta0:srtr2:smrt2:04} & = & \left[\begin{array}{c}p_x \cos \delta - p_y \sin \delta \\ p_x \sin \delta + p_y \cos \delta \end{array}\right] \\ \label{eq:cdta0:srtr2:smrt2:05} & = & \left[\begin{array}{c}q_x\\q_y\end{array}\right] = \left[\begin{array}{cc}\cos \delta & - \sin \delta \\ \sin \delta & \;\;\;\cos \delta \end{array}\right] \left[\begin{array}{c}p_x\\p_y\end{array}\right] . \end{eqnarray} \noindent{}Note that (\ref{eq:cdta0:srtr2:smrt2:05}) reduces the rotation problem to four multiplications and two additions (the matrix multiplication), provided that some approximation of the sine and cosine functions is available (see Section \ref{cdta0:ssco0}). To apply (\ref{eq:cdta0:srtr2:smrt2:05}), the embedded software may or may not need to approximate the sine and cosine functions. For some applications, if the angle of rotation is fixed, $\sin \delta$ and $\cos \delta$ may be calculated at compile time and tabulated in ROM rather than $\delta$ (so that the embedded software does not need to approximate these functions). For other applications, sine and cosine must be approximated (see Section \ref{cdta0:ssco0}). The 2 $\times$ 2 matrix in (\ref{eq:cdta0:srtr2:smrt2:05}) is called the \index{rotation matrix}\emph{rotation matrix}. There are other functionally equivalent ways to derive this result, including complex arithmetic (i.e. phasor analysis) and graphical geometric arguments. As pointed out in Section \ref{cdta0:ssco0}, the best way to approximate sine and cosine in low cost microcontrollers is usually by tabulation of the values of $\sin \delta$ for $\delta \in [0, \pi/2]$. Using the techniques presented in Section \ref{cdta0:ssco0} for approximation of sine and cosine and using (\ref{eq:cdta0:srtr2:smrt2:05}), rotation can usually be carried out using around 20 machine instructions. If a vector is rotated repeatedly using (\ref{eq:cdta0:srtr2:smrt2:05}), cumulative truncation and rounding errors may eventually yield a vector $\mathbf{q}$ with a significantly different magnitude $|\mathbf{q}| = \sqrt{q_x^2 + q_y^2}$ than the starting vector. It should be possible to develop an algorithm similar in spirit to the Bresenham circle algorithm (see Section \ref{cdta0:srtr2:sbrt2}) to adjust the magnitude of a vector to correct for cumulative errors while leaving its direction as nearly unchanged as possible (see Exercise \ref{exe:cdta0:sexe0:01}). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Bresenham Rotation In 2 Dimensions} %Section tag: BRT0 \label{cdta0:srtr2:sbrt2} Depending on the application \ldots{} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Rotational Transformations In 3 Dimensions} %Section tag: RTR3 \label{cdta0:srtr3} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Acknowledgements} %Section tag: ACK0 \label{cdta0:sack0} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Exercises} %Section tag: sexe0 \label{cdta0:sexe0} \begin{vworkexercisestatement} \label{exe:cdta0:sexe0:01} Develop an algorithm similar in spirit to the Bresenham circle algorithm to adjust a vector $\mathbf{q} = (q_x, q_y)$ with cumulative magnitude errors due to repeated rotations to a vector $\mathbf{z} = (z_x, z_y)$ which points as nearly as possible in the same direction as $\mathbf{q}$ but with a desired magnitude $r$. \end{vworkexercisestatement} \vworkexercisefooter{} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \vfill \noindent\begin{figure}[!b] \noindent\rule[-0.25in]{\textwidth}{1pt} \begin{tiny} \begin{verbatim} $RCSfile: c_dta0.tex,v $ $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_dta0/c_dta0.tex,v $ $Revision: 1.5 $ $Author: dtashley $ $Date: 2003/03/03 23:50:43 $ \end{verbatim} \end{tiny} \noindent\rule[0.25in]{\textwidth}{1pt} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % $Log: c_dta0.tex,v $ % Revision 1.5 2003/03/03 23:50:43 dtashley % Substantial edits. Safety checkin. % % Revision 1.4 2003/02/27 05:00:06 dtashley % Substantial work towards rotation algorithm section. % % Revision 1.3 2003/01/15 06:23:13 dtashley % Safety checkin, substantial edits. % % Revision 1.2 2003/01/14 05:39:59 dtashley % Evening safety checkin after substantial edits. % % Revision 1.1 2001/08/25 22:51:25 dtashley % Complex re-organization of book. % %End of file C_PCO0.TEX