Inefficient nice-to-have graphics routines
» > >
»
» View previous topic :: View next topic  
I found myself wanting to draw a sprite but flipped on the x-axis. Yes, I know that for the best performance, I should create the flipped sprite and draw it directly.

Anyway, here's what I came up with at first:

Code:
void draw_x_flipped_sprite(gfx_sprite_t* sprite, int dest_x, int dest_y, bool transparency) {
    char* data     = (char*) sprite;
    uint8_t width  = data[0];
    uint8_t height = data[1];

    for (int y = 0; y < height; y++) {
        int draw_y = dest_y + y;

        // clipping check in the y direction
        if (draw_y < 0 || draw_y >= LCD_HEIGHT) {
            continue;
        }

        for (int x = 0; x < width; x++) {
            int draw_x = dest_x + x;
           
            // clipping check in the x direction
            if (draw_x < 0 || draw_x >= LCD_WIDTH) {
                continue;
            }

            char pixel = data[y * width + width - x + 1];

            // transparency check
            if (transparency && pixel == MAGENTA) {
                continue;
            } else {
                gfx_vbuffer[draw_y][draw_x] = pixel;
            }
        }
    }
}


The above is inefficient: the framerate dropped by 10%. After pleading the #c-on-the-ce channel on the Cemetech Discord, calc84maniac, LogicalJoe, c4ooo, and fghsgh gave me some tips to optimize it a little. I now have this:


Code:
void draw_x_flipped_sprite(gfx_sprite_t* sprite, int dest_x, int dest_y, bool transparency) {
    // kinda optimized compared to the inefficient version
    // thanks, calc84maniac, c4ooo, LogicalJoe, fghsgh!
    // all of you helped me to squeeze a few more frames out

    char* data     = (char*) sprite;
    uint8_t width  = data[0];
    uint8_t height = data[1];

    // clipping checks

    // we might end up drawing out of the bounds of uint8_t in the x direction
    int start_x = 0 > dest_x ? 0 : dest_x;
    int start_y = 0 > dest_y ? 0 : dest_y;
    int end_x   = LCD_WIDTH <= (dest_x + width) ? (LCD_WIDTH - 1) : (dest_x + width);
    int end_y   = LCD_HEIGHT <= (dest_y + width) ? (LCD_HEIGHT - 1) : (dest_y + height);

    int source_x_left_bound   = dest_x < 0 ? (width + dest_x - 1) : 0;
    int source_x_right_bound  = (dest_x + width) >= LCD_WIDTH ? (LCD_WIDTH - dest_x) : width;
    int source_y_top_bound    = dest_y < 0 ? (height + dest_y - 1) : 0;
    int source_y_bottom_bound = (dest_y + height) >= LCD_HEIGHT ? (LCD_HEIGHT - dest_y) : height;

    int source_pixel_pointer     = source_y_top_bound * width + 1;
    uint8_t* destination_pointer = &(gfx_vbuffer[start_y][start_x]);
    int destination_offset       = &(gfx_vbuffer[1][start_x]) - &(gfx_vbuffer[0][end_x]);

    for (int y = start_y; y < end_y; y++, source_pixel_pointer += width + source_x_right_bound, destination_pointer += destination_offset) {
        for (int x = start_x; x < end_x; x++, source_pixel_pointer--, destination_pointer++) {
            char pixel = data[source_pixel_pointer];
            if (transparency && (pixel == MAGENTA)) {
                continue;
            } else {
                *(destination_pointer) = pixel;
            }
        }
    }
}


I managed to claw back a few frames! Laughing I do plan on writing a no-clip version and a non-transparency version for even faster performance, as well as variants for flipping on the y-axis. And a few more nice-to-have graphics functions... I'll post them here once I get them working. And I'll prepare a few carving knives so that you guys can gut me thoroughly for being so wasteful with my calculator's CPU cycles.

Is there anything else that I can do to make this faster? Is there a faster way of drawing a sprite flipped on the x-axis without generating a flipped sprite beforehand?
Even though I'm no longer a child, I can't help but gaze upon the world in awe and wonder.
After some more keyboard mashing and desperate debugging, I managed to write this function that draws only a section of a sprite:

Code:
void draw_sprite_section(gfx_sprite_t* sprite, int dest_x, int dest_y, uint8_t source_start_x, uint8_t source_start_y, uint8_t width, uint8_t height) {
    char* data = (char*) sprite;

    char sprite_width  = data[0];
    char sprite_height = data[1];

    // you know the drill: clipping checks
    int start_x = dest_x < 0 ? 0 : dest_x;
    int start_y = dest_y < 0 ? 0 : dest_y;

    // because we're drawing a section of the sprite here, we also want to check whether we're going to draw out of the bounds of the sprite
    uint8_t draw_width  = (uint8_t) ((start_x + width) >= LCD_WIDTH ? (LCD_WIDTH - start_x - 1) : width);
    draw_width          = (source_start_x + draw_width) >= sprite_width ? (sprite_width - source_start_x - 1) : draw_width;
    int draw_height     = (start_y + height) >= LCD_HEIGHT ? (LCD_HEIGHT - start_y - 1) : height;
    draw_height         = (source_start_y + draw_height) >= sprite_height ? (sprite_height - source_start_y - 1) : draw_height;

    // all of these checks will be skipped in the no-clip version

    // the plan: calculate pointers to rows of pixels, use memcpy
    // we must add 2 to the starting pointer because the first two char values are the width and height of the sprite
    char* source_pointer  = &(data[sprite_width * source_start_y + source_start_x + 2]);
    uint8_t source_offset = sprite_width * sizeof(char);
    uint8_t* dest_pointer = &(gfx_vbuffer[start_y][start_x]);
    int     dest_offset   = &(gfx_vbuffer[1][start_x]) - &(gfx_vbuffer[0][start_x]);

    while (draw_height >= 0) {
        memcpy(dest_pointer, source_pointer, draw_width);
        dest_pointer   += dest_offset;
        source_pointer += source_offset;
        draw_height--;
    }
}


