Как работает этот трюк смешивания цветов?

Я видел этот Java-код, который очень эффективно смешивает 50% цветов RGB888 на 50%:

public static int blendRGB(int a, int b) {
    return (a + b - ((a ^ b) & 0x00010101)) >> 1;
}

Это, по-видимому, эквивалентно извлечению и усреднению каналов по отдельности. Что-то вроде этого:

public static int blendRGB_(int a, int b) {
    int aR = a >> 16;
    int bR = b >> 16;
    int aG = (a >> 8) & 0xFF;
    int bG = (b >> 8) & 0xFF;
    int aB = a & 0xFF;
    int bB = b & 0xFF;
    int cR = (aR + bR) >> 1;
    int cG = (aG + bG) >> 1;
    int cB = (aB + bB) >> 1;
    return (cR << 16) | (cG << 8) | cB;
}

Но первый способ гораздо эффективнее. Мои вопросы: как работает это волшебство? Что еще я могу с этим сделать? И есть ли еще подобные трюки?

1 ответ

Решение

(a ^ b) & 0x00010101 это то, что младшие биты каналов были бы в a + b если бы не керри пришел справа.

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

Другой способ взглянуть на это, не то, как это делается, а способ, который может помочь вам понять это, заключается в том, что входы эффективно меняются, так что их сумма одинакова для всех каналов. Кэрри затем красиво переходят в младшие биты (которые равны нулю, потому что даже), ничего не мешая. Конечно, на самом деле все происходит наоборот: сначала они просто суммируют их, и только потом это гарантирует, что суммы равны для всех каналов. Но порядок не имеет значения.

Более конкретно, есть 4 случая (до применения переноса со следующего канала):

  1. Значение lsb канала равно 0, и перенос следующего канала отсутствует.
  2. lsb канала равно 0, и имеется переход со следующего канала.
  3. lsb канала равно 1 и перенос следующего канала отсутствует.
  4. lsb канала - 1, и есть переход от следующего канала.

Первые два случая тривиальны. Сдвиг помещает перенесенный бит обратно в канал, которому он принадлежит, даже не имеет значения, был ли он 0 или 1.

Случай 3 более интересен. Если lsb равно 1, это означает, что сдвиг сместит этот бит в самый старший бит следующего канала. Это плохо. Этот бит должен быть как-то не установлен - но вы не можете просто замаскировать его, потому что, возможно, вы в случае 4.

Случай 4 самый интересный. Если lsb равен 1 и в этом бите есть перенос, он сбрасывается до 0 и перенос распространяется. Это не может быть отменено с помощью маскировки, но это может быть сделано путем обращения вспять процесса, то есть вычитания 1 из lsb (который возвращает его обратно в 1 и отменяет любой ущерб, нанесенный распространяемым переносом).

Как вы можете видеть, как в случае 3, так и в случае 4, излечение вычитает 1 из lsb, и это также случаи, когда lsb действительно хотел быть 1 (хотя, может быть, это не так, из-за переходите от следующего канала), и в обоих случаях 1 и 2 вам ничего не нужно (другими словами, вычтите 0). Это точно соответствует вычитанию того, что было бы в lsb a + b если бы не керри пришел справа ".

Кроме того, синий канал может попадать только в случаи 1 или 3 (нет следующего канала, который может нести), и сдвиг просто отбрасывает этот бит вместо того, чтобы поместить его в следующий канал (потому что его нет). Таким образом, в качестве альтернативы, вы можете написать (обратите внимание, что маска потеряла наименее значимое 1)

public static int blendRGB(int a, int b) {
    return (a + b - ((a ^ b) & 0x00010100)) >> 1;
}

Хотя на самом деле не имеет никакого значения.

Чтобы заставить его работать для ARGB8888, вы можете переключиться на старое доброе "среднее значение SWAR":

// channel-by-channel average, no alpha blending
public static int blendARGB(int a, int b) {
    return (a & b) + (((a ^ b) & 0xFEFEFEFE) >>> 1);
}

Какой вариант рекурсивного способа определения сложения: x + y = (x ^ y) + ((x & y) << 1) который вычисляет сумму без переносов, затем добавляет переносы отдельно. Базовый случай - это когда один из операндов равен нулю.

Обе половины эффективно сдвигаются вправо на 1 таким образом, что выполнение наиболее значимого бита никогда не теряется. Маска гарантирует, что биты не перемещаются в канал вправо, и одновременно гарантирует, что перенос не будет распространяться из своего канала.

Другие вопросы по тегам