The Algorithm

The voxel method's parallel implementation is perhaps most succinctly described by its CHARM++ interface file:

module parCollide {
  message triListMsg;
    
  array [3D] collideVoxel {
    entry collideVoxel();
    entry [createhere] void add(triListMsg *);
    entry void startCollision(void);
  };

  group collideMgr : syncReductionMgr {
    entry collideMgr(CkArrayID collideVoxels);
    entry void voxelMessageRecvd(void);
  };
};

collideVoxel is a grid of voxels- a sparse three-dimensional CHARM++ parallel array. This allows voxels to be created on any processor, receive messages from any processor, and migrate from processor to processor.

collideVoxel::add is called to add a list of objects to the voxel. Because add is declared createhere, if an add message is sent to a non-existent grid location, CHARM++ will create a new collideVoxel object on the sending processor to handle the request. triListMsg, the ``message'' parameter to add, contains a list of triangles to be collided by the voxel.

collideVoxel::startCollision runs the serial collision detection subscheme on all the voxel's accumulated objects. We use the RCB method described in Section ; although for triangles the BSP method can be nearly as efficient. An interesting approach might be to recursively apply the voxel method, especially if many objects lie in a single voxel.

collideMgr is a CHARM++ group, a special collection of parallel objects with exactly one object on every processor. The collideMgr sequences the collision detection computation.