In the first part, we figured that sorting lets us exploit the transitive property of inequality to optimise the number of pairwise tests.

We ended up with - let’s call it a “simplified version”, of the full sweep-and-prune algorithm.

This part explores the more sophisticated versions of sweep-and-prune.

Proper sweep-and-prune 🧐

Let’s see how the original version tackled the problem (Not sure which one’s original, tbh).

First, sorting widthy objects.

To account for the width of objects while keeping the benefits of unambiguous sort order, we track the left and the right edges of each object as two separate points.

This is done by maintaining a separate array of edge points corresponding to the objects’ left & right edges.

See how it works by playing with this draggable demo. The left and right edges of each ball are visualised. These edge points are stored in a sorted array shown below the box.

Of course, we need to initialise the edge data and continually keep them in sync with the objects. I’ll leave that out as an implementation detail.

// todo: extract 2 edges from each object into the array
let edges: Array<{
  object: Object;  // parent object
  x: number;       // x-coordinate
  isLeft: boolean; // true if left edge. false if right
}>;

This sorted array of edges is all we need to facilitate the reduction of unnecessary pairwise tests.

Index as position, position as index

Remember the intersects() function? Let’s focus only on the x-axis checks:

function intersects(object1, object2) {
  return object1.left < object2.right
      && object1.right > object2.left
      /* ... */;
}

We can replace these x-coordinate comparisons with a new approach based on array indices. Since we have a sorted array of every object’s left and right points, finding x-overlaps can be done via index-based searches rather than global pairwise testing.

Take one ball for example. Get the indices of its left and right points, and you can simply run in between those two points in the array to find all x-overlapping objects! This is a very fast linear operation.

Here’s a viz. Try dragging the highlighted ball below and observe the edges enclosed visually and in the sorted array:

The above is a simple 1-to-n overlap detection (which is flawed, btw). For n-to-n overlap detection, turns out there is a neat way to find all overlapping pairs in a single pass!

Chapter 2. Sweeping

To generalise the above to an n-interval overlap scan, imagine a vertical line sweeping across the whole space from left to right. The sweep line keeps track of the objects it is currently touching.

Let’s see what that looks like without collision:

As for the implementation, the line is merely a metaphor. It’s just a visualisation of an iteration through the sorted list of edges.

To keep track of objects touching the line, we maintain a set called touching in code.

Whenever the line runs into an object (a left edge), the object is added to the set. Likewise, whenever it exits an object (right edge), the object is removed from the set.

sort(edges);

const touching = new Set();
for (const edge of edges) {
  if (edge.isLeft) {
    // entering an object
    touching.add(edge.object);
  } else {
    // exiting an object
    touching.delete(edge.object);
  }
}

Once we have the sweep working, detecting overlaps is easy…

👉 Whenever the sweep line enters a new object (a left edge), in addition to inserting it to touching, we can mark it as overlapping with the rest of the objects in touching.

Watch closely whenever the line enters a ball while the line is touching other balls. Detected overlaps are highlighted:

Here’s the updated code for detecting and reporting overlaps:

  sort(edges);
  
  const touching = new Set();
  for (const edge of edges) {
    if (edge.isLeft) {
      // entering an object
+     
+     // the new object is overlapping with the existing ones
+     for (const other of touching) {
+       onOverlapX(other, edge.object);
+     }
+     
      touching.add(edge.object);
    } else {
      // exiting an object
      touching.delete(edge.object);
    }
  }

Chapter 3. Pruning

onOverlapX() is called whenever two balls are overlapping in the x dimension. What about the other dimension, y? What if we’re working with 3D, how about z?

Don’t worry; the sweep is just a broad-phase test, a way to prune candidate pairs in bulk. There will be a narrow-phase test to determine exactly the intersections in each of the remaining pairs.

onOverlapX() can be hooked up to an exact intersection test like the full intersects() function earlier. Or, since we already know that the argument pair overlaps in x, we can just check for y.

