4. monochrom-bitmap um 90 grad drehen

monochrom-bitmap um 90 grad drehen

  • N

    hallo,
    ich habe eine kleine grafik, 32*32 pixel, gespeichert als array zu 32 unsigned longs, pro zeile also ein 32-bit wert. ich möchte diese nun gerne um 90% drehen, so dass aus zeilen spalten werden und umgekehrt. ich habe mir ein paar funktionen gebastelt, mit denen das geht. dazu wird ein array von 128 bytes mit nullen initialisiert, und dann die funktion 'rot32x32' aufgerufen (siehe unten). mich beschleicht nur der verdacht, dass es auch einfacher geht. hat jemand eine idee oder einen fertigen algo etc?

    void bitset (UINT8 *arr, UINT16 bit)
{
   UINT16 byteoffset = bit/8;
   UINT8 bitoffset = 7 - bit%8;
   //printf ("%d(%d, %d)\n", bit, byteoffset, bitoffset);
   arr[byteoffset] |= (1<<bitoffset);
}

int bitget (UINT8 *arr, UINT16 bit)
{
   UINT16 byteoffset = bit/8;
   UINT8 bitoffset = 7 - bit%8;
   //printf ("%d(%d, %d) --> ", bit, byteoffset, bitoffset);
   return !!(arr[byteoffset] & (1<<bitoffset));
}

void rot32x32 (UINT8 *in, UINT8 *out)
{
   UINT16 s;
   UINT16 n;
   UINT16 bcount = 0;
   for (s=0; s<32; s++)
   {
      for (n=0; n<32; n++)
      {
         if (bitget (in, n*32+s))
            bitset (out, bcount);
         bcount++;
      }
   }
}
    0
  • C

    hm, du koenntest dir die expansion in ein 128 byte feld sparen und direkt in ein neues 32 long array reinschreiben.
    mit shiftoperatoren, binaer-und und binaer-oder geht das.

    edit: aehm, ich seh in deinem code keine 128 bytes. offenbar machst du es schon wie ich das vorschlagen wollte.

    0
  • N

    c.rackwitz schrieb:

    edit: aehm, ich seh in deinem code keine 128 bytes. offenbar machst du es schon wie ich das vorschlagen wollte.

    genau. aber das ist, wie mir scheint, die hau-ruck methode. das ding braucht z.b. 1024 schleifendurchläufe. bestimmt gibt es eine gescheiten alogrithmus, der sowas viel schneller kann. aber wo finde ich einen?

    0
  • C

    nein, es braucht nur 128 durchlaeufe.

    du koenntest eine zeile (einen long) auf einmal belegen, indem zu den innersten loop (per hand) ausrollst (viel shifting).
    dabei gewinnst du aber nicht viel bei so kleinen arrays.

    edit: eleganter geht es nicht, weil bei der 90-grad-drehung immer zwei benachbarte "pixel" im jeweils anderen array genau 32 ints abstand voneinander haben.

    0
  • N

    c.rackwitz schrieb:

    edit: eleganter geht es nicht,

    na, das will ich erstmal bezweifen. ich hab' da was interessantes gefunden: http://www.acm.org/pubs/tog/GraphicsGems/gemsii/rotate8x8.c
    mal sehen, ob mir das irgendwie weiterhilft.
    jedenfalls danke für deine hilfe 🙂

    0
  • C

    ueberleg doch mal, wieviele operationen dieses rotate8x8 verbraucht und wieviele deine routine verbraucht.
    beides sehr aehnlich, nur dass rotate8x8 quasi die loops ausgerollt hat und makros benutzt, um das zu verstecken.

    0
  • N

    c.rackwitz schrieb:

    ueberleg doch mal, wieviele operationen dieses rotate8x8 verbraucht und wieviele deine routine verbraucht.
    beides sehr aehnlich, nur dass rotate8x8 quasi die loops ausgerollt hat und makros benutzt, um das zu verstecken.

    hmpfff?! stimmt. so ein beschiss!

    0
  • C

    wie gesagt, du kannst keine zwei "pixel" mit einer operation gleichzeitig lesen und schreiben. also brauchst du auf jeden fall 128 lese-schreib-operationen.
    du kannst nur optimieren, dass du die bits in einem register (volatile/register unsigned long) sammelst und dann in den speicher schreibst (eine zeile soll ja long sein).
    dass die and/or/shift operationen optimal sein muessen, versteht sich.

    0
Anmelden zum Antworten