Simple rayface intersect optimization
I was looking for ways to handle rayface 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 rayface intersection that may speedup your model picking or intersection test.
any implementation of rayface 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 faceray overlap or intersection tests, only the faces with points on both sides of the cutting plane are consider see diagram.
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 rayface overlap specially when dealing with high number of faces like in a mesh.
Here's a simple optimization on rayface intersection that may speedup your model picking or intersection test.
any implementation of rayface 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 faceray overlap or intersection tests, only the faces with points on both sides of the cutting plane are consider see diagram.
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 rayface 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 KDtree, raymesh 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 rayface 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 kdtree 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 kdtree 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 kdtree, but the same idea should work with AABB trees as well.
I'm not sure what u mean by a kdtree, but the same idea should work with AABB trees as well.
http://en.wikipedia.org/wiki/Kdtree
Kdtrees are almost universally accepted as the fastest treemethod [citation needed], and are pretty much the defacto 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.
Kdtrees are almost universally accepted as the fastest treemethod [citation needed], and are pretty much the defacto 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 kdtree it would work even better!
with the kdtree it would work even better!
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
Calculate face direction from bvh or 3d skeleton data  harisz  3  2,983 
May 29, 2013 10:50 AM Last Post: OneSadCookie 

glDrawElements and Face indices  Ashford  8  12,675 
Nov 11, 2009 03:03 PM Last Post: Ashford 

Indexed Face Sets (meshes)  wyrmmage  4  4,133 
Dec 15, 2006 11:18 AM Last Post: wyrmmage 

Face Problems when ZNear down!!!  leodeus  5  4,920 
Oct 31, 2005 12:14 PM Last Post: OneSadCookie 

OpenGL code optimization  unknown  38  13,615 
Jul 28, 2005 10:22 PM Last Post: unknown 