Knowledge Base¶
Contents:
Geometric Operations¶
Homogeneous Point¶
Homogeneous coordinates are used to support translation.
\[\begin{split}P = \begin{bmatrix} x & y & z & 1 \end{bmatrix}\end{split}\]
If the fourth component is not 1, the point can be normalized:
\[\begin{split}\begin{bmatrix} x & y & z & w \end{bmatrix} \to \begin{bmatrix} x \over w & y \over w & z \over w & 1 \end{bmatrix}\end{split}\]
Translation¶
\[\begin{split}T(x, y, z) = \begin{bmatrix}
1 & 0 & 0 & x \\
0 & 1 & 0 & y \\
0 & 0 & 1 & z \\
0 & 0 & 0 & 1 \\
\end{bmatrix}\end{split}\]
Rotation¶
\[\begin{split}R_x(\theta) = \begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & \cos(\theta) & \sin(\theta) & 0 \\
0 & -\sin(\theta) & \cos(\theta) & 0 \\
0 & 0 & 0 & 1 \\
\end{bmatrix}\end{split}\]\[\begin{split}R_y(\theta) = \begin{bmatrix}
\cos(\theta) & 0 & -\sin(\theta) & 0 \\
0 & 1 & 0 & 0 \\
\sin(\theta) & 0 & \cos(\theta) & 0 \\
0 & 0 & 0 & 1 \\
\end{bmatrix}\end{split}\]\[\begin{split}R_z(\theta) = \begin{bmatrix}
\cos(\theta) & \sin(\theta) & 0 & 0 \\
-\sin(\theta) & \cos(\theta) & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
\end{bmatrix}\end{split}\]
Scaling¶
\[\begin{split}S(x, y, z) = \begin{bmatrix}
x & 0 & 0 & 0 \\
0 & y & 0 & 0 \\
0 & 0 & z & 0 \\
0 & 0 & 0 & 1 \\
\end{bmatrix}\end{split}\]
Transforming Normals¶
Normals cannot be transformed like normal vectors. Transpose of the inverse of a transformation matrix must be used to transform normals:
\[N' = N * M^{-1T}\]
Coordinate Systems¶
| Vector | Left-handed | Right-handed |
|---|---|---|
| Right | x | x |
| Forward | y | -z |
| Up | z | y |
Interpolation¶
General Form¶
\[\begin{split}v = \mathrm{F}(a, b, r) \qquad & a \le \mathrm{F}(a, b, r) \le b, \\
& 0 \le r \le 1\end{split}\]
- \(\mathrm{F}\)
- Interpolation function.
- \(a, b\)
- Values to interpolate between.
- \(r\)
- Interpolation factor.
To Interpolate in n dimensions, apply 1D interpolation recursively to collapse them one by one. Until there is only a scalar value:
\[v_n = \mathrm{F}(\mathrm{F}(\cdots, \cdots, r_{n-1}),\mathrm{F}(\cdots, \cdots, r_{n-1}), r_n)\]
This would mean \(2^n-1\) applications of \(\mathrm{F}\).
Linear Interpolation¶
1D¶
\[\begin{split}x = (1 - r) x_a + r x_b \qquad & 0 \le r \le 1, \\
& x_a \le x_b\end{split}\]
- \(x_a, x_b\)
- Values to interpolate between.
- \(r\)
- Interpolation factor.
2D¶
\[\begin{split}z = z_{00} + x (z_{10} - z_{00}) + y (z_{01} - z_{00}) + x y (z_{00} - z_{01} - z_{10} + z_{11}) \qquad & 0 \le x \le 1, \\
& 0 \le y \le 1\end{split}\]
- \(z_{00}, z_{01}, z_{10}, z_{11}\)
- Values to interpolate between.
- \(x, y\)
- Interpolation factors.
Cosine Interpolation¶
1D¶
\[x = x_a + \frac{1 - \cos(\pi r)}{2} (x_b - x_a) \qquad 0 \le r \le 1\]
- \(x_a, x_b\)
- Values to interpolate between.
- \(r\)
- Interpolation factor.
2D¶
\[\begin{align*}
z = & \frac{z_{0} (1 + \cos(\pi x) + z_{1} (1 - \cos(\pi x)}{2} \\
z_0 = & \frac{z_{00} (1 + \cos(\pi y) + z_{01} (1 - \cos(\pi y)}{2} \\
z_1 = & \frac{z_{10} (1 + \cos(\pi y) + z_{11} (1 - \cos(\pi y)}{2} \\
& 0 \le x \le 1 \\
& 0 \le y \le 1
\end{align*}\]
- \(z_{00}, z_{01}, z_{10}, z_{11}\)
- Values to interpolate between.
- \(x, y\)
- Interpolation factors.
Cubic Interpolation¶
\[\begin{align*}
x = & A r^3 + B r^2 + C r + D \\
A = & (x_3 - x_2) - (x_0 - x_1) \\
B = & (x_0 - x_1) - A \\
C = & x_2 - x_0 \\
D = & x_1 \\
& 0 \le r \le 1 \\
& x_0 \le x_1 \le x \le x_2 \le x_3
\end{align*}\]
- \(x_0, x_1, x_2, x_3\)
- Values to interpolate between.
- \(r\)
- Interpolation factor.
Bezier Curve¶
\[x = (1 - r)^3 x_0 + 3 (1 - r)^2 r x_1 + 3 (1 - r) r^2 x_2 + r^3 x_3\]
Optimized:
\[\begin{align*}
x = & A r^3 + B r^2 + C r + D \\
A = & x_3 - 3 x_2 + 3 x_1 - x_0 \\
B = & 3 x_2 - 6 x_1 + 3 x_0 \\
C = & 3 x_1 - 3 x_0 \\
D = & x_0 \\
& 0 \le r \le 1 \\
& x_0 \le x_1 \le x \le x_2 \le x_3
\end{align*}\]
- \(x_0, x_1, x_2, x_3\)
- Values to interpolate between.
- \(r\)
- Interpolation factor.
Matrices¶
Identity Matrix¶
\[\begin{split}I_1 = \begin{bmatrix}
1 \end{bmatrix}
,\
I_2 = \begin{bmatrix}
1 & 0 \\
0 & 1 \end{bmatrix}
,\
I_3 = \begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \end{bmatrix}
,\ \cdots ,\
I_n = \begin{bmatrix}
1 & 0 & \cdots & 0 \\
0 & 1 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 1 \end{bmatrix}\end{split}\]
Matrix Multiplication¶
Also known as matrix product.
To be able to multiply two matrices, column count of the first matrix must be equal to the row count of the first matrix.
\[[M \times P] * [P \times N] = [M \times N]\]
Resulting matrix has as many rows as the first operand and as many columns as the second operand:
\[\begin{split}A = \begin{bmatrix}
a_{0:0} & a_{0:1} & a_{0:2} \\
a_{1:0} & a_{1:1} & a_{1:2} \\
\end{bmatrix} \qquad B = \begin{bmatrix}
b_{00} & b_{01} \\
b_{10} & b_{11} \\
b_{20} & b_{21} \\
\end{bmatrix}\end{split}\]\[C = A * B\]\[c_{i:j} = \sum_{k=1}^{3} a_{j:k} \, b_{k:j}\]\[\begin{split}C = \begin{bmatrix}
\sum\limits_{k=1}^{3} a_{0:k} \, b_{k:0} & \sum\limits_{k=1}^{3} a_{0:k} \, b_{k:1} \\
\sum\limits_{k=1}^{3} a_{1:k} \, b_{k:0} & \sum\limits_{k=1}^{3} a_{1:k} \, b_{k:1} \\
\end{bmatrix}\end{split}\]
Matrix multiplication is not a commutative operation.
\[A * B \neq B * A\]
Transposition¶
\[\forall x, y \quad M_{(x, y)}^T = M_{(y, x)}\]
Inversion¶
To be invertible a matrix:
- Must be square. (Must have equal number of rows and column.)
- Determinant must not be zero.
Multiplying a matrix with its inverse yields identity matrix:
\[M * M^{-1} = M^{-1} * M = I\]
Gauss-Jordan Method¶
Elementary row operations are:
- Swap rows.
- Multiply (or divide) each element in a row with a constant
- Add a multiple of another row to a row.
Gauss-Jordan method is applying elementary row operations to a matrix \(M\) until it is equal to identity vector and applying the same operations to identity vector which ends up being \(M^{-1}\).
- Ensure, for each column pivot (\(1\)‘s in identity matrix) is non-zero.
- For each row set non-pivot values to zero.
- Scale each pivot to one.
Example:
\[\begin{split}\begin{bmatrix}
3 & 0 & 2 \\
2 & 0 & -2 \\
0 & 1 & 1 \\
\end{bmatrix} \qquad \begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}\end{split}\]
Swap rows 1 & 2:
\[\begin{split}\begin{bmatrix}
3 & 0 & 2 \\
0 & 1 & 1 \\
2 & 0 & -2 \\
\end{bmatrix} \qquad \begin{bmatrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
\end{bmatrix}\end{split}\]
All pivots are non-zero now. Add row 2 to row 0:
\[\begin{split}\begin{bmatrix}
5 & 0 & 0 \\
0 & 1 & 1 \\
2 & 0 & -2 \\
\end{bmatrix} \qquad \begin{bmatrix}
1 & 1 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
\end{bmatrix}\end{split}\]
Add to row 1, row 2 divided by 2:
\[\begin{split}\begin{bmatrix}
5 & 0 & 0 \\
1 & 1 & 0 \\
2 & 0 & -2 \\
\end{bmatrix} \qquad \begin{bmatrix}
1 & 1 & 0 \\
0 & 0.5 & 1 \\
0 & 1 & 0 \\
\end{bmatrix}\end{split}\]
Add to row 1, row 0 multiplied by -0.2:
\[\begin{split}\begin{bmatrix}
5 & 0 & 0 \\
0 & 1 & 0 \\
2 & 0 & -2 \\
\end{bmatrix} \qquad \begin{bmatrix}
1 & 1 & 0 \\
-0.2 & 0.3 & 1 \\
0 & 1 & 0 \\
\end{bmatrix}\end{split}\]
Add to row 2, row 0 multiplied by -0.4
\[\begin{split}\begin{bmatrix}
5 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & -2 \\
\end{bmatrix} \qquad \begin{bmatrix}
1 & 1 & 0 \\
-0.2 & 0.3 & 1 \\
-0.4 & 0.6 & 0 \\
\end{bmatrix}\end{split}\]
Multiply row 0 with 0.2 and row 2 with -0.5
\[\begin{split}\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{bmatrix} \qquad \begin{bmatrix}
0.2 & 0.2 & 0 \\
-0.2 & 0.3 & 1 \\
0.2 & -0.3 & 0 \\
\end{bmatrix}\end{split}\]
Result:
\[\begin{split}\begin{bmatrix}
3 & 0 & 2 \\
2 & 0 & -2 \\
0 & 1 & 1 \\
\end{bmatrix}
*
\begin{bmatrix}
0.2 & 0.2 & 0 \\
-0.2 & 0.3 & 1 \\
0.2 & -0.3 & 0 \\
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}\end{split}\]
Relational Algebra¶
Binary Operators¶
- ∪ set union
- ∩ set intersection
- - set difference
- ⨯ carthesian product
Unary Operators¶
- π projection
- σ restriction
- ρ rename
Joins¶
- ⋈ natural join
- θ-join & equijoin
- ⋉ & ⋊ semijoin
- ▷ antijoin
- ÷ division
Resources¶
Vectors¶
Length of a Vector¶
\[\|\vec{V}\| = \sqrt{{\vec{V}.x}^2 + {\vec{V}.y}^2 + {\vec{V}.z}^2}\]
Result is a scalar.
Normalizing¶
\[\hat{V} = {\vec{V} \over { \| \vec{V} \| }}\]
Result is a vector with \(length = 1\).
Addition and Subtraction¶
\[\begin{align*}
\vec{C} & = \vec{A} + \vec{B} & \vec{C} & = \vec{A} - \vec{B} \\
\vec{C}.x & = \vec{A}.x + \vec{B}.x & \vec{C}.x & = \vec{A}.x - \vec{B}.x \\
\vec{C}.y & = \vec{A}.y + \vec{B}.y & \vec{C}.y & = \vec{A}.y - \vec{B}.y \\
\vec{C}.z & = \vec{A}.z + \vec{B}.z & \vec{C}.z & = \vec{A}.z - \vec{B}.z
\end{align*}\]
Result is a vector.
Multiplication and Division¶
With a scalar:
\[\begin{align*}
\vec{B} & = \vec{A} \, k & \vec{B} & = \frac{\vec{A}}{k} \\
\vec{B}.x & = \vec{A}.x \, k & \vec{B}.x & = \frac{\vec{A}.x}{k} \\
\vec{B}.y & = \vec{A}.y \, k & \vec{B}.y & = \frac{\vec{A}.y}{k} \\
\vec{B}.z & = \vec{A}.z \, k & \vec{B}.z & = \frac{\vec{A}.z}{k}
\end{align*}\]
With another vector:
\[\begin{align*}
\vec{C} & = \vec{A} \, \vec{B} & \vec{C} & = \frac{\vec{A}}{\vec{B}} \\
\vec{C}.x & = \vec{A}.x \, \vec{B}.x & \vec{C}.x & = \frac{\vec{A}.x}{\vec{B}.x} \\
\vec{C}.y & = \vec{A}.y \, \vec{B}.y & \vec{C}.y & = \frac{\vec{A}.y}{\vec{B}.y} \\
\vec{C}.z & = \vec{A}.z \, \vec{B}.z & \vec{C}.z & = \frac{\vec{A}.z}{\vec{B}.z}
\end{align*}\]
Result is a vector.
Dot Product¶
\[\vec{A} \cdot \vec{B} = \vec{A}.x * \vec{B}.x + \vec{A}.y * \vec{B}.y + \vec{A}.z * \vec{B}.z\]
Result is a scalar.
Length can be derived from dot product of vector with itself:
\[\|\vec{V}\| = \sqrt{\vec{V} \cdot \vec{V}}\]
Dot product is a commutative operation:
\[\vec{A} \cdot \vec{B} = \vec{B} \cdot \vec{A}\]
Dot product of two unit vectors is the cosine of the angle between:
\[\begin{split}\hat{A} \cdot \hat{B} & = \cos(\theta) \\
\vec{A} \cdot \hat{B} & = \|\vec{A}\| \cos(\theta) \\
\vec{A} \cdot \vec{B} & = \|\vec{A}\| \, \|\vec{B}\| \cos(\theta) \\
\theta & = \arccos(\frac{\vec{A} \cdot \vec{B}}{\|\vec{A}\| \, \|\vec{B}\|})\end{split}\]
Cross Product¶
\[\begin{split}\vec{C} & = \vec{A} \times \vec{B} \\
\vec{C}.x & = \vec{A}.y \, \vec{B}.z - \vec{A}.z \, \vec{B}.y \\
\vec{C}.y & = \vec{A}.z \, \vec{B}.x - \vec{A}.x \, \vec{B}.z \\
\vec{C}.z & = \vec{A}.x \, \vec{B}.y - \vec{A}.y \, \vec{B}.x\end{split}\]
Result is a vector.
Cross product is anticommutative:
\[\vec{A} \times \vec{B} \neq \vec{B} \times \vec{A}\]\[\vec{C} = \vec{A} \times \vec{B} \iff \vec{B} \times \vec{A} = -\vec{C}\]
Spherical Coordinates¶
A left-handed coordinate system (z-up) is used below:
- \(\theta\) (polar)
- Angle perpendicular to xy plane.
- \(\phi\) (azimuth)
- Angle that lies on xy plane.
Given a unit vector:
\[\begin{align*}
\theta & = \arccos(z) & 0 \le \theta \le \pi \\
\phi & = \arctan\left({y \over x}\right) & 0 \le \phi \le 2\pi \\
\end{align*}\]
Spherical coordinates can be converted to a unit vector using:
\[\begin{split}x & = cos(\phi) \, sin(\theta) \\
y & = sin(\phi) \, sin(\theta) \\
z & = cos(\theta)\end{split}\]