Extrapolation

Sorry, no new binary release. The last one can be found here.Sorry, no new source release. The last one can be found here.

fast_fps

Since we have a triple renderstate, a big advantage is that I always have two renderstates that may be read by the renderer without having to worry that the data is being updated. During the discussion with Bourgond Aries, I made a couple of workflow-sketches that uses a separate extrapolation-thread (see image on the right). We do not require access to the some physics state or keep track of motion vectors to extrapolate (or interpolate) from, we can just use information from the other renderstate that is currently being left alone.

I'm still not sure whether it is a good idea to have a separate extrapolation thread, because it runs at the same speed as the render-thread and usually API calls to DirectX (and OpenGL) are non-blocking. For this reason I'm not adding this, but who knows, maybe later. Still, it is a good time to get a decent implementation going for extrapolation. My current implementation is just not awesome enough, so let's see what we need to accomplish here.

Goals

goalsslow_fpsEven though the renderer has access to an additional render-state, which can be used for extrapolation, the update-thread is continually busy updating and is doing pointer switches during our rendering process. So even though we have a state that is safe to read from, this safe-state may change during extrapolation. It is very unlikely that this will happen, but if it happens we might get one frame with wrong extrapolation results (e.g. from a 4x4 matrix that has been partially written to). This is not something negligible because partially updated data may result in very weird rendering results.

Even though we're not going to create a separate extrapolation-thread, it would be nice to keep that option open without having to change anything in the engine's API. The extrapolation process should work for both extrapolation and interpolation, which might happen with a slow FPS (see image on the right). The workflow shows the exact same design as the one above, but values and pointers are modified to show the effects in case the game is rendering at a low FPS.

Implementation

The implementation is relatively simple. Since it's so unlikely that the update-thread is modifying the state that we are currently using for extrapolation, we'll just redo the calculation if there was a pointer-switch during the extrapolation calculation. Since it is difficult to mentally visualize multithreaded access, I've created an animation that hopefully clears things up. It is best to watch it fullscreen at 1080p, because some text's are a bit small (there was a lot I wanted to display :) )

You can also download the video here. This allows you to step through frames at any desired speed. In VLC the default key-binding for next-frame is 'e'.

Keep in mind that I made some liberties in the pseudo-code to make it easier to understand. The two most important differences between the pseudo-code and the real world are:

  • Nearly all operations for the video-card API are non blocking, so instead of waiting for the cube to get drawn on the CPU, it just queues this work for the video-card. When the information on the buffer is really needed (just before the actual flip is done probably), it makes sure to have finished all the jobs in the queue. This is done to make better use of multithreading on the GPU.
  • The renderer just blindly assumes that the update thread is running at 60 IPS. When the update thread is actually running slower than the desired IPS, we want to use the actual update IPS in our calculations.

Another fun thing to notice is that it is possible that extrapStep can actually become negative at times (where it basically becomes interpolation). The actual implementation is a little bit more difficult because we are using a tree and we are constantly adding and removing nodes. However, we already talked about how to tackle that issue in "Multithreaded renderloop - Part 2", so we won't repeat it here.

No source? Where is the download?

Nope, still nothing to download. Be patient, after the review/refactoring period is over a brand new v2.7.2.0.0 will appear! Super Secret Pinky Promise!

Multithreaded Game EngineResource Manager v2

  1. Redee says:

    Very powerful thing.
    But need some time to understand....

  2. Redee says:

    Available any sources to better understand.
    Ok main theory its a lot info too.
    Sry for bad english ).

  3. Jan says:

    Your tripple-state implementation works great when using extrapolation to smooth out rendering.

    However, extrapolation introduces some rather annoying rendering artifacts when suddenly shifting direction and similar abrupt changes in the position/direction of the object.
    Interpolation would smooth out this transition, however, where extrapolation only requires knowledge of one state and the velocities to predict any future step, interpolation requires 2 known states. You do say that your tripple state engine does supply 2 states ready for use by the renderer, but that is not really true, is it? I agree that at any given time, the updater will be updating in one queue, and the other queues will be be available for use by the renderer. However, as soon as the renderer grabs hold of the remaining 2 queues, the updater can no longer switch to a new queue after updating.

    So interpolation does not seem to be an option with the currently described engine. Or am I missing something?

    • eierkoek eierkoek says:

      The renderer always has access to one base-state. That is the state that is guaranteed not to change during the whole rendering process, the state that was the most recently updated when rendering began.

      There 'is' a second state that is currently not being touched by the updater, but which state that exactly is might change during rendering. And that second state may either lay in the past of our base-state (in which case it is extrapolation we use) or the state may lay in the future (in which case it is interpolation which should be used).

      Whether we should be using interpolation or extrapolation is not a big deal, since the math for both are the same. The changing of our second state however is a problem that we need to account for.

      The strategy for the renderer here is to just keep using the state that is not in use by the updater, assuming everything is fine. After extrapolation/interpolation is done we can simply do a stateId-comparison check to see if the updater has switched to the state we are currently using for 'polation. If indeed the updater has switched states, we assume that our 'polation failed (because the updater might have changed things) and we will redo the 'polation of the node in our render-tree. This is done by the "if (!extrapSuccessful)" in the video.

      Hope this explanation helps!

  4. http://www./ says:

    It's good to see someone thinking it through.

line