Re: Re: Sub-pixel area computations

Around 11 o'clock on May 3, Carl Worth wrote:

> For these implementation suggestions, I'll have to think about them a
> bit more.

They aren't implementation suggestions, they'll be part of any spec we 
write.  Implementing the code differently will generate different results.

> Meanwhile, I don't think it will be hard to plug in the new alpha
> calculations to the implementation shell I have so far. The only
> outstanding implementation issue I'm still dealing with is in coming up
> with the rounded-off sub-pixel vertex coordinates:

That's really pretty easy.  Your bresenham should be walking sub-pixel 
coordinates rather than pixel coordinates.  Now you can calculate the 
sub-pixel Y coordinate for any arbitrary sub-pixel X coordinate (or vice 
versa).

	ey:	y error term (distance from current Y sub-pixel to line) * dx
	ex:	x error term (distance from current X sub-pixel to line) * dy
	dx:	difference of X coordinates for line endpoints
	dy:	difference of Y coordinates for line endpoints
	x:	current fixed-point X coordinate
	y:	current fixed-point Y coordinate

One of ey or ex will always be zero, depending on whether the distance to 
the line was measured horizontally or vertically.

In moving from x, y to x1, y1:

	(x1 + e1x/dy) - (x + ex/dy)   dx
	--------------------------- = --
	(y1 + e1y/dx) - (y + ey/dx)   dy

	(x1dy + e1x) - (xdy + ex) = (y1dx + e1y) - (ydx + ey)

	dy(x1 - x) + (e1x - ex) = dx(y1-y) + (e1y - ey)

So, if you know y1 and want to know x1:

    Set e1y to zero and compute the error from x:

	oex = dx(y1 - y) - ey + ex

    Compute the number of whole pixels to get close to the line:

	wx = oex / dy

    Set x1:

	x1 = x + wx

    Now compute the e1x:

	e1x = oex - wx * dy

A similar operation moves to a known y1.  Note that this computation (in 
general) requires 64 bit arithmetic.  I suggest just using the available 
64 bit datatype for now, we can optimize the common cases with a few 
conditionals.  There's some cpp code in fb/fb.h that selects a 64 bit type 
for machines that XFree86 builds on; there aren't any machines missing a 
64 bit datatype that I know of.

Keith Packard        XFree86 Core Team        Compaq Cambridge Research Lab