Geum.ru

Низкоуровневое программирование для Дzenствующих

Вид материалаДокументы

Содержание


Алгоритм быстрой реализации alpha-blitting'а.
Подобный материал:
1   ...   15   16   17   18   19   20   21   22   ...   42

Алгоритм быстрой реализации alpha-blitting'а.


Альфа-блитинг (полупрозрачное наложение поверхностей) позволяет создавать красивые и интересные, а иногда и просто полезные эффекты. К сожалению при использовании альфа-блитинга приходится сталкиваться с одной очень не приятной проблемой – его слишком медленной реализацией. Связанно это с тем, что DirectDraw не предоставляет аппаратной поддержки данной процедуры (я уже не говорю про включение её в HAL и эмуляцию, если видеокарта её выполнить не может), поэтому приходиться не только использовать программную эмуляцию, но ещё и каждый раз изобретать велосипед, создавая эту самую программную эмуляцию заново. Конечно, можно использовать Direct3D, он поддерживает текстурирование с использованием альфа-ключа. Но, на мой взгляд, это совершенно лишнее, если у вас ни о какой трёхмерной графике речь не идёт, а просто необходимо скопировать несколько прямоугольных областей и хочется сделать это с альфа-ключом. И вот тут проблема скорости встаёт со всей своей злободневностью даже на P4 – каждую цветовую компоненту необходимо обрабатывать отдельно, а это очень медленно. В данной статье я собираюсь изложить достаточной простой алгоритм блочного преобразования цветовых компонент, который позволяет увеличить скорость работы в три раза по сравнению с обыкновенным. Кроме того, я приведу вариант реализации данного алгоритма с использованием набора инструкций MMX, что даёт прирост ещё на 25% по сравнению с реализацией его на чистом С.

Начнём с простой математики. Допустим, у нас есть две поверхности s1 и s2, а также альфа-ключ а, который показывает степень прозрачности. Тогда, если мы копируем поверхность s1 в s2, к цветовым компонентам пикселов мы должны применить следующие преобразования:

s1[x][y][ck] = a*(s1[x][y][ck] – s2[x][y][ck]) + s2[x][y][ck],


где ck {r, g, b} и 0<=a<=1 (1).

Как видите, не слишком быстро получается – сначала нам необходимо выделить цветовую компоненту из пары копируемых пикселей. Если у нас 24-х или 32-х битный режим, то это сделать довольно просто – один байт, одна компонента. А как быть с 16-ти и 15-ти битными режимами? Тут придётся использовать маски и накладывать их по AND, и, если не пересчитать для каждой цветовой компоненты отдельно, то и использовать команду сдвига, чтобы поместить цветовую компоненту в начала байта. И только после этого мы сможем произвести необходимы вычисления, среди которых есть умножение. Потом опять необходимо будет соединить цветовые компоненты в единый пиксел – и опять таки, для 24-х и 32-х битовых режимов проблем как бы нет, а вот для 15-ти и 16-ти опять придётся использовать сдвиг и последующее наложение по OR.

Если вы думаете, что на этом проблемы и заканчиваются, то вы глубоко заблуждаетесь. Как известно, математика оперирует непрерывным континуумом чисел, а мы, то есть компьютер – дискретным. Кроме того, существует ещё одно ограничение – все операции должны проводиться только в целых числах (конечно, можно и в double, но это слишком уж медленно). Поэтому реальный код будет выглядеть несколько иначе, а именно.

unsigned char getColorComponent(unsigned long pixel, unsigned componentNum);

void setColorComponent(unsigned long pixel, unsigned componentNum,

unsigned char componentValue);

unsigned long getPixel(unsigned surfNum, unsigned x, unsigned y);


unsigned long pixel1 = getPixel(1, 0, 0);

unsigned long pixel2 = getPixel(2, 0, 0);

extern unsigned long alphaKey;

for(unsigned i=0;i<3;i++) {

long l1 = getColorComponent(pixel1, i);

long l2 = getColorComponent(pixel2, i);

l1 = ((l1 - l2)*alphaKey)/255 + l2;

setColorComponent(pixel1, i, l1);

}

Первое, на что необходимо обратить внимание – это расширение типа для цветовой компоненты с unsigned char до unsigned long (предполагается, что всё происходит на wintel-платформе). Если вы внимательно посмотрите на (1), то увидите, что при выполнении вычитания цветовых компонент может возникнуть переполнение, если вторая цветовая компонента окажется больше первой. Если мы не расширим тип, то часть данных будет утеряна и наложение будет выполнено неправильно. Второе – это, конечно же, замена простой конструкции (s1 – s2)*a на более сложную (s1 – s2)*a/255 и, соответственно, изменение диапазона альфа-ключа с 0<=a<=1 на 0<=a<=255. Это связанно с тем, что мы используем целочисленные вычисления. Конечно, эту строчку можно упростить и сделать в виде l1 = (((l1 – l2)*alphaKey)>>8) + l2. Изменение коэффициента нормировки на единицу на глаз заметно не будет. Дальше, если ввести ограничение, что альфа-ключ принимает значение а пределах 0<=a<=8, то можно вообще избавится от умножения и сделать следующее.

unsigned nak = 8 – alphaKey;
…..
l1 = ((l1 – l2)>>nak) + l2;
…..

