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.
(I should point out that most of this analysis is not my own but came
through several conversations with Keith. I'm simply applying the same
analysis to the latest batch of equations).
Anyway, here's our pixel picture:
n u v o
| \ / |
l---+--------\-----------/---------+
| \ / |
| a \ b / c |
| \ / |
r ===============\===/================
| \e/ |
| d X f |
| /t\ |
s ===============/===\=============|
| / \ |
|g / h \ i|
| / \ |
m---+--------/-----------\---------+
Notice the new triangle, t, that was not part of the earlier
drawing. The allocation of the area(t) must be considered carefully to
guarantee that the sum of all polygon alpha values results in the
alpha of the pixel.
Things can still work in this case, but we have to make some slight
adjustments to our definitions.
First, I'll reproduce the equations we have already. I'll only show
the equations needed to compute alpha(e) which is really the term of
interest, (namely the alpha coverage of this pixel by the given
trapezoid).
alpha(a) = alpha_from_area(area(a))
alpha(ad) = alpha_from_area(area(ad))
alpha(ab) = alpha_from_area(area(ab))
alpha (abde) = alpha_from_area(area(abde))
alpha (d) = alpha(ad) - alpha (a)
alpha (de) = alpha (abde) - alpha (ab)
alpha (e) = alpha (de) - alpha (d)
All of the other equations we had before can be generated using this
set and simply substituting n,o in place of u,v and substituting l,m
in place of r,s.
So, what happens with this new triangle t? When we compute the area of
the trapezoid to the left, we will get an area:
alpha(d') = alpha(d) + alpha(t)
and for the trapezoid to the right:
alpha(f') = alpha(f) + alpha(t)
Notice that the area of t is counted twice! We can't prevent this,
since when generating each of these, only one of the lines u or v will
be available, so it is impossible to determine how large t is and
subtract it off in either case.
So, to compensate for this we can subtract it during the computation
of e, since both u and v are available:
alpha(e') = alpha(de) - (alpha(dt))
With this in place we have the sum of d', e', and f' equal to d,e,f,t
as necessary. (Note: It's important to point out that alpha values
must be non-negative, so this only works as long as t is never larger
than e. Fortunately, the client can be careful in its tessellation to
guarantee this fact.)
Well, that all may seem rather hairy, but we can actually formulate
the specification in a way that is no more complicated than the
original equations above, that still does the right thing in this
case.
Instead of using regions designated by letter, let's formulate the
equations in terms of trapezoids that are always specified by two
horizontal lines, (top and bottom), and two non-horizontal lines,
(left and right). We can designate the pixel boundaries with four
similar lines, (pt, pb, pl, and pr):
pl l r pr
| \ / |
pt---+--------\-----------/---------+
| \ / |
| \ / |
| \ / |
t ===============\===/================
| \A/ |
| X |
| / \ |
b ===============/===\=============|
| / \ |
| / \ |
| / \ |
pb---+--------/-----------\---------+
Using T(t,b,l,r) to specify a trapezoid bounded by t,b,l, and r we have:
alpha(T(t,b,l,r)) = alpha(T(t,b,pl,r)) - alpha(T(t,b,pl,l)
alpha(T(t,b,pl,l)) = alpha(T(pt,b,pl,l)) - alpha(T(pt,t,pl,l))
alpha(T(t,b,pl,r)) = alpha(T(pt,b,pl,r)) - alpha(T(pt,t,pl,r))
Which, by careful examination can be seen to be equivalent to the
original equations modified to handle the case when the lines cross as
discussed above.
If anyone can think of a more intuitive way of writing these three
equations, that would be appreciated. But this should capture the
essential details of the specification I think. Hopefully one can see
that they correspond to the former equations:
alpha(e) = alpha(d+e) - alpha(d+t)
alpha(d+e) = alpha(abde) - alpha(ab)
alpha(d+t) = alpha(ad+t) - alpha(a)
But, that would perhaps not be as good a way to specify the equations
since t will not always exist. Maybe there's a better way to specify
it in terms of pixel_area_left_of(...) or something.
-Carl
--
Carl Worth
USC Information Sciences Institute [EMAIL PROTECTED]
3811 N. Fairfax Dr. #200, Arlington VA 22203 703-812-3725
_______________________________________________
Render mailing list
[EMAIL PROTECTED]
http://XFree86.Org/mailman/listinfo/render
