Around 15 o'clock on Dec 9, Carl Worth wrote:
> Here's another small wrinkle in the trapezoid algorithm:
I was chatting with Lyle Ramshaw on Thursday and he suggested that we
reappraise our alpha computation technique. Switching from area
computation to point sampling would eliminate the difficulties we're having
with negative alphas and weird interactions of multiple edges within the
same pixel.
This would also regularize the algorithm for depth = 1 vs depth > 1.
However, it would reduce the accuracy of the alpha computations, but we
already know our current 'box' filter is just an approximation in any case.
The basic idea is to place points within the pixel and count how many are
"inside" the trapezoid. I think this works precisely when the number of
points within the pixel equals the number of non-zero alpha values so that
no rounding is required. A simple case to consider is depth 1 where
precisely one trapezoid covering a pixel must have alpha 1 while all other
trapezoids have alpha 0; if there is more than one point within the pixel,
then which trapezoid is assigned alpha 1 is ambiguous.
Now that we know how many points are within the pixel, we need to
distribute them evenly to approximate area coverage as closely as possible.
For alpha depth d, the number of non-zero alpha values is
d
2 - 1
When d == 2n, we can array our points in a nearly square grid by noticing
that:
2n n n
2 - 1 = (2 + 1) * (2 - 1)
For other depths (which, except for depth 1, don't occur in practice), we
can lay the points in a line across the pixel. Here's a table:
depth width height points
-------------------------------
1 1 1 1
2 3 1 3
3 7 1 7
4 5 3 15
5 31 1 31
6 9 7 63
7 127 1 127
8 17 15 255
9 511 1 511
10 33 31 1023
11 2047 1 2047
12 65 63 4095
13 8191 1 8191
14 129 127 16383
15 32767 1 32767
16 257 255 65535
It seems like it will be easy enough to construct code to step down the
pixel counting points covered on each scanline; a more interesting problem
is how to construct a purely analytic algorithm which computes the number
of covered points without iteration. The iterative algorithm suffers from
computational cost that scales as the depth of the alpha channel, which is
undesireable.
Keith Packard XFree86 Core Team HP Cambridge Research Lab
_______________________________________________
Render mailing list
[EMAIL PROTECTED]
http://XFree86.Org/mailman/listinfo/render
