# Physics engine order

This topic is 4175 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, this week I'm going to try my hand at my first physics engine! First of all can any of you give me advice or important points? and my main question, in my engine I'll have 5 main parts: force calculation, collision detection, collision response, integration, rendering. Is that the correct order? If not what order should I do them in? Thanks.

##### Share on other sites
A physics engine should not do rendering. Leave that to the rendering engine.

##### Share on other sites
I suggest you do some reading/research before even thinking about writing code. For example, Chris Hecker's pages, David Baraff's notes, this paper, etc etc.

##### Share on other sites
I looked at "this paper" and it was very interesting. I liked how it handeled collision detection. But there was something I didn't understand they say:
Quote:
 Instead, our algorithm uses a novel fixed-time integration scheme, where we allow for penetration between bodies inside a simulation step. A simple Euler integration scheme with time step 0.01s has shown to be sufficiently robust for all our tests. Our algorithm splits the collision and resting contact phases, where only the velocities are updated between both: Algorithm 1: Fixed-time integration scheme Collision detection and resolution. Update velocities. Resting contact resolution. Update positions. Update time. Basically, both stages 1 and 3 perform a collision resolution step, but the only difference between both is the coefficient of restitution used in the impulse computation. In the contact resolution phase, we model the collision as completely plastic (ε = 0).

what is the difference between Collision detection and resolution and Resting Contact resolution. Do I define some velocity threashhold that if the Colliding bodys are moving slower than it they are in "resting contact"? Or do I also have to define a minimum collision the below it turns into contact? And when do I do Contact detection - in the third step or in the first?
Thanks!

##### Share on other sites
At the risk of seeming not very helpful - it's all explained quite well in the paper...

However - bear in mind their implementation seems designed for non-real-time animation, and they seem to do multiple collision detections per time-step. For real-time simulation you can get away with just one (seems to work just as well anyway).

There's also some "notes" I made a while back here, though they may not be completely up to date with my implementation.

##### Share on other sites
MrRowl -- just checked out your demo. pretty awesome stuff.

##### Share on other sites
MrRowl, you're demo's and movies are incredible!!
Quote:
 The basic order of integration is this: -Get all forces acting on the bodies. -Integrate velocity using the forces. Use the new velocities integrate positions. Detect collisions (ideally a swept test from old positions to new ones... but I currently just do an overlap test with the new positions). -Restore positions and velocity to their original values. -Process (see below) all collisions and constraints using impulses, iterating a few times over the list. These impulses update the velocities, but not the positions, of course. -Integrate the velocities (again) using the forces. -Process all collisions and constraints using impulses again, except now treat all collisions as inelastic, iterating a few times over the list. -Do a "shock" step - see below. This allows objects to stack up even when the number of iterations in the previous steps is small. -Integrate the positions using the new velocities.

I can see how you'd do that with Euler integration but how do you implement that with RK4? how do you first do the velocity and then the postion?
Thanks.

##### Share on other sites
Quote:
 Original post by daniel_i_lI can see how you'd do that with Euler integration but how do you implement that with RK4?

Unfortunately, I don't have an answer to that. Wish I did...

##### Share on other sites
Is you're demo with Euler then? Maybe I should just do Euler and forget RK4?
Thanks.

##### Share on other sites
RK4 is good for springs.
I recommend velocity verlet.

##### Share on other sites
If they meant what I call SGDI, then they meant.

v = v0 + a
d = d0 + v

You first calculate acceleration, then from most current acceleration calculate speed, then from the most current speed calculate position. This order of operation IS important.

It's oversensitive, and symplectic. Oversensitive means it would tend to overshot a little thus making a simulation more sensitive, if you don't know what the second term means, don't worry.

I'm currently using a RK6, because it was deadly easy to implement. It's not all win to win, for simple movement of objects, SGDI is better because it's faster errors are more visible, and it's easier to apply some constraints.

##### Share on other sites
MrRowl: I'm thinking on trying to implement you're algorithm. Sofar I have one question: In the 4th and 6th step to you go through all of the collisions? In step 4 I looped through all the collisions 10 times and resolved them using impulse (the impulse equation in Chris Heckers collision article) with a constant of resolution 0.95. then I updated just the velocities and in step 6 I looped through all the collisions again 10 times and resolved them the same way as before just this time with a constant 0. I didn't do the "shock" yet.
Did I do it right? what do I do with contact cases?
When I did this it worked well when the bodies were going relativly quickly but then when they got to the floor they fell through. Is that because I didn't do the shock?
Thanks.

##### Share on other sites
Don't do the shock stuff - that's really just "emergency" code. Everything should be working 99% right before you turn that on (if you do at all).

It sounds like you're not applying the impulses immediately you calculate them. Don't accumulate the impulses...

It's very important to be absolutely sure your low-level code is working. Go through and with a simple box in no gravity apply impulses to it - initially through the centre of mass, then afterwards not through the CoM and check your code gives you the same results you get doing the calculations by hand.

Then when testing your collision stuff start with a single sphere dropping/resting on a plane since it just has one contact. Then box on a plane. Then sphere on a box... etc etc. start small. Check by hand the results of each stage - either in a debugger or dumping the values to a log file/console.

