Affine transformations and their inverse

When you're programming games or other 3d applications using OpenGL or DirectX, it is often required to use affine transformation matrices to describe transformations in space (4x4 matrices and the like). There is not a lot of documentation about this online, and most implementations I've seen, have some sort of hack. In this tutorial, I'll describe what affine transformations are, and more importantly, how to invert them correctly and efficiently. It is assumed that the reader knows what a matrices are and how to multiply them.

The affine transformation
Imagine you have a ball lying at (1,0) in your coordinate system. You want to move this ball to (0,2) by first rotating the ball 90 degrees to (0,1) and then moving it upwards with 1. This transformation is described by a rotation and translation. The rotation is: $$ \left[\begin{array}{cc} 0 & -1\\ 1 & 0\\ \end{array}\right] $$ and the translation is (0,1). To apply this transformation to a vector $\vec{x}$, we do: $$\vec{x}^\prime = R \vec{x} + \vec{T}$$ where R is a rotation matrix, and T is a translation vector. This is called an affine transformation.

If you're in 2d space, there is no 2x2 matrix that will do this transformation for all points. However, if we go one dimension higher, to a 3x3 matrix, you can! That's why OpenGL uses 4x4 matrices to describe 3d transformations, as we'll see later. 

The matrix representation
The best way to explain how to make this matrix, is to give the matrix for the example above.

$$ \left[\begin{array}{ccc} 0 & -1 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \\ \end{array}\right]  $$

As you can see, the left upper block is the rotation matrix, and to the right going downwards we have our translation. Because it's a 3x3 matrix now, we have to apply it to a 3d vector. We take the vector we had, $(1,0)$, and set the third component to 1. See what happens:

$$ \left[\begin{array}{ccc} 0 & -1 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \\ \end{array}\right] \begin{pmatrix} 1\\0\\1 \end{pmatrix} = \begin{pmatrix} 0\\2\\1 \end{pmatrix} $$

This gives the result we wanted! If you look closer to the matrix multiplication, we see why this works. The trick is to set the last component of the vector to 1, so that the translation just gets added. In a short-hand notation the matrix and vector look like this:

$$ \left[\begin{array}{c|c} R & T \\ \hline 0 & 1 \\ \end{array}\right] \begin{pmatrix} x\\ \hline 1 \end{pmatrix}=\begin{pmatrix} x^\prime\\ \hline 1 \end{pmatrix}$$

Inverting an affine transformation matrix
Sometimes it is very imporant to invert an affine transformation, for example to transform back from world space to object space. A naive approach is to just write a function that inverts 3x3 or 4x4 matrices. This is very inefficient,  because there are some nice properties we can use.


If we think about what happens when we apply the affine transformation matrix, we rotate first over an angle $\alpha$, and then translate over $(T_x, T_y)$. So the inverse should translate first with $(-T_x, -T_y)$, and then rotate over $-\alpha$. Unfortunately, that's not what happens. What does happen is that the rotation is always applied first. So we have to correct for that by modifying our translation. A derivation:

$$
\begin{array}
\vec{x}^\prime = R\vec{x} + T \\
\vec{x}^\prime - T = R\vec{x} \\
R^{-1}(\vec{x}^\prime - T) = \vec{x}\\
\end{array}
$$

So to get back the original vector $\vec{x}$, we have a new affine transformation:

$$ \vec{x} = R^{-1}\vec{x}^\prime  - (R^{-1}T) $$

What we have to do now is calculate the inverse of a rotation matrix and using that result, calculate our new translation.


Let's recall how a general rotation matrix in 2d looks like:

$$ \left[\begin{array}{cc} \cos(\alpha) & - \sin(\alpha) \\ \sin(\alpha) & \cos(\alpha) \\ \end{array}\right] $$

Because a rotation matrix is unitary, the inverse of a rotation matrix is equal to its transpose, so inverting can be done very quickly:

$$ \left[\begin{array}{cc} \cos(\alpha) & \sin(\alpha) \\ -\sin(\alpha) & \cos(\alpha) \\ \end{array}\right] $$

Now all we have to do is apply this to T, to get all the components for our inverse matrix:

$$ \left[\begin{array}{c|c} R^{-1} & R^{-1}T \\ \hline 0 & 1 \\ \end{array}\right] \begin{pmatrix} x^\prime\\ \hline 1 \end{pmatrix}$$

Putting it together

As we've seen, general 2d affine transformation matrices look like

$$ \left[\begin{array}{ccc} \cos(\alpha) & - \sin(\alpha) & T_x \\ \sin(\alpha) & \cos(\alpha) & T_y \\ 0 & 0 & 1 \\ \end{array}\right] $$

Applying the strategy we've derived above, the inverse is:

$$ \left[\begin{array}{ccc} \cos(\alpha) & \sin(\alpha) & -T_x \cos(\alpha) - T_y \sin(\alpha) \\ -\sin(\alpha) & \cos(\alpha) & -T_y \cos(\alpha) + T_x \sin(\alpha) \\ 0 & 0 & 1 \\ \end{array}\right] $$


Expanding to 3d is trivial, since the same rules hold. For example, let's pick the rotation of $\theta$ over the axis $(0,1,0)$ and a translation $(1,2,3)$.

The matrix becomes:
$$ \left[\begin{array}{cccc} \cos(\theta) & 0 &  \sin(\theta) &1 \\ 0 & 1 & 0 & 2\\ -\sin(\theta) & 0 & \cos(\theta) & 3 \\ 0 & 0 & 0 & 1 \\ \end{array}\right] $$

And the inverse is:
$$
\left[


\begin{array}{cccc}
 \cos (\theta ) & 0 & -\sin (\theta ) & 3 \sin (\theta )-\cos (\theta ) \\
 0 & 1 & 0 & -2 \\
 \sin (\theta ) & 0 & \cos (\theta ) & -3 \cos (\theta )-\sin (\theta ) \\
 0 & 0 & 0 & 1
\end{array}

\right]

$$

These 4x4 matrices are the ones that OpenGL expects in functions like glMultMatrixf!

In order to use this knowledge in your code, you should write a matrix class that can 1) create a rotation matrix from an angle and axis 2) transpose a matrix and 3) be applied to a vector.


Conclusion
Hopefully this tutorial has helped you better grasp the concepts of affine transformations. We've seen the definition of these transformations and how to use those to find a shortcut for a quick inversion algorithm. If you have any questions, please let me know!

Facebook blacklisted me...

For a website I am building I want to have facebook authentication, which means that users don't have to make an account. In order to use their API, facebook forces you to make an actual profile on their website. With great reluctance, I made my profile page, getting flooded with requests and other messages instantly. Well, I thought, this is what I have to do to get my key. So then I went to the app registration page and I got the following message:

