Triangle Line-Segment Intersection - detecting near misses

Question

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?

Answer 1

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.

Answer 2

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.