Optimization tip: faster 2D transforms

18 May

Drop the last column

A 2D transform is typically shown as a 3×3 augmented matrix. However the last column (or row depending which order you use) of an augmented matrix is always 0 0 1, so we don’t need to store it. We only store a 2×3 matrix.

\begin{bmatrix} a & b \\ c & d \\ e & f \end{bmatrix}

The 2 upper rows will contain the rotation, scale and shear factors, while the lower row contains the translation.

In-place transformation of matrices

A translation only modifies the bottom row. It leaves the rotation and scale alone, but is affected by them

\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ tx & ty & 1 \end{bmatrix} \times \begin{bmatrix} a & b & 0 \\ c & d & 0 \\ e & f & 1 \end{bmatrix} = \begin{bmatrix} a & b & 0 \\ c & d & 0 \\ tx*a+ty*c+e & ty*b+ty*d+f & 1 \end{bmatrix}

A rotation modifies the 2 top rows, and leaves the current translation alone

\begin{bmatrix} co & -si & 0 \\ si & co & 0 \\ 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} a & b & 0 \\ c & d & 0 \\ e & f & 1 \end{bmatrix} = \begin{bmatrix} co * a + -si * c & co * b + -si * d & 0 \\ si * a + co * c & si * b + co * d & 0 \\ e & f & 1 \end{bmatrix}

A scale also modifies the 2 top rows, and leaves the current translation alone

\begin{bmatrix} sx & 0 & 0 \\ 0 & sy & 0 \\ 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} a & b & 0 \\ c & d & 0 \\ e & f & 1 \end{bmatrix} = \begin{bmatrix} sx*a & sx*b & 0 \\ sy*c & sy*d & 0 \\ e & f & 1 \end{bmatrix}

This means we can prevent a lot of additions and multiplications (not to mention allocations) if we do these calculations directly instead of creating translation, rotation and scale matrices and start multiplying them. If you look down in the code you will also see that the calculation of the inverse transform can also be simplified by taking into account the fixed column.

The result

A typical transform class might look like this

class Transform {
public:
  Transform() {
    f11 = f22 = 1.0f;
    f12 = f21 = f31 = f32 = 0.0f;
  }

  void translate(float x, float y) {
    f31 += x * f11 + y * f21;
    f32 += x * f12 + y * f22;
  }

  void rotate(float angle) {
    angle = deg2rad(angle);
    float tmp = f11;
    float c = cosf(angle), s = sinf(angle);
    f11 = c * f11 + s * f21;
    f21 = -s * tmp + c * f21;
    tmp = f12;
    f12 = c * f12 + s * f22;
    f22 = -s * tmp + c * f22;
  }

  void scale(float s) {
    scale(s, s);
  }
    
  void scale(float x, float y) {
    f11 *= x;
    f12 *= x;
    f21 *= y;
    f22 *= y;
  }

  Vector transform(const Vector &vector) const {
    return Vector(vector.x * f11 + vector.y * f21 + f31, vector.x * f12 + vector.y * f22 + f32);
  }

  Vector translation() const {
    return Vector(f31, f32);
  }
    
  float rotation() const {
    return atan2f(f12, f22); // or atan2f(-f21, f11)
  }
    
  Vector scale() const {
    return Vector(sqrtf(f11*f11 + f21*f21), sqrtf(f12*f12 + f22*f22));
  }

  Transform inverse() const {
    Transform inv;
    float det = f11*f22 - f21*f12;
    inv.f11 = f22 / det;
    inv.f12 = -f12 / det;
    inv.f21 = -f21 / det;
    inv.f22 = f11 / det;
    inv.f31 = (f21 * f32 - f31 * f22) / det;
    inv.f32 = (f31 * f12 - f11 * f32) / det;
        
    return inv;
  }

  float f11, f12,
        f21, f22,
        f31, f32;
};

I don’t include a matrix multiplication as it’s generally not needed. In fact I hardly ever use the vector transform. Instead I upload the current matrix into a GLSL uniform location.

The translation, rotation and scale extraction functions are handy when you need objects which are in a scene tree but need to be immune to certain transformations. For example a sprite that doesn’t rotate with the rest of the world. The sprite can extract the current global rotation and undo it before drawing.

The inverse transform can be used to bring for example mouse coordinates into the untransformed coordinate system of an object, in order to do hit testing or local changes like vertex editing.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: