ETC1 textures loading and alpha handling with Android NDK

 Previous parts

• Simple cross-platform game engine - Introduction
• Universal Box2D debug draw for OpenGL ES 1.x and OpenGL ES 2.0
• Loading images under Windows 
• Load images under Android with NDK and JNI
• Using JNI_OnLoad() in Adroid NDK development 
• Simple streaming audio mixer for Android with OpenSL ES - part 1  
• Simple streaming audio mixer for Android with OpenSL ES - part 2
• Crunch - very lightweight unpacker used in our Android and bada games
• Using zlib compression library in Adroid NDK

 In this post I will describe how to work with ETC1 textures.

 What are compressed textures good for?

 You are probably familiar with image formats like .png and .jpg. The first one employs lossless compression while the second uses lossy compression. Usually the .jpg files are smaller for the same image for price of decreased quality.

 Regardless the way the image is stored compressed on the disk, when you load and extract it into memory it bloats to its uncompressed size. For RGBA 8888 it is 32 bits per each one pixel. So when your 1024x1024 image as a texture may eat 4MB of precious video memory

  Beside these well known image formats there are also formats that compress the texture and it stays compressed on GPU. These formats can drastically reduce number of bits required for each pixel.

 Unfortunately, when coding for Android these formats are vendor specific. Currently there are four of them: ETC1, PVRTC, ATITC, S3TC. See more here.

 Only ETC1 is available on all Android devices so the rest of the article is about this format. But it lacks one important thing - it does not support textures with alpha. Fortunately, there are ways how to bypass this. As mentioned before, these format means that texture stays compressed on GPU being decompresssed on the fly which will reduce texture space used as well as increase performance of your openGL game (reduced data bandwidth).

 Another atractiviy of these texture formats comes from fact that you do not need to include any image unpacking library like libpng into your game. Nor you need to load images on the java side like I was describing in my older post (Load images under Android with NDK and JNI).

 The drawback is that textures in its compressed form are bigger than .jpg or .png files with the same image, so more disk space will be consumed. Further in the article I will also describe way how I solved it.

Creating ETC1 texture

 Every GPU vendor has its own set of tools including tool for compressing textures. I am using tool from ARM (load it here). After you run the tool you will get initial screen. Open image file with you texture (do not forget that open GL ES needs height and width to be power of 2) and you should get screen like this:

 Select the texture(s) in left panel and press "Compress" icon (). The compression parameters panel will pop up:

 Choose ETC1/ETC2 tab (1.) and select PKM as output format. PKM is very simple format that ads small header to compressed data. The header is this:

+0: 4 bytes header "PKM "
+4: 2 bytes version "10"
+6: 2 bytes data type (always zero)
+8: 2 bytes extended width
+10: 2 bytes extended height
+12: 2 bytes original width
+14: 2 bytes original height
+16: compressed texture data

 In ETC1 format each 4x4 pixel bloc is compressed into 64 bits. So the extended width and height are the original dimensions rounded up to multiple of four. If you are using power of 2 textures then the original and extended dimensions are the same.

 From these parameters you can calculate the size of compressed data like this:

(extended width / 4) * (extended height / 4) * 8

 This formula just says: there is so many 4x4 pixel blocks and each of them is 8 bytes long (64 bits).

 Parameters marked 2. and 5. on the picture will affect quality of compression. The compression takes quite a lot of time. So during development you can use worse quality if you do not want to wait. But be sure that when finishing your game you use maximum quality - the size of output remains the same.

 Under 3. do not forget to check that ETC1 is chosen and udder 4. choose to create separate texture for alpha channel. This texture will have the same dimensions as the original one. But in the red channel of it there will be stored alpha instead of color. The green and blue channels are unused so theoretically you can put any additional information there (but not with the tool - it would be up to you how to do it).

Loading ETC1 texture

  Now when you have the texture compressed it is time to load it into GPU.

//------------------------------------------------------------------------
u16 TextureETC1::swapBytes(u16 aData)
{
 return ((aData & 0x00FF) << 8) | ((aData & 0xFF00) >> 8);
}

//------------------------------------------------------------------------
void TextureETC1::construct(SBC::System::Collections::ByteBuffer& unpacked)
{
 // check if data is ETC1 PKM file - should start with text "PKM " (notice the space in the end)
 // read byte by byte to prevent endianness problems
 u8 header[4];
 header[0] = (u8) unpacked.getChar();
 header[1] = (u8) unpacked.getChar();
 header[2] = (u8) unpacked.getChar();
 header[3] = (u8) unpacked.getChar();

 if (header[0] != 'P' || header[1] != 'K' || header[2] != 'M' || header[3] != ' ')
  LOGE("data are not in valid PKM format");

 swapBytes is just help method the real work is done in construct method. ByteBuffer is our simple wrapper around array of bytes holding not only data but also its size. This is not important here it just increases readability.

 We start with header to check whether the input data are really PKM file.

 // read version - 2 bytes. Should be "10". Just skipping
 unpacked.getShort();
 // data type - always zero. Just skip
 unpacked.getShort();

 // sizes of texture follows: 4 shorts in big endian order
 u16 extWidth = swapBytes((u16) unpacked.getShort());
 u16 extHeight = swapBytes((u16) unpacked.getShort());
 u16 width = swapBytes((u16) unpacked.getShort());
 u16 height = swapBytes((u16) unpacked.getShort());

 // calculate size of data with formula (extWidth / 4) * (extHeight / 4) * 8
 u32 dataLength = ((extWidth >> 2) * (extHeight >> 2)) << 3;

 In next step we skip additional information on version and data type as we do not use them. Then dimensions are read and with swapByte it is converted from big endian to little endian. The size of compressed data is calculated with already mentioned formula.

  // openGL part
  // create and bind texture - all next texture ops will be related to it
  glGenTextures(1, &mTextureID);
  glBindTexture(GL_TEXTURE_2D, mTextureID);
  // load compressed data (skip 16 bytes of header)
  glCompressedTexImage2D(GL_TEXTURE_2D, 0, GL_ETC1_RGB8_OES,
    extWidth, extHeight, 0, dataLength, unpacked.getPositionPtr());

  // set texture parameters
  glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
  glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
  glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP_TO_EDGE);
  glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP_TO_EDGE);

  // save size
  mWidth = extWidth;
  mHeight = extHeight;
}

 Now it is time to create texture with OpenGL calls. We first allocate texture ID and then we sent data for it. Note that internal format is GL_ETC1_RGB8_OES. This says that we are using OES_compressed_ETC1_RGB8_texture extension that ads support for ETC1 textures.

 Now we can use this texture as any other loaded from .png.

