TODO come back and write this out more simply

• Possible Godot implementation

Original post

The algorithm is dead simple, so I'll just describe it and you can decide: First it scales the image to 8x size, using a "pixel guessing" algorithm to add detail. Then it scales the image to 1/8 size and also rotates it using standard aliased rotation and scaling. That's basically it. To get a big speed increase for a small penalty in quality, you could use 4x instead of 8x and skip some other optional steps I did, but I wanted high quality above all else.

Here's the more detailed version: First it scales the image to double size using something similar to Scale2x, but checking if pixels are more similar to each other instead of if they're equal, which makes the result less blocky and ultimately leads to smoother output. The important thing is that the scaling algorithm works by choosing a pixel instead of by blending pixels. It does that 3 times to achieve an 8x scale, determined empirically to be a good place to stop. Then (optional step) it tries to find the best rotation offsets by looping through a small grid of offsets between 0 and 7 pixels in x and y, and for each one looping through the 8x image at the rotation angle with step size 8 pixels, and adding the squared distance of the difference in color components between each point and its immediate (1 pixel) neighbors in the 8x image, which will be 0 except on the boundaries between 8x pixels. Then it simply performs standard nearest-neighbor scaling+rotation, starting at the offsets that gave minimal sum of squared differences, and using 1/8 scale to return the image to normal size while rotating it. Finally (optional step), it tries to fix any overlooked single-pixel details by checking for any pixels in the output image that have 3 or 4 identical neighbors equal to them and unequal to the color at the corresponding place in the source image, and replacing those pixels with the one from the source image.

You might say I'm cheating by not vectorizing the graphics into lines and curves and rotating those, but I say this method is an approximation of that and works better in practice. When the original image has little detail at the angle it's being sampled, aliased rotation makes too many arbitrary decisions, but the smoothing of a pixel-choosing enlargement algorithm is sufficient to resolve most of the ambiguity.