Unity Mathf.Atan2 algorithm complexity

Question

using Unity5.5.1f; using C#;

So I have a circle (2D) divided equally by 16 directions, and I also have a direction V which is different from the other 16.

In order to know which direction is the closest I thought of two apporaches:

1. Dot product between V and all the other directions and choose the max one
2. Store atan for all the 16th directions then compute atan for V and see which angle is the closest to V's

My questions are,does anyone know what is the complexity of Mathf.Atan2? Or of an Atan2 algorithm in general? I read it gets worse and worse as the angle becomes bigger, is it true?

Answer 1

It doesn't make a lot of sense to talk about algorithmic complexity (in the big-O sense) for the way we use atan2 in game development. Our inputs are always one fixed size (32 bit floats for the Mathf version), whereas complexity analysis looks at how the algorithm performs as the input gets arbitrarily large (not strictly in magnitude, but in how many bits it takes to write it). So, we could trivially say atan2 is O(1) for our purposes - its execution has a constant upper bound, set by whatever the worst-case pair of floats might be.

So, I'm going to interpret your question instead as "How can I efficiently categorize a Vector2 into one of 16 evenly-spaced directions?"

Empirically testing this in Unity, doing 10000 calls to Mathf.Atan2 takes about 1 millisecond on my laptop's i7, which means on average each call costs something like a tenth of a microsecond. I'd be willing to bet that this is efficient enough for your needs. And it's clear:

Vector2[] directions = // populate this with your 16 directions.
                       // Counter-clockwise from (1, 0)

Vector2 RoundToNearestDirection(Vector2 vector) {
     // Convert the input vector to an angle.
     float angle = Mathf.Atan2(vector.y, vector.x);
     // Round to one of 16 buckets, using modulo to wrap 16 back to 0.
     int index = Mathf.Round((angle * 8 / Mathf.PI) + 16) % 16;
     // Look up the corresponding entry in our direction table.
     return directions[index];
}

If you wanted to, you could replace Atan2 above with an ApproximateAtan2 method you define based on examples like these, though you may find that some vectors very close to the edges of the 16 direction buckets get slightly mis-categorized this way. It probably wouldn't be noticeable in gameplay, but you'll have to make the call whether a few compute cycles is worth adding the extra uncertainty and opportunity for bugs into your codebase.

Compare this against how messy it gets when we try to avoid runtime trigonometry and its approximations:

Vector2 RoundToNearestDirection(Vector2 vector) {

    // If given a near-zero vector, punt and return an arbitrary direction.
    if(Mathf.Approximately(absolutes.sqrMagnitude, 0f))
       return directions[0];

    Vector2 absolutes = new Vector2(Mathf.Abs(vector.x), Mathf.Abs(vector.y));

    int index;

    if(absolutes.x > absolutes.y) {
        int inSegment = IndexInSegment(absolutes.y/absolutes.x) * Mathf.Sign(vector.y);
        if(vector.x > 0) {
            index = (16 + inSegment) % 16;
        } else {
            index = 8 - inSegment;
        }
    } else {
        int inSegment = IndexInSegment(absolutes.x/absolutes.y) * Mathf.Sign(vector.x);
        if(vector.y > 0) {
            index = 4 - inSegment;
        } else {
            index = 12 + inSegment;
        }
    }

    return directions[index];
}

// Use constant tangent ratios that will be pre-computed, so there's no runtime trig.
int IndexInSegment(float a) {
    if(a < Mathf.Tan(Mathf.Deg2Rad * 1f * 180f/16f)
       return 0;

    if(a < Mathf.Tan(Mathf.Deg2Rad * 3f * 180f/16f)
       return 1;

    return 2;
}

This code is not nearly so clear as the code using atan2. The trig let us see every salient operation on 3 lines, and we can verify in our heads that it's working as intended. This though - if I hadn't told you what this function does, would you have guessed? If it contains bugs, would we notice from looking at the code?

My strong suspicion is that this added code complexity, uncertainty, and sheer added surface area for bug accumulation is not going to be worth whatever fraction of a tenth of a microsecond we might hope to shave off of the standard atan2.