计算机图形学

第三章输出图元

用于图形应用的通常软件包括计算机图形应用编程接口（CG API），它提供可以在C++等程序设计语言中用来创建图形的函数库。如2.8节所提出的，函数库可以分成几种类型。创建图形时最先要做的一件事就是要描述显示场景的组成部分。图形的组成部分可以是树木和地形、家具和墙壁、商店铺面和街景、汽车和广告牌、原子和分子或者星星和银河等。对于每一类场景，要描述每一对象的结构及其在场景中的坐标位置。图形软件包中用来描述各种图形元素的函数称为图形输出原语（graphics output primitive），或简称为图元（primitive）。描述对象几何要素的输出图元一般称为几何图元。点的定位和直线段是最简单的几何图元。图形软件包中包含的其他几何图元有圆和其他二次曲线、二次曲面、样条曲线和曲面及多边形填色区域。多数图形系统还提供显示字符串的某些函数。在选定的坐标系中指定一个图形的几何要素后，输出图元投影到该输出设备显示区域对应的二维平面上，并扫描转换到帧缓存的整数像素位置。

本章将介绍OpenGl中的输出图元并讨论实现输出图元的设备级算法。对图形库实现算法的探讨将使我们了解这些图形软件包的功能，并且可以理解这些函数是如何工作的，也许会发现如何改进它们，以及如何自行为某特定应用实现图形函数。计算机图形学方面的研究不断地为特定应用（如因特网图形等）发现新的和改进的技术，并且开发更快、更逼真的通用图形显示方法。

3.1 坐标系统

为了描述图形，必须首先确定一个称为世界坐标系的合适的二维或三维笛卡尔坐标系。接着通过给出世界坐标系中的位置等几何描述来定义图形中的对象。例如，通过两个端点定义一条直线段，通过一组顶点位置定义一个多边形。这些坐标位置与该的对象的颜色、坐标范围（coordinate extent）即对象的坐标x、y、z最小、最大值等其他信息一起存储在场景描述中。坐标范围也称为对象的包围盒(bounding box)。对于二维图形来说，坐标范围也称为对象的包围矩形（bounding rectangle）。通过将场景信息传送给观察函数、由观察函数识别可见面、将对象映射到视频监视器上来实现对象的显示。扫描转换过程将颜色值乖场景信息保存到帧缓存的相应位置，从而在输出设备上显示场景中的对象。

3.1.1 屏幕坐标

视频监视器上的位置使用与帧缓存中的像素位置相对应的整数屏幕坐标（screen coordinate）进行描述。像素的坐标值给出扫描行号（y值）和列号（扫描行的x值）。屏幕刷新等硬件

处理一般从屏幕的左上角开始对像素进行编址。从屏幕最上面的0行到屏幕最下面的某整数值ymax行对扫描行进行编号，每一行像素位置从左到右，从0到xmax进行编号。但是，使用软件命令可以按照任何方式设定屏幕位置的参考系统。例如，我们可以设定屏幕区域左下角为原点，用整数坐标（参见图3.1）或非整数笛卡尔坐标来描述图形。描述场景几何要素的坐标值由观察转换为帧缓存中的整数像素位置。

图元的扫描转换算法使用定义的坐标来确定要显示像素的位置。例如，给定一直线段的两个端点，其显示函数必须计算出两端点间位于线段上所有像素的位置。由于一个像素占用屏幕上的一个有限范围，因此，实现算法必须考虑像素的有限大小。目前，我们假设每一个整数屏幕位置代表区域的中心。

一旦确定了一个像素的像素位置，必须将合适的颜色值存入帧缓存。为此，我们要使用一个底层函数setPixel(x,y);

该函数将当前颜色设定值存入帧缓存的整数坐标位置(x,y)处，该位置相对于屏幕坐标原点而选定，有时我们也希望获得一个像素位置的当前帧缓存设置。这可使用下列底层函数来获得。

getPixel(x,y,color);

在这一函数中，参数color得到一个与存储在位置(x,y)的像素中的RGB组合相对应的整数值。

对于二维图形来说，仅需要在（x,y）位置指定颜色值；但是对于三维图形来说，还需要其他的屏幕坐标信息。这时，屏幕坐标按三维值来存储，第三维表示对象位置相对于观察位置的深度。在二维场景中，深度值均为0。

