Optimal sprite size for rotations

Question

I am making a sprite based game, and I have a bunch of images that I get in a ridiculously large resolution and I scale them to the desired sprite size (for example 64x64 pixels) before converting them to a game resource, so when draw my sprite inside the game, I don't have to scale it.

However, if I rotate this small sprite inside the game (engine agnostically), some destination pixels will get interpolated, and the sprite will look smudged.

This is of course dependent on the rotation angle as well as the interpolation algorithm, but regardless, there is not enough data to correctly sample a specific destination pixel.

So there are two solutions I can think of. The first is to use the original huge image, rotate it to the desired angles, and then downscale all the reaulting variations, and put them in an atlas, which has the advantage of being quite simple to implement, but naively consumes twice as much sprite space for each rotation (each rotation must be inscribed in a circle whose diameter is the diagonal of the original sprite's rectangle, whose area is twice of that original rectangle, supposing square sprites).

It also has the disadvantage of only having a predefined set of rotations available, which may be okay or not depending on the game.

So the other choice would be to store a larger image, and rotate and downscale while rendering, which leads to my question.

What is the optimal size for this sprite? Optimal meaning that a larger image will have no effect in the resulting image.

This is definitely dependent on the image size, the amount of desired rotations without data loss down to 1/256, which is the minimum representable color difference.

I am looking for a theoretical general answer to this problem, because trying a bunch of sizes may be okay, but is far from optimal.

Answer 1

I think what you are trying to do is the 2D image space equivalent to double rounding. I can construct a loose proof that it is impossible to find such an intermediate size, at least in the case of simple downscaling algorithms such as linear interpolation.

Suppose we found N such that the intermediate image has size N×N, greater than 64×64. Suppose we aren't even applying rotation yet (angle is zero).

Now let’s build a picture that doesn’t work.

Building the intermediate image

Consider a fully black intermediate image. Obviously, the final image will be fully black, too. Then, add one gray pixel of minimum intensity (R¸G,B = 1,1,1). The final image should still be fully black. Add another gray pixel touching the first one. Proceed building a circle until the final image is no longer fully black.

Image 1

Now one pixel in the final image is gray (if we continued forever, the resulting image would be fully gray, so obviously at some point one pixel becomes gray), and if we remove that last pixel, it’s fully black again.

Building the original image

Consider the hypothetical original image that led to our intermediate image. I cannot prove it exists, but I have a strong feeling that it does. For instance, if the original image has size 2N×2N, this could be it:

Image 2

When downscaling Image 2 to the intermediate size, we get Image 1.

And by hypothesis, when downscaling to 64×64, we get one grey dot in the final image.

Now let's break apart the last pixel we added and scatter it around the original cluster:

Image 3

This is our counter-example.

When downscaled to the final size, this image should give us a grey pixel, because the pixels we scattered are even closer to the cluster, so the global intensity is at least as high.

When downscaled to the intermediate size, this image should miss the special pixel because they have been scattered around, so we get a fully black image when doing the two-step resize.

Conclusion and future thoughts

I hope this convinces you that what you are trying to achieve will not work in the general case.

My approach to your problem would be to compute the best size per image: start with the original image and eg. N = 128, then try all possible angles and compute the maximum error. If the maximum error is not satisfying, try N = 256 etc. until you get the correct size.