Wednesday, November 9, 2011

Using Vector Mathematics, Point against axis-aligned box intersection test

In this post we will talk about how to determine if a point is intersecting with an axis-aligned box. Axis-aligned boxes are highly common in games due to being highly efficient, they're often used with culling techniques and other techniques that require spatial partitioning. If you're not familiar with the term "axis-aligned", I recommend reading this, and this. If you're not familiar with the term "spatial partitioning" I recommend reading this.

An axis-aligned box can be fully described using only two points, a min and max point, so all that is needed to see if a point lies inside the box is checking each component of the point to see if it is outside of the min or max range for the box.

For example, lets define a box with a minimum point of (-1, -1, -1) and a maximum point of (1, 1, 1). If we want to check the point (-5, 0, 0.5), we first check the x component, which is -5, and we can see it's less than the minimum x, which is -1, so it cannot be in the box. If we check another point, of (0.5, 1.5, 0), we first check the x component, which is 0.5, and find that it is not less than the minimum x of -1, or greater than the maximum x of +1, so it could lie within the box. We then check the y component, which is 1.5, and find it is not less than the minimum of -1, but it greater than the maximum of +1, so this point cannot be within the box. With a maximum of 6 comparisons we can tell if a point lies within an axis-aligned box, this is why they are so efficient. Checking against a box that isn't axis-aligned, would likely be about 10-20x as expensive. I may cover that kind of intersection test in a later post.

Here's the function to perform a point/axis-aligned box intersection test:
bool Vector3::IsWithinAxisAlignedBox(const Vector3& minPt,
                                     const Vector3& maxPt)
    if ( x < minPt.x )
        return false;

    if ( y < minPt.y )
        return false;

    if ( z < minPt.z )
        return false;

    if ( x > maxPt.x )
        return false;

    if ( y < maxPt.y )
        return false;

    return ( z < maxPt.z );

No comments:

Post a Comment