Waste of Length in Vector Libraries

I've recently been on a bit of a vector math hook lately which naturally comes with coding up things, testing, toying, and experimenting. Not just vectors, but basically everything commonly used in game development -- boxes, spheres, intersections of shapes, rays, matrices, etc.

I wanted to better understand Sphere-Line collision test, so I made this up a few nights ago.


Click here to go to graph.
There are a few extra unused variables in there. For instance, variable a₁ is the angle between x₃ and x₄ converted to degrees. I don't use it in actually calculating the intersection points, but it was a useful reminder to me that the process of finding the angle between two vectors is almost entirely part of finding the intersection between a sphere and a line. It's literally just missing a call to arccos().

It got me to thinking about how many other vector operations do this sort of thing where two operations will calculate the same thing independent of each other. How many times in our programs do we redundantly calculate something twice?

One thing that immediately stuck out to me was the length of a vector. Programmers should hate Length() ( or Magnitude or whatever you want to call it). Length requires both a call to sqrt() and a division, both of which are (generally) several times more costly than sum and multiply. We even avoid the sqrt() call if we're only comparing two lengths. Ignoring the sqrt call doesn't change the outcome of the comparison, so why do the extra work?

So then I thought, if I already know the length of a vector, why can't I pass that length in to a function that would calculate the length anyway?

Consider the following:

// Lets say this function causes the class it belongs to to look 
// at a vector if the vector is close enough. Kinda contrived, but
// it illustrates the point.
void LookAtNearbyTarget( const Vector3& vec )
{
    const float length = Length(vec);
    if( length < m_FarSight) 
    {
        return;
    }

    // later on in the function...
    const float angle = Angle(vec, Vector3(0.0f, 1.0f, 0.0f) );
    // use the angle for something like creating a rotation matrix
    // by which to turn a game object.
}

Aside from grabbing the length directly, Angle() will also calculate the length of vec and use it. Here's a decent implementation of Angle(). I've changed it to create some temporaries for readability and I'm not worried about inlining or anything. I'm just trying to illustrate.

float Angle(const Vector3& vec1, const Vector3& vec2)
{
    const float length1 = Length(vec1);
    const float length2 = Length(vec2);
    const float dot =  Dot(vec1, vec2);
    return acos( dot / length1 / length2 );
}

Ah! Now, not only are we calculating a length the program already knew, we're also calculating a length the program could have statically knew. After all, we just passed it a statically typed normal vector facing up. Lets see if we can't make this better. And I'll inline the dot value this time.

float Angle(const Vector3& vec1, const float length1, const Vector3& vec2, const float length2)
{
    return acos( Dot(vec1, vec2) / length1 / length2 );
}

Now let's revisit our LookAtNearbyTarget function.

void LookAtNearbyTarget( const Vector3& vec )
{
    const float length = Length(vec);
    if( length < m_FarSight) 
    {
        return;
    }

    // later on in the function...
    const float angle = Angle(vec, length, Vector3(0.0f, 1.0f, 0.0f), 1.0f );
}

Great. Now we're saving some cycles. Of course, there are times when we don't know the two lengths, and we don't want to lose the convenience of a function that will calculate the lengths for us, so lets implement this too.

float Angle(const Vector3& vec1, const Vector3& vec2)
{
    return Angle(vec1, Length(vec1), vec2, Length(vec2) );
}

And if you really wanted to go nuts, you could even add these. Part of me thinks "eh, this is getting silly." but another part of me says "Why not? If nobody uses it, no big deal. If someone does find it useful, then good for them."

float Angle(const Vector3& vec1, const float length1, const Vector3& vec2)
{
    return Angle(vec1, length1, vec2, Length(vec2) );
}

float Angle(const Vector3& vec1, const Vector3& vec2, const float length2)
{
    return Angle(vec1, Length(vec1), vec2, length2 );
}

Personally, I think stuff like this is really important. Why? Because believe it or not, not all programmers are good at vector math. In fact, most programmers I know have admitted they don't like vector math. It is entirely unlikely that someone who doesn't like vector math will write performant vector math code. Heck, I like vector math, but my work project doesn't provide a standard Angle() function, so whenever I needed the angle between two vectors, I would naively something write this:

const float angle = acos( Dot(Normalized(vec1), Normalized(vec2)) );

Why? Because everything I'd read about finding the angle between two vectors has said "to find the angle between two normalized vectors, get the arccosine of the dot product". Without having the time to investigate how I could optimize this (this is game development people, we have deadlines), I took that at face value and went with it. And sure, this gets the job done. And when I'm not in a tight loop or operating over 100's of objects, this is probably okay and not really a performance impact. Still, when I think back about some systems I've written, I've certainly put this in code where I'm operating over lots of vectors.

 But it's not just about performance either. Not every programmer is good at vector math. So when a programmer who has to dabble in vector math for a task says "I need the angle between these two vectors... crap, how do I do that again?" he's now wasting valuable development time googling "Angle Between Two Vectors", reinterpreting someone else's psuedo-code into the particular library he's working on, and then steping through it slowly to verify that it's actually doing what he thinks it is. And if he messed up and gets an unexpected result, he's sitting there wondering whether the answer he got wasn't right. Maybe he should look for a different answer. Debugging and testing your own code becomes laborious.

 Instead, someone who is good at vector math can take the time (a trivial amount for them of course) to implement a few functions that are performant, well tested, and easy to use for other programmers. When provided with the tools to do so, even the most junior of junior programmers can write performant code or at the very least, when time for code review comes, it's very easy to spot places where performance can be improved.

Some Extra Credits
For those interested, using the naive implementation of acos( Dot(Normalized(vec1), Normalized(vec2)) ); also has a few more downsides.

First, Normalized() will be creating a temporary. Two for that matter in this case.

Secondly, Normalized() will divide each element by the length. When instead you divide by the length of each vector after you already have the dot product, you are only dividing twice (once for each vector) instead of six times (once for each element of each vector.