Tuesday, November 8, 2011

Using Vector Mathematics (and a bit of trig), Point against cone intersection test

In this post we're going to see how to check if a point lines within a 3D cone. To be clear, it's not exactly a cone, it's like a cone that goes on forever, or if we give a max distance it's like a cone with a round bottom instead of flat.

You might wonder what this kind of intersection test is good for; It's mostly used for things like checking if a point is within an object's field-of-view.

So for checking if a point is within an object's field of view, we need 4 parameters.
We need the position of the object, the direction it is facing, the position of the point we're checking, and the field of view of the object.

We'll pick some convenient values to make things easier to understand.
Object position = (0, 0, 0)
Object facing direction (0, 0, 1)
Point position = (0.5, 0, 1.5)
Field of view = π/3 radians (60 degrees)

We need to get the direction from the object to the point:
Difference vector = (0.5 - 0, 0 - 0, 1.5 - 0) = (0.5, 0, 1.5)

Now that we have the difference, we need to unitize it to get a direction.
length = √( 0.5² + 0² + 1.5² ) = √( 0.25 + 0 + 2.25 ) = √2.5 = 1.5811388
inverse length = 1 / 1.5811388 = 0.63245554
direction = (0.5 * 0.63245554, 0 * 0.63245554, 1.5 * 0.63245554) = (0.31622777, 0, 0.94868331)

Now that we have the direction from the object to the point we get the dot product between that vector and the object's facing direction.

Facing direction (dot) direction to point = (0 * 0.31622777 + 0 * 0 + 1 * 0.9486331) = 0.9486331

Now we need to calculate the cosine of half of the player's field of view. We use half because we want the angle from the center of the cone of FOV, just like dot product is the angle from the center.

half of FOV = π/6
cosine(π/6) = 0.866025

And finally, what determines if the point is in the object's FOV is if the dot product (0.9486331) is greater than or equal to the cosine of half of the FOV (0.866025). In this case it is greater than or equal to the cosine of the FOV, so that point is in the object's FOV.





















And here's the function for doing this type of calculation:
bool IsPointWithinCone(const Vector3& coneTipPosition,
                       const Vector3& coneCenterLine,
                       const Vector3& point,
                       const float FOVRadians)
{
    Vector3 differenceVector = point - coneTipPosition;
    differentVector.Unitize();

    return ( coneCenterLine.Dot(differenceVector) >=
             cos( FOVRadians ) );
}

The above function assumes a cone the continues on forever. If the we assume that our object cannot see for an infinite distance then we can add a distance check.
bool IsPointWithinFiniteCone(const Vector3& coneTipPosition,
                             const Vector3& coneCenterLine,
                             const Vector3& point,
                             const float FOVRadians,
                             const float maxDistance)
{
    Vector3 differenceVector = point - coneTipPosition;

    // Notice that Unitize() is returning a float. The
    // original one we wrote didn't return a float, we'll
    // cover this change in an upcoming blog post
    float length = differentVector.Unitize();

    if ( length > maxDistance )
    {
        return false;
    }

    return ( coneCenterLine.Dot(differenceVector) >=
             cos( FOVRadians );
}

In our original example at the top of the post our point was 1.58 units away, so if we used a finite distance check like the function just above and passed a max distance of 1.5 in, the object would be considered outside of the view.


1 comment: