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);