Handling alpha with ETC1 textures

 As previously said, ETC1 does not support alpha. During texture creation time we exported alpha into separate texture. This texture has the same dimension as the one with colors. You can employ fragment shader to compose the final color containing alpha from these two textures.

 The simple fragment shader doing this may look like this:

#ifdef GL_ES
precision mediump float;
#endif

uniform lowp sampler2D u_map[2];
varying mediump vec2 v_texture;

void main(void)
{
  gl_FragColor = vec4(texture2D(u_map[0], v_texture).rgb, texture2D(u_map[1], v_texture).r);
}

 It took me less than 1 hour to rewrite parts of our game to support ETC1 with alpha in separate texture instead of previously used textures from .png files. And I got really sweet reward in increasing the frame rate by about 10% on my Samsung Galaxy Tab.

Compression to the power of two

 The last thing that I did not liked first was that ETC1 textures without alpha were 2 times bigger than .jpg files (in our prepared game Shards we are using .jpg for backgrounds - so no need for alpha for these). I finally solved this with additional compression of .pkm file with zlib library. It took me some time to find how to use it on Android, but you can read it here (Using zlib compression library in Adroid NDK) - it is really worth of it.

 Now I am almost on the size of .jpg file. When creating texture I first uncompress the file with zlib and the uncompressed .pkm is sent to previously described routine.

Conclusion

  ETC1 texture compression is the only one supported by all Android devices (having OpenGL ES 2.0 of course). It lacks alpha so small overhead is present when bypassing this. It pays as you are saving texture memory and increasing your frame rate - 10% in case of my Samsung Galaxy Tab.

Using zlib compression library in Adroid NDK

 Previous parts

• Simple cross-platform game engine - Introduction
• Universal Box2D debug draw for OpenGL ES 1.x and OpenGL ES 2.0
• Loading images under Windows 
• Load images under Android with NDK and JNI
• Using JNI_OnLoad() in Adroid NDK development 
• Simple streaming audio mixer for Android with OpenSL ES - part 1  
• Simple streaming audio mixer for Android with OpenSL ES - part 2
• Crunch - very lightweight unpacker used in our Android and bada games

 Just one day after writing article on Crunch the packing utility and way how to unpack data created with it I wandered how much overhead it would take to get into zlib library. It was very pleasant for me, that using it is very intuitive and also the implementation was without problems.

Android implementation

 Android NDK already contains library and header file in NDK. The header is in directory:

    \android-ndk-r8b\platforms\android-14\arch-arm\usr\include\zlib.h

and library is indirectory

    \android-ndk-r8b\platforms\android-14\arch-arm\usr\lib\libz.so

 To make it part of your NDK project you have to open Android.mk file and add the following lines into it (first one is just comment):

  #Zlib
  LOCAL_LDLIBS    += -lz

 Now it is enough to include header file "zlib.h" in the beginning of any source file where you want to use it.

 In my engine I build simple wrapper around it to simplify calling of compress / uncompress. I am again using the IPacker interface introduced in previous article. The target is to have unified interface for various packing / unpacking utilities and libraries. I just want to send it ByteBuffer (our class for wrapping array, its length and adding some utilities for working with it) and get another with result back. Just to remember the interface methods are like this:

 // compress data and returns pointer to heap allocated ByteBuffer with it
 virtual SBC::System::Collections::ByteBuffer* compress(u8* aUnpackedData, s32 aSize) = 0;
 virtual SBC::System::Collections::ByteBuffer* compress(
   SBC::System::Collections::ByteBuffer& aUnpackedData) = 0;
 // uncompress data and returns heap allocated ByteBuffer with it
 virtual SBC::System::Collections::ByteBuffer* uncompress(u8* aPackedData, s32 aSize) = 0;
 virtual SBC::System::Collections::ByteBuffer* uncompress(
   SBC::System::Collections::ByteBuffer& aPackedData) = 0;

 There are two things I found important about zlib:
 - it is not Zip, gzip or any other unpacking program (while these use algorithms from zlib heaving the same authors). Do not expect that it will open zip archives you created for example in WinZip program. Zlib has its own internal format,
 - when you compress piece of memory you get result compressed into another piece of memory without any information on how much bytes the original data had. It is up to you to handle it somehow if you do not want to allocate extra large space for uncompression that every file will fit in.

Compress

 Here is the implementaion of compress routines:

//------------------------------------------------------------------------
ByteBuffer* ZlibPacker::compress(u8* aUnpackedData, s32 aSize)
{
 ByteBuffer buffer;
 buffer.construct(aUnpackedData, aSize, false);

 return compress(buffer);
}

