mannycalaveras
asked on
Using Wu's Anti-Aliasing algorithm
I'm having problem finding resources to help me grasp Wu's Anti-Aliasing algorithm and use it in actual code (c++).
I need it for lines as well as curves and would need a starter to get me the basics maths behind it. I found some formulas explained either incomprehensibly or well-explained but with variables (both code and formula) that were not explained where do they come from and especially what they do.
Any help would be a booster!
But a good resource would be a lot better of course :)
Rich.
I need it for lines as well as curves and would need a starter to get me the basics maths behind it. I found some formulas explained either incomprehensibly or well-explained but with variables (both code and formula) that were not explained where do they come from and especially what they do.
Any help would be a booster!
But a good resource would be a lot better of course :)
Rich.
I never heard of Wu's algorithm but before 3d chips came out I used to create 3d engines and have encountered antialiasing and had to develop my own approach. If You tell me where to find theese formulas or send them to me, I can try to figure out, what is behind.
I'm not familiar with Wu's AA Algorithm either, but most AA routines follow similar patterns:
1. Rendering objects at a much higher resolution internally and then sampling them down. To visualise this, imagine drawing on a black screen of resolution of 1280 by 960 pixels. Two white lines go across each diagonal corner forming an "X" on the screen. Now, divide that screen into little blocks of 2 by 2 pixels. Each block can have between 0 and 4 white pixels in it.
If a block has no white pixels in it, we can plot a corresponding black pixel on a 640 by 480 screen.
If a block has, say, two white pixels in it, we can plot a corresponding mid-grey pixel on a 640 by 480 screen.
If a block has four white pixels in it, we can plot a corresponding white pixel on a 640 by 480 screen.
Following this we'll get an antialiased image of the X at 640 by 480.
The higher resolution we prerender the "X" into, the higher number of pixels in each block, and correspondingly the greater range of shades available for the antialiased low-res version.
This method is fast but requires a lot of memory to render the high resolution image into. There is a similar method which uses an accumulation buffer to prerender small sections of the high-res image, which can save much of the memory, but is a fair bit more complax to implement.
2. The second method (and the one that I suspect this Wu's algorithm is similar to) considers a line to be an instance of a very thin rectangle and how far each pixel is from the theoretical line centre. The further away it is, the darker it should be. If I remember correctly it uses something like one square root per pixel (!) making it *much* slower than method 1 above, and is quite difficult to generalise to other graphical primitives (eg. circles) but being computational in nature it has very low memory requirements. This algorithm is described in great detail in "Computer Graphics: Principles and Practice", 2nd edition, by Feiner, Van Dam, Foley and Hughes - a *must* for graphics programmers.
HTH
1. Rendering objects at a much higher resolution internally and then sampling them down. To visualise this, imagine drawing on a black screen of resolution of 1280 by 960 pixels. Two white lines go across each diagonal corner forming an "X" on the screen. Now, divide that screen into little blocks of 2 by 2 pixels. Each block can have between 0 and 4 white pixels in it.
If a block has no white pixels in it, we can plot a corresponding black pixel on a 640 by 480 screen.
If a block has, say, two white pixels in it, we can plot a corresponding mid-grey pixel on a 640 by 480 screen.
If a block has four white pixels in it, we can plot a corresponding white pixel on a 640 by 480 screen.
Following this we'll get an antialiased image of the X at 640 by 480.
The higher resolution we prerender the "X" into, the higher number of pixels in each block, and correspondingly the greater range of shades available for the antialiased low-res version.
This method is fast but requires a lot of memory to render the high resolution image into. There is a similar method which uses an accumulation buffer to prerender small sections of the high-res image, which can save much of the memory, but is a fair bit more complax to implement.
2. The second method (and the one that I suspect this Wu's algorithm is similar to) considers a line to be an instance of a very thin rectangle and how far each pixel is from the theoretical line centre. The further away it is, the darker it should be. If I remember correctly it uses something like one square root per pixel (!) making it *much* slower than method 1 above, and is quite difficult to generalise to other graphical primitives (eg. circles) but being computational in nature it has very low memory requirements. This algorithm is described in great detail in "Computer Graphics: Principles and Practice", 2nd edition, by Feiner, Van Dam, Foley and Hughes - a *must* for graphics programmers.
HTH
ASKER
About baldrick's first solution, I could not implement it since I am not in a full graphics context. It's for a Photoshop Plug-in so I must use a computed equation much like Wu's (and also implementing Rokne's optimization which doubles it's speed).
And I have in hand "Computer Graphics: Principles and Practice" but cannot, as you state, find Wu's algorithm details in the book. The only algorithm about anti-aliasing is the Gupta-Sproull algorithm. Not that I am extremely picky, but I do need the greater speed and effiency of Wu's algorithm.
And I have in hand "Computer Graphics: Principles and Practice" but cannot, as you state, find Wu's algorithm details in the book. The only algorithm about anti-aliasing is the Gupta-Sproull algorithm. Not that I am extremely picky, but I do need the greater speed and effiency of Wu's algorithm.
About Baldrick's advices. The first one is commonly used in 3d graphics chips called Full Screen Anti Aliasing, but it requires extremely high number of pixels to be generatedand because graphics chips can not live up to that, there are optimisations entering that area too. Description of nvdia's solution (quincunx anti aliasing) You can find here:
http://www.tomshardware.com/graphic/01q1/010227/index.html
I know You are not interesting in full screen methods, but in objet anti aliasing methods. The second Baldrick's advice is of that kind. He wrote that these methods are slower, which is not always true.
As said in my first comment, I played quite a lot with own graphics theory in the past and i came to the next conclusions.
- If Your texture maping (condensing) routine is well written, You only need to bother with AA at the edge area of each object.
- Every mathematical function needed can be represented with a table (indexed acceses to that table are very efficient).
- To use this it is better not to split Your object into small triangles, but to deal with more complex objects.
- You always need to use real life and not mathematical objects (must have all the dimensions - point is a small circle or sphere and line is three dimensional too (could be 2d if Your whole space is 2d too))
http://www.tomshardware.com/graphic/01q1/010227/index.html
I know You are not interesting in full screen methods, but in objet anti aliasing methods. The second Baldrick's advice is of that kind. He wrote that these methods are slower, which is not always true.
As said in my first comment, I played quite a lot with own graphics theory in the past and i came to the next conclusions.
- If Your texture maping (condensing) routine is well written, You only need to bother with AA at the edge area of each object.
- Every mathematical function needed can be represented with a table (indexed acceses to that table are very efficient).
- To use this it is better not to split Your object into small triangles, but to deal with more complex objects.
- You always need to use real life and not mathematical objects (must have all the dimensions - point is a small circle or sphere and line is three dimensional too (could be 2d if Your whole space is 2d too))
ASKER
It's not really that I'm not interested in FSAA...
It's because I can't use this solution. The normal context for which I am developping is enterprises with fairly good computers (mostly macs... graphism after all) but not necessarily with 3d power...
It must be an entirely software solution applicable in the 2D space...
All I need it for is for lines and circles... at least for now, but later I could just take what I'd already have and modify it.
Rich.
It's because I can't use this solution. The normal context for which I am developping is enterprises with fairly good computers (mostly macs... graphism after all) but not necessarily with 3d power...
It must be an entirely software solution applicable in the 2D space...
All I need it for is for lines and circles... at least for now, but later I could just take what I'd already have and modify it.
Rich.
ASKER
It's not really that I'm not interested in FSAA...
It's because I can't use this solution. The normal context for which I am developping is enterprises with fairly good computers (mostly macs... graphism after all) but not necessarily with 3d power...
It must be an entirely software solution applicable in the 2D space...
All I need it for is for lines and circles... at least for now, but later I could just take what I'd already have and modify it.
Rich.
It's because I can't use this solution. The normal context for which I am developping is enterprises with fairly good computers (mostly macs... graphism after all) but not necessarily with 3d power...
It must be an entirely software solution applicable in the 2D space...
All I need it for is for lines and circles... at least for now, but later I could just take what I'd already have and modify it.
Rich.
Hi!
I know what you're talking about.. :)
Wu's antialiased line algorithm is more or less a extension of the good old bresenham line drawing algorithm. Are you really forced to use wu's algorithm, or is it no problem for you to choose something, which is faster and has the same output quality?
Here is a very simple antialiased line drawing algorithm that's in quality comparable to wu, and it's also faster on modern cpu's.
basically all you do is to write a simple line drawing algorithm. But instead of drawing just one pixel you draw two. The colors of these pixels depend on the subpixel fraction.
For the example i assume, that the line is drawed from <0,0> to <100,10>. The algorithm can be extended to any line.. I just don't want to write all the 8 different versions for each octant down.
Here it goes:
void simple_line (float x1, float y1, float x2, float y2
{
// width
float delta_x = (x2-x1);
// height
float delta_y = (y2-y2);
// how long is the line??
int numPixels = floor(delta_x);
// start-height
float start_y = y1;
// how willthe height differ from pixel to pixel?
float dydx = delta_y / delta_x;
for (int i=0; i<numPixels; i++)
{
// that's the current y-value
float y = start_y + dydx*(float)i;
// where to put the pixel??
int pixel_x = i+floor(x1);
int pixel_y = floor(y);
// now.. if you put a pixel at pixel_x, pixel_y you
// have a ordinary one pixel sized line.
// to do that stuff antialiased you just have to draw
// two pixels depending on the fraction of y.
// this is the fractional value that's normally
// thrown away.. we use it to do the antialiased
// blending.
float frac1 = y-floor(y);
float frac2 = 1.0f-frac1;
putpixel (pixel_x, pixel_y, frac2);
if (frac1)
putpixel (pixel_x, pixel_y+1, frac1)
}
}
putpixel gets an additional float value.. if this value is 1.0 the pixel should be drawed with 100% strength.. if 0% it should be transparent (so a little alphablend routine is nessesary for that).
This is the principle.. and i hope it's easy to understand-. I haven't tested the code - just wrote it down from memory, so there might be a bug here or there..
Anyways.. the priciple should be clear.. This code will - as said - only draw lines which start left and have a higher width than height.. You might want to change that code for different cases (e.g. line height > widht)..
For circles it works almost the same. just use a normal circle scanning algorithm, scale the coordinates and use the accuracy that's normally thrown away when converting to pixel-values as a alpha blend factor.
Hope it helps,
Nils
I know what you're talking about.. :)
Wu's antialiased line algorithm is more or less a extension of the good old bresenham line drawing algorithm. Are you really forced to use wu's algorithm, or is it no problem for you to choose something, which is faster and has the same output quality?
Here is a very simple antialiased line drawing algorithm that's in quality comparable to wu, and it's also faster on modern cpu's.
basically all you do is to write a simple line drawing algorithm. But instead of drawing just one pixel you draw two. The colors of these pixels depend on the subpixel fraction.
For the example i assume, that the line is drawed from <0,0> to <100,10>. The algorithm can be extended to any line.. I just don't want to write all the 8 different versions for each octant down.
Here it goes:
void simple_line (float x1, float y1, float x2, float y2
{
// width
float delta_x = (x2-x1);
// height
float delta_y = (y2-y2);
// how long is the line??
int numPixels = floor(delta_x);
// start-height
float start_y = y1;
// how willthe height differ from pixel to pixel?
float dydx = delta_y / delta_x;
for (int i=0; i<numPixels; i++)
{
// that's the current y-value
float y = start_y + dydx*(float)i;
// where to put the pixel??
int pixel_x = i+floor(x1);
int pixel_y = floor(y);
// now.. if you put a pixel at pixel_x, pixel_y you
// have a ordinary one pixel sized line.
// to do that stuff antialiased you just have to draw
// two pixels depending on the fraction of y.
// this is the fractional value that's normally
// thrown away.. we use it to do the antialiased
// blending.
float frac1 = y-floor(y);
float frac2 = 1.0f-frac1;
putpixel (pixel_x, pixel_y, frac2);
if (frac1)
putpixel (pixel_x, pixel_y+1, frac1)
}
}
putpixel gets an additional float value.. if this value is 1.0 the pixel should be drawed with 100% strength.. if 0% it should be transparent (so a little alphablend routine is nessesary for that).
This is the principle.. and i hope it's easy to understand-. I haven't tested the code - just wrote it down from memory, so there might be a bug here or there..
Anyways.. the priciple should be clear.. This code will - as said - only draw lines which start left and have a higher width than height.. You might want to change that code for different cases (e.g. line height > widht)..
For circles it works almost the same. just use a normal circle scanning algorithm, scale the coordinates and use the accuracy that's normally thrown away when converting to pixel-values as a alpha blend factor.
Hope it helps,
Nils
ASKER
I tried a bit adapting my algorithm to use your method of
float dydx = delta_y / delta_x;
for (int i=0; i<numPixels; i++)
{
// that's the current y-value
float y = start_y + dydx*(float)i;
...
but there is no way I could adapt it since I would absolutely have to use "dydx*(float)i", the main problem being that I do not use a simple loop with incremental counter but rather an optimized version of Rokne's optimized version of Wu's algorithm (yeah lot's of optimization).
The pattern selection (4 patterns actually) and decision (based on a simple calculation of the thickness % 2 to decide wether or not I need to draw a pattern of pixels or not based on the spread of a pattern of pixels (let's say with 5x5 I only need to draw 1 out of 3 pixels to get the pattern)) calculations makes so that I cannot use a simple counter on every pixel I draw.
What I tried up-to-date is to find a pattern of angles using both deltas to decide a pattern of pixels to draw. But I haven't found anything usefull yet.
Rich.
float dydx = delta_y / delta_x;
for (int i=0; i<numPixels; i++)
{
// that's the current y-value
float y = start_y + dydx*(float)i;
...
but there is no way I could adapt it since I would absolutely have to use "dydx*(float)i", the main problem being that I do not use a simple loop with incremental counter but rather an optimized version of Rokne's optimized version of Wu's algorithm (yeah lot's of optimization).
The pattern selection (4 patterns actually) and decision (based on a simple calculation of the thickness % 2 to decide wether or not I need to draw a pattern of pixels or not based on the spread of a pattern of pixels (let's say with 5x5 I only need to draw 1 out of 3 pixels to get the pattern)) calculations makes so that I cannot use a simple counter on every pixel I draw.
What I tried up-to-date is to find a pattern of angles using both deltas to decide a pattern of pixels to draw. But I haven't found anything usefull yet.
Rich.
Found this:
http://www.sanctuary.org/~ashe/coding/aaline.html
Wu's algorithm draws pairs of pixels straddling the line. Each pair of pixels is of opposing intensity/transparency, so that the center of intensity lies exactly on the line. We do this by keeping track of the error on the pixel in the direction of the slope, and altering the intensity to it linearly. This produces an excellent anti-aliasing effect on the line except for the endpoints, which could no doubt be calculated using the slower normalized distance technique. An potentially useful side-effect of the non-correctly antialiased endpoints is that two parallel line segments, joined end to end, are indistinguishable from a long line segment.
==========================
long x,y,xInc,yInc;
long dx,dy;
int swap;
dx = ( inLine->h2 - inLine->h1 );
dy = ( inLine->v2 - inLine->v1 );
if ( ABS( dx ) > ABS( dy ) )
{
if ( dx < 0 )
{
dx = -dx;
dy = -dy;
swap = inLine->v2;
inLine->v2 = inLine->v1;
inLine->v1 = swap;
swap = inLine->h2;
inLine->h2 = inLine->h1;
inLine->h1 = swap;
}
x = inLine->h1 << 16;
y = inLine->v1 << 16;
yInc = ( dy * 65536 ) / dx;
while ( ( x >> 16 ) < inLine->h2 )
{
SetCPixel( x >> 16,y >> 16,GrayColor( y & 0xFFFF ) );
SetCPixel( x >> 16,( y >> 16 ) + 1,GrayColor( ~y & 0xFFFF ) );
x += ( 1 << 16 );
y += yInc;
}
}
else
{
if ( dy < 0 )
{
dx = -dx;
dy = -dy;
swap = inLine->v2;
inLine->v2 = inLine->v1;
inLine->v1 = swap;
swap = inLine->h2;
inLine->h2 = inLine->h1;
inLine->h1 = swap;
}
x = inLine->h1 << 16;
y = inLine->v1 << 16;
xInc = ( dx * 65536 ) / dy;
while ( ( y >> 16 ) < inLine->v2 )
{
SetCPixel( x >> 16,y >> 16,GrayColor( x & 0xFFFF ) );
SetCPixel( ( x >> 16 ) + 1,( y >> 16 ),GrayColor( ~x & 0xFFFF ) );
x += xInc;
y += ( 1 << 16 );
}
}
==========================
Hope this is what you're after!
Best Regards
http://www.sanctuary.org/~ashe/coding/aaline.html
Wu's algorithm draws pairs of pixels straddling the line. Each pair of pixels is of opposing intensity/transparency, so that the center of intensity lies exactly on the line. We do this by keeping track of the error on the pixel in the direction of the slope, and altering the intensity to it linearly. This produces an excellent anti-aliasing effect on the line except for the endpoints, which could no doubt be calculated using the slower normalized distance technique. An potentially useful side-effect of the non-correctly antialiased endpoints is that two parallel line segments, joined end to end, are indistinguishable from a long line segment.
==========================
long x,y,xInc,yInc;
long dx,dy;
int swap;
dx = ( inLine->h2 - inLine->h1 );
dy = ( inLine->v2 - inLine->v1 );
if ( ABS( dx ) > ABS( dy ) )
{
if ( dx < 0 )
{
dx = -dx;
dy = -dy;
swap = inLine->v2;
inLine->v2 = inLine->v1;
inLine->v1 = swap;
swap = inLine->h2;
inLine->h2 = inLine->h1;
inLine->h1 = swap;
}
x = inLine->h1 << 16;
y = inLine->v1 << 16;
yInc = ( dy * 65536 ) / dx;
while ( ( x >> 16 ) < inLine->h2 )
{
SetCPixel( x >> 16,y >> 16,GrayColor( y & 0xFFFF ) );
SetCPixel( x >> 16,( y >> 16 ) + 1,GrayColor( ~y & 0xFFFF ) );
x += ( 1 << 16 );
y += yInc;
}
}
else
{
if ( dy < 0 )
{
dx = -dx;
dy = -dy;
swap = inLine->v2;
inLine->v2 = inLine->v1;
inLine->v1 = swap;
swap = inLine->h2;
inLine->h2 = inLine->h1;
inLine->h1 = swap;
}
x = inLine->h1 << 16;
y = inLine->v1 << 16;
xInc = ( dx * 65536 ) / dy;
while ( ( y >> 16 ) < inLine->v2 )
{
SetCPixel( x >> 16,y >> 16,GrayColor( x & 0xFFFF ) );
SetCPixel( ( x >> 16 ) + 1,( y >> 16 ),GrayColor( ~x & 0xFFFF ) );
x += xInc;
y += ( 1 << 16 );
}
}
==========================
Hope this is what you're after!
Best Regards
This may also help:
http://www.gamedev.net/reference/articles/article382.asp
This was written by none other than Michael Abrash... and accordingly, it kicks major butt!
http://www.gamedev.net/reference/articles/article382.asp
This was written by none other than Michael Abrash... and accordingly, it kicks major butt!
ASKER
I found the site yesterday (my boss actually) and am on my way to modify it accordingly. So far what I have found is that it's a pretty good algorithm but one that needs a bit help to work itself in it's present form.
Because unfortunately the present algorithm only works for black lines on white background as it processes shades of grey that ca only be applied for black on white.
I think that with certain modifications this is the algorithm that will win the race as long as I can resolve both the color probleme (with background blend) and a modifiable thickness (who needs only 1 pixel large lines anyway?).
Here is what I have so far that not only works for black on white but also (fortunately) for colors with equal RGB values (i.e only red: (255,0,0), only blue (0,0,255) or yellow (255,255,0), so as long as I don't have different values for one color (0,64,128) won't work correctly, giving me tints of green instead of pale navy blue).
void CPainter::DrawAaLine(CPt pOrigin, CPt pDest, COLORREF clrColor, bool bAntialiased)
{
long lPosX;
long lPosY;
long lIncX; // Increment for X
long lIncY; // Increment for Y
long lDeltaX;
long lDeltaY;
lDeltaX = pDest.x - pOrigin.x;
lDeltaY = pDest.y - pOrigin.y;
if(ABS(lDeltaX) > ABS(lDeltaY))
{
if(lDeltaX < 0)
{
lDeltaX = -lDeltaX;
lDeltaY = -lDeltaY;
SWAP(pDest.x, pOrigin.x);
SWAP(pDest.y, pOrigin.y);
}
lPosX = pOrigin.x << 16;
lPosY = pOrigin.y << 16;
lIncY = lDeltaY * 65536 / lDeltaX;
while(lPosX >> 16 < pDest.x)
{
byte Grey = (lPosY & 0xFF00) >> 8;
SetPixel(m_hdcBuffer, lPosX >> 16, lPosY >> 16, RGB(Grey,Grey,Grey) | clrColor);
SetPixel(m_hdcBuffer, lPosX >> 16, (lPosY >> 16) + 1, RGB(~Grey,~Grey,(~Grey)) | clrColor);
lPosX += 1 << 16;
lPosY += lIncY;
}
}
else
{
if (lDeltaY < 0 )
{
lDeltaX = -lDeltaX;
lDeltaY = -lDeltaY;
SWAP(pDest.x, pOrigin.x);
SWAP(pDest.y, pOrigin.y);
}
lPosX = pOrigin.x << 16;
lPosY = pOrigin.y << 16;
lIncX = lDeltaX * 65536 / lDeltaY;
while(lPosY >> 16 < pDest.y)
{
byte Grey = (lPosX & 0xFF00) >> 8;
SetPixel(m_hdcBuffer, lPosX >> 16, lPosY >> 16, RGB(Grey,Grey,Grey) | clrColor);
SetPixel(m_hdcBuffer, (lPosX >> 16) + 1, lPosY >> 16, RGB(~Grey,~Grey,~Grey) | clrColor);
lPosX += lIncX;
lPosY += 1 << 16;
}
}
}
And about the article I think it's pretty out-dated... (I think he mentionned something about new VGA display at 320x256...)
Rich.
Because unfortunately the present algorithm only works for black lines on white background as it processes shades of grey that ca only be applied for black on white.
I think that with certain modifications this is the algorithm that will win the race as long as I can resolve both the color probleme (with background blend) and a modifiable thickness (who needs only 1 pixel large lines anyway?).
Here is what I have so far that not only works for black on white but also (fortunately) for colors with equal RGB values (i.e only red: (255,0,0), only blue (0,0,255) or yellow (255,255,0), so as long as I don't have different values for one color (0,64,128) won't work correctly, giving me tints of green instead of pale navy blue).
void CPainter::DrawAaLine(CPt pOrigin, CPt pDest, COLORREF clrColor, bool bAntialiased)
{
long lPosX;
long lPosY;
long lIncX; // Increment for X
long lIncY; // Increment for Y
long lDeltaX;
long lDeltaY;
lDeltaX = pDest.x - pOrigin.x;
lDeltaY = pDest.y - pOrigin.y;
if(ABS(lDeltaX) > ABS(lDeltaY))
{
if(lDeltaX < 0)
{
lDeltaX = -lDeltaX;
lDeltaY = -lDeltaY;
SWAP(pDest.x, pOrigin.x);
SWAP(pDest.y, pOrigin.y);
}
lPosX = pOrigin.x << 16;
lPosY = pOrigin.y << 16;
lIncY = lDeltaY * 65536 / lDeltaX;
while(lPosX >> 16 < pDest.x)
{
byte Grey = (lPosY & 0xFF00) >> 8;
SetPixel(m_hdcBuffer, lPosX >> 16, lPosY >> 16, RGB(Grey,Grey,Grey) | clrColor);
SetPixel(m_hdcBuffer, lPosX >> 16, (lPosY >> 16) + 1, RGB(~Grey,~Grey,(~Grey)) | clrColor);
lPosX += 1 << 16;
lPosY += lIncY;
}
}
else
{
if (lDeltaY < 0 )
{
lDeltaX = -lDeltaX;
lDeltaY = -lDeltaY;
SWAP(pDest.x, pOrigin.x);
SWAP(pDest.y, pOrigin.y);
}
lPosX = pOrigin.x << 16;
lPosY = pOrigin.y << 16;
lIncX = lDeltaX * 65536 / lDeltaY;
while(lPosY >> 16 < pDest.y)
{
byte Grey = (lPosX & 0xFF00) >> 8;
SetPixel(m_hdcBuffer, lPosX >> 16, lPosY >> 16, RGB(Grey,Grey,Grey) | clrColor);
SetPixel(m_hdcBuffer, (lPosX >> 16) + 1, lPosY >> 16, RGB(~Grey,~Grey,~Grey) | clrColor);
lPosX += lIncX;
lPosY += 1 << 16;
}
}
}
And about the article I think it's pretty out-dated... (I think he mentionned something about new VGA display at 320x256...)
Rich.
> And about the article I think it's pretty out-dated...
> (I think he mentionned something about new VGA display
> at 320x256...)
Actually I think this demonstrates a certain advantage in judging the algorithm quality. At 320x200 or 320x240 etc., each pixel is clearly discernible as a small rectangle (hence the blockiness). Thus if you get half-decent antialiasing in this mode (this is, after all, what AA was developed for) then it's a safe bet that the results will look fantastic at 640x480 and above.
As for thick lines, a quick'n'dirty cheat here is to render the thick line as a polygon and just redraw the edges using your antialiasing algorithm above.
You mentioned earlier about the colour problem. Yes, it's a difficult problem to overcome. This is why the fullscreen antialiasing methods are so popular - they do not exhibit this difficulty as you're just averaging blocks of pixels. This is also why I regard the "object based" AA methods to be significantly slower: Whilst you will get quick results with Wu's algorithm for, say, white lines on a black screen, generalising it to work with any colours will slow it down inordinately as you'll probably have to calculate each polygon-to-polygon intersection and redefine the RGB values for the range of antialiased colours between the foreground and background. If your polygons are texture mapped, this'll be tougher still (I wouldn't want to go there).
One potentially quick(ish) solution may be to render each polygon to a memory buffer first so that you can quickly read the colour of background pixels. However, this is a bit pointless - you may as well do FSAA in this case, and I get the impression that this is not an option to you.
What screen mode are you working in (ie. how many colours do you have available)? If you are limited to, say, a 256 colour palette then this will be difficult. You're getting into the realms of working in colour spaces and alpha blending which is really beyond the scope of the original question. I don't know what facilities Photoshop provides you with to assist in this.
> ... and would need a starter to get me the basics maths
> behind it.
Most of these routines are based on differential calculus - dealing with small increments of change (1st order), the change in change (2nd order) and so on. A decent maths text should give you the introduction you need.
BTW You're absolutely right, I was thinking of the Gupta-Sproull algorithm. I need a RAM upgrade :-P
Regards
> (I think he mentionned something about new VGA display
> at 320x256...)
Actually I think this demonstrates a certain advantage in judging the algorithm quality. At 320x200 or 320x240 etc., each pixel is clearly discernible as a small rectangle (hence the blockiness). Thus if you get half-decent antialiasing in this mode (this is, after all, what AA was developed for) then it's a safe bet that the results will look fantastic at 640x480 and above.
As for thick lines, a quick'n'dirty cheat here is to render the thick line as a polygon and just redraw the edges using your antialiasing algorithm above.
You mentioned earlier about the colour problem. Yes, it's a difficult problem to overcome. This is why the fullscreen antialiasing methods are so popular - they do not exhibit this difficulty as you're just averaging blocks of pixels. This is also why I regard the "object based" AA methods to be significantly slower: Whilst you will get quick results with Wu's algorithm for, say, white lines on a black screen, generalising it to work with any colours will slow it down inordinately as you'll probably have to calculate each polygon-to-polygon intersection and redefine the RGB values for the range of antialiased colours between the foreground and background. If your polygons are texture mapped, this'll be tougher still (I wouldn't want to go there).
One potentially quick(ish) solution may be to render each polygon to a memory buffer first so that you can quickly read the colour of background pixels. However, this is a bit pointless - you may as well do FSAA in this case, and I get the impression that this is not an option to you.
What screen mode are you working in (ie. how many colours do you have available)? If you are limited to, say, a 256 colour palette then this will be difficult. You're getting into the realms of working in colour spaces and alpha blending which is really beyond the scope of the original question. I don't know what facilities Photoshop provides you with to assist in this.
> ... and would need a starter to get me the basics maths
> behind it.
Most of these routines are based on differential calculus - dealing with small increments of change (1st order), the change in change (2nd order) and so on. A decent maths text should give you the introduction you need.
BTW You're absolutely right, I was thinking of the Gupta-Sproull algorithm. I need a RAM upgrade :-P
Regards
ASKER
My boss brought me Micheal Abrash's "Graphics Programming Black Book" which contains the article mentionned at http://www.gamedev.net/reference/articles/article382.asp by with figures and sample code.
However his algorithm, as the one found at http://www.sanctuary.org/~ashe/coding/aaline.html (and the one that seems to best fit the needs of the problem), still is of use only for black or pure colors (red, green, blue) on white background.
It did prove a good source of information though as it does explain bits of information missing at some places I found.
The best way I found was actually to apply the most important principle that I have found in anti-aliasing : A total intensity of 1 for every pair of pixels drawn (applied to 1-pixel width line, but that must be modified for thicker lines... still the same).
100% (intensity of 1) would mean 255 in RGB value for every color. So this is the best result I have found so far :
SetPixel(m_hdcBuffer, lPosX >> 16, lPosY >> 16, RGB(iRed | Grey, iGreen | Grey, iBlue | Grey));
SetPixel(m_hdcBuffer, lPosX >> 16, (lPosY >> 16) + 1, RGB(iRed | ( 255 - Grey), iGreen | (255 - Grey), iBlue | (255 - Grey)));
(iRed, iGreen and iBlue are only separate RGB values I get from my base color)
But it still misses the track by a tiny bit (I think I got hold of something... but I'm not sure) and it still doesn't handle different background colors. It's still closer to the solution.
The screen modes I would be the most likely to encounter would be 1024x768 at True color (32 bit).
And I think I see what you mean about thick lines. I will try it.
Rich.
However his algorithm, as the one found at http://www.sanctuary.org/~ashe/coding/aaline.html (and the one that seems to best fit the needs of the problem), still is of use only for black or pure colors (red, green, blue) on white background.
It did prove a good source of information though as it does explain bits of information missing at some places I found.
The best way I found was actually to apply the most important principle that I have found in anti-aliasing : A total intensity of 1 for every pair of pixels drawn (applied to 1-pixel width line, but that must be modified for thicker lines... still the same).
100% (intensity of 1) would mean 255 in RGB value for every color. So this is the best result I have found so far :
SetPixel(m_hdcBuffer, lPosX >> 16, lPosY >> 16, RGB(iRed | Grey, iGreen | Grey, iBlue | Grey));
SetPixel(m_hdcBuffer, lPosX >> 16, (lPosY >> 16) + 1, RGB(iRed | ( 255 - Grey), iGreen | (255 - Grey), iBlue | (255 - Grey)));
(iRed, iGreen and iBlue are only separate RGB values I get from my base color)
But it still misses the track by a tiny bit (I think I got hold of something... but I'm not sure) and it still doesn't handle different background colors. It's still closer to the solution.
The screen modes I would be the most likely to encounter would be 1024x768 at True color (32 bit).
And I think I see what you mean about thick lines. I will try it.
Rich.
ASKER
And I just realized there is no way this :
SetPixel(m_hdcBuffer, lPosX >> 16, lPosY >> 16, RGB(iRed | Grey, iGreen | Grey, iBlue | Grey));
SetPixel(m_hdcBuffer, lPosX >> 16, (lPosY >> 16) + 1, RGB(iRed | ( 255 - Grey), iGreen | (255 -
Grey), iBlue | (255 - Grey)));
would work...
64: 0100 0000
| 137: 1000 1001
= 1100 1001
128: 1000 0000
| 137: 1000 1001
= 1000 1001
64 gives an higher value than 128...
So using or's on bits can't work.
Oh well...
Rich.
SetPixel(m_hdcBuffer, lPosX >> 16, lPosY >> 16, RGB(iRed | Grey, iGreen | Grey, iBlue | Grey));
SetPixel(m_hdcBuffer, lPosX >> 16, (lPosY >> 16) + 1, RGB(iRed | ( 255 - Grey), iGreen | (255 -
Grey), iBlue | (255 - Grey)));
would work...
64: 0100 0000
| 137: 1000 1001
= 1100 1001
128: 1000 0000
| 137: 1000 1001
= 1000 1001
64 gives an higher value than 128...
So using or's on bits can't work.
Oh well...
Rich.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Right now I get near-photoshop anti-aliasing on a white background. I just have to do a few adjustments to keep in mind the background color and I will try, as you said, bitwise OR with the background, with a few adjustments if needed. Plus line thickness, but that is just a few tweaks.
So with all this information I'm on my way to success!
Thanks a lot!
You were a life saver!
Rich.
So with all this information I'm on my way to success!
Thanks a lot!
You were a life saver!
Rich.
ASKER
Think I said everything I had in mind...
Thank you - that's very kind. Please bear in mind that the method above was improvised & will probably need considerable modification though.
Good luck, and enjoy!
Good luck, and enjoy!