3.1.2 绝对和相对坐标描述

到目前为止，我们讨论的坐标均为绝对坐标（absolute coordinate）值。这表示的值是所在坐标中的实际位置。

然而，有些图形软件还允许使用相对坐标(relative coordinate)来描述位置。该方法在许多图形应用中很有用，比如用笔式绘图仪、艺术家绘画系统进行绘图及出版和印刷应用的图形软件包。使用这一方法，我们可以使用从离开最后一次引用位置（称为当前位置，current position）的位移量来指定坐标位置。例如，如果位置（3，8）是应用程序刚刚引用的位置，则相对坐标描述（2，-1）与绝对坐标（5，7）相对应。有一个函数专门用来在指定任何图元坐标前设定当前位置。在描述一串首发相连的直线段场景时，我们可以在建立开始位置后仅给出一串相对坐标（位移）。图形系统中会给出指定定位中使用相对坐标还是绝对坐标的选项。在此后的讨论中，除非特别声明，我们假定都使用绝对坐标。

3.1.3 OpenGl中指定二维世界坐标系统

第一个示例程序介绍了gluOrto2D命令，我们可以利用该命令设定一个二维笛卡尔坐标系。该函数的变量是指定图形x和y坐标范围的四个值。由于gluOrtho2D函数指定正交投影，因此我们也要确定坐标值放进了OpenGl投影矩阵中。此外，我们只可以将世界坐标范围设定前的投影矩阵定义为一个单位矩阵。这样可保证坐标值不会受以前设置的投影矩阵的影响。因此，对于最初的二维例子，我们可以通过下列语句定义屏幕显示窗口的坐标系统。

glMatrixMode(GL_PROJECTION);

glLoadIdentity();

gluOrtho2D(xmin,xmax,ymin,ymax);

如图3.2，显示窗口将被指定为其左下角位于坐标(xmin,ymin处)，右上角位于坐标（xmax,ymax）处。

我们随后可使用gluOrtho2D语句描述的坐标系来指定一个或多个要显示的图元。如果一个图元的坐标范围完全在显示窗口的坐标范围内，则该图元将完整地显示出来。否则，仅仅在显示窗口坐标范围内的图元部分被显示。同样，在建立图形的几何描述时，所有OpenGl图元的位置和gluOrtho2D函数宝岛的坐标系统中的绝对坐标给出。

3.1.4 OpenGL画点函数

要描述一个点的几何要素，我们只需要在世界坐标系中指定一个位置。然后该坐标位置和场景中已有的其他几何描述在一起传递给观察函数。除非指定其他属性值，OpenGl图元按默认的大小和颜色来显示。默认的图元颜色为白色，而默认的点的大小等于一个屏幕像素的大小。

使用下面的OpenGL函数可指定一个点位置的坐标值。

glVertex*()

这里的星号*表示该函数要有后缀码。这些后缀码用来指明空间尺寸、用做坐标值的数据类型和可能的向量形式坐标描述。在glBegin函数和glEnd函数之间必须有一个glVertex函数。glBegin函数的变量用来指定要显示的输出图元的类型，而glEnd函数没有变量。对于点的绘制，glBegin函数的变量是符号常量GL_POINTS。因此，一个点位置的OpenGL描述形式是：

glBegin(GL_POIONTS);

glVertex*();

glEnd();

尽管术语顶点（vertex）严格地代表一个多边形的角点、一个角两边的交点、椭圆和其主轴的交点或几何结构中其他类似的坐标位置，OpenGL中的glVertex函数可用于描述任意一点的位置。这样，使用一个简单的函数来描述点、线段和多边形，而更多地使用多边形面来描述场景对象。

OpenGL中的坐标位置可以是二维、三维和四维。glVertex的后缀为2、3、4表示其坐标位置的维数。四维描述意味着齐次坐标（hiomogeneous-coordinate）表示，其中的齐次参数h(第四维坐标)是笛卡尔坐标值的比例因子。齐次坐标表示利用矩阵形式表达变换操作很有用，由于OpenGL将二维作为三维的特殊情况来处理，任意(x,y)坐标描述等同于h=1时的(x,y,0)。

