3D Orientation§

  • Rotation matrix
    • 9 numbers to represent 3D orientation, i.e. upper-left 3x3 block of a 4x4 transformation matrix.
    • Usually, all other orientation representations are converted into a rotation matrix.
  • Fixed angles/Euler Angles/Yaw-Pitch-Roll
    • 3 numbers can represent any 3D orientation
    • TODO: Insert image.
    • Euler’s rotation theorem
      • Any rotation can be expressed as a single rotation about some axis
      • 4 numbers to represent a 3D orientation
    • Prone to gimbal lock.
  • Quaternions
    • Interpolation is easy using (S)LERP between begin and end quaternions.
    • $i^2 = j^2 = k^2 = ijk = -1$
    • $ij = k, jk = i, ki = j$
    • $ji = k, kj = -i, ik = -j$ $$w + xi + yj + zl \iff (w, x, y, k) \iff (w, \vec{v})$$
    • Quaternion algebra
      • $q_0 = (w_0, \vec{v}_0), q_1 = (w_1, \vec{v}_1)$
      • $q_1q_0 = (w_1w_0 - \vec{v}_1 \cdot \vec{v}_0, w_1\vec{v}_0 + w_0\vec{v}_1 + \vec{v}_1 \times \vec{v}_0)$
      • $q_1 q_0 \neq q_0 q_1$
    • Unit quaternions can be used to represent 3D rotations
      • Let $w = \cos \left(\frac{1}{2}\theta\right)$ and $\vec{v} = \sin \left(\frac{1}{2}\theta\right)\hat{r}$

Interpolation§

LERP: Linear Interpolation§

$$ \begin{align} \vec{q}(u) &= (1-u)\\ \hat{q}(u) &= \frac{\vec{q}(u)}{\|\vec{q}(u)\|_2} \end{align} $$

SLERP: Spherical Linear Interpolation§

$$ \begin{align} \hat{q}(u) &= \frac{\sin ((1 - u) \theta)}{\sin \theta} \hat{q}_0 + \frac{\sin (u \theta)}{\sin \theta}\hat{q}_1\\ \theta &= \arccos \left(\frac{\vec{q}_0 \cdot \vec{q}_1}{\|\vec{q}_0\|_2\,\|\vec{q}_1\|_2}\right) \end{align} $$

LERP vs. SLERP§

  • SLERP gives constant rotation speed
  • LERP can interpolate between more than 2 quaternions
    • $\vec{q}(\alpha, \beta, \gamma) = \alpha\hat{q}_0 + \beta\hat{q}_1 + \gamma\hat{q}_2$
    • $\hat{q}(\alpha, \beta, \gamma) = \textrm{norm}(\vec{q})$
  • LERP is easier to use with splines

Long vs. Short Path§

When interpolating rotations with quaternions, there is a short and long way to get to the target rotation. For example, if we want to rotate right by 90 degrees, we can choose to add 90 degrees to our orientation or -270 degrees. We want to choose the short path to prevent any weird artifacts.

Arc Length Parameterization§

Problem: Distance in world space is not the same as $u$, the distance along a parametric curve.

E.g. the distance $\|p(u)\|$ for $u \in [1, 1.1]$ is not necessarily the same as for $u \in [3, 3.1]$ even if the intervals both have length $0.1$.

Given 2 $u$ values, how can we compute the arc length between them?

$$ \begin{equation} S = \int_{u_0}^{u_1}\|\vec{p}\,’(u)\|_2\,\mathrm{d}u \end{equation} $$

Unfortunately, this intergral is intractable.

A crude approximation can be obtained by computing the following

$$ \begin{equation} S \approx \|\vec{p}(u_1) - \vec{p}(u_0)\|_2 \end{equation} $$

and building a lookup table between $u$ and $s.$

  • Both $u$ and $s$ are monotonically increasing
  • We increase $u$ with constant $\Delta u$ (i.e. linearly)
  • Note that $s$ does not respond linearly

Lookup Table Construction

