[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$