# Triangle Line-Segment Intersection - detecting near misses

Filed under:
##### 3d

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

• #### How to convert videos to 3D format so that I can watch them with 3D glasses

as seen on Super User - Search for 'Super User'
Are there any softwares to convert 2D videos to 3D (preferably XviD avi) so that I can watch them with 3D glasses? No matter if it's freeware or shareware. >>> More

• #### In Email, Image (img) Source (src) Tags are rewritten as relative links. How to fix?

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm working on sending out an html based email, and every time it sends the image src tags and some of the anchor href tags are modified to be relative url's. Update 2: This is happening between when the body of the email is generated and sent and when it arrives in my inbox. Update: I am using… >>> More

• #### WPF 3D - Need help writing conversion methods between 2D and 3D (Point3DToPoint and PointAndZToPoint

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm new to WPF 3D, so I may just be missing something obvious, but how do I convert from 3D to 2D and (for a given z location) from 2D to 3D? Specifically, I need two conversion methods: Point3DToPoint - If I have an (x, y, z) coordinate in the 3D world, how do I determine the (x, y) coordinate… >>> More

• #### 3D point on 3D mesh surface

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi All, How can I get a 3D point on 3D mesh surface made up triangulars ? The 3D point may be anywhere on the 3D surface. Thanks. M.Ken >>> More

• #### Matlab 3d volume visualization and 3d overlay

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, so the question ist pretty much the title. I have a 3d volume loaded as raw data [256, 256, 256] = size(A). It contains only values of zero's and ones, where the 1's represent the structure and 0's the "air". I want to visualize the structure in matlab and then run an algorithm on it and put… >>> More