这种可在并行颜色组件上工作的颜色混合技巧如何工作?

问题描述

我看到了这段Java代码，可以非常高效地在两种RGB888颜色之间完美地完成50％的混合:

I saw this Java code that does a perfect 50% blend between two RGB888 colors extremely efficiently:

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

这显然等效于分别提取和平均通道.像这样:

That's apparently equivalent to extracting and averaging the channels individually. Something like this:

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

但是第一种方法效率更高.我的问题是:这种魔术如何起作用?我还能做什么?还有更多与此类似的技巧吗?

But the first way is much more efficient. My questions are: How does this magic work? What else can I do with it? And are there more tricks similar to this?

推荐答案

(a ^ b) & 0x00010101是如果没有从右边进位的话，通道的最低有效位应该在a + b中.

(a ^ b) & 0x00010101 is what the least significant bits of the channels would have been in a + b if no carry had come from the right.

从总和中减去它可以确保移入下一个通道的最高有效位的位只是该通道的进位，不受该通道的影响.当然，这也意味着该频道不再受下一频道的进位影响.

Subtracting it from the sum guarantees that the bit that is shifted into the most significant bit of the next channel is just the carry from that channel, untainted by this channel. Of course that also means that this channel is no longer effected by the carry from the next channel.

查看此问题的另一种方法(不是执行此操作的方法，而是可以帮助您理解它的一种方法)是有效地更改输入，以使所有通道的输入和相等.然后，进位会很好地进入最低有效位(为零，因为是偶数)，而不会打扰任何东西.当然，它实际上所做的是相反的操作，首先它只是对它们求和，然后才确保所有通道的和是均匀的.但是顺序并不重要.

An other way to look this, not the way it does it but a way that may help you understand it, is that effectively the inputs are changed so that their sum is even for all channels. The carries then go nicely into the least significant bits (which are zero, because even), without disturbing anything. Of course what it actually does is sort of the other way around, first it just sums them, and only then does it ensure that the sums are even for all channels. But the order doesn't matter.

更具体地说，有4种情况(在应用来自下一个通道的进位之前):

More concretely, there are 4 cases (before the carry from the next channel is applied):

1. 一个频道的lsb为0，下一个频道没有进位.
2. 一个频道的lsb为0，下一个频道有一个进位.
3. 一个频道的lsb为1，下一个频道没有进位.
4. 一个频道的lsb为1，下一个频道有一个 进位.

1. the lsb of a channel is 0 and there is no carry from the next channel.
2. the lsb of a channel is 0 and there is a carry from the next channel.
3. the lsb of a channel is 1 and there is no carry from the next channel.
4. the lsb of a channel is 1 and there is a carry from the next channel.

前两种情况是微不足道的.移位会将进位位放回其所属的通道中，甚至是0还是1都不重要.

The first two cases are trivial. The shift puts the carried bit back in channel it belongs to, it doesn't even matter whether it was 0 or 1.

案例3更有趣.如果lsb为1，则表示移位会将该位移位到下一个通道的最高有效位.那很糟.该位必须以某种方式取消设置-但是您不能仅仅将其掩盖掉，因为可能是在情况4中.

Case 3 is more interesting. If the lsb is 1, that means the shift would shift that bit into the most significant bit of the next channel. That's bad. That bit has to be unset somehow - but you can't just mask it away because maybe you're in case 4.

案例4是最有趣的.如果lsb为1，并且该位中有一个进位，则将其翻转为0，并传播该进位.不能通过掩蔽来撤消，但是可以通过逆转该过程来完成，即从lsb中减去1(将其恢复为1，并消除传播的进位造成的任何损害).

Case 4 is the most interesting. If the lsb is 1 and there is a carry into that bit, it rolls over to a 0 and the carry is propagated. That can't be undone by masking, but it can be done by reversing the process, ie subtracting 1 from the lsb (which puts it back to 1 and undoes any damage done by the propagated carry).

如您所见，在情况3和情况4中，治愈都是从lsb中减去1，而在这些情况下，lsb确实希望为1(尽管可能不再如此， (由于来自下一个通道的进位)，在情况1和情况2中，您都不需要做任何事情(换句话说，减去0).这恰好等于减去如果右边没有进位，则lsb在a + b中应该是什么".

As you can see, in both case 3 and case 4, the cure is subtracting 1 from the lsb, and those are also the cases in which the lsb really wanted to be 1 (though maybe it isn't any more, due to a carry from the next channel), and in both case 1 and 2, you don't have to anything (in other words, subtract 0). That exactly corresponds to subtracting "what the lsb would have been in a + b if no carry had come from the right".

此外，蓝色通道只能进入情况1或3(没有下一个通道可以承载)，并且移位只会丢弃该位，而不是将其放入下一个通道(因为没有).因此，您也可以编写(请注意，掩码丢失了最低有效位1)

Also, the blue channel can only fall into cases 1 or 3 (there is no next channel which could carry), and the shift would just discard that bit instead of putting it in the next channel (because there is none). So alternatively, you may write (note the mask has lost the least significant 1)

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

但是，实际上并没有什么区别.

Doesn't really make any difference, though.

要使其适用于ARGB8888，您可以切换到旧的"SWAR平均":

To make it work for ARGB8888, you can switch to the good old "SWAR average":

// 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)计算不带进位的总和，然后将进位分别加进去.基本情况是操作数之一为零时.

Which is a variation on a recursive way to define addition: x + y = (x ^ y) + ((x & y) << 1) which computes the sum without carries, then adds the carries in separately. The base case is when one of the operands is zero.

两个半部均有效地右移1，这样就不会丢失最高有效位的进位.掩码确保位不会移到右侧的通道，同时确保进位不会从其通道外传播.

Both halves are effectively shifted right by 1, in such a way that the carry out of the most significant bit is never lost. The mask ensures that bits don't move to a channel to the right, and simultaneously ensures that a carry won't propagate out of its channel.

这篇关于这种可在并行颜色组件上工作的颜色混合技巧如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！