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:}