There's no transparency support yet. I don't know if there's a way to efficiently check for transparent pixels without looping through all of them. Or if there's a way to do all of the clipping checks without as many ternary statements...
Even though I'm no longer a child, I can't help but gaze upon the world in awe and wonder.
Here is an algorithm to draw a non-transparent sprite flipped about its x-axis:


Code:
void draw_x_flipped_sprite_noclip(gfx_sprite_t* sprite, uint24_t x, uint8_t y)
{
  uint8_t sprite_width = sprite->width;
  uint8_t sprite_height = sprite->height;
  uint8_t counter = sprite_width;
  uint8_t* sprite_data_ptr = sprite->data + (sprite_width * sprite_height) - 1;
  uint8_t* dest_ptr = &(gfx_vbuffer[y - 1 + sprite_height][x]);

  do
  {
    if (!counter)
    {
      counter = sprite_width;
      sprite_height--;
      dest_ptr -= (LCD_WIDTH + sprite_width);
    }
    else
    {
      *dest_ptr = *sprite_data_ptr;
      dest_ptr++;
      sprite_data_ptr--;
      counter--;
    }

  } while (sprite_height);

  return;
}


It reads the sprite data from the end to the start and draws the sprite onscreen from left-to-right, and from the bottom-up. If GraphX had a function like gfx_GetTransparentColor() (hint, hint Wink ), you could add an if-statement before copying a sprite pixel to check if it was transparent, and then if it was, skip the copy.

Oh wow! That's a lot better, especially since it doesn't have any nested for loops. Maybe that's how I'm going to write graphics functions from now on...

I'm thinking of implementing the following twenty functions in C:

Code:

void gfx_Sprite_FlipX(gfx_sprite_t* sprite, int x, int y);
void gfx_TransparentSprite_FlipX(gfx_sprite_t* sprite, int x, int y);
void gfx_Sprite_FlipY(gfx_sprite_t* sprite, int x, int y);
void gfx_TransparentSprite_FlipY(gfx_sprite_t* sprite, int x, int y);

void gfx_Sprite_FlipX_NoClip(gfx_sprite_t* sprite, int x, int y);
void gfx_TransparentSprite_FlipX_NoClip(gfx_sprite_t* sprite, int x, int y);
void gfx_Sprite_FlipY_NoClip(gfx_sprite_t* sprite, int x, int y);
void gfx_TransparentSprite_FlipY_NoClip(gfx_sprite_t* sprite, int x, int y);

void gfx_Sprite_Section(gfx_sprite_t* sprite, int src_x, int src_y, int width, int height, int dest_x, int dest_y);
void gfx_TransparentSprite_Section(gfx_sprite_t* sprite, int src_x, int src_y, int width, int height, int dest_x, int dest_y);
void gfx_Sprite_Section_FlipX(gfx_sprite_t* sprite, int src_x, int src_y, int width, int height, int dest_x, int dest_y);
void gfx_TransparentSprite_Section_FlipX(gfx_sprite_t* sprite, int src_x, int src_y, int width, int height, int dest_x, int dest_y);
void gfx_Sprite_Section_FlipY(gfx_sprite_t* sprite, int src_x, int src_y, int width, int height, int dest_x, int dest_y);
void gfx_TransparentSprite_Section_FlipY(gfx_sprite_t* sprite, int src_x, int src_y, int width, int height, int dest_x, int dest_y);

void gfx_Sprite_Section_NoClip(gfx_sprite_t* sprite, int src_x, int src_y, int width, int height, int dest_x, int dest_y);
void gfx_TransparentSprite_Section_NoClip(gfx_sprite_t* sprite, int src_x, int src_y, int width, int height, int dest_x, int dest_y);
void gfx_Sprite_Section_FlipX_NoClip(gfx_sprite_t* sprite, int src_x, int src_y, int width, int height, int dest_x, int dest_y);
void gfx_TransparentSprite_Section_FlipX_NoClip(gfx_sprite_t* sprite, int src_x, int src_y, int width, int height, int dest_x, int dest_y);
void gfx_Sprite_Section_FlipY_NoClip(gfx_sprite_t* sprite, int src_x, int src_y, int width, int height, int dest_x, int dest_y);
void gfx_TransparentSprite_Section_FlipY_NoClip(gfx_sprite_t* sprite, int src_x, int src_y, int width, int height, int dest_x, int dest_y);


Assembly would be much faster, but I'll have to make do with C until the graphx officially supports something like this.
Even though I'm no longer a child, I can't help but gaze upon the world in awe and wonder.
I wouldn't really say getting rid of nested loops is better, unless you've reduced the complexity of the actual algorithm.
Drawing a sprite is an O(m*n) algorithm by nature, so you end up with that many iterations of the inner (pixel drawing) loop no matter what.

Folding it all into one loop means you end up checking the outer loop condition on every iteration, even when there's no way the condition could have changed.
  
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
Inefficient nice-to-have graphics routines
»
» 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