41 ms·

In the context of a game engine, when you have fast moving objects, and your collision detection only runs a few times each second, how do you detect if objects

In the context of a game engine, when you have fast moving objects, and your collision detection only runs a few times each second, how do you detect if objects should have collided, if the fast moving object fully passes through another, between each tick?

Arch485 5y ago
This is actually a fairly common problem in game development! There are two largely used solutions: 1. Don't have fast moving objects 2. Use "continuous" collision detection. Option 2 is more interesting. Continuous collision detection is, in essence, "looking ahead" at where an object is going and seeing if there are any potential collisions (typically using a bounding box or simplified geometry to save on CPU power). If there are no potential collisions, all is well, and if there is a potential collision we can then calculate its outcome.
rossnordby 5y ago
The usual approach is some form of sweep to get a time of impact. Once you've got a time of impact, you can either generate contacts, or avoid integrating the involved bodies beyond the time of impact, or do something fancier like adaptively stepping the simulation to ensure no lost time. If the details don't matter much, it's common to use a simple ray cast from the center at t0 to the center at t1. Works reasonably well for fast moving objects that are at least kinda-sorta rotationally invariant. For two dynamic bodies flying at each other, you can test this "movement ray" of body A against the geometry of body B, and the movement ray of body B against the geometry of body A. One step up would be to use sphere sweeps. Sphere sweeps tend to be pretty fast; they're often only slightly more complicated than a ray test. Pick a sphere radius such that it mostly fills up the shape and then do the same thing as in the previous ray case. If you need more detail, you can use a linear sweep. A linear sweep ignores angular velocity but uses the full shape for testing. Notably, you can use a variant of GJK (or MPR, for that matter) for this: http://dtecta.com/papers/jgt04raycast.pdf http://dtecta.com/papers/jgt04raycast.pdf If you want to include angular motion, things get trickier. One pretty brute forceish approach is to use conservative advancement based on distance queries. Based on the velocity and shape properties, you can estimate the maximum approaching velocity between two bodies, query the distance between the bodies (using algorithms like GJK or whatever else), and then step forward in time by distance / maximumApproachingVelocity. With appropriately conservative velocity estimates, this guarantees the body will never miss a collision, but it can also cause very high iteration counts in corner cases. You can move a lot faster if you allow the search to look forward a bit beyond potential impact times, turning it into more of a root finding operation. Something like this: https://box2d.org/files/ErinCatto_ContinuousCollision_GDC2013.pdf https://box2d.org/files/ErinCatto_ContinuousCollision_GDC201... I use a combination of speculative contacts and then linear+angular sweeps where needed to avoid ghost collisions. Speculative contacts can handle many forms of high velocity use cases without sweeps- contact generation just has to be able to output reasonable negative depth (separated) contacts. The solver handles the rest. The sweeps use a sorta-kinda rootfinder like the Erin Catto presentation above, backed up by vectorized sampling of distance. A bit more here, though it's mainly written for users of the library: https://github.com/bepu/bepuphysics2/blob/master/Documentation/ContinuousCollisionDetection.md https://github.com/bepu/bepuphysics2/blob/master/Documentati...
syntheweave 5y ago
As the other comments note, you can create a sweep form to detect penetration. But this belies the more thorny issues of achieving a "high quality" solution: if two things impact a third within the exact same time step, you have to come up with a globally satisfying solution that coordinates all three, and sweeping doesn't do that by itself, it just says "well at some time it might hit one or both of them" - which if you run with directly, leads to weird behaviors related to the information loss where objects squeeze past each other or gain excess energy or trigger events they shouldn't. The solution to that problem is generally handled through the solver by various iterative methods. In a 2D platforming game using AABBs this is as simple as "step the physics on Y axis, then step them on X axis" - which completely eliminates the possibility of hitting two things at once, albeit it makes corners "sticky" on one axis. Once you have things rotating and colliding at any angle it gets a lot harder and the focus then is on how to iterate approximately in a way that produces the least error. (If you can afford it, backtracking the solver to optimize the solution quality to some metric of fewest/smallest impacts is one way to create satisfying interactions).
TheAceOfHearts 5y ago
One option is to not worry about it so speedrunners can have a bit of extra fun breaking the game. It's a feature, not a bug!
tlarkworthy 5y ago
In games the fastest moving object is bullets, so model them as lines, not points.

