Introduction

This project is the final coursework for the Physics-Based Animation module. The module focused on teaching techniques and algorithms for building physics engines. Over the course of the module, concepts like particles, springs and cloth simulation were thought. The aim of the final coursework though, was the creation of a physics simulation that realistically represented a domino effect using cuboids.

The biggest parts of the project were collision detection, collision response, friction and optimization.

Collision detection and response

These are the most difficult problems to solve in a physics simulation. Collision detection relies on the separating axis theorem, which is used to find an axis that if two bodies were projected onto, a gap could be found. If no such gap is found the bodies are intersecting. This is quite simple in 2 dimensions, where for squares only 4 axes need to be checked - the ones parallel to the edges of the squares. When working in 3 dimensions however, edge to edge, face to edge and face to corner collisions cannot be detected with just the 6 axes parallel to the edges of the cuboids. 15 axes have to be checked to find out whether the objects are intersecting.

Once a collision has been detected, an appropriate response can be used to simulate the collision. To do this the point of contact, the depth of intersection and the type of collision (face to edge, etc.) have to be determined. Once that information is calculated, the colliding objects are moved apart enough so they are no longer intersecting but just touching. After that an appropriate impulse is calculated and applied to each cuboid.

Friction

To make collisions look realistic friction is essential. While there are many small details to take into account when implementing friction, the main idea is not very complex - depending on the material the colliding objects are made of and the force with which the objects are colliding, friction counteracts force that is perpendicular to the collision normal.

Optimization

Collision detection between every object in the scene has the complexity of O(n²). This means that every object added to the scene increases the computation time for collision detection exponentially. There are many approaches to solve this problem. This project implements two of the simpler ones - inactive objects and broad/narrow phase approach. The former works by recognizing when objects have stopped moving and meaningfully interacting with other objects and freezing them until another object interacts with it in some way. The latter is simply running a much less computationally expensive version collision algorithm to find all objects that could collide, and then using a precise approach on those objects.

Results

The resulting application is capable of simulating a domino effect on thousands of objects. This is due to the fact that once the object stops moving it is put into an inactive state and at any one point only about 15 - 20 objects are being fully simulated. The simulation looks realistic and runs smoothly.