Friday, December 16, 2016

Fast Branchless Integral Axis-Aligned Bounding Box Intersection Test

If you're like me you have a hard time finding basic things on the Internet.  Maybe these concepts aren't all that basic then, I haven't really considered that.  If you're also like me you want to see the code, not endless walls of text, so without further ado, here is the fast code to detect if two integral 3-dimensional axis-aligned bounding boxes intersect without branching assuming a twos-complement architecture:

    boolean intersects(IntAxisAlignedBox left, IntAxisAlignedBox right) {
        return
            (
                lineDeltaFactor(left.min.x, left.max.x, right.min.x, right.max.x) |
                lineDeltaFactor(left.min.y, left.max.y, right.min.y, right.max.y) |
                lineDeltaFactor(left.min.z, left.max.z, right.min.z, right.max.z)
            ) == 0;
    }

    int lineDeltaFactor(int leftMin, int leftMax, int rightMin, int rightMax) {
        final int
                leftWidth = leftMax - leftMin,
                rightWidth = rightMax - rightMin,

                leftMid = leftMin + ((leftMax - leftMin) >> 1),
                rightMid = rightMin + ((rightMax - rightMin) >> 1);

        return (abs(leftMid - rightMid) << 1) / (leftWidth + rightWidth + 1);
    }

    int abs(int value) {
        final int mask = value >> (Integer.SIZE - 1);

        value ^= mask;
        value += mask & 1;
        return value;
    }

Now, if you have a smart compiler / LLVM, it will inline expand these functions to avoid expensive stack juggling and v-table lookups. Note that this example also includes a branchless version of the absolute value function.  Now if your architecture isn't twos-complement, then this isn't going to work because abs will return garbage. This will fail for input values that are close to 32-bit extremes (i.e. Integer.MAX_VALUE and Integer.MIN_VALUE).