$u \leftarrow 0$ $s \leftarrow 0$ insert $(u, s)$ while not done do:   $s \leftarrow s + \mathrm{arclength}(u, u \rightarrow \Delta u)$   $u \leftarrow u + \Delta u$   insert $(u, s)$

With this table we can perform lookups in either direction: $u \rightarrowtail s$ and $s \rightarrowtail u$.

Lookup Table

We’ll use the following lookup table for the next few examples.

index$u$$s$
00.00.0
10.12.0
20.23.0
30.33.5
40.45.0
50.58.0

$u \rightarrowtail s$

Given $u = 0.371,$ what is $s?$

We compute the indices for the lower and upper bound of the table, the lower bound for an arbitrary $u$ is given by $\left\lfloor\frac{u}{\Delta u}\right\rfloor,$ the upper bound is simply the lower bound plus one.

Using these indicies, we get $u_0 = 0.3$, $u_1 = 0.4$, $s_0 = 3.5,$ and $s_1 = 5.0.$

Then,

$$ \begin{align*} \alpha &= \frac{u - u_0}{\Delta u} = \frac{0.371 - 0.3}{0.4 - 0.1}\\ S &= (1 - \alpha) S_0 + \alpha S_1 = 3.5\,(1 - \alpha) + 5\,\alpha = 4.565 \end{align*} $$

$s \rightarrowtail u$

Given $s = 3.2,$ what is $u?$

First, we find $S$ values in the table that bound $S.$

Unfortunately, this is not possible to do in constant time:

  • $\mathcal{O}(n)$ with linear search
  • $\mathcal{O}(\log n)$ with binary search

In this example, $3.0$ and $3.5$ are the lower and upper bounds corresponding to indicies $2$ and $3$, respectively.

$$ \begin{align*} \alpha &= (S - S_0) / (S_1 - S_0)\\ &= (S - 3) / (3.5 - 3)\\ &= 0.4 \end{align*} $$

Then, $$ u = (1 - \alpha) u_0 + \alpha u_1 = (0.6)(0.2) + (0.4)(0.3) = 0.24 $$

Time Control§

Without interpolation, the speed at which we move between control points is dependent on the positions of those points; i.e. the farther away two points the faster we move between them. With (S)LERP we learned how to interpolate between the points at a constant speed.

Here, we talk about controling the speed with an arbitrary curve.

Note: The discontinuities in these control functions can be represented as fp NaNs or $\infty$.

We can use a cubic fit

$$ \begin{equation} s(t) = at^3 + bt^2 + ct + d \end{equation} $$

we need $4$ conditions (points/samples) to solve for coefficients $(a, b, c, d).$

Cubic Fit

TODO: Add graph.

$$ \begin{align*} s(t=0) = 0 &\implies 0 = a \cdot 0^3 + b \cdot 0^2 + c \cdot 0 + d\\ s(t=0.9) = 2.5 &\implies 2.5 = a \cdot 0.9^3 + b \cdot 0.9^2 + c \cdot 0.9 + d\\ s(t=2) = 1.5 &\implies 1.5 = a \cdot 2^3 + b \cdot 2^2 + c \cdot 2 + d\\ s(t=3) = 4 &\implies 4 = a \cdot 3^3 + b \cdot 3^2 + c \cdot 3 + d \end{align*} $$

Next, we express this as a system $A\vec{x} = \vec{b}$ where $\vec{x} = (a, b, c, d)$ and $\vec{b}$ are the values of $s(t):$

$$ \begin{pmatrix} 0 & 0 & 0 & 1\\ 0.9^3 & 0.9^2 & 0.9 & 1\\ 2^3 & 2^2 & 2 & 1\\ 3^3 & 3^2 & 3 & 1 \end{pmatrix} \begin{pmatrix} a\\ b\\ c\\ d \end{pmatrix} = \begin{pmatrix} 0\\ 2.5\\ 1.5\\ 4 \end{pmatrix} $$

