Rotating and drawing bitmaps on a GLCD (ks0108)

Hi.

In order to make simple animations with my graphic LCD (128x64), I wrote a function that rotates bitmap images by an arbitary angle and then draws it using an altered DrawBitmap-function http://www.arduino.cc/playground/Code/GLCDks0108 which is part of the ks0108 library by mem.

I’m very new to C and libraries, so it is very likely that I did everything the way I shouldn’t have - I’m happy if you correct my code - but it’s definitely working.

See what the turning dolphin looks like:
http://www.wunderwald.ch/pics/delfin_am_eintauchen.avi

That is the Sketch:

#include <ks0108.h>
#include <ks0108_Panel.h>
#include <SystemFont5x7.h>   // system font
#include <delfin_am_eintauchen_56x56.h>   // Bitmap

/*
 * Bitmap Rotation
 * Programm rotates a bitmap from PROGMEM, stores the rotated image in an array in RAM
 * and displays the rotated image. Non-square images might get cropped.
 */

unsigned long startMillis;
unsigned int iter = 0;              // used to calculate the frames per second (FPS)
float winkel = 0;                   // angle the bitmap is to be rotated by

void setup(){
  Serial.begin(57600);
  GLCD.Init(NON_INVERTED);   // initialise the library, non inverted writes pixels onto a clear screen
  GLCD.ClearScreen();  
  GLCD.SelectFont(System5x7); // switch to fixed width system font 
}

void Rotate_and_Draw_Bitmap(const uint8_t * bitmap, float winkel, uint8_t x, uint8_t y, uint8_t color){
  uint8_t width, height;
  width = ReadPgmData(bitmap++);            // Read the image width from the array in PROGMEM
  height = ReadPgmData(bitmap++);           // Read the height width from the array in PROGMEM

  float altes_x, altes_y, neues_x, neues_y; // old and new (rotated) Pixel-Coordinates

  float drehpunkt_x = width / 2 + 0.5;      // Calculate the (rotation) center of the image (x fraction)
  float drehpunkt_y = height / 2 + 0.5;     // Calculate the (rotation) center of the image (y fraction)

  float sin_winkel = sin (winkel);          // Pre-calculate the time consuming sinus
  float cos_winkel = cos (winkel);          // Pre-calculate the time consuming cosinus
  uint8_t gedrehtes_bild[height/8*width+2]; // Image array in RAM (will contain the rotated image)
  
  for (int i = 0; i < height/8*width+2; i++){gedrehtes_bild[i] = 0;}  // Clear the array
  int i, j, counter = 0;

  gedrehtes_bild[0] = width;                // First byte of the rotated image contains (as the original) the width
  gedrehtes_bild[1] = height;               // Second byte of the rotated image contains (as the original) the height

  for(i = 0; i < height * width / 8; i++) { // i goes through all the Bytes of the image
         uint8_t displayData = ReadPgmData(bitmap++);  // Read the image data from PROGMEM
       for(j = 0; j < 8; j++) {           // j goes through all the Bits of a Byte
                   if(displayData & (1 << j)){ // if a Bit is set, rotate it
                     altes_x = ((i % width) + 1) - drehpunkt_x;                     // Calculate the x-position of the Pixel to be rotated
                     altes_y = drehpunkt_y - (((int)(i/width))*8+j+1);              // Calculate the y-position of the Pixel to be rotated
                     neues_x = (int) (altes_x * cos_winkel - altes_y * sin_winkel); // Calculate the x-position of the rotated Pixel
                     neues_y = (int) (altes_y * cos_winkel + altes_x * sin_winkel); // Calculate the y-position of the rotated Pixel
                     
                     // Check if the rotated pixel is withing the image (important if non-square images are used). If not, continue with the next pixel.
                     if (height == width || (neues_x <= (drehpunkt_x - 1) && neues_x >= (1 - drehpunkt_x) && neues_y <= (drehpunkt_y - 1) && neues_y >= (1 - drehpunkt_y))){ 
                       // Write the rotated bit to the array (gedrehtes_bild[]) in RAM
                       gedrehtes_bild[(int)(neues_x + drehpunkt_x)%width + ((int)((drehpunkt_y - neues_y - 1) / 8)*width) +2] |= (1 << (int)(drehpunkt_y - neues_y - 1)%8); 
                     }
                   }
       }
  }
  GLCD.DrawRamBitmap(gedrehtes_bild,x,y,color); // Draw the rotated image
}



void loop(){   // run over and over again
  iter = 0;
  startMillis = millis();
  while( millis() - startMillis < 1000){ // loop for one second
    winkel += 5;                         // increase angle by 5 degrees
    Rotate_and_Draw_Bitmap(delfin_am_eintauchen_56x56, winkel/57, 50,8, BLACK); // Division by 57, because the function expects an angle in radians, not degrees.
    iter++;
  } 
  //display number of iterations in one second
  GLCD.CursorTo(0,0);              // positon cursor  
  GLCD.Puts("FPS=");               // print a text string
  GLCD.PrintNumber(iter);          // print the number of iterations per second
  
}

