Collisions Between Two Bodies Undergoing Multiple Transformations

In summary, the problem is that it is difficult to determine when two bodies will collide, and there is a limit to the number of time-steps that can be processed per body per frame.
  • #1
StarWarsNerd
19
1
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

  • RlfmW.gif
    RlfmW.gif
    228.5 KB · Views: 585
Last edited:
Technology news on Phys.org
  • #2
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.
 
  • #3
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.
 
  • #4
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.
 
  • #5
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.
 
  • #6
Can you do this analytically? You can simplify with the points of one object colliding with the walls of the other.
 
  • #7
Vanadium 50 said:
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...
 
  • #8
Numerous computer games must deal with projectile-target collisions. How do they do it?
 
  • #10
Ibix said:
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.
 
  • #11
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.
 
  • #12
Ibix said:
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

  • 8Ksqh.png
    8Ksqh.png
    17.5 KB · Views: 412
  • #13
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.
 
  • #14
Ibix said:
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.
 
  • #15
StarWarsNerd said:
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:
  • #16
StarWarsNerd said:
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.
 
  • #17
anorlunda said:
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.
 
  • #18
Ibix said:
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:
  • #19
StarWarsNerd said:
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.
 
  • #20
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.
 
  • #21
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.
 
  • Like
Likes Ibix

1. What is meant by "multiple transformations" in the context of collisions between two bodies?

In this context, multiple transformations refer to changes in the velocity, direction, and/or shape of the two bodies involved in the collision. These transformations can occur before, during, and after the collision.

2. How do multiple transformations affect the outcome of a collision between two bodies?

Multiple transformations can greatly impact the outcome of a collision between two bodies. The changes in velocity, direction, and shape of the bodies can result in different types of collisions, such as elastic or inelastic collisions, and can also affect the final velocities and momentum of the bodies after the collision.

3. What factors influence the number of transformations that occur during a collision between two bodies?

The number of transformations that occur during a collision between two bodies can be influenced by factors such as the initial velocity and direction of the bodies, the angle of impact, and the physical properties of the bodies, such as their mass and elasticity.

4. How do scientists study and analyze collisions between two bodies undergoing multiple transformations?

Scientists use mathematical equations, computer simulations, and experiments to study and analyze collisions between two bodies undergoing multiple transformations. They also use principles of physics, such as conservation of momentum and energy, to understand the behavior of the bodies during the collision.

5. What practical applications can be derived from studying collisions between two bodies undergoing multiple transformations?

Studying collisions between two bodies undergoing multiple transformations has practical applications in various fields, such as engineering, sports, and transportation. It can help in designing safer cars and other vehicles, improving athletic performance, and understanding the effects of collisions in different scenarios, such as in car accidents or sports injuries.

Similar threads

Replies
10
Views
1K
  • Classical Physics
Replies
12
Views
1K
  • Programming and Computer Science
Replies
12
Views
1K
  • Introductory Physics Homework Help
Replies
2
Views
1K
  • Mechanics
Replies
5
Views
912
  • Classical Physics
Replies
13
Views
2K
  • Mechanics
Replies
9
Views
1K
  • Programming and Computer Science
Replies
1
Views
888
Replies
2
Views
828
  • Programming and Computer Science
Replies
2
Views
2K
Back
Top