You can no longer create apps because our systems indicated that your account may not be authentic. Facebook requires users to provide their real first and last names, and fake accounts are a violation of our Statement of Rights and Responsibilities (SRR 4.1), even when used to host or test apps. Also note that maintaining multiple accounts, even if they are authentic, is also prohibited. If you would like to create a test user to test app functionality, you can do so here: http://developers.facebook.com/docs/test_users/. If you believe you have received this message in error, please submit an appeal: https://www.facebook.com/help/contact_us.php?id=140703502680919.

Seriously, WTF. After all that trouble I went through, their "systems" say my account is not authentic. What does that even mean, their systems? This completely baffles me, since I have dumped all sorts of personal stuff on there and I went through an SMS authentication. Nonetheless, their "systems" think I am lying.

 I am pretty pissed off right now. The API key proved to be one big carrot on a stick to lure me in. Now I have to scan government papers to actually prove I am who I am. If their oh so intelligent system doesn't think my passport is a fake, that is...

update: I have sent a heavily censored copy of my driver's license to facebook. I am un-blacklisted now.

Skills every programmer should have #1: Dynamic programming

During this course I'll try and describe several techniques and skills that every programming should have. Many of these subjects involve concepts that save a lot of time and provide easier solutions to problems than ad-hoc ones. If you have any suggestions, please let me know!

Dynamic programming

Dynamic programming is the first skill that every programmer should have. It can be used when you have a problem that can be split up into sub-problems that you've already calculated and cached. I have used it in numerous situations, including optimal control theory problems and Project Euler problems. An example:

Imagine you want to write an application that prints the factorial for every number up to N, so:

0! 1! 2! 3! ... N!

A naive solution would be

public class Main {
 public static long fac(int n) {
  if (n <= 1) {
   return 1;
  }

  return n * fac(n - 1);
 }

 public static void main(String[] args) {
  for (int i = 0; i < 10; i++) {
   System.out.println(fac(i));
  }
 }
}

This becomes very slow if N is large (in this example you can't make N too large, because the long overflows very quickly. Use BigInteger instead). However, if we look at the factorial function, we see that if we calculate 10!, we're recalculating 9!. We see that 10! = 10 * 9!. In general:

N! = N * (N-1)!

If we were to cache n! in a map, we'd be able to significantly reduce computation time. An improved solution:

public class Main {
 static Map<Integer, Long> facs = new HashMap<Integer, Long>();

 public static long fac(int n) {
  if (facs.containsKey(n)) {
   return facs.get(n);
  }
  
  if (n <= 1) {
   return 1;
  }

  long result = n * fac(n - 1);
  /* Add factorial to map. */
  facs.put(n, result);
  
  return result;
 }

 public static void main(String[] args) {

  for (int i = 1; i < 10; i++) {
   System.out.println(fac(i));
  }
 }
}

This is what's called dynamic programming and it is very useful to make seemingly infeasable solutions possible in exchange for memory. Let's look at a realistic example.

Best path in a triangle

Imagine you have a triangle like this:

   3
  7 4
 2 4 6
8 5 9 3

and you're aked to calculate the path with the optimal score. The score is calculated by adding all the numbers you go through. In this case the optimal score is 3 + 7 + 4 + 9 = 23. Note that this is problem 67 of the Euler Project, so if you want to try it for yourself first, you should stop reading here!

 This problem is easy to solve for small triangles, but for big triangles it becomes infeasable to calculate all the routes. We're now going to look at a triangle with a depth of 100. This means that there are 2^99 routes! Looking at the triangle above, we see that the value at the top is 3 + [the maximum of the subtree 7 and subtree 4].

This looks like a division into subproblems! If we were to cache the values of the tree at 7 and 4, we'd know the value at the top incredibly fast. The dynamic programming solution is thus as follows:

public class Main {
 /* Values at every point in the tree. */
 public static Map<Point, Integer> values;
 public static List<List<Integer>> tree;
 
 public static Integer getValue(Point p) {
  /* Check cache first. */
  if (values.containsKey(p)) {
   return values.get(p);
  }
  
  /* Boundary conditions. */
  if (p.y == tree.size() - 1) {
   return tree.get(p.y).get(p.x);
  }
  
  /* Get the values of the two subtrees. */
  Integer left = getValue(new Point(p.x, p.y + 1));
  Integer right = getValue(new Point(p.x + 1, p.y + 1));
  Integer value = tree.get(p.y).get(p.x) + Math.max(left, right);
  
  values.put(p, value);
  return value;  
 }

 public static void main(String[] args) {
  /* TODO: read tree from file. */
  
  System.out.println(getValue(new Point(0,0)));
 }

}

This solution is a sketch. I leave parsing the tree from a file as an exercise to the reader. Note that if you're serious about perfomance, using Integer and other boxed types is a bad idea. I would strongly recommend using the Trove High Performance Collections for the cache.

 Until next time!

Lazy loading of images in Listview

A common scenario is adding images to a Listview. For example, if you´re making a cocktail recipe app, you´d want a picture next to the cocktail name. Sometimes the images should be retrieved from the internet and then be displayed. Unfortunately, this is difficult to do right. If you´ve tried it, you´ve probably noticed performance hits, or some strange glitches. In this tutorial, I´ll show you how to download images and display them. We´ll also discuss some pitfalls, like recycling and concurrency.


Setting up the listview
I assume you already know how to define a row layout for a Listview and know about adapters.

Below is an example of an adapter for an RSS reader. The text data is retrieved from an Article class, which contains the title of the Article, the author and the publication date. To make the tutorial more clear, I have an explicit list of URLs that will be used for the images of each entry.

public class ListAdapter extends ArrayAdapter<Article> {
 private List<Article> articles;
 private Context context;
 private final LayoutInflater inflator;

 private static final String[] URLS = {
   "http://lh5.ggpht.com/_mrb7w4gF8Ds/TCpetKSqM1I/AAAAAAAAD2c/Qef6Gsqf12Y/s144-c/_DSC4374%20copy.jpg",
   "http://lh5.ggpht.com/_Z6tbBnE-swM/TB0CryLkiLI/AAAAAAAAVSo/n6B78hsDUz4/s144-c/_DSC3454.jpg",
   "http://lh3.ggpht.com/_GEnSvSHk4iE/TDSfmyCfn0I/AAAAAAAAF8Y/cqmhEoxbwys/s144-c/_MG_3675.jpg",
   "http://lh6.ggpht.com/_Nsxc889y6hY/TBp7jfx-cgI/AAAAAAAAHAg/Rr7jX44r2Gc/s144-c/IMGP9775a.jpg",
   "http://lh3.ggpht.com/_lLj6go_T1CQ/TCD8PW09KBI/AAAAAAAAQdc/AqmOJ7eg5ig/s144-c/Juvenile%20Gannet%20despute.jpg",
   "http://lh6.ggpht.com/_ZN5zQnkI67I/TCFFZaJHDnI/AAAAAAAABVk/YoUbDQHJRdo/s144-c/P9250508.JPG",
   "http://lh4.ggpht.com/_XjNwVI0kmW8/TCOwNtzGheI/AAAAAAAAC84/SxFJhG7Scgo/s144-c/0014.jpg",
   "http://lh6.ggpht.com/_lnDTHoDrJ_Y/TBvKsJ9qHtI/AAAAAAAAG6g/Zll2zGvrm9c/s144-c/000007.JPG",
   "http://lh6.ggpht.com/_qvCl2efjxy0/TCIVI-TkuGI/AAAAAAAAOUY/vbk9MURsv48/s144-c/DSC_0844.JPG",
   "http://lh4.ggpht.com/_4f1e_yo-zMQ/TCe5h9yN-TI/AAAAAAAAXqs/8X2fIjtKjmw/s144-c/IMG_1786.JPG",
   "http://lh6.ggpht.com/_iFt5VZDjxkY/TB9rQyWnJ4I/AAAAAAAADpU/lP2iStizJz0/s144-c/DSCF1014.JPG",
   "http://lh5.ggpht.com/_hepKlJWopDg/TB-_WXikaYI/AAAAAAAAElI/715k4NvBM4w/s144-c/IMG_0075.JPG",
   "http://lh6.ggpht.com/_OfRSx6nn68g/TCzsQic_z3I/AAAAAAABOOI/5G4Kwzb2qhk/s144-c/EASTER%20ISLAND_Hanga%20Roa_31.5.08_46.JPG",
   "http://lh6.ggpht.com/_ZGv_0FWPbTE/TB-_GLhqYBI/AAAAAAABVxs/cVEvQzt0ke4/s144-c/IMG_1288_hf.jpg",
   "http://lh6.ggpht.com/_a29lGRJwo0E/TBqOK_tUKmI/AAAAAAAAVbw/UloKpjsKP3c/s144-c/31012332.jpg",
   "http://lh3.ggpht.com/_55Lla4_ARA4/TB6xbyxxJ9I/AAAAAAABTWo/GKe24SwECns/s144-c/Bluebird%20049.JPG",
   "http://lh3.ggpht.com/_iVnqmIBYi4Y/TCaOH6rRl1I/AAAAAAAA1qg/qeMerYQ6DYo/s144-c/Kwiat_100626_0016.jpg",
   "http://lh6.ggpht.com/_QFsB_q7HFlo/TCItd_2oBkI/AAAAAAAAFsk/4lgJWweJ5N8/s144-c/3705226938_d6d66d6068_o.jpg",
   "http://lh5.ggpht.com/_JTI0xxNrKFA/TBsKQ9uOGNI/AAAAAAAChQg/z8Exh32VVTA/s144-c/CRW_0015-composite.jpg",
   "http://lh6.ggpht.com/_loGyjar4MMI/S-InVNkTR_I/AAAAAAAADJY/Fb5ifFNGD70/s144-c/Moving%20Rock.jpg",
   "http://lh4.ggpht.com/_L7i4Tra_XRY/TBtxjScXLqI/AAAAAAAAE5o/ue15HuP8eWw/s144-c/opera%20house%20II.jpg",
   "http://lh3.ggpht.com/_rfAz5DWHZYs/S9cstBTv1iI/AAAAAAAAeYA/EyZPUeLMQ98/s144-c/DSC_6425.jpg",
   "http://lh6.ggpht.com/_iGI-XCxGLew/S-iYQWBEG-I/AAAAAAAACB8/JuFti4elptE/s144-c/norvig-polar-bear.jpg",
   "http://lh3.ggpht.com/_M3slUPpIgmk/SlbnavqG1cI/AAAAAAAACvo/z6-CnXGma7E/s144-c/mf_003.jpg",
   "http://lh4.ggpht.com/_loGyjar4MMI/S-InQvd_3hI/AAAAAAAADIw/dHvCFWfyHxQ/s144-c/Rainbokeh.jpg",
   "http://lh4.ggpht.com/_yy6KdedPYp4/SB5rpK3Zv0I/AAAAAAAAOM8/mokl_yo2c9E/s144-c/Point%20Reyes%20road%20.jpg",
   "http://lh5.ggpht.com/_6_dLVKawGJA/SMwq86HlAqI/AAAAAAAAG5U/q1gDNkmE5hI/s144-c/mobius-glow.jpg",
   "http://lh3.ggpht.com/_QFsB_q7HFlo/TCItc19Jw3I/AAAAAAAAFs4/nPfiz5VGENk/s144-c/4551649039_852be0a952_o.jpg",
   "http://lh6.ggpht.com/_TQY-Nm7P7Jc/TBpjA0ks2MI/AAAAAAAABcI/J6ViH98_poM/s144-c/IMG_6517.jpg",
   "http://lh3.ggpht.com/_rfAz5DWHZYs/S9cLAeKuueI/AAAAAAAAeYU/E19G8DOlJRo/s144-c/DSC_4397_8_9_tonemapped2.jpg",
   "http://lh4.ggpht.com/_TQY-Nm7P7Jc/TBpi6rKfFII/AAAAAAAABbg/79FOc0Dbq0c/s144-c/david_lee_sakura.jpg",
   "http://lh3.ggpht.com/_TQY-Nm7P7Jc/TBpi8EJ4eDI/AAAAAAAABb0/AZ8Cw1GCaIs/s144-c/Hokkaido%20Swans.jpg",
   "http://lh3.ggpht.com/_1aZMSFkxSJI/TCIjB6od89I/AAAAAAAACHM/CLWrkH0ziII/s144-c/079.jpg",
   "http://lh5.ggpht.com/_loGyjar4MMI/S-InWuHkR9I/AAAAAAAADJE/wD-XdmF7yUQ/s144-c/Colorado%20River%20Sunset.jpg",
   "http://lh3.ggpht.com/_0YSlK3HfZDQ/TCExCG1Zc3I/AAAAAAAAX1w/9oCH47V6uIQ/s144-c/3138923889_a7fa89cf94_o.jpg",
   "http://lh6.ggpht.com/_K29ox9DWiaM/TAXe4Fi0xTI/AAAAAAAAVIY/zZA2Qqt2HG0/s144-c/IMG_7100.JPG",
   "http://lh6.ggpht.com/_0YSlK3HfZDQ/TCEx16nJqpI/AAAAAAAAX1c/R5Vkzb8l7yo/s144-c/4235400281_34d87a1e0a_o.jpg",
   "http://lh4.ggpht.com/_8zSk3OGcpP4/TBsOVXXnkTI/AAAAAAAAAEo/0AwEmuqvboo/s144-c/yosemite_forrest.jpg",
   "http://lh4.ggpht.com/_6_dLVKawGJA/SLZToqXXVrI/AAAAAAAAG5k/7fPSz_ldN9w/s144-c/coastal-1.jpg",
   "http://lh4.ggpht.com/_WW8gsdKXVXI/TBpVr9i6BxI/AAAAAAABhNg/KC8aAJ0wVyk/s144-c/IMG_6233_1_2-2.jpg",
   "http://lh3.ggpht.com/_loGyjar4MMI/S-InS0tJJSI/AAAAAAAADHU/E8GQJ_qII58/s144-c/Windmills.jpg",
   "http://lh4.ggpht.com/_loGyjar4MMI/S-InbXaME3I/AAAAAAAADHo/4gNYkbxemFM/s144-c/Frantic.jpg",
   "http://lh5.ggpht.com/_loGyjar4MMI/S-InKAviXzI/AAAAAAAADHA/NkyP5Gge8eQ/s144-c/Rice%20Fields.jpg",
   "http://lh3.ggpht.com/_loGyjar4MMI/S-InZA8YsZI/AAAAAAAADH8/csssVxalPcc/s144-c/Seahorse.jpg",
   "http://lh3.ggpht.com/_syQa1hJRWGY/TBwkCHcq6aI/AAAAAAABBEg/R5KU1WWq59E/s144-c/Antelope.JPG",
   "http://lh5.ggpht.com/_MoEPoevCLZc/S9fHzNgdKDI/AAAAAAAADwE/UAno6j5StAs/s144-c/c84_7083.jpg",
   "http://lh4.ggpht.com/_DJGvVWd7IEc/TBpRsGjdAyI/AAAAAAAAFNw/rdvyRDgUD8A/s144-c/Free.jpg",
   "http://lh6.ggpht.com/_iO97DXC99NY/TBwq3_kmp9I/AAAAAAABcz0/apq1ffo_MZo/s144-c/IMG_0682_cp.jpg",
   "http://lh4.ggpht.com/_7V85eCJY_fg/TBpXudG4_PI/AAAAAAAAPEE/8cHJ7G84TkM/s144-c/20100530_120257_0273-Edit-2.jpg" };

 private static class ViewHolder {
  public ImageView iconView;
  public TextView nameTextView;
  public TextView bottomText;
 }

 public ListAdapter(Context context, int textViewResourceId,
   List<Article> articles) {
  super(context, textViewResourceId, articles);
  this.articles = articles;
  this.context = context;
  inflator = (LayoutInflater) context
    .getSystemService(Context.LAYOUT_INFLATER_SERVICE);

  BitmapManager.INSTANCE.setPlaceholder(BitmapFactory.decodeResource(
    context.getResources(), R.drawable.icon));
 }

 @Override
 public View getView(int position, View convertView, ViewGroup parent) {
  ViewHolder holder;

  if (convertView == null) {
   convertView = inflator.inflate(R.layout.article_row, null);

   TextView nameTextView = (TextView) convertView
     .findViewById(R.id.title);
   TextView bottomText = (TextView) convertView
     .findViewById(R.id.bottomtext);
   ImageView iconView = (ImageView) convertView
     .findViewById(R.id.article_icon);
   holder = new ViewHolder();
   holder.nameTextView = nameTextView;
   holder.bottomText = bottomText;
   holder.iconView = iconView;
   convertView.setTag(holder);
  } else {
   holder = (ViewHolder) convertView.getTag();
  }

  Article article = articles.get(position);
  holder.nameTextView.setText(article.getTitle());
  holder.bottomText.setText(article.getAuthor() + " | "
    + article.getPubDate());

  holder.iconView.setTag(URLS[position]);
  BitmapManager.INSTANCE.loadBitmap(URLS[position], holder.iconView, 32,
    32);

  return convertView;
 }
}

As you can see, I am recycling the view, because I only inflate from XML when convertView == null. I also store references to all the children views in a tag. Recycling and tagging greatly improves performance, as can be seen in this Google Conference video.

Downloading the bitmaps
A naive way to download a bitmap is to just make a http connection in the getView and set the bitmap using iconView.setImageBitmap(). This would cause severe lag, because the UI thread would have to wait until the image is downloaded. What we want is to download in a separate thread. We also want some kind of cache to store downloaded bitmaps.

All this can be done in a singleton BitmapManager. Here is the download function:

private Bitmap downloadBitmap(String url, int width, int height) {
  try {
   Bitmap bitmap = BitmapFactory.decodeStream((InputStream) new URL(
     url).getContent());
   bitmap = Bitmap.createScaledBitmap(bitmap, width, height, true);
   cache.put(url, new SoftReference<Bitmap>(bitmap));
   return bitmap;
  } catch (MalformedURLException e) {
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  }

  return null;
 }

I don't know if this is the optimal way to download a file, so if you know a better way, please leave a message. As you can see, the bitmap is stored in cache, which is defined as Map<String, SoftReference<Bitmap>> cache;. We are using a SoftReference, because we want the bitmap to be garbage collected if the VM is low on memory.

The recycle trap
As I've mentioned before, the row view can be recycled. This means that, if you're scrolling, the view of a row that slides off the screen, can be used as the view of a row that comes into the screen. For example, row 1 disappears and row 3 appears during scrolling. When row 1 was on the screen, the download of the image started. Now imagine that the downloaded of the image of row 1 takes a very long time. When row 3 appears, the image of row 3 is put into the queue. It may happen that this download finishes before the one of row 1, which means that the picture of row 3 will be the one of row 1.

Row 1 visible: start download of image 1
Scrolling
Row 3 visible (recycled view of row 1): start download of image 3
Download of image 3 done: row 3 image set to image 3
Download of image 1 done: row 3 image set to image 1

In order to avoid these recycling issues, we have to store the URL that is lastly associated with the ImageView. If a download is completed, but is not associated with the view anymore (image 1, in the example above), the download is ignored. This is the association map: Map<ImageView, String> imageViews = Collections.synchronizedMap(new WeakHashMap<ImageView, String>());.

Retrieving the bitmap

 public void loadBitmap(final String url, final ImageView imageView,
   final int width, final int height) {
  imageViews.put(imageView, url);
  Bitmap bitmap = getBitmapFromCache(url);

  // check in UI thread, so no concurrency issues
  if (bitmap != null) {
   Log.d(null, "Item loaded from cache: " + url);
   imageView.setImageBitmap(bitmap);
  } else {
   imageView.setImageBitmap(placeholder);
   queueJob(url, imageView, width, height);
  }
 }

The first thing we do when we load the bitmap, is associating the URL with the ImageView. Then we see if the bitmap is in the cache. If so, we load it from cache, or else we queue the download.
It should be noted that the loadBitmap function is called in the UI thread, which means that we don't have to check if the imageView is recycled and we can call functions like setImageBitmap directly.

The working thread
All that's left now is to call the downloadBitmap function from a new thread. Most code I saw online just spawns a new thread, but that can become very inefficient. Imagine that the Listview contains 500 items: that would mean that 500 threads would be spawned! Instead, we use the ExecutorService class from the Java Concurrency framework. We create a fixed thread pool (newFixedThreadPool) with 5 items (this number is arbitrary, I haven't tested which amount is optimal), which means that there will be up to five images that are downloaded at the same time. All the other downloads are stored in an unbounded queue.

