Around 16 o'clock on May 3, Carl Worth wrote:
> I don't want to belabor things too painfully, but there is one more
> case to note which must be addressed with this latest
> algorithm. Namely, the degenerate when the lines u and v cross within
> one pixel.
> n u v o
> | \ / |
> l---+--------\-----------/---------+
> | \ / |
> | a \ b / c |
> | \ / |
> r ===============\===/================
> | \e/ |
> | d X f |
> | /t\ |
> s ===============/===\=============|
> | / \ |
> |g / h \ i|
> | / \ |
> m---+--------/-----------\---------+
Some of you may recall the discussion on this point last fall; that
revolved around the precise computation of the area of 'e' which requires
192 bit arithmetic. The solution then was to define the "area" of 'e'
in terms of the area to the left of 'v' minus the area to the left of 'u',
essentiall 'e' - 't'. This carries forward to our current problem.
The polygon 'd' is not a trapezoid in this figure, the application can
either draw 'de' or 'dt', but never 'd'. Similarly, it can never draw
'f', only 'ft' or 'fe'. Assuming that the application draws 'e', and
assuming that it intends to fill the pixel exactly, it will then
draw both 'dt' and 'ft'. Hence, we must make:
alpha(dt) + alpha(e) + alpha (ft) = alpha (detf)
Using Carl's simplified alpha functions where the alpha value of any
polygon, 'p', touching the upper left corner is alpha_from_area(area(p))
alpha(dt) = alpha(adt) - alpha (a)
alpha (de) = alpha (abde) - alpha (ab)
| alpha (de) - alpha (dt) where alpha(de) >= alpha(dt)
alpha (e) = |
| 0 otherwise
alpha (detf) = alpha (abcdetf) - alpha (abc)
alpha (ft) = alpha (detf) - alpha (de)
Now check:
alpha (dt) + alpha (e) + alpha (ft)
= alpha(dt) + alpha (de) - alpha(dt) + alpha (ft)
= alpha (de) + alpha (detf) - alpha (de)
= alpha (detf)
To ensure that the pixel can be exactly filled, the application must
ensure that alpha(de) >= alpha(dt). This can be done by adjusting 's' to
be the nearest fixed-point coordinate above the intersection; of course,
if 's' is simply adjusted to be the nearest fixed point coordinate to the
intersection, then 'e' may become a trapezoid and 'h' may become a
triangle, but that's fine as alpha(gh) >= alpha(gt) in that case.
I thought that because Render permits 16 bits of alpha that we would need
to permit 's' to be moved to within 1 part in 2**16 of 'X', but that isn't
clear to me now. Oh yes, here's a construction:
v
l ---+----/---------------------+
|e / f |
u ''----/____ |
|d/ t ''''----____ |
s ====/==================''''----____
/ |
/| |
| |
| |
+--------------------------+
Here I can make 'e' arbitrarily small and must be able to move 's' so that
alpha(dt) == alpha(de); permitting 's' to be moved to within 1 part in
2**16 satisfies that condition, given Carl's alpha_from_area function.
Keith Packard XFree86 Core Team Compaq Cambridge Research Lab
_______________________________________________
Render mailing list
[EMAIL PROTECTED]
http://XFree86.Org/mailman/listinfo/render
