antialiasing straight lines

[JohnF]

Google gives tons of antialiasing hits, and the right page
must be out there somewheres, but I couldn't find one with a
straightforward description of an algorithm for what I want.

I've got an in-memory grid of bytes, all initted to 255=white=bg,
and want to draw a line from, say, (x,y) to (x',y').
I'm now doing that by divide-and-conquer: find the midpoint
x"=(x+x')/2, y"=(y+y')/2, and then recursively call the drawing
routine for lines (x,y) to (x",y") and also (x",y") to (x',y').
When the (truncated) points coincide, that pixel is set to 0=black.

I'd now like to grayscale adjacent points a bit for antialiasing.
What's a good way to do that? Or just a pointer to an online
page is great, too. Thanks,
--
John Forkosh ( mailto: j...@f.com where j=john and f=forkosh )

[Daniel Pitts]

That's an unusual line drawing algorithm you've got there. Typical line
algorithms iterate for each pixel on *one* axis, calculating the value
of the other axis. You can include an "error" term, which will tell you
how far between the two pixels it is.

This is a bit of a naive approach, but it works for common cases.

[Thomas Richter]

This sounds like a very strange algorithm. The typical line drawing
approach is that of Bresenham - the line advances pixel by pixel in the
major direction, and movement in the minor direction depends on an
integrated error term. For antialiasing, I would use an interpolation
dependent on this error term.

There is lots of online material if you look for "Bresenham".

HTHH,
Thomas

[JohnF]

Nope, Bresenham's no help, but a page about it tangentially mentioned
Wu's algorithm,
http://wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm
which is perhaps what I'm looking for.
I don't need to keep my original divide-and-conquer algorithm
if it doesn't permit a feasible antialiasing enhancement. But I coded
it that way along with a bezier curve function, whose "natural"
implementation is similarly divide-and-conquer, though more complicated.
So I just used that same technique for several different drawing
functions. Easier to read them together that way. But now I need
to antialias them, and figured I'd focus on straight lines first.
However, I'm not sure how Wu's straight line algorithm would
translate to bezier curves, which is why I'd prefer to antialias
the divide-and-conquer algorithm if that's feasible.
The C code for the unantialiased (is that a word?) looks
something like, where grid is a struct with all relevant stuff,
and setpixel() and iround() do the obvious,
/* --- entry point --- */
int line_recurse ( grid *gp, double row1, double col1,
double row2, double col2 ) {
/* -------------------------------------------------------------------------
draw line in grid from point (row1,col1) to point (row2,col2)
-------------------------------------------------------------------------- */
double delrow = fabs(row2-row1), /* 0 if horizontal */
delcol = fabs(col2-col1), /* 0 if vertical */
tolerance = 0.5; /* draw when line converges to point*/
double midrow = 0.5*(row1+row2), /* midpoint row */
midcol = 0.5*(col1+col2); /* midpoint col */
/* -------------------------------------------------------------------------
recurse if either delta > tolerance
-------------------------------------------------------------------------- */
if ( delrow > tolerance /* row hasn't converged */
|| delcol > tolerance ) { /* or col hasn't converged */
line_recurse(gp,row1,col1,midrow,midcol); /* draw left half */
line_recurse(gp,midrow,midcol,row2,col2); /* draw right half */
return ( 1 ); }
/* -------------------------------------------------------------------------
draw converged point
-------------------------------------------------------------------------- */
setpixel(gp,iround(midrow),iround(midcol),0); /*set midrow,midcol pixel=0*/
return ( 1 ); } /* --- end-of-function line_recurse() --- */

[Thomas Richter]

Am 30.01.2012 13:45, schrieb JohnF:

> Nope, Bresenham's no help, but a page about it tangentially mentioned
> Wu's algorithm,
> http://wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm
> which is perhaps what I'm looking for.

This is pretty much what I had in mind, I didn't know it had a
particular name, though.

> I don't need to keep my original divide-and-conquer algorithm
> if it doesn't permit a feasible antialiasing enhancement. But I coded
> it that way along with a bezier curve function, whose "natural"
> implementation is similarly divide-and-conquer, though more complicated.

I see.

> However, I'm not sure how Wu's straight line algorithm would
> translate to bezier curves, which is why I'd prefer to antialias
> the divide-and-conquer algorithm if that's feasible.

A simple approach would be to compute the points on the Bezier curve in
fixed point precision (i.e. several bits preshifted) and use the
fractional part of the point position to establish the grey value for
anti-aliasing purposes. This would be an analogue of Wu's algorithm.

So long,
Thomas

[Dr J R Stockton]

In comp.graphics.algorithms message <jg43p0$2gd$1...@reader1.panix.com>,
Sun, 29 Jan 2012 18:39:28, JohnF <jo...@please.see.sig.for.email.com>
posted:

>I'd now like to grayscale adjacent points a bit for antialiasing.
>What's a good way to do that? Or just a pointer to an online
>page is great, too. Thanks,

Google: bresenham greyscale grayscale .

--
(c) John Stockton, nr London, UK. ?@merlyn.demon.co.uk Turnpike v6.05.
Website <http://www.merlyn.demon.co.uk/> - w. FAQish topics, links, acronyms
PAS EXE etc. : <http://www.merlyn.demon.co.uk/programs/> - see in 00index.htm
Dates - miscdate.htm estrdate.htm js-dates.htm pas-time.htm critdate.htm etc.

[JohnF]

Thanks, Thomas. That sounds like a terrific idea. So if dx=x-(int)x,
and ds^2=dx^2+dy^2, then pixel=0(black fg) if ds=0, and =255(white bg)
if ds^2=2. My eyeball experience suggests it'll look best going to black
faster than linearly, e.g., pixel=255*(.5*ds^2). Guess I'll just have
to try it and look. Thanks again,