public void queueJob(final String url, final ImageView imageView,
   final int width, final int height) {
  /* Create handler in UI thread. */
  final Handler handler = new Handler() {
   @Override
   public void handleMessage(Message msg) {
    String tag = imageViews.get(imageView);
    if (tag != null && tag.equals(url)) {
     if (msg.obj != null) {
      imageView.setImageBitmap((Bitmap) msg.obj);
     } else {
      imageView.setImageBitmap(placeholder);
      Log.d(null, "fail " + url);
     }
    }
   }
  };

  pool.submit(new Runnable() {
   @Override
   public void run() {
    final Bitmap bmp = downloadBitmap(url, width, height);
    Message message = Message.obtain();
    message.obj = bmp;
    Log.d(null, "Item downloaded: " + url);

    handler.sendMessage(message);
   }
  });
 }

This code adds a new Runnable to the queue, which downloads the bitmap. Then it sends a message to a handler. A handler is used because all interactions with the UI have to be done in the UI thread. This means that we cannot directly set the image bitmap. A handler should be created in the thread the message will be handled in, so that's why we have to move the code outside of the Runnable anonymous class.

In handleMessage the bitmap is retrieved from msg.obj. The bitmap is only set if the current URL is the last one to be associated with the ImageView. If the download failed for some reason, a placeholder is used.

