Triangle Line-Segment Intersection - detecting near misses
- by Will
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?
