Collision Iterators - ProkopHapala/SimpleSimulationEngine GitHub Wiki

Consider I have a spacial datastructure which divide space into some bounding boxes ( e.g. 3D grid, octree, bounding volume hierarchy ), in each box I have stored several objects (e.g. spherical balls).

Now I would like e.g. these operations:

• ball-ball collision - execute some_procedure(ball,test_ball) for all balls which collide with a test ball
• ray-ball collision - shoot a ray from point gun.pos in direction gun.dir and execute ball.some_procedure()
  • for the first ball ray hits (i.e. closest to the gun.pos ).
  • for all balls ray hits until it consumes all ray_energy

In both cases the collision problem can be separated to broad phase and narrow phase.

• broad phase depends on details of spacial datastructure
• narrow phase depends on details of particular object type (e.g. of ball)

The straightforward code for this operations (without iterators) would look something like this:

ball-ball collision

boxes = grid.getOverlapingBoxes( test_ball.pos, interaction_radius );
for( box : boxes ){ 
   for( ball : box.getObjects() ){
      if( test_ball.collide( ball ) )  some_procedure(ball,test_ball); // narrow phase
   }
}

ball-ray collision - just first hit

ray.init(gun.pos, gun.dir); 
grid.initRayCating( ray );
while( box = grid.nextBoxOnRay() ){
    // find the closest collision
    double tmin = +infinity;
    int    imin = -1;
    for( i,ball : box.getObjects() ){
        double t_hit = ball.collide( ray );
        if( t_hit < tmin ) { imin=i; tmin=t_hit };
    }
    if( imin >= 0 ) ball.some_procedure();
}

ball-ray collision - penetrate multiple targets

ray_energy = 1.0;
ray.init(gun.pos, gun.dir); 
grid.initRayCating( ray );
while( box = grid.nextBoxOnRay() ){
    objects            = box.getObjects();
    sorted_hit_objects = sort_by_collision_distance( objects, ray );
    for( i,ball : sorted_hit_objects ){
       ray_energy -= ball.some_procedure( ray_energy );
       if( ray_energy < 0 ) break;
    }
}

Not nice things about this solutions:

• user have to write quite lot of code each time he wants to test for some collisions
• especially if order is important (as in case of ball-ray collision ) it is quite complex code on user side
• if objects or boxes are returned as some container (e.g. array). This could make several problems
  • user should take care about this containers ( either allocate/deallocate them, or keep them as some static temporaries )

With iterators

this complicated logic can be enclosed into custom iterators which will return to user the objects one-by-one in proper order. The user code would then look like this:

ball-ball collision

for( balls : grid.sphereIterator( test_ball.pos, interaction_radius ) ){ // iterator takes care about broad phase 
    if( test_ball.collide( ball ) )  some_procedure(ball,test_ball);  // narrow phase
}

ball-ray collision - just first hit

double tmin = +infinity;
int    imin = -1;
for( balls : grid.rayCollisionIterator_sorted( gun.pos, gun.dir) ){ // this iterator takes care about ordering
    ball.some_procedure( i );
    break;
}

ball-ray collision - penetrate multiple targets

ray_energy = 1.0;
for( balls : grid.rayCollisionIterator_sorted( gun.pos, gun.dir) ){ // this iterator takes care about ordering
    ray_energy -= ball.some_procedure( ray_energy );
    if( ray_energy < 0 ) break;
}