Уже существенно лучше. Но, если вы примените этот метод, то будете разочарованы – это работает всё ещё медленно. Где узкое место? В тройном обращении к памяти - мы извлекаем компоненты поочерёдно. И, естественно, в приведении типов. Можно ли ускорить эту операцию? Да, можно, написав, например, всё на ассемблере, максимально использую регистры, уменьшив тем самым количество обращений к памяти. А можно сделать несколько иначе. Давайте ещё раз посмотрим на нашу оптимизированную формулу и уясним, что же мы должны сделать с каждой компонентой. Для этого раскроем скобки.

s1[x][y][ck] = a*s1[x][y][ck] – а*s2[x][y][ck] + s2[x][y][ck],


или, в упрощённом варианте,


l1 = (l1>>nak) – (l2>>nak) + l2;

Теперь немного поменяем порядок выполнения операций.

l1 = (l1>>nak) + l2 – (l2>>nak);

Что у нас получилось? Во-первых, переполнение больше не может возникнуть, так как величина "l2 – (l2>>nak)" всегда больше либо равна нулю, а само выражение не выйдет за пределы отведённого количества бит (8-и бит для 24-х и 32-х битных режимов и 5-и бит для 15-ти и 16-ти битных). Во-вторых, так как переполнения больше нет, мы можем применить потоковую обработку для 32-х бит сразу, не выделяя отдельно цветовых компонент! Вот вам и увеличение скорости в три раза. Сделать это очень просто. Возьмём, для примера, 15-ти битный режим и посмотрим внимательно на то, как биты компонент расположены в слове (рис. 1).

0
r
r
r
r
r
g
g
g
g
g
b
b
b
b
b

Для того чтобы корректно выполнить сдвиговые операции, которые на самом деле являются простым делением, нам необходимо сначала прочистить данное слово маской, а потом выполнить сдвиг всего слова целиком. После чего мы можем выполнить оставшиеся операции сложения и вычитания целиком для всего слова, так как полученные значения гарантировано не выйдут за пределы значений, отданных на одну цветовую компоненту и, таким образом, не смогут испортить данные в соседних битах. На рис. 2 представлена ситуация для 15-ти битного режима и альфа-ключа равного шести.

0
r
r
r
r
r
g
g
g
g
g
b
b
b
b
b




AND alphaMask

0
1
1
1
0
0
1
1
1
0
0
1
1
1
0
0




=

0
r
r
r
r
r
g
g
g
g
g
b
b
b
b
b




>> (сдвиг на alphaShift)

0
0
0
r
r
r
0
0
g
g
g
0
0
b
b
b




А в коде это будет выглядеть следующем образом.

unsigned long a1 = getPixel(1, 0, 0);

unsigned long a2 = getPixel(2, 0, 0);


a1 &= m_uAlphaMask;

a1>>=m_uAlphaShift;

a1 += a2 - ((a2&alpha&alphaMask)>>alphaShift);

setPixel(1, 0, 0, a1);

Где alphaMask является маской, которой необходимо прочистить двойное слово перед сдвигом, а alphaShift – собственно величиной сдвига. Собственно, реализация MMX использует тот же принцип, только по восемь байт за раз, а не по четыре.

Что ещё можно упростить? Можно разделить собственно альфа-блитинг и альфа-заполнение. Для альфа-заполнения можно ещё существеннее поднять скорость, так как мы избежим лишнего обращения к поверхности s2, плюс уменьшим количество вычислений. Или, более конкретно (предполагается, что fillColor задаётся в формате поверхности, которую будут заполнять).

s1[x][y][ck] = a*s1[x][y][ck] + nfillColor,

где nfillColor = s2[x][y][ck] – а*s2[x][y][ck] и вычисляется за циклом. Или

unsigned long a1 = getPixel(1, 0, 0);

unsigned long nfillColor = fillColor - ((fillColor&alpha&alphaMask)>>alphaShift);


a1 &= m_uAlphaMask;

a1>>=m_uAlphaShift;

a1 += nfillColor;

setPixel(1, 0, 0, a1);

Те, кто любит изобретать велосипед, уже могут запускать свой любимый компилятор, ну а для остальных приведу несколько функций из моей графической библиотеки, которая, кроме всего прочего, занимается ещё и альфа-блитингом.

Прежде чем привести необходимый код, дам несколько пояснений относительно встречающихся там классов, исходный код которых не был включён в статью, так как к альфа-блитингу он никакого отношения не имеет. TVideoCard – основной класс видеокарты, который устанавливает необходимый видеорежим и, что более важно для нас, хранит данные о текущем формате пикселей, который можно получить с помощью метода TVideoCard::PixelFormat(). Что касается TPixelFormat, то там должно быть всё понятно из имён его полей. Дальше, TSurface, предоставляет следующие необходимые методы: Lock()/Unlock() для блокирования поверхности с целью получения прямого доступа к её данным и разблокирования соответственно, DataPtr() возвращает указатель на начало данных поверхности, FullRowLen() – полную длину одной строки поверхности, она может быть больше, чем длина умноженная на количество байт на один пиксел. Класс TRect – описывает прямоугольную область с помощью задания левой верхней точки (методы X(), Y()) и длины с шириной (методы W(), H()). В ссылка скрыта находиться С++ реализация данного алгоритма, а в ссылка скрыта – ассемблерная (следует учесть, что ассемблерная реализация использует переменные, объявленные в С++ реализации, а разделение сделано только для наглядности). Есть правда два "но". Первое: я использую портированный gcc в качестве компилятора, поэтому ассемблерный код написан с использованием синтаксиса AT&T. Второе: никаких проверок функции не делают, всё что выходит за пределы четырёх (для С++ реализации) или восьми (для MMX реализации) байт просто игнорируют. Вот и всё, дальше – rtfs.