Re: Sub-pixel area computations

On May 2, Keith Packard wrote:
 > We can't snap coordinates to the top and bottom of the trapezoid -- we 
 > could snap them to the top and bottom of the pixel.  Here's why:
 > 
 >                         E
 >                          \
 >                 +---------J----+
 >                 |          \   |
 >                 |    A      \ B|
 >            ==================I |
 >                 |             \|
 >                 |    C         K
 >                 |              |\
 >                 +--------------+ \
 > 
 > I'm tesselating a figure and I've got three trapezoids meeting here in 
 > this pixel.  The sum of A, B and C must be exactly 1.  The area to the 
 > left of 'E' is going to be compute three times, the whole area when 
 > drawing 'B', and part of the area when drawing 'A' and 'C'.  The sub-area 
 > computations needed for 'A' and 'C' must sum to the same value as the area 
 > computation needed for 'B'.  
 > 
 > Hence the x coordinate at the intersection 'I' cannot be snapped for the
 > computation of either A or C -- the location of 'I' is unknown during the 
 > computation of 'B'.  If snapping 'J' and 'K' would be useful, we can do 
 > that -- those locations are known during all of the computations.

Excellent example Keith.

(BTW: This is Carl speaking live to the Render list now, rather than
through Keith's way-back machine).

Here's one obvious way to deal with this case:

When computing pixel coverage, first determine the area without
considering the horizontal trapezoid line, (eg. find the area of A+C
in the figure above using only the points J and K).

Then, given that area, which I'll call D, the implementation can then
consider the horizontal trapezoid line, (even snapping I if
necessary). It simply must guarantee that the computation satisfies:

	 A + C = D

One way to do this would be to always directly compute only the
sub-pixel area above the horizontal trapezoid line, (eg. A would be
computed directly while C would be determined by D minus A ).

There might still be another case or two to work out if both
horizontal lines appear in a single pixel.

-Carl

-- 
Carl Worth                                        
USC Information Sciences Institute                 [email protected]
3811 N. Fairfax Dr. #200, Arlington VA 22203		  703-812-3725