Around 10 o'clock on May 16, Keith Packard wrote:
> I think this particular problem is occuring because we're losing half a
> bit of alpha in the conversion from area to alpha. Remember that the
> area to alpha computation is currently specified by:
No, that wasn't the problem. The basic problem is that alphas are only
an approximation of area and the result of arithmatic operations on
approximations are worse approximations. In particular:
+-\-----|---+
|A \ B | |
| \ | |
=====\==|====
| C \D| |
========|====
| \| |
+-------\---+
Now, let:
Ap = area(A) * 255 ("precise alpha of a")
ABp = area(AB) * 255 ("precise alpha of AB")
ACp = area(AC) * 255 ("precise alpha of AC")
ABCDp = area(ABCD)* 255 ("precise alpha of ABCD")
Given these precise relationships, it should be obvious that:
ABCDp >= ABp + ACp - Ap
Now we need to conver these rational values to integers. Any conversion
must obey the following relationship:
if area(x) < area(y) then alpha(x) <= alpha(y)
This means we must use a consistent conversion rule to compute alphas:
Xa = approx (Xp) ("approximate alpha of X")
Any approximation will have an error (e):
e = abs (Xp - Xa)
Rounding provides the smallest error bounds:
Xa = floor (Xp + 1/2)
abs (Xp - Xa) <= 1/2
Any other conversion will have no smaller error bounds, so let's work with
1/2.
Now consider how Da is computed:
Da = CDa - Ca
= (ABCDa - ABa) - (ACa - Aa)
= round(ABCDp) + round(Ap) - round(ABp) - round(ACp)
We must use our approximate integer alpha values here to ensure that
any alpha error is correctly offset (ref earlier article on this topic).
If D is quite small, it's easy to see that errors in ABCDa, ABa, ACa and Aa
can accumulate. Here's an example:
ABCDp = 12.4
Ap = 2.4
ABp = 7.6
ACp = 6.6
Dp = 12.4 + 2.4 - 7.6 - 6.6 = 0.6
Da = 12 + 2 - 8 - 7 = -1
It's easy to see that the difference between Dp and Da is computed with:
De = Dp - Da = (ABCDp - ABCDa) + (Ap - Aa) + (ABa - ABp) + (ACa - ACp)
We've got four error values, each of which can be as much as 1/2, so the
maximum error is 2. If Dp < De, then the resulting alpha computation
will be less than zero.
So, now the obvious question is what to do about the problem.
I don't believe this algorithm is "fixable" in any reasonable way, it's a
fundemental limitation in computing similar areas in different ways, which
is the central idea in this algorithm.
I'm not at all adverse to developing a completely different algorithm, I
have one which I think is easily demonstrated to satisfy the constraints
already enumerated -- split the pixel up into equal sized boxes and count
the number of box (centers, corners, whatever) covered by the trapezoid.
For even depths (2n), split the pixels into ((1<<n)-1) x ((1<<n)+1)
pieces, for odd depths (2n+1), split the pixels into vertical strips (the
only interesting odd depth is 1, many others are prime). This has two
problems -- I think it's harder than the current algorithm, and it suffers
from dropouts. If anyone else has a replacement algorithm, please make it
known.
The other obvious solution is to live with the limitations of the current
algorithm, truncating the negative alpha values to zero. Because of the
way the algorithm works, an area with negative alpha will be balanced by
the remaining portion of the pixel having total alpha greater than one, so
the alpha of the pixel will end up overestimated. In the worst case, it's
probably possible to compute a tesselation that covers only half of the
pixel and yet contributes a full pixel-worth of alpha values. This
will cause visible anomalies along the edge of polygons. Fortunately, the
most important case, that of a complex tesselation with the affected pixel
in the center works OK -- the alpha will saturate at one leaving the pixel
opaque.
As always, suggestions and comments are welcome.
Keith Packard XFree86 Core Team HP Cambridge Research Lab
_______________________________________________
Render mailing list
[EMAIL PROTECTED]
http://XFree86.Org/mailman/listinfo/render
