Flipping RLET-Encoded Sprites
» > >
»
» View previous topic :: View next topic  
  • Flipping RLET-Encoded Sprites
  • 17 Nov 2021 02:38:15 pm
  • Last edited by King Dub Dub on 19 Nov 2021 09:04:18 am; edited 1 time in total
Heller fellas, I've been trying to figure out how to flip RLET sprites since converting them to regular sprites, flipping them, and converting them back to RLET sprites is slow and inefficient. I managed to reverse engineer the format create a function to flip it across the horizontal axis:
Code:
//Takes a RLET-encoded sprite and flips it across the X-axis
void horizontal_flip_rletsprite(const gfx_rletsprite_t *input, gfx_rletsprite_t *output, const uint24_t size)
{
    output->width  = input->width;
    output->height = input-> height;

    uint24_t data_offset = 0;

    //the input size has the first 2 bytes for height and width, we only need the data:
    uint24_t data_size = size - 2;

    for(uint8_t y = 0; y < input->height; ++y)
    {
        //reset the line size (in bytes, not pixels):
        uint8_t row_size = 0;

        //figure out the row size:
        for(uint8_t x = 0; x < input->width;)
        {
            //grab the transparent run length and increment sizeof afterwards:
            x += input->data[data_offset + row_size++];

            //make sure the last transparent run wasn't the whole line:
            if(x < input->width)
            {
                //the next byte is number of non-transparent colors:
                x += input->data[data_offset + row_size];

                //the next byte is the number of non-transparent colors, add that plus 1 for the next run:
                row_size += (input->data[data_offset + row_size] + 1);
            }
        }

        //copy the first row of the input to what will be the last row of the output:
        memcpy(&output->data[data_size - row_size - data_offset], &input->data[data_offset], row_size);

        data_offset += row_size;
    }
}

It's works and doesn't make me want to stab forks in my eyes, but I wanted to ask if there were any optimizations I could make. I also made a function for finding the size:
Code:
//Gets the data size of an RLET-encoded sprite, good for allocating memory for flipped copies
uint24_t get_rlet_size(const gfx_rletsprite_t *input)
{
    //optimizing for speed here:
    uint24_t width  = input->width;
    uint24_t height = input->height;

    uint24_t data_offset = 0;

    for(uint8_t y = 0; y < height; ++y)
    {
        //figure out the row size:
        for(uint8_t x = 0; x < width;)
        {
            //grab the transparent run length and increment sizeof afterwards:
            x += input->data[data_offset++];

            //make sure the last transparent run wasn't the whole line:
            if(x < width)
            {
                //the next byte is number of non-transparent colors:
                x += input->data[data_offset];

                //the next byte is the number of non-transparent colors, add that plus 1 for the next run:
                data_offset += (input->data[data_offset] + 1);
            }
        }
    }

    //add the two width and height values:
    return data_offset + 2;
}

Again, any optimizations or possible bugs? I'm working on the vertical flipping now, and my logic is to paste the first transparent run on the end of the row (the length/offset of which I find beforehand) if it isn't zero, copy the non-transparent data over, and then make sure the first byte of the output row is zero if there aren't any transparent runs at the end of the input. It works in my head until I think about it for too long, so I'll see what I can do. Hopefully this'll help someone in the future!
"You can say literally anything and claim it's a quote from The Art of War." -Sun Tzu Update your MyCalcs coward.
Quote:
Flipping RLET-Encoded Sprites
I know, right? Screw RLET sprites.

Anyways, assuming that I remember how RLET sprites work, I don't see anything obviously wrong with the functions.
It's possible that the compiler already optimizes this out for you, but you could replace input->data[data_offset] and output->data[data_size - row_size - data_offset] with two pointers that get added and subtracted from once per loop so that you don't have to re-compute the entire thing every single loop.
My projects: Wordle | CEleste | Unit Tool | Tanks! | Terminal CE
Sorry if I'm missing the point, but... why would you flip an run length encoded sprite instead of say, copying the function from the source and simply changing the render direction from positive to negative(inc->dec)? If you're insistent on measuring from the top left corner, just add the width of the sprite to the x offset at the start of the function.This breaks with clipping of course, but again, just a few modified lines and you're gucci, yeah? No need to allocate space for a flipped sprite.
Well, "changing the render direction" isn't directly possible - the rendering routine uses an ldir, which can only copy data in the same direction it's already in. So, you can't just directly substitute in another instruction to swap the direction.

Even if you could, the full RLET code is more than 250 lines long, which would result in a substantial amount of code duplication. In addition to the code size increase, future optimizations to the C library functions wouldn't be passed on to the copy without a manual rebuild.

So, depending on how many sprites you want to allocate and how many times you'll display them, it might be faster to flip them once and repeatedly display them, or more memory efficient to create a flipped copy of the sprite at runtime than to include a duplicate copy of the function.
My projects: Wordle | CEleste | Unit Tool | Tanks! | Terminal CE
Zaalane, I had that idea last night and I think it could fit some use cases, but for the reasons Commandz mentioned and the fact that I know next to nothing about assembly, I don't think I'd be able to pull it off. However, you could make one function where the x/y-increment values are parameters (e.g. you can set x-step to -1 and it draws the sprite backwards, or flipped). You'd have to deal with offsetting the coords and stuff, but it could work for all four directions, albeit with some very weird looking code and lots of conditionals. As for what Commandz said about pointers, sprite.data has always been the same as ((void*)sprite + 2) in my experience. The compiler also doesn't like it when I try to assign to a pointer like that and I can't figure out how to keep it from erroring out.

Flipping across the Y is harder then I thought since you have to re-encode rows and the output size can be a byte larger or smaller than the input size in a few cases, specifically if the row starts with a transparent run and ends with a solid run or if it starts with a zero-transparent run and ends with a transparent run. The issues are due to the fact that I have to either prepend a zero to the run or remove the zero from the end. I've got it correctly writing out the row data size and writing the increased-size rows, but the shrunk rows are giving me flak since I keep forgetting what it is I'm trying to do and optimizing this as I go is hard.
"You can say literally anything and claim it's a quote from The Art of War." -Sun Tzu Update your MyCalcs coward.
Okay then, I've got everything working correctly now with the new flipping. There's room for optimization and I don't actually know why it works, I just know that after rewriting the line-copying code four times it started kinda working until I changed some numbers and it started really working. I did make it much more readable and renamed the functions to fit the existing gfx_Flip* naming scheme. I might make a version for flipping from corner to corner soon if I don't lose my patience first.

UPDATE: I straight up forgot to update the code after optimizing it some more Shock , I got everything streamlined and now it takes a little less space. Commandz, I figured out what you were talking about and I got it to work, all the optimization came from that. As for flipping corner-to-corner, I might work on that someday but I'd like to put these functions to use in some projects. Rotating RLET sprites might be impossible without an extra buffer, although I have a rough idea involving calculating the colors of individual pixels and making a new RLET sprite with them... I can't explain it since I don't get it myself, but I might not waste my time.
Code:
//Gets the data size of an RLET-encoded sprite, good for allocating memory for flipped copies
uint24_t Get_RLET_Size(const gfx_rletsprite_t *src)
{
    //optimizing for speed here
    uint24_t width  = src->width;
    uint24_t height = src->height;

    uint24_t data_offset = 0;

    for(uint8_t y = 0; y < height; ++y)
    {
        //figure out the row size
        for(uint8_t x = 0; x < width;)
        {
            //grab the transparent run length and increment the size afterwards
            x += src->data[data_offset++];

            //make sure the last transparent run wasn't the whole line
            if(x < width)
            {
                //the next byte is number of non-transparent colors
                x += src->data[data_offset];

                //the next byte is the number of non-transparent colors, add that plus 1 for the next run
                data_offset += (src->data[data_offset] + 1);
            }
        }
    }

    //add the two width and height values
    return data_offset + 2;
}

Code:
//calculates what the size of an RLET-encoded sprite would be after flipping it across the Y-axis
uint24_t Get_Vertical_RLET_Size(gfx_rletsprite_t *src)
{
    uint24_t data_offset = 0;

    //the range of possible dest size differences range from -255 to 255
    int24_t dest_difference = 0;

    for(uint8_t y = 0; y < src->height; ++y)
    {
        uint24_t row_start = data_offset;

        //figure out the row size
        for(uint8_t x = 0; x < src->width;)
        {
            x += src->data[data_offset++];

            //make sure the last transparent run wasn't the whole line
            if(x < src->width)
            {
                //the next byte is number of non-transparent colors
                x += src->data[data_offset];

                //the next byte is the number of non-transparent colors, add that plus 1 for the next run
                data_offset += (src->data[data_offset] + 1);

                if((x >= src->width) && (src->data[row_start]))
                {
                    //if the line ends in a solid run but starts with a transparent run, we need to increase the ouput row size
                    //so we can append zero to the start of the dest data
                    ++dest_difference;
                }
            }
            else if(!src->data[row_start])
            {
                //if the line ended with a transparent run but started without one, the dest row needs to be shrunk by one byte
                //since the zero will be replaced with the last transparent run and the data cannot end in zero
                --dest_difference;
            }
        }
    }

    //add the width and height variables size to the data size
    return data_offset + dest_difference + 2;
}

