I've found an interesting little ambiguity in the current trapezoid
algorithm[*].
Consider the alpha computation for the following pixel intersected by
the trapezoid top and bottom lines. The right edge of the trapezoid
does not intersect this pixel, (though its containing line does).
+--------------+
| |
| |
| |
top --+--------------+o---
| | \
bottom --+--------------+--o-
| | right
+--------------+
The current implementation in the X server computes the alpha for this
pixel as:
alpha = alpha_above (bottom) - alpha_above (top)
Meanwhile, the reference nickle implementation considers the infinite
extension of the right edge:
\
+-----------\--+
| \A|
| \|
| \
top --+--------------+o---
| | \
bottom --+--------------+--o-
| | \right
+--------------+ \
and computes:
alpha = alpha_above_left (bottom, right) - alpha_above_left (top, right)
In other words, the small triangular area A is subtracted from both of
the area calculations used to compute the two alpha terms. Since the
alpha_from_area function involves rounding, the two subtractions don't
exactly cancel and the final alpha value computed is different. (I've
got a case in hand with 8-bit alpha values where the nickle approach
gives a result 1-bit smaller than the implementation in the server).
In all conversations during the development of the algorithm, we used
the infinite extensions of the left and right edges, but I'm inclined
to think now that the algorithm should actually compute things
according to the first diagram above.
My reasoning is that the algorithm is designed to provide a "sum to 1"
guarantee for trapezoids tessellating a pixel. But the "sum to 1"
property only holds if the tessellation actually involves all common
edges used in the calculations of separate trapezoids.
For example, in the case above, the area of the pixel above the top
line might later be filled in by a single trapezoid, or by two
separate trapezoids split by the extension of the current right
edge. We don't really know which is going to occur, but we won't get
the "sum to 1" result unless we guess correctly.
My argument is that the extents of the left and right edges provide
exactly the clue we need to determine how the remainder of the
tessellation will likely occur. For example, in the trapezoid I found
that caused this problem, (which came from an Xr tessellation of a
stroked spline), the right edge appears as shown, bounded by top and
bottom; while the left edge extends up 1 pixel and down about 70
pixels. This is a nice hint that the line containing the right edge
will not be used in trapezoids above and below the current one, while
the left edge probably will.
Of course, using the infinite extension of the edges does lead to a
simpler specification. Using just the edges forces the specification
to state what happens when an edge terminates within the trapezoid, or
beyond the trapezoid but within the pixel.
Comments and suggestions are welcome as always.
-Carl
[*] Pay no mind to the fact that said algorithm does not yet have
a formal written specification.
--
Carl Worth
USC Information Sciences Institute [EMAIL PROTECTED]
_______________________________________________
Render mailing list
[EMAIL PROTECTED]
http://XFree86.Org/mailman/listinfo/render
