计算机图形学（三）Geometric Objects and Transformations

1. Vector and Vector Operation

• Vectors 向量
  • 加法 Addition：$(a_1,a_2,a_3)+(b_1,b_2,b_3)=(a_1+b_1,a_2+b_2,a_3+b_3)$
  • 标量乘法 Scalar Multiplication：$c\langle x,y,z\rangle=\langle cx,cy,cz\rangle$
  • 点乘 Dot Product：
    • $(a_1,a_2,a_3)\cdot(b_1,b_2,b_3)=a_1b_1+a_2b_2+a_3b_3$
    • $A\cdot B=||A||||B||\cos(\theta)$
  • 叉乘 Cross Product：
    • $(a_1,a_2,a_3)\times(b_1,b_2,b_3)=(a_2b_3-a_3b_2,a_3b_1-a_1b_3,a_1a_2-a_2b_1)$
    • $A\times B=-(B\times A)$
    • Reflection Vectors:$Q=2N(N\cdot P)-P$

2. What is a 2D or 3D Space?

• ADTs for points and Vectors
  • ADT 虚拟数据结构

3. Lines and Parameter Equation

• ray, line segment
  • $P=P_0+t(P_1-P_0)=(1-t)P_0+tP_1$

4. Plane and Normal

• Plane Equation
  • $(A,B,C)\cdot (x-x_0,y-y_0,z-z_0)=0$
  • $Ax+By+Cz+D=0$
• Relations of a Plane and a Point
  • $Ax+By+Cz>-D$ （in front）
  • $Ax+By+Cz<-D$ （in back）
• line segment intersects the plane
  • $t=-(Ax_0+By_0+Cz_0+D)/(A(x_1-x_0)+B(y_1-y_0)+C(z_1-z_0))$
  • $0\le t\le 1$，有交点
• Distance from a Point to a Plane
  • $D=|(P-Q)\cdot n|$
• Convexity 凸性

5. Parametric Curves

• Parametric curve: $x(t),y(t),z(t)$

• Parametric surface: $x(s,t),y(s,t),z(s,t)$

• Triangle-Based Collision Detection

  • 算法

  1. 比较两个包围球或包围盒：两个球心距离小于两个半径的和，则可能碰撞；

  2. 可能碰撞时，则一个物体的每个三角形与另一个包围体比较，假设是包围球：比较三角形的每个顶点:如果顶点与球心距离小于三角形最长边+球的半径， 则可能碰撞；或比较三角形外接圆（circumcircle）与包围球:如果外接圆心与球心距离 小于 外接圆半径+球的半径，则可能碰撞;

  3. 比较两个三角形是否碰撞：一个三角形的每个顶点 是否 在另一个三角形平面 的一边，即$Ax_i+By_i+Cz_i+D>0$ (i=1,2,3) 或$Ax_i+By_i+Cz_i+D<0$ (i=1,2,3)。如果在一边，则不会碰撞，否则可能碰撞（三角形与另一三角形相交）；

  4. 判断一个三角形是否与另一个三角形相交：
     一个三角形的边$Q_0Q_1$与另一个三角形平面的交点Q是否在另一个三角形$P_0P_1P_2$里面，即，若以下三个不等式同时成立
     $N·((P_1-P_0) ×(Q-P_0)) > 0$
     $N·((P_2-P_1) ×(Q-P_1)) > 0$
     $N·((P_0-P_2) ×(Q-P_2))> 0$

     则Q在三角形$P_0P_1P_2$里面

6. What is Transformation?

• Translation：$P’=P+T$, T is translation vector
  • $T=(T_x,T_y,T_z)$
• Scaling: $P’=S*P$, S is a scaling matrix
  • $S=\begin{bmatrix}S_x&0&0\0&S_y&0\0&0&S_z\end{bmatrix}$
• Rotation: $P’=R*P$, R is a rotation matrix
  • $R=\begin{bmatrix}1&0&0\0&\cos\theta&-\sin\theta\0&\sin\theta&\cos\theta\end{bmatrix}$

7. Homogeneous Coordinates

