How do I determine if a triangle is visible in my view frustum?

Question

I need a fast way to determine if a triangle is visible from a perspective projection view frustum. I am not looking to use an approximation with AABBs or bounding spheres, but need to accurately check an actual triangle against the frustum.

What do I need to do to test whether or not a triangle is completely outside the view frustum volume?

---

Edit: The nature of my question changed after discussing the actual problem I was trying to solve. I'm not too sure what to do here; do I accept answers based on the original question, or ones that address the actual problem? I'm also writing the original problem here for reference:

I'm trying to put together a 3d scene where I can get the visible longitude and latitude extents given an Earth sphere (centered at 0,0,0 in ECEF coordinates) and a normal perspective projection camera frustum. I then plan to load assets based on the lon/lat extents returned.

I couldn't figure out how to get extents given a view frustum analytically, so I tried to create a mesh based representation of the Earth at various LODs. I wanted to cull the triangles from this mesh against the view frustum which would leave a bunch of quads I could derive lon/lat extents from. Culling using vertices or bounding boxes wasn't appropriate at lower LODs where the mesh faces were much larger, which is why I needed to test the triangles themselves.

Seth's answer below seems like a better solution than generating meshes and culling them.

Answer 1

Get the projection of the triangle and the view frustrum. You then have a 2D box and a triangle.

If the X ordinate of all of the points are less than the minimum X value of the box or is greater than the maximum X value then it's totally outside the box.

If the X value is inbetween these values then repeat the test but with the Y values.

As Nathan points out this isn't the whole solution but will enable you to throw away a large number of triangles in one go. You can couple this with other tests to determine whether the triangles are behind the camera to throw away even more.

Answer 2

Continuing from comments: if you are trying to estimate the visible area of a sphere, you don't need to detect individual triangles at all. You should be able to reduce that to a fixed mathematical process. Doing this should reduce the O complexity of your operation to constant time. The math itself will involve several steps, possibly with branching logic. But unless you have a very small number of vertices, it will be faster than counting triangles.

The goal is to determine the red angle. In any position, this can be calculated from the sphere's position and the frustum's orientation. Once you've done that, you can divide by the angle size of the quad. (Or skip that step, since you said the goal is to determine the angle.) Obviously this is a 2D diagram, so you may need to repeat the process for the frustum's up-down and left-right directions.

I haven't posted anything specific because the process will vary depending on your situation. Is the sphere filling the whole frustum, or is it partially filling it like I show in my sketch? Is the sphere so large that you are seeing only a small portion of it, or is it just barely filling the viewable area? Referencing that sketch, the green triangle's viewable edge is calculated differently than the purple triangle's edge. Regardless, placing the sphere into one of a few different "zones" will still yield the visible area faster than bounds-testing individual vertices.

Answer 3

If you really need an exact test, you can use SAT (separating axis test). Google it; there's tons of resources on the web. But it's not all that fast.

If you just need to quickly reject most out-of-frame triangles (a conservative intersection test), and the triangles are reasonably small compared to the frustum, then just loop through the frustum's planes and check if all three triangle vertices are on the outside of the plane. This will get rid of most of the triangles, though it will fail to reject some triangles that are outside the frustum near its edges/corners. Most importantly, it won't reject any triangles that are actually visible.