Hi there, These last few weeks I went back to the physic code I started some months ago (>6) and you maybe remember my thread about it. Well, I've been reading a lot of things ever since and I improved it quite a lot so here it is. This is DirectX8 and it uses triadic operator without checking for support (Geforce2MX has it) so I suppose it should work almost everywhere. Comments are more than welcome, if people are interested I can post a kind of what worked/what didn't about the various tricks I tried to make it more stable. The most interesting thing being that it actually is almost a bare implementation. Most tricks I used to use (sticky col, time warp) where in fact not useful or would even cost some stability when used. So it's impulse based with normal Euler integrator and close to no damping, 32 iterations max, largest mass ratio in scenes is 1/10 all under standard Earth gravity, scales are corrects so, for example, the books are small and light. The previous version couldn't stabilise one book of this size on the ground at 150hz \:. There's a lot of drifting going on at 75hz and I've started studying how to solve contact points simultaneously because it definitively is the key to more stability. The problem being that my maths really are not up to the task so far. You may find some setup too stable and that's due to the activation threshold being too large. Simultaneous contact solving should allow to reduce that threshold so stacks can deactivate and activate as expected. I also have some ideas on how to improve the reactivation heuristic that would require that I maintain a list of sleeping contact wich I do not have now... Oh and yes, I still only have OBB/OBB collision (well with contact support) so I really need to add some more of these... [Edited by - b34r on June 23, 2005 2:02:40 AM]

Quote:Original post by mengha
That was good :)

One thing that was strange though is your controls:
Q = Strafe Left
D = Strafe Right
Z = Forward
S = Backward

Wouldnt doing WSAD be a better idea?

Arg, sorry about that... Damn :( sorry for all non-french keyboard layout users... I thought Windows would map the VK_ flags.

Quote:Original post by Programmer16
The physics in that were awesome (good graphics too.) Keep up the good work!

Thanks [smile] I plan to!

Quote:Original post by MrRowl
That's really really good :)

I'd be very interested to read more info about your implemtation, if you're able to post it.

Edit: Ah yes - just realised what your original thread was - the one that made me go and write jiglib!! Looks like I have some more work to do to catch up again :)

Ahah, no way you don't need to catch up. Jiglib is very nice and stable, I also saw you implemented polymesh collision, that's nice! It's on my todo list because box/box is getting very limited [smile]. I'll try to sum up some details of my implementation no problem, that's just fair seeing how your various posts helped me so far. Later then.

Ok, big one incoming...
Some of the things that had the greatest impact on stability were:

• Contact determination. I'm using the SAT for overlap determination. I simply collect both OBB extremities along the overlap normal and perform feature clipping from there to determine a contact feature set. Simply changing the way I defined extremities from farthest along the normal' to 'inside the offending OBB' gave a major stability increase. This is the modification that made the more difference so far.
  
• Allow some amount of interpenetration. That is, completely ignore contacts when the penetration amount is below a given threshold (in the demo 1.0mm). Now when the penetration correcting impulse kicks in, instead of having it resolve the penetration completely, have it resolve the penetration minus epsilon (i'm using half the penetration tolerance). This is a standard method when dealing with thresholds to have a 'neutral' zone in order to avoid oscillating around the threshold boundary. However, I really didn't expect it to have much impact in this case and I honestly don't really get why it helps so much.
  
• Deactivation/activation heuristic: As Mr.Rowl says it, this one is easier said than done. I can't recap all the heuristics I tried but the simplest the better (as usual?) and for what its worth the current algorithm goes like this:
  
  When inactive, wake up if:
  
  
  
  • (1) In colliding contact with a body whose velocities are above the activation threshold (16x sleep threshold in the demo) or (2) if after the solver pass the body velocities are above the activation threshold. Note: The activation threshold is a two-edged sword. When a very large activation threshold is used it can make arbitrary large stacks stable but also prevent correct reactivation in many cases (see my plans for a possible fix to this large activation threshold and activation problem). The (1) point can be omitted and relying only on the post-solver test kinda works. Bodies are indeed woke up but the initial response is flawed since the initial overlap occurs with a sleeping body the active body's velocities will most likely be completely cancelled and the sleeping body will receive no impact at all. This is very dependent on my implementation however so YMMV.
    
  • Contact vanishes. Detecting when a contact between two bodies vanishes is fairly easy if you have the previous update contact list handy when starting a new update. Just check that each contact in the list are still touching. If not, wake up the contact body pair. Note: I currently do not store sleeping contacts so I could (and should) miss some reactivation since two inactive bodies are not considered by the overlap tests (and so no contact pair is stored). What's helping here is the penetration tolerance that guarantees that in most cases after reactivation and the first position update the newly activated bodies will still be in contact. This should fail sometimes but in practice does not so I didn't bother fixing it until now. I have an idea on how to easily fix that (not sure how it will look tho :)) wich would involve delaying the position update for one update on reactivation so that the collision engine has time to register the contact with sleeping positions.
    
  
  
  When active, go to sleep if:
  
  
  
  • If velocities are below the sleep threshold for 'n' updates and there is a colliding contact with at least one inactive body.
    Requiring a contact makes sure that active bodies with very low velocities do not go to sleep while mid-air. Requiring a contact with an inactive body avoids up/down deactivation in stacks wich is very bad. Very bad since a body velocity must go back above 16 times the sleep velocity to reactivate, bottom bodies in large stack would often get caught between two deactivated bodies and slowly crawl out of the stack in search for more room to rest (this problem can be seen in Meqon maybe for different reasons tho). This also helps against overly stable stacks. In the demo, for example, the Jenga stacks are too stable but when the top of the stack is woke up in an non-equilibrium position it will collapse while it could incorrectly go back to sleep if the sleep order was not enforced. Requiring a colliding contact (as opposed to a resting or separating one) makes sure that when a contact vanishes and causes a reactivation, the reactivated body does not incorrectly go back to sleep. Not requiring a colliding contact would be a problem as we allow some penetration and, for example, in a sleeping stack where the bottom body is removed all sleeping bodies are in resting/separating collision with a sleeping body directly above them (re-edit: no it makes sense [smile]).
    
  
  

