Collision detection for particle systems

One of the things I’m working on for motor2 is the inclusion of a particle system, mainly for simulating bullets, fluids and soft bodies. The main challenge is to build a fast particle-polygon collision detection which would be able to compute the penetration depth and collision normal for a huge amount of particles. The containment check could be done with a binary search over the vertices of the polygon, an O(n log(n)) operation, but it doesn’t give you the information to push the particle outward.

After reading some papers I finally found the solution to my problem, namely a signed distance field.
A distance field is a scalar field that measures the distance from a given point to an object or data volume. Each element in a distance field specifies its minimum euclidean distance to the shape. Positive and negative distances are used to distinguish outside and inside of the shape (thus signed). This information is precomputed and stored with the shape.

Actually it’s very simple in 2D: First, the shape’s bounding box is divided into a regular grid. Second, each grid cell is analyzed – it can be either outside, inside or intersecting one or multiple edges. For the inside and outside case, a flag is stored with the cell. For the intersecting case, all piercing edges are found and converted into planes, stored in the point-normal form, n (X – P) = 0. At the end you are left with a very simple plane-point distance check.
A lower resolution requires less memory, but makes the lookup slower. The opposite is true for very small cells, because then each cell is likely to contain only one edge to test against. The demo below shows the ‘rasterized’ distance field:

In the next demo you see a ‘pseudo color representation’ of the distance field. As you see, no information is lost, and the original shape can be reconstructed by extracting a point-based contour at true Euclidean distance and any level of accuracy:

The last demo shows the minimum translation distance vector (MDT) obtained by evaluating the distance field. The vector, with its length and direction has the required information to push the particle outward if it’s contained by the polygon:

The steps are:

  1. Transform the particle to the polygon’s local space.
  2. Evaluate the distance field and resolve collision.
  3. Transform the new particle’s position back to world space.

4 dot products, 6 additions (step 1 + 3) and in the best case one array lookup and one dot product (step 2) are required. Of course, the method can fail if a particle moves very fast, in this case the particle’s movement should be modeled as a ray, which is then clipped against the polygon.

The source code for the distance field is not yet included in the motor2 svn, since it would mess up existing classes, but it will be very soon.