Monday, November 7, 2011

Using Vector Mathematics, utilizing squared lengths

As we've learned in the Optimizing Methods blog post, the most expensive part about doing distance checks is the square-root calculation. There are some cases where we need to do things like compare distances, but we can forego the square-root calculation.

If we want to compare two vectors to see which is longer we can do that without a square-root calculation. We don't need to know the exact length of each vector, we just need to know which is longer, so if we just skip the square-root calculation during the Length() function, when instead end up getting a squared length, which is all we want in this case.

Here's a static/helper method:
float GetSquaredLength( const Vector3& inVect )
{
    return ( inVect.x * inVect.x
           + inVect.y * inVect.y
           + inVect.z * inVect.z );
}

Here's the method you might find in a Vector class:
inline float Vector3::SquaredLength() const
{
    return ( x*x + y*y + z*z );
}

So if we put this two the test, with two vectors, (2, 2, 2) and (2, 2, 3).

The squared length of (2, 2, 2) is ( 2² + 2² + 2² ), or 12.
The squared length of (2, 2, 3) is ( 2² + 2² + 3² ), or 17.

Based on the calculations we know that (2, 2, 2) is the shorter of the two vectors, which may have been obvious, but now we've seen the proof. The actual length of these vectors isn't needed to know which is shorter, but just for some more proof, to find the actual lengths now is very easy because we already have the squared length, so we can now just do the square-root calculation:

The length of (2, 2, 2) is 12, or 3.4641.
The length of (2, 2, 3) is √17, or 4.1231.

In the Optimizing Methods blog post I mentioned that sometimes is isn't the method itself that needs to be optimized, but rather that sometimes you can avoid needing the expensive methods together. Using squared lengths for distance comparisons is just one example of this.

Here's a helper function for returning the longest of two vectors:
Vector3 Vector3::GetLongest(const Vector3& first,
                            const Vector3& second) const
{
    if ( first.SquaredLength() > second.SquaredLength() )
        return first;

    return second;
}

2 comments:

  1. Late, I know; however, this quick article helped me understand the reasoning behind including a .length2() function in a vector class when I assumed .length() (sqrt version) was already enough. Thanks!

    ReplyDelete