Aug 18 2009

The math behind rayintersect (closest point on ray)

when i was i first thinking about writing the the rayIntersect function, my plan was to iterate through the entire mesh, and test all the triangles in mesh object with the rayIntersectTriangle function.
the fundamental problem with this is that to run this test on every traingle in a mesh can become very slow.
so i started thinking of running a simpler less expensive test on the faces, figure out which faces are more likely to intersect and only process those. for this i’m thinking i can figure out what the closest point along the ray is to the center of the face, and test the distance between the closet point and the center of the face.
if the this distance is larger than the diameter of the face then this triangle will be ignored.

fn closestPointOnRay ray pos =
    w = pos - ray.pos
    vsq = dot(ray.dir,ray.dir)
    proj = dot(w,ray.dir)
    return  (ray.pos + (proj/vsq)*ray.dir)

i have not tested this function yet. but it should look something like this.
the next thing I’m going to do is test for the for the distance, but use a cool trick that i found in the book “Essential Mathematics for games and interactive applications”.
the most common way for solving the distance between two points is using the good all Pythagorean theory or (x2 + y2 + z2 = d2).
so in order to find the distance of a point from origin we have get the square root of (x2+y2+z2).
being that the square root is one of the heavier math calculations we can avoid it buy just test for the distance squared.

fn sqrDistance pA pB =
    p = pA - pB
    d = (p.x * p.x)+(p.xy* p.y)+(p.z * p.z)
    return d

so we can the test would look something like

fn faceSimpleTest =
    cp = closestPointOnRay ray.pos faceCenter
    sqD = sqrDistance cp faceCenter
    if sqD < faceDiameter then
        return true

Leave a Reply