🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Back to Math and Physics

Frustum intersection testing

binder2 · 2019-11-30T13:05:40

I want to be able to determine if OBBs or Triangles intersect a Frustum. Specifically, in my case, it is for selection. So I need the result to be accurate, as opposed to some rough frustum culling approximation. I've done a bit of research, and a lot of the algorithms I have found simply test to see if all the points of the geometry are on one side of any frustum plane, if so, they assume it is outside of the frustum, else it is inside (or intersects). But this doesn't seem to really work, as you can quite easily have points that are all outside the frustum, but are not all on any one side of a frustum plane. I have seen other techniques where they do the above test first, and then they flip the test around and use the OBB planes to then test the frustum points. I assume this will also work with the triangle case? and that I just test the plane of the triangle with the normal being rendered (if back face culling is enabled) Or should I do these calculations in 2D space? so transform the points by the ViewProj matrix, and use SAT (something I am not familiar wih yet) to test for intersection of the OBB points in NDC space and the triangle points in NDC space?

Math and Physics Programming

Started by binder2 November 29, 2019 10:50 AM

14 comments, last by JohnnyCode 4 years, 7 months ago

binder2

Author

November 30, 2019 12:10 PM

Green_Baron said:
This approach does not test against planes but coordinates (first near/far, then x/y). Would it solve the problem of false positives ?
http://www.lighthouse3d.com/tutorials/view-frustum-culling/radar-approach-testing-points/

This only tests points though, if you think about a triangle, all points could be outside the frustum, but the segments still interesting the frustum, so the triangle would incorrectly be marked as not visible.

Beosar said:
Green_Baron said:
This approach does not test against planes but coordinates (first near/far, then x/y). Would it solve the problem of false positives ?
http://www.lighthouse3d.com/tutorials/view-frustum-culling/radar-approach-testing-points/
The link doesn't work for me:
You don't have permission to access this resource.Server unable to read htaccess file, denying access to be safe Additionally, a 403 Forbidden error was encountered while trying to use an ErrorDocument to handle the request.
I don't think testing points instead of planes helps. I don't see what's wrong with the original approach, it should work.
Alternatively, just render the scene to a 32 bit uint render target and give each element a unique index and then just read the texture. This way you won't select things that are behind another thing.

I need to select eveything that interesects the frustum, like a marquee selection

binder2

Author

November 30, 2019 12:12 PM

binder2

Author

November 30, 2019 12:13 PM

Green_Baron

221

November 30, 2019 12:48 PM

It was just to show how the test work, there are algorithms for spheres and aabbs as well. I haven't found a triangle though, but triangles can be left to the pipeline to do it automagically.

Will this help ?

http://jcgt.org/published/0002/01/05/paper.pdf

JohnnyCode

1,084

November 30, 2019 01:05 PM

Sorry, I confused OBB as AABS/OBS. I would advise you with that geometry primitive as better for texting against soon rejection, it will give a bit more positiives though, but never give a negative.