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

2 Answers

It sounds like what you really want to do is intersect the triangle with a volume representing the space the player swept out during the last timestep. If the player is represented by a sphere, this volume is a capsule (cylinder capped with spheres on the ends); if the player is an axis-aligned bounding box then the volume is a convex polyhedron; etc.

There are references to numerous intersection tests for all sorts of geometry at this page. You probably want to scroll down to the Dynamic section and look at the links for "Moving Sphere/Triangle". Their recommendation is to build an "inflated" triangle consisting of three spheres for the vertices, three cylinders for the edges, and a slab (convex polyhedron) for the interior; then do a raycast against their union (i.e. raycast against each of these shapes, return true if at least one of them hit). There is a link to some sample code.

Incidentally, this kind of shape is known as a Minkowski sum. Here's it's the sum of the triangle and the player-sphere. In general it's one shape "inflated" by another shape. This is a term you'll see often if you delve into the collision detection literature.

-
so often held up by a lack of knowing the terminology! thank you. – Will Sep 20 '12 at 7:27

You can check against the individual triangle edges (segments) using an algorithm that provides you with the distance between two line segments.. it's probably not fast, but it works.. If you google for this algorithm, there are various (pseudocode) implementations to help you get started with your own. See here.

-