• Homogenous Coordinates 齐次坐标系：

  • in order to express all transformations as matrices and allow them to be combined easily: $P’ = (M_3 *(M_2 *(M_1 *P)))$
  • 最重要的优点是所有的仿射变换（具有直线的特性）都可以借助齐次坐标表示成矩阵相乘的形式。

• Translation

  • $P’=T\cdot P$

  $$
  \begin{align}
  \begin{bmatrix}x’\y’\z’\1\end{bmatrix} =
  \begin{bmatrix}1&0&0&T_x\0&1&0&T_y\0&0&1&T_z\0&0&0&1\end{bmatrix}
  \begin{bmatrix}x\y\z\1\end{bmatrix} =
  \begin{bmatrix}x+T_x\y+T_y\z+T_z\1\end{bmatrix}
  \end{align}
  $$

• Scaling

  • $P’=S\cdot P$

  $$
  \begin{align}
  \begin{bmatrix}x’\y’\z’\1\end{bmatrix} =
  \begin{bmatrix}S_x&0&0&0\0&S_y&0&0\0&0&S_z&0\0&0&0&1\end{bmatrix}
  \begin{bmatrix}x\y\z\1\end{bmatrix} =
  \begin{bmatrix}S_xx\S_yy\S_zz\1\end{bmatrix}
  \end{align}
  $$

• Rotation: $\theta$逆时针

• $P’=R_x(\theta)\cdot P$

$$
\begin{align}
\begin{bmatrix}x’\y’\z’\1\end{bmatrix} =
\begin{bmatrix}1&0&0&0\0&\cos\theta&-\sin\theta&0\0&\sin\theta&\cos\theta&0\0&0&0&1\end{bmatrix}
\begin{bmatrix}x\y\z\1\end{bmatrix}
\end{align}
$$

$$
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}
\
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}
$$

• Inverses Matrices

• Translation: $T^{-1}(d_x,d_y,d_z)=T(-d_x,-d_y,-d_z)$
• Rotation: $R^{-1}(\theta)=R(-\theta)=R^T$
• Scaling: $S^{-1}(s_x,s_y,s_z)=S(1/s_x,1/s_y,1/s_z)$
• $I=AB=BA$, then $B=A^{-1}$

8. Composite Transformations

• Ex1. Scaling with respect to a fixed position (a,b,c)

  1. Translate fixed point to origin $T(-a,-b,-c)=T_1$
  2. Scale $S$
  3. translate fixed point back to its starting positions $T_2$
  • $P’=(T_2(S(T_1P)))=(T_2ST_1)P=M*P$

• Ex2. rotation with respect to a fixed position (a,b,c)

• Ex3. scaling with respect to a fixed direction $\theta$

  1. rotation a fixed angle counterclockwise $R(\theta)=R_1$
  2. scaling $S$
  3. rotation a fixed angle clockwise $R(\theta)=R_2$
  • $P’=(R_2(S(R_1*P)))$

• Ex4. rotation with respect to an arbitrary line

  • $P’=T(p_0)R_x(-\theta_x)R_y(-\theta_y)R_z(\theta_z)R_y(\theta_y)R_x(\theta_x)T(-p_0)*P$

9. Reflection Transformation 反射变换

• x轴，y轴，z轴（相对于坐标原点），y=x

$$
\begin{bmatrix}1&0&0\0&-1&0\0&0&1\end{bmatrix}\ \ \
\begin{bmatrix}-1&0&0\0&1&0\0&0&1\end{bmatrix}\ \ \
\begin{bmatrix}-1&0&0\0&-1&0\0&0&1\end{bmatrix}\ \ \
\begin{bmatrix}0&1&0\1&0&0\0&0&1\end{bmatrix}\ \ \
$$

10. Shear Transformation 错切变换

• 相对于X轴的x方向错切的变换矩阵

  • $x=x+sh_x*y$; $y=y$

• 相对于Y轴的y方向错切的变换矩阵

  • $x=x$; $y=y+sh_y*x$

  $$
  \begin{bmatrix}1&sh_x&0\0&1&0\0&0&1\end{bmatrix}
  \ \ \
  \begin{bmatrix}1&0&0\sh_y&1&0\0&0&1\end{bmatrix}
  $$