我们需要指出的是坐标的数值描述中使用什么数据结构。这由glVertex()函数的第二个后缀来完成。用于指定数值数据类型的后缀是i、s、f和d。最后，glVertex中可以使用显式地坐标值或引入矩阵形式坐标位置的单个变量。如果使用矩阵形式坐标位置，则需要第三个后缀码v（向量）.

在下面的例子中，在斜率为2的直线上绘出了三个等距离的点。

glBegin(GL_POINTS);

glVertex2i(25,50);

glVertex2i(50,100);

glVertex2i(75,150);

glVertex2i(100,200);

glEnd();

换一种方法：我们可以将前面这些点的坐标值以矩阵形式描述：

int point1[]={25,50};

int point2[]={50,100};

int point3[]={75,150};

int point4[]={100,200};

且调用OpenGL函数来给出这三个点：

glBegin(GL_POINTS);

glVertex2iv(point1);

glVertex2iv(point2);

glVertex2iv(point3);

glVertex2iv(point4);

glEnd();

glFlush();

下面是在三维坐标系中描述两个点位置的例子。这里按显式浮点数的方式给出坐标。

glVertex3f(78.05,100.72,14.60);

glVertex3f(146.91,20.00,88.30);

我们还可以为各种维数中描述的点位置的定义C++类或结构（struct），例如：

Class wcPt2D{

Public:

GLFloatx,y;

}

有了这一类定义，我们可以使用下列语句描述一个二维世界的坐标点位置：

wcPt2D pointPos;

pointPos.x=120.75;

pointPos.y=45.30;

glBegin(GL_POINTS);

glVertex2f(points.x,poinPos.y);

glEnd();

然后我们可以使用C++过程中使用OpenGL画点函数来实现setPixel命令。

直线、圆和椭圆是二维场景中的基本图形。尽管MFC的CDC类已经提供了相关的绘制函数，

但是直接使用这些函数仍然无法满足真实感图形绘制的要求。例如对基本图形进行反走样处理，绘制颜色光滑过渡的直线段等。光栅扫描显示器是画点设备，基本图形的光栅化就是在像素点阵中确定最佳逼近于理想图形的像素点集，并用指定的颜色显示这些像素点集的过程。当光栅化与按扫描线顺序绘制图形的过程结合在一起时，也称为扫描转换。本章从基本图形的生成原理出发，使用绘制像素点函数实现基本图形的扫描转换。

COLORREF SetPixel(intx,inty,COLORREFcrColor)

COLORREF SetPixel(POINT point,COLORREFcrColor)

BOOL setPixelV(intx,inty,COLORREFcrColor)

BOOL SetPixelV(intx,inty,COLORREFcrColor)

上述函数是将设备坐标系为(x,y)或point像素点设置为指定的crColor颜色i.SetPixelV函数不需要返回实际像素点的RGB值。执行速度比SetPixel()快得多。以后主要使用SetPixelV()函数绘制像素点。这里请注意设备坐标(x,y)或point只能取整数值和，而理想逻辑坐标一般为双精度值，扫描转换时需要进行四舍五入处理。对双精度数值的调整，本书采用以下宏定义#define ROUND(x) int(x+0.5)

3.3 直线的扫描转换

直线的扫描转换是在屏幕像素点阵中确定最佳逼近于理想直线的像素点集的过程。连续理想直线段扫描转换的结果是离散的像素点。从图中可以看到，黑色像素点都是距离直线最近的像素点。计算机图形学要求直线的绘制速度要快，即尽量使用加减法，避免乘、除、开方、三角等复杂运算。有许多算法可以实现直线的扫描转换，如数值微分法（digital differential analyzer,DDA）、逐点比较法等，其中最著名的算法是Bresenham于1965年提出的Bresenham 算法。在一个迭代算法中，如果第一步的x、y值是用前一步的值加上一个增量来获得的。那么，这种算法就称为增量算法。Bresenham算法就是一个经典的增量算法，利用前一个像素的信息来计算当前像素的位置。Bresenham算法有几种变体，计算方法略有不同。这里重点介绍中点Bresenham算法（midpoint bresenham algorithm）。对于直线中点，中点Bresenham 算法与Bresenham算法产生同样的像素点，而且还可以扩展为更复杂的图形扫描转换算法。如圆的中点Bresenham算法和椭圆中点Bresenham算法。

3.3.1 算法原理

