# Finding roots/zeros for collision detection?

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.

• You can write an expression for the distance between two objects as a function of time. When the distance is 0 you have a collision. – Charles E. Grant Dec 7 '13 at 17:17
• Ah, that makes sense. I can see this working on 2 circular objects, but, what if the shapes are irregular? How do you calculate the distance between them when some parts may overlap, and others may not? – JackOfAll Dec 8 '13 at 17:00

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.

• Yes, this makes sense. I have run into "tunneling" myself, when coding in Visual Basic, and the "timer" control isn't iterating fast enough to check 2D overlapping rectangles quickly enough, and the object has already passed through the other. – JackOfAll Dec 8 '13 at 17:02
• Where can I take this idea to the next concrete level? I would like to implement (or download) a simple example of dynamic root finding to CALCULATE when/where something will collide. – JackOfAll Dec 8 '13 at 17:03
• @JackOfAll I edited the answer. – concept3d Dec 8 '13 at 17:27
• I'll take a look. Thanks for getting me started! This is actually just theoretical. I am not actually making a game. I just want to understand the basic principle and, at most, implement a very basic rudimentary example of dynamic. I have done overlapping rectangles before (comparing top/left/height/width of 2 rectangles) but want to know the basics of root finding, etc. Am more interested in the Math that is used, but would be lovely to try a "Hello World" caliber example of dynamic collision detection of the most simplest kind. – JackOfAll Dec 9 '13 at 3:41
• I don't want deep theory or 3rd part libraries, as I am not actually coding up a game. I just want to learn the concept behind this idea in a very simple yet "real" example. Maybe there is a very basic tutorial that demonstrates this? Like a parabola trajectory and seeing when it hits some other parabola. Then I could use some distance formula and calculate when distance = 0... right? – JackOfAll Dec 9 '13 at 3:45