Godot - Image Rotation

Note that due to issues with shearing, I am not opening a PR for my work atm

Godot’s built-in image rotation functions are lacking. You can only rotate 90 or 180 degrees.

I required functions to rotate images by an arbitrary amount of degrees when working on EqVS, a cleaning simulator similar to the one below, and ended up implementing them here.

These were, however, still lacking. While they did the job, they weren’t great memory-wise: requiring duplicating the memory for the image. There was no way to improve things without diving into the engine itself, so that’s what I decided to do.

TODO this is NOT TRUE!!! you can access the data buffer directly, this could be a GDExtension

For testing, I fittingly took TV Test Cards to perform rotations on. Very easy to see if anything was done wrong.

This is the project I use to play around with my custom Godot builds.

Image rotation theory

An image is, effectively, a 2-dimensional matrix (even if it is stored as a 1-dimensional array). This means that we can apply the same type of transformations to it. See here for other types of transformations.

Matrix rotation by an angle that is not a factor of the angle of the matrix (i.e) will always result in some form of data loss. A very good example is the following video, where a single line is continuously rotated by one degree, resulting in the destruction of the image.

While investigating, I found this SO question that pointed me to leptonica, which is self-describe as:

Leptonica is a pedagogically-oriented open source library containing software that is broadly useful for image processing and image analysis applications. It has a very interesting page on rotations

Stand-up Maths, a fun channel similar to Numberphile in subject matter, has an interesting video on image rotation by shearing

A basic implementation is not that hard. What becomes hard is trying to optimize.

I sometimes write about AI, and there’s a very interesting discussion on how ChatGPT gets many things wrong when building out algorithms to rotate images.

Research Papers

Here are some various papers on the subject, some with novel approaches:

• Double Line Image Rotation
• High Quality Alias Free Image Rotation
• In-Place Algorithm for Image Rotation
• Convolution-B ased Interpolation for Fast, High-Quality Rotation of Images

There is also this library that implements some other research papers.

Cropping

The first step to rotating an image is by enlarging it without resizing the image itself. This can be done by cropping the image into a larger area. The one and only case that the matrix maintains the same dimensionality is when all dimensions are the same size.

Godot does have cropping functions, however, as noted above, it isn’t efficient. From the Godot source code:

/* to save memory, cropping should be done in-place, however, since this function will most likely either not be used much, or in critical areas, for now it won’t, because it’s a waste of time. */

In my case, this function was used a lot.

The implementation is very simple:

uint32_t pixel_size = get_format_pixel_size(format);
int row_copy_size = p_width;
int empty_buffer_size = 0;
bool forward = true; //Iteration direction

int effective = width - p_x;
if (p_width > effective) {
	empty_buffer_size = p_width - effective;
	row_copy_size = effective;
	forward = false;
}

while (r >= 0 && r < p_height) {
	int offset_orig = p_x + ((r + (p_height > height ? 0 : p_y)) * width);
	int offset_dst = r * p_width;

	memcpy(w + (offset_dst * pixel_size), w + (offset_orig * pixel_size), row_copy_size * pixel_size);
	memset(w + ((offset_dst + row_copy_size) * pixel_size), 0, empty_buffer_size * pixel_size);

	r += forward ? 1 : -1;
}

Basically, for each row, copy the data we want into it, and if needed write empty pixels.

There is one bit of trickery here: when to iterate from the first row to the last, or last to the first. The reason for this is very simple: if we need to add empty pixels to each row, this will, potentially, overwrite pixels that we need. To avoid this, we iterate backwards on the image if we are going to be pasting empty pixels.

In testing, my method can be more than 5x faster than the old one.

Interpolation

By Cmglee - Own work, CC BY-SA 4.0, Link

Interpolation is easy if you only consider nearest-neighbour and linear methods.

Trilinear interpolation is very interesting. Linear is for 1-dimensional data, bilinear is for 2-dimensional data, hence trilinear is for 3-dimensional data. But where does the third dimension exist in a 2-dimensional image? The answer is with Mipmaps.

Sampling & Mapping

Sampling is, in basic implementations, relatively boring. You create a temporary image to act as a buffer, and read pixels from the original.

Yay.

Area Mapping is sort of interesting, and you can read more on it here, but it’s basically a niche variant of reverse sampling more tuned to specific image types.

Sampling memory optimisations

When using any sampling technique, you need a buffer to write the image to. Basic implementations use a buffer the same size of the image, and reducing this size is generally difficult, albeit possible.

Something that becomes interesting are cases where you need to rotate the same image multiple times. This was the case for me. However, in the section “Image Rotation Theory”, it is shown that performing consecutive rotations to an image results in significant destortions.

There’s a good memory boost here if you see it.

Do you?

Well, here it is: we keep the original image untransformed, and rotate it onto a “buffer” image. But the same, permanent, buffer image, always.

This is especially intersting in cases where rotations are performed frequently, as there is insignificant memory segmentation.

Shearing

Shearing is the more interesting method of image rotation, as the memory gains are impressive. As a shear can be done in-memory, it means this method is the only one that doesn’t require substantial buffers (buffer size depends on the interpolation method).

Good write-ups on this topic:

• blog post
• Wikipedia article
• Medium article
• Berkeley article

Moving to GDExtension

As mentioned at the beginning, it should be possible to do this without modifying the engine itself. This is because Godot’s image has a public data property, so it should be possible to just set this.

However, this comes with a major drawback: you lose the in-memory modifiability of the image data.

This isn’t problematic for some types of rotating, where we may not even want to write back to the same image.

However, for cropping and shearing, we lose a massive amount of performance, as the benefit of these two is that they can be done in-memory. This is not possibly when using GDExtension, as both get_data() and data return copies of the image data, not references.

As such, dropping this part except for rotation (maybe).