This is an example implementation of my method described in NOTES10# written in c++.
( This type of collision detection is ideal if you might have fast moving objects in your game, but if that isn't the case and you're looking for something simpler then click here for an explaination of a more simple method. )
I cut this out of Bal-Maz which (when I wrote this atleast) keeps the ball in a 2D plane, so I commented-out the code pertaining to one of the ordinates, but that code can probably be re-instated quite easily if you want to go 3D.
Unfortunately this routine wont work as-is, you'll have to do a bit of hacking to get it working in your program... for example since there is a collision table of objects not included below which cte_A_ptr etc. point to, you could instead specify your pair of spheres by passing previous and new sphere center positions as parameters for A_start_ptr, A_end_ptr etc.
typedef struct
{
float intrusion; // Intrusion including the length of travel when sphere passes right through a sphere and out the other side.
float closest_prop; // The proportion of the attempted travel before reaching the closest point with the line of the other object.
float inverse_closest_prop; // (1.0 - closest_prop)
float closest_dis; // The distance that the collision sphere centres are from each other when they are closest together.
float pre_coll_travel; // Only some collision detection routines calculate this it usually has to be calculated in collision_action()
long debug_info; // (Only for debugging purposes)
vector_3D world_touch_point; // Only some collision detection routines calculate this it usually has to be calculated in collision_action()
float speed_A; // Effectively the length of the first 4D line (from previous collision centre to new collision centre)
float speed_B; // Effectively the length of the first 4D line (from previous collision centre to new collision centre)
coll_table_ent_struct *cte_A_ptr;
coll_table_ent_struct *cte_B_ptr;
} coll_result_struct;
inline void reset_coll_result_struct( coll_result_struct *p_result_ptr )
{
p_result_ptr->intrusion = 0.0f;
p_result_ptr->closest_prop = 0.0f;
p_result_ptr->inverse_closest_prop = 0.0f;
p_result_ptr->closest_dis = 0.0f;
p_result_ptr->pre_coll_travel = 0.0f;
p_result_ptr->debug_info = 0;
p_result_ptr->world_touch_point.x =
p_result_ptr->world_touch_point.y =
p_result_ptr->world_touch_point.z = 0.0f;
p_result_ptr->speed_A = p_result_ptr->speed_B = -1.0f; // signify that fields not set.
p_result_ptr->cte_A_ptr = 0;
p_result_ptr->cte_B_ptr = 0;
}
long collision_system_class::sphere_collision( coll_result_struct *p_result,
long v_simple_test_required, long v_debug_flag )
{
// 4 dimensional linear sphere to sphere collision detection routine.
// (c) Jon P.
// (Floating point version)
// (Simplified version for games working on a 2D plane only)
//
// Main features:- no matter how fast the two spheres are travelling
// (or in other words no matter how far the spheres travel in a single frame)
// this routine will not miss the collision (provided their path is linear).
// Both spheres, or just one sphere can be moving.
// There is no overhead for spheres traveling very fast -- it does not
// have to do any binary chopping or any kind of iterative work.
//
// Specify 'v_simple_test_required' as non-zero for the quickest execution
// of this routine... but if you do specify this flag then from the result
// you will only beable to tell if there has been a collision or not and
// you will be given any more data....
// if 'v_simple_test_required' is specified as zero however you get various
// details back including at what point in their travel he spheres were closest
// as a proportion (from which you can calculate their collision points).
//
// The newest points are A_end_ptr and B_end_ptr.
// The previous points (i.e. starting points) are A_start_ptr and B_start_ptr.
//
// It is essential that all result fields in p_result (like speed and
// intrusion) are reset before calling this routine.
//
// p_result->speed_A and p_result->speed_B are only calculated
// when they are needed in this routine and so they should be checked
// against zero when the values are used outside this routine and if
// they are zero they should be calculated.
//
// Note that fields other than 'p_result->intrusion' will only be set when
// 'p_result->intrusion' is returned as > 0 and when the v_simple_test_required
// parameter was not set.
//
// Abreviations:-
// _prop = proportion of.
// _dis = distance
// @2 = some code commented-out for this 2D plane implementation to save CPU.
//
//
register float temp, temp2;
float min_dis, min_dis_squared, end_dis_squared, start_dis_squared,
mid_dis_squared, quarter_dis_squared,
end_points_furthest_apart,
dx, dz; //dy
vector_3D *A_end_ptr, *A_start_ptr, *B_end_ptr, *B_start_ptr;
// One sphere's position and previous position...
A_end_ptr = &p_result->cte_A_ptr->info.ma_sphere.centre;
A_start_ptr = &p_result->cte_A_ptr->info.ma_sphere.prev_centre;
// The other sphere's position and previous position...
B_end_ptr = &p_result->cte_B_ptr->info.ma_sphere.centre;
B_start_ptr = &p_result->cte_B_ptr->info.ma_sphere.prev_centre;
min_dis = p_result->cte_A_ptr->info.ma_sphere.radius +
p_result->cte_B_ptr->info.ma_sphere.radius; // combined collision sphere radii.
// ... from now-on compare squared distances where possible but when distances need
// to be subtracted use real distances.
#if DIAGS
if ( min_dis > 5000 )
{
err( 132 );
return 0;
}
#endif
// Quick calc when objects totally stationary...
if ( A_start_ptr->x == A_end_ptr->x &&
A_start_ptr->z == A_end_ptr->z &&
B_start_ptr->x == B_end_ptr->x &&
B_start_ptr->z == B_end_ptr->z )
{ //... (@2 removed Ys above for 2D plane implemantation)
p_result->intrusion = min_dis - fp_distance( A_end_ptr, B_end_ptr );
if ( p_result->intrusion < 0.0f )
p_result->intrusion = 0.0f; // no intrusion
else
p_result->speed_A = p_result->speed_B = 0.0f; // intruded so set speed
return 0;
}
min_dis_squared = min_dis * min_dis;
temp = A_start_ptr->x - B_start_ptr->x;
temp2 = temp * temp;
//temp = A_start_ptr->y - B_start_ptr->y; // (Commented-out for the 2D plane version)
//temp2 += temp * temp; // ... @2
temp = A_start_ptr->z - B_start_ptr->z;
temp *= temp;
start_dis_squared = temp2 + temp;
temp = A_end_ptr->x - B_end_ptr->x;
temp2 = temp * temp;
//temp = A_end_ptr->y - B_end_ptr->y;
//temp2 += temp * temp; // @2
temp = A_end_ptr->z - B_end_ptr->z;
temp *= temp;
end_dis_squared = temp2 + temp;
temp = A_end_ptr->x + A_start_ptr->x;
temp -= B_end_ptr->x;
temp -= B_start_ptr->x;
temp /= 2.0f;
temp2 = temp * temp;
//temp = A_end_ptr->y + A_start_ptr->y;
//temp -= B_end_ptr->y;
//temp -= B_start_ptr->y;
//temp2 += temp * temp; // @2
temp = A_end_ptr->z + A_start_ptr->z;
temp -= B_end_ptr->z;
temp -= B_start_ptr->z;
temp /= 2.0f;
temp = temp * temp;
mid_dis_squared = temp + temp2;
temp = end_dis_squared - start_dis_squared;
if ( temp > 0 ) // END POINTS ARE FURTHER APART THAN THE START POINTS...
{
end_points_furthest_apart = 1;
temp = A_end_ptr->x + A_end_ptr->x + A_end_ptr->x;
temp += A_start_ptr->x;
temp2 = B_end_ptr->x + B_end_ptr->x + B_end_ptr->x;
temp2 += B_start_ptr->x;
temp -= temp2; // dx * 4
temp /= 4.0f; // Mean value.
quarter_dis_squared = temp * temp;
//temp = A_end_ptr->y + A_end_ptr->y + A_end_ptr->y; // (commented-out for the 2D plane implementation)
//temp += A_start_ptr->y;
//temp2 = B_end_ptr->y + B_end_ptr->y + B_end_ptr->y;
//temp2 += B_start_ptr->y;
//temp -= temp2; // dy * 4
//temp /= 4.0f;
//quarter_dis_squared += temp * temp; // @2
temp = A_end_ptr->z + A_end_ptr->z + A_end_ptr->z;
temp += A_start_ptr->z;
temp2 = B_end_ptr->z + B_end_ptr->z + B_end_ptr->z;
temp2 += B_start_ptr->z;
temp -= temp2; // dz * 4
temp /= 4.0f;
quarter_dis_squared += temp * temp;
temp = quarter_dis_squared - mid_dis_squared;
temp2 = end_dis_squared - quarter_dis_squared;
}
else // START POINTS ARE FURTHER APART THAN THE END POINTS...
{
end_points_furthest_apart = 0;
temp = A_start_ptr->x + A_start_ptr->x + A_start_ptr->x;
temp += A_end_ptr->x;
temp2 = B_start_ptr->x + B_start_ptr->x + B_start_ptr->x;
temp2 += B_end_ptr->x;
temp -= temp2; // dx * 4
temp /= 4.0f; // Mean value.
quarter_dis_squared = temp * temp;
//temp = A_start_ptr->vy + A_start_ptr->vy + A_start_ptr->vy;
//temp += A_end_ptr->vy;
//temp2 = B_start_ptr->vy + B_start_ptr->vy + B_start_ptr->vy;
//temp2 += B_end_ptr->vy;
//temp -= temp2; // dy * 4
// temp /= 4.0f;
//quarter_dis_squared += temp * temp; //@2
temp = A_start_ptr->z + A_start_ptr->z + A_start_ptr->z;
temp += A_end_ptr->z;
temp2 = B_start_ptr->z + B_start_ptr->z + B_start_ptr->z;
temp2 += B_end_ptr->z;
temp -= temp2; // dz * 4
temp /= 4.0f; // Mean value.
quarter_dis_squared += temp * temp;
temp = quarter_dis_squared - mid_dis_squared;
temp2 = start_dis_squared - quarter_dis_squared;
}
if ( temp2 )
temp /= temp2;
else
temp = MASSIVE_FLOAT;
temp -= 0.333958f;
temp *= 1.31466f;
temp2 = temp;
temp *= temp2;
temp *= temp2;
temp -= temp2 / 4.0f;
temp *= 2.2f;
temp += temp2;
temp += 0.5f;
if ( end_points_furthest_apart )
{ // Points are diverging...
if ( v_simple_test_required == 0 && temp > 0.99f )
{
p_result->intrusion = -3.0f; // A negative num is returned to denote 'no collision'.
return 0;
}
p_result->closest_prop = 1.0f - temp;
p_result->inverse_closest_prop = temp;
}
else // Points are converging...
{
p_result->closest_prop = temp; // reverse to make the proportion relative to the end point.
p_result->inverse_closest_prop = 1.0f - temp;
}
if ( p_result->closest_prop > 1.0f ) p_result->closest_prop = 1.0f;
if ( p_result->closest_prop < 0.0f ) p_result->closest_prop = 0.0f;
if ( p_result->inverse_closest_prop > 1.0f ) p_result->inverse_closest_prop = 1.0f;
if ( p_result->inverse_closest_prop < 0.0f ) p_result->inverse_closest_prop = 0.0f;
dx = A_start_ptr->x * p_result->inverse_closest_prop;
dx += A_end_ptr->x * p_result->closest_prop;
dx -= B_start_ptr->x * p_result->inverse_closest_prop;
dx -= B_end_ptr->x * p_result->closest_prop;
//dy = A_start_ptr->y * p_result->inverse_closest_prop;
//dy += A_end_ptr->y * p_result->closest_prop;
//dy -= B_start_ptr->y * p_result->inverse_closest_prop;
//dy -= B_end_ptr->y * p_result->closest_prop;
dz = A_start_ptr->z * p_result->inverse_closest_prop;
dz += A_end_ptr->z * p_result->closest_prop;
dz -= B_start_ptr->z * p_result->inverse_closest_prop;
dz -= B_end_ptr->z * p_result->closest_prop;
//temp = fp_length( dx, dy, dz ); @2
temp = fp_length( dx, dz, 0.0f );
if ( temp >= min_dis )
{
p_result->intrusion = -4.0f; // A negative num is returned to denote 'no collision'.
return 0;
}
p_result->closest_dis = temp;
p_result->speed_A = fp_distance( A_end_ptr, A_start_ptr );
p_result->speed_B = fp_distance( B_end_ptr, B_start_ptr );
if ( p_result->closest_prop < 1.0f )
{
temp = min_dis - temp; // add the notional intrusion at the start of the travel
temp = temp + temp; // add the notional intrusion at the end of the lines
temp2 = p_result->speed_A + p_result->speed_B;
if ( p_result->closest_prop > 0 )
{ // add-on the length that the lines have intruded into each-other....
temp2 *= p_result->inverse_closest_prop;
}
p_result->intrusion = temp + temp2;
}
else
{
p_result->intrusion = min_dis - temp;
}
return 0;
}