Posts RSS Comments RSS Del.icio.us Digg Technorati Blinklist Furl reddit 63 Posts and Comments till now
This wordpress theme is downloaded from wordpress themes website.

Archive for November, 2013 (2013/11)

SDL 2 on a real device (Android)

Assuming you already have Android SDK & NDK with Eclipse working on a virtual Android device, the setup directions to do it on a real device was pretty simple.  Here’s links and a photo of my Nexus 7 (Android 4.3) running my hello world SDL 2 OpenGL ES app:
http://developer.android.com/tools/device.html -> http://developer.android.com/tools/extras/oem-usb.html
For Nexus 7, I just did Device manager -> driver -> C:\Programs\adt-bundle-windows-x86_64-20130917\sdk\extras\google\usb_driver
image

I also wanted to try mirroring to my Windows computer.  I tried MirrorOp but it did not work (because it requires ROOT).  I tried DroidAtScreen (uses USB, does not require ROOT).  You just have to set the path via ADB –> ADB Executable Path, or via environment variables (ANDROID_HOME or ANDROID_SDK_HOME) (for me it was C:\Programs\adt-bundle-windows-x86_64-20130917\sdk\platform-tools\adb.exe).  I faced some very strange quirk.  For some reason, setting environment variables (ANDROID_HOME or ANDROID_SDK_HOME) did not work, and pasting the adb.exe path directly did not work.  What did seem to work was to click the “…” (browse) button and selecting adb.exe via the GUI.
image image

Once I got it to work, the USB mirroring with DroidAtScreen was functional and very cool.  Although it was also very choppy (I got like 1 fps).  DroidAtScreen does not have an interface to input, so I just made sure my Nexus 7 was easily accessible from my desk (the USB cable that comes with the Nexus 7 is short, so I used my LCD monitor’s built-in USB 3.0 hub, Dell U2713HM).
image

I also tried my very old Android phone (Motorola Droid Pro Verizon) (very old Android 2.3.4) with my hello world SDL 2 OpenGL ES C++ NDK app and DroitAtScreen.  This also works – here’s a DroitAtScreen screenshot:
image

Cross-platform SDL 2: try Kindle Fire emulator, misc Android emulator usage

Amazon Kindle HD & HDX runs a fork of Android called Fire OS, so there are some additional steps to add it to the Android emulator.  The first step is to setup the Android NDK for Android (non-Kindle) usage.  After that, there are some additional steps to setup for Kindle Fire device emulation.  This takes a little time, but it’s simple if you follow the directions:
https://developer.amazon.com/sdk/fire/setup.html#InstallingKindleFire
https://developer.amazon.com/sdk/fire/emulator-guide.html
https://developer.amazon.com/sdk/fire/avd-launcher.html

Once I got it setup, I was surprised at how long it took the Kindle Fire emulator to boot the OS.  It took more than 5 minutes to boot HDX 7, and more than 15 minutes before I was able to interact with it and see my hello world SDL OpenGL app run.  Even then, it was sluggish and choppy.  My other Android emulator devices did not have this problem.  Possibly part of the problem is the screen resolution.

image image image

I noticed this error:
emulator: ERROR: Could not load OpenGLES emulation library: Could not load DLL!
emulator: WARNING: Could not initialize OpenglES emulation, using software renderer.
I found the fix for that here:
http://stackoverflow.com/questions/11567574/what-graphic-cards-do-android-emulator-gpu-emulation-support
Which just said to add to my PATH, C:\Programs\adt-bundle-windows-x86_64-20130917\sdk\tools\lib\, which contains libOpenglRender.dll

I also got this error:
emulator: Failed to open the HAX device!
HAX is not working and emulator runs in emulation mode
emulator: Open HAX device failed
I found the fix for that here:
http://stackoverflow.com/questions/10761696/running-the-new-intel-emulator-for-android
Which just said to download the add-on via Android SDK Manager, then run C:\Programs\adt-bundle-windows-x86_64-20130917\sdk\extras\intel\Hardware_Accelerated_Execution_Manager –> IntelHaxm.exe.  Unfortunately, I still got this error:
image
I think it means the feature requires an Intel CPU with “support for VT-x, EM64T, and Execute Disable (XD) Bit functionality”
http://stackoverflow.com/questions/9823216/virtual-machine-acceleration-for-android-emulator

