英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料

---

光栅显示器的高效多边形填充算法

迈克尔·R·邓拉维

波士顿大学

描述了基于奇偶校验的算法，用于着色在光栅显示器上绘制的多边形的内部。 多边形作为增量移动链输入。 这些算法是自动的，因为它们不需要手动指定的内部点。 首先，区分用于光栅显示的两个可能的坐标系，面向区域的和面向矢量的坐标系。 Ackland和Weste的边缘填充算法用于面向区域的坐标系，然后适用于面向矢量的坐标系。 接下来，通过两种方法提高算法效率，分别是围栏填充法和成对填充法，它们可以在存储中高速的交换数据。 最后，在附录中，证明了面向矢量的边缘填充法的正确性。

类别和主题描述符：1.3.3 [计算机图形]：图像/图像生成 - 显示算法

一般术语：算法

附加关键词和短语：多边形填充，光栅扫描，图形。

1. 引言

基于奇偶校验的算法已用于在光栅显示器上绘制任意区域。与各种“泛滥”算法[2,4,5]不同，算法无需人为输入指定点来判别内部点。基本原理是，在从左到右遍历扫描线时，多边形边界的每个交叉点反转多边形外部或内部的条件。在选择多边形填充算法时，可以使用两种不同的栅格坐标系，如图1所示。面向区域的坐标系是大多数关于多边形填充的文献[1-5]中假设的系统。在这个系统中，像素位于网格线之间，而不是网格线之上。这适用于地图和卡通动画等应用，因为共享公共边框的多边形将无缝地邻接，而不共享任何像素。表示面向矢量的交替坐标系是像素位于网格线上的交替坐标系。它适用于面向线路的应用，如接线图。在绘制导线时，必须指定两个边缘而不仅仅是中心线，这将是繁重的。

图1可选择的坐标系统：（a）目标形状，（b）面向区域形状，（c）面向矢量形状

被填充多边形（dx，dy）以及起始位置（x，y）作为序列参数传递给算法，其中所有值都是整数型，并且增量用以描述闭合曲线。 dx值可以是从正无穷大到负无穷大的任何整数。 dy值为 1,0或-1。 排除空移动（0,0）。
移动可以分为四类。 无论dx如何，所有的向上移动（即dy = 1）都称为北向运动。 类似地，所有向下“向下”（dy = -1）的移动都被称为向南，而不管dx如何变化。 最后，如果dy = 0，则移动为东向运动（dxgt; 0）或西向（dx lt;0）。 我们预定左右术语来表示相对于局部运动方向的方向。 可能的移动集合如图2所示。

图2 可允许移动的类

1. 区域边缘填充算法

该算法与Edge Fill [1]相同。 直观的原理如图3。在多边形边界与扫描线相交的每个点，所有像素从那一点到屏幕的左边缘都是倒置的。 因此，多边形外的每一个点都将被反转偶数次。将所有像素转换到给定X，Y位置左侧的操作被表示为CLEAR。 在区域边缘填充算法中，CLEAR操作只会因南北方向的移动导致，因为东西方向的移动不与扫描线相交。当进行这样的移动时，最接近交叉点的像素（在网格线中间）会被清除。、

算法在从序列文件中读取时的移动操作中被执行。简化了表现形式并强调了算法的存储有限的性质。

图三 边缘填充算法

VAR x, Y, dx, dy, i: INTEGER;

PROCEDURE invert-scan-segment(xl, x2, y: INTEGER);

BEGIN

IF xl lt; x2 THEN

FOR i xl 1 TO x2 DO invert-pixel(i, y)

ELSE

FOR i := x2 1 TO xl DO invert—pixel(i, y);

END;

PROCEDURE clear(x, Y. INTEGER);

BEGIN

invert—scan—segment(0, x, y);

END;

BEGIN {begin REGION -EDGE-FILL}

read(x, y); {read starting position}

{for each move}

WHILE not end-of-file DO BEGIN

read(dx, dy); {tread the move}

CASE Class (dx, dy) OF {do the appropriate clear}

east: Nop;

north: clear(x trunc(dx/2), y);

west: Nop;

south: clear(x trunc(dx/2), y 1);

END;

x := x dx; {do the move}

Y Y dy;

