## 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.

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.
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.
Member
Posts: 157
Joined: 2002.12
Post: #3
I mean face in general does not matter if is a quad or triangle etc.
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.
Member
Posts: 157
Joined: 2002.12
Post: #5
does not matter, even if you triangulate you end up with a face with 3 vertices
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.
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.
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.
Member
Posts: 157
Joined: 2002.12
Post: #9
thanks, now I know
with the kd-tree it would work even better!