计算机图形学重点和难点指导

B

F3 F2 F1 A

P4

距离理想直线0.2个像素远的像素亮度为20％

距离理想直线0.55个像素远

的像素亮度为55％

P5

P6

距离理想直线0.9个像素远的像素亮度为90％

图2 Wu反走样算法示意图

Wu反走样算法原理是对于理想直线上的任一点，同时以两个不同亮度等级的相邻像素来表示。例如，图3所示的理想直线段上的F1点，扫描转换后可用像素点P1和像素点P4以不同的亮度等级共同显示，而且像素点离理想直线段越近，其亮度值越小，像素越暗；像素点离理想直线段越远，其亮度值就越大，像素越亮，但二者的亮度值之和等于直线段上F1点的亮度值。可以将P4点与理想直线段上的F1点的距离e作为加权参数（P1点与F1点的距离为1-e），对相邻像素的亮度级别进行调节。P1点距离F1点0.8个像素远，该像素的亮度为80％；P4点距离F1点0.2个像素远，该像素的亮度为20％。

同理，P2点距离F2点0.45个像素远，该像素的亮度为45％；P5点距离F2点0.55个像素远，该像素的亮度为55％；P3点距离F3点0.1个像素远，该像素的亮度为10％。 P6点距离F3点0.9个像素远，该像素的亮度为90％。

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

第3章难点学习指导：

1. 彩色直线段的扫描转换算法

直线的光滑着色是光照模型的基础，使用直线光滑着色技术可以绘制物体的光照线框模型。给定直线段两个顶点的坐标和颜色值，使用拉格朗日线性插值方法可以实现直线段颜色从起点到终点的光滑过渡。给定直线段起点P0的坐标（x0,y0）起点和颜色c0，直线段终点P1的坐标（x1,y1）起点和颜色c1，直线的参数方程为

P?(1?t)P0?tP1 t∈[0,1]

展开式为

?x?(1-t)x0?tx1??y?(1?t)y0?ty1 ?c?(1?t)c?tc01?式中：P（x,y,c）为直线段上任意一点的坐标和颜色。

如果直线段的斜率k?1，则x方向为主位移方向，直线上任意一点P的颜色按照拉格朗日线性插值公式有

c?x?x0x?x1c0?c1

x0?x1x1?x0如果直线段的斜率k?1，y方向为主位移方向，直线上任意一点P的颜色按照拉格朗日线性插值公式有

c?y?y0y?y1c0?c1

y0?y1y1?y0x?x0y?y0x?x1y?y1，则1?t?；若令t?，则1?t?。可以统一

x0?x1x1?x0y1?y0y0?y1若令t?表示为

c?(1?t)c0?tc1，t∈[0,1]

彩色直线段可以使用本书第3章讲解的中点Bresenham算法绘制，效果如图3所示。

图3 起点红色终点蓝色的彩色直线段

2. 直线段绘制闭合图形算法

实际应用中，中点Bresenham算法并不仅用于绘制一段直线，常用于绘制折线构成的多边形。假定多边形各条边的颜色为单色且不相同（例如使用红绿蓝三段直线连接构成三角形，如图4（a）所示）。此时，需要考虑直线段连接点的正确着色问题。

对于每段折线的两个端点一般采用“起点闭区间、终点开区间”的处理方法，即一段折线终点处的颜色由下一段折线起点处的颜色来填充，如图4（b）图所示。为此，绘制多边形的边时应考虑折线绘制的方向问题，即从起点绘制到终点（例如PP）的算法应该与从

01终点绘制到起点（例如PP）的算法不同，而不是简单地交换两端点参数（坐标和颜色等）

10??后使用同一个算法处理（一般为从低端绘制到高端）。如果从P0点向P1点方向绘制时，采用的是主位移方向每次加1，另一个方向根据误差项选取距离理想折线最近的像素点，且端点P0绘制，端点P1不绘制；如果从P1点向P0点方向绘制时，采用的是主位移方向每次减1，另一个方向根据误差项选取距离理想折线最近的像素点，端点P1绘制，端点P0不绘制。采用上述方法，可以正确处理多边形顶点处的颜色并完整地闭合多边形，使用本算法绘制的三角形边界放大效果如图5所示。

P2P2P1P0P0P1

（a）折线的方向 （b）端点处理

图4 折线绘制三角形

图5三角形边界放大效果图

3. 基于背景色的第一个八分之一象限内彩色直线段上下相邻像素的颜色计算法；

设直线段的斜率0≤k≤1，直线段颜色（前景色）为RGB(rf,gf,bf)，屏幕背景色为RGB（rb,gb,bb)。下标f代表front，b代表back。彩色直线段的反走样算法是使直线段颜色从前景色过渡到背景色，在前景色和背景色之间出现模糊的边界。取ei为Fi与Pd的距离，则Pd（xi＋1,yi）像素的颜色为cd=RGB(((rb - rf)×ei+ rf) ×255,(( gb - gf)×ei+ gf) ×255,(( bb - bf)×ei+ bf) ×255)；Pu（x i＋1,y i＋1）像素的颜色为cd=RGB(((rb - rf)×(1-ei)+ rf) ×255,(( gb - gf)×(1-ei)+ gf) ×255,(( bb - bf)×(1-ei)+ bf) ×255)。

第4章 多边形填充

重点：平面着色与光滑着色；马赫带；边表与桶表；像素颜色取补；包围盒与栅栏；四邻接点与八邻接点；四连通边界与八连通边界；

难点：使用动态链表实现有效边表填充算法；压栈和出栈算法；

第4章重点学习指导：

1. 平面着色与光滑着色

多边形可以使用平面着色模式（flat shading mode）或光滑着色模式（smooth shading mode）填充。平面着色是指使用多边形第一个顶点的颜色填充，多边形内部具有单一颜色。光滑着色是指多边形内部像素点的颜色是由多边形各个顶点的颜色进行线性插值得到。假定三角形3个顶点的颜色分别为红色、绿色和蓝色。图6所示为三角形的平面着色，三角形填充为三角形第一个顶点的颜色红色。图7所示为三角形的光滑着色，三角形上任一点的颜色为3个顶点颜色的光滑过渡。

图 6三角形的平面着色 图7 三角形的光滑着色

2. 马赫带

马赫带效应（Mach band effect）是指视觉的主观感受在亮度有变化的地方出现虚幻的明亮或黑暗的条纹，马赫带效应的出现是人类的视觉系统造成的。生理学对马赫带效应的解释是：人类的视觉系统有增强边缘对比度的机制。当观察图8所示的不同灰度构成的矩形时，边界处亮度对比加强，使轮廓表现得特别明显。

图8 马赫带

3. 有效边表、边表与桶表

将有效边按照与扫描线交点的x坐标递增的顺序存放在一个链表中，称为有效边表（active edge table，AET），有效边表的结点如图9所示。

xymax1/knext

图 9 有效边表

由有效边表可以知道，xi?1?xi?的横坐标。增量为斜率的倒数。

为了确定新边从哪条扫描线上开始插入，就需要构造一个边表（edge table，ET），用以存放多边形各条边出现在扫描线上的信息。

1。随着扫描线y的递增，可以计算扫描线与边交点kx|yminymax1/knext

图10 边表

有效边表与边表的关系：边表是有效边表的特例，即该边最小y坐标处的有效边表。有效边表和边表可以使用同一个类来表示。

桶表是按照扫描线顺序管理边出现情况的一个数据结构。构造一个纵向扫描线链表，