Ray Frustum intersection

Quote:

Original post by Dragon_Strike u just have to test 3 planes at the most... u can determine which planes to test against using the rays direction vector...

Quote:

Original post by Dragon_Strike u just have to test 3 planes at the most... u can determine which planes to test against using the rays direction vector... when u have the right planes u test if there is an intersection... if there is an intersection u check if the intersection falls within the face of the plane...

Ray3 tmp = ray;tmp.m_dir.normalize();float dist;for (int i = 0; i < 6; ++i)	if (tmp.intersect(m_planes, dist))	{		if (dist > 0.0f) tmp.m_org += tmp.m_dir * dist;		else			 return intersect_out;	}	else return intersect_out;return intersect_in;

Quote:

Original post by B_old Hi, I would like to know whether a ray intersects a frustum. I know how to find a ray-plane intersection. But I can't simply test all 6 planes of the frustum, can I? I believe that would give me too many intersections where there actually are none.

Quote:

Original post by jyk If you only need to know if the ray intersects the frustum (not where), you could use the separating axis theorem, which I think would almost certainly be faster than performing multiple ray vs. quad intersections.

Quote:

Original post by Christer Ericson ...the separating axis test (not theorem)...

Quote:

Instead the best approach is probably to treat the frustum as the intersection volume of 6 halfspaces and compute t_enter and t_exit for the six planes and see if t_enter < t_exit in which case there is an intersection (and otherwise not). This is just 6 ray-vs-plane tests, which can be performed together using SIMD for additional speed.

Quote:

Original post by jyk Quote: Original post by Christer Ericson ...the separating axis test (not theorem)... Hm. A quick Google search for the phrase 'use the separating axis theorem' seems to indicate that its use in this context is not uncommon (the search returns, among other things, some scholarly papers and some online posts by professional developers). I take it you consider this usage to be strictly incorrect?

Quote:

Quote: Instead the best approach is probably to treat the frustum as the intersection volume of 6 halfspaces and compute t_enter and t_exit for the six planes and see if t_enter < t_exit in which case there is an intersection (and otherwise not). This is just 6 ray-vs-plane tests, which can be performed together using SIMD for additional speed. My thought was that the SAT might be faster for this purpose due to the lack of divisions and the efficiency of the plane tests (which, depending on the nature of the input data, could very well cull many if not most rays without any need for the six cross-product tests).

Quote:

Original post by Christer Ericson I'm of the opinion that there is no such thing as a "separating-axis theorem." A lot of papers talk about the "separating-axis theorem [X]" where X is a reference to (typically) the OBBTree paper by Gottschalk, Lin, and Manocha, but that paper doesn't ever talk about any separating-axis theorem! Indeed, I can't even locate a paper that attempts to formally state a separating-axis theorem! (There was a tech report by Gottschalk by that name but it was never published/completed. I do have an early draft of it.) Furthermore, obviously one could easily state (and prove) a "separating-axis theorem" if one wanted, but I find this silly as such a theorem trivially follows from the "separating hyperplane theorem" which is a KNOWN theorem that's _actually_ proved, used, and referred to in the theory of convex sets. See e.g. section 2.5.1 of Boyd and Vandenberghe's Convex Optimization. Downloadable from here: http://www.stanford.edu/~boyd/cvxbook/ I.e. my objection is that talking about the "separating-axis theorem" is a bit like, err, referring to addition as the "addition theorem." The reason you see references to people using the term "separating-axis theorem" is because they've seen other people use it. Somewhat annoyingly the term "separating-axis theorem" now even shows up on Wikipedia with its own entry http://en.wikipedia.org/wiki/Separating_axis_theorem but again without any references to an actual theorem being proved anywhere, I might point out.