Более быстрое альфа-смешивание с использованием таблицы поиска? - PullRequest
Новая
       34

Более быстрое альфа-смешивание с использованием таблицы поиска?

1 голос
/ 26 марта 2011

Я создал таблицу поиска, которая позволяет смешивать два однобайтовых канала (256 цветов на канал), используя однобайтовый альфа-канал, не используя значений с плавающей запятой (следовательно, нет преобразования с плавающей запятой в int).Каждый индекс в таблице поиска соответствует значению 256-ых канала, относящемуся к альфа-значению.

В целом, чтобы полностью рассчитать 3-канальное смешение RGB, потребовалось бы два поиска в массиве на канал, плюс добавление.Это всего 6 поисков и 3 дополнения.В приведенном ниже примере я разбил цвета на отдельные значения для упрощения демонстрации.В этом примере показано, как смешать три канала, RG и B, с альфа-значением в диапазоне от 0 до 256. 

BYTE r1, r2, rDest;
BYTE g1, g2, gDest;
BYTE b1, b2, bDest;

BYTE av; // Alpha value
BYTE rem = 255 - av; // Remaining fraction

rDest = _lookup[r1][rem] + _lookup[r2][av];
gDest = _lookup[g1][rem] + _lookup[g2][av];
bDest = _lookup[b1][rem] + _lookup[b2][av];

Прекрасно работает.Точно так же, как вы можете использовать 256 цветовых каналов.Фактически, вы получите те же точные значения, используя фактические вычисления с плавающей запятой.Таблица поиска была рассчитана с использованием двойников для начала.Таблица поиска слишком велика, чтобы поместиться в этом посте (65536 байт).(Если вам нужна его копия, напишите мне по адресу ten.turtle.toes@gmail.com, но не ожидайте ответа до завтра, потому что я сейчас засну.)

Итак .... что ты думаешь?Стоит это или нет?

Ответы [ 3 ]

5 голосов
/ 26 марта 2011

Мне было бы интересно увидеть некоторые тесты.

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

Я также давно реализовал реализацию SSE, если вам интересно ...

void PreOver_SSE2(void* dest, const void* source1, const void* source2, size_t size)
{
    static const size_t STRIDE = sizeof(__m128i)*4;
    static const u32 PSD = 64;

    static const __m128i round = _mm_set1_epi16(128);
    static const __m128i lomask = _mm_set1_epi32(0x00FF00FF);

    assert(source1 != NULL && source2 != NULL && dest != NULL);
    assert(size % STRIDE == 0);

    const __m128i* source128_1 = reinterpret_cast<const __m128i*>(source1);
    const __m128i* source128_2 = reinterpret_cast<const __m128i*>(source2);
    __m128i*       dest128 = reinterpret_cast<__m128i*>(dest);  

    __m128i d, s, a, rb, ag, t;

    for(size_t k = 0, length = size/STRIDE; k < length; ++k)    
    {
        // TODO: put prefetch between calculations?(R.N)
        _mm_prefetch(reinterpret_cast<const s8*>(source128_1+PSD), _MM_HINT_NTA);
        _mm_prefetch(reinterpret_cast<const s8*>(source128_2+PSD), _MM_HINT_NTA);   

        // work on entire cacheline before next prefetch
        for(int n = 0; n < 4; ++n, ++dest128, ++source128_1, ++source128_2)
        {
            // TODO: assembly optimization use PSHUFD on moves before calculations, lower latency than MOVDQA (R.N) http://software.intel.com/en-us/articles/fast-simd-integer-move-for-the-intel-pentiumr-4-processor/

            // TODO: load entire cacheline at the same time? are there enough registers? 32 bit mode (special compile for 64bit?) (R.N)
            s = _mm_load_si128(source128_1);        // AABGGRR
            d = _mm_load_si128(source128_2);        // AABGGRR

            // PRELERP(S, D) = S+D - ((S*D[A]+0x80)>>8)+(S*D[A]+0x80))>>8
            // T = S*D[A]+0x80 => PRELERP(S,D) = S+D - ((T>>8)+T)>>8

            // set alpha to lo16 from dest_
            a = _mm_srli_epi32(d, 24);          // 000000AA 
            rb = _mm_slli_epi32(a, 16);         // 00AA0000
            a = _mm_or_si128(rb, a);            // 00AA00AA

            rb = _mm_and_si128(lomask, s);      // 00BB00RR     
            rb = _mm_mullo_epi16(rb, a);        // BBBBRRRR 
            rb = _mm_add_epi16(rb, round);      // BBBBRRRR
            t = _mm_srli_epi16(rb, 8);          
            t = _mm_add_epi16(t, rb);
            rb = _mm_srli_epi16(t, 8);          // 00BB00RR 

            ag = _mm_srli_epi16(s, 8);          // 00AA00GG     
            ag = _mm_mullo_epi16(ag, a);        // AAAAGGGG     
            ag = _mm_add_epi16(ag, round);
            t = _mm_srli_epi16(ag, 8);
            t = _mm_add_epi16(t, ag);
            ag = _mm_andnot_si128(lomask, t);   // AA00GG00     

            rb = _mm_or_si128(rb, ag);          // AABGGRR      pack

            rb = _mm_sub_epi8(s, rb);           // sub S-[(D[A]*S)/255]
            d = _mm_add_epi8(d, rb);            // add D+[S-(D[A]*S)/255]

            _mm_stream_si128(dest128, d);
        }
    }   
    _mm_mfence();   //ensure last WC buffers get flushed to memory      
}
5 голосов
/ 26 марта 2011

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

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

BYTE r1, r2, rDest;
BYTE g1, g2, gDest;
BYTE b1, b2, bDest;

BYTE av; // Alpha value BYTE
rem = 255 - av; // Remaining fraction

rDest = (r1*rem + r2*av) / 255;
gDest = (g1*rem + g2*av) / 255;
bDest = (b1*rem + b2*av) / 255;

Если вы хотите стать действительно умным, вы можете заменить деление на умножение с последующим сдвигом вправо.

Редактировать: Вот версия, использующая сдвиг вправо. Добавление константы может уменьшить любые ошибки усечения, но я оставлю это как упражнение для читателя. 

BYTE r1, r2, rDest;
BYTE g1, g2, gDest;
BYTE b1, b2, bDest;

BYTE av; // Alpha value BYTE
int aMult = 0x10000 * av / 255;
rem = 0x10000 - aMult; // Remaining fraction

rDest = (r1*rem + r2*aMult) >> 16;
gDest = (g1*rem + g2*aMult) >> 16;
bDest = (b1*rem + b2*aMult) >> 16;
1 голос
/ 26 марта 2011

Смешивание цветов вычислительно тривиально. Я был бы удивлен, если бы это принесло значительную выгоду, но, как всегда, вы должны сначала доказать, что этот расчет является узким местом в производительности в первую очередь. И я полагаю, что лучшим решением будет использование аппаратного ускоренного смешивания.

...