onOverlapX = function(object1, object2) {
  // just check for y
  if (object1.top < object2.bottom
   && object1.bottom > object2.top) {
    collide(object1, object2);
  }
}

While the above formula works for most games, a more precise and time-consuming check could be done at this level since most candidates have already been pruned. Our ball example would work better with the following circle intersection test using the Euclidean distance formula🡵:

onOverlapX = function(object1, object2) {
  // compute circle-to-circle intersection
  const distance = sqrt(
      (object1.x - object2.x) ** 2
    + (object1.y - object2.y) ** 2
  );
  if (distance < object1.radius + object2.radius) {
    bounce(object1, object2);
  }
}

Finally, the demo:

Notice that it behaves very similarly to the simplified version. It limits tests to x-overlapping pairs.

The sweep-and-prune algorithm is also known as sort-and-sweep.

Note for higher dimensions

There is a variant which performs the sweep for each axis, not just x. For example in 3D, it maintains three separate sorted lists of edges for x, y, and z. Indeed, this is how the full sweep-and-prune implementation works as described in the original paper by D. Baraff🡵. Object pairs are flagged for overlaps separately per dimension. Pairs flagged in all dimensions would be considered intersecting.

This is the advantage the full sweep-and-prune has over the simplified “sorted pairwise” version. It can prune in multiple dimensions!

Performance of sweep-and-prune

Here’s a side-by-side comparison of the strategies we’ve covered so far! Observe the amount of intersection checks required per frame. 🔍

Let’s analyse the time complexity of 1D sweep-and-prune. 👓

The sort step, again, is O(n log n).

The sweep, which is a linear pass with an inner loop for overlaps, should be O(n + m) in the average case. Again, m is the number of overlaps.

function sweepAndPrune(edges) {
  // O(n log n)
  sort(edges);

  const touching = new Set();

  // O(n + m)
  for (const edge of edges) {
    if (edge.isLeft) {
      // O(1) at best; O(m/n) on average; O(n) at worst
      for (const other of touching) {
        onOverlapX(other, edge.object);
      }
      touching.add(edge.object); 
    } else {
      touching.delete(edge.object);
    }
  }
}

So this sweep-and-prune is O(n log n + m).

That’s great, but it’s the same as simplified sweep-and-prune but with more code and more state to keep tabs on. Can we improve it further?

Small detail, big improvement

Again, let’s ask the question: Where is redundant work being done here?

Let’s look at the sort step, which is the bottleneck of the algorithm according to the analysis.

The following is a visualisation of the sorting of the edges array, using an optimised quicksort🡵 (n log n):

You can see that most of the time, the sort does nothing at all! The list is almost always already sorted from the previous frame.

Even when it becomes unsorted, it usually just takes a couple of swaps to be sorted again. There won’t be more than a few object boundaries changing places in one time step.

Fortunately, the subject of sorting algorithms is well-researched. We’re dealing with the special quality of being nearly-sorted. And one great choice for sorting nearly-sorted lists is insertion sort🡵!

function insertionSort(edges) {
  for (let i = 1; i < edges.length; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (edges[j].x < edges[j + 1].x) break;
      [edges[j], edges[j + 1]] = [edges[j + 1], edges[j]];
    }
  }
}

Insertion sort has a running time of O(n) at best when the list is already sorted or nearly-sorted, and O(n²) at worst when the list is in reverse. We can argue that the average case is O(n), since the list is almost always sorted due to the previous frame’s sort.

Here’s insertion sort in action:

Look at it go!

By switching to insertion sort, we’ve reduced the overall average running time of sweep-and-prune to O(n + m)! Awesome!

Caveat: It’s important to consider the primary axis of sweep-and-prune due to the sweeps plus the nature of insertion sort. It should be the axis where objects are most widely distributed to minimize swaps and overlaps.

Of course, don’t forget about our simplified sweep-and-prune from the first part. Since it has a sort step as well, we can make it insertion sort too. So it can also be O(n + m)! Can we ever top that?

