Antialiasing Bresenham (Pitteway & Watkinson)

Antialiasing Bresenham (Pitteway & Watkinson)

Post by frab » Fri, 26 Apr 2002 14:15:02



Hi,

I'm trying to implement an anti-aliasing version of the Bresenham algo
by using the Pitteway and Watkinson area calculation. The only
information I have about the Pitteway and Watkinson algorithm is from my
old textbook.

Bresenham tests the sign of a variable to determine which pixel it
should draw next. The P&W version is based on modifying this variable so
that it is the area of the next pixel.

 From my text (Computer Graphics, Donald Hearn & Pauline Baker) you
determine which pixel is nearer by,

y - y_mid = [m(x_k + 1) + b] - (y_k + 0.5)

You can turn this into an area (and an interval from 0 to 1) by adding 1-m,

p = [m(xk + 1) + b] - (yk +0.5) + (1 - m)

which reduces to,

area = m*x_k + b - y_k + 0.5

where x_k and y_k are the current x and y that you are plotting. To test
which pixel to plot, you test p < 1 -m (y_k is nearer. else, y_k + 1 is
nearer).

This version works if m is from 0 to 1 and postive.

I tried putting this into Breshenham as shown below. The problem I'm
getting is that the area that I calculate isn't reliable; sometimes it's
more than 1.0, like 1.15.

The pixels light up exactly as Bresenham, so the condition works at
least. I would suspect that to get this working properly, I'd have to
draw the pixels that I skip too (the next pixel you pick is the pixel
that the line is on more; if it's still lies on the pixel I didn't pick,
I still need to draw that pixel, just very dim).

Does anyone know why the area is being calculated wrong? Can someone
point me to the original paper by Pitteway and Watkinson, or cite it? I
think it's published through the ACM, 1980.

//float x1, x2, y1, y2: incoming pixel coords
//
x1,y1 = 0,0. x2,y2 = 55,83.
int
d, x, y, ax, ay, sx, sy, dx, dy;
float
area, m, p, iM;         //iM is 1-m.

dx = x2 - x1;
ax = abs(dx) * 2;
sx = 1;
if (dx < 0) sx = -1;

dy = y2 - y1;
ay = abs(dy) * 2;
sy = 1;
if (dy < 0) sy = -1;

m = ay/(float)ax;
iM = 1.0 - m;

x = x1;
y = y1;

d = ax - ay / 2;        //bresenham
p = m * x + x1 - y + 0.5;
while (1)
{
        //draw pixel
        area = p;
        if (area < 0) area = -area;

        setpixel(pixmap, x, y, 1-area);

        //exit condition
        if (y == y2) return;

        if (p < iM)  //d > 0
        {
                x = x + sx;             //sx is x increment; 1.
                d = d - ay;                            
        }

        y = y + sy;
        d = d + ax;     //bresenham decision var

        p = m * x + x1 - y + 0.5;

Quote:}

 
 
 

Antialiasing Bresenham (Pitteway & Watkinson)

Post by Maxim Shemanar » Fri, 26 Apr 2002 22:09:25


In reality it's not as easy as it looks. I worked on it and came to
the conclusions:

1. First you need to modify Bresenham that it wouls work in subpixel
coordinates. It's hard to explain in a few words, but obviously line
segments (0,0) -> (5,3) and (0,0.45) -> (5,2.55) should activate
different sets of pixels even without anti-aliasing.

2. It's easier to perform anti-aliasing basing on the _distance_
between the center of pixel being activated and the line (represented
in
subpixel coordinates). The result it better for lines of about 1 pixel
width, but worse if the line has much less thickness (say, 0.2
pixels).

3. In general case you should be able to draw anti-aliased lines of
any thickness (say, 0.5 pixels, 1.2 pixels and so on).

4. I could not avoid expensive operations of integer division - one
division per line step.

Finally I implemented an algorithm that works in integer coordinates
with subpixel accuracy of 1/16 of a pixel. Actually, the accuracy can
be more than that, say, 1/32 of 1/64. But believe or not, with 1/64
you can easily obtain overflow working in 32-bit integers.

Download my old project from
http://www.veryComputer.com/

But even in this case the maximal line width is restricted with some
predefined value (say, 8 pixels).

In my new project I changed the approach and use a general polygon
renderer with anti-aliasing for drawing lines. It allows to draw lines
of any width (more than a pixel as well as less than a pixel) and any
shape (say, *cap, round cap, square cap), although my old lines
work 3-5 times faster and I'm thinking about the inclusion the old
algorithm into the new project.
http://www.veryComputer.com/ (sorry for broken links in the doc section -
it's in process now).

McSeem

 
 
 

Antialiasing Bresenham (Pitteway & Watkinson)

Post by Mik » Sun, 28 Apr 2002 06:26:24



> 2. It's easier to perform anti-aliasing basing on the _distance_
> between the center of pixel being activated and the line (represented
> in
> subpixel coordinates). The result it better for lines of about 1 pixel
> width, but worse if the line has much less thickness (say, 0.2
> pixels).

> 3. In general case you should be able to draw anti-aliased lines of
> any thickness (say, 0.5 pixels, 1.2 pixels and so on).

There is an issue with drawing lines less than one pixel wide.  The
whole feature is at a higher frequency than the Nyquist limit.  Even
"antialiased" lines produced by conventional means, such as
supersampling or attenuating based on the distance from the pixel to
the line, will produce aliasing artefacts.  I think the best way to
draw a line less than one pixel wide is to draw a one-pixel-wide line,
and 'fade' it out by an appropriate factor.
 
 
 

Antialiasing Bresenham (Pitteway & Watkinson)

Post by Maxim Shemanar » Tue, 30 Apr 2002 13:49:34


Quote:> There is an issue with drawing lines less than one pixel wide.  The
> whole feature is at a higher frequency than the Nyquist limit.  Even
> "antialiased" lines produced by conventional means, such as
> supersampling or attenuating based on the distance from the pixel to
> the line, will produce aliasing artefacts.  I think the best way to
> draw a line less than one pixel wide is to draw a one-pixel-wide line,
> and 'fade' it out by an appropriate factor.

Exactly. I meant you should be able to set the width less than 1 pixel
and it should be properly emulated with fading. Not every library can
do that, for example MS GDI+ cannot:
http://www.antigrain.com/agg_comparison/agg_gdiplus.html

McSeem

 
 
 

1. Pitteway's Curve Tracking Algorithm

I was wondering if anyone had source code to Pitteway's curve-tracking
algorithm, an integer-only incremental algorithm for drawing arbitrary
conic sections.  I have two good descriptions of the algorithm, but have
had a tough time getting it to work right.

If you have source you are willing to share or a pointer to source,
please email me.  Language matters not, it can be in LISP for all I care.

--Nick

2. no audio

3. Bresenham algorithm & 4-connex filling problem

4. FS: SIGGRAPH CD-ROMS, 1993-1999

5. Bresenham&Scanline?

6. Transparency in Direct3D8

7. fast Bresenham & constant Gouraud triangles

8. Progetto

9. DDA & Bresenham

10. TIFF antialiasing without antialiasing?

11. Full Scene Antialiasing [LONG] (was Re: Antialiasing fonts)

12. GLUT & Antialiasing

13. OpenGL & Antialiasing