//------------------------------------------------------------------------
ByteBuffer* ZlibPacker::compress(ByteBuffer& aUnpackedData)
{
 // maximum length needed for compression
 unsigned long destLength = compressBound(aUnpackedData.getLimit());

 The first one just wraps raw data into ByteBuffer to pass it further (the false says that ByteBuffer is not owner of the data and will not delete it on destruction). In the second the actual work starts. First we call compressBound() method with length of data we want to compress. The method will return maximum length required for target buffer where packed data will be placed. In worst case when there is no compression in result the final size will be size of the original data plus some zlib overhead.

 // add 4 for header (to save original unpacked data length)
 u8* out = new u8[destLength + 4];
 s32 result = ::compress(out + 4, &destLength,
   aUnpackedData.getDataPtr(), aUnpackedData.getLimit());

 if (result != Z_OK)
 {
  switch(result)
  {
  case Z_MEM_ERROR:
   LOGE("note enough memory for compression");
   break;

  case Z_BUF_ERROR:
   LOGE("note enough room in buffer to compress the data");
   break;
  }
 }

 We allocate new buffer for compressed data. We add 4 bytes. This will be our "minimalistic" header keeping information on how big were the original data.
 Notice the double colon before compress() method. It is to force the compiler use non-class uncompress() method. If you omit it you will get compiler error as non compress methods within class takes 4 parameters.
 We put out + 4 as a first parameter, because we want to reserve first 4 bytes in the beginning to write original data size into it later.
 Also note that destLength is handed over like pointer. It is because the length of final compressed data will be handed back in it.

 // create new buffer and copy data into it
 ByteBuffer* packed = new ByteBuffer();
 packed->construct(destLength + 4, out, destLength + 4);

 // delete old buffer - not needed more
 delete [] out;

 Now the data are packed and its final packed length is known. As the zlib works well our initial maximal buffer is probably to big. Part of it is empty just eating memory. So we create new ByteBuffer with capacity needed just for compressed data and 4 bytes header. The ByteBuffer construct copies the requested amount of data into new ByteBuffer.
 We can now free the old (probably partly empty) ByteBuffer.

 // set position to beginning and save unpacked size
 packed->setPosition(0);
 packed->setInt((s32) aUnpackedData.getCapacity());
 packed->setPosition(0);

 return packed;
}

 In the end we will write original (unpacked) data length into the beginning and return the result.

Uncompress

The uncompression looks similarly:

//------------------------------------------------------------------------
ByteBuffer* ZlibPacker::uncompress(u8* aPackedData, s32 aSize)
{
 ByteBuffer buffer;
 buffer.construct(aPackedData, aSize, false);

 return uncompress(buffer);
}

//------------------------------------------------------------------------
ByteBuffer* ZlibPacker::uncompress(ByteBuffer& aPackedData)
{
 // read size of unpacked data
 unsigned long destLength = (u32) aPackedData.getInt();

 // create bytebuffer with sufficient capacity to hold unpacked data
 ByteBuffer* unpacked = new ByteBuffer();
 unpacked->construct(destLength);

 First we read length of uncompressed data. This is not part of zlib and it is up to you to keep it somewhere (or allocate buffer big enough to hold the biggest file you consider to process).

 s32 result = ::uncompress(unpacked->getDataPtr(), &destLength,
   aPackedData.getPositionPtr(), aPackedData.getLimit() - 4);

 if (result != Z_OK)
 {
  switch(result)
  {
  case Z_MEM_ERROR:
   LOGE("note enough memory for uncompression");
   break;

  case Z_BUF_ERROR:
   LOGE("note enough room in buffer to uncompress the data");
   break;

  case Z_DATA_ERROR:
   LOGE("compressed data corrupted or incomplete");
   break;
  }
 }

 Here we call the zlib uncompress() method. The third parameter "aPackedData.getPositionPtr()" returns unsigned char* pointing just after the 4 byte header! Do not forget to skip any headers you added to point to raw zlib data. The position within ByteBuffer automatically moved when we read the size in the very beginning of the method.

 unpacked->setLimit(aPackedData.getLimit() - 4);

 return unpacked;
}

 Finally we adjust some ByteBuffer internal variables and return the result.

Summary

 It is easy to make the zlib work in your project. Remember that it is not UnZip program so just putting some zips into your asset will not work. The zlib library also supports compressing and uncompressing in gzip (.gz format) format and ads gzip file access functions to easily work with it. It is still too fresh for me, so I will have to examine it in future.

Crunch - very lightweight unpacker used in our Android and bada games

Previous parts

• Simple cross-platform game engine - Introduction
• Universal Box2D debug draw for OpenGL ES 1.x and OpenGL ES 2.0
• Loading images under Windows 
• Load images under Android with NDK and JNI
• Using JNI_OnLoad() in Adroid NDK development 
• Simple streaming audio mixer for Android with OpenSL ES - part 1  
• Simple streaming audio mixer for Android with OpenSL ES - part 2 

UPDATE: next day after writing this article I explored zlib compression library and found it very easy to implement. Read how to do it in "Using zlib compression library in Adroid NDK". My own unpacking utility, I spent lot of time with, described further down still works within our engine and as it is very small and fast in decompression I still may have use for it in projects without zlib. Teaching from this for me: "think twice, cut once".

 Here is next article on mobile games programming topics I came across when building our small games. This time it is about way how to minimize size of your game assets on the disk and how to quickly unpack them without need of Java code part or without need of any big library.

 Common way is to pack or compress the assets to the smallest possible size to reduce space consumed on target device. There are lossy compression formats like .jpg for pictures but what if lossless compression is needed? The possible solution in Android NDK development is to use zlib library. But it brings some overhead before you get familiar with it.

Crunch - the packer

 Fortunately I found very old program by me written in basic that compresses the data and rewritten it into Java. The program runs very slowly, but gives good results so I am using it now for assets compression. It also has only 6 bytes header, thus it is very easy to work with it. The program names Crunch and you can download it here.

 The Crunch looks like this:

 You can add multiple files and delete them from list. You can also set number of "Window bits" which says how far back in data the matches are being searched and "Match bits" which says how long can the matches be.

 The program can only compress the data. The result starts with 6 bytes header:

+0: length of packed data (4 bytes)
+4: window size bits (1 byte)
+5: match size bits (1 byte)
+6: packed data

Unpacking data

 Now  when we have our data packed, we need to decompress them in the game. To do it we first create IPacker interface that will help us to add different packing algorithms or wrap some 3rd party libraries in future.