That is the extension you have to add to ks0108.cpp (Section «public»):

      void DrawRamBitmap(const uint8_t * bitmap, uint8_t x, uint8_t y, uint8_t color);

That is the extension you have to add to ks0108.h:

void ks0108::DrawRamBitmap(const uint8_t * bitmap, uint8_t x, uint8_t y, uint8_t color){
      uint8_t width, height;
      uint8_t i, j;
      int z = 0;
      width = bitmap[z++]; 
      height = bitmap[z++];
      for(j = 0; j < height / 8; j++) {
            this->GotoXY(x, y + (j*8) );
            for(i = 0; i < width; i++) {
                  uint8_t displayData = bitmap[z++];
                  if(color == BLACK)
                        this->WriteData(displayData);
                  else
                        this->WriteData(~displayData);
            }
      }
}

That is the image that I used in the example:

And here comes the headerfile the image was converted to using glcd2bitmap:

/* delfin_am_eintauchen_56x56.h bitmap file for GLCD library */
/* Bitmap created from delfin_am_eintauchen_56x56.bmp        */
/* Date: 17 Feb 2010                             */

#include <inttypes.h>
#include <avr/pgmspace.h>

#ifndef delfin_am_eintauchen_56x56_H
#define delfin_am_eintauchen_56x56_H

static uint8_t delfin_am_eintauchen_56x56[] PROGMEM = {
  56, // width
  56, // height

  /* page 0 (lines 0-7) */
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  /* page 1 (lines 8-15) */
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  0x0,0xc0,0xc0,0x80,0x0,0x0,0x0,0x0,0x0,0x80,0x80,0x80,0x80,0x80,0xc0,0xc0,
  0xc0,0xc0,0xc0,0xe0,0xc0,0xe0,0xe0,0xc0,0xe0,0x60,0x40,0xf0,0xb0,0xc0,0x80,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  /* page 2 (lines 16-23) */
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x80,0x80,0xe0,
  0x7e,0x3f,0x1,0x3,0x3,0x2,0x3,0x3,0x3,0xc3,0x60,0xd1,0x29,0x14,0x1c,0xe,
  0x6,0x7,0x1,0x3,0x1,0x0,0x1,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  /* page 3 (lines 24-31) */
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x80,0xf0,0x7c,0x14,0x7,0x3,0x0,
  0x0,0x0,0x80,0xc0,0xe0,0x38,0x38,0xe,0x3,0x3,0x0,0x0,0x0,0x0,0x0,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  /* page 4 (lines 32-39) */
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x78,0xff,0xc1,0x0,0x88,0xe0,0xf0,0x3c,
  0xc,0xc,0xf,0xe,0x6,0x2,0x2,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  /* page 5 (lines 40-47) */
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x1,0xf,0xf,0x7,0x1,0x0,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  /* page 6 (lines 48-55) */
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
  0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0
};
#endif

Hope, you can use it!
Thanks for your input,

Dani

Simple speed up trick (please take this as constructive):

  1. Precompute a sin/cos lookup table (LUT), 256 values (instead of 360).

  2. Pass your angle (0-255) and read the lookup table for the sin/cos values (floats).

  3. Instead of floats, use fixed-point integer math.

  4. Talk to a graphics demo coder (or do some research); you can get much better speed out of this than the "brute force" method you show, but it will take some research, understanding, and time.

  5. Hmm - is there an Arduino fixed-point math library; a fixed-point 3D math library for the Arduino would be pretty cool...

  6. Definitely an interesting "first effort" to see, though! Thanks for sharing!

:)

CrOsh! I take it very constructive, thanks! I'll try to implement these enhancements and try to put it all into a (the) library.

Indeed, I'd like to do something like Rotation by Shear http://www.leptonica.com/rotation.html, but as you say, that needs understanding and time. Bruteforce was easely done up in the mountains without internet :)

Dani

Actually, brute force is (nearly) always the best way to start out any coding project - get the code in and working, with the features you need. Then move on to optimization.

If you read enough about "how to be/become a demo coder", you will eventually come upon someone saying nearly the same thing. At one time in a past life I played around with various demo coding "tricks" (mostly the low level stuff - unlimited bobs, 3d bobs, plasmas, rotations, zooms, simple 3D, fire effects, etc) - as I learned, the most important maxim was "never optimize your code early".

The main reason is that by optimizing your code before it is ready, you might actually make it slower than if you had waited. Also, pre-optimization might cause the compiler to barf and make it slower as well. There was also the issue that you might pre-optimize what you thought was going to be the final inner loop, only to later find that you needed to add something inside that.

