Hello. I'm working on a game that uses a simple physics engine to simulate the movement of some (spherical, later maybe rectangular) 2D objects "inside" the screen, using an accelerometer to make them tumble about the (smallish, 240x320) screen. I need to use fixed point maths only (one potential culprit is my newtonian iteration function for the square root, but it seemed sufficiently robust so far). There are to be anywhere between 1 and 20 Objects of identical mass and size on the screen. "Gravity" is determined by the XYZ-accelerometer input, plus some special "toss" impulse changes that occur when a short peak input comes from the accelerometers. Here's what I have so far: I use an Euler integration method, but I'm tentatively looking into better ones. The problem is, my target platform has a very limited processing power and memory. Maybe you can suggest one? Object-to-wall collisions are simple, I just clip whatever coordinate exceeds the maximum, reverse the velocity, lock the object's degree of freedom for the frame, and reduce the speed a little to emulate a semi-elastic collision. Because I want something to graphically happen to the object in that instant, showing it exactly at the point of collision for one frame is an added benefit of my method. For object-object-collisions, I use simple "Pool Ball" physics to calculate the changes in direction when they collide, by determining the impact normal, separating the objects along this normal, projecting the impact velocity onto it, calculate the impulse and determining the result to the velocity vectors of the objects. It's a fully elastic collision. This seems to work fine, and is rather convincing. However, it gets tough once degrees of freedom are lost (at the edge of the screen). My objects keep accelerating too long per frame (20 to 100 milliseconds), meaning they penetrate too deeply - and worse: their velocities do not converge at 0. Thus, the objects never really come to rest on top of each other. Instead, they chaotically jumble around in the corner. Now, I guess one step in the right direction would be to determine the precise point of impact for the objects. Currently, I just separate them if I detect an overlap (objects passing through each other at high velocities aren't an issue, as this is not noticeable on the tiny screen). However, there could be multiple impacts every frame. Acceleration data from the accelerometers would need to be broken up and integrated over small "fragments" of the time slice. Remaining degrees of freedom need to be propagated through chaotic stacks of potentially dozens of objects. I have no idea how to do that in a simple fashion. It's frustrating, because it seems like such a simple thing to do, but I just can't sort it out. In my search for a simple solution, I wrote a little hack that simulates a partially elastic collision (as opposed to a fully elastic "pool ball" collision) in case one of the objects hits another one that is currently touching a wall. This helps as long as the acceleration forces are sufficiently (read: quite) low. [Edited by - Thygrrr on August 9, 2008 7:11:52 PM]

Check out Nonconvex Rigid Bodies with Stacking. Even if you don't use their geometry representation, their simulation step is (IMHO) really, really great. It supports stacking reasonably well, and the situation you mentioned, colliding against a constrained object, works perfectly. Tell me if you decide to go with it and need help or sample code -- it's a rather difficult paper to follow in places.

I actually came across this paper on my searches on the topic before. I dismissed it, because my objects are convex. I will take a look at it, though, thanks!

One thing I didn't mention yet - my physics solver is for a 2D world. (though that doesn't really matter as much; but when cross products and other things are involved, adapting a 3D method to 2D may not be trivial anymore). I added it to the thread topic for good measure.

Actually, implementing that paper will most likely be easier in 2D than 3D. Also, adapting 3D physics to 2D is trivial: simply treat the result of the cross product as a scalar, and you'll find that everything works out.

Really? It always felt fishy to me when I did that. Anyway :-)

I took some of the ideas they used in the paper. And I realized that somehow, I broke my collision response code way back. Complete and utter bollocks, and whatever I did to it, I couldn't find out what went wrong.

I reimplemented collisions with support for a coefficient of restitution, and that alone fixed a crapload of problems (at least at high frame rates). Seriously, I wonder why my previous code did work convincingly at one point - it was (nearly) complete bollocks. This new code I built from scratch using some formulae from an old physics book even uses one square root less, and supports restitution coefficients, which I really needed.

For my prototype app, this will do; and I'll work on using their shock propagation ideas that cover the "rattling down" of items to zero speed/zero restitution. Combined with my degree of freedom system (and some minor extensions), I think I will now be able to reliably ignore acceleration for objects lying on top of other objects that are already restricted in one or two degrees of freedom.

There is probably no way I can build an arbitrary graph and perform some magick on it, though. Maybe if I pre-allocate some kind of buffer to do it in; however, this is Java, so my possibilities there are limited. Instantiating arbitrary amounts of new objects will open a huge can of worms later when porting this to memory constrained low-end devices.

Also, I find their description of the algorithm extremely vague; and maybe I missed it, but what kind of integrator are they using? An RK method?

Quote:Original post by Thygrrr
There is probably no way I can build an arbitrary graph and perform some magick on it, though. Maybe if I pre-allocate some kind of buffer to do it in; however, this is Java, so my possibilities there are limited. Instantiating arbitrary amounts of new objects will open a huge can of worms later when porting this to memory constrained low-end devices.

I'm not sure what you're talking about here. Building the contact graph? Easy to do in-place; just put the required bookkeeping fields in the rigid body class.

Quote:Also, I find their description of the algorithm extremely vague; and maybe I missed it, but what kind of integrator are they using? An RK method?

Euler. Because there's no penalty forces, there's no need for more complicated integrators.

Quote:I'm not sure what you're talking about here. Building the contact graph? Easy to do in-place; just put the required bookkeeping fields in the rigid body class.

Maybe I don't get it at all, then. Their circular dominoes example completely confuses me, to be honest. I'll go back to studying the paper...

If I keep an array or Vector with all the potential edges to other bodies in each body... is that what you mean by "bookkeeping fields"?