231多边形的扫描转换 多边形分为凸多边形、凹多边形、含内环的多边形 ①凸凸多边形 ②凹多边形③含内环的多边形 任意两顶点间的任意两顶点间的 连线均在多边形连线有不在多边 内 形内的部分 图23.1多边形的种类 2.3.1.1扫描线算法 扫描线多边形区域填充算法是按扫描线顺序,计算扫描线与多边形的相交区间,再用要求的颜色显示这 些区间的象素,即完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条 扫描线,多边形的填充过程可以分为四个步骤: (1)求交:计算扫描线与多边形各边的交点 (2)排序:把所有交点按x值递增顺序排序 (3)配对:第一个与第二个,第三个与第四个等等:每对交点代表扫描线与多边形的一个相交区间, (4)填色:把相交区间内的象素置成多边形颜色,把相交区间外的象素置成背景色。 P6(2,7) P4(118 B D P5(55) P1(2,2 P(5,1) 图2.3.2一个多边形与若干扫描线 为了提高效率,在处理一条扫描线时,仅对与它相交的多边形的边进行求交运算。我们把与当前扫描线 相交的边称为活性边,并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中,称此链表为活性边 表(AET) P6P1 P5P6 P4P5 P3P4 子·[207-.5H1.7一728-1081人 B△ x ymax (a)扫描线6的活性边表 P4P5 P3P4 |2|8-018∧ G (b)扫描线6的活性边表 图2.3.3活性边表(AE 计算机图形学第二章第22页共27页计算机图形学 第二章 第 22 页 共 27 页 2.3.1 多边形的扫描转换 多边形分为凸多边形、凹多边形、含内环的多边形。 ① 凸凸多边形： ② 凹多边形 ③ 含内环的多边形 任意两顶点间的 任意两顶点间的 连线均在多边形 连线有不在多边 内 形内的部分 图 2.3.1 多边形的种类 2.3.1.1 扫描线算法 扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这 些区间的象素，即完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条 扫描线，多边形的填充过程可以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按 x 值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间， （4）填色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。 图 2.3.2 一个多边形与若干扫描线 为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。我们把与当前扫描线 相交的边称为活性边，并把它们按与扫描线交点 x 坐标递增的顺序存放在一个链表中，称此链表为活性边 表(AET)。 (a)扫描线 6 的活性边表 (b)扫描线 6 的活性边表 图 2.3.3 活性边表(AET)