I found this alternative post about improving performance:
http://stackoverflow.com/questions/1554099/slow-android-emulator?rq=1
This post suggests to use the snapshot feature.  However, you have to pick either snapshot or use host GPU (not both).  So here are two options:
A) use snapshot feature without host GPU => this makes the emulator load faster (instead of having to boot)
B) boot the emulator once with use host GPU, and leave it open
image

image

Cross-platform SDL 2 game loop time steps, RK4 integration

Summary

Separate game updates from rendering – use a fixed timestep for game updates.  This can cause a spiral of death if you run on a slow computer, so here are some ways to deal with this.  You can use a small physics timestep.  Or you can dynamically make your timestep bigger (when the host is slows down), but then your simulation is no longer deterministic in terms of floating point calculations (if you wanted to do a replay, you can record when the timestep size changes).  Or you can allow your simulation to slow down (ie be slower than real-time).

For physics integration you can use Euler integration if you have a constant velocity or a constant acceleration.  If you timestep with (pos += v*dt + 0.5*a*dt*dt) then that is accurate as long as (v, a) are constant over the timestep.  If you have a non-constant acceleration (possibly from non-constant force vectors), then you either need a better physics equation (for Euler integration) with variables that are constant over the timestep, or you can approximate by integrating with RK4 (or RK2, Verlet, etc).

When using a constant time step, you end up with a fraction.  Suppose you just calculated current state for update 10, but your time is at update 10.3  You can just use current state (from update 10) but then you get temporal aliasing (jumping between update 10 and update 11).  Or you can extrapolate current + prediction (you can use a low computation cost prediction such as constant velocity), but you may see some jumping due to incorrect prediction.  Or you can interpolate between current and previous, based on one physics update in the past (so you’d have a latency of one physics step).

Visual effects (like particles) that do not affect game logic do not need a fixed time step, and do not need interpolation (or extrapolation).  This is assuming you don’t need your visual effects (like particles) to be deterministic or consistent.  Depending on how fast the host computer is, you could make your visual effects run more often (or less often).  However, you’d never need to simulate a visual effect (eg particles) more than once per render frame.

The rest of this post is verbose (not concise) rambling notes.  What happened was I often take notes when I’m reading (or thinking).  These particular notes I took reading about game loops (and RK4 integration), but they got disorganized.  I may (or may not) tweak these notes.

Game Loop time step

I did some code cleanup to decouple from SDLTest, to start with a minimal amount of code, and to organize the code for some small cross-platform demos.

I made a game loop based on this article – http://gafferongames.com/game-physics/fix-your-timestep/ .  It’s a good article and well-explained, going from simpler to more complex.  Here’s my simple game loop for the “Free the physics” part using an SDL timer (I removed my comments to make it shorter):

   1: while (!g_bDone)

   2: {

   3:     while (SDL_PollEvent(&event))

   4:     {

   5:         HandleSdlEvent(event);

   6:     }

   7:     newTime = SDL_GetTicks();

   8:     frameTime = newTime - currentTime;

   9:     const Uint32 maxFrameTime = 1000; // 1 sec per frame is the slowest we allow

  10:     if( frameTime > maxFrameTime)

  11:         frameTime = maxFrameTime;

  12:     currentTime = newTime;

  13:     accumulator += frameTime;

  14:     while( accumulator >= dTime )

  15:     {

  16:         Simulate(dTime); // simulate a "frame" of logic at a different FPS than we simulate a frame of rendering

  17:         accumulator -= dTime;

  18:         time += dTime;

  20:     Render();
  19:     }

  21:     SDL_GL_SwapWindow(g_state->windows[0]);

  22: }

The article’s example time() uses QueryPerformanceCounter() for Windows and Microseconds() for Apple.  I wrote a version using SDL_GetTicks().  SDL_GetTicks() is an integer of ms, while time() returns a float in seconds.