直线的中点Bresenham算法的原理：每次在主位移方向上走一步，另一个方向上走不走步取决于中点误差项的值。

给定理想直线的起点坐标为P0(x0,y0)，终点坐标为P1(x1,y1)，则直线的隐函数方程为

F(x,y):kx+y+b=0;其中直线斜率k=dy/dx，△x=x1-x0为直线水平方向位移，△y=y1-y0为直线垂

直方向位移，b是直线在y轴上的截距。

理想直线将平面划分为3个区域：对于直线上的点，F(x,y)=0，对于直线上方的点（F(x,y)>0，对于直线下方的点，F(x,y)<0。假设理想直线的斜率为0<=k<=1，则△x>=△y,所以取x方向为主位移方向。按照中点Bresenham原理，x方向上每次加1，y方向上加不加1取决于中点误差项的值。

假定直线的当前点为Pi(xi,yi)，沿主位移x方向上走一步，下一点只能在Pu(x+1,y+1)和Pd(x+1，y)两点中选取。Pu和pd的中点为M(x+1,y+0.5)，如图所示，显然，若中点M在理想直线的下方，则pu点距离直线近，选取pu，否则选取pd。

3.3.2 构造中点误差项

从Pi(xi,yi)的出发点取下一像素时，需要将pu和pd的中点M（xi+1,yi+0.5）代入隐函数方程，构造中点误差项di:

Di=F(xi+1,yi+0.5)=yi+0.5-k(xi+1)-b=0.5-kxi

当di<0时，中点M在直线的下方，pu点离直线距离近，下一个像素点应选取pu，取y方向上走一步，当di>0时，中点M在直线的上方，pd点离直线距离近，下一像素点应选取pd，即y方向不走步；当di=0时，中点M在直线上，pu、pd与直线的距离相等，选取pu 和pd均可，约定取pd。因此：

If(di<0)

Yi+1=yi+1;

Else if(di>=0)

Yi+1=yi;

为了能够继续选取直线上的后续像素，需要给出中点误差项的递推公式与初始值。

在主位移x方向上已走一步的情况下，现在考虑沿主位移方向再走一步，应该选择哪个中点代入中点误差项以判断下一步要选取的像素，如图所示。

当di<0时，下一步进行判断的中点坐标为M（xi+2,yi+1.5）。下一步中点误差项为

Di+1=F(xi+2,yi+1.5)=yi+1.5-k(xi+2)-b=1.5-2k=di+1-k

当di>=0时，下一步进行判断的中点坐标为m(xi+2,yi+0.5)。下一步中点误差项为：

Di+1=di-k

3.3.3 直线的扫描转换的实现

1．案例描述

使用中点Breseham算法绘制斜率为0<=k<=1的直线。

2.案例效果图

二、算法设计

1）输入直线的起点坐标P0(x0,y0)和终点坐标P1(x1,y1)

2) 定义直线当前坐标x和y，定义中点偏差差别式d，定义直线斜率k，定义像素点颜色rgb。3）x=x0,y=y0，计算d=0.5-k，k=(y1-y)/(x1-x)，rgb=RGB(0,0,255)

4) 绘制点（x,y），判断d的符号。若d<0，则x更新为(x+1,y+1)，d更新为d+1-k，否则（x,y）更新为（x+1,y），d更新为d-k。

5）如果当前点x小于点x1，重复步骤4，否则结束。

void CBresenhamLineView::DrawLine()

{

CClientDC dc(this);

COLORREF rgb=RGB(0,255,0);

double x,y,delta,slope;

x=m_x0;

y=m_y0;

slope=(m_y1-m_y0)/(m_x1-m_x0);

delta=0.5-slope;

for(x=m_x0;x<=m_x1;x++)

{

dc.SetPixel(ROUND(x),ROUND(y),rgb);

if(delta<0)

{

y++;

delta+=1-slope;

}else{

delta-=slope;

}

}

}

// CBresenhamLineView消息处理程序

void CBresenhamLineView::OnMenuDrawLine()

{

// TODO: 在此添加命令处理程序代码

CInputDialog dlg;

if(IDOK==dlg.DoModal())

{

m_x0=dlg.m_x0;

m_x1=dlg.m_x1;

m_y0=dlg.m_y0;

m_y1=dlg.m_y1;

}

AfxGetMainWnd()->SetWindowTextW(_T("基本图形扫描转换:)"));

RedrawWindow();

DrawLine();

}

