Alpha-blending за одно умножение на пиксель на Windows Mobile

Те, кто занимался графикой на Windows Mobile, наверняка слышали о графической библиотеке GapiDraw. Если заглянуть в их Feature List, то в разделе High Performance можно обнаружить следующие слова: «drawing surfaces with opacity will only require one multiplication per pixel». То есть, они утверждают, что для рисования полупрозрачных картинок требуется всего по одному умножению на каждый пиксель.

В данной статье я попытаюсь объяснить, как это возможно.

Во-первых, большинство устройств с Windows Mobile имеет экранчик с 65 тысячами цветов. То есть, для каждого пикселя на экране отведено по 2 байта в памяти. Во-вторых, такие устройства имеют 32 разрядный процессор. На таком процессоре скорость выполнения математических операций с 2-байтовыми числами немногим отличается от скорости работы с 4-байтовыми. Именно здесь кроется одна из оптимизаций вычислений. Графическая библиотека обрабатывает по 2 пикселя одновременно.

Посмотрим, как же устроен 16 разрядный пиксель. Старшие 5 бит отведены для красного цвета, далее 6 бит — для зеленого и оставшиеся 5 бит — для синего.
P = [RRRR RGGG GGGB BBBB]
     15      8 7       0

При этом, сами цвета можно получить с помощью сдвигов и масок по формулам:
int R = (P >> 11) & 0x1f;
int G = (P >> 5) & 0x3f;
int B = P & 0x1f;

А пиксель получается обратным преобразованием:
unsigned short P = (R << 11) + (G << 5) + B;

Когда мы пытаемся нарисовать один пиксель поверх другого с прозрачностью, происходит смешение цветов. Оба пикселя разбиваются на 3 компоненты: красный, синий, зеленый. Далее происходит смешение компонент, красный смешивается с красным, синий — с синим, зеленый — с зеленым. А из полученных значений составляется новый пиксель.

В общем виде смешение цветов выглядит так:
C = C1*α + C2*(1 - α)

C1 — значение красного, зеленого или синего цвета из первого пикселя.
C2 — значение этого же цвета во втором пикселе.
C — результирующий цвет.
α — коэффициент прозрачности, принимает значения от 0 до 1.

Хранить вещественное значение α и оперировать им довольно накладно, особенно на карманных компьютерах, поэтому его ограничивают некоторым целочисленным диапазоном. Обычно используют значения 0-255, но для 5-битного цвета будет достаточно 5-битного α.

Сначала обратим внимание на то, как делается смешение цветов с 50% прозрачностью:
C = C1/2 + C2/2

Деление на 2 можно заменить сдвигом:
C = (C1 >> 1) + (C2 >> 1)

Теперь посмотрим, что произойдет при смешении двух пикселей один к одному:
P = (R1 >> 1 + R2 >> 1) << 11 + (G1 >> 1 + G2 >> 1) << 5 + (B1 >> 1 + B2 >> 1)

Раскрыв скобки получим:
P = (P1 & 0xf7de) >> 1 + (P2 & 0xf7de) >> 1

Маска 0xf7de появляется, чтобы обеспечить правильность сдвига на 1 в каждой компоненте цвета. Сравните:
[RRRR RGGG GGGB BBBB] = P
[0RRR RRGG GGGG BBBB] = P >> 1 // Младший бит одних компонент становится старшим битом других

[RRRR RGGG GGGB BBBB] = P
[1111 0111 1101 1110] = 0xf7de
[RRRR 0GGG GG0B BBB0] = P & 0xf7de // Исправляем этот недостаток перед сдвигом
[0RRR R0GG GGG0 BBBB] = P & 0xf7de >> 1

Аналогично этому способу можно проделать те же операции для смешения пикселей 1 к 3, 1 к 7… Но на этих отношениях данный способ совершенно неэффективен, в основном из-за того, что деление идет раньше умножения. Поэтому сначала следует освободить место для умножения. Заметим, что умножая m-битное беззнаковое число на n-битное, мы получим число занимающее не более m+n бит. То есть, надо освободить по 5 бит перед каждым цветом, а для этого можно разделить цвета пикселя на четные и нечетные и оперировать уже ими. Так мы подошли к следующей процедуре смешения, использующей 2 умножения на пиксель:
#define Shift(p)   ((p)>>5)
#define OddCol(p)  ((p) & 0x07E0F81F)
#define EvenCol(p) ((p) & 0xF81F07E0)

// Забираем из каждого буффера по 2 пикселя
register unsigned int p1 = *dst;
register unsigned int p2 = *(src++);

// Здесь 4 умножения, но мы обрабатываем 2 пикселя одновременно
*(dst++) = OddCol( Shift(OddCol(p1)*a + OddCol(p2)*(32 - a)) ) |
           EvenCol( Shift(EvenCol(p1))*a + Shift(EvenCol(p2))*(32 - a) );

