Collisions Between Two Bodies Undergoing Multiple Transformations

I have been searching for an answer to this for a really long time and I have not found any definitive answers as of yet. What I am trying to do is determine if and when two bodies collided between the times t0 and t1. Calculating this is much more straight forward if each body is only either translating or rotating (about center or any point), but when adding multiple transformations on top of each other, things become a bit more messy. I made this animation to illustrate the problem.

RlfmW.gif


As you can see, at times t0 and t1 there are no collisions, but between there are multiple collisions occurring.

One way I thought of for tackling this problem was to reduce the size of the time intervals. So, between t0 and t1 there would be a total of n updates to check for collisions. This works, but the only way I found that I could guarantee no false negatives, i.e. not finding a collision that happened, was to integrate over extremely small time-steps. As you can imagine, this is very costly because it resulted in the tens to hundreds of time-steps per body per update cycle. I am not saying this idea has no merit, but I would need to find a way to calculate the minimum number of time-steps rather than uniformly moving each body forward one unit of distance/rotation until they reach the desired position and orientation.

So, my question is two parts:

  1. Is there a better way of determining if and when a collision occurs?
  2. If not, is it possible to calculate the minimum number of time-steps?
EDIT: I am not sure why this got moved to Programming and Computer Science. While I would like to know this for making a game, it is really a physics problem.
 

Attachments

Last edited:
10,452
3,971
I think because it’s more about detecting when a collision occurs for irregular shapes which make it about efficiently determining if and when a collision occurs.
 

Tom.G

Science Advisor
2,550
1,373
Just blue-skying here, how about:

For each body, draw an enclosing circle (sphere) around it with the circle centered at the center of rotation
If the circles intersect, the bodies can collide

-EQUIVALENTLY-

For each body, find the maximum extent of the body from center of rotation
Calculate distance between the bodies
IF {distance} {sum of maximum extents} THEN <collision possible>

That will at least filter out the impossible collisions.
 

Vanadium 50

Staff Emeritus
Science Advisor
Education Advisor
22,690
4,952
Tom G. is close. You want to do this for the smallest containing circles, i.e. circumscribed around the figures. This is irrespective of rotation.
 

anorlunda

Mentor
Insights Author
Gold Member
6,548
3,598
Draw a black and white animation, such as in the OP. Paint the first object. When painting the second object flipping pixels from black to white, if any pixel was already white, there is a collision.

That gives you an answer with one pixel resolution.
 

Vanadium 50

Staff Emeritus
Science Advisor
Education Advisor
22,690
4,952
Can you do this analytically? You can simplify with the points of one object colliding with the walls of the other.
 

Ibix

Science Advisor
Insights Author
4,868
3,192
Can you do this analytically? You can simplify with the points of one object colliding with the walls of the other.
The problem is that in any frame at least one of the bodies is moving (in general) so a point on the rim has an equation of motion that looks like $$\vec{x_0}+\vec vt+R\left(\begin{array}{c}\sin(\omega t)\\\cos(\omega t)\end{array}\right)$$which is difficult to solve...
 

anorlunda

Mentor
Insights Author
Gold Member
6,548
3,598
Numerous computer games must deal with projectile-target collisions. How do they do it?
 
Simplified models, often, I think.

https://en.m.wikipedia.org/wiki/Hitbox
So my engine so far has hit boxes implemented for rough collision detection, and then goes into the fine tuned collision detection if the hit boxes collide. That works, so if I have an exact time, I can say definitively if there is a collision or not. My problem is finding that time. Because this is a simulation, there has to be a certain time-step to integrate with, and that is the root of the problem I am having. If the time-step is too big you risk missing a collision, and if it is too small you risk performance issues. I have a couple of game engine books and one specifically on physics, and this problem is brought up only in the context of particle simulation where ray casting can be used, which is straightforward and easy.

That is why I decided to bring my question here to the physics forums. Either the answer I seek is super complicated and therefore is not easy to find because not many people can explain it and/or understand it, which may be part of the issue because most resources I found are very simplistic and only deal with circle collisions, or this is somewhat of an industry secret and each development company keeps their method under a lock and key.
 

Ibix

Science Advisor
Insights Author
4,868
3,192
One trick I've read of is to find a set of circles that approximately fill your shapes. Then the problem reduces to repeated circle collision detection.

The mathematical problem is the trigonometric term in my last post. But if you can assume that ##1/\omega\gg\delta t## then you can treat it as constant over a time step of length ##\delta t## and just solve the linear part of the equation. Hope that makes sense.
 
The problem is that in any frame at least one of the bodies is moving (in general) so a point on the rim has an equation of motion that looks like $$\vec{x_0}+\vec vt+R\left(\begin{array}{c}\sin(\omega t)\\\cos(\omega t)\end{array}\right)$$which is difficult to solve...
8Ksqh.png


Is this what you mean when talking about the motion for the point at the rim?
 

Attachments

Ibix

