Separate physics thread without locks

Question

I have a classic physics-thread vs. graphics-thread problem:

Say I'm running one thread for the physics update and one thread for rendering.

In the physics thread (pseudo-code):

while(true)
{
  foreach object in simulation

     SomeComplicatedPhysicsIntegration( &object->modelviewmatrix);
     //modelviewmatrix is a vector of 16 floats (ie. a 4x4 matrix)
}

and in the graphics thread:

while(true)
{
  foreach object in simulation
    RenderObject(object->modelviewmatrix);
}

Now in theory this would not require locks, as one thread is only writing to the matrices and another is only reading, and I don't care about stale data so much.

The problem that updating the matrix is not an atomic operation and sometimes the graphics thread will read only partially updated matrices (ie. not all 16 floats have been copied, only part of them) which means part of the matrix is from one physics frame and part is from the previous frame, which in turn means the matrix is nolonger affine (ie. it's basically corrupted).

Is there any good method of preventing this without using locks? I read about a possible implementation using double buffering, but I cannot imagine a way that would work without syncing the threads.

Edit: I guess what I'd really like to use is some sort of triple buffering like they use on graphic displays.. anyone know of a good presentation of the triple buffering algorithm?

Edit 2: Indeed using non-synced triple buffering is not a good ideea (as suggested in the answers below). The physics thread can run mutiple cycles eating a lot of CPU and stalling the graphics thread, computing frames that never even get rendered in the end.

I have opted for a simple double-buffered algorithm with a single lock, where the physics thread only computes as much as 1 frame in advance of the graphics thread before swapping buffers. Something like this:

Physics:

while(true)
{
  foreach physicstimestep
   foreach object in simulation    
      SomeComplicatedPhysicsIntegration( &object->modelviewmatrix.WriteBuffer);
  LockSemaphore()
  SwapBuffers()
  UnlockSemaphore()
}

Graphics:

 while(true)
    {
     LockSemaphore()
      foreach object in simulation
        RenderObject(object->modelviewmatrix.ReadBuffer);
     UnlockSemaphore()
    }

How does that sound?

Answer 1

You could maintain a shared queue between the two threads, and implement the physics thread such that it only adds a matrix to the queue after it has fully populated all of the values in that matrix. This assumes that the physics thread allocates a new matrix on each iteration (or more specifically that the matrices are treated as read-only once they are placed in the queue).

So any time your graphics thread pulls a matrix out of the queue, it is guaranteed to be fully populated and a valid representation of the simulation state at the time at which the matrix was generated.

Note that the graphics thread will need to be able to handle cases in which the queue is empty for one or more iterations, and that it would probably be a good idea to world-timestamp each queue entry so that you have a mechanism of keeping the two threads reasonably in sync without using any formal synchronization techniques (for instance, by not allowing the graphics thread to consume any matrices that have a timestamp that is in the future, and by allowing it to skip ahead in the queue if the next matrix is from too far in the past). Also note that whatever queue you use must be implemented such that it will not explode if the physics thread tries to add something at the same time that the graphics thread is removing something.

Answer 2

but I cannot imagine a way that would work without syncing the threads.

No matter what kind of scheme you are using, synchronizing the threads is an absolute essential here. Without synchronization you run the risk that your physics thread will race far ahead of the graphics thread, or vice versa. Your program, typically a master thread that advances time, needs to be in control of thread operations, not the threading mechanism.

Double buffering is one scheme that lets your physics and graphics threads run in parallel (for example, you have a multi-CPU or multi-core machine). The physics thread operates on one buffer while the graphics thread operates on the other. Note that this induces a lag in the graphics, which may or may not be an issue.

Answer 3

The basic gist behind double buffering is that you duplicate your data to be rendered on screen.

If you run with some sort of locking, then your simulation thread will always be rendering exactly one frame ahead of the display thread. Every piece of data that gets simulated gets rendered. (The synchronization doesn't have to be very heavy: a simple condition variable can frequently be updated and wake the rendering thread pretty cheaply.)

If you run without synchronization, your simulation thread might simulate events that never get rendered, if the rendering thread cannot keep up. If you include a monotonically increasing generation number in your data (update it after each complete simulation cycle), then your rendering thread can simply busy-wait on the two generation numbers (one for each buffer of data).

Once one (or both) of the generation numbers is greater than the most-recently-rendered generation, copy the newest buffer into the rendering thread, update the most-recently-rendered counter, and start rendering. When it's done, return to busy waiting.

If your rendering thread is too fast, you may chew through a lot of processor in that busy wait. So this only makes sense if you expect to periodically skip rendering some data and almost never need to wait for more simulation.

Answer 4

Don't update the matrix in the physics thread?

Take a chunk, (perhaps a row you have just rendered), and queue its position/size/whatever to the physics thread. Invert/transpose/whateverCleverMatrixStuff the row of modelviewmatrix's into another, new row. Post it back to the render thread. Copy the new row in at some suitable time in your rendering. Perhaps you do not need to copy it in - maybe you can just swap out an 'old' vector for the new one and free the old one?

Is this possible, or is the structure/manipulation of your matrices/whatever too complex for this?

All kinda depends on the structure of your data, so this solution may well be inappropriate/impossible.

Rgds, Martin