In our assignments, we would use GLM or Eigen to solve this linear system.

Cubic Fit with Derivative

TODO: Add graph.

Additionally, we can use three points along with a derivative of the curve instead of four.

$$ \begin{align*} s(t = 0.0) &= 0\\ s(t = 0.5) &= 0.5\\ s(t = 1.0) &= 1\\ s’(t = 0.5) &= -1 \end{align*} $$

Let $s(t)$ be the same cubic function from Eq. (7), and its derivative is $s’(t) = 3at^2 + 2bt + c.$

Then the constraints for $s(t)$ can be found like before, and $s’(0.5) = -1 \implies -1 = 3a(0.5)^2 + 2b(0.5) + c.$

Finally, the system is given by $$ \begin{pmatrix} 0 & 0 & 0 & 1\\ 0.5^3 & 0.5^2 & 0.5 & 1\\ 1 & 1 & 1 & 1\\ 3(0.5)^2 & 2(0.5) & 1 & 0 \end{pmatrix} \begin{pmatrix} a\\ b\\ c\\ d \end{pmatrix} = \begin{pmatrix} 0\\ 0.5\\ 1\\ -1 \end{pmatrix} $$

Note: Fitting higher order polynomials are prone to oscillations (see: Runge’s phenomenon). Soln: Use multiple cubics.

Cubic with 2 Curves

TODO: Add graph.

$$ \begin{align*} s_1(t) &= a_1 t^3 + b_1 t^2 + c_1 t + d_1\\ s_2(t) &= a_2 t^3 + b_2 t^2 + c_2 t + d_2 \end{align*} $$

We now have 8 unknowns, so we need 8 conditions.

In our example, we want the two curves to connect at the end of $s_1$ and the beginning of $s_2,$ so we set $s_1(t=0.5) = s_2(t=0.5).$

The system is given by this block matrix: $$ \begin{bmatrix} \begin{matrix} \cdot & \cdot & \cdot & \cdot\\ \cdot & \cdot & \cdot & \cdot\\ \cdot & \cdot & \cdot & \cdot\\ \cdot & \cdot & \cdot & \cdot \end{matrix} & \begin{matrix}|\\|\\|\\|\end{matrix} & 0\\ \hline 0 & \begin{matrix}|\\|\\|\end{matrix} & \begin{matrix} \cdot & \cdot & \cdot & \cdot\\ \cdot & \cdot & \cdot & \cdot\\ \cdot & \cdot & \cdot & \cdot \end{matrix}\\ \hline\begin{matrix}\cdot & \cdot & \cdot & \cdot\end{matrix} & | & \begin{matrix}\cdot & \cdot & \cdot & \cdot\end{matrix} \end{bmatrix} \begin{bmatrix} a_1\\b_1\\c_1\\d_1\\a_2\\b_2\\c_2\\d_2 \end{bmatrix} = \begin{bmatrix} \cdot\\\cdot\\\cdot\\\cdot\\\cdot\\\cdot\\\cdot\\0 \end{bmatrix} $$

Again, solve using some library like Eigen. Like the previous example, we can also add a constraint on the derivative, i.e. $s_1’(t=0.5) = s_2’(t=0.5).$

Gaussian Quadrature§

Recall the arc length formula Eq. (5)

$$ s = \int_{u_0}^{u_1}\|\vec{p}\,’(u)\|_2\,\mathrm{d}u $$

Using the $us-$Table method, we linearly interpolate between $u_0$ and $u_1$, for small $\Delta u$ the error between the actual arc length and this approximation is small.

However, we can better approximate this integral using Gaussian quadrature,

$$ \begin{equation} \int_{-1}^{1} f(x) \mathrm{d}x \approx \sum_{i=1}^{n} w_i f(x_i) \end{equation} $$