Which leads to one of the big optimizing tricks when you get to it: Optimize the inner loop first (and the best trick to doing so, if you can get away with it, provided what is being done in the loop isn't too complex - is to "unroll" the loop), then move on to the next outer loop if you need more speed.

Also, look up tables (LUTs), like I mentioned before - are very important. As is using fixed-point math, and sizing your variables correctly (ie, don't use an int if the data is only between 0-255 in value), as well as sizing your data for the pipeline (this was mainly for graphics; if your graphics pipeline works best on even bytes, size the data for that - which is why on many console systems of yesteryear, like the NES, sprites were 8x8 pixels).

I don't even know what today's tricks are; I am sure there are some, but the hardware has gotten so good (I'm talking PC and console realm here) that you can almost throw crappy code at the GPU and it will still run it fast enough to get by.

But these tricks are worth keeping in mind when you are talking about little processors like is used in the Arduino...

Good luck with your project!

:)

Cr0sh, I tried some of your ideas. The change to integer-math showed quite a speedbump, the lookuptables however didn’t make any difference. It seems that the cos/sin-calculations only take a small portion of the processor-time.

It will develop further with time.

So, with 22fps, one could rotate images now with the following code (and the above mentioned additions to mems code (ks0108.h/ks0108.cpp):

#include <ks0108.h>
#include <ks0108_Panel.h>
#include <SystemFont5x7.h>   // system font
#include <delfin_am_eintauchen_56x56.h>   // Bitmap
#include <string.h> // Noetig fuer memset
/*
 * Bitmap Rotation
 * Programm rotates a bitmap from PROGMEM, stores the rotated image in an array in RAM
 * and displays the rotated image. Non-square images might get cropped.
 */

long unsigned int startMillis;
short unsigned int iter = 0;              // used to calculate the frames per second (FPS)
int winkel = 0;      // angle the bitmap is to be rotated by
void setup(){
  Serial.begin(57600);
  GLCD.Init(NON_INVERTED);   // initialise the library, non inverted writes pixels onto a clear screen
  GLCD.ClearScreen();  
  GLCD.SelectFont(System5x7); // switch to fixed width system font 
}

void Rotate_and_Draw_Bitmap(const uint8_t * bitmap, int winkel, uint8_t x, uint8_t y, uint8_t color){
  uint8_t width, height;
  width = ReadPgmData(bitmap++);            // Read the image width from the array in PROGMEM
  height = ReadPgmData(bitmap++);           // Read the height width from the array in PROGMEM

  int altes_x, altes_y, neues_x, neues_y; // old and new (rotated) Pixel-Coordinates

  int drehpunkt_x = width / 2;      // Calculate the (rotation) center of the image (x fraction)
  int drehpunkt_y = height / 2;     // Calculate the (rotation) center of the image (y fraction)

  float winkel_rad = winkel / 57.3;

  float sin_winkel = sin(winkel_rad);   // Lookup the sinus
  float cos_winkel = cos(winkel_rad);   // Lookup the cosinus

  uint8_t gedrehtes_bild[height/8*width+2]; // Image array in RAM (will contain the rotated image)
  memset(gedrehtes_bild,0,sizeof(gedrehtes_bild)); // Clear the array with 0
  
  int i, j, counter = 0;

  gedrehtes_bild[0] = width;                // First byte of the rotated image contains (as the original) the width
  gedrehtes_bild[1] = height;               // Second byte of the rotated image contains (as the original) the height

  for(i = 0; i < height * width / 8; i++) { // i goes through all the Bytes of the image
         uint8_t displayData = ReadPgmData(bitmap++);  // Read the image data from PROGMEM
       for(j = 0; j < 8; j++) {           // j goes through all the Bits of a Byte
                   if(displayData & (1 << j)){ // if a Bit is set, rotate it
                     altes_x = ((i % width) + 1) - drehpunkt_x;                     // Calculate the x-position of the Pixel to be rotated
                     altes_y = drehpunkt_y - (((int)(i/width))*8+j+1);              // Calculate the y-position of the Pixel to be rotated
                     neues_x = (int) (altes_x * cos_winkel - altes_y * sin_winkel); // Calculate the x-position of the rotated Pixel
                     neues_y = (int) (altes_y * cos_winkel + altes_x * sin_winkel); // Calculate the y-position of the rotated Pixel
                     
                     // Check if the rotated pixel is withing the image (important if non-square images are used). If not, continue with the next pixel.
                     if (neues_x <= (drehpunkt_x - 1) && neues_x >= (1 - drehpunkt_x) && neues_y <= (drehpunkt_y - 1) && neues_y >= (1 - drehpunkt_y)){ 
                       // Write the rotated bit to the array (gedrehtes_bild[]) in RAM
                       gedrehtes_bild[(neues_x + drehpunkt_x)%width + ((int)((drehpunkt_y - neues_y - 1) / 8)*width) +2] |= (1 << (drehpunkt_y - neues_y - 1)%8); 
                     }
                   }
       }
  }
  GLCD.DrawRamBitmap(gedrehtes_bild,x,y,color); // Draw the rotated image
}



void loop(){   // run over and over again
  iter = 0;
  startMillis = millis();
  while( millis() - startMillis < 1000){ // loop for one second
    winkel += 2;                         // increase angle by 4 degrees
    Rotate_and_Draw_Bitmap(delfin_am_eintauchen_56x56, winkel, 50,8, BLACK); 
    iter++;
  } 
  //display number of iterations in one second
  GLCD.CursorTo(0,0);              // positon cursor  
  GLCD.Puts("FPS=");               // print a text string
  GLCD.PrintNumber(iter);          // print the number of iterations per second
  
}

Has anyone tried the code, altered it, made it better/faster? I’m looking forward to feedback!

Thanks, Dani