Collision detection in practice

By , last updated July 12, 2019

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

Simulated Solar system

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;
}

Runge-Kutta 2

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;
	}
}

Runge-Kutta 4

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.Runge-Kutta fourth-order method

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.