Conclusion
And there you have it. We've made a lazy loading bitmap manager that works with recycled listviews. Some things could be done to improve performance even more, for example cancelling downloads if the view is destroyed and preventing downloading the same file at the same time. Anyhow, if you found this tutorial helpful, please leave a message :)


Full code

public enum BitmapManager {
 INSTANCE;

 private final Map<String, SoftReference<Bitmap>> cache;
 private final ExecutorService pool;
 private Map<ImageView, String> imageViews = Collections
   .synchronizedMap(new WeakHashMap<ImageView, String>());
 private Bitmap placeholder;

 BitmapManager() {
  cache = new HashMap<String, SoftReference<Bitmap>>();
  pool = Executors.newFixedThreadPool(5);
 }

 public void setPlaceholder(Bitmap bmp) {
  placeholder = bmp;
 }

 public Bitmap getBitmapFromCache(String url) {
  if (cache.containsKey(url)) {
   return cache.get(url).get();
  }

  return null;
 }

 public void queueJob(final String url, final ImageView imageView,
   final int width, final int height) {
  /* Create handler in UI thread. */
  final Handler handler = new Handler() {
   @Override
   public void handleMessage(Message msg) {
    String tag = imageViews.get(imageView);
    if (tag != null && tag.equals(url)) {
     if (msg.obj != null) {
      imageView.setImageBitmap((Bitmap) msg.obj);
     } else {
      imageView.setImageBitmap(placeholder);
      Log.d(null, "fail " + url);
     }
    }
   }
  };

  pool.submit(new Runnable() {
   @Override
   public void run() {
    final Bitmap bmp = downloadBitmap(url, width, height);
    Message message = Message.obtain();
    message.obj = bmp;
    Log.d(null, "Item downloaded: " + url);

    handler.sendMessage(message);
   }
  });
 }

 public void loadBitmap(final String url, final ImageView imageView,
   final int width, final int height) {
  imageViews.put(imageView, url);
  Bitmap bitmap = getBitmapFromCache(url);

  // check in UI thread, so no concurrency issues
  if (bitmap != null) {
   Log.d(null, "Item loaded from cache: " + url);
   imageView.setImageBitmap(bitmap);
  } else {
   imageView.setImageBitmap(placeholder);
   queueJob(url, imageView, width, height);
  }
 }

 private Bitmap downloadBitmap(String url, int width, int height) {
  try {
   Bitmap bitmap = BitmapFactory.decodeStream((InputStream) new URL(
     url).getContent());
   bitmap = Bitmap.createScaledBitmap(bitmap, width, height, true);
   cache.put(url, new SoftReference<Bitmap>(bitmap));
   return bitmap;
  } catch (MalformedURLException e) {
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  }

  return null;
 }
}

In case you're wondering, an enum is the preferred way to create a singleton class.

A cutscene framework for Android - part 3

We've reached the third and final part of the tutorial on how to make cutscenes. Now that we've already defined Actors and Animations, we just have to define the Cutscene. The cutscene should consist of a list of actors, the current frame and the frame at which the cutscene ends. Animations don't have to be included explicitly, because they are part of the Actor class.

You may ask why we need to explicitly define an end frame. We could also look at the frame at which all the animations of each actor have finished. If we set that frame as the end frame, the cutscene is cut off immediately after the last transition. This leaves no time to actually see what's going on. That's why we use an end frame.

public class Cutscene {
 private Set<Actor> actors;
 private int endFrame;
 private int currentFrame;
 
 public Cutscene(Context context, int cutsceneResource) {
  load(context, cutsceneResource);
  currentFrame = 0;
 }
 
 public boolean isActive() {
  return currentFrame <= endFrame;
 }
 
 public Set<Actor> getActors() {
  return actors;
 }
 
 public void update() {
  if (!isActive()) {
   return;
  }
  
  for (Actor actor : actors) {
   actor.update();
  }
  
  currentFrame++;
 }
 
 public void draw(Canvas canvas) {
  for (Actor actor : actors) {
   actor.draw(canvas);
  }
 }
} 

As you can see, the Cutscene class is pretty straightforward. Using the framework so far, we can construct a cutscene from source code, with relative ease. It would be even better if we could just read it in from an XML file. For example, look at the following structure:

<?xml version="1.0" encoding="UTF-8"?>
<cutscenes>
 <cutscene end="140">
  <actor type="text" name="Intro" x="10.0" y="40.0"
   visible="true" text="This is the starting text.">
   <animation type="text" start="50" text="@string/anim_text" />
  </actor>
  <actor type="bitmap" name="Player" visible="true" x="0.0" y="50.0" bitmap="@drawable/player">
            <animation type="translate" start="4" end="60" from_x="0.0" from_y="50.0" to_x="100.0" to_y="50.0" />
  </actor>
 </cutscene>
</cutscenes>

All the elements of a simple scene are there: there is a text actor that displays two lines of text and a player bitmap that is moved across the screen. I've added two different ways to add text: you either hardcode it, or you give a reference to a string. The latter is recommended to support internationalisation.

I've given each actor a name, so that you can easily add additional information from source code. For example, in my project the player bitmap is a subrectangle of the resource @drawable/player. When this cutscene is parsed, I look for the actor with the name Player, and I substitute the bitmap. If you want to have a custom bitmap, you should use bitmap="custom" in the XML.

Now we have to parse the file:

public void load(Context context, int id) {
    actors = new HashSet<Actor>();
    
    XmlResourceParser parser = context.getResources().getXml(id);
    try {
        int eventType = parser.getEventType();
        
        Actor currentActor = null;
        
        while (eventType != XmlPullParser.END_DOCUMENT) {
            if (eventType == XmlPullParser.START_TAG) {
                if (parser.getName().equals("cutscene")) {
                    endFrame = parser.getAttributeIntValue(null, "end", 0);
                }
                
                if (parser.getName().equals("actor")) {
                    String type = parser.getAttributeValue(null, "type");
                    String name = parser.getAttributeValue(null, "name");
                    float x = parser.getAttributeFloatValue(null, "x", 0);
                    float y = parser.getAttributeFloatValue(null, "y", 0);
                    boolean visible = parser.getAttributeBooleanValue(null,
                    "visible", false);
                    
                    /* Read type specifics. */
                    if (type.equals("text")) {
                        String text = parser
                        .getAttributeValue(null, "text");
                        int res = parser.getAttributeResourceValue(null,
                        "text", -1);
                        if (res != -1) {
                            text = context.getResources().getString(res);
                        }
                        
                        // TODO: do something for paint. */
                        Paint paint = new Paint(Paint.ANTI_ALIAS_FLAG);
                        paint.setColor(Color.WHITE);
                        currentActor = new TextActor(name, text,
                        new Vector2f(x, y), paint);
                        currentActor.setVisible(visible);
                    }
                    
                    if (type.equals("bitmap")) {
                        Bitmap bitmap = null;
                        if (!parser.getAttributeValue(null, "bitmap")
                        .equals("custom")) {
                            int bitmapID = parser
                            .getAttributeResourceValue(null,
                            "bitmap", -1);
                            bitmap = BitmapFactory.decodeResource(
                            context.getResources(), bitmapID);
                        }
                        
                        currentActor = new BitmapActor(name, bitmap,
                        new Paint());
                        currentActor.setVisible(visible);
                        currentActor.getTransform().setTranslate(x, y);
                    }
                    
                    if (currentActor != null) {
                        actors.add(currentActor);
                    }
                }
                
                if (parser.getName().equals("animation")) {
                    String type = parser.getAttributeValue(null, "type");
                    int start = parser.getAttributeIntValue(null, "start",
                    0);
                    int end = parser.getAttributeIntValue(null, "end",
                    start);
                    
                    if (type.equals("text")) {
                        String text = parser
                        .getAttributeValue(null, "text");
                        currentActor.addAnimation(new TextAnimation(text,
                        start));
                    }
                    
                    if (type.equals("translate")) {
                        float from_x = parser.getAttributeFloatValue(null,
                        "from_x", 0);
                        float from_y = parser.getAttributeFloatValue(null,
                        "from_y", 0);
                        float to_x = parser.getAttributeFloatValue(null,
                        "to_x", 0);
                        float to_y = parser.getAttributeFloatValue(null,
                        "to_y", 0);
                        currentActor.addAnimation(new TranslationAnimation(
                        new Vector2f(from_x, from_y), new Vector2f(
                        to_x, to_y), start, end));
                    }
                }
            }
            
            eventType = parser.next();
        }
        } catch (XmlPullParserException e) {
        e.printStackTrace();
        } catch (IOException e) {
        e.printStackTrace();
    }
}

This function reads the XML and creates a cutscene. I have left some things out, like defining a Paint in the XML, because I haven't implemented those myself. If you want to do such a thing, I would recommend creating another XML structure just for Paints. Then you can add a reference to the resource in the cutscene structure. As you can see, this framework is easily extendable.

And there you have it. In this tutorial you've seen how to build a framework for cutscenes. We've started with simple building blocks like animations and actors and finally we've seen how to put them together to make cutscenes and read these from XML files. I hope you liked it!

Adding dictionaries to Android keyboard

I recently installed CyanogenMod-7.1.0-RC1 for my Wildfire, and I noticed that some dictionaries are missing from the default Gingerbread keyboard. What this means is that although you can select for example Dutch as input language, there will be no word suggestions. In this post I'll show you how to add those missing dictionaries.

Acquiring dictionaries
The keyboard application is stored in the file /system/app/LatinIME.apk. Online, you can find different LatinIME's that have more dictionaries. I have compiled a list of dictionaries available to two custom roms:

CyanogenMod: da, de, en, es, fr, it, iw, ka, pt, ru, sv
GingerVillain: da, de, en, es, it, nb, nl, sv

There are more custom roms available that may have different languages and you could also try official roms from HTC or any other company that publishes Android phones. When you've found and downloaded a good rom, store the file system/app/LatinIME.apk found in the zip.

Now there are two options. The first is replacing LatinIME.apk and the second is modifying the original to support extra dictionaries. In my case, the two keyboards I wanted are English and Dutch, so for me replacing the CyanogenMod's LatinIME.apk with the one from GingerVillain was good enough. You can see below how to copy the file.

Adding a dictionary
To add something to an apk, we first need to extract the apk. This is done using apktool. Download and extract both apktool and the helper scripts (depending on your OS) to the same folder.

Also make sure that you have adb, the android debugger and that you've set your phone to USB debugging mode (look here if you don't know how to do that). To get adb you need to install the SDK platform tools (see here).

Put the LatinIME.apk with the dictionary you want in the folder where you've stored apktool and rename it to LatinIME_new.apk. When you've done that open a console (cmd.exe in Windows) and navigate to the folder where you've stored apktool.

adb pull /system/app/LatinIME.apk LatinIME_old.apk
apktool d LatinIME_old.apk old
apktool d LatinIME_new.apk new

Now that you've done that, you have two new folder: old and new. The old one contains the contents of the original LatinIME.apk and the new folder contains the dictionary you want. Go to the new directory and find res/raw-YOURLANG, where YOURLANG is the two letter abbreviation of your language. Now copy this directory to res folder in the old directory.

