"Checkerboarding" effect when rotating sprite in software renderer?

Question

I'm writing a 2D software renderer and when rotating in certain angles I will get a sort of "checkerboarding" effect with my sprite pixels:

To try and get proper rotation, I tried rounding/flooring/ceiling the rotated pixels, but that did nothing to fix it.

It seems the pixels get set to the wrong position and overlap each other. Not exactly sure why this happens? I presume this may be a precision issue or something, maybe, really not sure..

Relevant portion of my code:

uint width = image.width;
uint height = image.height;

uint originX = width / 2;
uint originY = height;

float radians = angleDegrees * PI / 180.0f;

float sine = sin(radians);
float cosine = cos(radians);
for (uint r = 0; r < height; r++)
{
    for (uint p = 0; p < width; p++)
    {
        int translatedR = r - originY;
        int translatedP = p - originX;

        int rotatedR = round(translatedP * sine + translatedR * cosine) + originY;
        int rotatedP = round(translatedP * cosine - translatedR * sine) + originX;

        size_t index = (x + rotatedP + (frameBufferWidth * y)) + (frameBufferWidth * rotatedR);
        size_t index2 = p + (image.width * r);

        if (!image.pixels[index2].a)
            continue;
        
        frameBuffer[index].r = image.pixels[index2].r;
        frameBuffer[index].g = image.pixels[index2].g;
        frameBuffer[index].b = image.pixels[index2].b;
    }
}

You should do it the other way around, in the rotated image find out where the pixel came from in the original image. This could actually be "in between pixels" and this allows you todo bilinear interpolation to get the color in your final rotated image. — Pepijn Kramer
– Pepijn Kramer, Commented Aug 29, 2024 at 5:30

Mike Nakis · Accepted Answer · 2024-09-01 20:03:03Z

0

Your rotation algorithm visits pixels on the sprite from top to bottom and left to right, thus guaranteeing that all the source pixels will be visited; for each pixel, it computes the coordinates of the corresponding pixel on the frame buffer, and copies the pixel there.

Unfortunately, this does not guarantee that all of the pixels that must be painted on the frame buffer will be painted.

This is due to the imprecision inherent in any attempt to calculate integers (pixel coordinates) by multiplying integers by non-integers: the calculations naturally do not yield all of the desired target coordinates, while they yield some of the target coordinates twice.

The result is that during the rendering of a single frame, some pixels of the frame buffer are left unpainted, while some pixels are painted and then needlessly re-painted.

So, I am afraid I am going to disappoint you: It is not simple to solve.

However, with enough work, (a lot more work than what you have done so far,) it is possible.

Roughly, here is what you need to do:

First of all, you need to compute how the rectangle of your sprite maps to a rectangle on the frame buffer, after rotation has been applied. Unless the rotation is a multiple of 90 degrees, this frame buffer rectangle will be slanted.

You will be visiting the pixels of the frame buffer rectangle raster-line by raster-line, and within each raster line, one by one, as the following diagram shows:

                      ####
                     ##########
                     ###############
                    #####################
                    ##########################
                   ##########################
                        #####################
                             ###############
                                  ##########
                                       ####

This guarantees that all of the pixels in the frame buffer that must be painted, will be painted.

The value of each pixel on the frame buffer must come from visiting pixels on the sprite along slanted lines, where the slope of the lines is dictated by the amount of rotation applied.

To visit pixels on a sprite along a slanted line, I would advise you to read up on Bresenham's Line Algorithm. (Wikipedia.) It is a lot faster (insanely faster) than performing several multiplications per pixel to calculate each coordinate.

Here it is, in action: https://www.youtube.com/watch?v=AApyC2a4KVw

This was done by me in the early 1990s, in C++ and assembly, using the 320x200 pixel, 256 color mode of the VGA. By today's standards it is laughable, but back then it was quite something!

edited Sep 1, 2024 at 20:03

answered Aug 28, 2024 at 22:10

Mike Nakis

63k11 gold badges128 silver badges173 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Pepijn Kramer Over a year ago

No using bresenham is also going to introduce a lot of aliasing.

Mike Nakis Over a year ago

@PepijnKramer your comment is ambiguous. In any case, there will be aliasing. Getting rid of aliasing is a whole different ballgame.

Pepijn Kramer Over a year ago

Fair point, Yet using backprojection is an ancient and well known technique too ;)

Nasir Over a year ago

I read up on it, thanks. How exactly do I dictate the slope of the lines? To my understanding, if I use sine and cosine in any way then I'll get precision issues and thus checkerboarding will still occur either way.

Nasir Over a year ago

After a while of studying this, I managed to get some proper rotation actually working :) Well, it's certainly not perfect, quite a bit of jittering due to integer arithmetic, but decent enough I suppose.

|

Collectives™ on Stack Overflow

"Checkerboarding" effect when rotating sprite in software renderer?

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related