抗锯齿：Wu 算法
生成平滑的抗锯齿线；包含动画的示例代码
目录
引言
锯齿线是在栅格图形中实现专业显示的主要障碍。抗锯齿可以产生非常平滑的线条并提供时尚的外观。您一定已经观察到 PowerPoint 2003 中漂亮的抗锯齿图表。它们看起来非常平滑。虽然 GDI+ 提供了抗锯齿，但大多数计算机可能没有其可再发行组件。使用 .NET，您可以获得抗锯齿，但同样，大多数计算机可能没有可用的 .NET 框架。因此，我更喜欢在 VC++ 6 中编写“Windows 便携式”程序。因此，这里有一个 MFC 版本的 Wu 抗锯齿算法。
背景
研究导致了多种抗锯齿技术的出现。像 Foley、Van Dam 这样的图形教科书讨论了 Gupta-Sproul 和相关的算法。为了快速抗锯齿，Xiaolin Wu 发明了一种以他的名字命名的算法：Wu 抗锯齿。 Michael Abrash 的图形编程黑皮书 对该算法进行了出色的处理。 Hugo Elias 也有一篇关于此事的精彩文章；我强烈建议阅读这一篇。但是，两者都没有 MFC 可用的代码，因此我在 MFC 上实现了他们的代码。
我编写了一个简单的 WuCircle 例程来生成一个由线段组成的圆。现在让我们看看通过使用这个实现我们取得了什么不同。图 2 显示了上述辐条的放大视图。左侧的图像显示了正常的绘图。锯齿边缘在其中清晰可见。右侧的图像是抗锯齿绘图，我们可以看到使用“灰度”强度实现的平滑效果。
Using the Code
您可以重用函数 DrawWuLine。只需在需要绘制抗锯齿线的地方调用它即可。
void DrawWuLine (CDC *pDC, short X0, short Y0, short X1, short Y1,
short BaseColor, short NumLevels, unsigned short IntensityBits);
/*
Arguments:
+ pDC is where line is drawn. Can be memory device context.
+ (X0,Y0) is start point of line.
+ (X1, Y1) is end point of line.
+ BaseColor is intensity of line. Pass 0 for black line.
+ NumLevels is number of gray scale levels. Pass 256.
+ IntensityBits denotes bits used to represent color component. Pass 8.
Note: NumLevels and IntensityBits have
been preserved from Michael Abrash's implementation.
They come very handy in customizing drawing
algorithm on different graphics hardware.
You may hardcode them.
*/
有一个简单的圆生成例程，您可以重用。在内部，它调用上面解释的线条例程。
void DrawWuCirlce (CDC * pDC, int x, int y, int r);
/*
Arguments:
+ pDC is where circle is drawn. Can be memory device context.
+ (x,y) is center of circle.
+ r is radius of circle.
*/
可以轻松修改这两个函数以使用 HDC 而不是 CDC *，如果您正在编写非 MFC Win32 应用程序。
演示：辐条动画
此应用程序使用“普通” GDI（非抗锯齿）和抗锯齿线条例程生成一些辐条和同心圆。您可以按“a”键来切换动画。动画轮子清楚地显示了抗锯齿和普通线条绘图之间的区别。
RotorThread 是一个为辐条轮子制作动画的例程。它使用内存位图和设备上下文。以大约 20 fps（每秒帧数）的速度，它在内存位图上旋转轮子。使用 BitBlt，将图形显示在主窗口上。
再次按“a”会终止线程。
UINT RotorThread (LPVOID lpVoid)
{
bool * pbStop = (bool *) lpVoid;
CWnd * pWnd = AfxGetMainWnd();
CDC * pDC = pWnd->GetDC();
CRect rect;
pWnd->GetClientRect (&rect);
CDC memDC;
memDC.CreateCompatibleDC (pDC);
CBitmap bitmap;
bitmap.CreateCompatibleBitmap (pDC,
rect.Width(), rect.Height());
memDC.SelectObject (&bitmap);
CFont font;
font.CreatePointFont (185, "Verdana", &memDC);
memDC.SelectObject (&font);
memDC.SetTextAlign (TA_CENTER);
float phase = 0.0f;
while (!(*pbStop))
{
//1. Erase Background.
memDC.Rectangle (0, 0, rect.Width(), rect.Height());
//2. Draw new contents.
memDC.TextOut (100, 15, "Normal");
memDC.TextOut (350, 15, "Anti-aliased");
short x, y;
for (float theta= phase; theta<
360+phase; theta += 10 )
{
x = (short)(100.0*cos(theta*3.14/180.0)+355.0);
y = (short)(-100.0*sin(theta*3.14/180.0)+155.0);
DrawWuLine (&memDC,x, y, 355, 155, 0, 256, 8);
memDC.MoveTo (x-240,y);
memDC.LineTo (115,155);
}
//3. Blit drawing on screen.
pDC->BitBlt (0, 0, rect.Width(), rect.Height(),
&memDC, 0, 0, SRCCOPY);
//4. Update animation parameter.
phase += 1;
::Sleep (67); //15 fps.
}
font.DeleteObject();
bitmap.DeleteObject();
memDC.DeleteDC();
pWnd->ReleaseDC (pDC);
return 0;
}
DrawWuLine 函数
这是 DrawWuLine 函数的实现
void DrawWuLine (CDC *pDC, short X0, short Y0, short X1, short Y1,
short BaseColor, short NumLevels, unsigned short IntensityBits)
{
unsigned short IntensityShift, ErrorAdj, ErrorAcc;
unsigned short ErrorAccTemp, Weighting, WeightingComplementMask;
short DeltaX, DeltaY, Temp, XDir;
/* Make sure the line runs top to bottom */
if (Y0 > Y1) {
Temp = Y0; Y0 = Y1; Y1 = Temp;
Temp = X0; X0 = X1; X1 = Temp;
}
/* Draw the initial pixel, which is always exactly intersected by
the line and so needs no weighting */
DrawPixel(pDC,X0, Y0, BaseColor);
if ((DeltaX = X1 - X0) >= 0) {
XDir = 1;
} else {
XDir = -1;
DeltaX = -DeltaX; /* make DeltaX positive */
}
/* Special-case horizontal, vertical, and diagonal lines, which
require no weighting because they go right through the center of
every pixel */
if ((DeltaY = Y1 - Y0) == 0) {
/* Horizontal line */
while (DeltaX-- != 0) {
X0 += XDir;
DrawPixel(pDC,X0, Y0, BaseColor);
}
return;
}
if (DeltaX == 0) {
/* Vertical line */
do {
Y0++;
DrawPixel(pDC,X0, Y0, BaseColor);
} while (--DeltaY != 0);
return;
}
if (DeltaX == DeltaY) {
/* Diagonal line */
do {
X0 += XDir;
Y0++;
DrawPixel(pDC,X0, Y0, BaseColor);
} while (--DeltaY != 0);
return;
}
/* Line is not horizontal, diagonal, or vertical */
ErrorAcc = 0; /* initialize the line error accumulator to 0 */
/* # of bits by which to shift ErrorAcc to get intensity level */
IntensityShift = 16 - IntensityBits;
/* Mask used to flip all bits in an intensity weighting, producing the
result (1 - intensity weighting) */
WeightingComplementMask = NumLevels - 1;
/* Is this an X-major or Y-major line? */
if (DeltaY > DeltaX) {
/* Y-major line; calculate 16-bit fixed-point fractional part of a
pixel that X advances each time Y advances 1 pixel, truncating the
result so that we won't overrun the endpoint along the X axis */
ErrorAdj = ((unsigned long) DeltaX << 16) / (unsigned long) DeltaY;
/* Draw all pixels other than the first and last */
while (--DeltaY) {
ErrorAccTemp = ErrorAcc; /* remember current accumulated error */
ErrorAcc += ErrorAdj; /* calculate error for next pixel */
if (ErrorAcc <= ErrorAccTemp) {
/* The error accumulator turned over, so advance the X coord */
X0 += XDir;
}
Y0++; /* Y-major, so always advance Y */
/* The IntensityBits most significant bits of ErrorAcc give us the
intensity weighting for this pixel, and the complement of the
weighting for the paired pixel */
Weighting = ErrorAcc >> IntensityShift;
DrawPixel(pDC,X0, Y0, BaseColor + Weighting);
DrawPixel(pDC,X0 + XDir, Y0,
BaseColor + (Weighting ^ WeightingComplementMask));
}
/* Draw the final pixel, which is
always exactly intersected by the line
and so needs no weighting */
DrawPixel(pDC,X1, Y1, BaseColor);
return;
}
/* It's an X-major line; calculate 16-bit fixed-point fractional part of a
pixel that Y advances each time X advances 1 pixel, truncating the
result to avoid overrunning the endpoint along the X axis */
ErrorAdj = ((unsigned long) DeltaY << 16) / (unsigned long) DeltaX;
/* Draw all pixels other than the first and last */
while (--DeltaX) {
ErrorAccTemp = ErrorAcc; /* remember current accumulated error */
ErrorAcc += ErrorAdj; /* calculate error for next pixel */
if (ErrorAcc <= ErrorAccTemp) {
/* The error accumulator turned over, so advance the Y coord */
Y0++;
}
X0 += XDir; /* X-major, so always advance X */
/* The IntensityBits most significant bits of ErrorAcc give us the
intensity weighting for this pixel, and the complement of the
weighting for the paired pixel */
Weighting = ErrorAcc >> IntensityShift;
DrawPixel(pDC,X0, Y0, BaseColor + Weighting);
DrawPixel(pDC,X0, Y0 + 1,
BaseColor + (Weighting ^ WeightingComplementMask));
}
/* Draw the final pixel, which is always exactly intersected by the line
and so needs no weighting */
DrawPixel(pDC,X1, Y1, BaseColor);
}
WuLine 的彩色版本
我希望这对您的一些应用程序有所帮助。
资源
好的参考资料
致谢
Eien 发布了该算法的彩色版本，我原本计划将其作为下一期，为了简单起见。 :) 谢谢你，Eien！
更新
此处的整个代码已托管在 Google Code 上，以启用开源开发。请随时加入该开发小组并为其做出贡献。目前，FLTK 项目正在使用这项工作。
欢迎您提出意见和建议。只需在此处发布即可。
历史
- 2006 年 3 月 8 日 -- 发布原始版本
- 2006 年 3 月 10 日 -- 文章已移动
- 2007 年 11 月 6 日 -- 文章内容已更新