Now that you've added the file to the extracted apk, it's time to repackage it.

apktool b old LatinIME.apk

The newly generated LatinIME.apk contains your dictionary, along with all the old ones. Now we have to upload this file to your phone.

Updating the LatinIME.apk file
When you've got the LatinIME.apk you want, we can overwrite the file in your /system/app directory on your phone. Unfortunately, the /system folder is mounted read-only, so we have to remount it first. For the following steps, we make use of the adb again.

adb pull /system/app/LatinIME.apk LatinIME_backup.apk
adb remount
adb push LatinIME.apk /system/app/LatinIME.apk

The first line makes a backup. You can leave that out if you've already done so.

Conclusion
Now that you've updated your LatinIME.apk, you'll need the reboot your phone. After that, you're all set to use your new, fancy dictionary!

A cutscene framework for Android - part 2

In the last tutorial we've made a framework for basic animations, like translation and text changes. Now it's time to put them together to transform an actor.

The actor
An abstract actor is an object that has variables that can be transformed. In most cases, an actor can be drawn to the screen. For this tutorial, we'll assume that they all do. The actor class should at least contain a set of animations and a transformation matrix that defines how the model is drawn on the screen.

The actor also contains the elements that will be transformed by the animations, and therefore it should also be an AnimationChangedListener.

public abstract class Actor implements AnimationChangedListener {
 private final String name;
 private boolean visible;
 private Matrix transform;
 private Set<Animation> animations;

 public Actor(String name) {
  this.name = name;
  visible = false;
  animations = new HashSet<Animation>();
  transform = new Matrix();
 }

 public String getName() {
  return name;
 }

 public Matrix getTransform() {
  return transform;
 }

 public boolean isVisible() {
  return visible;
 }

 public void setVisible(boolean visible) {
  this.visible = visible;
 }

 /**
  * Adds an animation and links the actor as a listener.
  * 
  * @param animation
  *            Animation
  */
 public void addAnimation(Animation animation) {
  animations.add(animation);
  animation.addListener(this);
 }

 public void update() {
  for (Animation animation : animations) {
   animation.doTimeStep();
  }
 }
 
 public boolean isIdle() {
  for (Animation animation : animations) {
   if (!animation.isDone()) {
    return false;
   }
  }
  
  return true;
 }

 @Override
 public void valueChanged(Animation animation) {
  float[] old = new float[9];
  transform.getValues(old);

  switch (animation.getType()) {
  case POSITION:
   Vector2f trans = (Vector2f) animation.getCurrentValue();
   Vector2f diff = trans.sub(new Vector2f(old[Matrix.MTRANS_X],
     old[Matrix.MTRANS_Y]));
   transform.postTranslate(diff.getX(), diff.getY());
   break;
  case VISIBILITY:
   visible = (Boolean) animation.getCurrentValue();
   break;
  }
 }

 public final Vector2f getPosition() {
  float[] old = new float[9];
  transform.getValues(old);
  return new Vector2f(old[Matrix.MTRANS_X], old[Matrix.MTRANS_Y]);
 }

 public abstract void draw(Canvas canvas);

}

The base class Actor listens to two animations: a visibility animation and a translation animation. The exact implementation of the visibility animation is something I leave up to the reader, but it's just a simple switch at a certain frame. At this time, I use the Matrix class from Android to store the rotations, scaling and translations, but due to the lack of getters like getPosition or getRotation, I may replace this code with my own Matrix class. Alternatively, I could store the rotation, translation and scale in three different variables.

I have given the actor a name, so it can be identified at a later point, for debugging or for setting specifics in the source code (instead of the XML, we'll get to that).

The actor is abstract, because the draw method is not implemented. We'll look at two very useful derived classes now.

The text actor
The text actor is an actor that displays a piece of text on the screen. We'll use the drawText function of the Canvas for that. The class should also be an AnimationChangedListener, because it has to receive a notification when a TextAnimation changes the text.

public class TextActor extends Actor implements AnimationChangedListener {
 private String text;
 private final Paint paint;

 public TextActor(String name, String text, Vector2f pos, Paint paint) {
  super(name);
  this.text = text;
  this.paint = paint;

  getTransform().setTranslate(pos.getX(), pos.getY());
 }
  
 public Paint getPaint() {
  return paint;
 }

 @Override
 public void valueChanged(Animation animation) {
  if (animation.getType() == AnimationType.TEXT) {
   text = (String) animation.getCurrentValue();
  }

  super.valueChanged(animation);
 }

 @Override
 public void draw(Canvas canvas) {
  Vector2f pos = getPosition();
  canvas.drawText(text, pos.getX(), pos.getY(), paint);
 }

}

The class also requires a Paint instance to draw the text correctly.

The bitmap actor
Probably the most important actor is the bitmap actor: this class draws a bitmap to the screen using a certain transformation (defined in the base class). The implementation is very simple:

public class BitmapActor extends Actor {
 private Bitmap bitmap;
 private final Paint paint;

 public BitmapActor(String name, Bitmap bitmap, Paint paint) {
  super(name);
  this.bitmap = bitmap;
  this.paint = paint;
  setVisible(false);
 }
 
 public void setBitmap(Bitmap bitmap) {
  this.bitmap = bitmap;
 }

 public void draw(Canvas canvas) {
  if (bitmap != null && isVisible()) {
   canvas.drawBitmap(bitmap, getTransform(), paint);
  }
 }
}

Now that we've seen how to make actors, what's left is to put them together in a cutscene. Additionally, we'll learn how to define these cutscenes in simple XML. See you next time!

A cutscene framework for Android - part 1

Not many Android games I have played have cutscenes or lots of animations. Perhaps because it is hard to make. A cutscene requires higher quality sprites or meshes which the developers may not have. Secondly, and more importantly, coding all the animations is tedious. However, cutscenes contribute to the immersion of the player, much more than a static wall of text! In this tutorial series I will show you how to create a framework to create animations for multiple objects with relative ease. Over the course of this tutorial we'll look at the building blocks for cutscenes, like animations, actors and finally we'll learn to use an XML-format to quickly describe them all.

The code is not Android-specific and could be used for other platforms as well.

Defining what we want
Before we start coding, we have to get a better sense of what we want to achieve. For a cutscene we want a scene with multiple objects. These objects could be anything, like a bitmap (sprite) or a piece of text. We will call these objects actors. Each actor can be modified while playing the cutscene by an animation. This could be anything as well, for example: a translation, a rotation, a change of text or a visibility toggle. An animation basically mutates a property of the actor. In this part, we'll look at how to define these animations.

Gathering some tools
First we'll check if Android has some handy tools for us. It seems that from Android 3.0 on, the Property Animation is very useful and may do about the same as the framework we're going to build. However, Android 3.0 is too much of a restriction for me. I want my games to run on Android phones from 2.1 on. Their second library called View animations is only applicable to views, so that's not useful for sprites rendered in OpenGL or bitmap rendered on a canvas.

So it seems we have to do some things ourselves. That's ok, it's not a lot of work. First we start with some tools, a class that describes a 2d vector with float values: Vector2f.

import android.os.Parcel;
import android.os.Parcelable;

public class Vector2f implements Parcelable {
 private final float x, y;

 public Vector2f(float x, float y) {
  super();
  this.x = x;
  this.y = y;
 }

 public Vector2f(Vector2f vec) {
  super();
  this.x = vec.x;
  this.y = vec.y;
 }

 public Vector2f(Vector2d vec) {
  super();
  this.x = vec.getX();
  this.y = vec.getY();
 }

 public float getX() {
  return x;
 }

 public float getY() {
  return y;
 }

 public Vector2f add(Vector2f vec) {
  return new Vector2f(x + vec.x, y + vec.y);
 }

 public Vector2f sub(Vector2f vec) {
  return new Vector2f(x - vec.x, y - vec.y);
 }

 public Vector2f scale(float f) {
  return new Vector2f(x * f, y * f);
 }

 public float lengthSquared() {
  return x * x + y * y;
 }

 @Override
 public String toString() {
  return "(" + x + ", " + y + ")";
 }

 @Override
 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + Float.floatToIntBits(x);
  result = prime * result + Float.floatToIntBits(y);
  return result;
 }

 @Override
 public boolean equals(Object obj) {
  if (this == obj)
   return true;
  if (obj == null)
   return false;
  if (getClass() != obj.getClass())
   return false;
  Vector2f other = (Vector2f) obj;
  if (Float.floatToIntBits(x) != Float.floatToIntBits(other.x))
   return false;
  if (Float.floatToIntBits(y) != Float.floatToIntBits(other.y))
   return false;
  return true;
 }

 public Vector2f(Parcel in) {
  x = in.readInt();
  y = in.readInt();
 }

 @Override
 public int describeContents() {
  return 0;
 }

 public static final Parcelable.Creator<Vector2f> CREATOR = new Parcelable.Creator<Vector2f>() {
  @Override
  public Vector2f createFromParcel(Parcel in) {
   return new Vector2f(in);
  }

  @Override
  public Vector2f[] newArray(int size) {
   return new Vector2f[size];
  }
 };

 @Override
 public void writeToParcel(Parcel dest, int flags) {
  dest.writeFloat(x);
  dest.writeFloat(y);

 }

}