If we get a frameTime bigger than maxFrameTime, then the simulation slows down.  An alternative is to reduce the size of dTime, but then the simulation would not be deterministic – we’d be doing different calculations in terms of floating point rounding.  In general, the ability to reduce the size of a timestep (dTime) would allow you to run on a slower computer.

Game Loop interpolation vs. extrapolation (prediction)

Here’s another article ( http://www.koonsolo.com/news/dewitters-gameloop/ ) that focuses more on the graphics frame rate and less on physics (ie no details about RK4 integration, or dealing with non-constant acceleration).

Like the previous article, this article advises to do “Constant Game Speed independent of Variable FPS”.  Both articles also advise using interpolation: game code runs on it’s own frames per second, so when you draw/render your frames, it is possible that it’s in between 2 gameticks. Let’s say you have just updated your gamestate for the 10Th time, and now you are going to render the scene. This render will be in between the 10Th and 11Th game update. So it is possible that the render is at about 10.3.

koonsolo.com article predicts (extrapolates) into the future.  He does this by using a constant speed between physics updates (ie between update 10.0 and 10.3).  So we do a full physics update for 9 and 10 and 11.  But for 10.3, we do current (10) + a low-computation-cost prediction.  This low-computation-cost prediction is to just assume a constant velocity.  Then when we get to physics update 11, we’ll do the full (more expensive) update.

gafferongames.com article interpolates between previous state and current state.  This means his rendering is one physics step behind.  The advantage is that this method of interpolation is accurate (does not risk doing an incorrect prediction).  Author Comment: the reason i interpolate previous two frames is to always be accurate, you could extrapolate from the current frame if you want, but this causes discontinuities if the velocity changes abruptly (eg. a bounce…).  Author Comment: interpolating between the previous frame and the current – effectively adding one frame of latency.  Author comment: you can interpolate, you can extrapolate — if you interpolate you’ll add *up to* one frame of latency depending on how much accumulator you have left. the alternative is to extrapolate forward networking style and trade latency for misprediction.

The extrapolation (prediction) method of interpolation is more needed for network games, where you have a bigger delay (possible packet loss).  I remember doing this “dead reckoning” prediction for Super IsoBomb networking back in college ( http://www.mepem.com/resume_RIT_pre-SimNow/IsoBomb/IsoResearch.html ).

Comment: You are correct in that the velocity does not need to be interpolated. The code interpolates the entire physics state for the object but in fact the only interpolated quantity which is actually used is the position.

In summary three choices for what position to render:
A) current => just display the latest (bad – causes temporal aliasing)
B) interpolate current and previous => you get an accurate value between current and previous with one frame of latency (eg for 10.3 we use 9.3)
C) extrapolation: current + interpolate a low-computation-cost prediction (for example, use a constant velocity)

Game Logic Physics vs. Visual Effects

Comment: I’ve implemented interpolation for my physics engine, but I was wondering if I could circumvent the interpolation step for my particle emitter. Looping through hundreds of particles to interpolate seems unnecessary because a variable timestep for particles is efficient.  I was thinking about adding an additional update call before the interpolation, and passing in accumulator, which updates my particles.

Author: Yes that is a good plan. For particles and other visual effects it is typical to not fix time step for those, interpolation and the double copy of state is a waste

Game Loop limit FPS

Summary from koonsolo.com:
* A constant frame rate can be a good and simple solution for mobile devices
* but when you want to get everything the hardware has got, best use a game loop where the FPS is completely independent of the game speed, using a prediction function for high framerates
* If you don’t want to bother with a prediction function, you can work with a maximum frame rate, but finding the right game update rate for both slow and fast hardware can be tricky

