colliding with a loci mesh

Question

I want to avoid my player being able to stand inside walls. Each game tick my player moves some small distance and/or rotates.

TL;DR please provide a variant of the classic line-segment->-triangle intersection algorithm which returns near-misses too, or solve the problem in another way The line segment intersects if it passes within a given distance of the triangle. There's a lot of subtlety to the problem, such as the triangle's locus corners being rounded and if the line segment is tangential to the triangle.

I have the usual ray/triangle intersection code.

However, a ray is a very poor approximation of a moving player! I have problems with the player's center missing edges but the player mesh passing through them.

How do you efficiently determine when and where a player collides with walls and obstacles in a 3D environment?

One general approach would be to have near-miss triangle code, where the ray is a ball-capped cylinder.

The general solution I've tried making is to imagine the player is a sphere; turning this inside-out, I have tried to make a mesh that is radius bigger than the actual walls and do collision rays on that. I want to compute a mesh that is some fixed distance in front of this mesh, i.e. a cube would expand to be a slightly larger cube with rounded edges and corners. (My meshes are rather less regular than a cube. Imagine a mesh representation of the inside of a boiler room, and imagine trying to compute a mesh that is 20 cm from all walls and boilers and door-frames and such in that room.) Here is a simple mesh around a barrel:

For each face I can compute the surface normal; this is how I know which way is 'out'.

My brainstorming makes me imagine multiplying each face's normal by the fixed distance and then emitting a triangle with the corresponding offset.

This would however leave holes at the edges and would perhaps(?) cause some edges to pass through very tight acute corners?

I can also imagine joining each edge as ball-ended cylinders too and so on.

The approach I used for the barrel above is to compute the average normal of all faces sharing a vertex and then multiply that by the collision radius. It doesn't cope with acute angles well, and what to do if a vertex is falsely-shared between faces that are on opposite sides?

I will be computing this mesh, and then performing ray intersections, in Javacsript. So performance is a consideration too. A too fine detailed mesh will be expensive to do collision detection upon.

How can you effectively compute a good-enough loci mesh? Or do loci-aware fuzzy triangle intersection? Or is there a better way to do collision, and can it somehow model that things move in arcs rather than straight lines?

Answer 1

(no-one picked up the bounty :( Nathan Reed on gamedev.stackexchange helped with the terminology. Its called capsule-triangle intersection.)

Its surprisingly tricky maths and googling doesn't find much ready-made code to copy.

A standard way is to extrude the triangle by the radius, add also test each of the three triangle edges as capsules.

To extrude the triangle, you just multiply the triangle's normal by the capsule radius, offset each triangle corner by that amount and then do the normal line-segment triangle test against it.

The capsule test for each triangle edge is rather more expensive as you have to do it three times. Its possible that using the barycentric coordinates from the triangle test will help avoid some of the capsule edge tests but I haven't thought this through. You can also avoid the capsule test on edges that are shared with other triangles that are obtuse enough; you could compute this and mark those edges. I haven't bothered (yet).

I found that pre-computing the bounding sphere of each face and doing an intersection test with the bounding sphere of the capsule was a super-cheap way to avoid this expensive test most of the time. I also pre-compute the normals of each face, although that's a smaller win.

As the test is so expensive, the best thing to do is treat the player as a single sphere and have the intersection code give a list of face intersections. You can then model the player as a series of smaller spheres flying in formation, and you only have to do capsule face intersection code for the faces that the first pass with the bigger sphere found.