Before I start, a small apology is in order: A few weeks ago, I posted the first part of my “A Trip through the Graphics Pipeline 2011″ series – and nothing since. Don’t worry, it’s still coming up. But the goal for me was to turn in properly edited versions of my original blog posts, and the original series has a few structural problems because it was written installment by installment. Rather than risking the same thing again, I decided to wait until I have finished the series (which will be soon), then edit the whole thing in one piece and clean it up. So it’s gonna take a bit longer until parts 2 and following of the series show up, but I don’t want to make the same mistake twice. :)

Anyway, for the meantime, here’s a short post based on an exchange I had recently with a colleague at work (hey Per!). It’s about a few tricks for checking interval overlaps that aren’t as well-known as they should be.

The problem is very simple: We have two (closed) intervals [b_0,b_1] and want to find out if they overlap (i.e. have a non-empty intersection). So how would you do it? A simple solution can be obtained directly from the definition: we first compute the intersection of the two intervals, then check whether it’s non-empty.

The code for this is straightforward, and I’ve seen it many times in various codebases:

 
  i0 = max(a0, b0); // lower bound of intersection interval
 
  i1 = min(a1, b1); // upper bound of intersection interval
 
  return i0 <= i1;  // interval non-empty?

However, doing the check this way without a native “max” operation (which most architectures don’t provide for at least some types) requires three comparisons, and sometimes some branching (if the architecture also lacks conditional moves). It’s not a tragedy, but neither is it particularly pretty.

Center and Extent

If you’re dealing with floating-point numbers, one reasonably well-known technique is using center and extents (actually half-extents) for overlap checks; this is the standard technique to check for collisions using Separating Axis Tests, for example. For closed and open intervals, the intuition here is that they can be viewed as 1D balls; instead of describing them by two points on their diameter, you can equivalently express them using their center and radius. It boils down to this:

 
  float center0 = 0.5f * (a0 + a1);
 
  float center1 = 0.5f * (b0 + b1);
 
  float radius0 = 0.5f * (a1 - a0);
 
  float radius1 = 0.5f * (b1 - b0);
 
  return fabsf(center1 - center0) <= (radius0 + radius1);

This looks like a giant step back. Lots of extra computation! However, if you’re storing (open or closed) intervals, you might as well use the Center-Extent form in the first place, in which case all but the last line go away: a bit of math and just one floating-point compare, which is attractive when FP compares are expensive (as they often are). However, this mechanism doesn’t look like it’s easy to extend to non-floats; what about the multiply by 0.5? The trick here is to realize that all of the expressions involved are linear, so we might as well get rid of the scale by 0.5 altogether:

 
  center0_x2 = a0 + a1;
 
  center1_x2 = b0 + b1;
 
  radius0_x2 = a1 - a0;
 
  radius1_x2 = b1 - b0;
 
  return abs(center1_x2 - center0_x2) <= (radius0_x2 + radius1_x2);

No scaling anymore, so this method can be applied to integer types as well as floating-point ones, provided there’s no overflow. In case you’re wondering, there’s efficient branch-less ways to implement abs() for both floats and integers, so there’s no hidden branches here. Of course you can also use a branch-less min/max on the original code snippet, but the end result here will be a bit nicer than that. Because eliminating common terms yields:

 
  t0 = b1 - a0;
 
  t1 = a1 - b0;
 
  return abs(t0 - t1) <= (t0 + t1);

I thought this was quite pretty when I stumbled upon it for the first time. It only does one comparison, so it’s optimal in that sense, but it still involves a bit of arithmetic.

Rephrasing the question

The key to a better approach is inverting the sense of the question: instead of asking whether two intervals overlap, try to find out when they don’t. Now, intervals don’t have holes. So if two intervals a_1 < b_0. Applying that to our original problem (which involves negating the whole expression using de Morgan's laws), this gives the following version of the interval overlap check:

 
  return a0 <= b1 && b0 <= a1;

Which is about as simple as it gets.

Again, it’s not earth-shattering, but it’s not at all obvious from the original snippet above that the test can be done this way, so the longer version tends to come up quite often – even when the max and min operations use branches. It’s generally worthwhile to know all three forms so you can use them when appropriate – hence this post.