   Linear Physics Engine Problem: Multiple Collisions
  I've had this problem for a while now. Once I tried to solve multiple collisions with my engine, there were a lot of things I wasn't sure about. I think the general problem is that the number of iterations become so huge. I'm fairly sure that this is because the velocities and impulses all converge onto something so small, because when using floating point numbers, it will be as accurate as it possibly can. But I'm just not sure how exactly to limit the accuracy of everything.  I started just going thru the narrow collision function, and I tried just changing part of it. Rather than checking if the relative velocity along the collision normal was > 0, I changed it to see if the relative velocity along the normal was > than EPSILON, which I have defined at '0.00000001'. This did lower the number of iterations, but not by enough. And the entire time, I was thinking that if I kept it like that, it would just eventually crash. This is because my simulation loop is based on the simulation loop that was given by Chris Hecker. If the penetration goes beyond some amount, the time step will be sub-divided. So if the coefficient of restitution is 0, and at the last iteration the position was at the maximum penetration depth, no matter how many sub-divisions, it would never get out of that penetrating state. Is this correct? So I'm thinking that what I did with Epsilon was an incorrect use.  Another thing that I tried was, once the number of iterations go over some amount, I run a function that halts all the objects along involved in a collision along the collision normal. But this just doesn't seem to be a very good idea. It works well for one situation that I set up, but for others it just makes very unrealistic behavior. So I think I should take that out as well. I have searched some things about multiple collisions, but the majority of them seem to say that going thru each collision pair iteratively is the best way to solve it. And some other resources I've looked thru seem to address, indirectly, the problem I have. But I think those use a different overall method than me, like accepting penetration, and not sub-dividing the time step.  So is there any obvious way of reducing the iterations that I am just missing?Edit: Does it involve rounding, or the use of epsilon? I just cant seem to think of anything![Edited by - dustydoodoo on June 24, 2009 8:48:04 PM]
  You can warmstart your solver. This gives armotized iterations ofver several frames   ;  I'm not sure if that is what will help. I think my problem is a little more immediate than that. I kind of thought that warm starting was something of an optimization. My problem is something that needs to be solved in order for it to work! The number of iterations it uses right now to keep two boxes stacked on the ground is about 400! And my engine doesn't even have rotational effects, it's just linear!   Right now my 'solver' looks something like this:while(collDataList.getSize() > 0){    for(int i = 0; i < collDataList.getSize(); i++)  resolveCollision(collDataList);    collDataList.clear();    collisionNarrow(ptlCollDataList, collDataList) // searches through first array for collisions, pushes any colliding pair into the second array}My overall simulation loop is like this:- apply gravity- integrate- perform broad collision check,- using the results of the the first check, perform narrow collision check- if any pair of objects are penetrating, subdivide the time step and start over- else, [the source I posted]- save time step;  Hmm, could part of the solution be to add an impulse proportional to the penetration depth? My narrow collision phase allows the objects to be interpenetrating one half of a pixel. Maybe if I did that, I could limit the relative velocity needed to count as a collision to some number below the minimum penetration depth! I'm not sure though... Does this sound like something that would work?   ;  I would create some outward velocity, rather than adding an impulse. So = instead of +=. Your objects should just boil out of each other rather than explode like popcorn. Dunno if it'll help your iterations though..   ;Quote:Original post by bzroomI would create some outward velocity, rather than adding an impulse. So = instead of +=. Your objects should just boil out of each other rather than explode like popcorn. Dunno if it'll help your iterations though..Thanks I will try that :)It seems as though I'm going in the right direction. I've got the iterations way down now. But I've just got to stop the objects from penetrating indefinitely at the start of the frame.   ;  I would have thought that if you're subdividing the timestep you don't want to use an iterative solver, since that solver will (unless you don't care about performance) generally not completely resolve the collisions if they involve more than one contact point (warmstarting doesn't make sense for collisions, I think, because they're not (shouldn't be!) persistent, even though it does make sense for contacts).Why are you subdividing the timestep? Because you're interested in (engineering quality) accuracy? If you don't subdivide the timestep, but instead use the velocities at the start of the step to predict contacts (and near contacts), then process them before updating the position, this still prevents penetration in most cases (you can still get penetration as a result of not doing enough iterations, or when the contact prediction was not good enough). This also probably gives a much more "stable" processing cost - it's not nice for a physics engine to be unpredictable in its performance.   ;  I subdivide the time step simply because that's what all those articles by Chris Hecker used. I thought it was just the way it was usually done. Thanks for helping. That sounds like a good way of doing things. I will work on changing everything.   ;  You should look at Erin Catto's presentations here: www.gphysics.comTwo boxes stacked on e.g. a ground plane are stable at 1 iteration with warmstarting. A stack of 5 boxes is stable at 4 iterations. Both simulations using a fixed timestep of 1/60 ms and a gravity of -10.If you need 400 iterations there must be plenty of errors.Cheers,-Dirk   ;  Ok, thanks :)   