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:

- Transform the particle to the polygon’s local space.
- Evaluate the distance field and resolve collision.
- 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.

Why not sort CCW all polygon vertex along with the tested point.

Find the vertex in the sorted Array.

Take the points before and after the tested vertex in the Array.

Check Point-Line distance between the signed line-segment made of these 2 points and the tested-point.

Yet we have.

O(n log n) + //CCW Sort

O(n) + //Linear Search

O(1) //Point-Line Distance

= O(nlogn)

Oh! Forgot!

Mine was just another idea!

I think that CCW-Sort approach works only to Inside-Outside tests. Information of wich polygon-edge is closer to the point isn’t very accurate!

But this Distance-Field technique was really nice! Path planning uses some of its features too!

Very nice work! I’m really looking forward to try this out.

Thanks for sharing! Looks really useful!

Every time I find a new article on your blog, I feel like a kid who just got his hands on a new toy. Great read!

Love the article, but a few of the steps are a bit over my head. If you ever feel the need to dig deeper, I’d love to understand what happened between step 1 and step 2. Step 2 still seems magic; there is something I’m missing.

When you say “extracting a point-based contour at true Euclidean distance”, how do you connect the points?

actually it’s very easy, for step2 the only tricky thing is to collect the edges intersecting a grid cell. there are many ways to do this. in my case I’m casting a ray through the grid similar to bresenham’s algorithm for drawing lines.

And for the point-based contour: you can’t add the points together, it simply means that you get an image of the shape with all details captured (no information is lost because there is no compression/approximation going on.

If I’m not mistaken, you also need some float-to-int conversion (before indexing in your field array cache), and this is a pretty expensive operation.

Great information. I’m very interested in distance fields for non-convex collision detection. Are you going to post the source soon?

I’m actually using an index grid for fluid dynamics in my engine:

http://svn.dsource.org/projects/blaze/downloads/FluiDemo.zip

Very-very n1ce. But why there are no “round”-shaped examples?