#ifndef IPACKER_H_
#define IPACKER_H_

#include "../../System/system.h"

namespace SBC
{
namespace Engine
{

class IPacker
{
public:
 virtual ~IPacker() {};

public:
 // encodes data and returns pointer to heap allocated ByteBuffer with it
 virtual SBC::System::Collections::ByteBuffer* encode(u8* aUnpackedData, s32 aSize) = 0;
 virtual SBC::System::Collections::ByteBuffer* encode(
   SBC::System::Collections::ByteBuffer& aUnpackedData) = 0;
 // decodes data and returns heap allocated ByteBuffer with it
 virtual SBC::System::Collections::ByteBuffer* decode(u8* aPackedData, s32 aSize) = 0;
 virtual SBC::System::Collections::ByteBuffer* decode(
   SBC::System::Collections::ByteBuffer& aPackedData) = 0;
};

} /* namespace Engine */
} /* namespace SBC */
#endif /* IPACKER_H_ */

 ByteBuffer is class that I use for convenient manipulation with byte data (unsigned char / u8). It allows reading of int, short or char as well as storing it into ByteBuffer.

 Next we will implement this interface in class SBCDepacker:

#ifndef SBCDEPACKER_H_
#define SBCDEPACKER_H_

#include "IPacker.h"

namespace SBC
{
namespace Engine
{

class SBCDepacker: public IPacker
{
public:
 SBCDepacker();
 virtual ~SBCDepacker();

public:
 // IPacker implementation
 // encodes data and returns pointer to heap allocated ByteBuffer with it
 virtual SBC::System::Collections::ByteBuffer* encode(u8* aUnpackedData, s32 aSize);
 virtual SBC::System::Collections::ByteBuffer* encode(SBC::System::Collections::ByteBuffer& aUnpackedData);
 // decodes data and returns heap allocated ByteBuffer with it
 virtual SBC::System::Collections::ByteBuffer* decode(u8* aPackedData, s32 aSize);
 virtual SBC::System::Collections::ByteBuffer* decode(SBC::System::Collections::ByteBuffer& aPackedData);

private:
 u32 readData(s32 aNumBits, SBC::System::Collections::ByteBuffer& aPackedData);

private:
 u8 mData;
 u8 mDataBitsRest;
};

} /* namespace Engine */
} /* namespace SBC */
#endif /* SBCDEPACKER_H_ */

 It just implements methods from interface and ads private method readData() that is able to read requested number of bits from array of bytes.

 Here is implementation of decode() and readData() methods. As we can only unpack the data, the implementation for encode() just writes error message to the output. All source files is possible to download here:

//------------------------------------------------------------------------
ByteBuffer* SBCDepacker::decode(ByteBuffer& aPackedData)
{
 // clear data
 mData = 0;
 mDataBitsRest = 0;

 // read header
 s32 length = aPackedData.getInt();
 s8 winBits = aPackedData.getChar();
 s8 matchBits = aPackedData.getChar();

 // create byte array for result
 ByteBuffer* unpacked = new ByteBuffer();
 unpacked->construct(length);
 u8* dest = unpacked->getDataPtr();

 // not packed - just read
 if (!winBits && !matchBits)
 {
  memcpy(dest, aPackedData.getPositionPtr(), length);
 }
 // if packed then decode
 else
 {
  while (length)
  {
   // read 1 bit and check whether it is packed or not
   u32 result = readData(1, aPackedData);

   // packed
   if (result)
   {
    s32 zpet = readData(winBits, aPackedData);
    s32 shoda = readData(matchBits, aPackedData);

    for (s32 i = shoda; i > 0; --i)
    {
     *(dest) = *(dest - zpet);
     ++ dest;
    }

    length -= shoda;
   }
   // unpacked
   else
   {
    result = readData(8, aPackedData);

    *(dest ++) = (u8) (result & 0xFF);
    -- length;
   }
  }
 }

 // set limit to capacity
 unpacked->setLimit(unpacked->getCapacity());
 
 return unpacked;
}

//------------------------------------------------------------------------
u32 SBCDepacker::readData(s32 aNumBits, ByteBuffer& aPackedData)
{
 u32 result = 0;

 // while not requested number of bits read
 while (aNumBits > 0)
 {
  // if out of bits read next byte
  if (!mDataBitsRest)
  {
   mData = (u8) aPackedData.getChar();
   mDataBitsRest = 8;
  }

  // how many bits to read (limited with remaining bits)
  u32 num = Math::min(mDataBitsRest, aNumBits);
  // create mask for given number of bits
  u32 mask = (1 << num) - 1;

  // shift previous result and add masked values
  result = (result << num) | (mData & mask);

  // adjust variables for next read
  aNumBits -= num;
  mDataBitsRest -= num;
  mData >>= num;
 }

 return result;
}

Conclusion

 That's all. With this simple class you can unpack data previously packed with Crunch utility like this:

 // load compressed file from disk
 ByteBuffer* compressed = aLoader->loadToByteBuffer(aIdx);

 // create unpacker and unpack data
 SBCDepacker sbcDepacker;
 ByteBuffer* unpacked = sbcDepacker.decode(*compressed);

 // delete compressed data - no more needed now as all data is in unpacked
 delete compressed;

  If you do not want or need to link whole zlib library or you want something really simple that works, then you may give a try to Crunch. In our games we are currently using it for packing ETC1 textures. These are packed itself but format is targeted to reduce GPU bandwidth not minimize disk space. It can be reduced almost to half of the size with Crunch so the disk space consumption is decreased significantly.

Download Crunch 1.0

Source for unpacking

Bounce timing / easing function

Working on our next game the graphic designer designed one of the animations in such a way that I needed to write special timing function. There is big block falling from top of the screen, that bounces several times and stays still. I wanted to enrich my engine with function that will not only do this job, but will be also useful in future. I ended with flexible function that produces bounces based on given parameters and on the next lines I will describe it step by step.

