Computer Graphics Basics – Ⅰ

1. Vector

• Vector has length and direction
• Representation
• Usually drawn as segment with arrow-head

Vector Operations

• Scalar Multiplicaiton
• Negative of a Vector
• Addition of Vectors
• Dot(Inner) Product 点积
  • $u \cdot v = u v cos(\theta)$
  • $u \cdot v = \sum_i u_i v_i$
  • $u \cdot v = {||u||} {||v||} cos \theta$

  • $u \cdot v = u^T v$

    • 点积 = 0 -> 向量垂直
    • 向量点积通常用于求投影

• Length(Norm) of Vector

  • ||v|| = sqrt(v.v)

    • 利用点积求向量长度

• Normalization of a Vector 单位化

  • $v' = \frac{v}{||v||} = \frac{1}{\sqrt(v_1^2 + v_2^2 + ... + v_n^2)}v$

    • 令向量长度为1

• Cross Product 叉积
  • 方向：右手法则
  • 大小：平行四边形面积

Scalar Triple Product $A\cdot(B \times C)$

• 体积：叉乘的值是BC形成的面积，方向与BC形成的面垂直；再点乘时相当于A在BC垂线上的投影->高与面积相乘->体积
• 可以判断三向量共面，若共面，A与BC叉乘的点乘应为0

2. Point

• Point has a position in space

• Origin is a special point 原点

  O = (0, 0, …)

• Position Vector: Vector joining origin to a point

⭐Points and Vectors

• Vector operations can not be done on points
• Displacement Vector: A vector denoting transition

3. Co-ordinate Systems

能将点唯一确定->坐标系

• Concept of Dimension

  Dimension of Space v/s Dimension of Object

• Cartesian Co-ordinates

• Polar Co-ordinates 极坐标

  应用：航海时始终以自己为原点

• 柱坐标、球坐标
• Coordinate systems let us define points in 3D
  • Right handed 右手系

  • Left handed 左手系

    可能影响计算的简化程度

4. Line

• Representation
  • (Start Point, End Point)
  • (Point, Direction)
• Equation of Line
  • $L = P + t * D$
  • $L = P_1 + t * (P_2-P_1)$

5. Ray and Segments

• A Ray is a line with $0 \leq t \leq \infty$
• A segment is a line with $0 \leq t \leq 1$

6. Other Simple Objects

• Circle $x^2 + y^2 = R^2$
• Triangle: Inside Points Area

7. Affine Combinations 仿射变换

• Affine combination of points $P_i$ is given by $P = \sum_i a_i P_i$ where, $\sum_i a_i = 1$

Consider, the equation of line

\begin{aligned}
L &= P_1 + t * ( P_2-P_1 )\\
&= (1-t) * P_1 + t * P_2
\end{aligned}

8. Barycentric Co-ordinates

• Any point on a plane can be written as affine combination of three distinct points
• $P = \alpha P_1 + \beta P_2 + \gamma P_3$where, $\alpha + \beta + \gamma = 1$

• Note that, if $0 < (\alpha , \beta , \gamma) < 1$ point P lies inside the triangle

  限制范围(0,1)后点落在三角形内部

9. Polygons

• Polygon is a closed figure formed by an ordered set of points
• These corner points are usually termed as Vertices

10. Convex Combination 凸组合

• Convex combination is an ++affine combination++, where all the weights are constrained to interval [0,1]

  广义仿射变换只要求和为1，若要求0-1之间->凸组合

• Given a polygon, if all convex combinations of the vertices of the polygon lie inside the polygon, then we say that, the polygon is Convex(凸) otherwise it is said to be Concave(凹)

  许多绘制算法中要求多边形为凸

11. Intersections

• Finding intersections between various geometric objects is one of the important task in Computer Graphics Algotithms
• How to find the intersection between a moving vertex and a static triangle?
  • Line-plane intersection 求出运动轨迹直线与平面的交点
  • Inside test 判断交点是否在内部

• How to find the intersection between a moving vertex and a deforming triangle?

  deforming 变形，并非刚体移动。如布料随风飘动

  • Coplanar test 共面检测

  • Inside test

    -> Continuous Collision Deteciton 连续碰撞检测

  • Heuristic Culling -> Non-Penetraion Filters 非穿透性过滤器

    • 如果点一直在面的一侧，能否判断没有发生过穿透：两个叉积是不够的，要做六个
    • M. Tang, D. Manocha, and R. F. Tong. Fast continuous collision detection using deforming non-penetration filters. Proceedings of the ACM SIGGRAPH symposium on Interactive 3D Graphicsand Games, pages 7-14, 2010

12. Area Computations

• Finding lengths, areas, volumes, etc.. of various geometric objects is another important problem in Computer Graphics
• How to find an area of a polygon in 2D?
  

13. Matrix

• Two dimensional arrangement of numbers

  In a sense, it is a generalization of vectors

• It has number of rows and columns

Various Matrices

• Square Matrix 方阵

  Matrix whose columns = rows

• Identity Matrix: I

  A square matrix with diagonal elements = 1 and other elements = 0

• Transpose of a Matrix: $A^T$

Matrix Operations

• Scalar Multiplication: $R[i,j] = k * A[i,j]$
• Addition of Matrices: $R[i,j] = A[i,j] + B[i,j]$

• Multiplication of Matrices: $R[i,j] = \sum A[i,k] * B[k,j]$

  In general, $AB \ne BA$

• Vector – Matrix Multiplication

  

• Matrix – Matrix Multiplication

  

• Inverse of Matrix: A

  This is usually used while solving a set of linear equations:

  \begin{aligned}
  Ax &= B\\
  x &= A^{-1} B
  \end{aligned}