Finding roots/zeros for collision detection?

Question

For the most simple of 2D games, I have implemented a posteriori collision detection (overlapping rectangles) on the x/y Cartesian plane, but am now interested in understanding the basics of a priori collision detection...

In the link here, I noticed the reference to Newton’s Method. So, I want to better understand the link b/w finding zeros of an equation and detecting a posteriori collision.

Let's start with the most obvious case of finding roots of an equation: If you have a projectile's trajectory modeled as a quadratic function, you can find the roots to predict at what time the height will equal zero (or any other constant height, actually, by just solving f(x)=C to be f(x)-C=0 and then finding roots of that expression).

So, as I understand, finding the root can tell me the time at which the object will be at any chosen height. More broadly, we basically know the (x,y) location of the object for any given time. But how does root finding, in particular, translate to detecting collisions with another object? (The other object may be stationary, or be moving. If the latter, do you also determine roots/location of this moving object as well? Calculate the (x,y) trajectory of both objects and determine where they will intersect?)

Again, the basic question is where does root finding come into play? Any links to a basic primer on this topic, with a simple example would also be greatly appreciated.

Answer 1

Root finding is used to calculate when two objects intersect (distance = 0 ) a basic example could be a Sphere/Plane intersection, This is solved easily by calculting the distance between the sphere and the plane and checking if it's near zero. Now the problem here is that we assumed that both objects are stationary and wont't change their position .

The more interesting thing to talk about, is actually when root finding using numerical analysis methods comes to play when you want to calculate dynamic collision detection, in other words when your objects are moving and you want to take time into account.

Your static collision detection methods can't predict that your object at t+ delta t will be at a different position because it doesn't take time into considerations, so the collision check might happen in a frame where the object has already passed the obstacle, this is also called quantum tunneling or tunneling. This happens due to the discrete nature of computers, that updates the program each frame/delta time.

It's best to explain using examples, so let's say you have a wall (Plane) and a moving ball.

Dynamic Collision Detection is used to avoid the drawback of static collision detection tunneling. So instead of checking statically each frame or number of frames, you instead model the ball/object movement with respect to the plane as a function of time. This can be numerically solved to find the root (t) when the motion curve of the ball intersects with the plane.

So now instead of only checking for collision at T0 and T0 + delta time we can take into consideration the time interval between those, where your application fails to model due to it's discrete nature.

Keep in mind that not all dynamic collision detection cases need to be solved using numerical methods. Analytical methods can also come to play which is actually faster, but this is only true for specific cases of motion and shapes.

Your best bet is getting real time collision detection or real time rendering, both books will give you an overview of the techniques with code samples. However the resources on the internet for this topic is scarce, these links can be a good start although nothing straightforward:

Collision detection tutorial, have a section on dynamic collisions detection and source code.

David Eberly's paper on dynamic collision detection, great info but might be a bit heavy.

Real time rendering companion website with a lot of resources, some of them are on static and dynamic collision detection.

But keep in mind that that static collision detection might be enough if your objects are not moving quickly, so make sure you need dynamic collision detection before you implement it, but regardless learning is never a bad thing.