Arch485 5y ago

This is actually a fairly common problem in game development! There are two largely used solutions: 1. Don't have fast moving objects 2. Use "continuous" collision detection. Option 2 is more interesting. Continuous collision detection is, in essence, "looking ahead" at where an object is going and seeing if there are any potential collisions (typically using a bounding box or simplified geometry to save on CPU power). If there are no potential collisions, all is well, and if there is a potential collision we can then calculate its outcome.

rossnordby 5y ago

The usual approach is some form of sweep to get a time of impact. Once you've got a time of impact, you can either generate contacts, or avoid integrating the involved bodies beyond the time of impact, or do something fancier like adaptively stepping the simulation to ensure no lost time. If the details don't matter much, it's common to use a simple ray cast from the center at t0 to the center at t1. Works reasonably well for fast moving objects that are at least kinda-sorta rotationally invariant. For two dynamic bodies flying at each other, you can test this "movement ray" of body A against the geometry of body B, and the movement ray of body B against the geometry of body A. One step up would be to use sphere sweeps. Sphere sweeps tend to be pretty fast; they're often only slightly more complicated than a ray test. Pick a sphere radius such that it mostly fills up the shape and then do the same thing as in the previous ray case. If you need more detail, you can use a linear sweep. A linear sweep ignores angular velocity but uses the full shape for testing. Notably, you can use a variant of GJK (or MPR, for that matter) for this: http://dtecta.com/papers/jgt04raycast.pdf http://dtecta.com/papers/jgt04raycast.pdf If you want to include angular motion, things get trickier. One pretty brute forceish approach is to use conservative advancement based on distance queries. Based on the velocity and shape properties, you can estimate the maximum approaching velocity between two bodies, query the distance between the bodies (using algorithms like GJK or whatever else), and then step forward in time by distance / maximumApproachingVelocity. With appropriately conservative velocity estimates, this guarantees the body will never miss a collision, but it can also cause very high iteration counts in corner cases. You can move a lot faster if you allow the search to look forward a bit beyond potential impact times, turning it into more of a root finding operation. Something like this: https://box2d.org/files/ErinCatto_ContinuousCollision_GDC2013.pdf https://box2d.org/files/ErinCatto_ContinuousCollision_GDC201... I use a combination of speculative contacts and then linear+angular sweeps where needed to avoid ghost collisions. Speculative contacts can handle many forms of high velocity use cases without sweeps- contact generation just has to be able to output reasonable negative depth (separated) contacts. The solver handles the rest. The sweeps use a sorta-kinda rootfinder like the Erin Catto presentation above, backed up by vectorized sampling of distance. A bit more here, though it's mainly written for users of the library: https://github.com/bepu/bepuphysics2/blob/master/Documentation/ContinuousCollisionDetection.md https://github.com/bepu/bepuphysics2/blob/master/Documentati...

syntheweave 5y ago

As the other comments note, you can create a sweep form to detect penetration. But this belies the more thorny issues of achieving a "high quality" solution: if two things impact a third within the exact same time step, you have to come up with a globally satisfying solution that coordinates all three, and sweeping doesn't do that by itself, it just says "well at some time it might hit one or both of them" - which if you run with directly, leads to weird behaviors related to the information loss where objects squeeze past each other or gain excess energy or trigger events they shouldn't. The solution to that problem is generally handled through the solver by various iterative methods. In a 2D platforming game using AABBs this is as simple as "step the physics on Y axis, then step them on X axis" - which completely eliminates the possibility of hitting two things at once, albeit it makes corners "sticky" on one axis. Once you have things rotating and colliding at any angle it gets a lot harder and the focus then is on how to iterate approximately in a way that produces the least error. (If you can afford it, backtracking the solver to optimize the solution quality to some metric of fewest/smallest impacts is one way to create satisfying interactions).

TheAceOfHearts 5y ago

One option is to not worry about it so speedrunners can have a bit of extra fun breaking the game. It's a feature, not a bug!

tlarkworthy 5y ago

In games the fastest moving object is bullets, so model them as lines, not points.