END; {end REGION - EDGE-FILM

1. 矢量边缘填充算法

矢量边缘填充算法将输入的移动序列指令作为通过多边形边缘的像素，而不是绕过他们。假设多边形边框总是在逆时针电路中绘制，边框像素应始终与局部方向左侧运动的像素颜色相同如果一个多边形的宽度为0，并且他的长度非0，那么它应该表示为一条直线。这些规则可起到将多边形在以顺时针方向绘制并忽略边框的效果，如图4所示。这一方法能够有效的填充边缘高亮显示的多边形。但是，它也可以取得出乎意料的结果，正如图5中的图8的图形所示。因为分为两半的多边形相向运动，一半有边界，而另一半没有。除此之外，还可以在北方向与南方向创建极端“孤儿”像素。这些孤立像素是算法所期望的宽度为0的多边形（例如直线）可视的规则。

在多边形边缘填算法中，每一步移动动作不只依靠新的类，即移动所实现的类，但是在OLD类中，前一步运动的类。会有以下4中可能的动作：

C：CLEAR(X,Y)

C1:CLEAR(X-1,Y)

I：INVERT(X,Y)(equivalent to C and C1 together)

N: NOP

可以依据表一采取操作。除此之外，矢量边界填充算法与区域边界填充算法的唯一区别是操作适合延期执行于第一步移动，直到最后一步移动操作，因为这样操作之前，类的前一个结果尚未知。

PROCEDURE vector_edge_fill;

VAR newclass,

oldclass,

firstclass: (east, north, west, south);

VAR x, y, dx, dy, i: INTEGER;

PROCEDURE invert_scan_segment; {same as in region_edge_fill}

PROCEDURE clear(x, y); {same as in region_edge_fill}

图4 矢量边界填充算法 每一个像素倒置细节

表1

NEWCLASS	North	West	South	East
OLDCLASS
East	C	C	N	N
North	C	C	I	N
West	N	N	C1	C1
South	I	N	C1	C1

PROCEDURE take_action( oldclass, newclass );

CASE TABLE_I[ oldclass, newclass ] OF

C: clear(x, y);

CI: clear(x - 1, y);

I: invert_pixel(x, y);

N: Nop;

END;

END;

BEGIN {begin VECTOR_EDGE_FILL}

read(x, y); {read starting position}

read(dx, dy); {read first move}

firstclass := Class(dx, dy);

x := x dx; {do first move}

y := y dy;

oldclass := first class;

WHILE not end_of_file DO BEGIN {for each succeeding move}

read(dx, dy); {read the move}

newclass := class(dx, dy);

take_action( oldclass, newclass ); {perform the proper action}

x := x dx; {do the move}

y:= y dy;

oldclass := newclass;

END;

take_action( oldclass, firstclass ); {perform action at start position}

END; {end VECTOR_EDGE_FILL}

图5 边界自相交效果举例

1. 储存与时间权衡

上面给出的算法除了图像本身之外不使用任何存储器。这很容易看到小多边形距离左边缘的距离为X，倒置的像素数可以比多边形的面积大许多倍。但是，扫描线不需要一直向左反转至屏幕边缘。相反，可以使用任意边界，称为围栏。反转可以进入围栏，无论这意味着向右或向左清除。对于围栏来说，一个正确的选择就是在某个点的X值，这个点多边形的边界，例如第一个点。如图6所示，为了实现该功能，CLEAR程序进行如下修改。

PROCEDURE clear{x, y); BEGIN

invert_scan_segment(fence, x, y);

END;

出于参考的目的，以这种方式优化的算法被称为围栏算法。

算法更进一步的提升通过使用Q数组的X的值、每一根扫描线来实现。使得有有一个显著的空值存在在Q[Y]数组中，以表明数组中没有X值。初始的Q[Y]数组全部为空。第一个X值通过与扫描线相交简易地存储在数组中。当扫描线与第二个X值相交，沿着两个X值之间的像素会被反转。任何的扫描线相交都会重复这一过程。为了完成这一过程，我们对CLEAR方法做出如下优化：

PROCEDURE clear(x, y); BEGIN

IF q[y] = empty THEN q[y] := x

ELSE BEGIN

invert_scan_segment(q[y], x, y);

q[y] := empty;

END;

END;

图6 围栏填充算法

这个方法，用来表示两两配对填充法，是最佳的凸多边形的填充方法。并且它面对典型的非凸多边形也有良好的表现，正如图7所示，但是也存在其他更佳的算法在面对病态的多边形时，比如图8所示的螺旋线。

1. 附录 矢量边界填充法的正确性

基于对等多边形填充算法的正确性的一个必要条件是施加在任何一条扫描线的清理点的数量是平衡的。这个条件被称为局部属性。

为证明矢量边界填充算法的局部特征，我们会选择一个随意整数型的扫描线Y，并证明清除点数量通过扫描线数量平衡来实现。有三种方式实现扫描线与多边形的边界相交。它可以从一边到另一边穿越边界；它也可以从一侧穿过之后再回来原来这一侧

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[19520]，资料为PDF文档或Word文档，PDF文档可免费转换为Word