Code:
//Takes a RLET-encoded sprite and flips it across the X-axis
void Flip_RLETSpriteX(const gfx_rletsprite_t *src, gfx_rletsprite_t *dest, const uint24_t size)
{
    dest->width  = src->width;
    dest->height = src-> height;

    uint24_t data_offset = 0;

    //the src size has the first 2 bytes for height and width, we only need the data
    uint24_t data_size = size - 2;

    for(uint8_t y = 0; y < src->height; ++y)
    {
        const uint8_t *src_ptr  = &src->data[data_offset];

        //reset the line size (in bytes, not pixels)
        uint8_t row_size = 0;

        //figure out the row size
        for(uint8_t x = 0; x < src->width;)
        {
            //grab the transparent run length and increment the row size afterwards
            x += src_ptr[row_size++];

            //make sure the last transparent run wasn't the whole line
            if(x < src->width)
            {
                //the next byte is number of non-transparent colors
                x += src_ptr[row_size];

                //the next byte is the number of non-transparent colors, add that plus 1 for the next run
                row_size += (src_ptr[row_size] + 1);
            }
        }

        //copy the first row of the src to what will be the last row of the dest
        memcpy(&dest->data[data_size - row_size - data_offset], &src->data[data_offset], row_size);

        data_offset += row_size;
    }
}

Code:
//Takes a RLET-encoded sprite and flips it across the Y-axis
void Flip_RLETSpriteY(const gfx_rletsprite_t *src, gfx_rletsprite_t *dest)
{
    dest->width  = src->width;
    dest->height = src-> height;

    uint24_t src_data_offset  = 0;
    uint24_t dest_data_offset = 0;

    for(uint8_t y = 0; y < src->height; ++y)
    {
        uint8_t src_row_size  = 0;
        uint8_t dest_row_size = 0;

        //Why is the compiler like this? Why is this the right way? At least it saves 9 bytes...
        uint8_t *dest_ptr = &dest->data[dest_data_offset];

        //...and this one saves 48 bytes. Commandz is a wise block, I should've tried this earlier.
        const uint8_t *src_ptr  = &src->data[src_data_offset];

        //due to how the data encodes, we need to track if the ouput row size needs to be different than the src size
        bool funky_flag = 0;

        //figure out the row size
        for(uint8_t x = 0; x < src->width;)
        {
            x += src_ptr[src_row_size++];

            //make sure the last transparent run wasn't the whole line
            if(x < src->width)
            {
                //the next byte is number of non-transparent colors
                x += src_ptr[src_row_size];

                //the next byte is the number of non-transparent colors, add that plus 1 for the next run
                src_row_size += (src_ptr[src_row_size] + 1);

                if((x >= src->width) && (src_ptr[0]))
                {
                    //if the line ends in a solid run but starts with a transparent run, we need to increase the ouput row size
                    //so we can append zero to the start of the dest data
                    dest_row_size = src_row_size + 1;

                    funky_flag = true;
                }
            }
            else if(!src_ptr[0])
            {
                //if the line ended with a transparent run but started without one, the dest row needs to be shrunk by one byte
                //since the zero will be replaced with the last transparent run and the data cannot end in zero
                dest_row_size = src_row_size - 1;

                funky_flag = true;
            }
        }

        if(!funky_flag)
        {
            dest_row_size += src_row_size;
        }

        //Oh boy, I sure do love abusing bool types!
        for(int24_t i = 0; i < (src_row_size - funky_flag);)
        {
            uint8_t solid_length;

            //if the first transparent run isn't zero
            if(src_ptr[0])
            {
                dest_ptr[dest_row_size - 1 - i] = src_ptr[i];

                ++i;

                //ensure the whole line wasn't transparent
                if(i < (src_row_size - funky_flag))
                {
                    solid_length = src_ptr[i];
   
                    //set the transparent run length
                    dest_ptr[dest_row_size - 1 - solid_length - i] = solid_length;

                    for(uint24_t j = 0; j < solid_length; ++j)
                    {
                        dest_ptr[dest_row_size - solid_length - i + j] = src_ptr[i + solid_length - j];
                    }

                    //add the length of the copied data to the size count
                    i += solid_length + 1;

                    //if the src row ends with a solid run, we have to tack a zero-transparent run at the start of the dest
                    if(i >= (src_row_size - funky_flag))
                    {
                        dest_ptr[0] = 0;
                    }
                }
            }
            else //else things get weird because we have to read ahead of the src to skip the zero
            {
                solid_length = src_ptr[i + 1];

                dest_ptr[dest_row_size - 1 - solid_length - i] = solid_length;

                for(uint24_t j = 0; j < solid_length; ++j)
                {
                    dest_ptr[dest_row_size - solid_length - i + j] = src_ptr[i + solid_length + 1 - j];
                }

                i += src_ptr[i + 1] + 1;

                //ensure the whole line wasn't solid
                if(i < (src_row_size - funky_flag))
                {
                    dest_ptr[dest_row_size - 1 - i] = src_ptr[i + 1];

                    ++i;

                    //if everything is normal and it ends with a solid run, we need to apend a zero to the dest:
                    if((!funky_flag) && (i >= src_row_size))
                    {
                        dest_ptr[0] = 0;
                    }
                }
            }
        }

        src_data_offset  += src_row_size;
        dest_data_offset += dest_row_size;
    }
}
"You can say literally anything and claim it's a quote from The Art of War." -Sun Tzu Update your MyCalcs coward.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Flipping RLET-Encoded Sprites
»
» View previous topic :: View next topic  
Page 1 of 1
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement