計算機圖形學 Week 2_Basics - Ⅰ

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}