计算机图形学补充01：多边形填充算法.ppt

多边形填充
第三章:基本图形生成算法
直线生成
圆的生成
线宽与线型
实区域填充
图形反走样
4 区域填充
多边形填色:给出一个多边形边界,要求对多边形边界范围的所有像素单元赋予指定的颜色代码。
有序边表填充算法
边填充算法
简单种子填充算法
扫描线种子填充算法
4 区域填充
求交:I4, I3, I2, I1
排序:I1, I2, I3, I4
交点配对:(I1, I2), (I3, I4)
区间填色
扫描线填充算法
利用图形的空间连贯性和扫描线的连贯性
4 区域填充
扫描线填充(scan-line filling)算法
A
B
C
D
P1
P2
P3
P4
P5
P6
2
4
6
8
0
4 区域填充
有序边表填充算法
活化边表结点的数据结构
typedef struct tEdge
{ float x; /* 当前扫描线与边的交点的x值*/
float dx;
/*从当前扫描线到下一条扫描线之间的x增量*/
int ymax; /* 边所交的最高扫描线号*/
} Edge;
4 区域填充
①输入欲填充多边形的顶点数及其顶点坐标。这里,顶点数为实际顶点数加1,最后一个顶点坐标与第一个顶点坐标相同。
②计算所有多边形顶点坐标中y的最大值和最小值,以此作为扫描线的处理范围。
③对处理范围内的每条扫描线建立有序边表。
④对处理范围内的每条扫描线,重复下列步骤:
4 区域填充
;
,对该两个交点内的像素进行填充;
,即增加交点的x值和删除不再相交的边;
。
void ScanFill (t, POINT *pts, int color )
// cnt为多边形的顶点数,pts为顶点坐标数组
{ Edge * edges [ WINDOW_HEIGHT ], *active;
int i, scan, smax = 0, smin = 1024;
for (i = 0; i < cnt–1; i++) // 求smax和smin
{ if (smax < pts [i].y ) smax = pts [i].y;
if (smin > pts [i].y ) smin = pts [i].y;
}
for (scan = smin; scan <= smax; scan ++)
{ edges [scan] = (Edge *)malloc (sizeof (Edge));
edges [scan] –> next = NULL;
}
求扫描线的最大值最小值
初始化每条扫描线的边链表
BuildEdgeList (cnt, pts, edges); // 建立有序边表
active = new Edge; // 初始化活化边表
active –> next = NULL;
for (scan = smin; scan <= smax; scan++)
{ BuildActiveList (scan, active, edges);
if (active –> next)
{ FillScan (scan, active, color);
//填充当前扫描线
UpdateActiveList (scan, active);
//更新活化边表
ResortActiveList (active);
// 重排活化边表
}
}
}
扫描每条扫描线,求活化表