iDevGames Forums
Simple ray-face intersect optimization - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Graphics & Audio Programming (/forum-9.html)
+--- Thread: Simple ray-face intersect optimization (/thread-3086.html)



Simple ray-face intersect optimization - NYGhost - Aug 17, 2007 10:35 AM

I was looking for ways to handle ray-face intersections on the web, everyone talks about using a ray to do the test, but none suggested using a plane instead.

Here's a simple optimization on ray-face intersection that may speedup your model picking or intersection test.

any implementation of ray-face intersect would have to determine if the intersection point with a face is within the face bounds.
By using a plane instead of a ray you can cut down the number of face-ray overlap or intersection tests, only the faces with points on both sides of the cutting plane are consider see diagram.

[Image: ri_simple_optimize.png]

I have not tested how fast it could be using the plane versus the ray, but I bet the dot products should be faster than getting the intersection points, or testing for ray-face overlap specially when dealing with high number of faces like in a mesh.


Simple ray-face intersect optimization - Duane - Aug 17, 2007 10:39 AM

when you say 'face', you mean...? Triangles are almost as fast as spheres, and polygons can be triangulated. Together with a KD-tree, ray-mesh intersections get VERY fast.


Simple ray-face intersect optimization - NYGhost - Aug 17, 2007 10:44 AM

I mean face in general does not matter if is a quad or triangle etc.


Simple ray-face intersect optimization - Duane - Aug 17, 2007 11:11 AM

Of course it matters! you can optimize for triangle/quads!

Oh, you mean face as in polygon in general? Ok, you might be right. But triangulation might be a better option for simple polygons.


Simple ray-face intersect optimization - NYGhost - Aug 17, 2007 11:17 AM

does not matter, even if you triangulate you end up with a face with 3 vertices Smile


Simple ray-face intersect optimization - Duane - Aug 17, 2007 11:24 AM

Oh, I understand; you aren't optimizing the ray-face intersection per se, you're optimizing how to find the face itself.

I'm not so sure this will make it all that much faster; I think a kd-tree would be better suited for the task. Instead of checking all those faces for plane intersection, you just check the tree to see if the ray intersects with the box that contains the face.


Simple ray-face intersect optimization - NYGhost - Aug 17, 2007 11:33 AM

that's correct all it does is discard faces that have no chance to intersect with the ray.

I'm not sure what u mean by a kd-tree, but the same idea should work with AABB trees as well.


Simple ray-face intersect optimization - Duane - Aug 17, 2007 11:42 AM

http://en.wikipedia.org/wiki/Kd-tree

Kd-trees are almost universally accepted as the fastest tree-method [citation needed], and are pretty much the de-facto standard in raytracers. I don't really have much experience with them out of raytracing, so I can't say (for sure) that it's the same way in games. However, I'm pretty certain.

But, this will probably do quite well too.


Simple ray-face intersect optimization - NYGhost - Aug 17, 2007 12:01 PM

thanks, now I know Smile
with the kd-tree it would work even better!