More trouble in trapezoid land

Just when you thought it was safe to draw trapezoids...

I've been experimenting with 'sharp' polygons, those with aliased edges. 
This is effected by generating a 1-bit mask instead of an 8-bit mask.

It shows off-by-one errors quite easily.

Here's one:


	  +--/--------+
	  |A/         |
	  |/   B      |
	  /           |
	 /|           |
	------------------ 0.5
	 \|           |
	  \    C      |
	  |\          |
	  |D\         |
	  +--\--------+

Ok, so let's enumerate the "primitive" alphas, those computed
directly from the area:

	A, AB, D, ABCD

And composite alphas:

	B = AB - A
	CD = ABCD - AB
	C = CD - D

Now, try a few rounding modes:

		Round	Ceil	Floor
	A	0	1	0	<-
	AB	1	1	0
	D	0	1	0	<-
	ABCD	1	1	1
	B	1	0	0
	CD	0	0	1
	C	0	-1	1
	A+B+C+D	1	2	1


This example has a problem when using 'Ceil' rounding; the pixel
will be drawn by both trapezoid 'A' and 'D'.

Here's another one:

	         L
	+---------\---+------------+
	|          \  |            |
	|      A    \B|      C     |
	|            \|            |
	|             \            |
	---------------\-------------  N
	|      D      |E\    F     |
	+-------------+--\---------+

B and C belong to trap Q
A D E belong to trap R
F belongs to trap S

Trap R is rendered without knowledge of boundary N

When drawing trap Q:

	Aq: primitive
	ABq: primitive
	ADq: primitive
	Bq = ABq - Aq

When drawing trap R:

	ADr: primitive

Trap S doesn't intersect the left pixel at all, it's alpha is not
evaluated.

Now, try a few rounding modes:

		Round	Ceil	Floor
	Aq:	1	1	0
	ABq:	1	1	0
	ADq:	1	1	0
	ADr:	1	1	0	<-
	Bq:	0	0	0	<-

This example has a problem when using 'Floor' rounding; the pixel
is never drawn. Curiously, if you blindly evaluate the alpha for trap S,
it turns out to be one.  Pretend there is a zero-sized trapezoid 'G'
between the line 'L' and the right edge of the left pixel

	As: 	primitive
	ADs: 	primitive
	ABs:	primitive
	ABDGs:	primitive
	Ds 	= ADs - As
	DGs	= ABDGs - ABs
	Gs	= DGs - Ds

		Round	Ceil	Floor
	As	1	1	0
	ADs	1	1	0
	ABs	1	1	0
	ABDGs	1	1	1
	Ds	0	0	0
	DGs	0	0	1
	Gs	0	0	1

We've just approximated an empty pixel with an alpha of 1.  Move left and 
perform the same hat trick and you get another 'full' pixel.

Now we've eliminated 'floor' and 'ceil' as accurate rounding modes, here's
my final example:

	  +----------/
	  |         /|
	  |        / |
	  |       /  |
	  |  A   /   |
	  |     /    |
	  |    /   B |
	  |   /      |
	-----/----------  N
	  |C/        |
	  |/      D  |
	  +----------+

	Trap R:		AC (no knowledge of N)
	Trap S:		B
	Trap T:		D

	ACr/ACt:	primitive
	ABs/ABt:	primitive
	At/As:		primitive
	ABCD:		primitive
	Bs:		ABs - As
	CDt:		ABCD - ABt
	Ct:		ACt - At
	Dt:		CDt - Ct

			Round	Ceil	Floor

	At/As:		0	1	0
	ACr/ACt:	1	1	0	<-
	ABs/ABt:	1	1	0
	ABCD:		1	1	1
	Bs:		1	0	0	<-
	CDt:		0	0	1
	Ct:		1	0	0
	Dt:		-1	0	1	<-

Our old negative alpha friend has reappeared, resulting in a pixel getting
rendered twice.

I have two suggestions here -- it's clear that the 'Round' mode generates 
the most "reasonable" results, except for negative alpha.  Given that
these computations reflect sub-pixel accumulated error in coverage 
involving deeper alpha values, it seems that 'Round' is our mode of 
choice; it limits the error to cases where some portion of the pixel is 
smaller than 1/max_alpha, and then errors occur only in the upper left
corner of the trapezoid.

However, when depth is 1, we obviously need a different spec -- it's 
rather hard to generate trapezoids whose pixel coverage is always
>= 1/max_alpha when max_alpha is 1.  For this case, I suggest that we 
ignore area and look only at whether the desired region contains a 
particular point within the pixel -- to match our AA trapezoids, that 
should probably be the center.  I think all this requires is a change in 
how the primitive alpha values are computed; alpha is '1' if the primitive 
area contains the line from the center of the pixel to the origin, else 
'0'.  I'll give this a try and see what happens.

Keith Packard        XFree86 Core Team        HP Cambridge Research Lab