Ok, I spent the afternoon drawing figures on a whiteboard and getting help
from the PSU CS department here in Portland. I have the kernel of a
solution, which I'll explore here to see if it solves the general case.
This solution requires a prescription of portions of the algorithm used to
compute coverage; I'm not entirely happy with that, but I haven't found a
completely descriptive definition which satisfies the constraints and
which is computable with reasonable precision requirements.
I'll start with one tesselation of the pixel and move on from there:
n u v o
| / \ |
l---+------------/----\------------+
| / \ |
| a / b \ c |
| / \ |
r ===========/============\===========
| / \ |
| d / e \ f |
| / \ |
s =======/====================\====|
| / \ |
|g / h \ i|
| / \ |
m---+/----------------------------\+
This is a picture of a single pixel; we're interested in computing the
area of the pixel covered by each of the trapezoids in the figure; I
believe that is sufficient to compute any tesselation. The fact that 'u'
and 'v' intersect the pixel along the top and bottom shouldn't have any
effect on the discussion below -- they could intersect along the sides with
the same results.
Some functions:
area(polygon) range: [0 ... 1] - some approximation of the
area of the pixel covered
by the named polygon
area(line) range: [0 ... 1] - some approximation of the
area of the pixel to the
left of the specified line
alpha(polygon) range: [0...2**depth-1] - some approximation of the
fraction of the total
pixel alpha area covered
by the specified polygon
alpha(line) range: [0...2**depth-1] - some approximation of the
fraction of the total
pixel alpha area to the
left of the specified line
round(x) = floor (x + 1/2)
Now specify the alpha function:
alpha(u) = round ((2**depth-1) * area(u))
alpha(v) = round ((2**depth-1) * area(v))
alpha(o) = 2**depth-1
/ area(a) \
alpha(a) = round | alpha(u) * ------- |
\ area(u) /
/ area(ab) \
alpha(ab) = round | alpha (v) * -------- |
\ area(v) /
alpha(b) = alpha(ab) - alpha (a)
/ area(abc) \
alpha(abc) = round | alpha (o) * --------- |
\ area(o) /
alpha(c) = alpha(abc) - alpha(ab)
/ area(ad) \
alpha(ad) = round | alpha (u) * -------- |
\ area(u) /
alpha (d) = alpha(ad) - alpha (a)
/ area(abde) \
alpha (abde) = round | alpha (v) * ---------- |
\ area(v) /
alpha (de) = alpha (abde) - alpha (ab)
alpha (e) = alpha (de) - alpha (d)
/ area (abcdef) \
alpha (abcdef) = round | alpha (o) * ------------- |
\ area (o) /
alpha (def) = alpha (abcdef) - alpha (abc)
alpha (f) = alpha (def) - alpha (de)
/ area (adg) \
alpha (adg) = round | alpha (u) * ---------- | = alpha(u)
\ area(u) /
alpha (g) = alpha (adg) - alpha (ad)
/ area(abdegh) \
alpha (abdegh) = round | alpha (v) * ------------ | = alpha (v)
\ area(v) /
alpha (gh) = alpha (abdegh) - alpha (abde)
alpha (h) = alpha (gh) - alpha (g)
/ area (abcdefghi) \
alpha (abcdefghi) = round | alpha (o) * ---------------- | = alpha(o)
\ area (o) /
alpha (ghi) = alpha (abcdefghi) - alpha (abcdef)
alpha (i) = alpha (ghi) - alpha (gh)
As you can see, the alpha function for each polygon is computed by
calculating the alpha function for the area including the polygon and
areas above and to the left and then subtracting the alpha values
for the areas above and to the left. Careful examination shows that
each polygon is computed knowing only the values of the edges specified
for the polygon, not the edges for the other polygons in the figure.
What is also clear is that the actual values returned by the area function
aren't particularily important -- it need only return the same value each
time it is given the same polygon.
Finally, it's pretty easy to add up alpha(a)...alpha(i) to see that they
equal alpha(o) (the alpha value for the whole pixel).
Let's see if this algorithm extends to a different tesselation:
n
| u v
l---+-------\--------/-------------+
| \ / |
| a' \ b' / c' |
| \ / |
r ===================================
| / \ |
| d / e \ f |
| / \ |
s =======/====================\====|
| / \ |
|g / h \ i|
| / \ |
m---+/----------------------------\+
/ \
w x
Now note that the areas of a', b' and c' are independent of w and x.
Using the same definition of the areas as above, let's see if the pixel
alpha works out to unity again. I think all I need to show
is that:
alpha(a') + alpha (b') + alpha(c') = alpha(a) + alpha(b) + alpha(c)
But, by the definition of alpha above:
alpha(a') + alpha(b') + alpha(c') = alpha (a'b'c')
and, because alpha(a'b'c') is independent of u and v,
alpha(a'b'c') = alpha (abc)
Hence, the pixel is again covered perfectly.
Here's two more tesselations which I believe demonstrate that arbitrary
tesselations will work:
case V:
n u v o
| / \ |
l---+------------/----\------------+
| / \ |
| / b \ |
| / \ |
r | /============\ |
| / \ |
| A / e \ C |
| / \ |
s /====================\ |
| / \ |
| / h \ |
| / \ |
m---+/----------------------------\+
and
case H:
n o
| |
l---+------------------------------+
| |
| B |
| |
r ====================================
| / \ |
| d u e v f |
| / \ |
s =================================|
| |
| H |
| |
m---+------------------------------+
For case V:
alpha(a) + alpha (d) + alpha (g)
=
alpha(adg) = alpha(u)
=
alpha(A)
and
alpha(c) + alpha (f) + alpha(i)
= alpha (abc) - alpha (ab) +
alpha (def) - alpha (de) +
alpha (ghi) - alpha (gh)
= alpha(abc) - alpha (ab) +
alpha(abcdef) - alpha (abc) - (alpha(abde) - alpha(ab)) +
alpha(abcdefghi) - alpha (abcdef) -(alpha(abdegh) - alpha(abde))
= alpha (abcdefghi) - alpha(abdegh)
= alpha (o) - alpha (v)
= alpha(C)
For case H:
alpha (a) + alpha (b) + alpha (c)
= alpha (abc)
/ area (abc) \
= round | alpha (o) * ---------- |
\ area (o) /
/ area (B) \
= round | alpha (o) * -------- |
\ area(o) /
= alpha (B)
and
alpha (g) + alpha (h) + alpha (i)
= alpha (ghi)
= alpha (abcdefghi) - alpha (abcdef)
= alpha (o) - alpha (abcdef)
= alpha (o) - alpha (Bdef)
= alpha (H)
I think these two cases demonstrate that the alpha of each region is always
the sum of the alphas of any tesselation of that region; that shows that this
algorithm should work with an arbitrary tesselation.
The remaining piece, then, is to define the area function. Let's start
with the requirements of the area function:
range(area): [0...1]
if A contained in B then area(A) <= area(B)
I believe any function meeting this requirement will work. Because we're
interested in approximating the actual sub-pixel area covered, let's build
a function which approximates the actual sub-pixel area.
First, let's round each region vertex to the nearest point on the Render
sub-pixel grid. This eliminates a lot of bits needed in the computation,
as each of these positions can be held in 17 bits:
n u v o
| / \ |
l---+------------W----X------------+
| / \ |
| a / b \ c |
| / \ |
r ===========Y============Z===========
Note that the area function carefully computes only the sub-pixel area to
the left of a line, this can either be just one of the trapezoid edges,
the right edge of the pixel or a combination of both. For the combination
case, just split the region horizontally at the intersection of the
trapezoid edge and the pixel edge, compute the separate areas and add them
together.
Now all of the areas are just trapezoids. Compute the area by taking the
average of the top and bottom widths and multiply by the height.
For area(a):
w =((W - n) + (Y-n)) / 2
h = r - l
A = w * h
As 'w' and 'h' are both 17 bits [0...65536], this computation requires 33
bits. We can save a bit by just shifting the result after testing for
overflow:
if ((w & h) == 65536)
A = 0x80000000;
else
A = (w * h) >> 1;
This gives us the area with plenty of precision. Now when computing the
function:
round (alpha * area)
use:
((alpha * (area >> depth) + (1 << (30 - depth))) >> (31 - depth))
I suggest that
round (alpha * a / b)
be computed as
round (alpha * (a/b))
This clearly ensures the ordering constraint for sub-region areas. The
alternate:
((alpha * (a >> depth)) / b + (1 << (30 - depth))) >> (31 - depth)
is slightly more accurate; it appears to also obey the constraint, but I'd
have to think harder to convince myself.
Comments on any portion of the above discussion would be very welcome; I'm
hoping we're close to a solution to trapezoids in the Render extension.
Keith Packard XFree86 Core Team Compaq Cambridge Research Lab
_______________________________________________
Render mailing list
[EMAIL PROTECTED]
http://XFree86.Org/mailman/listinfo/render
