Змішуємо кольору правильно або оптимізуємо alphablend

Змішуємо кольору правильно або оптимізуємо alphablend
Я пишу мультипротокольний (але не мультиплатформенний, на жаль, зараз тільки windows) месенджер, який поки що підтримує тільки протокол TOX. Але мова не про мессенджере, а про його інтерфейсі, а якщо точніше, про основну його функції - AlphaBlend. Так, я вирішив написати свій велосипед GUI. Ну а який сучасний GUI без напівпрозорих елементів і плавних заокруглень? Тому гостро постала необхідність змішувати зображення з урахуванням напівпрозорості, тобто альфа-змішування або alpha blending. На щастя, в windows GDI така функція є - AlphaBlend. Працює як треба, робить те що потрібно. Але я той ще будівельник велосипедів, і мені стало цікаво, чи зможу я написати таку ж функцію, але більш швидку. Результат моїх праць під катом.

Теорія альфа змішування

Швидше за все ви знаєте цю теорію, тому я не буду розписувати її докладно, зазначу тільки основні моменти.

Отже, у нас є 2 пікселя - вихідний і піксель призначення. Їх потрібно змішати і отримати новий піксель призначення. Кожен піксель представлений 4-ма байтами A, R, G, B, де A - значення (не) прозорості пікселя (0 - повністю прозорий, 255 - повністю непрозорий), RGB - колірні компоненти. Класична формула змішування така:

Важливий момент! Одиниця - це у формулі. У житті у нас за одиницю виступає значення 255. Тобто щоб застосовувати формулу, ми повинні попередньо розділити значення кожного байта на 255. Як не важко помітити, 255 і 256 - досить близькі значення, а розподіл на 256 - це всього лише зрушення вправо на 8 біт. Тому часто зустрічається таке спрощення: замість операції

Це працює непогано (а головне, значно швидше чесного поділу), але, в разі альфа змішування результат не цілком коректний, а саме, результуючий піксель виходить трохи темніше. Далі, я покажу, як можна виконати обчислення точно і без втрати в швидкості роботи.

Інший важливий момент! Подивіться на формулу. У другій частині є SRC_COLOR * SRC_ALPHA. Таке множення 3D акселератори виконують мільйонами і навіть мільярдами, не моргнувши оком. Але ми то намагаємося вирішити задачу, використовуючи центральний процесор, і зайве множення (точніше 4 зайвих множення) на кожен піксель - це не дуже добре. Чому зайве? Та тому що це множення можна зробити заздалегідь, перетворивши вихідну картинку. У таких зображень навіть назва є: premultiplied. Я не знаю терміна в російській мові, але перевівши дослівно отримаємо «предумноженние». І точно, GDI функція AlphaBlend вимагає в якості вихідного зображення строго premultiplied. Це розумно.

Що ж, з теорією закінчили. На практиці будемо працювати з 32-бітовим кольором. Один піксель представлений 32-бітовим числом, в якому 4 байта, починаючи з молодшого, означають: B (lue), G (reen), R (ed), A (lpha). Поїхали.

перша реалізація

Моя перша реалізація була такою:

Згоден, виглядає не дуже. 4 речових (точніше 5) множення і 4 округлення на кожен піксель - це занадто. Не дивно, що за швидкістю цей монстр програвав AlphaBlend'у приблизно в 7 разів.

Спробуємо поліпшити. Позбудемося речових умножений.

Тут функції BLUEx256, GREENx256, і т.п. повертають відповідну компоненту, зрушену вліво на 8 біт, тобто помножену на 256.

Ця функція примітна тим, що в ній є компенсація заміни поділу на 255 зрушенням на 8 біт вправо. Помітили? Якщо немає, потерпіть, нижче я опишу цей момент докладніше.

За швидкістю ця реалізація поступається AlphaBlend'у приблизно в 3 рази. Вже краще, але все ще дуже далеко від ідеалу.

несподіваний результат

Як можна поліпшити попередню функцію? Здається, ми зробили все що можна. Однак, у мене вийшло покращити цю функцію способом, який став для мене сюрпризом. Я і спробував його просто щоб переконатися, що нічого не вийде. Однак, вийшло.
Що якщо винести операцію множення байта на байт в таблицю. Вийде не дуже багато - всього 65536 байт. Копійки.

Заводимо таку табличку:

Отже. Тут більше нічого оптимізувати. Мені не приходить в голову більше нічого. Але AlphaBlend все ще швидше, рази в два. Як вони цього добилися? Здається, пора на пенсію?

