Simple ray-face intersect optimization
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]](http://education.med.nyu.edu/~garcij01/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.
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]](http://education.med.nyu.edu/~garcij01/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.
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.
It's not magic, it's Ruby.
I mean face in general does not matter if is a quad or triangle etc.
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.
Oh, you mean face as in polygon in general? Ok, you might be right. But triangulation might be a better option for simple polygons.
It's not magic, it's Ruby.
does not matter, even if you triangulate you end up with a face with 3 vertices
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.
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.
It's not magic, it's Ruby.
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.
I'm not sure what u mean by a kd-tree, but the same idea should work with AABB trees as well.
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.
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.
It's not magic, it's Ruby.
thanks, now I know 
with the kd-tree it would work even better!

with the kd-tree it would work even better!
Possibly Related Threads...
| Thread: | Author | Replies: | Views: | Last Post | |
| glDrawElements and Face indices | Ashford | 8 | 8,010 |
Nov 11, 2009 03:03 PM Last Post: Ashford |
|
| Indexed Face Sets (meshes) | wyrmmage | 4 | 3,137 |
Dec 15, 2006 11:18 AM Last Post: wyrmmage |
|
| Face Problems when Z-Near down!!! | leodeus | 5 | 3,951 |
Oct 31, 2005 12:14 PM Last Post: OneSadCookie |
|
| OpenGL code optimization | unknown | 38 | 11,580 |
Jul 28, 2005 10:22 PM Last Post: unknown |
|
| keep always visible a polygon face...!!! | alert | 5 | 3,880 |
Apr 14, 2005 09:46 AM Last Post: alert |
|