Parameters & result

 I will start with brief gallery of achieved results. The function takes four parameters:

•  duration of whole effect in seconds,
•  number of bounces (actually how much times the floor is touched),
•  elasticity,
•  whether to start the first bounce from floor or from top

 You can call the function with all four parameters set but if you want for example bounce three times and stay still then you can omit elasticity (set to -1) and the function will calculate it for you. On the following pictures is what I am exactly writing about - I am asking to produce such a curve that it should take 3 seconds and 3 bounces and then the bouncing object will stay still. In first case I want to start it from top (for example something may fall from off screen region into visible area) and in the second case I want to make it jump from bottom:

  In the first of following two I am saying, that I want 3 seconds again, elasticity 0.5 and start from top. I do not know how many bounces is necessary to leave the object on floor. But the function calculates for me it is 8 of them and calculates the speed of move to squeeze it into 3 seconds.

 In the second I am setting the elasticity over 1 so I will overshot 0.0-1.0 output range and so I have to define the number of bounces else the function would try to squeeze infinite number of bounces into three seconds. It ends itself only when zero height is reached or when requested number of bounces is met.

Header

 Look at the header file below. You will see we are defining some variables, constants and functions. The constants will limit our function to 10 bounces as well as it defines epsilon error value that will be explained during implementation.

 The variables holds the ones needed for whole function - as its duration, number of bounces, elasticity, calculated acceleration and so on. And it also holds values specific for every single bounce - its duration, initial velocity and height. Yes, the resulting function faces itself for programmer as single function but it is inside series of individual consecutive bounces.

 The functions are simple getters (imagine you are calling with unknown number of bounces in initialization; you can ask then how many of them was calculated) and functions that set and return the height based on duration progress.

 One remark: the function is taken from my cross-platform engine (you can read other posts regarding it on this blog) so do not get confused with specific namespaces. Rewrite them with yours or delete it.

#ifndef TIMINGBOUNCE_H_
#define TIMINGBOUNCE_H_

#include "../../System/system.h"

namespace SBC
{
namespace Engine
{

class TimingBounce
{
public:
 static const u32 BOUNCES_MAX = 10;
 static const f32 EPSILON;
 static const f32 INTERNAL_HEIGHT;

public:
 TimingBounce();
 virtual ~TimingBounce();

public:
 void initialize(f32 aDuration, s32 aBounces, f32 aElasticity = -1.0f, bool aHalveFirstBounce = true);
 f32 tick(f32 aDeltaTime);
 f32 getActual();
 f32 getAt(f32 aDurationProgress);

 // getters
 f32 getDuration();
 f32 getDurationProgress();
 s32 getBounces();
 f32 getElasticity();
 f32 getAcceleration();

private:
 // duration of function
 f32 mDuration;
 // actual position in duration
 f32 mDurationProgress;

 // number of bounces
 s32 mBounces;
 // elasticity - how high is next amplitude
 f32 mElasticity;
 // acceleration for requested parameters
 f32 mAcceleration;
 // start from peek or from bottom
 bool mHalveFirstBounce;

 // duration of particular bounces
 f32 mBounceDuration[BOUNCES_MAX];
 // height of particular bounces
 f32 mBounceHeight[BOUNCES_MAX];
 // bounce velocity
 f32 mBouceVelocity[BOUNCES_MAX];
};

} /* namespace Engine */
} /* namespace SBC */
#endif /* TIMINGBOUNCE_H_ */

Implementation

 Next follows the implementation. It is cut into pieces and described and explained step by step:

 We simply start with defining some of the constants. The EPSILON is error member and is set to 1, which is in most cases 1 pixel on the screen. The INTERNAL_HEIGHT is defined as 1000. The function inside calculates the height of bounces in range 0-1000 and this is then normalized into 0-1 before vales are returned to client.

 Constructor simply sets initial values. Actually undefined elasticity (-1.0f) and zero number of bounces are together invalid parameters.

#include "TimingBounce.h"

#undef LOG_TAG
#define LOG_TAG  "TimingBounce"

