Collision Systems for C++98

Abstract:

The code simulates the colliding motion of N frictionless hard sphere particles that exhibit perfect elastic collision in an event-driven simulation.

Constraints:

Each particle is assumed to be a hard sphere (think pool balls or something) and confined in a unit box. This is technically known as a hard sphere or hard circle model, depending on the number of available dimensions. Constraints are as follows:

• Particles have a known position (x,y), velocity (vx,vy), radius (r), and mass. All except the mass are represented in double floating point (0 <= d <= 1).
• Perfect elastic collisions with everything
• No loss of total kinetic energy due to deformation of particles, friction, or elasticity of material.
• No external forces will be applied
• Particles move in straight lines between collisions.
• Particles may only collide two at a time (this makes simulating billiards incorrect, since a 3-way collision has different physics than two 2-way collisions).

Simulation:

There are 2 ways to implement this simulation. Time driven and event driven.

• Time-driven: For each time unit dt, move each particle the appropriate amounts. If a particle overlaps another, roll back time for the 2 particles, simulate the collision, and repeat the process. Unforntunately this results in N^2 runtime, as for each increment of dt will require a search between each possible pair of particles. Furthermore, depending on the size of dt, the simulation could take an insane amount of time (if dt is small) or it could miss collisions if two particles pass through each other (with a large dt). Thus the simulation is timely and inaccurate.
• Event-Driven: Create a priority queue, and for each particle p, determine when it will collide with another particle or the boundaries of the box and add the event to the PQ. Move each particle by dt until the next collision event. Then for each particle invovled, update velocities, calculate new imminent collisions, and add the new events to the PQ. Although the initilazation will cost N^2 runtime, each subsequent update to a particle(s) after a collision will take between N and 2N runtime. Furthermore collisions will not be skipped and unnessecary calculations will not be performed; it is not nessecary to make any new calculations when a collision event is not taking place.