Sign in to follow this  
Thaumaturge

Polygon-polygon collision - corner-related bug (I believe)

Recommended Posts

I'm currently working on pinball physics, using (for reasons beyond the scope of this thread, I think) polygon-to-polygon collision. Both the ball and the walls are represented as series of points, and via those points, line segments. By storing the ball's last position, I'm able to take into account movement, and thus have the system working fairly well for both high and low speeds, I think. "So what's the problem?", you may be thinking. Unfortunately, under certain circumstances I find that the ball manages to penetrate a wall and get stuck, freezing the game in an eternal loop of collision after collision with no resolution. This seems to happen when corners are involved in the collision, although it's hard to be certain that it will never happen without a corner being involved. Testing suggests that the ball may be colliding as per usual the first time, somehow not escaping directly afterwards, and then being bounced back and forth with decreasing power over and over. How this might be happening I'm not sure, I'm afraid - the system that I have in place looks to me as though it shouldn't allow the ball to stay within the wall, as long as the appropriate values are being reported correctly - which I suspect of being my problem. In brief and broad strokes, and with some simplification (excluding some test culling, for example, as well as the flippers) this is more or less how my current system works: First, collision testing returns a rollback time (which should be duration for which the objects have been colliding - and thus the amount of time to roll back in order to have them just touching), a response "push", and a collision point (used elsewhere). In the main game logic loop:
dt = 1
while(may_continue and dt > some_small_value)
 {
  for each object
   {
    update by dt+some_very_small_value
   }
  
  for each object
   {
    for each wall
     {
      test for a collision between the current object and wall
      if the reported time is greater than the current maximum,
       set the minimum to the reported time, and store the index
       of the current object.
     }
   }
  
  if a collision was found
   {
     dt = maximum_reported_rollback_time
     
     for each object
      {
       update by -dt-some_very_small_value
      }

     apply the "push" force to the object that collided
   }
  else
   {
    may_continue = false
   }
 }



In other words, I update each object, find the largest rollback time (i.e. the earliest collision), rollback by slightly more than that amount of time (so that the objects are not colliding), apply the appropriate force to that first collider, then try again - and continue trying again until either there are no collisions, or we run low on time in the current frame, in which case the last action taken should be a rollback, leaving no collisions (hopefully). It seems to be in this loop that the system is getting stuck - in the problem cases that I've looked at, after a certain point the rollback times don't seem to decrease overmuch, although the "push" dwindles to zero- or near-zero- length. The collision test looks something like this:
for each point in the object (e.g. the ball), create a segment
 from that point's last position to its current position. We will
 call this list "obj_segments".

Do the same for the wall, subtracting the object's offset to
 generate the "current" position. We will call this list "wall_segments".

for each segment in the wall (not wall_segments)
 {
  for each segment in obj_segments
   {
    If they intersect
     {
      use the difference between the reported intersection point and
       the end of the current obj_segment to find the depth of intersection
      
      if the depth of intersection is greater than the current maximum,
       replace that value with this (and note that there was an intersection).
     }
   }

  if an intersection was found, project the object's velocity onto the
   normal of the current segment of the wall, negate that, multiply the result
   by 1+a_restitution_value (the latter of which lies between 0 and 1), and add
   that to a cumulative response "push".
 }

//Handle corners of the wall penetrating the object
for each segment in the object (not obj_segments)
 {
  for each segment in wall_segments
   {
    if they intersect
     {
      use the difference between the reported intersection point and
       the end of the current wall_segment to find the depth of intersection
      
      If the depth of intersection is greater than the current maximum,
       replace that value with this (and note that there was an intersection).
     }
   }

  if an intersection was found
   {
    take the normals of the wall's current and previous segments,
     add them, and then normalise the result to give a new normal.

    project the object's velocity onto this new normal, negate that,
    multiply the result by 1+a_restitution_value (the latter of which
    lies between 0 and 1), and add that to a cumulative response "push".
   }
 }

finally, calculate the rollback time as
  rollback_time = maximum_penetration/object_velocity_length,
and return that and other relevant values.



The first potential problem that occurs to me is that corner intersections might be reporting incorrect penetration depths, and thus resulting in incorrect rollback times - potentially too little to clear the object from the wall. However, I don't see the flaw in my penetration depth logic at the moment. Similarly, I'm aware that the resulting combined normal might not be quite appropriate - but I don't think that it should cause this problem, since the rollback should keep the object clear of the wall, even if it ends up going the wrong way, and I don't think that I have any anti-parallel pairs being combined. I've performed searches, here and elsewhere, and have been working at this problem myself for a while, but thus far to little success. I realise that I may not have given enough to go on here - but I'm honestly not sure of which way to look at this point, so perhaps we should start with any suggestions that you might have for places in which to look, things to check, or portions of my system to elaborate on. Of course, if anyone has any suggestions that they believe might solve the problem, then please do share them! My thanks for any help given, and my apologies for the long post. ^^;

Share this post


Link to post
Share on other sites
My suggestion would be to understand more about the problem. A good way to debug rare problems like this is to make your physics engine deterministic (lock the timestep and make all randomness come from a constant seeded value), then play around until you get a repro-case. If you have the ability to load/save the state in the engine, you can save periodically and then when you repro it, rollback to the save and step forward until you hit the problem. Then you can step through everything on the exact frame it's happening.

It's hard to tell if the problem is in your collision detection or response. Are touching (not penetrating) collisions properly handled? Or maybe its somehow penetrating farther than the maximum penetration distance? Or maybe its detecting penetrations of multiple walls (since it is at a corner) and doing something strange because of it, or it picks the wrong wall on different iterations.

Good luck!

Share this post


Link to post
Share on other sites
Thank you very much for your suggestions - you have some good ideas and advice there, I believe. ^_^

Ironically, I think that I just found and sorted out the problem.

It was a typo, by the looks of it - I had left an 'x' where I should have changed it to become a 'y'.

further investigation of the problem, originally aiming to confirm that it was indeed a corner issue, revealed that it was actually a top-intersection issue (I feel silly for not thinking of and testing for that rather sooner >_<), which led me to look at a piece of code that I hadn't checked, which set up a board-phase (well, closer to medium-phase, I suppose) collision cull.

It turned out that I was at one point comparing a point's x-value against a currently-stored y-value. >_<

I do still have some genuinely corner-related issues - thankfully rather less serious ones, I believe - but those I think that I can handle.

Thank you again, however - your advice is much appreciated! ^_^

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this