Simple ray-face intersect optimization

Member
Posts: 157
Joined: 2002.12
Post: #1
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.
Quote this message in a reply
Member
Posts: 567
Joined: 2004.07
Post: #2
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.
Quote this message in a reply
Member
Posts: 157
Joined: 2002.12
Post: #3
I mean face in general does not matter if is a quad or triangle etc.
Quote this message in a reply
Member
Posts: 567
Joined: 2004.07
Post: #4
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.

It's not magic, it's Ruby.
Quote this message in a reply
Member
Posts: 157
Joined: 2002.12
Post: #5
does not matter, even if you triangulate you end up with a face with 3 vertices Smile
Quote this message in a reply
Member
Posts: 567
Joined: 2004.07
Post: #6
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.

It's not magic, it's Ruby.
Quote this message in a reply
Member
Posts: 157
Joined: 2002.12
Post: #7
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.
Quote this message in a reply
Member
Posts: 567
Joined: 2004.07
Post: #8
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.

It's not magic, it's Ruby.
Quote this message in a reply
Member
Posts: 157
Joined: 2002.12
Post: #9
thanks, now I know Smile
with the kd-tree it would work even better!
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Calculate face direction from bvh or 3d skeleton data harisz 3 3,167 May 29, 2013 10:50 AM
Last Post: OneSadCookie
  glDrawElements and Face indices Ashford 8 13,237 Nov 11, 2009 03:03 PM
Last Post: Ashford
  Indexed Face Sets (meshes) wyrmmage 4 4,220 Dec 15, 2006 11:18 AM
Last Post: wyrmmage
  Face Problems when Z-Near down!!! leodeus 5 5,020 Oct 31, 2005 12:14 PM
Last Post: OneSadCookie
  OpenGL code optimization unknown 38 13,996 Jul 28, 2005 10:22 PM
Last Post: unknown