Research : Spatial : Sweep and Prune

Background

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.

Setup

Assume (for the sake of simplification) that we are working in two dimensions, $x$ and $y$ . Let $S$ be a set of objects we’re considering for collision, with each $s \in S$ using $s_x$ and $s_y$ for the position of the object in their respective dimensions. Further, assume that each $s$ is unique and identified by $s_{id}$ . Finally, let $r_s$ be the radius of the object (which we will assume is the same in all dimensions).

Intervals & Points

For each object $s$ , we will generate two intervals $X_s$ and $Y_s$ , defined as follows:

$X_s = (s_x - r_s, s_x + r_s),\ \ Y_s = (s_y - r_s, s_y + r_s)$

. Points in these intervals are ordered based on two criteria. For a point $p$ , let $d(p)$ be the position of $p$ , and let $t(p) = 0$ if $p$ is the starting point of an interval, with $t(p) = 1$ otherwise. Then for two points $p_1$ and $p_2$ , we have: $p_1 < p_2 \iff d(p_1) < d(p_2) \text{ or } ( d(p_1) = d(p_2) \text{ and } t(p_1) < t(p_2) )$ . 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¹:

-- 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

Algorithm

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

Analysis

Assume that update_intervals() runs in $O(n)$ , and that a generic table.sort() will run in $O(n\log{n})$ , and that the set_intersection() algorithm runs in $O(n)$ . 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 $O(n)$ time. As we’re then iterating over every endpoint, the worst case is an $O(n^2)$ runtime.

The intersection_sweep algorithm is thus the dominant factor in the algorithm, giving us $O(n^2)$ worst-case complexity. In general, intersection_sweep will have an average $O(nm)$ running time, where $m$ is the number of intersecting objects.

Improvements

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 $O(n + d)$ , where $d$ 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 $O(nk)$ , where $k$ is the number of objects involved in intersections from the previous axes.

Notes and References

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.
↩