Sweep Tests
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 Real Time Rendering Intersection Tests Page (Website + Book)
- Geometric Tools (Books + Website)
- Real Time Collision Detection (Book)
- Solid / Collision Detection in Interactive 3D Environments(Book + Website + Collision Library)
The rough plan for posts I will make(very much subject to change):
- Sweeping a sphere against a point and another sphere
- Sweeping a sphere against a line/edge
- Sweeping a sphere against a plane
- Sweeping a sphere against a polygon
- Capsules and sweeping them against a sphere
- Sweeping a capsule against a point
- Sweeping a capsule against a line
- Sweeping a capsule against a polygon
- Sweeping a capsule against another capsule
- Sweeping a polyhedron against points, faces and edges
- 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).
