There are a number of methods to choose when programming a collision detection. They vary from simple to complex and from accurate to not at all.

Euler method is the simplest way to go while programming a collision detection between objects. It’s also the most inaccurate one. While programming our solar system collided Venus with the Sun already after 5 seconds of simulation.

The Euler method is a first-order numerical procedure for solving ordinary differential equations (ODEs) with a given initial value. Applied to collision detection it calculates the next velocity and next position of an object according to the force applied and time passed. You can read more about the method here at wiki.

Here is how the program will look like in C++:

Calculating the next velocity:

//length of the array with all objects int size = objects.size(); for (int i=0; i<size; i++) { mamma = objects[i]; mamma->vel = mamma->force / mamma->masse * dt + mamma->vel; }

Calculating the next position of the object:

for (int i=0; i<size; i++) { mamma = objects[i]; mamma->pos = mamma->pos + mamma->vel * dt; }

The Runge-Kutta methods are more complex but also more powerful methods. The Runge-Kutta 2 is the second-order numerical procedure for solving ODEs (ordinary differential equations).

//length of the array with all objects int size = objects.size(); for (int i=0; i<size; i++) { Array< Vector3D > start_pos; Array< Vector3D > start_speed; Array< Vector3D > dsk1; Array< Vector3D > vk1; Vector3D tmp_dsk1, tmp_vk1, tmp_ak1, tmp_dsk2, tmp_vk2, tmp_ak2; for (i = 0; i < size; i++) { start_pos.add(objects[i]->pos); start_speed.add(objects[i]->vel); tmp_vk1 = objects[i]->axx*dt; tmp_dsk1 = objects[i]->vel*dt + objects[i]->axx*dt*dt*0.5; dsk1.add(tmp_dsk1); vk1.add(tmp_vk1); objects[i]->vel = objects[i]->vel + tmp_vk1; } for(i = 0; i<size; i++) { tmp_vk2 = (vk1[i] + objects[i]->axx*dt)*0.5; tmp_dsk2 = (dsk1[i] + objects[i]->vel*dt + objects[i]->axx*0.5*dt*dt)*0.5; objects[i]->vel = start_speed[i] + tmp_vk2; objects[i]->pos = start_pos[i] + tmp_dsk2; } }

The fourth-order Runge-Kutta methods is especially powerful and popular. This particular method is so commonly used that it is often referred to as “RK4”, “classical Runge-Kutta method” or simply as “the Rungeâ€“Kutta method” [wiki].

This method takes four trial steps and uses their weighted average to advance the particle according to the formula shown below.

To program this one we follow the theory:

//length of the array with all objects int size = objects.size(); for (int i=0; i<size; i++) { Vector3D start_pos, start_vel; Vector3D dx, dx1, dx2, dx3, dx4, dv, dv1, dv2, dv3, dv4; start_pos = objects[i]->pos; //pos0 start_vel = objects[i]->vel; //vel0 dx1 = objects[i]->vel*dt; dv1 = objects[i]->axx*dt; dx2 = (objects [i]->vel + dv1/2)*dt; dv2 = (objects[i]->axx + objects[i]->axx*dx1/2)*dt; dx3 = (objects [i]->vel + dv2/2)*dt; dv3 = (objects[i]->axx + objects[i]->axx*dx2/2)*dt; dx4 = (objects [i]->vel + dv3/2)*dt; dv4 = (objects[i]->axx + objects[i]->axx*dx3/2)*dt; dx = (dx1 + dx2*2 + dx3*2 + dx4)/6; //new delta position dv = (dv1 + dv2*2 + dv3*2 + dv4)/6; //new delta velocity objects[i]->vel = start_vel + dv; if(objects[i]->id!=2||objects[i]->id!=8) objects[i]->pos = start_pos + dx; }

In this sample we used an operator overloading for multiplication of two vectors to simplify the code. We also created a template for a point. A Point3D is simple a point with 3 coordinates (x, y, z). Here is how we override a multiplication of two vectors:

Point<T,n> operator*(Point<T,n> t) { Point<T,n> m; for (int i=0; i<n; i++) m.mat[i] = mat[i] * t.mat[i]; return m; }

Senior Software Engineer developing all kinds of stuff.