Another tweak to the above game loop would be to cap the graphics frame rate (such as by the monitor refresh rate).  As described here ( http://stackoverflow.com/questions/3102888/game-development-how-to-limit-fps ).  For example, if the number of microseconds per frame is 1000000 / frames_per_second, then before rendering you could sleep for (1000000 / frames_per_second) – elapsed_microseconds.

Game Loop with RK4 for Physics, overview

At first I didn’t completely understand the RK4 (Runge-Kutta order 4 integrator) parts, but then I noticed the time step article author had a previous article explaining RK4, http://gafferongames.com/game-physics/integration-basics/ .  If the physics side of our simulation only uses constant velocities to affect position, then Euler integration is accurate.  However, in certain more complex scenarios Euler integration is not accurate (or even fails horribly), so we need a more accurate (but not perfect) method such as RK4.  Here’s my notes on the RK4 article:

Numerical integration, Euler integration (note p & v & f are vectors such as 3D with x y z components) (constant force & mass => constant acceleration):
p = p + v*dt;
v = v + (f/m)*dt; // f=ma, a=f/m, so we use f/m instead of directly specifying a

Euler integration as done above is only accurate if the rate of change is constant over the timestep.  It’s accurate to integrate position over time with a constant velocity.  it’s accurate to integrate velocity over time with a constant acceleration.  But as shown above, Euler is not accurate when we integrate position over time with non-constant velocity (if we have a constant acceleration, then our velocity is non-constant).

Aside: the article’s example above is artificial.  For constant acceleration, Euler is accurate if you add 0.5*a*t*t, see “Constant Acceleration” section below.

For non-constant acceleration, RK4 is not perfectly accurate, but it’s more accurate than Euler integration.  RK4 works by evaluating (sampling) the derivatives at four points in the timestep, then it combines these samples with a weighted average.

Game Loop with RK4 for Physics, detail

The article’s example defines object state (position, velocity) and its derivative (derivative of position = velocity, derivative of velocity = acceleration).

evaluate() advances physics state one time step (t + dt) by doing a Euler Integration step (with input derivatives p, v).  Then it uses that integrated state to calculate output derivatives (p, v) using this new state.  To calculate output dv, it uses acceleration().  evaluate()’s only return value is the output derivatives (it does not return the integrated state).

acceleration() – the article’s example is spring and damper force assuming unit mass (Hooke’s law).  The implementation depends on what you want to simulate.  You might calculate a force here, and rename the function as force().

integrate() does RK4 integration for t to t+dt.  It evaluate()’s four sample derivatives.  Each evaluate takes the same value for (state, t) but different value sfor (time, derivative).  a uses (0, 0); b uses (dt*0.5, a); c uses (dt*0.5, b); d uses (dt, c).  Then integrate() takes a weighted sum (a + 2*(b+c) + d)/6 (“comes from the Taylor Series expansion”).  Then integrate() uses that weighted sum to advance state (p, v) over timestep dt.

Game Loop with RK4 for Physics, summary & notes from comments section

For constant velocity or constant acceleration, Euler Integration is fine (so RK4 is not needed).  Author comment: well if the car physics has constant acceleration it would be OK, but if the acceleration was non-constant (eg. changing gears, or changing the weight on the accelerator), then RK4 will give you less error than euler.  That’s really the point of this article, as per the best integrator for a simple constant acceleration situation, try this one: s = ut + 1/2at^2 it’s an exact solution

For anything beyond that (such as non-constant acceleration, force, momentum), one option is RK4.  RK4 can be used for single values, vectors, or even quaternions and matrices for rotational dynamics.  The article’s RK4 code can easily be modified to use 3d vectors, and to customize the acceleration() function.  A further example would be to switch from integrating velocity directly from acceleration(), and instead integrate momentum from force().

Comment: For multiple bodies with RK4, you integrate both bodies together, ideally you have a single method that returns an array of forces to apply to the points — you cant update each body independently with RK4.

Comment: Don’t disparage Verlet methods – RK4 is accurate enough for game simulations, but unfortunately does not conserve energy over long periods of time (which doesn’t really matter for game physics, but does if you want to do real physics). Google “symplectic integrators” for more details. [Verlet integration]

Author comment: i would not recommend RK4 unless your simulation suits this model well – RK4 is easy once you understand it, but structuring your simulation in this way is non-traditional, and difficult unless you are doing everything with spring forces

Author comment: for any interesting simulation acceleration is a continuous function of other variables such as current velocity (for example, drag), and position (springs). since these quantities change over the frame, the force which is a function of them also changes over the frame. in these cases, RK4 provides better accuracy – because [it] is able to detect and correct for these changes in acceleration over the timestep

Author comment: To get the benefits of RK4 it is essential that you recalculate all forces at each step of RK4, otherwise your drag force is constant over the frame time – and you are really just doing an euler integration

Constant Acceleration?

Someone in the comments points out it’s accurate to do “Euler integration” (or is it “ballistic integration”?) if acceleration is constant over the timestep:

d’ = d + v*t + 0.5*a*t*t
v’ = v + a*t

Later in the comments, someone explained: I’m intrigued, if acceleration is applied during the timestep, then the velocity isn’t constant and so the position must be calculated with respect to the acceleration. So, why wouldn’t the following work?

while ( t <= 10 )
{
float accel ( force / mass );
position+= (velocity*dt) + ((accel*(dt*dt))/2);
velocity+= accel * dt;
t+= dt;
}

The article’s author replied: that would actually work perfectly, and without error – given [constant] acceleration, but what about the case where acceleration is non-linear?  In this case RK4 works much better, because it can take into account change down to the fourth derivative, any error in RK4 is O(5) from the taylor’s series expansion.  So in the general case RK4 is better than the integrator that you present, but if you have a linear acceleration only, perhaps a ballistic point under constant gravity, then the integrator you presented works just fine.

I wrote a simple test program to show that with a constant acceleration, you can get 100% accuracy (ignoring double precision issues) without RK4.  The result was the same for for doing t in one timestep as doing t in 100 timesteps:

   1: void test()

   2: {

   3:     // p = p + v*dt + a*0.5*dt*dt

   4:     // v = v + a*dt

   5:     double p, v, a, dt, t;

   6:     double pStart = 50;

   7:     double vStart = 3;

   8:     a = 1;

   9:     t = 100.0;

  10:     dt = 1.0;

  11:  

  12:     // first try the full 100 in one step

  13:     p = pStart + vStart*t + a*0.5*t*t;

  14:     v = vStart + a*t;

  15:     printf("full: %.2f, %.2f\n", p, v); // 5350.00, 103.00

  16:  

  17:     p = pStart;

  18:     v = vStart;

  19:     for (double tSoFar = 0; tSoFar < 100.0; tSoFar += dt)

  20:     {

  21:         p = p + v*dt + a*0.5*dt*dt;

  22:         v = v + a*dt;

  23:         printf("%6.2f: %7.2f, %6.2f\n", tSoFar + 1.0, p, v);

  24:     }

  25: }

Author Comment: s = ut + 1/2at^2 gives exact results, but simple euler integration like this: v += a * dt, s += v * dt does not.  The reason being that the constant acceleration means that velocity is changing constantly, so the inaccuracy is incurred in the s += v * dt term

Game Loop code

TODO post my updated game loop that takes above notes into account?

Performance

Another article, http://codeflow.org/entries/2010/aug/28/integration-by-example-euler-vs-verlet-vs-runge-kutta/ , points out that you can adjust your time time step for a less accurate method to make it more accurate (but slower).  This is an issue to consider with different integration methods (Euler, RK2, RK4, Verlet).

Cross-platform SDL 2.0 with OpenGL ES 2.0 setup C++

I downloaded SDL 2.0 and decided to setup a cross-platform development code project with an online subversion repository.  My idea is to write some cross-platform graphics demos using C++ and graphics API’s using some combination of (OpenGL ES, OpenGL, and DirectX).  Although just setting up five different development environments for the same code required significant effort.  SDL made this easier.

For my initial setup, I started from the “SDL2-2.0.0” source code download.  SDL includes README-android.txt etc files that describe how to setup the build process of SDL.  And there are tutorials and other resources online to help with the setup for each platform.  Since I wanted to use a shared cross-platform code base in subversion, I needed some extra setup and debug effort to get my hello world cube running on multiple platforms.  It took some effort to setup, but it was really cool once I got it working.

So my initial idea for my cross-platform build was to create a subversion project where I could build and run a hello world OpenGL program with SDL on five different platforms – Windows, Linux (Ubuntu), OS X, iOS, and Android.  I setup a single subversion repository (on the internet) and two real hardware computers to do this.  My Windows 7 desktop builds the Windows project with Visual Studio, and my Android project with Android Eclipse & JDK & NDK.  I setup an Ubuntu virtual machine in VMWare Player for the Linux build with gcc.  For OS X and iOS, I used a MacBook Air and XCode (two XCode projects – one for iOS, one for OS X).

My OS X laptop already runs VMWare Fusion with Windows 8 and Ubuntu, so it would probably not be hard to build all five projects from my MacBook Air.  I suspect it’s not that hard to run OS X on a virtual machine (such as VMWare Player), so it would probably not be hard to build all five projects from my Windows desktop.  If I wanted to go extra crazy, I could even setup an Android build environment for Ubuntu and OS X (in addition to Windows).

SDL2 includes some sample programs in the “test” directory, including “testgl2.c”” and “testgles.c”.  The OpenGL 2 demo uses some old stuff like glBegin() & glEnd() instead of a vertex buffer.  OpenGL ES 2.0, on the other hand, does not.  OpenGL ES 2.0 is roughly a subset of OpenGL 2.0.  However, it eliminates most of the fixed-function render pipeline in favor of a programmable one in a move similar to the transition from OpenGL 3.0 to 3.1.  So I decided to get “testgles.c” to build on five platforms.

I read here ( http://www.g-truc.net/post-0457.html ) (warning that link is from 2012/03) there are different paths for OpenGL ES to run on a desktop OS.  But what I did is just use #ifdef for OpenGL ES mobile versus OpenGL desktop.  At least for now, this method allowed me to get my hello world cube to build & run on all five platforms.  My only #ifdef code so far is this:

   1: #include "SDL_test_common.h"

   2:  

   3: #if defined(__IPHONEOS__) || defined(__ANDROID__)

   4: #define HAVE_OPENGLES

   5: #endif

   6:  

   7: #ifdef HAVE_OPENGLES

   8: #include "SDL_opengles.h"

   9: #else

  10: #include "SDL_opengl.h"

  11: #endif

And this:

   1: #ifdef HAVE_OPENGLES // GLES supports fixed point, but GL does not

   2:         glOrthof(-2.0, 2.0, -2.0 * aspectAdjust, 2.0 * aspectAdjust, -20.0, 20.0);

   3: #else

   4:         glOrtho(-2.0, 2.0, -2.0 * aspectAdjust, 2.0 * aspectAdjust, -20.0, 20.0);

   5: #endif

It was enjoyable to get this initial setup working (and a little more effort than I ‘d hoped, but all things considered not too bad).  A future setup step may be to add a DirectX path Windows and for Windows Phone 8.  I’ve read there’s a project called ANGLE that translates WebGL and other OpenGL ES 2.0 API calls to DirectX 9 or DirectX 11.  And of course there are plenty of middleware gaming frameworks to support cross-platform development ( http://stackoverflow.com/questions/13483179/can-i-use-opengl-es-in-a-windows-phone-8-app ).  But your best option depends on your goal.

There are different layers of abstraction that a graphics programmer or GPU programmer could work on.  Here’s one way to look at it:
1) GPU hardware, GPU simulation, GPU systems software (drivers & VBIOS)
2) Low-level API development & tools (OpenGL, DirectX, AMD’s Mantle, NVIDIA CUDA, OpenCL)
3) Middleware & middleware tools, game engine & game engine tools, using low-level GPU APIs directly
4) Writing a game or other 3d application using an existing game engine or middleware
* Disclaimer: this list is not the only way to consider the layers of abstraction

This cross-platform building with SDL 2.0 graphics demo project falls into “using low-level GPU APIs directly”.  For certain kinds of game or 3d application development, it makes sense to use middleware.  But someone has to write that middleware.  And for many projects it makes sense to use OpenGL or DirectX (or AMD Mantle etc) directly.

Okay enough babbling – here are the screen shots of my OpenGL / OpenGL ES hello world cube building and running on five different platforms – Windows 7, Android, Ubuntu Linux, OS X, and iOS:

win7 android ubuntu osx ios