Computer Graphics II

Game Physics

Mankyu Sung 1
Computer Graphics II

Game Physics
 Apply classical Mechanics
 The laws that govern how large objects move under the gravity and other force
 Mass, Inertia, bounce, buoyancy
 Game Physics : Real time physics applicable to Computer Games
 Advantage:
 Can apply wide variety of games
 Realistic movement
 disadvantage
 Heavy computation
 All movement are not controllable (Given the physics law, it generate motion
automatically
 Require a lot of testing

Mankyu Sung 2
Computer Graphics II

Two approaches for building physics engine

 Depending on Object Types
 Rigid Body Engine: Treat objects as a whole
 Complicate

 Mass Aggregate Engine: Treat objects as if they were made of lots of little
masses
 Easy to implement
 Fortunately, we can extend this model to full rigid body

Mankyu Sung 3
Computer Graphics II

Two approaches for building physics engine

 Depending on how to process touching objects
 Iteration method:
 Fast
 handle contacts one by one making sure each works well on its own
 However, one contact processing may affect another
 Easy to implement
 Jacobian approach
 Calculate an overall set of effects to apply to all objects at the same time
 Very complex and time consuming
 Commercial engines use this method
 Contacts and constraints between objects
 Apply problem-specific laws, change these laws frame-by-frame
 Highly realistic and very slow

Mankyu Sung 4
Computer Graphics II

In this course
 Mass aggregate approach
 Iteration method for contact solving

Mankyu Sung 5
Computer Graphics II

Math review

Same slides that I used for Computer graphics 1

Mankyu Sung 6
Computer Graphics II

Points
 Points are represented as n numbers in n dimension
 N numbers are called as coordinates, this coordinates represent a Position
 Ex) Point (2, 3, 4) (X coordinate: 2, Y coordinate: 3, Z coordinate: 4)

Mankyu Sung
Computer Graphics II

Vectors
 Vectors are also represented as n number in n dimension, however, it
represent directions having a specific length

 Data structure point of view, points and vectors are same

 Why? Both need n numbers in a list structure
 Also, we are able to represent the point with a vector if we know the origin.

Mankyu Sung 8
Computer Graphics II

How to represent a vector?

 Column vector
 Row vetor

Mankyu Sung 9
 Computer Graphics II

Point and Vector

vector (q-p) Point q

Point p
 <Point> is a position
 <Vector>can be get from two points
 If there is an origin, <point> can be represent as a
<vector> from origin to the point

Mankyu Sung 10
Computer Graphics II

Addition

p+w

u+v v w

u p
u + v is a vector p + w is a point
u, v, w : vectors
p, q : points
Mankyu Sung
Computer Graphics II

Example
 p = (2, 3, 4) v = (1, -1, 1)

 p+v=?

v It is a translation from
one position to other
p position

Mankyu Sung
Computer Graphics II

Subtraction
p p-w

u u-v p-q -w

v q p
u - v is a vector p - q is a vector p - w is a point
u, v, w : vectors
p, q : points
Mankyu Sung
 Computer Graphics II

Magnitude of a Vector

 Geometrically, magnitude of a vector is the length between two ending

points

 Vector magnitude in n-D:


Vector magnitude in 2-D:

Mankyu Sung
 Computer Graphics II

Example

 v = (1, -1, 1)

 ||v||= ?

Mankyu Sung
 Computer Graphics II

Normalized Vectors

 A Vector with magnitude = 1

 We can convert from any vector to normalized vector
 In general, we put ‘^’ mark on the vector

^
V=

Mankyu Sung
 Computer Graphics II

Example

 v = (1, -1, 1)

^
V =?

Mankyu Sung
Computer Graphics II

Vector addition and multiplication

Mankyu Sung
Computer Graphics II

Vector operations

a = a x ay az 
b = b x by bz 
a + b = a x + b x a y + by a z + bz 
a − b = a x − b x a y − by a z − bz 
− a = − a x − ay − az 
sa = sa x sa y sa z 
Mankyu Sung
Computer Graphics II

Vector Representation
#include <iostream>
#include <core.h>

using namespace cyclone;

int main()
{

Vector3 A(1, 2, 3);

Vector3 B(1, 2, 3);
Vector3 C = A + B;
Vector3 C = A - B;
A += B;
A -= B;
A *= 3.0f;
[Link]();
return 0;
std::cout << [Link]() << std::endl;
}

