See Collision Detection for a general description of the problem.
As the Wikipedia article on Sweep and Prune is a bit light on details, I’ll elaborate on the general idea of a sweep-and-prune algorithm here.
Collision detection is usually done in a two-phase approach in order to cut down on the amount of work. In a simulation where the world has objects with a significant amount of detail, we’d like to quickly determine a likely set of object collisions, then determine from this much smaller set of potential collisions whether a collision has actually occurred.
The first phase is typically called the broad phase. The broad phase will typically check for collisions using a simplified set of geometry for each object. As an example, one could use a general bounding radius for all dimensions (this approach isn’t very accurate for objects that aren’t round), or an axis-aligned bounding box of some sort. In the examples below, we will use a simple bounding radius.
The Sweep and Prune algorithm is a broad-phase algorithm.
Assume (for the sake of simplification) that we are working in two dimensions, and . Let be a set of objects we’re considering for collision, with each using and for the position of the object in their respective dimensions. Further, assume that each is unique and identified by . Finally, let be the radius of the object (which we will assume is the same in all dimensions).
For each object , we will generate two intervals and , defined as follows:
. Points in these intervals are ordered based on two criteria. For a point , let be the position of , and let if is the starting point of an interval, with otherwise. Then for two points and , we have: . Or, in English, a point is less than another one if it has a smaller value, or if their values are the same but the first point is a starting interval and the second one is not.
In code^{1}:
-- START = 0 < 1 = END
function sort_endpoints(a,b)
return a.value < b.value or a.value == b.value and a.ending < b.ending
end
Fundamentally, the algorithm sorts the set of points along each axis. Once sorted, we then iterate over the list and as we cross the starting point for each interval, we add the object associated with the interval to a set of potentially collidable objects. If one object’s interval overlaps another’s in an axis, they have potentially collided. Finally, if a pair of objects has collided on every axis, a collision has occurred.
Given a sorted list, we can find intersections using the following algorithm:
-- given a list of endpoints, returns a list of intersecting objects for an axis
-- endpoints have an object (that the interval is associated with) and an ending
-- (either start or end).
function intersection_sweep(list)
local active = {} -- the set of active intervals
local intersections = {} -- the set of intersecting objects
for _, endpoint in ipairs(list) do
if endpoint.ending == START then
for _, other in pairs(active) do -- we intersected with anything active
table.insert(intersections, { other, endpoint.object })
end
active[endpoint.object] = endpoint.object
else
active[endpoint.object] = nil
end
end
return intersections
end
Using intersection_sweep, and assuming we have a set_intersection function, we then have:
-- returns a list of collisions
-- assume intervals_x, intervals_y are the lists of intervals
-- for their associated axes.
function collisions()
update_intervals() -- updates the intervals based on object position
table.sort(intervals_x, sort_endpoints)
table.sort(intervals_y, sort_endpoints)
local x_collisions = intersection_sweep(intervals_x)
local y_collisions = intersection_sweep(intervals_y)
return set_intersection(x_collisions, y_collisions)
end
Assume that update_intervals() runs in , and that a generic table.sort() will run in , and that the set_intersection() algorithm runs in . It remains to determine the worst-case behavior of the intersection_sweep.
Looking at the algorithm, it’s clear that if every interval is active at the same time, the inner loop will require time. As we’re then iterating over every endpoint, the worst case is an runtime.
The intersection_sweep algorithm is thus the dominant factor in the algorithm, giving us worst-case complexity. In general, intersection_sweep will have an average running time, where is the number of intersecting objects.
After the lists are sorted the first time, they’re likely to generally stay sorted (with a few inversions on any given world update). As such, an insertion sort for each update would reduce the amount of work necessary in the sort phase to , where is the number of inversions.
Observe that if the second axis intersection sweep knew what the results of the first intersection sweep were, it could completely skip over the inner loop for cases where no intersection occurred for the object on previous axes. This improves the running time for the second (and third, if we’re in 3D) execution to , where is the number of objects involved in intersections from the previous axes.
I realize that Lua’s lack of any data structure outside of a table makes this analysis a bit silly, but humor me. I was researching this while I was learning Lua.
↩