namespace SBC
{
namespace Engine
{

using namespace SBC::System::MathUtils;

const f32 TimingBounce::EPSILON = 1.0f;
const f32 TimingBounce::INTERNAL_HEIGHT = 1000.0f;

//------------------------------------------------------------------------
TimingBounce::TimingBounce()
{
 mDuration = 0.0f;
 mDurationProgress = 0.0f;
 mBounces = 0;
 mElasticity = -1.0f;
 mAcceleration = 0.0f;
 mHalveFirstBounce = false;
}

//------------------------------------------------------------------------
TimingBounce::~TimingBounce()
{
}

Now comes the initialize function where most of the fun takes place:

//------------------------------------------------------------------------
void TimingBounce::initialize(f32 aDuration, s32 aBounces, f32 aElasticity, bool aHalveFirstBounce)
{
 // check parameters validity
 if (aBounces <= 0 && aElasticity < 0.0f)
 {
  LOGE("Invalid parameters (aBounces = %i, aElasticity = %f)", aBounces, aElasticity);
  return;
 }
 else if (aDuration < 0.0f)
 {
  LOGE("Duration cannot be less than zero");
  return;
 }

 First we check whether input parameters are correct. Either one of aBounces or elasticity must be defined (bounces higher than zero and / or elasticity also higher than 0).

 // calculate missing parameters
 // if defined bounces but not elasticity
 if (aBounces > 0 && aElasticity < 0.0f)
 {
  aElasticity = Math::pow(EPSILON / INTERNAL_HEIGHT, 1.0f / aBounces);

 }
 // if defined elasticity but not bounces
 else if (aElasticity > 0.0f && aBounces <= 0)
 {
  if (aElasticity >= 1.0f)
  {
   LOGE("Elasticity must be less than 1");
   return;
  }

  // EPSILON = aElasticity ^ aBounces ... aBounces = log_aElasticity EPSILON = ln EPSILON / ln aElasticity
  aBounces = Math::log(EPSILON / INTERNAL_HEIGHT) / Math::log(aElasticity);
 }

 If we know the number of bounces and elasticity is unknown we have to calculate it. It will have such a value that after requested number of bounces the potential next bounce would had its height less or equal to EPSILON. It comes from calculation:

$$
$\text{EPSILON}= \text{INTERNAL\_HEIGHT}\ast {\mathrm{elasticity}}^{\mathit{bounces}}$

$\mathit{elasticity}={\mathit{(EPSILON}/\text{INTERNAL\_HEIGHT)}}^{1/\mathit{bounces}}$

 In second case the unknown are the bounces so the calculation is:

$\mathit{bounces}=\frac{\log (\text{EPSILON}/\text{INTERNAL\_HEIGHT})}{\log (\mathit{elasticity})}$

Now when we know the parameters we can save it:

 // store parameters
 mDurationProgress = 0.0f;
 mBounces = aBounces;
 mElasticity = aElasticity;
 mHalveFirstBounce = aHalveFirstBounce;

 But with the parameter above we still do not know how much time the function will take. We request some time but we do not know the speed. So, we have to calculate it. As the whole function is not a single function but internally it is sequence of functions we will choose some random speed to calculate how much time each bounce takes and calculate the total time
 Each bounce takes 2 times the result of:

$\mathit{ }$
$\mathit{height}=\frac{1}{2}\mathit{acceleration}\ast {\mathit{time}}^2$

$\mathit{ }$

$\mathit{time}=\sqrt{\frac{2\ast \mathit{height}}{\mathit{acceleration}}}$

  Two times because we have to reach the top of bounce and then the same time it takes to fall down.

 // get "some" acceleration and calculate time for bounces
 f32 acceleration = INTERNAL_HEIGHT / 1000.0f;
 f32 totalDuration = 0.0f;
 f32 height = INTERNAL_HEIGHT;
 for (s32 i = 0; i < mBounces; i++)
 {
  // s = 1/2 a * t^2 ... 2s / a = t^2 ... sqrt(2s / a) = t
  f32 duration = Math::sqrt(2 * height / acceleration) * 2;

  if (mHalveFirstBounce && i == 0)
   duration /= 2;

  mBounceDuration[i] = duration;
  mBounceHeight[i] = height;

  totalDuration += duration;
  height *= mElasticity;
 }

 Let's say that the total duration resulted in 340 seconds with some initial velocity. This is more than 100 times more than we requested. But as we have the time ratio between the bounces we can adjust it to our requested time:

 // adjust total duration to fit requested duration
 mDuration = 0.0f;
 for (s32 i = 0; i < mBounces; i++)
 {
  f32 duration = mBounceDuration[i] * aDuration / totalDuration;
  mBounceDuration[i] = duration;
  // sum up to avoid imprecision
  mDuration += duration;
 }

 Now, when we are in requested time limit, we have to calculate the acceleration that will help us to achieve it (again the same formula is used but the unknown is the acceleration this time):

 // calculate new acceleration
 f32 firstHalfBounceDuration = mHalveFirstBounce ? mBounceDuration[0] : mBounceDuration[0] / 2;
 // s = 1/2 a * t^2 ... 2s / t^2 = a
 mAcceleration = (2.0f * INTERNAL_HEIGHT) / (firstHalfBounceDuration * firstHalfBounceDuration);

 Finally we can calculate the parameters for each bounce:

 // calculate initial bounce velocities
 for (s32 i = 0; i < mBounces; i++)
 {
  // v = v0 + at ... on the top of bounce the v equals zero => v0 = -at
  // if bounce starts halved (on top) than its initial velocity is zero
  // halve duration of each bounce (as it contains the way up and down)
  if (i == 0 && aHalveFirstBounce)
   mBouceVelocity[i] = 0.0f;
  else
   mBouceVelocity[i] = mBounceDuration[i] / 2.0f * mAcceleration;
 }


 // change the sign of acceleration to point downwards
 mAcceleration = -mAcceleration;

 The debug output is now commented out:

 // debug output
 /*
 LOGD("Bounces: %i, Elasticity: %f, Acceleration: %f, Duration: %f, HalveFirstBounce %s",
   mBounces, mElasticity, mAcceleration, mDuration, mHalveFirstBounce ? "true" : "false");
 for (s32 i = 0; i < mBounces; i++)
 {
  LOGD("Bounce %i: height = %f, duration = %f, velocity = %f",
    i, mBounceHeight[i], mBounceDuration[i], mBouceVelocity[i]);
 }
 */
}

 The function is initialized now so we can start using it. There are three function - one tracks current position within requested time and is called tick(). Its parameter is time elapsed from last frame so you can feed it with your game loop timing steps. The second takes the value for current position and the last one returns value from any requested position. this one is the most important one and it is the place where things happens:

//------------------------------------------------------------------------
f32 TimingBounce::tick(f32 aDeltaTime)
{
 // adjust progress
 mDurationProgress += aDeltaTime;

 // return actual value
 return getAt(mDurationProgress);
}

//------------------------------------------------------------------------
f32 TimingBounce::getActual()
{
 return getAt(mDurationProgress);
}

//------------------------------------------------------------------------
f32 TimingBounce::getAt(f32 aDurationProgress)
{
 // check time bounds
 if (aDurationProgress < 0.0f)
  aDurationProgress = 0.0f;
 else if (aDurationProgress > mDuration)
  aDurationProgress = mDuration;

 After check of bounds we have to find index of the bounce we are currently in:

 s32 index = 0;
 f32 totalDuration = 0.0f;

 // get index to particular bounce
 while(index < mBounces && aDurationProgress > totalDuration + mBounceDuration[index])
 {
  totalDuration += mBounceDuration[index];
  ++ index;
 }

 // get duration within bounce (if not the first one)
 aDurationProgress = aDurationProgress - totalDuration;

 and then we can calculate the height in range 0 - INTERNAL_HEIGHT and normalize it to 0-1:

 f32 height = 0.0f;
 if (index == 0 && mHalveFirstBounce)
 {
  // height = height + 1/2 * mAcceleration * aDurationProgress^2
  height = INTERNAL_HEIGHT + mAcceleration * (aDurationProgress * aDurationProgress) / 2.0f;

 }
 else
 {
  // height = mBounceVelocity * aDurationProgress + 1/2 * mAcceleration * aDurationProgress^2
  // height = aDurationProgress * (mBounceVelocity + 1/2 * mAcceleration * aDurationProgress)
  height = aDurationProgress * (mBouceVelocity[index] + (mAcceleration * aDurationProgress) / 2.0f);
 }


 return height / INTERNAL_HEIGHT;
}