##### Share on other sites
Ok, i was checking the impulse code and found a (-) mistake. after fixing that the code worked perfectly for two rigid bodies on each other. To make the floor I just put a very massive rigid body and told it to be static. When the body gets to the floor it bounced up rotated instead of straight up, I think this is because the impulse on one corner was making the other corner get a bigger impulse. So then instead of updating the velocities right after calculating the impulse I added up all the changes in velocity (linear and rotational) in all the bodies and then after looping through the collision resolver 10 times I added the accululated velocities / 10 to the current ones. After this the bodies bounced straight up in the air and didn't sink into the floor!! The only problem is, even when the COR was e=1, the bodies only bounced up a little bit instead of returning to their original height. So my question is:
Could the fact that I applied all the impulses immediatly have been the reason that they sunk into the floor? Or is there another problem that I have to look for? And, why isn't bouncing all the way up after what I did?
Thanks a lot!

##### Share on other sites
Why do you want the box to bounce up without rotating? Bear in mind that your test case is extremely artificial - really you don't get perfect boxes colliding with a coefficient of restitution = 0.95 and perfectly aligned with the collision surface. I don't think you should add "hacks" to just try to make this artifical test case conform to some arbitrary idea of a solution... get everything working at 95% quality with hack-free code before even thinking about adding hacks to solve the remaining niggly little problems.

Having said that... it is nice to have no rotation in the inelastic case (used for resting contact). Here you can add an extra contact point (bear in mind that the idea of representing the contact as a set of points rather than a surface is rather artificial/arbitrary anyway). Where you choose that point is up to you - could be the geometrical centre of your contact points, or some weighted average. Anyway, if you process this extra point first then your collisions/contact will result in no rotation in the "perfect" case you're testing - and may behave better in other cases too. However, you then need to handle friction. I suggest you check out some old threads - look for posts by me, b34r, John Schultz and Billy Zelsnack and others - e.g. a good one is here but there's others too.

Hey - you realise you have to upload your demo somewhere now so we can all play :)

##### Share on other sites
Thanks a lot for all your help! I just want to clear something up that has been confusing me a little, do I treat all collisions (= collisions AND contacts) the same way - first calculating elasic collision and then inelastic, or do the contact points get a "special treatment"?
-I'd be thrilled if I get something stable enough to upload to other people!
Thanks!

##### Share on other sites
Read the Guendelman et al. paper (at least twice :). That is the cool thing about their scheme - you don't distinguish between collisions/contacts based on some arbitrary tolerance values.

Also, if it's still unclear, look at my source code. Actually the jiggle source code may be slightly clearer and simpler... I forget. Ideally implement stuff on your own before looking at other code though, else you'll end up with stuff in your code that you don't understand, and it will take away from the thrill of you playing with your demo and thinking to yourself "I did that - all of it!!" :)

##### Share on other sites
Thanks a lot for all your help, I think i understand the most of it now. I'll post here if any more questions come up.
Thanks!

##### Share on other sites
Ok, I took out the impulse stuff that I mentioned before and only did the following:
-get forces and update velocity and position
-get collisions
-undo last update
-resolve all collisions 20 times using constant of 0.8
-update velocity
-resolve all collisions 20 times with constant of 0.0
-update positions

This worked well but the bodies slowly(in about a minute) but surely sunk into the floor.
So then to fix that I pulled any objects that were still colliding apart and that fixed the sinking into the floor problem. Now I only see one problem left, when one block is ontop of the other one and the bottom one is on the floor the top one sometimes sinks into the bottom one. How do I fix that?
And other strange thing I noticed, if I run the same simulation multiole time, I don't get the same outcome every time! Sometimes they all of a sudden stop and then "come back to life" and when they do sometimes they're inside each other!
I thought it had do do with the framerate but I don't see how cause I'm doing this for the simulation:
(DeltaTime = framerate, TimeRate is constant)
void CSimulation::Update(vector<RigidBody> ¤ts, double DeltaTime){  double accumulator = 0.0f;  vector<RigidBody> previous;  previous = currents;  if(DeltaTime > 0.25)	  DeltaTime = 0.25;  accumulator += DeltaTime; if(DeltaTime>TimeStep) { while(accumulator>=TimeStep)  {	  accumulator -= TimeStep;	  previous = currents;	  Integrate(currents, TimeStep);  }  if(accumulator!=0)   currents = Interpolate(previous, currents, accumulator/TimeStep); } else  Integrate(currents, DeltaTime);}

so I should get the same resaults regardless of the frame rate? I think it might be because of the "else" in the end were I just use the DeltaTime no matter what if it's smaller than the TimeStep (for me it is cause DeltaTime is about 0.005, and TimeStep is 0.02) but what else should I do?

Thanks.

##### Share on other sites
State of art engines are doing.
Get forces. Estimate collisions A PRIORY.

Sinkable floor, and fall through the geometry are common problems of some companies (like Bethesda).
The first is easily remedied by testing if object is ABOVE plane. The second is remedied by 1. making it correctly, 2. double layering (it's interesting for simulation of a grass, so it's nifty to use it even with 1.) 3. Use rule system, not completely slavishly copied textbook/paper from some scientists that never programmed.

BTW when you adjust position of the object sinking into the floor, what would happen?

##### Share on other sites
Hi guys, great tips :)

I just want to focus on one side issue that was mentioned earlier. It is possible writing the physics engine using a separate thread and it is also possible writing the physics engine as part of the game loop.

It seems to me that a physics thread is better in terms of separation from rendering and the general loop, but will incurr synchronization problems.

How does commercial engines work ? Can anyone shed some light or give other pointers regarding this ?