3.4 圆的扫描转换

圆的扫描转换是在屏幕像素点阵中确定最佳逼近于圆的像素点集的过程。圆的绘制可以使用

简单方向画圆算法或极坐标画圆算法，但这些算法涉及开方运算或三角运算，效率很低。本节主要讲解仅包含加减运算的顺时针1/8圆弧中点Bresenham算法原理。根据对称性可以绘制整圆。

3.4.1 算法原理

圆心在原点，半径为R的圆方程的隐函数表达式为：

F(x,y):X^2+y^2-R^2=0

圆将平面划分成三个区域，对于圆上的点F(x,y)=0,对于圆外的点F(x,y)>0，对于圆内的点F(x,y)<0。

根据圆的对称性，可以用4条对称轴x=0,y=0,x=y,x=-y将圆分成八等分，如图所示，只要绘制出第一象限的1/8圆弧，根据对称性就可以绘制出整圆，这称为八分法画圆算法。假定第一象限的任意点为p（x,y），可以顺时针确定其它7个点。

首先考虑扫描转换图，此时Bresenham算法要从（0，R）到（R/2,R/sqrt(2)）顺时针确定最佳逼近于该段圆弧的像素点集。因为△x>=△y，所以x方向为主方向，因此中点Bresenham 算法的原理简化如下：x方向上每次加1，y方向上减不减1取决于中点误差项的值。

假定圆弧的当前点为Pi(xi,yi)，沿主位移x方向上走一步，下一点只能在Pu(x+1,y)和Pd(x+1，y-1)两点中选取。Pu和pd的中点为M(x+1,y-0.5)，如图所示，显然，若中点M在理想圆弧的下方，则pu点距离圆弧近，选取pu，否则选取pd。

3.4.2 构造中点误差项

从Pi(xi,yi)的出发点取下一像素时，需要将pu和pd的中点M（xi+1,yi+0.5）代入隐函数方程，构造中点误差项di:

Di=F(xi+1,yi-0.5)=（xi+1）^2+(yi-0.5)^2-R^2=2*xi+yi+1.25

当di<0时，中点M在圆内，pu点离圆弧距离近，下一个像素点应选取pu，取y方向上走一步，当di>0时，中点M在圆外，pd点离圆弧距离近，下一像素点应选取pd，即y方向不走步；当di=0时，中点M在圆上，pu、pd与圆弧的距离相等，选取pu和pd均可，约定取pd。因此：

If(di<0)

Yi=yi;

Else if(di>=0)

Yi=yi-1;

为了能够继续选取圆上的后续像素，需要给出中点误差项的递推公式与初始值。

在主位移x方向上已走一步的情况下，现在考虑沿主位移方向再走一步，应该选择哪个中点代入中点误差项以判断下一步要选取的像素，如图所示。

当di<0时，下一步进行判断的中点坐标为M（xi+2,yi+1.5）。下一步中点误差项为

Di+1=F(xi+2,yi+1.5)=di+2Xi+3;

当di>=0时，下一步进行判断的中点坐标为m(xi+2,yi+0.5)。下一步中点误差项为：

Di+1=di+2(xi-yi)+5

3.4.3 圆的扫描转换的实现

一、案例需求

1.案例描述

使用中点Breseham算法绘制圆心位于屏幕客户区中心的圆。

2.案例效果图

二、算法设计

1.输入圆的半径R。

2.定义圆当前坐标x和y，定义中点偏差差别式d，定义像素点颜色rgb。

3.计算d=1.25-R，x=0,y=R，rgb=RGB(0,0,255)

4.绘制点（x,y）及其在八分圆中的另外七个对称点。

5.判断d的符号，如d<0，则x,y更新为x+1,y，d更新为d+2x+3,否则（x,y）更新为(x+1,y-1)。

D更新为d+2(x-y)+5

void CBresenhamCircleView::GetScreenHeight()

{

CRect rect;

GetClientRect(&rect);

screenHeight=rect.bottom;

}

void CBresenhamCircleView::GetScreenWidth()

{

CRect rect;

GetClientRect(&rect);

screenWidth=rect.right;

}

