One of the bottlenecks to obtain real-time physical based simulations is the collision detection process and much research has been done on this. In the past, I proposed a method to fit the collision process to any given budget of time. See the paper here. This method works for rigid and deformable bodies.
The idea is to interrupt the collision process when our budget of time has expired and use the available information to compute the collision response (it this happened). The computed response is an approximation of the real one: Yes, we trade time for accuracy, but in general the results are quite satisfactory.
The method is based on sphere representations of the object. Each of these representations goes from a coarse representation (a) to a high quality representation (d). If we have little time, we compute the collision detection process using (a) or (b) representations as in the figure above. If we have lots of time, we use more detailed representations (c) or (d). The coarser the representation the less accurate is the response (or even the detection).
The complexity of the problem comes to compute good responses even with little information.
The question is: do you prefer high accurate responses even if your application goes slow or do you prefer to keep your simulation rates and obtaining some non-accurate responses ??
Well, here at Atari we have decided to go for high accurate responses... so, that means that I will have to find other ways to keep good simulation rates... good challenge !
So, if anybody have some good ideas, please let me know.