David's Blog

Mostly Hobby Stuff

Sweep Tests

leave a comment »

Sweep tests are an essential part of any programmers tool box if they are interested in writing a 3D application. Sadly the amount of information about them is somewhat limited and often inaccessible, at least for the more sophisticated tests. So I plan on writing a number of blog posts describing the approach I have taken writing my library of sweep tests. These posts will work from basic principles, developing the more sophisticated tests based on simpler tests.

To start with I should probably define what a sweep test is: given a geometric shape and its position in space, check which shapes it intersects when it is swept along a path, returning the first shape that it intersects, the “time of impact”, the intersection point and the intersection normal. In these posts I will restrict my discussion to linear sweeps along a single line. In general sweep tests can also be formulated for rotational paths as well, but I will not cover these. In addition I will only cover “discrete” sweep tests, ie I will formulate each test individually rather than using a general method such as an adapted GJK approach.

There is a bunch of information available online(and in paper form) concerning intersection testing and some concerning sweep tests, below I will list a few useful resources:

The rough plan for posts I will make(very much subject to change):

  1. Sweeping a sphere against a point and another sphere
  2. Sweeping a sphere against a line/edge
  3. Sweeping a sphere against a plane
  4. Sweeping a sphere against a polygon
  5. Capsules and sweeping them against a sphere
  6. Sweeping a capsule against a point
  7. Sweeping a capsule against a line
  8. Sweeping a capsule against a polygon
  9. Sweeping a capsule against another capsule
  10. Sweeping a polyhedron against points, faces and edges
  11. Sweeping a polyhedron against another polyhedron

I should note that I derived the tests I use from first principles and then debugged/optimized them so that they were suitable for my needs. I do not make any assertions about their robustness or performance except that I have been using them for a while to handle player control and moving platforms etc in my hobby game.

An important point to mention is that a lot of the difficulty in writing sweep tests is related to establishing a framework to ensure they are easy to debug and robust. The approach I took was to add a command to my level editor which allowed me to experiment with the sweep tests with a visualization of important information. Being able to do this interactively is essential as most problems are related to long thin objects, objects of different scales, grazing contacts etc. In addition I created a number of unit tests to tackle regressions(however testing all permutations this way is prohibitively expensive).


Written by therealdblack

June 26, 2010 at 1:20 pm

Posted in Sweep Tests

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: