GDevelop [SpriteRuntimeObject] Optimize custom hitboxes vertices transformations.

Each time a point is transformed, the current implementation do a lot of calculus to apply an affine transformation.

https://github.com/4ian/GDevelop/blob/bc606ed1be28275624678dd7c6bcc192c2da846d/GDJS/Runtime/spriteruntimeobject.ts#L847-L883

The affine transformation can be calculated only once and reused for each point transformation:

    private _transformToGlobal(x: float, y: float, result: number[]) {
      result.length = 2;
      result[0] = x;
      result[1] = y;
      // @ts-ignore It's a FloatPoint at this point.
      this.getAffineTransformation().transform(result, result);
    }

    transform(source: FloatPoint, destination: FloatPoint) {
      //       x
      //       y
      //       1
      // a b c
      // d e f
      // 0 0 1
      const x = this.a * source[0] + this.b * source[1] + this.c;
      const y = this.d * source[0] + this.e * source[1] + this.f;
      destination[0] = x;
      destination[1] = y;
    }

Using the AffineTransformation class also make the code easier to follow (once used to the composition order).

It needs more tests and more features on AffineTransformation, but I wanted your view on this. I think it could be interesting to have it also in the base class.

I couldn't find any library that allows instantiation-free affine transformations so I started to implement this one.

A project example to check: https://www.dropbox.com/s/ygqc3m4nv9nb221/CustomHitboxTransformation.zip?dl=1

Nov 19 '21 19:11 D8H

I couldn't find any library that allows instantiation-free affine transformations so I started to implement this one.

I quickly looked, basically this is a very simple matrix handling library that you started? :)

There is this: https://code.google.com/archive/p/webgl-mjs/ - but probably too complex compared to our needs. At least this is mostly for 4x4 matrices, not 3x3. I've seen that Phaser has some utilities: https://photonstorm.github.io/phaser3-docs/Phaser.Utils.Array.Matrix.html but very generic too.

It's still interesting to see how they do, webgl-mjs is storing a matrix in a Float32Array. Phaser is using an array.

It needs more tests and more features on AffineTransformation, but I wanted your view on this.

I think it's generally a good idea, to have a lightweight AffineTransformation/Matrix capabilities (especially if we add in the future things like custom hitboxes or points to other objects).

My main concerns/points of attention are:

memory usage of this/cost of initialization. We now have for each object 9 additional floats (whether we store them in an array or not). I wonder about the impact (it's now a bit more costly to initialize an object), should/could we somehow have a lazy initialization (we leave _affineTransformation at null, and only instanciate it if needed?)
Is there a way to optimise the most usual operations? Much like we could lazily use this when needed, is there a way for example to not store a full 3x3=9 elements when we just need the translation (i.e: the x/y position... which is already in the object)?

Matrix in video game engines are very interesting, I'm pretty sure we could have something lightweight and with some clever optimisations :) There are tons of 4x4 matrix libraries for WebGL I think - but they are too heavyweight but can be useful to see if they have some optimisations done.

Nov 20 '21 14:11 4ian

I couldn't find any library that allows instantiation-free affine transformations so I started to implement this one.

I quickly looked, basically this is a very simple matrix handling library that you started? :)

There is this: https://code.google.com/archive/p/webgl-mjs/ - but probably too complex compared to our needs. At least this is mostly for 4x4 matrices, not 3x3. I've seen that Phaser has some utilities: https://photonstorm.github.io/phaser3-docs/Phaser.Utils.Array.Matrix.html but very generic too.

It's still interesting to see how they do, webgl-mjs is storing a matrix in a Float32Array. Phaser is using an array.

Phaser uses a Float32Array too. It's strange that the 3rd row is stored as it's never used for affine transformation calculus (maybe some general matrix algo needs it). Otherwise, the implementation follows the same logic that what I was starting.

https://github.com/photonstorm/phaser/blob/5c8ecbcf999e6f328d21884e877c9e5935d2d350/src/gameobjects/components/TransformMatrix.js#L48-L55

I couldn't easily access to the source of webgl-mjs but I bet it's similar too.

Phaser use {x, y} to represent points. We could use their implementation as a base and modify it to use GDJS types.

Nov 20 '21 17:11 D8H

Otherwise, the implementation follows the same logic that what I was starting

Nice. Interesting that they store the last row - I guess this is for allowing passing the matrix as is (well, the Float32Array) to WebGL/other algos.

We don't need their full implementation I would say, let's keep something just as complete as we need - to avoid having to maintain stuff we don't need (and avoid things that would be not performant) :)

Nov 21 '21 21:11 4ian

So I think we could go ahead with this if:

maybe we rename the AffineTransformation to... Matrix2d ?
let's set up a benchmark (makeBenchmarkSuite) to see how long it takes to transform multiple points. This test will be useful to measure the speed up (this version should be largely faster).

In theory, this only adds a "pointer" and a boolean to objects which don't have a rotation/scale/flip (so this should not impact too much games having a lot of static objects).

Dec 26 '21 22:12 4ian

maybe we rename the AffineTransformation to... Matrix2d ?

For me, "Matrix2d" stands for a m x n matrice data structure. Maybe "Transformation2d" to have a shorter name and allow to make a Transformation3d if GDevelop goes 3d one day.

let's set up a benchmark (makeBenchmarkSuite) to see how long it takes to transform multiple points. This test will be useful to measure the speed up (this version should be largely faster).

It looks like the transformation do well only on rotating objects. I guess it's because cos and sin calls are put in cache for the fix rotated object. The non rotated case is worst probably because of the extra check for translation only.

With affine transformations:

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 53.71833333273729,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 60.83999999985099,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 70.08000000019868

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 52.33833333303531,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 58.33166666701436,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 69.546666666617

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 53.62000000004967,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 59.65833333258828,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 71.25833333383004

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 55.371666666616996,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 60.44999999925494,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 71.32333333442608

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 56.28000000044703,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 61.60499999995033,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 73.10333333263794

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 55.83833333378037,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 63.14833333219091,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 73.90500000094374

Without affine transformations:

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 50.32499999975165,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 61.79666666562358,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 80.28000000144044

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 51.61333333477378,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 63.605000000447035,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 76.62499999850988

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 65.86666666691502,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 76.2433333327373,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 93.18166666651766

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 52.23666666597128,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 63.12999999970198,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 78.5683333342274

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 52.090000000099344,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 60.81333333378037,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 75.68499999940396

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 53.19166666592161,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 63.92833333313465,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 77.8933333337307

Dec 27 '21 01:12 D8H

The gain seems to be around 5% on only translating or rotating sprites.

With affine transformations

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 47.20833333283663,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 61.76666666641832,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 71.03166666701436

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 49.536666670441626,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 64.0383333320419,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 75.70833333233992

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 51.16666666716337
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 65.92166666587194
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 81.8933333337307

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 46.82666666805744,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 65.18833333303532,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 75.61166666448116

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 46.71666666567326,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 64.11999999980132,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 74.4750000009934

o

getAABB of a non rotated sprite, with custom hitboxes, origin and center(60000x): 49.831666667262716,
getAABB of a rotated sprite, with custom hitboxes, origin and center(60000x): 65.65333333363135,
getAABB of a rotating sprite, with custom hitboxes, origin and center(60000x): 73.80999999890724

Dec 27 '21 16:12 D8H

The gain seems to be around 5% on only translating or rotating sprites.

Alright! Thanks a lot for running this benchmark (we really have to think about a way to extract and push these benchmarks automatically from master/from a PR, would be useful to have it done in the cloud automatically).

A modest improvement, and in any case no regression, is what we want (because we're trading this for memory, so it better be faster!).

Dec 27 '21 20:12 4ian

For me, "Matrix2d" stands for a m x n matrice data structure. Maybe "Transformation2d" to have a shorter name and allow to make a Transformation3d if GDevelop goes 3d one day.

Right! What about then just Matrix3 or Matrix3x3? Could have Matrix4/4x4 in the future?

Dec 27 '21 20:12 4ian

For me, "Matrix2d" stands for a m x n matrice data structure. Maybe "Transformation2d" to have a shorter name and allow to make a Transformation3d if GDevelop goes 3d one day.

Right! What about then just Matrix3 or Matrix3x3? Could have Matrix4/4x4 in the future?

It's not a general purpose matrix. It can't be used to solve equations for instance. The 3rd row is even implicitly always 0, 0, 1. It only does affine transformations in 2D space.

Dec 27 '21 21:12 D8H

Fair enough then! Last question: do you see other places in the game engine where this could be used?

Dec 28 '21 18:12 4ian

Fair enough then! Last question: do you see other places in the game engine where this could be used?

It could be used to

transform positions in layers It will optimize games with a lot of mouse conditions (though it would be more efficient to cache the cursor position) It will optimize the visual debugger (I think it can be important that debuggers are as light as possible to keep the same frame rate if it's important to reproduce issues)
allow affine transformations of Polygon (might be useful to JS extensions and the tilemap collision mask will probably use it)
generalize affine transformations to every object to prepare for object composition (to avoid to stack transformation calculus on deep composites) For the ShapePainter, I used the transformation from Pixi. It doesn't need extra memory and it is computed for rendering so it's almost free, but it relies on Pixi which is not a good idea if it must be generalized or if we want to use other rendering methods.

Jan 11 '22 15:01 D8H

I tried affine transformations for layer points transformation and it wasn't conclusive. Layer calculus are simpler than the Sprite one. With Math caching cos, there are only 2 multiplications to save and indirection eat it up. Even a simple if for translations makes the general case 50% heavier to process and save peanuts for translation.

It think affine transformations could be useful in Layer only if it allows to do transformations of a custom points to the screen directly which means that objects will have an additional absolute transformation. This is probably something to think about only when implementing object composition.

Jan 12 '22 17:01 D8H

wow. Amazing work @D8H , does it work on in physic 2.0 engine?

Mar 15 '22 10:03 jjhesk

Does it work on in physic 2.0 engine?

I don't know how the physic 2.0 engine works but doubt this will have much impact on the over-whole efficiency when the physic behavior is used.

Mar 15 '22 12:03 D8H