This is a thread-safe 2d vector implementation that's parcelable (useful if you want to store a vector using onSaveInstanceState). You can also see that a class Vector2d is mentioned, which is the same class only with ints instead of floats. I use Vector2d for positions in a grid.

Next in line is defining an Animation. This will be the abstract framework on top of which all the possible animations are built. It should certainly have the start frame, the end frame and the current frame. The framerate itself is determined by the main loop of the application (a nice tutorial can be found here). The Animation classes will all transform a single variable (this can be expanded) between those two keyframes. To identify which type of variable is transformed, I use an Enum. You could also use instanceof. 

public abstract class Animation {
 private final int startFrame;
 private final int endFrame;
 private int currentFrame;
 private AnimationType type;
 private List<AnimationChangedListener> listeners;

 public Animation(int startFrame, int endFrame, AnimationType type) {
  super();
  this.startFrame = startFrame;
  this.endFrame = endFrame;
  this.type = type;

  currentFrame = 0;
  listeners = new ArrayList<AnimationChangedListener>();
 }

 public AnimationType getType() {
  return type;
 }

 public boolean isActive() {
  return currentFrame >= startFrame && currentFrame <= endFrame;
 }

 public void addListener(AnimationChangedListener listener) {
  listeners.add(listener);
 }

 protected void dispatchValueChangedEvent() {
  for (AnimationChangedListener listener : listeners) {
   listener.valueChanged(this);
  }
 }

 /**
  * Can be overridden. This function should be called at the end.
  */
 public void doTimeStep() {
  if (currentFrame <= endFrame) {
   currentFrame++;
  }
 }

 public abstract Object getCurrentValue();
}

As you can see, I use an observer pattern to notify all listeners that a variable has changed. Because the abstract base class cannot see when a variable is changed, it is up to the derived classes to call dispatchValueChangedEvent(). AnimationChangedListener is a simple interface:

public interface AnimationChangedListener {
 void valueChanged(Animation animation);
}

Each time a frame is being updated, doTimeStep is called. Classes that extend Animation should do their logic there. Let's write a simple animation to see how this works in practice.

The translation animation
Image we want to translate a sprite on the screen between frames 10 and 20. The starting position is (0,0) and the final position is (100,100). This means that the velocity has to be:

dir = end.sub(start).scale(1.f / (float) (endFrame - startFrame));

This is simply the distance divided by the time in frames. What's left now is to add dir to the variable that tracks the position if the current frame is between the start frame and end frame, or in other words: when the animation is active.

public class TranslationAnimation extends Animation {
 private final Vector2f dir;
 private Vector2f current;

 public TranslationAnimation(Vector2f start, Vector2f end, int startFrame,
   int endFrame) {
  super(startFrame, endFrame, AnimationType.POSITION);

  current = start;
  dir = end.sub(start).scale(1.f / (float) (endFrame - startFrame));
 }

 @Override
 public void doTimeStep() {
  if (isActive()) {
   current = current.add(dir);
   dispatchValueChangedEvent();
  }

  super.doTimeStep();
 }

 @Override
 public Object getCurrentValue() {
  return current;
 }
}

And there we have it. The animated variable can be retrieved by calling getCurrentValue(). As we can see, that function returns an Object and not a Vector2f. By querying the type with getType() we know that the variable is a Vector2f.

Instead of polling getCurrentValue all the time, it's better to use the callback from dispatchValueChangedEvent().

The text changer
A second example of a useful animation in cutscenes is one that changes text. This is easily built:

public class TextAnimation extends Animation {
 private String text;
 private String newText;

 public TextAnimation(String newText, int startFrame) {
  super(startFrame, startFrame, AnimationType.TEXT);
  this.newText = newText;
  text = null;
 }

 @Override
 public void doTimeStep() {
  if (isActive()) {
   text = newText;
   dispatchValueChangedEvent();
  }

  super.doTimeStep();
 }

 @Override
 public Object getCurrentValue() {
  return text;
 }

}

This class doesn't store the original text, because that would complicate the constructor. It's no problem, because the listeners are only called when a real value is set.


We've reached the end of tutorial one. Part 2 will come soon!