 For completeness here are also getter functions:

//------------------------------------------------------------------------
f32 TimingBounce::getDuration()
{
 return mDuration;
}

//------------------------------------------------------------------------
f32 TimingBounce::getDurationProgress()
{
 return mDurationProgress;
}

//------------------------------------------------------------------------
s32 TimingBounce::getBounces()
{
 return mBounces;
}

//------------------------------------------------------------------------
f32 TimingBounce::getElasticity()
{
 return mElasticity;
}

//------------------------------------------------------------------------
f32 TimingBounce::getAcceleration()
{
 return mAcceleration;
}

} /* namespace Engine */
} /* namespace SBC */

Usage

 To demonstrate the use our bouncing function all you have to do for example is something like this (this will produce the output you have seen on the first graph):

 TimingBounce b;
 b.initialize(3.0f, 3, -1.0f, true);

 for (f32 i = 0.0f; i < 3.0f; i = i + 0.01f)
  LOGD("height: %f", b.tick(0.01f));

Conclusion

 So, we created bouncing function that is flexible enough. It also hides all its details (series of functions) inside and the user just initializes it with desired values. You can download the source here.

Shards - Work In Progress I

This is short info on our upcoming game - Shards - we are working on. The game will be clone of well known arcade classic with glassy look and very nice fractal backgrounds. The music in video is just a placeholder I found on the web - it sounds to make me sure the sound engine works.

 Making the game we are using these technologies:

• box2D for physics,
• notice the usage of our universal box2D debug draw that works for Open GL ES 1.x and 2.0,
• our cross platform engine -  the video is taken from desktop Windows while the game runs on Android as well,
• PicOpt - our sprite atlas creation tool that is free to download,
• for Android NDK: textures are loaded through this way, while sound (not too much of them in the game presently) is coded like this,
• for ads we plan to utilize our simple ads manager.

Creating Ads Manger for Android - Part 5 - Implementing Leadbolt

previous parts

• Creating Ads Manger for Android - Part 1 - First part of SBCAdManager 
• Creating Ads Manger for Android - Part 2 - Finishing SBCAdManager
• Creating Ads Manger for Android - Part 3 - Implementing AdMob
• Creating Ads Manger for Android - Part 4 - Implementing Madvertise

 In previous part we implemented Madvertise. This time we will do the same with Leadbolt. While AdMob and Madvertise pays you for click, Leadbolt pays you usually for action the user has to do. So you may encounter CPA term which stands for Cost per Action instead well known CPC (cost per Click). If I convert my latest revenue to CPC I get very low value 0.01 - 0.02 while AdMob is 0.035 in average. Beside this Zone Alarm for Android is warning users that your app contains AdwareAndroidos.leadbold... Is it still worth to implement it? Ok, I am using only banners, not any kind of ads like push notifications and so on, so my users will not get angry. The app passed registration at Slideme.org or Amazon.com without problems. And the size of the banner is smaller than AdMob or Madvertise banners. Thus, for our game Deadly Abyss 2 is Leadbolt only network if playing on mobile phone (if playing on tablet then AdMob, Madvertise and Leadbolt are rotating).
 Finally, we are making ad manager to handle multiple networks, so it is not wise to rely only on one network.
 If you intent to use Leadbolt you can register through this link. If you do so, I will get some small reward from them :-)

Adding Leadbolt SDK

 This should be no problem. Leadbolt has very good and simple manual. It is located under App Developer SDKs in HELP/FAQS section. Actually it is the same as AdMob integration - copy .jar with SDK into libs folder and then adjust Build Path in Project Properties (right click on project name in Eclipse). Then Add JARs...

Adjusting manifest

 As for previous ad networks we have to adjust manifest file with permissions. Leadbolt has three required permissions: INTERNET, ACCESS_NETWORK_STATE and READ_PHONE_STATE. The first two we already have from times of AdMob implementation. There are three optional permissions: ACCESS_COARSE_LOCATION, ACCESS_FINE_LOCATION and ACCESS_ LOCATION_EXTRA_COMMANDS. The coarse location we already allowed for Madvertise so we adjust the manifest like this:

  <!-- additional LeadBolt permissions -->
  <uses-permission android:name="android.permission.READ_PHONE_STATE" /> 
  <uses-permission android:name="android.permission.ACCESS_FINE_LOCATION"/> 
  <uses-permission android:name="android.permission.ACCESS_LOCATION_EXTRA_COMMANDS"/> 

Adjusting constatns

 While most of the other networks has some way how to set refresh rate for Leadbolt you have to do it by yourself. So in the file with constants (SBCAdsConstatnts.java) we will define these lines:

 // Leadbolt
 public static final String LEADBOLT_UNIT_ID = "YOUR_LEADBOLT_ID_HERE";
 public static final long LEADBOLT_REFRESH_RATE = 1000 * 90 * 1;

 The first line contains the ID your ad unit is assigned by Leadbolt. The second line defines refresh rate in millis - here 1,5 minute.

LeadboltSystem.java

 Now let's start implementation. As usual the imports and fields come first:

