Re: Trouble in trapezoid land

Around 19 o'clock on May 17, Carl Worth wrote:

> Accurately reproducing small features of sub-pixel geometry and
> precisely computing area is never important. The "sum to 1" invariant
> is only important when the whole pixel is covered and the algorithm
> maintains that even with truncating negative alphas to 0.

I respectfully disagree.  Sub-pixel coverage areas are very visible along
the smooth edges of objects; coverage discrepancies on the order of 1/4 of
a pixel are visually jarring, while discrepancies down around 1/10 of a
pixel are discernable on close visual inspection.  They appear as 
discontinuities in otherwise smooth surfaces.

The goal of the algorithm is to reproduce alpha values for cummulative 
rendering proceses to within a few parts of the true alpha value; this 
ensures clean edges for figures even when some pixels are rendered by many 
trapezoids.

I think we could use some quantitative measurement about how often such 
pixels will occur.  I think we can analyse this:

 1	They can only occur at the upper left corner of a trapezoid;
	those are the only pixels with more than two alpha values. used
	in their computation.

 2	They can only occur when the area covered by the corner of the
	trapezoid is less than 1/255.

 3	The can only occur when the total error in estimating the four
	alpha values is greater than 1 + area(trap)*255

Condition 1 says that we only get one broken pixel per trapezoid.

Condition 2 limits the number of broken trapezoids to 1/255 of the total
number drawn

Condition 3 limits this even further; trapezoids with an area of 1/255 must
be matched with an error in alpha computation of precisely 1/2 in all four 
terms, a rather small amount of the time while trapezoids with an area of 
zero can be matched with many possible sets of error bounds, perhaps as 
much as 1/2 of the time (that's just a rough guess, not a computed answer).

So, we're looking at getting broken trapezoids somewhere less than one in 
a thousand trapezoids, each of these results in the alpha for the 
containing pixel being mis-computed by one.  Randomly distribute the 
broken trapezoids around the screen and the chance of any particular pixel 
being hit by more than one broken trapezoid is remote, the chance of 
getting hit by enough trapezoids to cause a visible effect should be 
vanishingly small.  If there is a problem, simply increase the depth of 
the alpha buffer.  This serves to both reduce the number of broken 
trapezoids as well as reduce their impact.

Keith Packard        XFree86 Core Team        HP Cambridge Research Lab