Efficient collision detection of sphere with wall

Question

I'm building a first-person game where up till now the player has been represented as a dimensionless point; this makes collision detection really easy, as I can just cast a ray along their velocity vector, find the distance to the nearest obstacle, and clamp the magnitude of the displacement vector to that maximum distance on every frame.

Unfortunately, though, this runs into occasional glitches where a player can jump through a corner between two walls, especially if there isn't anything on the other side to collide with--if the player is facing exactly into the intersection, then the projected ray passes right through the corner without registering a hit on either adjacent wall.

To fix this, I want to instead model the player as a finite-sized sphere, which cannot fit through floating-point-error-sized gaps. (This will also have the nice side effect of forcing a minimum standoff distance for the camera from the walls, so you can't stick your eyeball right up against the surface and fill the screen with a single texel.)

Now, checking whether or not that sphere currently intersects a wall is easy. However, I find myself stuck on how to check whether the sphere will intersect a wall if translated in a certain direction--and if so, where.

All of my walls are axis-aligned, which I expect should simplify things.

Any tips?

Answer 1

I am assuming you have a sphere of radius r between two timeframes, at position $$x(t), \,\,t \in \left[0, 1\right]dt$$ and want to know whether there exists a time t such that the sphere is touching the wall. A wall is a plane, in general. So it can be defined using a position vector and the normal versor $$ x_p,\,\,\widehat{n} $$ See figure. We assume that the sphere is moving at a constant velocity during the two frames x(0) and x(1), that is $$ x(t) = x(0) + t \,dx, \,\,\,\text{with}\,\,dx = \left( x(1) - x(0) \right) $$

The conditions for collision are

• The two objects are overlapping geometrically at some time t $$ \left(x(t) - x_p\right) \cdot \widehat{n} < r $$
• The sphere is approaching the wall (velocity is towards the wall). $$ dx \cdot \widehat{n} < 0 $$

The last equation is easy to check. The former one has to be solved for t, using the linear motion assumed above. The solution is $$ t = \frac{ r \,\,–\,\, x(0) \cdot \widehat{n} + x_p \cdot \widehat{n} }{dx \cdot \widehat{n} } \;\;\; \& \;\;\; t \in [0, 1]dt $$ remember to check whether your t occurs within the timeframe, \$ t \in [0, 1]dt \$. From t calculated here you can get the exact position x(t) where the sphere starts touching the wall.

I hope there are no mistakes in the computation. Let me know if it works.

Answer 2

There are 2 ways of handling this

The first and the most primitive way is to substep the collision checks: for example if your player is about to move N meters for the current tick: and your sphere radius is M... you could subsequently move your player by amount of (for example) M/2 up until it reaches the N or hits a wall - this is easy to implement - and works fast enough, I am using it for the Collision Detection Avoidance in my game it handles hundreds of collisions like that without any CPU performance hit.

The second solution is to implement a sweep function - where you will sweep the sphere from start to end point - or up until the collision. This requires a bit more sophisticated mathematics.

This article may help you to get started: https://www.gamedev.net/forums/topic/526931-how-do-you-do-swept-sphere-vs-line-segment-intersection-tests/

In case you wonder here is the implementation of the first way with 200 moving agents - please note the Game Time (which is the actual CPU time) the overall FPS is low because my GPU cant handle that much animated skeletal meshes https://drive.google.com/file/d/17vYRyQxUtEN3QkUyx1nx9sx4oWsx_B0s/view?usp=drivesdk