3.5 Region Filling Region Filling is a process of “coloring in” a definite image area or region. 2019/4/19

Definition of regions Defined at the pixel level Boundary-defined regions: to describe the region in terms of the boundary pixels that outline the region. (boundary fill algorithm ) Interior-defined region: to describe the region in terms of the totality of pixels that comprise it. (flood fill algorithm) Defined at the geometric level: polygonal region 2019/4/19

4-connected Vs. 8-connected Which pixels are considered connected to each other to form a “continuous” boundary. Two ways 4-connected: a pixel may have up to four neighbors. 8-connected: a pixel may have up to eight neighbors. 2019/4/19

3.5.1 Boundary-fill algorithm The algorithm is to start at a point inside a region and paint the interior outward toward the boundary. A boundary-fill procedure accepts as input the coordinates of an interior point(x,y), a fill color, and a boundary color. 2019/4/19

algorithm Steps: Starting from (x,y), the procedure tests neighboring positions to determine whether they are of the boundary color or whether they have been painted with the fill color. If not, they are painted with the fill color, and their neighbors are tested. This process continues until all pixels up to the boundary color for the area have been tested. 2019/4/19

4-connected boundary-fill algorithm: void boundaryFill4 (int x, int y, int fill, int boundary) { int current; current = getpixel (x, y); if ((current != boundary) && (current != fill)) setcolor (fill) ; setpixel (x, y); boundaryFill4 (x+l, y, fill, boundary); // right boundaryFill4 (x, y+l, fill, boundary);//above boundaryFill4 (x-1, y, fill, boundary);//left boundaryFill4 (x, y-1, fill, boundary);//below } 2019/4/19

If 不成立 BF(4, 1, G, R) If 不成立 If 成立 (3, 1) →Green ② BF(2, 1, G, R) Current=Red If 不成立 BF(4, 1, G, R) Current=Green If 不成立 Current =White If 成立 (3, 1) →Green ② BF(2, 1, G, R) BF(2, 1, G, R) Current =White If 成立 (2, 1) →Green ① BF(3, 1, G, R) Current=White If 成立 (3, 2) →Green ③ BF(3, 2, G, R) BF(1, 1, G, R) BF(2, 2, G, R) BF(3, 0, G, R) BF(2, 0, G, R) 2019/4/19

If 不成立 If 不成立 BF(4, 2, G, R) BF(3, 2, G, R) If 成立 (2, 2) →Green ④ ⑤ Current=Red If 不成立 Current=Green If 不成立 BF(4, 2, G, R) BF(3, 2, G, R) Current=White If 成立 (2, 2) →Green ④ Current=White If 成立 (1, 2) →Green ⑤ BF(1, 2, G, R) BF(2, 2, G, R) (3, 2) →Green ③ BF(2, 3, G, R) BF(3, 3, G, R) BF(2, 1, G, R) BF(3, 1, G, R) 2019/4/19

If 不成立 BF(2, 2, G, R) BF(0, 2, G, R) (1, 2) →Green ⑤ If 不成立 Current=Green If 不成立 BF(2, 2, G, R) Current=Red If 不成立 (1, 2) →Green ⑤ BF(0, 2, G, R) Current=Red If 不成立 BF(1, 3, G, R) Current=White If 成立 (1, 1) →Green ⑥ BF(1, 1, G, R) 2019/4/19

If 不成立 If 不成立 BF(4, 2, G, R) BF(3, 2, G, R) ⑤ If 成立 (2, 2) →Green ④ Current=Red If 不成立 Current=Green If 不成立 BF(4, 2, G, R) BF(3, 2, G, R) Current=White If 成立 (1, 2) →Green ⑤ Current=White If 成立 (2, 2) →Green ④ BF(1, 2, G, R) BF(2, 2, G, R) (3, 2) →Green ③ Current=Red If 不成立 Current=Red If 不成立 BF(2, 3, G, R) BF(3, 3, G, R) Current=Green If 不成立 Current=Green If 不成立 BF(2, 1, G, R) BF(3, 1, G, R) 2019/4/19

If 不成立 BF(4, 1, G, R) If 成立 (3, 1) →Green ② If 不成立 BF(2, 1, G, R) Current=Red If 不成立 BF(4, 1, G, R) Current =White If 成立 (3, 1) →Green ② Current=Green If 不成立 BF(2, 1, G, R) BF(3, 1, G, R) BF(2, 1, G, R) Current =White If 成立 (2, 1) →Green ① Current=White If 成立 (3, 2) →Green ③ BF(3, 2, G, R) Current=Green If 不成立 BF(1, 1, G, R) Current=Green If 不成立 Current=Red If 不成立 BF(2, 2, G, R) BF(3, 0, G, R) Current=Red If 不成立 BF(2, 0, G, R) 2019/4/19

problems If some interior pixels are already displayed in the fill color, recursive boundary-fill algorithm may not fill regions correctly. This procedure requires considerable stacking of neighboring points. 2019/4/19

A modified method Step1: Starting from the initial interior point with this method, we first fill in the contiguous span of pixels on this starting scan line. Step2: We locate and stack starting positions for spans on the adjection scan lines. Step3: At each subsequent step, we unstack the next start position and repeat the process. 2019/4/19

2019/4/19

2019/4/19

2019/4/19

3.5.2 Flood-fill algorithm Boundary-fill algorithm: A filled area is defined within a signal color boundary. Flood-fill algorithm: A filled area is bordered by seveal different color regions. 2019/4/19

We can paint such areas by replacing a specified interior color instead of searching for a boundary color value. If the area we want to paint has more than one interior color, we can first reassign pixel values so that all interior points have the same color. 2019/4/19

4-connected Flood-fill algorithm Void floodFill4 (int x, int y, int fillColor, int oldColor) { if (getpixel (x, y) == oldcolor) setcolor (fillcolor); setpixel (x, y); floodFill4 (x+l, y, fillColor, oldColor); floodFill4 (x-1, y, fillColor, oldColor); floodFill4 (x, y+l, fillColor, oldColor); floodFill4 (x, y-1, fillColor, oldColor); } 2019/4/19

3.5.3 Polygon Filling Algorithms （多边形填充算法） Scan-line Approaches (扫描线算法) 2019/4/19

Scan-line Approaches Check pixel by pixel (逐点判断) P4 P0 P2 P1 P3 P6 P7 2019/4/19

Scan-line Approaches Improved P4 P0 P2 P1 P3 P6 P7 P5 2019/4/19 改进的逐点判断算法，利用包围盒减小计算量。 P7 P5 Improved 2019/4/19

Coherence Properties of the Scan-Line x y P0 P1 P2 P3 P4 P5 P6 P7 Coherence Properties of the Scan-Line (扫描线的连贯性) 2019/4/19

Coherence Properties of the Scan-Line x y P0 P1 P2 P3 P4 P5 P6 P7 Coherence Properties of the Scan-Line 2019/4/19

Coherence Properties of the Scan-Line x y P0 P1 P2 P3 P4 P5 P6 P7 Coherence Properties of the Scanline 2019/4/19

Polygon Filling Algorithms Scan-Line Approaches To determine the overlap intervals for scan lines that cross the area. They are typically used to fill polygons, circles, ellipses, and other simple curves. 2019/4/19

Scan-Line Approaches Scan-Line Polygon Fill Algorithm (扫描线多边形填充) 2019/4/19

Scan-Line Polygon Fill Algorithm x y P0 P4 P2 P1 P3 P7 P6 算法的基本思想：按从下到上的顺序求得各条扫描线的交点序列，并确定各条扫描线上位于多边形内的区段，将多边形表示成点阵形式。 P5 2019/4/19

Scan-Line Intersections at Polygon Vertices x y P0 P1 P2 P3 P4 P5 P6 P7 ? 当扫描线与多边形边界的交点是该多边形的顶点时，称该交点为奇点。 2019/4/19

Scan-Line Intersections at Polygon Vertices x y P0 P4 P2 P1 P3 ? P7 P6 P5 2019/4/19

Scan-Line Intersections at Polygon Vertices Local Extremum (局部极值) x y P0 P4 P2 P3 Otherwise P1 P7 P6 当奇点为极值点时，该点按两个交点计算；否则按一个交点计算。 P5 2019/4/19

Scan-Line Intersections at Polygon Vertices x y P0 P4 P2 P1 P3 P7 P6 P5 2019/4/19

Scan-Line Polygon Fill Algorithm Data Structure of Each Edge in the Edge Table X ΔX ΔY Next X ΔX ΔY 对于多边形的每条边求出与其相交的最高扫描线，把该边的信息存入与这一扫描线相对应的y桶。Y桶中的每条边记录：该边与对应扫描线交点的x值（该边在对应扫描线上的x截距），多边形边穿过的扫描线条数ΔY以及相邻扫描线之间的x增量ΔX 。 Take advantage of the edge coherence property. 2019/4/19

Sorted Edge Table(边分类表) x y A A (1,5) B (1,1) e1 e3 C (5,1) B C e2 2019/4/19

Sorted Edge Table 6 e1 e3 5 1 3 1.5 1 3 4 X ΔX ΔY Next 3 2 1 2019/4/19

Scan-Line Polygon Fill Algorithm Active Edge List-AEL（活化边表） Contains all edges crossed by the current scan line, with interative coherence calculations used to obtain the edge intersections 2019/4/19

Active Edge List AEL e1 e3 1 3 1.5 1 3 X ΔX ΔY Next 2019/4/19

Scan-Line Polygon Fill Algorithm x y A Y bucket 1 2 3 1 空行 D 2 XAD, ΔXAD, ΔYAD AD B XBA, ΔXBA, ΔYBA AB C 3 空行 AEL 扫描线3 XAD+ΔXAD, ΔXAD, ΔYAD-1 XAB+ΔXAB, ΔXAB, ΔYAB-1 2019/4/19

Scan-Line Polygon Fill Algorithm x y A Y bucket 1 2 3 1 空行 D 4 2 XAD, ΔXAD, ΔYAD AD B AB XBA, ΔXBA, ΔYBA C 3 空行 AEL 空行 4 扫描线4 XAD+2ΔXAD, ΔXAD, ΔYAD-2 XAB+2ΔXAB, ΔXAB, ΔYAB-2 2019/4/19

Scan-Line Polygon Fill Algorithm x y A Y bucket 1 2 3 1 空行 D 4 5 2 AD XAD, ΔXAD, ΔYAD B XBA, ΔXBA, ΔYBA AB C 3 空行 AEL 空行 4 5 CD XCD, ΔXCD, ΔYCD 扫描线5 XAD+3ΔXAD, ΔXAD, ΔYAD-3 XAB+3ΔXAB, ΔXAB, ΔYAB-3 XCD, ΔXCD, ΔYCD 2019/4/19

Scan-Line Polygon Fill Algorithm x y A Y bucket 1 2 3 1 空行 D 4 5 2 XAD, ΔXAD, ΔYAD AD B 6 XBA, ΔXBA, ΔYBA AB C 3 空行 AEL 空行 4 5 XCD, ΔXCD, ΔYCD CD 扫描线6 XCD+ΔXCD, ΔXCD, ΔYCD-1 6 BC XBC, ΔXBC, ΔYBC XAB+4ΔXAB, ΔXAB, ΔYAB-4 XBC, ΔXBC, ΔYBC 2019/4/19

Scan-Line Polygon Fill Algorithm x y A Y bucket 1 2 3 1 空行 D 4 5 2 XAD, ΔXAD, ΔYAD AD B 6 7 XBA, ΔXBA, ΔYBA AB C 3 空行 AEL 空行 4 5 XCD, ΔXCD, ΔYCD CD 扫描线7 XCD+2ΔXCD, ΔXCD, ΔYCD-2 6 XBC, ΔXBC, ΔYBC BC XBC+ΔXBC, ΔXBC, ΔYBC-1 空行 7 2019/4/19

Scan-Line Polygon Fill Algorithm x y A Y bucket 1 2 3 1 空行 D 4 5 2 XAD, ΔXAD, ΔYAD AD B 6 7 XBA, ΔXBA, ΔYBA AB C 8 3 空行 AEL 空行 4 5 CD XCD, ΔXCD, ΔYCD 扫描线8 XCD+3ΔXCD, ΔXAD, ΔYCD-3 6 XBC, ΔXBC, ΔYBC BC XBC+2ΔXBC, ΔXBC, ΔYBC-2 空行 7 8 空行 2019/4/19

Scan-Line Polygon Fill Algorithm x y A Y bucket 1 2 3 1 空行 D 4 5 2 XAD, ΔXAD, ΔYAD AD B 6 7 AB XBA, ΔXBA, ΔYBA C 8 9 3 空行 AEL 空行 4 5 XCD, ΔXCD, ΔYCD CD 扫描线9 XCD+4ΔXCD, ΔXCD, ΔYCD-4 6 BC XBC, ΔXBC, ΔYBC XBC+3ΔXBC, ΔXBC, ΔYBC-3 空行 7 8 空行 9 空行 2019/4/19