On May 16, Keith Packard wrote:
> I've got an alpha computation problem. I fear for the algorithm.
Keith,
I might have an idea here.
In the discussion which follows, terms such as a, ab, abcd, etc. refer
to alpha values when standing alone and refer to polygon regions when
inside an area calculations, (such as "area(ab)). Context should make
this clear.
Heres a picture in which we are interested in calculating an alpha
value for the sub-pixel trapezoid `d':
lr
|\
+--|-\-------+
| a| b\ |
=======|===\========== top
| c| d \ |
=======|=====\======== bot
| | \ |
+--|-------\-+
The current specification involves four alpha values that are directly
computed from area calculations:
a = AreaAlpha(area(a))
ab = AreaAlpha(area(ab))
ac = AreaAlpha(area(ac))
abcd = AreaAlpha(area(abcd))
I'll add the following constraints to these definitions which will be
useful later. There's nothing new here --- I believe these have always
held, but I'll state them for completeness:
area1 >= area2 ---> AreaAlpha(area1) >= AreaAlpha(area2)
area(ab) >= area(a)
area(ac) >= area(a)
The remaining alpha values are then defined in terms of the alpha
values from above:
b = ab - a
c = ac - a
cd = abcd - ab
d = cd - c = abcd - ab - (ac - a)
OK, that was background which should be familiar. Now, the problem
Keith is currently encountering can be resolved by adding a further
constraint that no final-result alpha value, (a, b, c, or d), can be
negative:
a >= 0
ab - a >= 0
ac - a >= 0
abcd - ab - (ac - a) >= 0
These first three non-negativity constraints are satisfied by the
definitions above and are not causing any problems. It's that fourth
one that is currently tripping us up. Let's look closer:
abcd - ab - (ac - a) >= 0
abcd - ab - ac + a >= 0
ab + ac <= abcd + a
The term abcd is fixed. It is either 1 if the right and bottom
trapezoid edges are coincident with pixel edges, or else it is the "a"
term in an identical trapezoid solution higher up in the algorithm.
The `a' term can be arbitrarily small, but is non-negative by
definition, so we can ignore it here and still satisfy the constraint:
ab + ac <= abcd
So, my proposal is to define ab and ac such that this constraint is
always met. That is:
ab = MIN( AlphaArea(area(ab)), abcd - AlphaArea(area(ac))
ac = MIN( AlphaArea(area(ac)), abcd - AlphaArea(area(ab))
which gives us our final equation for the alpha of d:
d = abcd - ab - (ac - a)
d = abcd - MIN( AlphaArea(area(ab)), abcd - AlphaArea(area(ac)))
- MIN( AlphaArea(area(ac)), abcd - AlphaArea(area(ab)))
+ a
which fortunately is not too much more complex to compute.
-Carl
_______________________________________________
Render mailing list
[EMAIL PROTECTED]
http://XFree86.Org/mailman/listinfo/render
