1
\$\begingroup\$

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.

Animation

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 (it makes calculating the collision response much easier since I know the exact points of contact), 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?

P.S.

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.

\$\endgroup\$
0
\$\begingroup\$

There is a method of pixel-perfect collision detection for polygons such as this that involves using the dot-product operation. You essentially get the angle between each vertex of the shape and divide the screen into two sides and determine if the shape overlaps the other shape's "side" for any two vertices, and if so, move the shape outside of the other shape's collision area and a collision is detected.

Here is a short article on the method:

https://onense.wordpress.com/2011/11/04/the-dot-product-is-awesome-adventures-in-collision/

\$\endgroup\$
  • 1
    \$\begingroup\$ Wouldn't that only work for static points? Also, how would this work for rotation? I have code in place currently that can check if two shapes are overlapping so that is not the issue I am facing. \$\endgroup\$ – Jedi_Maseter_Sam Feb 7 at 16:18
  • \$\begingroup\$ Why would you think that it would? In this case, you wouldn't transform the position of the vertex that collides with the shape, but the position of the object it collided with as a whole. So if you represent the position of your objects as an (x,y) pair in the center of the object, just translate that. \$\endgroup\$ – Darin Beaudreau Feb 7 at 16:29
  • \$\begingroup\$ But the points on the edge are not moving in a straight line. I read the article a few times and I do not see how this can be applied to my problem. \$\endgroup\$ – Jedi_Maseter_Sam Feb 7 at 16:58
  • \$\begingroup\$ Ah, I slightly misunderstood what you were asking. So these objects aren't being updated and moved in real time, and you just have their rotational and movement velocities and positions and want to know if they would collide in a certain time-frame? \$\endgroup\$ – Darin Beaudreau Feb 7 at 21:13
  • \$\begingroup\$ That is correct. I found this paper that might have the answer. twvideo01.ubm-us.net/o1/vault/gdc2013/slides/… \$\endgroup\$ – Jedi_Maseter_Sam Feb 7 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.