# Triangle Line-Segment Intersection - detecting near misses

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!

I have made a little test app with classic triangle-intersection code: https://gist.github.com/3751097

The simple test code:

``````# barycentric coords
w = vec3_sub(hit,a)
uu = vec3_dot(u,u)
uv = vec3_dot(u,v)
uw = vec3_dot(u,w)
vv = vec3_dot(v,v)
vw = vec3_dot(v,w)
invDenom = 1.0 / (uu * vv - uv * uv)
U = (vv * uw - uv * vw) * invDenom
V = (uu * vw - uv * uw) * invDenom
W = U+V
# basic in-triangle test
A, B, C = U>=0.0, V>=0.0, W<1.0
if A and B and C:
return GREEN
# near miss?
if U>-0.1 and B and C:
return BLUE
if A and V>-0.1 and C:
return YELLOW
if A and B and W<1.1:
return CYAN
# far miss
return BLACK
``````

generates this:

Clearly the threshold on the barycentric coordinates for a near-miss need scaling somehow by something and multiplying by the `ray_radius`. Also the corners need special casing.

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

-
Scale up the triangle and try again. If it missed the first and hit the second, it was a "near miss". – Byte56 Sep 18 '12 at 16:43
@Byte56 sounds simple, but how exactly do you scale up the triangle and how do you special-case the corners which should be rounded? – Will Sep 18 '12 at 19:33
@Will: scaling should be trivial for an ABC triangle. Just translate the triangle via the -OA vector then scale the translated triangle and then translate it via the OA vector (be sure to keep the OA vector somewhere in a temp variable). This is an approximation and won't cover the case where you want rounded corners (as for an advancing front).. but it should work. – teodron Sep 19 '12 at 8:08