The Galton Board or Quincunx was developed in order to demonstrate the central limit theorem. It is a simple way to visualize a normal distribution. During the first trimester in my Master’s year for the Simulation module we had this coursework in which we were supposed to create a physics engine in order virtually simulate this experiment. I have choose C++ and OpenGL and I implemented full 3D rigid body motion with friction, angular velocity and speculative contacts (a technique also introduced in Nvidia PhysX 3.4). The biggest challenge of this project was to implement a stable and robust collision detection method which should also be not very computational expensive. I also had to re-familiarize myself with differential calculus in order to better understand the link between mathematics and motion physics.

The following section describes the various collision detection methods considered and the advantages of the chosen one.

COLLISION DETECTION AND SOLVING

A lot of time has been spent researching the topic of real-time collision detection which seems to be avery difficult problem to solve perfectly. Each approach has its advantages and disadvantages. On theone hand discrete detection is very easy to implement however it lacks stability and suffers fromtunneling (Figure 1).

On the other hand, complete dynamic collision detection can become very computationally expensivebecause the possible contacts need to be ordered by the time of impact in order to avoid strangebehaviors. Then after resolving the collisions which happen first the contacts needs to be regeneratedand reordered again by time of impact. This happens in order to avoid the following situation: consider asphere, A, moving towards an AABB object, B. If dynamic collision finds that for the rest of the currentframe A will hit B it can compute the time of impact (TOI), move A to the correct position and the for therest of the frame (deltaTime – TOI) compute the collision response. The problem happens if we assumethat another sphere C will intersect with A during A’s journey towards B and will totally change thetrajectory making our first assumption and computation incorrect (Figure 2).

The chosen and implemented technique in the project is Speculative Dynamic Collision Detection whichis a type of dynamic collision with better performance and easier implementation. It was described byPaul Firth on his blog (Firth, 2011). It works by finding it there will be a collision in the next frame andthen reduces the velocity of the object in order to perfectly hit and be in contact with the obstacle in thenext frame. The reduction in velocity is applied as an impulse.

This technique will make the simulation very stable compared to discrete collision detection and also itcan be applied in multiple iterations for better accuracy. The tests done have shown that a number of 3or more iterations produce decent results. In order to avoid incorrect results when computing impactresponse (such as bounce), the old velocity sometimes needs to be stores and provided to the solverinstead of the actual velocity.Collision checking has been implemented between sphere – OBB, sphere – cylinder and sphere – sphere.Each of the checks has some early exits condition in order to reduce computation time if the objects arevery far apart.In order to solve the collision, at impact, a model which handles elasticity, friction and full rigid bodymotion has been implemented allowing for realistic behaviors. It computes both a normal impulse basedon elasticity and a tangential force based on the friction value. The implementation of the solver wasbased on (Baraff & Witkin, 1997).

NUMERICAL INTEGRATION

The numerical integration available in this project is Euler and Runge Kutta 4. The implementation issimilar to the one presented in the slides and described more in-depth in An Introduction to PhysicallyBased Modelling (Baraff & Witkin, 1997). The rigidbody contains a State object which can be derivedallowing for easy implementation of some numerical integration techniques. However, it does not allowto easy implement integrations which assume that the State is a pair of ordinary equation (such as SemiExplicit Euler).

REFERENCES

Baraff , D. & Witkin, A., 1997. Physically Based Modeling: Principles and Practice. Online Siggraph ’97.
Decaudin, P., 2013. AntTweakBar. [Online] Available at: http://anttweakbar.sourceforge.net/doc/
[Accessed December 2018].
Firth, P., 2011. https://wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collisionengine-approach-part-1/. [Online] Available at: https://wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collisionengine-approach-part-1/
[Accessed November 2018].
GLM, 2017. OpenGL Mathematics. [Online] Available at: https://glm.g-truc.net/0.9.9/index.html
[Accessed November 2018].