Как же избавиться от еще одного умножения? Попробуем раскрыть скобки и перегруппировать слагаемые:
C = (C1*α + C2*(32 - α)) >> 5 = (C1 - C2)*α >> 5 + C2

Но в скобках может получиться отрицательное число, а арифметические операции с отрицательными числами основаны на переполнении. Таким образом, применить формулу в данном виде для распараллеливания вычислений невозможно. Поэтому избавимся от отрицательных значений прибавив максимально возможное:
C = (C1 - C2 + 32 - 32)*α >> 5 + C2 = (C1 - C2  + 32)*α >> 5 + C2 - α

С помощью этой формулы и трюка с четными и нечетными цветами можно получить процедуру смешения пикселей, использующую всего одно умножение на пиксель:
#define OddCol(p)  ((p) & 0x07E0F81F)
#define EvenCol(p) ((p) & 0xF81F07E0)

register unsigned int p1 = *dst;
register unsigned int p2 = *(src++);

register unsigned int oddA = (a<<22) | (a<<11) | (a);
register unsigned int evenA = (a<<27) | (a<<16) | (a<<6);
register unsigned int oddP2 = OddCol(p2);
register unsigned int evenP2 = EvenCol(p2);

// 2 умножения при обработке 2 пикселей
oddCol = (((OddCol(p1) - oddP2 + 0x08010020) * a) >> 5) + oddP2 - oddA;
evenCol = ((( (EvenCol(p1)>>5) - (evenP2>>5) + 0x08010040) * a) + evenP2 - evenA );

*(dst++) = OddCol(oddCol) | EvenCol(evenCol);
Поддержать автора
Поделиться публикацией

Похожие публикации

Комментарии 12

    +1
    Грамотно :) Вехой будет Unreal 1 в software mode на мобильнике
      +1
      Спасибо огромное, прям ну очень в тему легло!
      Как раз сейчас сижу и вывод 16 бит графики оптимизирую, в т.ч. и с альфа-каналом.
        0
        Тогда рекомендую опробовать оба способа. На некоторых устройствах способ с двумя умножениями на пиксель показывал чуть большую производительность. ;)
          0
          Да, конечно. Я еще и с ассемблером поэкспериментирую.
          У меня еще и источник premultiplied в большинстве случаев. Но, главное, информация к размышлению есть.
            –1
            Теперь понятно почему в моей NVideo Riva TNT2 ускорение работало только в 16-битном режиме
              0
              Это неправда. Ускорение там работает и в 32-битном режиме. Не смешивайте теплое и мягкое и учите матчасть.
        0
        >> oddA = (a<<22) | (a<<11) | (a);
        А зачем вы двигаете 2 компонента, если достаточно подвинуть только G?
          0
          протупил =)
            +2
            На всякий случай распишу подробнее:

            [RRRR RGGG GGGB BBBB RRRR RGGG GGGB BBBB] = P // 2 пикселя
            [0000 0111 1110 0000 1111 1000 0001 1111] = 0x07E0F81F
            [0000 0GGG GGG0 0000 RRRR R000 000B BBBB] = P & 0x07E0F81F = P' // выделяем нечетные компоненты

            [A AAAA] = a // коэффициент прозрачности состоит из 5-ти бит

            [0000 0AAA AA00 0000 AAAA A000 000A AAAA] = oddA // выравниваем α по нечетным компонентам
            [GGGG GGGG GGGR RRRR RRRR R0BB BBBB BBBB] = P' * oddA // после умножения компоненты начинают занимать выделенные пространства
            [0000 0GGG GGGG GGGG RRRR RRRR RR0B BBBB] = P' * oddA >> 5 = P" // выравниваем полученные значения
            [0000 0GGG GGG0 0000 RRRR R000 000B BBBB] = P" & 0x07E0F81F // очищаем место для вставки четных компонент
              +2
              Меня одолевает непреодолимое чувство фейспалма,
              не только потому что я проглядел по диагонали вашу статью, но
              и что я сам такое же делал на GBA в своё время =)

              Слова о 2х умножениях на пиксел, не иначе как под воздействием космических лучей, у меня в голове резюмировались примерно следующим образом

              ldrh C1, [src, #0]
              ldrh C2, [dst, #0]

              or ps, C1, C1, LSL #16; ?G?R?B
              and ps, ps, mask_G_R_B; 0G0R0B
              or pd, C2, C2, LSL #16
              and pd, pd, mask_G_R_B

              mul ps, ps, alpha ;fast 32х8 bit mul
              mla ps, pd, inv_alpha, ps

              and ps, mask_G_R_B, ps, LSR #5
              or ps, ps, LSR #16

              strh ps, [dst, #0]
          0
          Спасибо за статью, многим новичкам будет полезно. Однако алгоритм, озвученный здесь не является чем-то новым, все всегда так и кодили демки для svga-режимов. Подробнее есть в demo design faq от лохматого года.
            0
            Да, все уже написано до нас:)
            Просто хотелось показать путь размышлений, как можно прийти к этому алгоритму.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое