Integration methods

[aqnuep]

Hi,

I need to have the physics integration in a way that it should work efficiently and well with both networking and it variable rendering frame rates. This introduces a few problems:

1. If I use simulation intervals based on frame rendering time, then in case of a networking environment the clients won't have exactly the same results for physics because of numerical errors (as far as I know Newton does not guarantee exact same results if simulation times are different on the two clients).
2. If I use fixed simulation intervals it is quite expensive to interpolate the previous and current results to be able to have variable frame rendering times (as I know somebody from this forum already implemented this kind of interpolated physics results).

A few other physics libraries, like e.g. Bullet solves this problem by having a fixed internal simulation time of 60Hz and based on whether the simulation time requested from the application, if it is large enough then Bullet internally advances one (or in some cases even more) iterations with the solver and if it is small enough then Bullet does not advance at all. However the matrix callback always sends back interpolated values based on the simulation time requested even if the internal simulation time is always 16.67ms.

Does anybody know how to achieve the same with Newton? Have somebody implemented fixed physics updates with variable render times efficiently?
And actually am I right that Newton is only consistent between network clients if all clients use the same simulation period?

[Julio Jerez]

I did not kwno tha was some kind of extraordinaty technology, but who am I to say.
I do not do any of that stuff in the engine side, I prefer the client application to implement that kind of inteplation at the see fix.

All of the the wiki tutorials demos for 2.0 run phsyics at a fix fps and do smoothing key frame interpolation here is the getting started
http://newtondynamics.com/wiki/index.php5?title=Tutorial_101:_-_Getting_Started

basically all it need ot one key frame memory, in your visual object and add a couple fo function to do the interpolation.
I did not see what the difficulty that it needed to be part of the engine, and I do no thonk it is that expensive since it is just one interplations.
plus I beleive every end application does it in way or another.

[aqnuep]

Of course, I understand why it is not in Newton itself.
I already knew how to do the basic interpolation stuff, I have problems only because I have separate threads for graphics and physics and that way I think the solution is not that straightforward.
Now I'm planning how to do the integration of physics and graphics threads. Currently I ended up with the following solution:

1. PhysicsThread - Call NewtonUpdate, results are stored in a diff buffer (containing only the changes, based on matrix callback).
2. PhysicsThread - Send integrate message to GraphicsThread.
3. GraphicsThread - Copy next buffer (containing 1 simulation earlier results) to prev buffer (containing 2 simulations earlier results).
4. GraphicsThread - Apply diff buffer to the next buffer (copy only the changed values).
5. GraphicsThread - Send integrate complete message to PhysicsThread.
6. GraphicsThread - Interpolate next buffer and prev buffer and copy the results to the OpenGL uniform back buffer.
7. GraphicsThread - Switch uniform back and front buffer.
8. GraphicsThread - Draw scene using uniform front buffer.

This seems to be a very efficient method, however, I have concerns about step 3 and 6.
First, step 3 involves the copying of quite large amount of data but it is needed because if we just switch the prev buffer with the next buffer then the new next buffer won't contain the results of the previous integration so the new integration will result in invalid data. An alternative would be to store the diff buffer from the previous integration, just use switch instead of copy and then apply both diff buffers (probably usually this would be more efficient).
Second, step 6 involves again large number of interpolations and again, it is not enough to update only the differences because there is double buffering also on graphics side when dealing with the uniform buffers to prevent sync issues between CPU and GPU. It is possible to keep track of "dirty" objects (which moved in the last simulation step) and interpolate only those, also, interpolation can be done in vertex shader, but that's a waste of GPU power.
If I would have the same time interval for simulation and rendering then it would be much simpler as I can directly update the uniform back buffer in the matrix callback and then just copy the uniform back buffer data to the uniform front buffer data with a fast GPU copy.

Maybe I've overcomplicated something but for now this seems the only viable solution.
Have anybody of you managed to solve this kind of problem or at least have a better idea?

[aqnuep]

I was thinking... a lot
Maybe there is a better solution, however I have one question which strongly influences whether the new solution is better or not.
The matrix callbacks are called after the solver done it's job so it uses only a small period of time or it is called by the solver on-the-fly?
If I can lock the destination buffer during the period when all the matrix callbacks are called then there would be a better solution, but if the calls are spread during the constraint solving then it would lock the resources for too long.
How is this thing working inside Newton?

