[Numerical Analysis] 3. Transformation
Transformantion
To Change geometric structure such as translations, scaling, rotations, and combinations of them
Translation
- position : changed
- size, angle, ... : unchanged
Scaling
size: changed:
- position, angle, ... : unchanged
Rotation
angle: changed:
- size, position, ... : unchanged
Unchanged properties : Invariant
Geometric Properties
- Position : Distance from the origin
- Distance : Relative distance ( size )
- Angle : Relative angle
- Orientation : Absolute angle
- Collineation : Preseves lines ( points on a line also form a line afeter the transformation ) L' = T(L), P' = T(P) -> Line
- Distance-preseving : Distance between any two points is preserved after the transformation, Preseve angles, area, and volume
- Conformal : Preserve angles
Geometries
- Congruent geometry : Sizes and shapes anre identical
- Conformal geometry : corresponding angles are equal
- Affine geometry : Parallel lines remain parallel and ratios are preservved
- Projective geometry : Straight lines remain straight
Isometries
- Also called as rigid-body transformation
- distance-preserving map
- rigid-body motion
- include translations, rotations, reflections
- Equations describing general 2D isometries : $$x' = ax + by + t_x, y' =cx+dy+t_y \\ \begin{bmatrix}
a & b \\
c & d \\
\end{bmatrix}^T = \begin{bmatrix}
a & b \\
c & d \\
\end{bmatrix}^{-1}, \begin{vmatrix}
a & b \\
c & d \\
\end{vmatrix} = \pm 1 $$
- $x, y$ : original coordinates, $x', y'$ : transformed, $t_x, t_y$ : translation
Similarities
- Preseve shapes - isometry + scaling (uniform)
- Also called as conformal transformation
Shear
- Slanting an axis
- Translate along an axis and the amount of translation is proportional to its coordinates
- $x' = ax + by, y' = cx + dy$ -> x direction : a = d = 1, b = k, c = 0 || y direction : a = d = 1, b = 0, c = k
Affines
- Collinearity ( Points on AB are transformed to points on A'B')
- Preseve parallelism : AB parallel to CD -> A'B' parallel to C'D'
- Preserve ratios : EA : EB = E'A' : E'B'
Linear Transformations
- Homogeneous linear system $X' = MX$
- Linaer Transformation + Translation = Affine Transformation $X' = MX + T$
Scaling
- Uniform scaling ( Isotropic ) : same scales for all axes
- Non-uniform scaling : Different scale for each axis
Translation
- $X' = X + T$, T : vector
Rotations
- $x' = |P'|\cos (\theta + \omega) , y' = |P'|\sin (\theta + \omega )$
- $|P| = |P'|$ : length invarient
- $x' = x\cos \theta - y \sin \theta , y' = x \sin \theta + y \cos \theta$ ( 2D )
- $X' = RX$, $|R| = 1 $
- $R^{-1} = R^T$ -> orthogonal matrix
Rotation around a point P
1. Translate P to the origin ( $X' = X - P$ )
2. Rotate around the origin ( $X' = RX$ )
3. Translate the origin to P ( $X' = X + P$ )
=> $X' = R(X-P) + P$
Homogeneous Coordinates
- Except translations, all transformations can be represented as homogeneous systems, and corresponding matrix multiplications , $X' = M_3 M_2 M_1 X, X = (M_3M_2M_1)^{-1} X'$
- Including translations, they can be represented as matrix products and vector additions ( $X' = MX + T$ )
-> Points on the x-y plane in 3D are equivalent to the point in 2D
-> 2D point represent to 3D point $X = (hx, hy, h) \text{if} h=1, X = (x, y, 1)$
- Shear transformation in xy direction
$X' = SX = \begin{bmatrix} 1 & 0 & a \\ 0 & 1 & b \\ 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} hx \\ hy \\ h \\ \end{bmatrix} = \begin{bmatrix} hx + ha \\ hy+hb \\ h \\ \end{bmatrix}$
$X' = (h(x+a), h(y+b), h) \to X' = (x+a, y+b)$ in 2D
- 3D points can be also represented in 4D
- Express translations with matrix products ( n-dim translations -> n+1-dim shear transformation )
$ M = \begin{bmatrix} M & 0 \\ 0 & 1 \\ \end{bmatrix}, T = \begin{bmatrix} I & T \\ 0 & 1 \\ \end{bmatrix} $
- For computational efficiency, use h = 1
Orthogonal Matrix
- Definition : if $AA^T = I$, then A is an orthogonal matrix
- By definition of inverse matrix : $A^{-1} = A^T$
- Orthonormal : Two vectors are orthonormal if they are orthogonal and both of unit length
- Theorem : if vectors $V_1, \cdots, V_n$ form an orthonormal set, then n x n matrix constructed by setting the i-th column equal to $V_i$ is orthogonal
- Proof : if vectors $V_1, \cdots V_n$ are orthonormal $V_i \cdot V_j = \delta_{ij}$. Since i-th row of $A^T$ is $V_i$, $(i,j)$ element of $A^TA$ is $V_i \cdot V_j = \delta_{ij}$, therefore $A^T = A^{-1}$
- Theeorem : if the n x n matrix M is orthogonal, then $M$ preserves lengths and angles
- Proof : 1. Length : $MX \cdot MX = (MX)^T (MX) = X^T M^T MX = X^T X = X\cdot X$
- Angle: $X\cdot Y = |X||Y|\cos \theta, \theta = \cos^{-1}( \frac{X\cdot Y}{|X||Y|} )= \cos^{-1}( \frac{MX\cdot MX}{ |MX||MY|} )$, therefore, if $MX \cdot MY = X\cdot Y$, angle is preserved. $MX \cdot MY = (MX)^T MY = X^TM^TMY = X^TY = X\cdot Y$
- Rotation Matrix is orthogonal matrix
- 3D : $(R_x R_y R_z)^{-1} = R_z^{-1} R_y^{-1} R_x^{-1} = R_z^T R_y^T R_x^T = (R_x R_y R_z)^T$
Transforming Normal Vectors
- is the transformed normal vector still the normal vector? (perpendicular to the surface?)
- Tangent vector : direction of the surface at a point
- Let G be the transformation with which $GN$ become the normal vector of the transformed surface $(GN)\cdot (MT) = (GN)^T (MT) = N^T G^T MT = 0 $, Since $N^TT = 0, G=M$ if $M$ is orthogonal
Translation of Coordinate System
- Translating coordinate system is equivalent to oppositely translating points ( $X' = T^{-1}X$ )
( $T$ 만큼 translation 한다는것은, Coordinate system을 $-T$ 만큼 translation 한것과 동일하다는 뜻 )
Rotation of Coordinate System
- Rotating coordinate system is equivalent to oppositely rotating points ( $X' = R^{-1} X$ )
Transformation of Coordinate System
- Rotation + Translation ( $X' = (TR)^{-1}X = R^{-1} T^{-1} X$ )
- New coordinate system is specified by
- Origin : $X_0$
- Coordinate axes : $U, V, N$ ( in 3D )
- $N$ can be derived from $U$ and $V$ $N = \frac{U \times V}{|U \times V|}$
Reflection and Inversion
- Reflection across a line $m$
- Reflectioin about a line $m$ passing through the origin : $R = \begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \\ \end{bmatrix}$, $X' = R\begin{bmatrix} 1 & 0 \\ 0 & -1 \\ \end{bmatrix} R^{-1}X $
- Reflection about a line $m$ passing through a point $P(a,b)$ : $T = \begin{bmatrix} 1 & 0 & a \\ 0 & 1 & b \\ 0 & 0 & 1 \\ \end{bmatrix}$, $X' = TR\begin{bmatrix} 1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} R^{-1}T^{-1}X$
- Inversion in a point $P$
- inversion in a point $P(a,b)$ : $X' = T\begin{bmatrix} -1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} T^{-1}X, T = \begin{bmatrix} 1 & 0 & a \\ 0 & 1 & b \\ 0 & 0 & 1 \\ \end{bmatrix} $
- 3D Reflection
- xy : $x' = x, y' = y ,z'= -1$ : \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -1 \\ \end{bmatrix}$ ...
- Reflection about a plane passing through a poiint $P (a,b,c) $ and habing a normal vector N
- $T = \begin{bmatrix} a & b & c \\ \end{bmatrix}^T$
- $R$ : Rotation to move $N$ to z - axis ( 다른방법으로 xyz -> N UZ 으로 rotation 하는 $R$ 을 이용해도됨 )
- $X' = TR^{-1}F_{xy}RT^{-1}X $
3D Rotation
- Counter-clockwise rotation around axis (axis coordinate is same, other axis coordinate is roated by $\theta$ )
- Right-handed coordinate system
Rotation
- Rotation by $\theta$ around an arbitrary axis $A$
1. Rotate around z axis by $\alpha$ so that $A$ lies on the x-z plane. Let $A_{xy}$ be projection of $A$ onto x-y plane, then $\alpha$ = angle between $A_{xy}$ and x axis $X' = R_{\alpha}X$ $R_{\alpha}$ : clock wise rotation with z axis
2. Rotate around y axis by $\beta$ which is the angle between $R_{\alpha}A$ and x axis ( $X' = R_{\beta} R_{\alpha} X$ )
3. Rotate around x axis by $\theta$ ( $X' = R_{\theta}R_{\beta}R_{\alpha} X$ )
4. Rotate around y axis by $-\beta$ ( $ X' = R_{\beta}^{-1}R_{\theta}R_{\beta}R_{\alpha} X$ )
5. Rotate around z axis by $- \alpha$ ( $ X' = R_{\alpha}^{-1} R_{\beta}^{-1}R_{\theta}R_{\beta}R_{\alpha} X$ )
- Rotate $P$ by $\theta$ around an arbitrary axis $A$
- Decompose $P$ into $proj_A P$ and $perp_A P$
- $proj_A P$ : parallel to $A$ : Not changed after rotation
- $perp_A P$ : perpendicular to $A$
- $|A| = 1$
- $proj_A P' = proj_A P$
- $P = proj_A P + perp_A P$
- $proj_A P = (A \cdot P)A, perp_A P = P - (A\cdot P)A$
- $perp_A P' = (A \times P)\sin \theta + (perp_A P)\cos \theta $
- $P' = proj_A P' + perp_A P' = P \cos \theta + (A \times P) \sin \theta + A( A\cdot P) (1- \cos \theta)$
- Arbitrary rotations in 3D
- Represent the rotation as a product of successive rotations arounde ach axes
- Different orders produce different results
Rotations - Euler Angles
- Arbitrary rotations in 3D ( Pitch (x), Roll (y), Yaw (z) )
- can be achieved by a product of three elemental rotations ( rotations around a axis)
- Various combinations are possible
- Gimbal Lock
- A rotation in one axis could override a rotation in another => loss of a degree of freedom
- ex) Y axis rotated 90 degrees in X-Y-Z rotation => Z axis aligned to X axis
- Interpolation problems
- Interpolate between two rotations
- Calculated interpolations may not be smooth
Quaternions
- An alternative to Euler angles for representing rotation
- Somewhat less intuitive
- More predictable behavior and smooth interpolations
- Invented by William Hamilton as a non-commutative generalization to complex numbers
- 4-tuple : $w + xi +yj+zk$, where $i,j,k$ are special imaginaries (just like $i$ in complex number)
- $i^2 = j^2 = k^2 = -1$ , $ij = -ji = k$, $jk = -kj = i$, $ki = -ik = j$
Quaternions and Rotation
- Any rotation in 3-space can be encoded as a quaternion : $(w, x, y, z)$
- Quaternions for simple rotation around each axis
- $q_x = (\cos \frac{\alpha}{2}, \sin \frac{\alpha}{2}, 0,0)$
- $q_y = (\cos \frac{\beta}{2}, 0 , \sin \frac{\beta}{2} , 0)$
- $q_z = (\cos \frac{\gamma}{2} ,0,0,\sin \frac{\gamma}{2})$
- Euler angles : multiply simple rotations : $q = q_x q_y q_z ( X' = R_x R_y R_z X)$
- Quaternion $(w, x, y ,z)$ to matrix
$R_q = \begin{bmatrix} 1-2y^2-2z^2 & 2xy - 2wz & 2xz + 2wy \\ 2xy + 2wz & 1-2x^2-2z^2 & 2yz - 2wx \\ 2xz - 2wy & 2yz+2wx & 1-2x^2-2y^2 \\ \end{bmatrix} $
- Interpolation : Interpolating points on a 4D unit sphere, Unique path between two rotations, More predictable and statble
Projection
Projection : World (3D) -> Screen (2D)
- Parallel (or orthogonal) projection
- Perspective projection
Parallel Projection
- Lengths may be scaled
- Angles may not be preserved
- Preserves parallelism of lines
Perspective Projection
- Lengths may be scaled
- Angles may not be preserved
- Parallelism of lines may not be preserved
- Perspective foreshortening
- Near objects appear larger
Parallel Projection
Projection on the plane, $z=d$ -> $x,y$ is same, $z'= d$
Perspective Projection
Plane $z=d$->
$\frac{x'}{d} = \frac{x}{z} $ => $x' = \frac{x}{\frac{z}{d}}$
$\frac{y'}{d} = \frac{y}{z} $ => $y' = \frac{y}{\frac{z}{d}}$
$z' = d = \frac{z}{\frac{z}{d}}$
$ M = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & \frac{1}{d} & 0 \end{bmatrix} $
Lines in 3D Space
- A line passing through a point $S$ and having a direction $V$ -> $P = S + tV$
- Distance between a point $Q$ and a line
$d^2 = |Q - S|^2 - | proj_V(Q-S)^2| = |Q-S|^2 - | \frac{(Q-S)\cdot V}{|V|^2} V|^2 $
- Distance between two lines : $P_1, P_2$, $P_1 = S_1 + t_1V_1, P_2 = S_2 + t_2 V_2$
- minimun of $|P_1(t_1) - P_2(t_2)|$
- $ |P_1(t_1) - P_2(t_2)|^2 = P_1 \cdot P_1 + P_2 \cdot P_2 - 2P_1\cdot P_2 = At_1^2 + Bt_2^2 + Ct_1 + Dt_2 + Et_1t_2 + F$
- $\frac{\partial f}{\partial t_1}=0, \frac{\partial f}{\partial t_2}=0$
- $(V_1 \cdot V_2)^2 - V_1^2 V_2^2 = 0$ => Two lines are parallel, Distance between the line and any point on the line
Planes in 3D Space
plane : $ax+by+cz + d = 0$, $N \cdot (X-P) = 0$, $L = < N, -N\cdot P> = < N, D>$, $(|N| = 1)$
- Distance between a point $Q$ and a plane
- $d = N \cdot Q - N \cdot P = L \cdot Q$
- 1. d = 0, $Q$ is on the plane
- 2. d > 0, $Q$ is in the positive side (normal vector direction)
- 3. d < 0, $Q$ is in the negative side (opposite direction of normal vector)
- Intersection between three planes
- $N_1 \cdot Q - N_1 \cdot P_1 = 0$
- $N_2 \cdot Q - N_2 \cdot P_2 = 0$
- $N_3 \cdot Q - N_3 \cdot P_3 = 0$
- $ Q = M^{-1}\begin{bmatrix}N_1 \cdot P_1 \\ N_2 \cdot P_2 \\ N_3 \cdot P_3 \end{bmatrix}$
- Intersection between two planes : line
- $N_1 \cdot Q - N_1 \cdot P_1 = 0$
- $N_2 \cdot Q - N_2 \cdot P_2 = 0$
- $$ Q = \begin{bmatrix}
N_1 \\
N_2 \\
N_1 \times N_2 \end{bmatrix}^{-1}
\begin{bmatrix}
N_1 \cdot P_1 \\
N_2 \cdot P_2 \\
0 \end{bmatrix} $$
- $ P = Q + t(N_1 \times N_2) $
- Distance between a point $Q$ and a plane
- $N \cdot (Q' - P) = 0, Q' = Q - dN$
- $N \cdot (Q - dN - P) = 0$
- $d = N \cdot (Q - P) = L \cdot Q$
Transforming Planes
- Plane : $L = <N, D> = <N, -N\cdot P>$ ( $D = - N \cdot P$ )
- Transformation $F = TM = \begin{bmatrix} M & T \\ 0 & 1 \\ \end{bmatrix} $, ($M$ : Linear Transformation, $T$ : Translation )
- $ L \to L' = <N', D'>$
- $ N' = (M^{-1}^TN $, $P' = FP$
- $D' = -N' \cdot P' = - N' \cdot (FP) = - ((M^{-1})^T N) \cdot (MP + T) = - ((M^{-1})^T N)^T (MP + T) = - N^T M^{-1} MP - N^T M^{-1} T = D - N \cdot M^{-1} T$
- $L' = (F^{-1})^T L$