package com.sbcgames.sbcads;import com.pad.android.iappad.AdController;import com.pad.android.listener.AdListener;import com.sbcgames.sbcengine.SBCEngine;import android.util.Log;import android.view.KeyEvent;import android.view.ViewGroup;public class LeadboltSystem implements SBCAdSystem, AdListener
{
 private final String SYSTEM_NAME = "LEADBOLT ";
 private SBCAdEventListener mListener = null;
 private AdController mAdView;
 private final ViewGroup mLayout;
 private Runnable mR = null;
 private SBCEngine mSBCEngine = null;

 The constructor is very simple:

 // ------------------------------------------------------------------------
 public LeadboltSystem(SBCEngine aSBCEngine, ViewGroup aLayout)
 {
  mSBCEngine = aSBCEngine;
  mLayout = aLayout;
 }

SBCAdSystem implementation

 Next follows implementation of our SBCAdSystem interface:

 //------------------------------------------------------------------------
 // SBCAdSystem
 //------------------------------------------------------------------------
 @Override
 public void start()
 {
  final LeadboltSystem system = this;

  mR = new Runnable()
  {
   public void run()
   {
    Log.d("AdsSystem", SYSTEM_NAME + "Creating AdController and asking for Ad");

    if (mAdView != null)
    {
     stop();
     destroy();
     mAdView = null;
    }
    
    mAdView = new AdController(mSBCEngine, SBCAdsConstants.LEADBOLT_UNIT_ID, system);
    mAdView.loadAd();
    
    mLayout.postDelayed(this, SBCAdsConstants.LEADBOLT_REFRESH_RATE);
   }
  };

  mLayout.postDelayed(mR, 0);
 }

 Here is problem that I encountered: to refresh ad, calling to destroyAd() (called in destroy() method) and then calling to loadAd() should be enough. But the refreshing in this way did not work for me. So I am destroying the mAdView (the AdController object) every time and creating new one. I posted question to forum and I got reply from user called jay-z. While the above method works, I will try his code and update this article accordingly if it will work for me too.

 Here is implementation of next methods - nothing special here:

 //------------------------------------------------------------------------
 @Override
 public void stop()
 {
  if (mR != null)
  {
   Log.d("AdsSystem", SYSTEM_NAME + "removing listener");
   mLayout.removeCallbacks(mR);
  }
 }

 //------------------------------------------------------------------------
 @Override
 public void destroy()
 {
  if (mAdView != null)
  {
   mAdView.destroyAd();
  }
 }

 //------------------------------------------------------------------------
 @Override
 public void setEventListener(SBCAdEventListener aListener)
 {
  mListener = aListener;
 }

 In last two parts when implementing AdMob and Madvertise we left our keyDown implementation empty. For Leadbolt we have to handle back key. This is the reason why we have this method in interface. Of course, to avoid implementation in every ad system we could create abstract class between interface and concrete implementation (that will do nothing) and override it only when we need specialised behavior - I will leave this small change on your choice:

 //------------------------------------------------------------------------
 @Override
 public boolean keyDown(final int aKeyCode, final KeyEvent aEvent)
 {
  if (aKeyCode == KeyEvent.KEYCODE_BACK)
  {
   if (mAdView.onBackPressed())
   {
    Log.d("AdsSystem", SYSTEM_NAME + "back key pressed");
    return true;
   }
  }
  
  return false;
 }

AdListener implementation

 Leadbolt, as well as other ad networks we have seen so far has its own interface for callbacks. The name is AdListener - the same as for AdMob. But this time it has different set of methods. Their implementation is empty for most of the them. The one that is important is onAdClicked(). Despite AdMob or Madvertise, the Leadbolt does not start any new Activity that would pause your current activity - your game. So, you have to do it by yourself. We are calling sendMessage() method. This method is general method in my engine to send messages to Java part of the engine from other Java parts or from NDK. Thanks to this I can ask engine to do lot of things just with different method's arguments.

 //------------------------------------------------------------------------
 // LEADBOLT
 //------------------------------------------------------------------------
 @Override
 public void onAdClicked()
 {
  stop();
  mSBCEngine.sendMessage(SBCEngine.MESSAGE_OUT_PAUSE, 0, 0);
  Log.d("AdsSystem", SYSTEM_NAME + "onAdClicked");
 }
 
 //------------------------------------------------------------------------
 @Override
 public void onAdAlreadyCompleted()
 {
  Log.d("AdsSystem", SYSTEM_NAME + "onAdAlreadyCompleted");
 }
  
 //------------------------------------------------------------------------
 @Override
 public void onAdClosed()
 {
  Log.d("AdsSystem", SYSTEM_NAME + "onAdClosed");
 }

 //------------------------------------------------------------------------
 @Override
 public void onAdCompleted()
 {
  Log.d("AdsSystem", SYSTEM_NAME + "onAdCompleted");
 }

 //------------------------------------------------------------------------
 @Override
 public void onAdFailed()
 {
  Log.d("AdsSystem", SYSTEM_NAME + "onAdFailed");
  mListener.onFailed(this);
 }

 //------------------------------------------------------------------------
 @Override
 public void onAdHidden()
 {
  Log.d("AdsSystem", SYSTEM_NAME + "onAdHidden");
 }

 //------------------------------------------------------------------------
 @Override
 public void onAdLoaded()
 {
  Log.d("AdsSystem", SYSTEM_NAME + "onAdLoaded");
 }

 //------------------------------------------------------------------------
 @Override
 public void onAdPaused()
 {
  Log.d("AdsSystem", SYSTEM_NAME + "onAdPaused");
 }

 //------------------------------------------------------------------------
 @Override
 public void onAdProgress()
 {
  Log.d("AdsSystem", SYSTEM_NAME + "onAdProgress");
 }

 //------------------------------------------------------------------------
 @Override
 public void onAdResumed()
 {
  Log.d("AdsSystem", SYSTEM_NAME + "onAdResumed");
 }}

Conclusion

 This is all for Leadbolt implementation. This was also last part of this little series. We created simple but extensible ad manager. Now it is up to you to enhance it and add other ad networks.