Science Advisor
Insights Author
4,868
3,192
Yes. The problem is that you need to set that equal to the similar equation of motion for a point on the other object and solve for ##t##. That's straightforward if you pretend the rotation happens instantaneously between ticks (and hence you don't need to include a ##t## inside the trigonometric functions) rather than smoothly during ticks.

A different approach, depending on how far in advance you can predict your objects' locations, is to solve the full equation numerically far in advance. So if your objects are asteroids, say, and not going to be changing trajectory unless they collide, you can pre-calculate collisions and just check your list of future collisions to see if any happened each time step. It won't work if many of your objects are under active control since the unpredictability means you'd be recalculating all the time.
 
Yes. The problem is that you need to set that equal to the similar equation of motion for a point on the other object and solve for ttt. That's straightforward if you pretend the rotation happens instantaneously between ticks (and hence you don't need to include a ttt inside the trigonometric functions) rather than smoothly during ticks.
I thought about that, but I ran across a case that may cause issues. Imagine the shape on the right was a rectangle rotated in the direction that it is moving that is longer in the translation direction than it is wide. If it rotates 180 degrees, then translates, it will miss the collision, even though if it was rotating while translating, it would collide around 90 degrees.
 

Ibix

Science Advisor
Insights Author
4,868
3,192
If it rotates 180 degrees, then translates, it will miss the collision, even though if it was rotating while translating, it would collide around 90 degrees.
But for that to happen you have to have an angular velocity of around ##\pi## radians per time step, ##\omega=\pi/\delta t##. Note that I said it would only be appropriate if your angular velocities satisfied ##1/\omega\gg\delta t##, which is not the case in this example.
 
Last edited:

anorlunda

Mentor
Insights Author
Gold Member
6,548
3,598
If the time-step is too big you risk missing a collision, and if it is too small you risk performance issues.
How then can anyone answer that without numbers? What are the max velocities? How slow is an "issue"? You need first to specify requirements.
 
How then can anyone answer that without numbers? What are the max velocities? How slow is an "issue"? You need first to specify requirements.
I don't have any specific values, but doing 100+ integrations per object would task the processor. If the simulation has 500 to 1,000 entities that would be 50,000 to 100,000 integration steps. That is probably too much for most computers.
 
But for that to happen you have to have an angular velocity of around ##\pi## radians per time step, ##\omega=\pi/\delta t##. Note that I said it would only be appropriate if your angular velocities satisfied ##1/\omega\gg\delta t##, which is not the case in this example.
I think the maximum translation per time-step can be the shortest distance between any two points in the body. This would not allow it to hop over anything. When it comes to rotation about the center or orbiting a point I do not know how to determine the minimum angle. It probably has to do with the arc length, but what should that maximum distance be?

EDIT: this is not right. For a triangle, the base would be the shortest distance between two of its points, but the top could pass through something that is less wide than the triangle base.
 
Last edited:
I don't have any specific values, but doing 100+ integrations per object would task the processor. If the simulation has 500 to 1,000 entities that would be 50,000 to 100,000 integration steps. That is probably too much for most computers.
If they all interact you have a problem. If they don't the advised previously provided to use bounding volumes/boxes helps to cut down on the cost by magnitudes.
 

Vanadium 50

Staff Emeritus
Science Advisor
Education Advisor
22,690
4,952
If you don't tell us what the constraints and limitations are, it will be hard to provide more than generalities.

I find it hard to believe that it takes less time to integrate over many steps than to solve a dozen equations. They are ugly, but we know them in advance, and more importantly, we know their derivatives in advance, so we can use Newton's method to get an arbitrarily good solution quickly.
 

Klystron

Gold Member
305
314
There are several tested algorithms derived from fire-control radar systems adopted by early video games including "track while scan" and "gun laying algorithms" that simulate the optimal collision of a moving projectile with a guided or unguided moving target. While the wikipedia references are informative they are 1) quite general and 2) use British radar phraseology that may obscure the relation to your questions. Assuming the objects in the original posts permit radar (EM) returns and the presence of a tracking system, collision data is inherent in the scanning "memory" including hits and misses. Object rotations and minor course corrections are typically subsumed in the much faster EM returns; the basis of radar tracking.

While the objective of "gun laying" algorithms is to cause a collision (kinetic projectiles) or to intercept the moving target such that it enters the "circle of destruction" of an exploding projectile during the correct time interval, similar algorithms have been modified for electronic traffic collision avoidance systems (TCAS) to avoid collisions. Both intercept and TCAS easily fit aboard modern air/space -craft often assisted by a dedicated EM system on the ground, in the air (such as AWACS), or from space. In all cases the idea is to create a field that produces returns from the moving objects.

In place of visualizing with triangles, I suggest using conic sections oriented from the targets or from the source of the indicated EM fields. Stipulating a third object -- a radar or lidar, for example -- also allows you to track the projectile while scanning/tracking the target but this model is not necessary. The projectile, say a guided missile, can include EM target tracking noting that the system and information is destroyed during the successful collision. Hard examples include SHRIKE missiles that home on radar emissions and heat-seekers that track radiation in infra-red.
 

Want to reply to this thread?

"Collisions Between Two Bodies Undergoing Multiple Transformations" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top