Sweeps and swaps

Well, there is yet another way to optimise this algorithm! Hold on to your balloons, it’s about to get quite dense. 🪨

Look at the insertion sort example above. You can observe that swaps happen when and only when an edge point passes through another edge point.

The event where an edge point passes another can be classified into four cases:

Each swap scenario can mean something significant. Let’s look more closely into each case.

case )↔(. “Entering”

When a right edge from the west swaps with a left edge from the east, we can infer that the corresponding balls are initiating an overlap.

case (↔). “Exiting”

Conversely, when a left edge from the west swaps with a right edge from the east, the corresponding balls cease to overlap.

cases (↔( and )↔)

Edges of the same polarity can swap without affecting the overlappedness of their corresponding balls. We can ignore these ones.

Swaps and sweeps

Based on these swap events we can reframe the mechanics of sweep-and-prune in a new perspective, a bottom-up way centred around the swaps.

A fun way to think about it is to pretend that a right edge is equivalent to a localised sweep line. In that sense, the right edge is the line sweeping over these other left edges.

Just as in a global sweep, passing over left edges will mark the corresponding balls as “touching”; in right-edge-as-a-local-sweep version, swapping left edges will mark its ball as overlapping with the right edge’s ball.

In the global sweep, there is a global touching set keeping track of which balls are in contact with the sweep line. In local swaps, we keep track of overlaps per ball. (More precisely, per pair.)

Lastly, in the global sweep, a right edge means the end of contact with a ball. In a local swap, a left edge passing over a right edge means the same thing. The corresponding balls are unmarked as overlapping.

Essentially, instead of a global sweep line, small local “sweeps” happen around each ball. Swaps become mini-sweeps.

Thus we arrive at the one-dimensional sweep-and-prune’s final form:

function init() {
  overlapping = new Map()
}

function sweepAndPrune(edges) {
  // Insertion sort
  for (let i = 1; i < edges.length; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (edges[j].x < edges[j + 1].x) break;

      // Swap
      [edges[j], edges[j + 1]] = [edges[j + 1], edges[j]];

      // --- Code up until this point is plain insertion sort ---

      // These two edges have just swapped places, process it...
      const edge1 = edges[j];
      const edge2 = edges[j + 1];

      if (edge1.isLeft && !edge2.isLeft) { // case R-L → L-R
        // Mark as overlapping
        overlapping.set(
          key(edge1, edge2),
          [edge1.ball, edge2.ball]
        );
      } else if (!edge1.isLeft && edge2.isLeft) { // case L-R → R-L
        // Unmark as overlapping
        overlapping.delete(key(edge1, edge2));
      }
    }
  }

  return overlapping.values();
}

It’s essentially insertion sort hooked up to track overlaps.

Let’s see it in action:

While it behaves the same and has the same time complexity as the preceding variants, I’m guessing it’s practically much more efficient in terms of processing speed. In video games where every frame has a processing budget, the actual speed matters, not just the scalability. As always, benchmarking will determine the real practical measurement of speed. (Disclaimer: I haven’t done any benchmarks!)

Quick comparisons

n = number of balls, m = number of collisions

(todo: Add benchmark here. I’m a little lazy right now. 😺)

The real measure of speed lies in real measurements on real hardware!

Stop Doing Algorithm Analysis
byu/theawesomenachos inProgrammerHumor

Appendix

Things I’ve noted or realised while writing this post:

• General algorithm design insights
  • Pre-sorting a list can replace a bunch of inequality checks, and unlocks:
    • Some power when linearly scanning over the list
    • Faster range / adjacency checks
    • (unrelated, but good to bring up) Binary search
  • Different sorting algorithms have situational strengths.
• Big O, while useful, can only go so far when analysing performance.
• I might need a frontend framework for my blog now, at least for the interactive demos.
  • Vanilla JS is starting to get scary with bigger demos like these.
  • .mjs is pretty good though.

Bonus demo, 25 balls! It’s a ball party ⚽⚾🏀🏐