Mankyu Sung 20
Computer Graphics II

accessing elements

Vector3 a(1,2,3);
Vector3 b(1,2,3);

float x = a[0];
float y = a.y;

Mankyu Sung 21
Computer Graphics II

Practice of cyclone
1. Move Point p(1,4,-5) to vector v(5,1,4).
2. Add vector v1(1,0,0) and vector v2(0,1,0)
3. Multiply v1(0,1,0) with scalar 5.
4. Get a vector v starting at (8,2,5) and ending at (1,-1,4)
5. Normalize vector v(1,3,4).

 [Link]/mksung89/simple_math
 Post your source codes of 5 problems
 Title : ID number_ name

Mankyu Sung 22
Computer Graphics II

Dot Product / Cross Product of vectors

Two most important operations on vectors

Mankyu Sung
Computer Graphics II

Dot product

a  b = a x bx + a y b y + a z bz =  a i bi
a  b = a b cos 

The result of dot product of

vectors is scalar value

Mankyu Sung
Computer Graphics II

Example
 What is the value of dot product of v ·u?
 v = (7,3,-2)
 u = (10,4,2)

 v ·u ?

Mankyu Sung
Computer Graphics II

Example: Angle between two vectors

 How do you find the angle θ between vectors a and b?

b θ
a

Mankyu Sung
Computer Graphics II

Example: Angle Between Vectors

a  b = a b cos 
a b
cos  =  
 a b 
 
b θ
a b
 = cos −1   a
 a b 
 
Mankyu Sung
Computer Graphics II

Quiz
 a = (2,-1,1) b=(1,1,2)
 Angle between vector a and vector b?

Mankyu Sung
Computer Graphics II

#include <iostream>

#define _USE_MATH_DEFINES
#include <cmath>

#include "core.h"

using namespace cyclone;

int main()
{
const double DEGREES_TO_RADIAN = M_PI / 180.0f;
const double RADIANS_TO_DEGREES = 180.0f / M_PI;
Vector3 v(2, -1, 1);
Vector3 u(1, 1, 2);
float d = [Link](u);
float c = d /( [Link]() * [Link]());
double deg = acos(c) * RADIANS_TO_DEGREES;
}

Mankyu Sung 29
 Computer Graphics II

Dot Products with Unit Vectors

0 < a·b < 1

a·b = 0 a·b = 1
b
θ a

-1 < a·b < 0 a·b

a = b = 1. 0
a  b = cos ( )

a·b = -1

Mankyu Sung
 Computer Graphics II
Another use of dot product
: Vector Projection (only one vector is Unit Vector)

 if |u|=1.0, then a·u represent a length of vector that is projected

from vector a onto vector u.

u
a·u
Mankyu Sung
Computer Graphics II

Vector Decomposition
 Any vector can be decomposed into two perpendicular vectors. By using
projection concept, we can make one of them is parallel to a specific vector

There are infinite number

of vectors

What if I say that one of them must parallel

to this unit vector?

Mankyu Sung 32
Computer Graphics II

Cross (vector) product a  b = −b  a

a  b = a b sin 

b

a
 Cross product orthogonal to two initial vectors (perpendicular to both
vectors)
 Direction determined by right-hand rule
 Useful in constructing coordinate systems (later)
Mankyu Sung
Computer Graphics II

Cross Product

i j k The result of cross product is another

a  b = ax ay az vector
bx by bz (In the case of dot product, it is a scalar)

a  b = a y b z − a z b y a z bx − a x bz a x b y − a y bx 
Cross product only works in 3D space(dot product works in 2D
and 3D space as well)

Mankyu Sung
Computer Graphics II

Two perpendicular vectors

v v

u u
uxv
 Which one is the cross product of two vector u and v?
 Right hand rule -> [Link]

Mankyu Sung 35
36
Computer Graphics II

Properties

x y = +z
y  x = −z
a  ba=−bb=−ab  a
y  z = +x
a  aa= 0a = 0
z  y = −x
a  (ab + (cb) += ca)=ba+ab+c a  c
z x = +y
a  (akb)(=kbk)(=
a k b(a)  b)
x z = −y

x,y,z are three axis

Mankyu Sung
Computer Graphics II

Vector3

cyclone::Vector3 A(1, 3, 4);

cyclone::Vector3 B(-1, 2, 7);

