Faces a grid of loci

Question

I want my player to not be able to stand inside the walls. Each game tick my player moves a short distance and / or rotates.

TL DR, please provide a version of the classical triangle intersection triangle → triangle, which also returns near misses or solves the problem in another way. . within a given distance from the triangle. There are many subtleties of the problem, for example, the angles of the locus of a triangle are rounded, and if the segment of the line is tangent to the triangle.

I have a regular ray / triangle intersection code.

However, the beam is a very poor approximation of a moving player! I have problems with missing edges in the center of the player, but a grid of players passes through them.

How do you effectively determine when and where a player is faced with walls and obstacles in a 3D environment?

One general approach would be to have a triangle with a gap, where the beam is a cylinder with balls.

The general decision I tried to make was to imagine that the player is a sphere; turning it inside out, I tried to make a grid whose radius is larger than the actual walls, and collisions overlap on it. I want to calculate a grid that is a fixed distance in front of that grid, i.e. The cube will expand to be a slightly larger cube with rounded edges and corners. (My grids are quite rare than the cube. Imagine the grid view inside the boiler room and imagine that you are trying to calculate a grid that is 20 cm from all walls, boilers and door frames, etc. In this room.) Here's a simple net around the trunk:

For each face, I can calculate the surface normal; so I know which way is "out".

My brainstorming makes me imagine that each person multiplied by a normal distance over a fixed distance and then emitted a triangle with a corresponding offset.

Would this, however, leave holes at the edges and possibly (?) Cause some ribs to pass through very dense sharp corners?

I can also imagine how to connect to each rib like ball cylinders, etc.

The approach I used for the trunk above is to calculate the average normal of all the faces dividing the vertex, and then multiply them by the radius of collision. He doesn’t do very well with sharp corners, and what if the top is falsely divided between faces that are on opposite sides?

I will compute this grid and then do ray intersections in Javacsript. Therefore, performance is also considered. Too thin a detailed grid will be expensive for collision detection.

How can you efficiently calculate a sufficient locus grid? Or the intersection of points with a fuzzy triangle? Or is there a better way to make a collision, and can it somehow simulate that things move in arcs rather than straight?

Answer 1

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

Its surprisingly complex math and search engine did not find much ready-made code for copying.

A standard way is to extrude a triangle in radius, add also a test of each of the three edges of the triangle in the form of capsules.

To displace a triangle, you simply multiply the normal triangle by the radius of the capsule, shift each corner of the triangle by this amount, and then perform a regular triangle triangle with it.

A capsule test for each edge of the triangle is quite expensive since you have to do this three times. It is possible that using the barycentric coordinates from the triangle test will help to avoid some cross-capsule tests, but I did not think about that. You can also avoid checking the capsule at the edges that are shared with other triangles that are fairly blunt; you can calculate this and mark these edges. I have not been worried yet.

I found that preliminarily calculating the bounding sphere of each face and performing the intersection test with the bounding sphere of the capsule was a very cheap way to avoid this expensive test most of the time. I also pre-calculate the normals of each face, although a smaller victory.

Since the test is so expensive, it’s best to work with the player as with one sphere and have an intersection code that gives a list of intersections of faces. Then you can model the player as a series of smaller spheres flying in the formation, and you only need to make a capsule face intersection code for persons who have a first pass with a larger sphere found.