I recently revamped my graphics-drawingcombinators module to have a handsome denotational semantics. I may write a post going into full detail later, but the executive summary is that Image a = R2 → (Color, a). Due to TCM, I get semantics for Image’s Functor instance from this, and if Color is a monoid I get the semantics for the Applicative and Monoid instances as well. OpenGL combines colors by alpha blending, so I happily defined my monoid instance as alpha blending:
mempty = Color 0 0 0 0 mappend c@(Color _ _ _ a) c' = a*c + (1-a)*c'
It doesn’t take a genius to see that this violates two of the three monoid laws (the only one it satisfies is left unit: mempty `mappend` x = x). This is embarrassing. My new rigorous denotational semantics has a pretty awesome flaw.
To make this right, let’s redefine Color not as something which is drawn, but as a transformation on alpha-free colors. I do this because functions make great monoids: composition is always associative and identity is always a unit. But it’s not just any function, it’s an alpha blending function. So we say that f is a “Color” if there exists constants a and x such that f(c) = a x + (1-a) c, which I will write as f = [a; x]. Here a is a scalar and x is another alpha-free color like c. We would really like it if the composition of two Colors were also a Color. Let’s try:
f(g(c)) = [fa;fx]([ga;gx](c)) = fa fx + (1 - fa) ([ga;gx](c)) = fa fx + (1 - fa) (ga gx + (1 - ga) c) = fa fx + (1 - fa) ga gx + (1 - fa) (1 - ga) c = fa fx + (1 - fa) ga gx + (1 - fa - ga + fa ga) c = (fa fx + (1 - fa) ga gx) + (1 - (fa + ga - fa ga)) c
It looks like the “alpha” of our composition is (fa + ga – fa ga). Let’s call this a’. Now we have to get the left side of the addition into the form a’ r for some r. Let’s just hack it: multiply and divide1 by a’.
= a' (fa fx + (1 - fa) ga gx) / a' + (1 - a') c
And then we can read off the answer:
[fa;fx] . [ga;gx] = [a' ; (fa fx + (1 - fa) ga gx) / a'] where a' = fa + ga - fa ga
For the identity, we need:
a x + (1 - a) c = c
Which is satisfied for a = 0 with x = anything, so we can use [0,0].
Because we derived this from composition and identity, the laws must hold. The mathematically untrusting may wish to check this.
And there you have it: my new Color monoid which actually satisfies the laws. This is the way to compose alpha-blended colors — it reflects what happens if you draw one after the other, blending as you go. This is the math that pre-blends any segment of that sequence.
I should have known that OpenGL’s colors were transformations all along, since the color of an object that you see can depend on the color you used to clear the screen.
1 But what if (fa + ga – fa ga) = 0? Fortunately, the only place this happens when these variables are between 0 and 1 is fa = ga = 0, which means both f and g are the identity color.