[Julio Jerez]

updat matrix is call after update yes.

you can ignore matrix update and iterate over the bodies list after the call back to update your double buffer of rotation and position

[aqnuep]

OK, thanks. Based on this I'll polish my new idea and I'll post it here because it will possibly be useful for others as well.

[aqnuep]

Almost found a very efficient method to do the whole stuff, just one thing messes up the double buffering of the uniform buffers:

Can I determine with a Newton callback if a body was previously moving but now it's in equilibrum?
More precisely, is there a Newton callback which will called in the current NewtonUpdate for those object which had a matrix callback in the previous NewtonUpdate but had no such callback in the current NewtonUpdate, due to their reached the state of equilibrum?

In pre-2.0 version of Newton there was a callback NewtonBodySetAutoactiveCallback which was called if the body state changed from moving to equilibrum of vice-versa.
Is there something similar in Newton 2.0 which I can use for this purpose?

[aqnuep]

Never mind! I've found a workaround. Now it seems that I've found the most efficient method for integration when the following conditions apply:
- the rendering frame rate is not the same as simulation rate
- object matrices are stored in uniform buffers
- physics and graphics is done in separate threads

It would be too complicated to explain it, so I'd better post some pseudo-code:

Code: Select all

---- PHYSICS THREAD ------------------------------------------------------

// physics simulation step counter
curr_physics_step = 0
// time when last NewtonUpdate finished
last_update_time = 0

// moving objects in the current simulation step
curr_dirty_list = ()
// moving objects in the previous simulation step
prev_dirty_list = ()

function matrix_callback( body, new_matrix )
  // keep track of previous and next matrix
  body.prev_matrix = body.next_matrix
  body.next_matrix = new_matrix
  // keep track of when it was last modified
  body.last_physics_update = curr_physics_step
  curr_dirty_list.add( body )
endfunction

thread physics_processor
  forever
    curr_physics_step = curr_physics_step + 1
    prev_dirty_list = curr_dirty_list
    NewtonUpdate( PHYS_UPDATE_FREQ )
    last_update_time = current_time()
    foreach body in prev_dirty_list
      if body.last_update = curr_physics_step - 1 then
        // handle bodies that just got in equilibrum
        // - no more need for previous matrix
        // - it's still dirty as it just finished it's movement
        body.prev_matrix = body.next_matrix
        curr_dirty_list.add( body )
      endif
    endforeach
    synchronize with graphics_processor
      send curr_dirty_list, last_update_time
    endsynchronize
  endforever
endthread

---- GRAPHICS THREAD -----------------------------------------------------

// frame rendering counter
curr_graphics_step = 0

// moving objects in the current simulation step
dirty_list = ()
// time when last NewtonUpdate finished
update_time = 0

thread graphics_processor
  forever
    curr_graphics_step = curr_graphics_step + 1
    synchronize with physics_processor
      if received new_dirty_list, last_update_time
        dirty_list = new_dirty_list
        update_time = last_update_time
      endif
    endsynchronize
    foreach body in dirty_list
      // LERP the matrices of moving objects
      alpha = ( current_time() - update_time ) / PHYS_UPDATE_FREQ
      matrix = body.prev_matrix * ( 1 - alpha ) + body.next_matrix * alpha
      body.last_graphics_update = curr_graphics_step
      // update the back uniform buffer with interpolated matrix
      body.back_UBO.update( matrix )
      // make sure the front and back uniform buffers will be flipped before usage
      body.flip_UBOs = true
    endforeach
    DrawScene()
  endforever
endthread

I hope you'll understand it and find it useful.

Of course, there is room for optimizations like the following:
- use shared memory for the dirty lists to minimize copied data
- use triple-buffering for uniform buffers to further prevent sync issues between CPU and GPU

If you have questions then don't be afraid to ask

[kane7777]

Hi aqnuep,

I am also trying to implement Physics for networking (using RakNet). I have implemented in it my game but how no idea to get the same results for two clients which have different frame rates. Can you please guide me step by step on how to go about achieving this?
Many thanks in advance!

[JernejL]

you can run physics at a fixed step and interpolate graphics rendering positions.