Frustum Culling: How to calculate if an angle is between another two angles

Question

I am trying to implement frustum culling but got stuck on how to determine if the angle that the object is from the player is in the FOV of the player. So basically I have the following information:

1. FOV
2. Player's 3D position (x1, y1, z1)
3. Object's 3D position (x2, y2, z2)
4. Player's turning angle with turning left being positive and right negative

How do I determine if the player should be rendered (in the player's field of view) or not?

I tried using this, but it will cull at certain player turn angle and not work in other player turn angle. Ex, work at 0 - 90, but doesn't work at 90 - 180.

    float turn = player.getTurn();
    float FOV = this.FOV;
    if (square(entity.getPosition(), player.getPosition()) < FAR_PLANE / 6) {
        double playerz = player.getPosition().z * -1;
        double playerx = player.getPosition().x;
        double entityz = entity.getPosition().z * -1;
        double entityx = entity.getPosition().x;
        double degrees = Math.toDegrees(Math.atan((playerz - entityz)
                / (playerx - entityx)));
        double sinfz = Math.asin((playerz - entityz)
                / square(player.getPosition(), entity.getPosition()));
        double cosfx = Math.acos((playerx - entityx)
                / square(player.getPosition(), entity.getPosition()));
        /*
         * if(sinfz > 0 && cosfx > 0) degrees = degrees; else
         */
        if ((entityz - playerz) > 0 && (entityx - playerx) < 0)
            degrees = 180 - Math.abs(degrees);
        else if ((entityz - playerz) < 0 && (entityx - playerx) < 0)
            degrees = Math.abs(degrees) + 180;
        else if ((entityz - playerz) < 0 && (entityx - playerx) > 0)
            degrees = 360 - Math.abs(degrees);
        if(betweenAngle(90 + turn - FOV / 2, (float) degrees, 90 + turn + FOV / 2))
            return true;
    }
    return false;

Answer 1

The best way to solve this is not with trigonometry, but with vector math!

I'm going to write some quick pseudocode of what you need to check for difference in angles, if you want the juicy details of the why and how scroll further down.

Summary:

float l1x = entity.getPosition().x - player.getPosition().x;
float l1y = entity.getPosition().y - player.getPosition().y;
float l1z = entity.getPosition().z - player.getPosition().z;
float l1mag = Math.sqrt(l1x*l1x + l1y*l1y + l1z*l1z);
float l2x = Math.sin(turn);
float l2y = 0;
float l2z = Math.cos(turn);
float dot = l1x * l2x + l1y * l2y + l1z * l2z;
float angle = Math.acos( dot / l1mag);
return Math.abs(angle) <= FOV/2;

Copy code at own risk, it was written completely freestyle and I give no guarantees it will actually function straight off the bat.

Explanation:

I'm going to assume you know what a vector is, if not the answer might not make a lot of sense but I'll try to be pedagogical.

Getting the angle of two points is utterly nonsensical, two points are connected with a line, an alone line has no angle, but there is an angle between two lines.

So our first line will be the line through the two points but what will the second line be, we could pick an arbitrary direction but then we'll have to figure out absolute degrees inte relative degrees and as you noticed that's just a mess we want to stay clear of.

Since we're only interested in where the second object is relative to the players FOV it makes much sense for the second line to always be from where the player is to where the player is looking, this way 0° will always be right in front and 180° will always be behind, much simpler to get our heads around wouldn't you say?

Now we come to the tricky part, how do we know where the player is looking? The best would be to have a unit vector denoting direction that gets transformed whenever the player turns, this is something I would highly recommend to implement in the future but for now we'll stick to something relatively more simple using only what you posted.

Assuming 0° means the player is facing +z and he can only turn around the y-axis the equation for figuring out the points position in the world is:

pointX = player.x+sin(player.turn)

pointY = player.y

pointZ = player.z+cos(player.turn)

Notice we didn't multiply the sin or cos with anything, this is because the the point will always be 1 unit in front of the player meaning the line from player to point will always be 1 in length, why 1? Because it's easier to work with.

Now we have two lines, l1 from the player to the object and l2 from the player to where the player is looking, but how do we represent the lines? Should we have three different points? No, we use vectors! Vectors are excellent for representing lines, they contain both direction and magnitude.

So now that we have two separate vectors there is a very simple way to get the angle between them; we use their dot product! The dot product of two vectors is defined as:

$$A \cdot B\sum_{i=1}^n A_i B_i = A_1 B_1 + A_2 B_2 + ... + A_n B_n$$

Which means:

dot = l1.x * l2.x + l1.y * l2.y + l1.z * l2.z

Now you might find yourself asking "What does this have to do with angles?" Well it all comes down to the second definition of the dot product namely:

$$A \cdot B = \Vert A \Vert\Vert B \Vert cos\theta$$

Translated this says that the dot product of two vectors is equal to the product of the two vectors magnitude(length) and the cosine of the angle between them the last part is important because it means that if we know the length of the vectors we can figure out the angle with a simple equation.

We know the length of the vector l2 is 1 and to calculate the length of l1 we take square root of the sum of the squares of its components.

l1.mag = sqrt(l1.x^2 + l1.y^2 + l1.z^2

And the pivotal equation that figures out the angle would then be:

angle = acos(dot / l1.mag)

And then we compare the absolute value of the angle to the FOV/2.

if( abs(angle) <= FOV ) return true