2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Usually, the best way to do this is to let the GPU do it for you. Do you have a specific need to detect them in game logic? If so you should elaborate on your usage; it might improve answers. \$\endgroup\$ – Seth Battin Aug 11 '13 at 22:38
  • \$\begingroup\$ I'm deriving an estimate of the visible area of a spherical mesh in lon/lat by counting the quads (two triangles) that intersect with a given camera frustum. It's unorthodox, but the frustum culling in this case is unrelated to controlling rendering complexity. \$\endgroup\$ – Pris Aug 11 '13 at 23:41
  • \$\begingroup\$ Ah, ok. Is that not a question of trigonometry, rather than vertex counting? If you know the distance from the sphere, you ought to be able to calculate the visible fraction of its surface, and then determine how many quads are visible from their size. I will post this as an answer. \$\endgroup\$ – Seth Battin Aug 12 '13 at 1:12
  • \$\begingroup\$ I just saw your edit; I'll try to improve my answer soon. \$\endgroup\$ – Seth Battin Aug 13 '13 at 4:39
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You also have to handle triangles behind the camera, or that are partly in front / partly behind the camera, with this approach. \$\endgroup\$ – Nathan Reed Aug 11 '13 at 21:07
  • \$\begingroup\$ @NathanReed - good point. \$\endgroup\$ – ChrisF Aug 11 '13 at 21:09
2
\$\begingroup\$

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.

sphere visible angle

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I actually have the opposite setup with respect to triangle size. The triangles are huge with respect to the view frustum and I'd expect to run into the case where none of the triangle vertices are inside the frustum, but still intersects it. I'll take a look at the SAT \$\endgroup\$ – Pris Aug 11 '13 at 23:39
  • \$\begingroup\$ @Pris In that case, another fast test is to find the corners of the frustum and test if they're all on the same side of the triangle's plane. That might be effective depending on the relative sizes. \$\endgroup\$ – Nathan Reed Aug 11 '13 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.