void CBresenhamCircleView::DrawCircle()

{

double x,y,delta;

delta=1.25-radius;

x=0;

y=radius;

for(x=0;x

{

DrawCirclePoint(x,y);

if(delta<0)

{

delta+=2*x+3;

}

else{

delta+=2*(x-y)+5;

y--;

}

}

}

void CBresenhamCircleView::DrawCirclePoint(double x,double y)

{

CClientDC dc(this);

COLORREF rgb=RGB(0,0,255);

dc.SetPixel(ROUND(x)+screenWidth/2,ROUND(y)+screenHeight/2,rgb);

dc.SetPixel(ROUND(y)+screenWidth/2,ROUND(x)+screenHeight/2,rgb);

dc.SetPixel(ROUND(x)+screenWidth/2,-ROUND(y)+screenHeight/2,rgb);

dc.SetPixel(-ROUND(y)+screenWidth/2,ROUND(x)+screenHeight/2,rgb);

dc.SetPixel(-ROUND(x)+screenWidth/2,-ROUND(y)+screenHeight/2,rgb);

dc.SetPixel(-ROUND(y)+screenWidth/2,-ROUND(x)+screenHeight/2,rgb);

dc.SetPixel(-ROUND(x)+screenWidth/2,ROUND(y)+screenHeight/2,rgb);

dc.SetPixel(ROUND(y)+screenWidth/2,-ROUND(x)+screenHeight/2,rgb); }

void CBresenhamCircleView::On32771()

{

// TODO: 在此添加命令处理程序代码

CInputDialog dlg;

if(IDOK==dlg.DoModal())

{

radius=dlg.m_radius;

}

AfxGetMainWnd()->SetWindowText(_T("基本图形扫描转换!"));

RedrawWindow();

GetScreenWidth();

GetScreenHeight();

DrawCircle();

}

3.5 反走样技术(wu反走样算法)

直线扫描算法在处理非水平、非垂直且非45度的直线段时会出现锯齿，这是因为直线段在光栅扫描显示器上显示的图像是由一系列亮度相同而面积不为零的离散像素点构成的。这种由离散量表示连续量而引起的失真称为走样（aliasing）。用于减轻走样现象的技术称为反走样（anti-aliasing）或者称为抗锯齿。走样是理想直线（理想直线宽度为0）扫描转换后（真实像素点面积不为0）的必然结果。走样是光栅扫描显示器的一种固有现象，不可避免，只能减轻。

对于图3-18所示的黑色理想直线段，使用蹲点Bresenham算法进行扫描转换后，得到一组距离直线最近的黑色像素点。每当前一列所选的像素点和后一列所选的像素点不同行时，在显示器上就会出现一个锯齿，发生了走样。显然，只有对于水平线、垂直线和45度角直线，才不会发生走样。

许多绘图工具软件自身带有反走样功能，例如Microsoft Office Word 2003就使用了反走样技术。图3-19是使用Word软件中的绘图工具绘制的斜线，图3-20是该斜线放大8倍后的效果图。Windows的附件画图工具没有提供反走样功能。Word使用了现行像素来绘制反走样斜线，并且相信像素的亮度发生了变化，而“画图”工具只使用了一行像素来绘制走样斜线，并且像素的亮度等级保持不变。

反走样技术主要分为两类：一类是硬件技术，通过提高显示器分辨率来实现；另一类是软件技术，通过改进软件算法来实现。

图3-25中，从硬件角度把显示器的分辨率提高了一倍。由于每个锯齿在x方向和y方向上都只有原先分辨率的一阗，所以看上去走样现象有所减弱。虽然如此，硬件反走样技术由于受到硬件条件和成本的限制，使用起来较为困难，很难达到理想的反走样效果。

软件反走样技术主要是加权区域采样。算法的实质是利用人眼视觉特性，通过加权平均的方

法，调节像素的亮度或灰度等级以产生模糊边界，从而达到较好的视觉效果以消除“锯齿”。加权参数可以选择距离、面积和体积等。下面主要讲解直线的距离加权反走样算法，关于面积加权反走样算法和体积加权反走样算法请读者参考相关文献。

3.5.1 算法原理

Wu反走样算法是根据像素和理想直线的距离对相信两个像素的亮度等级进行调节。已知理想直线段A（x0,y0），B(x1,y1)，斜率k=△y/△x（0<=k<=1），直线与上下像素中心连线的交点为F1、F2、F3。如图3-26所示，按照中点Bresenham算法，直线段AB的x方向为主位移方向，理想直线段经过扫描转换后，像素点P4离直线上的点F1较近，像素点P1离直线上的点F1较远，p4点被选取；像素点P2离直线上的点F2较近，像素点P2离直线上的点F2较远，p2点被选取；像素点P3离直线上的点F3较近，像素点P6离直线上的点F6较远，p6点被选取；直线段扫描结果为P4、P2和P3。P4显示第一徙，P2和P3显示在第二行和第三行，出现了锯齿走样。

Wu反走样算法是采用空间混色原理对走样进行修正。空间混色原理指出，人眼对某一区域颜色的识别是取这个区域颜色的平均值。Wu反走样算法原理是对于理想直线上的任意一点，同时以两个不同亮度等级的相邻像素来表示。

在RGB(r,b,b)宏中，当r,g,b这3个值的变化率不同步时，出现彩色，当b,g,r3个值的变化率同步时，出现不同等级的亮度。B,g,r这3个分量的值都在0~255之间，共有256个亮度级别，并且规定亮度级别越大，也就是亮度值越大，像素越亮；规定亮度级别越小，也就是亮度值越小，像素越暗。如RGB(255,255,255)表示白色，RGB(0,0,0)表示黑色。本算法将亮度级别规范化到[0,1]闭区间，使用时乘以255即可。

图3-26所示的理想直线段上的点F1，扫描转换后可用像素点P1和像素点P4以不同的亮度等级共同表示，像素点离理想直线越近，其亮度值越小，像素越暗；像素点离理想直线段越远，其亮度值越大，像素越亮，但二者的亮度之各等于直线段上F1点的亮度值。

可以将p1点和p4点与理想直线的距离e作为加权参数，对像素的亮度级别进行调节。P1点距离理想直线0.8个像素远，该像素的亮度为80%,P4点距离理想直线0.2个像素远，该像素的亮度为20%。同理，P2点距离理想直线0.45个像素远，该像素的亮度为45%,P5点距离理想直线0.55个像素远，该像素的亮度为55%。P3点距离理想直线0.1个像素远，该像素的亮度为10%,P2点距离理想直线0.9个像素远，该像素的亮度为90%

从图3-26看出，Wu算法是用两个像素来共同表示理想直线上的一个点，依据两个像素与理想直线的距离而调节其亮度等级，使所绘制的直线达到视觉上消除锯齿的效果。实际使用中，两个像素宽度的直线反走样的效果较好，视觉效果上过线的宽度会有所减小，看起来好像是一个像素宽度的直线。

3.5.2 构造距离误差项

设通过原点的直线方程为

Y=kx

式中，k为斜率（0<=k<=1）

从Pi(xi,yi)的出发点取下一像素时，下一像素点只能在Pu(xi+1,yi+1)和p(xi+1,yi)中选取。理想直线段pu和pd的像素中心的交点为Fi,ei为fi与pd之间的距离。

3.6 区域填充图元

除了点、直线段和曲线之外，还有一种描述图形组成部分的有用结构是使用某种颜色或图案进行填充的区域。这种类型的图形部分一般称为填充区（fill area）或填充的区域（filled area）。通过填充区用于描述实体表面。但在许多其他应用中也很有用。填充区常常是一个平表面，主要是多边形。但一般而言，图形中可能有多种开关的区域选用某种颜色填充。图3.40给出了几种可能的填充区形状，目前我们假定填充区只能指定的某种颜色显示。

尽管有可能使用各种形状，但图形库一般不支持任意填充形状的描述。多数库函数要求填充区指定为多边形。由于多边形有线性边界，因而比其他填充开关更容易处理。另外，多数曲面可用一组适当的多边形面来逼近，就如曲线可用一组直线段逼近一样。在使用光照效果和表面处理时，逼近曲面可以相当逼真。利用多边形面片对一曲面进行的逼近有时称为表面细分，或者可以使用多边形网络来拟合曲面。图3.41给出了一个用轮廓线形式的多边形网络逼近的金属圆柱体，作为线框图，因其仅给出一般标识表面结构的多边形的边，所以这类图能够快速地进行显示。线框模型经绘制处理生成具有自然材料表面的显示使用一组多边形面片描述的对象称为标准图形对象（standard graphics object）或称为图形对象（graphics object）。

我们可以使用任何边界描述来建立填充区，如圆或互相连接的样条段线段。下一节讨论的一些多边形方法可以用来显示有非线性边界条件的填充区。曲线边界对象的填充方法将在第4章讨论。

void CFillPolygonView::OnMenuFillPolygon()

{

AfxGetMainWnd()->SetWindowTextW(_T("多边形填充：有效边表算法"));

CColorDialog dlg(getColor);

if(IDOK==dlg.DoModal())

{

getColor=dlg.GetColor();

}

RedrawWindow();

CreateBucket();

CreateAET();

PolygonFill();

}

void CFillPolygonView::CreateBucket()

{

int scanMin,scanMax;//确定扫描线的最小值和最大值

scanMin=scanMax=points[0].y;

for(int i=0;i

{

if(points[i].y

{

scanMin=points[i].y;//扫描线的最小值

}

if(points[i].y>scanMax)

{

scanMax=points[i].y;//扫描线的最大值

}

}

for(int i=scanMin;i<=scanMax;i++)//建立桶结点

{

if(i==scanMin)

{

headBucket=new Bucket;

currentBucket=headBucket;

currentBucket->scanLine=scanMin;

currentBucket->pAET=NULL;

currentBucket->next=NULL;

}else{//建立桶的其它结点

currentBucket->next=new Bucket;

currentBucket=currentBucket->next;

currentBucket->scanLine=i;

currentBucket->pAET=NULL;

currentBucket->next=NULL;

}

}

}

void CFillPolygonView::CreateAET()//构造边表函数

{

for(int i=0;i

{

currentBucket=headBucket;

int j=i+1;

if(POLYGON_VERTEX_NUMBER==j)j=0;

if(points[j].y>points[i].y)//终点比起点高

{

while(currentBucket->scanLine!=points[i].y)//在桶内寻找该边的yMin

{

currentBucket=currentBucket->next;

}

aetTable[i].x=points[i].x;

aetTable[i].yMax=points[j].y;

aetTable[i].k=double((points[j].x-points[i].x))/(points[j].y-points[i].y);

aetTable[i].next=NULL;

currentAET=currentBucket->pAET;

if(NULL==currentBucket->pAET)

{

currentAET=&aetTable[i];

currentBucket->pAET=currentAET;

}else{

while(currentAET->next!=NULL)

{

currentAET=currentAET->next;

}

currentAET->next=&aetTable[i];

}

}

if(points[j].y

{

while(currentBucket->scanLine!=points[j].y)//在桶内寻找该边的yMin

{

currentBucket=currentBucket->next;

}

aetTable[i].x=points[j].x;

aetTable[i].yMax=points[i].y;

aetTable[i].k=double((points[i].x-points[j].x))/(points[i].y-points[j].y);

aetTable[i].next=NULL;

currentAET=currentBucket->pAET;

if(NULL==currentBucket->pAET)

{

currentAET=&aetTable[i];

currentBucket->pAET=currentAET;

}else{

while(currentAET->next!=NULL)

{

currentAET=currentAET->next;

}

currentAET->next=&aetTable[i];

}

}

}

currentBucket=NULL;

currentAET=NULL;

}

void CFillPolygonView::AddEdage(AET*newEdage)//插入临时边

{

T1=headAET;

if(NULL==T1)

{

T1=newEdage;

headAET=T1;

}else{

while(T1->next!=NULL)

{

T1=T1->next;

}

T1->next=newEdage;

}

}

void CFillPolygonView::EdageOrder()//对边表进行排序{

T1=headAET;

if(NULL==T1)

{

return;

}

if(NULL==T1->next)

{

return;

}else{

if(T1->next->xx)

{

T2=T1->next;

T1->next=T2->next;

T2->next=T1;

headAET=T2;

}

T2=headAET;

T1=headAET->next;

while(T1->next!=NULL)

{

if(T1->next->xx)

{

T2->next=T1->next;

T1->next=T1->next->next;

T2->next->next=T1;

T2=T2->next;

}else{

T2=T1;

T1=T1->next;

}

}

}