Repeating alpha over/under operation multiple times

Question

I have two RGBA colors in linear [0..1] space, src and dst and I want to alpha blender src over/under dst n times. Of course, I could call the respective operation n times using the result from the previous one (which is what I am currently doing), but I want to optimize it into a single operation. I think just calculating the correct alpha on src should be sufficient, but I may be wrong. Here's what I currently use:

public static final Color alphaOver(Color dst, Color src) {
    float src1A = 1 - src.a;
    float outA = src.a + dst.a * src1A;

    if (outA == 0)
        return Color.TRANSPARENT;
    return new Color(
            outA,
            (src.r * src.a + dst.r * dst.a * src1A) / outA,
            (src.g * src.a + dst.g * dst.a * src1A) / outA,
            (src.b * src.a + dst.b * dst.a * src1A) / outA);
}

public static final Color alphaUnder(Color dst, Color src) {
    return alphaOver(src, dst);
}

public static final Color alphaOver(Color dst, Color src, int times) {
    Color ret = dst;
    for (int i = 0; i < times; i++)
        ret = alphaOver(ret, src);
    return ret;
}

public static final Color alphaUnder(Color dst, Color src, int times) {
    Color ret = dst;
    for (int i = 0; i < times; i++)
        ret = alphaUnder(ret, src);
    return ret;
}

How can I optimize the last two functions?

user1118321 · Accepted Answer · 2018-09-08T05:28:58.053

1

So taking source over as an example, the math works out to:

dst = a * src + (1 - a) * dst

Taking Nathan Reed's suggestion of replacing (1 - a) with b, that gives us:

dst = a * src + b * dst

If we perform the next iteration, it becomes:

dst = a * src + ab * src + b^2 * dst

Doing it again, we get:

dst = a * src + ab * src + ab^2 * src + b^3 * dst

And then:

dst = a * src + ab * src + ab^2 * src + ab^3 * src + b^4 * dst

The pattern appears to be:

int exponent;
for (exponent = 0; exponent < numIterations; exponent++)
{
    newDst += a * pow(b, exponent) * src;
}
newDst += pow(b, exponent) * dst;

edited Sep 08 '18 at 05:28

answered Sep 07 '18 at 20:28

user1118321

3,401
11
14

Are you sure to plug the result of the first alpha over into src of the next one? As I understand it, I would put it into dst instead. This lines up with some quick tests of the final equation with black src, white dst and an a>0. Overlaying black over white should darken the color but + dst prevents this. – piegames Sep 07 '18 at 20:43
I agree that substituting into dst is the correct thing to do here. If you imagine doing n separate blends on top of each other, the src would be the same for all, and result of each blend would be the following blend's dst. I think you should be able to simplify the result to a single blend using alpha of 1 - (1 - a)^n though. (Try defining a new variable b = 1 - a, and repeating the derivation you used for the first part of the answer.) – Nathan Reed Sep 08 '18 at 02:37
Great idea! I've updated it with your suggestion. Let me know how it works. – user1118321 Sep 08 '18 at 05:30
How about dst := (1 - b)*src + b*dst, and then rewrite that as src + b*(dst - src). Then it works out similarly to your original derivation. :) – Nathan Reed Sep 08 '18 at 05:48
Ah, I see what you mean. I'll give that a try in the morning. I'm getting sleepy now and would probably screw it up. – user1118321 Sep 08 '18 at 06:18
Whoa, that looks really good. Am I allowed to bracket out src in that sum, to avoid multiplicating with src n times and reduce it to once at the end? Because if so, this becomes a geometric series which can be optimized even further. – piegames Sep 08 '18 at 08:09
Absolutely! If it works, go for it! – user1118321 Sep 08 '18 at 14:48

Repeating alpha over/under operation multiple times

1 Answers1