[prev in list] [next in list] [prev in thread] [next in thread] 

List:       xfree-render
Subject:    [Render] Point sampling trapezoid alpha (was: Another subtle issue...)
From:       Carl Worth <cworth () east ! isi ! edu>
Date:       2002-12-19 17:09:41
[Download RAW message or body]

On Dec 14, Keith Packard wrote:
 > I was chatting with Lyle Ramshaw on Thursday and he suggested that we
 > reappraise our alpha computation technique.  Switching from area
 > computation to point sampling would eliminate the difficulties we're having
 > with negative alphas and weird interactions of multiple edges within the
 > same pixel.
 > 
 > The basic idea is to place points within the pixel and count how many are 
 > "inside" the trapezoid.

This looks like a promising approach. I'd like to pick up where Keith
left off as far as formalizing the description above.

Keith already proposed a formula for the number of sample points per
pixel as well as a rectangular grid relationship among the points:

	d == alpha depth
	s == # of sample points per pixel
	w,h == width and height of rectangular grid (w * h = s)

	     d
	s = 2  - 1

	               (d/2)
	w = { d even: 2      + 1 }
	               d
	    { d  odd: 2  - 1     }

	               (d/2)
	h = { d even: 2      - 1 }

	    { d  odd: 1          }

The next question is how to place these points on Render's subpixel
grid. I propose that the first point should be placed on the integer
coordinate of the whole-pixel grid.

So, given a pixel with integer coordinates (pixel.x, pixel.y), the
ideal coordinates of the sample point p[i,j] (0<=i<w, 0<=j<h) are
given by:

	p[i,j].x = (pixel.x << 16) + i * (1<<16) / w;
	p[i,j].y = (pixel.y << 16) + j * (1<<16) / h;

These ideal coordinates need to be rounded to the subpixel
grid. The natural approach, (with rounding down) would be:

	p[i,j].x = (pixel.x << 16) + floor(i * (1<<16) / w);
	p[i,j].y = (pixel.y << 16) + floor(j * (1<<16) / h);

Which has an unfortunate side-effect that the spacing between samples
is not uniform for some bit depths. It does turn out to give uniform
spacing for some interesting bit depths though, namely: 1, 2, 4, 8,
16.

We can rewrite the equations above to guarantee uniform spacing for
any bit depth:

	p[i,j].x = (pixel.x << 16) + i * floor((1<<16) / w);
	p[i,j].y = (pixel.y << 16) + j * floor((1<<16) / h);

For depths 1, 2, 4, 8, 16, these equations yield identical
results. For other depths, using these equations will yield some more
error as the samples will cover our box less uniformly.

It's easier to see why rounding the spacing does not affect the result
for our magic bit depths by rewriting the equations as:

	p[i,j].x = (pixel.x << 16) + i * floor(((1<<16) - 1) / w);
	p[i,j].y = (pixel.y << 16) + j * floor(((1<<16) - 1) / h);

Where here it is easily observed that 65535 is evenly divided by 1, 3,
5, 15, 17, 255, and 255, (the possible values for w and h given alpha
depth of 1, 2, 4, 8, or 16).

Does this final placement of the sample locations seem reasonable?

Once we have firmly placed the sample points, the remaining question
is how to define whether a sample point is "within" the trapezoid.

A first attempt would be that a sample point (p) is within the
trapezoid (t) if it meets all the following conditions:

	p.y >= t.top
	p.y <  t.bottom
	p is left of t.right
	p is right of t.left

The definitions of "left of" and "right of" need some closer
examination, with especial care so that no sample point is ever
counted as within two disjoint trapezoids. We can make our lives
easier by rewriting the last condition as "p is not left of t.left".

I'm still not sure how to define "left of" though. The simplest
implementation as proposed by Keith would walk the trapezoid lines
along the sample point grid determining how many sample points are
left of the line at each row/column of the grid. A difficulty arises
when rounding line intersections to points within the sub-pixel grid.

Consider the following line which passes within a sub-pixel in each
dimension of sample point p:

     \     |
      \----+----+
      |\   |    |
      | \  |    |
p.y---+--x-p----+---
      |   \|    |
      |    y    |
      +----+\---+
           | \
          p.x

If the line is intersected with the Y value of the sample point (p.x),
the resulting ideal X value (x) could be rounded down and the sample
point will be not be considered left of the line. If however, the line
is intersected with the X value of the sample point (p.y), the
resulting ideal Y value (y) could be rounded down so that the point
will be considered left of the line.

This specific example demonstrates a problem when rounding
down. Corresponding problems exist with any rounding mode.

I mentioned this same rounding ambiguity earlier in relation to whole
pixel intersections with the area-based alpha computation. The point
sampling approach can suffer from the problem more since potentially
as many as w points may be classified differently by different
implementations depending on which axis is used for intersecting lines
to compute sample point containment.

If we can come up with an approach that can analytically compute the
number of sample points within a trapezoid given only the pixel
intersection points, (without doing sub-pixel stepping), then the
severity of this ambiguity would be reduced.

-Carl

_______________________________________________
Render mailing list
Render@XFree86.Org
http://XFree86.Org/mailman/listinfo/render
[prev in list] [next in list] [prev in thread] [next in thread]