Collision Iterators

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 to do these two operations:

• shoot a ray from point gun.pos in direction gun.dir and execute ball.some_procedure() for all balls which colide with that ray.
• execute some_procedure(ball,test_ball) for all balls which collide with a test ball

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

ray.init(gun.pos, gun.dir); 
grid.initRayCating( ray );
while( box = grid.nextBoxOnRay() ){
    objects = box.getObjects()
    for( ball : objects ){
        // if we care if balls are ordered according to the
        //    position of intersection point along the ray
        //    it would be more complicated
        if( ball.collide( ray ) ) ball.some_procedure();  // narrow phase
    }
}

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:

for( balls : grid.( test_ball.pos, interaction_radius ) ){ // this iterator takes care about order ball.some_procedure(); // }

for( balls : grid.rayIterator_Ordered( gun.pos, gun.dir ) ){ // this iterator takes care about order ball.some_procedure(); // }