Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
3  
This isn't a helpful answer, but I read over the question, said "Oh, that's easy!", went to write an answer, frowned, read it again, and then thought about it really hard for a few minutes before concluding that it is not, in fact, easy. That said, my gut instinct is "twice the resolution on each axis is either perfect or definitely-good-enough", but I don't have any evidence for this. Finally, I suspect this depends dramatically on the downscaling kernel you're comparing against - a simple pixel-averaging kernel may be easy to analyze and replicate, but a Lanczos kernel may prove impossible. –  ZorbaTHut Dec 17 '12 at 13:15
    
I think your assumption that 1/256 is the limit of the acceptable colour difference delta is wrong because the traditional colourspace (sRGB) is non-linear. –  Sam Hocevar Dec 17 '12 at 14:16
    
@sam It may not be linear when compated to the actual light spectrum, but the quantization is linear. However, it really depends on the interpolation algorithm, and the results may be very different for linear and say, bicubic interpolation. But even without interpolation there should be a way to calculate the optimal size. –  Panda Pajama Dec 17 '12 at 14:23
    
@zorbathut The answer is definitely different depending on the downsampling algorithm. But it should be relatively simple to come up with a general solution for nearest-neighbor or linear interpolation. I'm still working on it, but I think that for 8 directions, sqrt(2) the area is optimal. Let me know where you got to –  Panda Pajama Dec 17 '12 at 14:28

1 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.

building intermediate image 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:

original image 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:

non-working imageImage 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.

share|improve this answer
    
Seeing this problem as a double rounding is a pretty interesting approach, but I would like to disagree with your hypothesis that it is impossible, since you're looking at this numerically, not as a signal problem. Let's consider a 1-dimensional signal. By sampling it at n points, we will retain all information with frequencies up to 1/2n. Using Nyquist's theorem, it is possible to sample the signal at m>n points, and then resample it at n points, and arrive at the same result as if we had originally sampled it at n points. This can be easily extended to n-dimensions. –  Panda Pajama Dec 18 '12 at 3:02
1  
@PandaPajama unfortunately by invoking Nyquist you assume that the signal can be made strictly band-limited, which is not the case when our samples are over a discrete domain. This is what my counter-example exploits and why it is related to rounding. –  Sam Hocevar Dec 18 '12 at 8:24
    
If the original image is arbitrarily large, it can be considered as if it were on a continuous domain though. However, on a more practical discussion, your argument is valid when considering a very specific algorithm for downscaling with a very specific size (2x). Nearest-neighbor, bilinear and bicubic interpolations will give different results. Specifically for nearest-neighbor, I believe it is possible to geometrically construct a general solution, but that will have to wait for the weekend. –  Panda Pajama Dec 18 '12 at 11:55
1  
@PandaPajama you are correct again, very large images can be considered continuous, but the problem is that the intermediate image still is on a discrete domain. Also, nearest-neighbour will not suffer from the rounding problem by definition, but apart from trivial cases it will suffer from 1) problems related to the equidistribution theorem that will make the minimum size close to 6400×6400, ie. quite impractical, and 2) severe aliasing issues. –  Sam Hocevar Dec 18 '12 at 13:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.