Triangle Line-Segment Intersection - detecting near misses

Posted by Will on Game Development See other posts from Game Development or by Will
Published on 2012-09-18T16:00:04Z Indexed on 2012/09/18 21:54 UTC
Read the original article Hit count: 517

Filed under:

A ray is a very poor approximation of a player! I think approximating a player with a sphere traveling a straight line each game tick will solve my problems of the player intersecting edges of scenery because their line segment missed it yet their own model is not infinitely thin...

I have a 3D triangle and a line segment. I have the normal triangle-line-segment intersection code which I admit I have only a woolly grasp of.

To model movement and compute collisions of the player I have to determine if a line passes within sphere-radius of a triangle. But I can find no convenient line near-miss intersection code!

Here's the classic triangle intersection ### commented ### code with my starting assumptions:

function triangle_ray_intersection(a,b,c,ray_origin,ray_dir,ray_radius) {
    // http://softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm#intersect_RayTriangle%28%29
    // get triangle edge vectors and plane normal
    var u = vec3_sub(b,a);
    var v = vec3_sub(c,a);
    var n = vec3_cross(u,v);
    if(n[0]==0 && n[1]==0 && n[2]==0) return null; // triangle is degenerate
    var w0 = vec3_sub(ray_origin,a);
    var j = vec3_dot(n,ray_dir);
    if(Math.abs(j) < 0.00000001) {
        //### if parallel, might still pass within ray_radius of it
        return null; // parallel, disjoint or on plane
    }
    var i = -vec3_dot(n,w0);
    // get intersect point of ray with triangle plane
    var k = i / j;
    if(k < 0.0) return null; // ray goes away from triangle
    //### as its a line segment, k > 1+ray_radius means no intersect
    var hit = vec3_add(ray_origin,vec3_scale(ray_dir,k)); // intersect point of ray and plane
    // is I inside T?
    //### here I'm a bit lost; this is presumably computing barycentric coordinates?
    var uu = vec3_dot(u,u);
    var uv = vec3_dot(u,v);
    var vv = vec3_dot(v,v);
    var w = vec3_sub(hit,a);
    var wu = vec3_dot(w,u);
    var wv = vec3_dot(w,v);
    var D = uv * uv - uu * vv;
    var s = (uv * wv - vv * wu) / D;
    //### therefore, compute if its within ray_radius scaled to the 0..1 of barycentric coordinates? 
    if(s<0.0 || s>1.0) return null; // I is outside T
    var t = (uv * wu - uu * wv) / D;
    if(t<0.0 || (s+t)>1.0) return null; // I is outside T
    //### finally, if it passses a barycentric test it might still be too far
    //### to a point; must check that its distance from a corner is within ray_radius too if more than one barycentric coord is >1
    //### so we have rounded corners...
    return [hit,n]; // I is in T
}

Given the distance between the point of plane intersection and each corner, I ought to be able to determine distance at world scale of how far beyond the edge - beyond 1.0 in barycentric coordinates for each axis - that point is... At this point my head explodes! Is this the right track? What's the actual code?

UPDATE: you can earn 100 pts on SO if you answer this question there...!

How can you determine if a line segment passes within some distance of a triangle?

© Game Development or respective owner

Related posts about 3d