-
企业建站所需
2008-01-10 19:56:21
-
当爱情悄然走过，我才懂得
2007-04-23 08:52:43
-
[论坛] 做不了爱人，我们做什么？
2007-04-23 08:32:46
-
浪漫的事
2007-04-22 14:19:04
-
世界上最浪漫的事
2007-04-22 14:13:18
-
删除U盘病毒出高招
2007-04-19 09:18:52
-
高斯赛德尔迭代法
2007-04-19 09:13:33
-
历城二中~人生在勤
2007-04-12 20:25:36
历城二中~人生在勤在高中的三年中，我们做到了：
学会做人，学会处世；
学会合作，学会学习；
静思苦学，志存高远；
自强自信，稳定心态；
遵守纪律，关心集体。
不负恩师厚望，不负父母期盼；
不负十二年寒窗苦读，不负青春梦想！
态度决定一切，一切皆有可能，
我们永不言弃！！！ -
江苏各大高校排名
2007-04-07 19:32:46
-
2.5.2求交线算法
2007-04-07 10:51:22
-
2.4 字符的生成 2.5 图形求交
2007-04-07 10:50:24
2.4 字符的生成
在计算机图形学中，字符可以用不同的方式表达和生成。常用的方法有点阵式、矢量式和编码式。
2.4.1 点阵式字符
点阵式字符将字符表示为一个矩形点阵，由点阵中点的不同值表达字符的形状。常用的点阵大小有5? 7、7? 9、8? 8、16? 16等等。图2.4.1(a)所示的字母“P”的点阵式表示例子。在这种8? 8网格中的字形比较粗糙，但当点阵变大时，字型可以做得非常漂亮。
使用点阵式字符时，需将字库中的矩形点阵拷贝到buffer中指定的单元中去。在拷贝过程中，可以施加变换，以获得简单的变化。图2.4.1(b)~(d)列出了P字母原型的一些变化例子。相应的变换算法是：
(a) (b) (c) (d)
图2.4.1 点阵式字符及其变化
图（b）变成粗体字。算法是：当字符原型中每个象素被写入帧缓存寄存器的指定位置xi, yi时，同时被写入xi+1, yi。
图（c）旋转90? 。算法是：把字符原型中每个象素的x, y坐标彼此交换，并使y值改变符号后，再写入帧缓存寄存器的指定位置。
图（d）斜体字。算法是：从底到顶逐行拷贝字符，每隔n行，左移一单元。
此外，还可以对点阵式字符作比例缩放等其他一些简单的变换。但是对点阵式字符作任意角度的旋转等变换，是比较困难的操作。
由于光栅扫描显示器的普遍使用，点阵式字符表示已经成为一种字符表示的主要形式。从字库中读出原字型，经过变换拷贝到buffer中去的操作，经常制成专门的硬件来完成。这就大大加快了字符生成的速度。
2.4.2 矢量式字符
矢量式字符将字符表达为一个点坐标的序列，相邻两点表示一条矢量，字符的形状便由矢量序列刻划。图2.4.2示出用矢量式表示的字符“B”。“B”是由顶点序列{a, b, c, d, e, f, e, g, h, I, j, k ,a, l}的坐标表达。
调用矢量式字符的过程相当于输出一个polyline。由于矢量式字符具有和图形相一致的数据结构，因而可以接受任何对于图形的操作，如放大、旋转，甚至透视。而且，矢量式字符不仅可用于显示，也可用于绘图机输出。
图2.4.2 矢量式表示字符“B”
2.4.3 方向编码式字符
方向编码式字符用有限的若干种方向编码来表达一个字符，常用的如8方向编码。图2.4.3示出8个方向的编码为0~7，其中编码为偶数和0的固定长度为1，编码为奇数的固定长度为
。一个字符就可以表示为一连串方向码。图2.4.4(a)示出字母“B”的方向矢量构成。这样，“B”就表示为8方向编码：{000012344400012344440666666}。方向编码式字符很容易被填入帧缓存寄存器中予以显示（图2.4.4(b)），方向编码所占的空间比较小，它也能接受一些特定的变换操作，如按比例在x和y两个方向放大或缩小以及以45? 角为单位的旋转，但难以进行任意角度的旋转。
图2.4.3 图2.4.4
方向编码既可用于字符的显示，也可用于字符的绘图机输出
2.4.4 轮廓字型技术
当对输出字符的要求较高时（如排版印刷），需要使用高质量的点阵字符。对于GB2312-80所规定的6763个基本汉字，假设每个汉字是72X72点阵，那么一个字库就需要72X72X6763/8=4.4兆字节存储空间；不但如此，在实际使用时，还需要多种字体（如基本体、宋体、仿宋体、黑体、楷体等），每种字体又需要多种字号。可见，直接使用点阵字符方法将耗费巨大的存储空间。因此把每种字体、字号的字符都存储一个对应的点阵，在一般情况是不可行的。
解决这个问题一般采用压缩技术。对字型数据压缩后再存储，使用时，将压缩的数据还原为字符位图点阵。压缩方法有多种，最简单的有黑白段压缩法，这种方法简单，还原快，不失真，但压缩较差，使用起来也不方便，一般用于低级的文字处理系统中。另一种方法是部件压缩法。这种方法压缩比大，缺点是字型质量不能保证。三是轮廓字型法，这种方法压缩比大，且能保证字符质量，是当今国际上最流行的一种方法，基本上也被认为是符合工业标准化的方法。
轮廓字型法采用直线、或者二/三次Bezier曲线的集合来描述一个字符的轮廓线。轮廓线构成一个或若干个封闭的平面区域。轮廓线定义加上一些指示横宽、竖宽、基点、基线等的控制信息，就构成了字符的压缩数据。这种控制信息用于保证字符变倍时引起的字符笔划原来的横宽/竖宽变大变小时，其宽度在任何点阵情况下永远一致。采用适当的区域填充算法，可以从字符的轮廓线定义产生的字符位图点阵，区域填充算法可以用硬件实现，也可以用软件实现。
由美国Apple和Microsoft公司联合开发的TrueType字型技术就是一种轮廓字型技术，已被用于为Windows中文版生成汉字字库。当前占领主要的电子印刷市场的我国北大方正和华光电子印刷系统，用的字型技术是汉字字型轮廓矢量法。这种方法能够准确地把字符的信息描述下来，保证了还原的字符质量，又对字型数据进行了大量的压缩。调用字符时，可以任意地放大、缩小或进行花样变化，基本上能满足电子印刷中字型质量的要求。轮廓字型技术有着广泛的应用。到目前为止在印刷行业中使用最多，随着Ms-Windows的大量使用，在CAD、图形学等领域也将变得越来越重要。
2.5 图形求交
在计算机图形学中常常会遇到求交计算。例如，在进行扫描线区域填充时要求线段的交点，许多消隐算法需要进行直线和平面多边形的求交，等等。求交运算往往是比较复杂的，为了减小计算量，在进行真正的求交计算之前，往往先用凸包等辅助结构进行粗略的比较，排除那些显然不相交的情形。求交计算是CAD系统的重要部分。它的准确性与效率直接影响CAD系统的可靠性与实用性。
在数学上两个浮点数可以严格相等，但计算机表示的浮点数有误差，所以当两个浮点数的差的绝对值充分小时（例如，小于某个正数? ），就认为它们相等。相应地，求交运算中也要引进容差。当两个点的坐标值充分接近时，即其距离充分近时，就被认为是重合的点，直观地说，点可看作半径为? 的球，线可看作半径为? 的圆管，面可看作厚度为2? 的薄板。一般取? =10-6或更小的数。
求交问题可以分为求交点和求交线两类。本节的讨论不涉及自由曲线曲面，有关自由曲线曲面的求交问题将在2.7和2.8节讨论。
2.5.1求交点算法
求交点可以分两种情况：求线与线的交点以及求线与面的交点。下面首先讨论线与线的交点的求法。。
1、直线段与直线段的交点
假设二条直线的端点分别为P1，P2，Q1，Q2，则它们可以用向量形式表示为：
P(t)=A+Bt (0? t? 1)
Q(s)=C+Ds (0? s? 1)
其中，A=P1，B=P2-P1，C=Q1，D=Q2-Q1。
构造方程
A+Bt=C+Ds (2-5-1)
对三维空间中的直线段来说，上述方程实际上是一个二元一次方程组，由三个方程式组成。可以从其中两个解出s, t，再用第三个验证解的有效性：若第三个方程成立则说明找到了解，否则说明两条直线不相交。当所得的解（ti, si）是有效解时，可用二个线段方程之一计算交点坐标，例如P(ti)=A+Bti。
我们还可以根据向量的基本性质，直接计算s与t：对（2-5-2）两边构造点积得
(C? D)·（A+Bt）=（C? D）·（C+Ds）
由于C? D同时垂直于C和D，等式右边为零。故有
类似地有
完整的算法还应判断无解与无穷多解（共线）的情形，以及考虑数值计算误差造成的影响。
2、直线段与二次曲线的交点
不失一般性，考虑平面上一条直线与同平面的一条二次曲线的交。
假设 曲线方程为 f(x, y)=0,
直线段方程为 (x, y)=(x1+tdx, y1+tdy),
则在交点处有 f(x1+tdx, y1+tdy)=0
当曲线为二次曲线时，上述方程可写为
at2+bt+c=0
用二次方程求根公式即可解出t值。
3、圆锥曲线与圆锥曲线的交点
圆锥曲线有代数法表示、几何法表示与参数法表示。在进行一对圆锥曲线的求交时，把其中一条圆锥曲线用代数/几何法表示为隐函数形式，另一条表示为参数形式（如二次NURBS曲线）。将参数形式代入隐函数形式可得关于参数的四次方程，可以使用四次方程的求根公式解出交点参数。得到交点后可再验证交点是否在有效的圆锥曲线段上。
下面讨论线与面的交点的求法。
1、直线段与平面的交点
图2.5.1 线段与平面求交
考虑直线段与无界平面的求交问题，如图8.3.6所示。把平面上的点表示为P(u, w)=A+uB+wC，直线段上的点表示为Q(t)=D+tE，二者的交点记为R。假设线段不平行于平面，则它们交于R=P(u, w)=Q(t)，即
A+uB+wC=D+tE
等式两边点乘（B? C），得
（B? C）·（A+uB+wC）=（B? C）·（D+tE）
由于B? C既垂直于B，又垂直于C，故有
（B? C）·A=（B? C）·（D+tE）
可解出
类似求得
如果是直线与平面区域求交点，则要进一步判断点是否在平面上的有效区域中，其算法可参见2.5.3节。
2、圆锥曲线与平面的交点
圆锥曲线与平面求交时，可以把圆锥曲线表示为参数形式，并把圆锥曲线的参数形式代入平面方程，即可得到参数的二次方程进行求解。
- 圆锥曲线与二次曲面的交点
圆锥曲线与二次曲面求交时，可把圆锥曲线的参数形式代入二次曲面的隐式方程，得到参数的四次方程，用求根公式求解。
-
2.3.3 种子填色算法
2007-04-07 10:46:16
2.3.3 种子填色算法
种子填色又称边界填色（Boundary Filling）。它的功能是：给出多边形光栅化后的边界位置及边界色代码boundary，以及多边形之内的一点x, y位置，要求将颜色color填满多边形。
通常采用的填法有两种：四邻法（4-connected）和八邻法。四邻法是已知x, y（图2.3.6(a)的黑色象素）是多边形内的一点，据此向上下左右四个方向测试（图2.3.6(a)中打勾的象素）、填色、扩散。四邻法的缺点是有时不能通过狭窄区域，因而不能填满多边形。如图2.3.6(b)所示，左下角方形中的种子（打点的象素）不能扩散到右上角的方形中，因为采用四邻法通不过中间的狭窄区域。八邻法是已知x, y（图2.3.6 (c)中黑色的象素）为多边形内的一点，即种子，据此可向周围的八个方向（图2.3.6(c)中打勾的象素）测试、填色、扩散。八邻法的缺点是有时要填出多边形的边界。如图2.3.6(d)所示的边界，按八邻法就会将色彩涂出多边形。由于填不满往往比涂出更易于补救，因此四邻法比八邻法用的更普通。
四邻法种子填色基本程序如程序2.3.2所示。这种程序书写简洁，但运行效率不高，因为包含有多余的判断。在它的基础上可以写出各种改进的算法[8]。
void seed_filling (x, y, fill_color, boundary_color)
int x, y, fill_color, boundary_color;
{
int c;
c=inquire_color(x, y);
if((c< > boundary_color) && (c< > fill_color))
{
set_pixel(x, y, fill_color);
seed_filling(x+1, y, fill_color, boundary_color);
seed_filling(x-1, y, fill_color, boundary_color);
seed_filling(x, y+1, fill_color, boundary_color);
seed_filling(x, y-1, fill_color, boundary_color);
}
}
程序2.3.2 四邻法种子填色程序
图2.3.6 四邻法和八邻法种子
-
四邻法
-
四邻法不能填满此多边形
-
八邻法
-
八邻法会涂出此多边形
-
-
2.3.2 扫描线填色算法
2007-04-07 10:44:32
2.3.2 扫描线填色算法
一、算法的基本思想
多边形以n, x_array, y_array形式给出，其中x_array，y_array中存放着多边形的n个顶点的x, y坐标。扫描线填色算法的基本思想是：
用水平扫描线从上到下扫描由点线段构成的多段构成的多边形。每根扫描线与多边形各边产生一系列交点。将这些交点按照x坐标进行分类，将分类后的交点成对取出，作为两个端点，以所填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。
上述基本思想中，有几个问题需要解决或改善。它们是：
1. 左、右顶点处理 当以1, 2, 3的次序画多边形外框时，多边形的左顶点和右顶点如图2.3.3 (a)、(b)所示的顶点2。它们具有性质：
左顶点2：y1<y2<y3
右顶点2：y1>y2>y3
其中y1, y2, y3是三个相邻的顶点的y坐标。
(a)左顶点 (b)右顶点
图2.3.3
当扫描线与多边形的每个顶点相交时，会同时产生2个交点，这是因为一个顶点同属于多边形之两条边的端点。这时，如果所交的顶点是左顶点或右顶点，填色就会因奇偶计数出错而出现错误。因此，对多边形的所有左、右顶点作如下处理；
左、右顶点的入边（以该顶点为终点的那条边），即1, 2边之终点删去。即：
对于左顶点：入边（x1, y1）（x2, y2）修改为（x1, y1）（
,y2-1）；对于右顶点：入边（x1, y1）（x2, y2）修改为（x1, y1）（
,y2+1）；其中m=
，即入边之斜率。对于多边形的上顶点（y2>y1 & y2>y3）或下顶点（y2<y1 & y2<y3），奇偶记数保持正确，因此不必修改，保持相邻边原状不变。
2. 水平边处理 水平边（y1=y2）与水平扫描线重合法求交点。因此，将水平边画出后删去，不参加求交及求交以后的操作。
3. 扫描线与边的求交点方法采用递归算法 边（x1, y1）（x2, y2）与扫描线i+1的交点为：
（当交点不为x1, y1时）
否则，交点为x1, y1。
由上式可知，求交点只须做两个简单的减法。
4. 减少求交计算，采用活性边表 对于一根扫描线而言，与之相交的边只占多边形全部边的一部分。因此，在基本算法思想中，每根扫描线与多边形所有边求交的操作是一种浪费，需要加以改善。活性边表（Active List of Side）的采用将多边形的边分成两个子集：与当前扫描线相交的边的集合，以及与当前的扫描线不相交的边的集合。后者不必予以求交，这样就提高了算法的效率。
(a) (b)在scan1的情况
图2.3.4 活性边表及其指针的表示
活性边表的构成方法是：
1）将经过左、右顶点处理及剔除水平边后的多边形之各边按照max y值排序，存入一个线性表中。表中每一个元素代表一根边。第一个元素是max y值最大的边，最后一个元素是max y值最小的边。图2.3.4 (a)中的多边形所形成的线性表如（b）所示。其中F点和B点的y值相等，且为全部多边形的max y的最大值。因此FG, FE, AB, BC等四边排在表之首。而C点的y值>E点的y值，所以CH排在DE前面，余类推。在max y值相等的边之间，按任意次序排列。
2）在上述线性表上加入两个指针first和last，即形成活性边表。这两个指针之间是与当前扫描线相交的边的集合和已经处理完（即扫描完）的边的集合。这两者的区分方法是在处理完的边上加上记号：? y=0。在last指针以后的是尚未与当前扫描线相交的，在first指针以前的是已经处理完了的边。对于图2.3.4 (a)中扫描线scan1的情况下，图2.3.4 (b)中列出first, last的位置。如果扫描线由上而下移到了scan2的位置，则活性边表的first应指向AB，last应指向CH。每根扫描线只须与位于first, last之间的，而且? y? 0的边求交即可。这就缩小了求交的范围。
3）活性边表中每个元素的内容包括：
·边的max y值，记为y_top；
·与当前扫描线相交点的x坐标值，记为x_int；
·边的y方向当前总长。初始值为y2-y1。记为? y；
·边的斜率倒数：
，记为x_change_per_scan。4）活性边在每根扫描线扫描之后刷新。刷新的内容有2项：
·调整first和last指针字间的参加求交的边元素之值：? y=? y-1; x_int = x_int - x_change_per_scan;
·调整first和last指针，以便让新边进入激活范围，处理完的边退出激活范围：
当first所指边的? y=0时，first=first+1；
当last所指的下一条边的y_top? 下一扫描线的y值时，last=last+1。
二、扫描线填色程序
程序2.3.1示出扫描线填色算法的程序。主程序名为fill_area(count, x, y)，其中参数x, y是两个一维数组，存放多边形顶点（共count个）的x和y坐标。它调用8个子程序，彼此的调用关系如图2.3.5所示。各子程序的功能为：
图2.3.5 fill_area的程序结构
typedef struct {
int y_top;
float x_int;
int delta_y;
floaat x_change_per_scan;
} EACH_ENTRY;
EACH_ENTRY SIDES[MAX_POINT];
int x[MAX_POINT], y[MAX_POINT];
int side_count, first_s, last_s, scan, bottomscan, x_int_count, r;
fill_area(count, x, y)
int count, x[ ], y[ ];
{
sort_on_bigger_y(count);
first_s=1;
last_s=1;
for (scan=sides[1].y_top; scan>bottomscan ?; scan - -)
{
up date_first_and_last(count, scan);
process_x_intersections(scan, first_s, last_s);
draw_lines (scan, x_int_count, first_s);
update-_sides_list ( );
}
}
void put_in_sides_list(entry, x1, y1, x2, y2, next_y);
int entry, x1, y1, x2, y2, next_y;
{
int maxy;
float x2_temp, x_change_temp;
x_change_temp = (float) (x2-x1) / (float) (y2-y1);
x2_temp =x2; /*以下为退缩一点操作. */
if ((y2>y1) && (y2<next_y)) {
y2 - - ;
x2_temp - = x_change_temp;
}
else {
if ((y2<y1) && (y2 >next_y)) {
y2++;
x2_temp+=x_change_temp;
}
}
/* 以下为插入活性表操作. */
maxy = (y1 > y2)? y1: y2;
while (( entry >1) && (maxy > sides [entry -1]. y_top))
{
sides[entry]=sides [entry ?];
entry - -;
}
sides[entry]. y_top=maxy;
sides[entry]. delta_y =abs(y2-y1)+1;
if (y1>y2)
sides[entry]. x_int =x1;
else{
sides[entry].x_int=x2_temp;
sides[entry]. x_change_per_scan=x_change_temp;
}
void sort_on_bigger_y(n)
int n;
{
int k, x1, y1;
side_count=0;
y1=y[n];
x1=x[n];
bottomscan=y[n];
for (k=1; k<n+1; k++)
{
if (y1 ! =y[k]) {
side_count ++;
put_in_sides_list(side_count, x1, y1, x[k], y[k]);
}
else {
move ((short)x1, (short)y1);
line((short)x[k], (short)y1, status);
}
if (y[k] <bottomscan) bottomscan=y[k];
y1=y[k]; x1=x[k];
}
}
void update_first_and_last(count, scan)
int count, scan;
{
while((sides[last_s+1]. y_top>=scan) && (last_s <count)) last_s ++;
while(sides[first_s]. delta_y = = 0) first_s ++;
}
void swap(x, y)
EACH_ENTRY x, y;
{
int i_temp;
float f_temp;
i_temp=x.y_top; x.y_top=y.y_top; y.y_top=i_temp;
f_temp=x.x_int; x.x_int=y.x_int; y.x_int=f_temp;
i_temp=x.delta_y; x.delta=y.delta_y; y.delta_y=i_temp;
f_temp=x.x_change_per_scan; x. x_change_per_scan=y. x_change_per_scan; y.x.
change_per_scan=f_temp;
}
void sort_on_x(entry, first_s)
int entry, first_s;
{
while((entry > first_s) && (sides[entry]. x_int < sides[entry-1]. x_int))
{
swap (sides[entry], sides[entry-1]);
entry - -;
}
}
void process_x_intersections(scan, first_s, last_s)
int scan, first_s, last_s;
{
int k;
x_int_cout=0;
for(k=first_s; k<last_s+1; k++)
{
if(sides[k]. delta_y >0) {
x_int_count ++;
sort_on_x(k, first_s);
}
}
}
void draw_lines(scan, x_int_count, index)
int scan, x_int_count, index;
{
int k, x, x1, x2;
for (k=1; k< (int) (x_int_count/2+1.5); k++)
{
while(sides[index]. delta_y = = 0) index ++;
x1=(int)(sides[index]. x_int +0.5);
index ++;
while(sides[index].delta_y = = 0) index ++;
x2 = (int) (sides [index]. x_int +0.5);
move((short)x1, (short)scan);
line((short)x2, (short)scan, status);
index ++;
}
}
void update_sides_list( )
{
int k;
for (k=first_s; k<last_s +1; k++)
{
if(sides[k].delta_y >0)
{
sides[k].delta_y - -;
sides[k]. x_int - = sides[k]. x_change_per_scan;
}
}
}
程序2.3.1 扫描线填色程序
1、sort_on_bigger_y子程序的主要功能是按照输入的多边形，建立起活性边表。操作步骤是：对每条边加以判断：如非水平边则调用put_in_side_list子程序放入活性边来；如是水平边则直接画出。
2、put_in_sides_list子程序的主要功能是将一条边存入活性边表之内。操作步骤是：对该边判别是否左顶点或右顶点，如果将入边之终点删去，按照y_top的大小在活性边表中找到该点的合适位置，在该边的位置中填入数据。
3、update_first_and_last子程序的主要功能是刷新活性边表的first和last两根指针的所指位置，以保证指针指出激活边的范围。
4、process_x_intersections子程序的主要功能是对活性边表中的激活边（即位于first和last之间的，并且? y? 0的边）按照x_int的大小排序。操作步骤是：从first到last，对每一根? y? 0的边，调用sort_on_x子程序排入活性边表中合适位置。
5、sort_on_x子程序主要功能是将一条边side[entry]，在活性边表的first到entry之间按x_int的大小插入合适位置。操作步骤是：检查位于entry的边的x_int是否小于位置entry-1的边的x_int，如是，调用swap子程序交换两条边的彼此位置。
6、swap子程序的主要功能是交换活性边表中两条相邻位置边的彼此位置。
7、draw_lines子程序的主要功能是在一条扫描线位于多边形内的部分，填上指定的色彩。操作步骤是：在活性边表的激活边范围内，依次取出Δy¹ 0两边的x_int，作为两个端点（x1, scan），(x2, scan)，画一条水平线。
8、update_sides_list子程序的主要功能是刷新活性边表内激活边的值：Δy=Dy-1
x_int=x_int_x_chang_per_scan；
-
2.3 区域填充算法
2007-04-07 10:43:25
2.3 区域填充算法
2.3.1 基础知识
区域填充即给出一个区域的边界，要求对边界范围内的所有象素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色，本节中我们就以此为例讨论区域填充算法。
多边形填色即给出一个多边形的边界，要求对多边形边界范围的所有象素单元赋予指定的色代码。要完成这个任务，一个首要的问题，是判断一个象素是在多边形内还是外。数学上提供的方法是“扫描交点的奇偶数判断”法：
1、将多边形画在纸上。
2、用一根水平扫描线自左而右通过多边形而与多边形之边界相交。扫描线与边界相交奇次数后进入该多边形，相交偶次数后走出该多边形。图2.3.1示出这类情况：扫描线与多边形相交四点。相交a点之后入多边形；交b点（第2交点）之后出多边形；交c点（第3交点）之后又入多边形；交d点（第4交点）之后又出多边形。
上述方法似乎能完满地解决问题，但事实并非如此，因为直线在光栅化后变成了占有单位空间的离散点。图2.3.1中的A点处和B、C处，在光栅化后变成图2.3.2所示的情况。此时，使用上述判断法则，在A、B、C处发现错判现象。在A处，扫描线通过一点后以为入多边形，其实此时已出多边形。结果是在A点之后的扫描线段上全都错误地填上色。在B和C处，因为光栅化后，使得扫描线通过交点的个数发生变化而同样导致填色错误。因此，原始的奇偶判断方法需要加以周密地改善，才能成为计算机中实用的填色算法。
图2.3.1 图2.3.2
填色算法分为两大类：
1、扫描线填色（Scan-Line Filling）算法。这类算法建立在多边形边边界的矢量形式数据之上，可用于程序填色，也可用交互填色。
2、种子填色（Seed Filling）算法。这类算法建立在多边形边边界的图象形式数据之上，并还需提供多边形界内一点的坐标。所以，它一般只能用于人机交互填色，而难以用于程序填色。
-
2.2.2 圆的Bresenham算法
2007-04-07 10:42:40
2.2.2 圆的Bresenham算法
设圆之半径为r。先考虑圆心在（0,0），并从x=0, y=r开始的顺时针方向的1/8圆周的生成过程。在这种情况下，x每步增加1，从x=0开始，到x=y结束。即有：
xi+1=xi+1
相应的yi+1则在两种可能中选择：
yi+1=yi，或者yi+1=yi-1
选择的原则是考察精确值y靠近yi还是靠近yi-1（图2.2.2），计算式为：
y2=r2-(xi+1)2
d1=yi2-y2
=yi2-r2+(xi+1)2
d2=y2-(yi-1)2
=r2-(xi+1)2-(yi-1)2
图2.2.2 y的位置
令pi=d1-d2，并代入d1, d2，则有
pi=2(xi+1)2+yi2+(yi-1)2-2r2 (2.2.1)
pi称为误差。如果pi<0则yi+1=yi，否则yi+1=yi-1。pi的递归式为：
pi+1=pi+4xi+6+2(yi2+1-yi2)-2(yi+1-yi) (2.2.2)
pi的初值由式（2.6）代入xi=0, yi=r而得
p1=3-2r (2.2.3)
根据上面的推导，圆周生成算法思想为：
1、求误差初值，p1=3-2r; i=1；画点(0, r)；
2、求下一个光栅位置：
xi+1=xi+1；
if pi<0 则yi+1=yi；
否则yi+1=yi-1；
3、画点（xi+1, yi+1）
4、计算下一个误差：
if pi<0 则pi+1=pi+4xi+6；
否则 pi+1=pi+4(xi-yi)+10；
5、i=i+1; if x=y则end；否则返2。
虽然式（2.2.2）式表示pi+1的算法似乎很复杂，但因为yi+1只能取值yi或yi-1，因此在算法中，第4步的算式变得很简单，只须作加法和4的乘法。因此圆的Bresenham算法运行速度也是很快的，并适宜于硬件实现。
圆的Bresenham算法的程序实现见程序2.2.1。
circle (xc, yc, radius, c)
int xc, yc, radius, c;
{
int x, y, p;
x=0;
y=radius;
p=3-2*radius;
while (x<y){
plot_circle_points(xc, yc, x, y, c);
if (p<0) p=p+4*x+6;
else{
p=p+4*(x-y)+10;
y-=1;
}
x+=1;
}
if (x= =y)
plot_circle_points(xc, yc, x, y, c);
}
plot_circle_points(xc, yc, x, y, c)
int xc, yc, x, y, c;
{
set_pixel(xc+x, yc+y, c);
set_pixel(xc+x, yc+y, c);
set_pixel(xc+x, yc-y, c);
set_pixel(xc-x, yc-y, c);
set_pixel(xc+y, yc+x, c);
set_pixel(xc-y, yc+x, c);
set_pixel(xc+y, yc-x, c);
set_pixel(xc-y, yc-x, c);
}
程序2.2.1 Bresenham的圆生成算