Про компенсацію заміни поділу на 255 зрушенням

Є багато способів швидкого ділення на 255. Мені зустрічався такий:

Це не погано. Це швидше чесного поділу на 255. Але це все ще занадто громіздко. Я довго думав, як швидко розділити на 255 і не втратити ні в якості ні в швидкості. Як компенсувати деградацію кольору при використанні зсуву?

Припустимо, у нас є колірна компонента, що дорівнює 0xff (255) і у нас є інша компонента, теж рівна 0xff (255). Перемножая їх, ми отримуємо:

0xff * 0xff = 0xfe01. Зсунувши на 8 біт вправо, отримаємо 0xfe - яскравість компоненти зменшена. Погано.
А що, якщо ми одну з компонент збільшимо на 1 перед множенням?
0xff * 0x100 = 0xff00. Хм, здається це воно. Перевіримо випадок, коли одна з компонент дорівнює 0:
0xff * 1 = 0x00ff. зрушуємо вправо на 8 біт, отримуємо 0. Вуаля! При інших значеннях компонент результат також буде вірним.
Тепер легко знайти місце компенсації в другій функції: uint not_a = 256 - ALPHA (src);
Чи не 255 - A, а 256 - A, тобто +1 до компоненті перед множенням. Для табличного методу множення компенсація не потрібно, тому що в таблиці всі значення і так пораховані як потрібно.

Важка артилерія - інструкції SSSE3

Пора задуматися про оптимізацію з використанням simd. Кажуть, компілятор Intel вміє це робити і без участі людини. Можливо. Але гложат мене сумніви, що Intel впорається з AlphaBlend'ом. Ну максимум - зрівняється з нею. Але мені то потрібно зробити швидше. Відкриваємо довідник і вперед.

Перше питання, яким слід задатися - під які інструкції робити оптимізації? У мене є підозра, що AlphaBlend оптимізована під MMX, інакше я не можу пояснити її переваги над чистою x86 реалізацією. MMX - це добре, але це минуле століття. Зараз важко знайти комп'ютер, де б не було підтримки SSE4. А під SSE взагалі можна оптимізувати, навіть не обтяжуючи себе перевіркою на наявність підтримки цих інструкцій - ймовірність, що твоя програма буде запущена на чимось нижче Pentium 3 близька до нуля. Я, звичайно ж, веду мову про desktop додатках. Екзотика поза рамками цієї статті.

Я зупинив свій вибір на SSSE3. Цей набір інструкцій досить поширений, щоб задурити оптимізацією саме під нього, з огляду на наявність в ньому дуже дуже зручних інструкцій.

Сама ж корисна інструкція, яка і ляже в основу всіх оптимізацій - це pshufb (інтрінсік _mm_shuffle_epi8). Саме заради неї і обраний SSSE3. У чому ж її сила? У тому, що ця інструкція дозволяє розкидати байти вихідного 16-байтового регістра в будь-якому довільному порядку або взагалі викинути ці байти за непотрібністю. Тобто я можу за допомогою цієї інструкції в один рух готувати все необхідне для потрібних розрахунків. Інша важлива інструкція - pmulhuw (інтрінсік _mm_mulhi_epu16) - це 8 умножений і 8 зрушень вправо на 16 біт. Неначе спеціально для операції альфа змішування. Тобто однією цією командою я фактично обчислюю відразу 2 пікселя.

Ну що ж, поїхали:

Простирадло asm коду

Як видно, simd реалізація змішує відразу 4 вихідних пікселя з 4-ма пікселями призначення. Ну на то вона і simd. За кадром рамками цієї статті залишу опис вирішення проблеми, коли потрібно змішати не кратна 4-м кількість пікселів. Особисто я застосовую для цього «однопіксельні» виклики c ++ реалізації.

Код в статті наведено лише для ознайомлення з самим принципом ssse3 оптимізації. Я не став тут приводити значення використовуваних констант. Якщо ви захочете використовувати оптимізований AlphaBlend в своєму проекті, вам доведеться добути робочий код безпосередньо з вихідних текстів Isotoxin'а (так називається моя розробка).

Репозиторій Isotoxin'а на гітхабе.
Безпосередньо файл, в якому знаходиться потрібна функція тут.

Прошу вибачення, що не підготував робочі приклади і не виніс все в окрему бібліотеку. Якщо вам дійсно потрібна ця функція, і ви відчуваєте труднощі в тому, щоб самостійно дістати її з моїх початкових кодів, напишіть мені приватне повідомлення і я докладно розповім вам, як це зробити.

Схожі статті