Around 20 o'clock on Apr 30, Carl Worth wrote:
> I've got the code figured out for line walking I think. Bresenham
> never really applies since in one dimension I walk a full pixel while
> in the other I walk some number of partial pixels, (so a binary
> decision variable doesn't help).
It's not a "real" bresenham, but the essential trick is to walk in
rational space rather than fixed-point space.
Here's an extract from mi/miwideline.h which does this:
left_x += left_stepx;
left_e += left_dx;
if (left_e > 0)
{
left_x += left_signdx;
left_e -= left_dy;
}
As you can see, the error term is used to walk the rational slope of the
line so that no error accumulates across an arbitrary number of steps,
so it looks a lot like a bresenham.
You can use this to step forward a number of partial pixels as well, this
should let you compute error terms at the fractional pixel points of the
horizontal edges of the trapezoid. The first step would then use a
different dx/dy value.
You'll also need separate x-major/y-major versions to walk in different
directions. I'm wondering (aloud) if we'll want a span-based interface at
some level so that we don't push a lot of zeros around when drawing thin
objects (like lines); that's obviously a second stage in this process
though.
> The one case I still need to think about precision is in clipping the
> initial left/right lines to the top line before starting the iterative
> walking. Maybe I'll just have to use the same iterative walk to extend
> from the points I'm given until I hit the top line.
That just requires a partial step before the main loop. I think that just
needs a different dy value, of course you'll have to compute the precise
dx value needed as well, that should be pretty easy and equivalent to
clipping bresenham lines.
Keith Packard XFree86 Core Team Compaq Cambridge Research Lab
_______________________________________________
Render mailing list
[EMAIL PROTECTED]
http://XFree86.Org/mailman/listinfo/render