cyclone::Vector3 C = [Link](B);
cyclone::Vector3 C2 = [Link](B); Three functions are same
cyclone::Vector3 C3 = A % B;

std::cout << [Link]() << std::endl;

std::cout << [Link]() << std::endl;
std::cout << [Link]() << std::endl;

Mankyu Sung 38
Computer Graphics II

Example
 U = (1,-2,-1) V = (-2,4,1)

 UxV=?

 (-2*1-(-1)*4, -1*(-2)-1*1, 1*4-(-2)*(-2))

Mankyu Sung
 Computer Graphics II

Properties of cross product

Note that a x b = another vector, but |a x b| = scalar

Length of
vector a  b = a b sin 
The area of parallelogram that is
a  b = consisted of a와 b
a  b = 0 If, a and b are parallel
a b is perpendicular to both a and b, in the
direction defined by the right hand rule

Mankyu Sung
Computer Graphics II

Intuition of Cross product

 Can be used for rotation axis
 Rotation vector for vector a to be rotated to axb
vector b
b

Mankyu Sung 41
Computer Graphics II

Orthonormal basis
 In order to be animated, we need construct a 3D coordinate system. Three
axes must be mutually orthogonal each other
 Those three axes can be represented as triple vectors (both orthogonal and
unit size)
 Called as orthonormal basis (orthogonal + normal)
 Given two vectors, we can find those three axes
 The two vectors must not be parallel (if they are parallel, then we can’t get it)

Given two vectors, we have to choose

a fixed vector

Mankyu Sung 42
Computer Graphics II

Obtaining Orthonormal basis fixed vector(a)

a
b
fixed vector

b
b fixed vector
0. Normalize a (a is fixed) a
1. Normalize b
2. cross product c = a x b
3. c
If ([Link]() == 0) //a and b are parallel
Else { b a
Normalize c;
b = c x a;
}
c

Mankyu Sung 43
Computer Graphics II

Coding..
 Given following two vectors A and B, set the vector A as a fixed vector and
calculating 3 Orthonormal basis vectors.

 A = (1,2,-1) (fixed vector)

 B = (3,0,2)

 Find three orthonormal basis

 Use cyclone vector3

Mankyu Sung 44
Computer Graphics II

Matrix

Mankyu Sung 45
Computer Graphics II

Matrices

 Reminder: A matrix is a rectangular array of numbers

 An m x n matrix has m rows and n columns
 Mij denotes the entry in the i-th row and j-th column of
matrix M
 These are generally thought of as1-indexed (instead of 0-indexed)

Mankyu Sung
Computer Graphics II

Matrices

 Here, M is a 2x5 matrix:

Mankyu Sung
Computer Graphics II

Matrix Transposes

 The transpose of an m x n matrix is an n x m

matrix
 Denoted MT
 MTij = Mji

Mankyu Sung
Computer Graphics II

Matrix Addition

 Only well defined if the dimensions of the 2 matrices are the

same
 That is, m1 = m2 and n1 = n2
 Here, M and G are both 2 x 5

Mankyu Sung
Computer Graphics II

Scalar Multiplication

 Matrix * Scalar = Matrix

Mankyu Sung
Computer Graphics II

Matrix Scaling

 Just like vector scaling

 Matrix * Scalar = Matrix

Mankyu Sung
Computer Graphics II

Matrix multiplication

 # of rows of the first matrix must match to # of columns of the second

matrix
 # of columns of the first matrix must match to # of rows of the second
matrix

 Matrix * Matrix = Matrix

 if F is m x n, and G is
n x p, then FG is
mxp

Mankyu Sung
Example
Computer Graphics II

The Identity Matrix

 Defined such that the product of any matrix M and the identity matrix
I is M
 IM = MI = M
 Let’s derive it
 The identity matrix is a square matrix with ones on the diagonal and
zeros elsewhere

Mankyu Sung
Computer Graphics II

Multiplication of a matrix with a vector

 We can multiply a matrix with a vector
 It actually “transform” a vector to another
 The number of rows of matrix must match to the number of dimension of
vector

𝑣′ = M 𝑣

𝑣 : 4D vector
: : 4x4 matrix
M

Mankyu Sung 55
Computer Graphics II

An example

1 0 2 1
𝐴= 1 2 3 𝑣= 1
−1 0 1 −1

𝐴×𝑣 =?
𝑣×𝐴 =?

Mankyu Sung 56