Opinion: Checking For Interval Overlap

[In this reprinted #altdevblogaday-opinion piece, production consultant Keith Fuller examines what an ideal Production certification would entail, and suggests that having at least two tracks for project management and creative leadership would be a good start.] Here's a short post based on an exchange I had recently with a colleague at work (hey Per!). The problem is very simple: We have two (closed) intervals

[a_0,a_1]

[b_0,b_1]

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

I_a=[a_0,a_1]

I_b=[b_0,b_1]

I_b

I_a

I_b

I_a

b_1

a_0

b_1 < a_0

a_1 < b_0

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. [This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]