Some of the things that had potential but were in fact causing more problems than they would solve:

• Buffering impulses and processing them after a solver pass. It avoids erratic bounce on face/face contacts and as a derived benefit increases stacks stability. However, as Mr.Rowl (again :)) states it on his website the combined impulse (well at least by naively averaging force and torque) is incorrect. A moderate stack of boxes will go up and down as the impulses fail to stop the stack from collapsing and the penetration impulse kicks back in, this no matter how much iterations are took. It also badly prevent disturbed stacks from going to sleep efficiently (eg: shooting on the pyramid in the demo would most of the time entirely wake up the stack and take several seconds to deactivate when it not would fall down due to the base crates crawling out). I'm however convinced that solving impulses simultaneously for each body will increase the demo current stability by a great deal as the main source of stack instability right now is the jittering induced by the sequencial (yet quasi-randomized) processing of the contacts. This should also help a lot when running less updates per second.
  
• No sleep delay but an equilibrium check. This works incredibly well and feels very robust, it's a shame I couldn't solve the one big quirk I encountered. The algorithm went like this, when item velocities goes below their threshold perform a check on the current contact set. If more than 2 contacts, not lying on the same line, can be found then go to sleep. It works 90% of the time... and especially not in stacks (doh! :(). As there are contacts both above and under stacked bodies that do not lie on the same line any stack will go to sleep immediatly even while falling. Of course I tried for a while to add some more heuristics to filter the bad cases but got some pretty bad headaches so left it where it was. Note: Heuristics needs to be modified on a per body basis. Obviously a sphere only requires 1 contact to go to sleep while a two-sphere composite object will use the same heuristic as a box.
  
• Time warping, well I believe that's how it is called (see Mr.Rowl's website for a description of the method). Very efficient at removing bad bounces caused by too large penetration correction but starts stopping bodies before they actually get in contact and I have better results both in stability and plausability without it.
  
• Sticky contacts, good to artificially improve stacks but prevents fast deactivation as stacked bodies are not free enough to move out of offending positions.
  
• Shock propagation and variant. Brilliant for large stacks but also makes them way too stable. Mr.Rowl's modification, not to update angular velocity during the shock propagation, helps solving the over-stability issue a bit but I do not feel like the cost in plausability is worst the stability and increase in complexity unless you're making buildings or alikes ;). I also tried a pseudo shock propagation wich is not activated in the demo where an extra solver iteration is taken with all active bodies set to the same mass. This seems to work okay but I didn't test it that much so far. A variant, that I did not test, would be to only take the first iteration of the solver with different mass and all following ones with equal masses, this should be ugly though...
  
• Activation resillience. I tried to make the activation threshold dynamic so that when a body goes to sleep the activation threshold is set to 128xsleep threshold than gradually goes down to sleep threshold. This worked to some extends, it give a nice effect were any activation will propagate through all contacts but didn't really help with either stability or activation problems.
  
• Filtering gravity. When things are stacked and settling down what really makes things unstable is the gravity so I tried a great deal of on-contact gravity filtering but they all had some kind of drawbacks that didn't justify the (sometime major) increase in stability.
  

Next things to try in order to increase stability:

• Find an efficient way to store original delta position (at deactivation time) between an active and an inactive body so that it is possible to wakeup body if the delta gets too big. This should allow for much higher activation threshold while still waking up stacks when a body is slowly removed from the bottom of the stack.
  
• Multiple contact processing...
  

Another nasty hack wich somehow increased stability but not that much, so the demo is not using it, is to blend the current body velocities with the previous state ones in place of standard damping. The drawback is that it bias speeds and collision feedback, really not nice. However it does really help the integrator as it blur out sudden changes in velocity. A blend coefficient of 0.8 (nv = nv * 0.8 + ov * (1 - 0.8)) does not impact too much on the realism and used to provide a nice improvement in the earlier stages of my simulator.

About speed, its full C++ with no special optimisations, using a sweep and prune ala OPCODE with insert sort. Not much more really :). I also discovered with some of the later test scenes that my renderer is awfully slow at rendering large number of small objects.

If you need more details, do not hesitate to ask.

edit: Added 2 hack I tested.

[Edited by - b34r on June 20, 2005 5:08:36 AM]

All I can say is fantastic!

Keep up the good work, I find these posts very intresting….

Quote:Original post by Structure
All I can say is fantastic!

Keep up the good work, I find these posts very intresting….

Thanks ;) I'll add more of the things I tried to the lists as I recall them...