1.​ Metaprogramming. What is a metaprogram (in relation to compilation, templates, and
recursion). Write a metaprogram computing , where A, N are integers. Describe the𝐴
𝑁
following metaprogram and find a defect in its implementation
template<int N> struct F{
static inline float result(float* u, float* v) {
return (*u) * (*v) + F<N-1>::result(u, v);
}
};
template<> struct F<1> {
static inline float result(float* u, float* v) {
return (*u) * (*v);
}
};
2.​ Rotations I. Describe the relation between the rotation matrix and orthonormal
coordinate basis vector. Euler angles (source and target frame, line of nodes,
conventions, intrinsic vs. extrinsic rotations, gimbal lock). Tait-Bryan angles (relation to
Euler angles, conventions).
3.​ Rotations II. Axis angle representation. Explain the Rodrigues’ rotation formula (use the
picture below left - rotating vector about by angle ). Linear and spherical𝑣 𝑎 θ
interpolation of axis angle (issues with LERP; for SLERP use the picture below right interpolating
from to by ).𝑢 𝑣 0 ≤ 𝑡 ≤ 1
4.​ Rotations (Quaternions).Definition, Scalar-vector notation. Operations (addition,
multiply by scalar, conjugation, length). Quaternions representing rotations (similarity to
Rodrigues’ rotation formula - relation of angles; inverse rotation, composition of
rotations). Linear and spherical interpolation of quaternions (for slerp( ) - explain𝑞0
, 𝑞1
, 𝑡
the use of “delta quaternion”: ).∆𝑞𝑞0
= 𝑞1
5.​ Particle system. Particle representation. Newton’s equations of motion. Describe the
initial value problem of 1st-order ODEs. Describe the interface of an ODE solver:
using F_y_t = std::function<float(std::vector<float> const&,float)>;
void ODE(
std::vector<float> const& y0,
std::vector<F_y_t> const& Fyt,
float& t,
float const dt,
std::vector<float>& y
);
External force acting on a particle (gravity, viscous drag, simple friction). Collision of a
particle with a plane.
6.​ Differential equations I. Describe the initial value problem of 1st-order ODEs.
Numerical solution (implicit vs explicit method, Taylor theorem). Forward Euler method
(accuracy, stability issue). Solve this example (what equations should be used?):
Let’s consider a particle 𝒫(𝑡)=(𝒙,𝒗,𝑭,𝑚), where 𝑚=0.1kg, in a homogenous gravity
field with 𝒈=(0,0,−10)^⊤ m⋅s^(−2). At time 𝑡=1 we have 𝒙=(1,−1,5)^⊤ m,
𝒗=(1,0,0)^⊤ m⋅s^(−1). Using forward Euler’s method with Δ𝑡=0.5s compute 𝒫(2).
7.​ Differential equations II. Explain the backward Euler method (write down the
fundamental theorem of the calculus, infer the formula of the method, explaining the
integral computation of this picture):
Solve this example: Let us consider IVP =(3−4𝑦)/2𝑡,𝑦(1)=−4. Compute 𝑦(2) by backward𝑦˙
Euler’s method.
8.​ Differential equations III. Explain the principal functionality of the midpoint method (use
this picture):
Explain the principle of the implicit midpoint method (how to compute the integral?).
Runge-Kutta methods (explain the idea of the integral computation):
Solve this example:
Runge-Kutta method of order 1 has the form:
𝑘1
= 𝐹(𝑦(𝑡0
), 𝑡0
)
𝑦(𝑡0
+ Δ𝑡) = 𝑦(𝑡0
) + Δ𝑡𝑏1
𝑘1
What value to choose for (what polynomial to use for the comparison)?𝑏1
9.​ Unconstrained rigid body motion I. Concept of particles (explain the picture below and
write equations for computing from and vice versa)𝑝𝑖
(𝑡) 𝑝𝑖
'
Linear and angular velocity (relation between and and and ). The𝑥˙(𝑡) 𝑣(𝑡) 𝑅˙(𝑡) ω(𝑡)
velocity of a particle ( ). Mass center in the body and world space. Force𝑣𝑖
(𝑡) = 𝑝˙
𝑖
(𝑡) =...
and torque (acting on a particle; total force and torque; how to get torque given a force).
10.​Unconstrained rigid body motion II. Linear and angular momentum (on a particle and
total on body, relations: and , and , and , and ),𝑃(𝑡) 𝑣(𝑡) 𝑃˙(𝑡) 𝐹(𝑡) 𝐿(𝑡) ω(𝑡) 𝐿˙(𝑡) τ(𝑡)
Inertial tensor (in world space and related important issue, solution of the issue and
relation and via ). Newton-Euler equations of motion.𝐼(𝑡) 𝐼' 𝑅(𝑡)
11.​Constrained rigid body motion I. Collision constraint (describe the constraint using the
picture below and formulate the constraint in terms of particle positions; how to express
the constraint in terms of particle velocities?)
A collision constraint can be expressed in the following general form. Explain it:
Collision constraint force and torque (write down the equation for the force acting on the
bodies i and j; use the vector in the picture above to express the forces and torques).
12.​Constrained rigid body motion II. Friction (explain the Coulomb law using this picture:
static vs dynamic friction). Write down friction constraints (in terms of velocities; use this
picture for reference):
Explain the friction constraints:
13.​Constrained rigid body motion III. Constraint bias (explain for “bouncing” collision
) using this picture:𝐶˙(𝑝𝑖
, 𝑝𝑗
) = 𝑁⋅𝑉 ≥ − β(𝑁⋅𝑉0
)
Explain these constraints (their type and method for their solving):
Explaining transformation of constraints to the unified form:
14.​Constrained rigid body motion IV. Explain the constraint system (meaning of variables
(matrices, vectors), what are the unknowns):
What kind of the algorithm is this:
How can we extend this algorithm so that it can solve the constraint system:
15.​Collision detection I. Broad and narrow phase (difference between phases, input, and
output of the phases). Explain the Sweep-and-prune algorithm (use this picture for
functionality description):
Describe the weakness of the algorithm. How can we deal with it?
16.​Collision detection II. Given two shapes 𝒜 and ℬ define the Minkowski sum 𝒜+ℬ and
difference 𝒜-ℬ. Compute 𝒜+ℬ for objects in this picture:
Define a support function for a shape 𝒜 (what is the input and the output of the function;
demonstrate the computation using following picture):
17.​Collision detection III. Explain the GJK algorithm on the intuitive level using following
example:
18.​Collision detection IV. Explain terms “penetration” and “tunneling”. Collision caching
(based on distance in world/body space, based on geometrical properties (collision ID) use
the picture below-left; explain the use of the cache in the game loop). Computation
of the collision time (explain and demonstrate using picture below-right):
19.​Fluid simulation I. Describe the principle of Euler’s approach. Describe Navier-Stokes
equations (variables, operators, and parts of the equations (their purpose)):
20.​Fluid simulation II. Discretization and numerical solution of Navier-Stokes equations
(grid, boundary conditions, finite difference - write down how to compute , the∇𝑝𝑖,𝑗,𝑘
method of splitting (principle and usage)). Helmholtz-Hodge decomposition (explain how
a vector field w is decomposed - into what fields and what are their properties).
21.​Fluid simulation III. Lagrange approach to fluid simulation (particle properties,
equations of motion, Lenard-Jones forces - explain their purpose and describe their𝐹𝑖,𝑗
properties on this plot):
22.​Fluid simulation IV. Smoothed particle hydrodynamics (Lagrange vs. Euler approach,
smoothing kernel W(x)). What parts of the Navier-Stokes equations can be ignored?
How do we use Newton’s equations of motion? What is the computed unknown, and
how do we get the pressure?
23.​Fluid simulation V. Height-field surface approximation (grid and function ℎ(𝑥,𝑦,𝑡),
explain the equation:
What substitution do we use to decompose the equation into two? Apply the forward
Euler method to solve the system of the equations numerically; how to approximate ).∇
2
ℎ
24.​Low-level Engine Systems. State low-level sub-systems of typical game engines,
described selected one in more detail.
25.​Game Loops. Define what the game loop is - from the developer’s point of view, not the
designer’s PoV. State examples of typical loops in the game engine.