this is a weighted sum of the function’s values, as $n \to infty$ the approximation improves.

  • For $n = 1$, use $x_1 = 0$ and $w_1 = 2$.
  • For $n = 2$, use:
    • $x_1 = -1/\sqrt{3}, w_1 = 1$.
    • $x_2 = 1/\sqrt{3}, w_2 = 1$.
  • For $n = 3$, use:
    • $x_1 = \sqrt{3/5}, w_1 = 5/9$.
    • $x_2 = 0, w_2 = 5/9$.
    • $x_3 = \sqrt{3/5}, w_3 = 5/9$.
  • See Wikipedia for $n \geq 4.$

Gaussian Quadrature

Approximate the following using the Gaussian quadrature method:

$$ \int_{-1}^{1} \cos x\,\mathrm{d}x $$

first with $n = 1$, then $n=3.$

For $n = 1:$ $$ \begin{align*} \int_{-1}^{1} f(x)\,\mathrm{d}x &\approx w_1 f(x)\\ &= 2 \cos(0)\\ &= 2 \end{align*} $$

For $n = 3:$ $$ \begin{align*} \int_{-1}^{1} f(x)\,\mathrm{d}x &\approx w_1 f\left(-\sqrt{3/5}\right) + w_2 f(0) + w_3 f\left(\sqrt{3/5}\right)\\ &= 5/9 \left(\cos\left(-\sqrt{3}/5\right) + \cos 0 + \cos \left(\sqrt{3}/5\right)\right)\\ &= 1.6830 \end{align*} $$

The analytical soln: $$ \int_{-1}^{1} \cos x\,\mathrm{d}x = \sin x |_{-1}^{1} \approx 1.6829 $$

Change of Interval§

The method thus far works for interval $[-1, 1],$ to make it work for an arbitrary interval $[a, b]:$

$$ \int_{a}^{b} f(x)\,\mathrm{d}x \approx \frac{b-a}{2}\sum_{i=1}^{n} w_i f\left(\frac{b-a}{2}x_i + \frac{a+b}{2}\right) $$

Quadrature Change of Interval

Approximate the following integral with $n = 3:$

$$ \begin{align*} \int_{0}^{4} \cos x\,\mathrm{d}x &\approx \frac{4 - 0}{2}\sum_{i=1}^{3}w_i \cos\left(\frac{4 - 0}{2}x_i + \frac{0 + 4}{2}\right)\\ &= 2 \left(\frac{5}{9} \cos\left(2\left(-\sqrt{3/5}\right) + 2\right) + \frac{8}{9}\cos 2 + \frac{5}{9}\cos\left(2\sqrt{3/5} + 2\right)\right)\\ &= -0.7598 \end{align*} $$

Analytical soln: $-0.7518.$

Arc Length Approximation§

$$ s = \int_{u_0}^{u_1}\|\vec{p}\,’(u)\|_2\,\mathrm{d}u $$

$$ \vec{p}\,’(u) = GB \vec{u}\,’,\quad\vec{u}\,’ = \left(0, 1, 2u, 2u^2\right)^T $$

Then, define $\|\vec{p}\,’\|_2 = \sqrt{\vec{p}\,’ \cdot \vec{p}\,’}$ and the approximation for $s$ is given by $$ s \approx \frac{u_1 - u_0}{2} \sum_{i=1}^{n} w_i \left\|\vec{p}\,’\left(\frac{u_1 - u_0}{2} x_i + \frac{u_0 + u_1}{2}\right)\right\|_2 $$

For $n = 2,$ $$ \begin{align*} s &\approx \frac{0.1}{2}\left(\left\|\vec{p}\,’\left(\frac{0.1}{2} \cdot \frac{-1}{\sqrt{3}} + \frac{0.1}{2}\right)\right\|_2 + \left\|\vec{p}\,’\left(\frac{0.1}{2} \cdot \frac{1}{\sqrt{3}} + \frac{0.1}{2}\right)\right\|_2\right)\\ &= \frac{1}{20}\Big(\left\|\vec{p}\,’(0.02113)\right\|_2 + \left\|\vec{p}\,’(0.07887)\right\|_2\Big) \end{align*} $$