华中科技大学软件学院 Computer Graphics Wu Jianjie

华中科技大学软件学院 Chap3 Output Primitives Raster-scan displays Line-drawing algorithms Circle-generating algorithms Ellipse-generating algorithms Fill-Area primitives Character primitives Summary 1D1D 2D2D X=f1(t) Y=f2(t) X=f1(u,v) Y=f2(u,v) Linear Surface

华中科技大学软件学院 3.6 Fill-Area primitives Overview Polygon Scan Conversion Region Fill Polygon Scan Conversion vs Region Fill Inside-Outside Tests

华中科技大学软件学院 Overview Requirements  To describe an area, we should not only show its boundary, but also filled it with some solid color or pattern for raster-scan displays.  In 3D display, objects are often projected onto planes and are filled.  For random displays, section lines are usually used to represent a section.

华中科技大学软件学院 3.6 Overview

华中科技大学软件学院 3.6 Overview Procedure Here we only consider solid filling algorithms.  Determine which pixels need to be filled  Determine what color to be used to fill a region

华中科技大学软件学院 3.6 Overview An simple approach: Check each pixel to determine whether it is inside the polygon Disadvantages:L ow efficiency Improvement:Find bounding box of the polygon

华中科技大学软件学院 3.6 Overview Two basic approaches  Polygon Scan Conversion  Region Fill Deal with polygons without intersecting edges

华中科技大学软件学院 3.6 Overview Region FillPolygon Scan Conversion

华中科技大学软件学院 3.6 Overview Polygon Scan Conversion vs Region Fill Polygon Scan Conversion (Polygon- fill algorithms ） Region Fill(Seed-fill algorithms) Theory Determine the overlap intervals for scan lines that cross the area Start at en inside position and “paint” the interior, point by point, out to the boundary Applications Point-writing devices and Line-drawing devices Raster-scan displays

华中科技大学软件学院 3.6 Fill-Area primitives Overview Polygon Scan Conversion Region Fill Polygon Scan Conversion vs Region Fill Inside-Outside Tests

华中科技大学软件学院 Polygon Scan Conversion Definitions General Scan-line Polygon-Fill Algorithm( X- 扫描线算法 ) Improved Scan-line Polygon-Fill Algorithm( Y- 连贯线算法 ) Edge-Fill Algorithm( 边缘填充算法 )

华中科技大学软件学院 Polygon Scan Conversion Two representations of polygon in computer graphics  By a set of vertices ( 顶点表示 )  By a set of pixels ( 点阵表示 )

华中科技大学软件学院 Polygon Scan Conversion Vertex-MethodPixel-Method RepresentationBy a set of sorted vertices By a set of pixels that are within the boundary of the polygon Geometrically- important?(Y/N) Yes. Intuitive, Need little space for storage No. Lose a lot of geometry information Can be directly filled?(Y/N) NoYes. Easy to describe graphics using frame buffers

华中科技大学软件学院 Polygon Scan Conversion Two representations of polygon in computer graphics  By a set of vertices ( 顶点表示 )  By a set of pixels ( 点阵表示 ) Two basic approaches to fill an area  Polygon Scan Conversion  Region Fill

华中科技大学软件学院 Polygon Scan Conversion Definitions General Scan-line Polygon-Fill Algorithm( X- 扫描线算法 ) Improved Scan-line Polygon-Fill Algorithm( Y- 连贯线算法 ) Edge-Fill Algorithm( 边缘填充算法 )

华中科技大学软件学院 Polygon Scan Conversion General Scan-line Polygon-Fill Algorithm  Theory: First determine the intersection positions of the boundaries of the fill region with the screen scan lines. Then the fill colors are applied to each section of a scan line that lies within the interior of the fill region.

华中科技大学软件学院 Polygon Scan Conversion General Scan-line Polygon-Fill Algorithm  Procedure: Locate  Sort  Intersection pair  Fill color  Special cases ：  Scan-line intersections at polygon vertices  Boundary pixels

华中科技大学软件学院 Polygon Scan Conversion General Scan-line Polygon-Fill Algorithm  Disadvantages ： Low efficiency Improved Scan-line Polygon-Fill Algorithm( Y- 连贯线算法 )

华中科技大学软件学院 Polygon Scan Conversion Definitions General Scan-line Polygon-Fill Algorithm( X- 扫描线算法 ) Improved Scan-line Polygon-Fill Algorithm( Y- 连贯线算法 ) Edge-Fill Algorithm( 边缘填充算法 )

华中科技大学软件学院 Polygon Scan Conversion Improved Scan-line Polygon-Fill Algorithm  Only compute the intersection positions of the scan line with the active edges which are crossed by that scan line  Coherence properties of scan lines  Coherence properties of polygons  Theory

华中科技大学软件学院 Polygon Scan Conversion Improved Scan-line Polygon-Fill Algorithm  Coherence properties: certain properties of one part of a scene are related in some way to the properties in other parts of the scene  X k+1 =x k +1/k

华中科技大学软件学院 Polygon Scan Conversion Improved Scan-line Polygon-Fill Algorithm  Active Edge  Active Edge List: Contains all the information of polygon edges intersecting with scan lines (except horizontal edge)  Sorted Edge Table XYmax1/knext X-intercept value for the edge Maximum y value for that edge (To determine when to reject that edge) Inverse slope of the edge Pointer to next edge

华中科技大学软件学院 Polygon Scan Conversion Improved Scan-line Polygon-Fill Algorithm  Active Edge  Active Edge List  Sorted Edge Table: Contains all the information of polygon edges (except horizontal edge) necessary to process the scan lines X|y min Ymax1/knext X-intercept value ( at the lower vertex) for the edge Maximum y value for that edge (To determine when to reject that edge) Inverse slope of the edge Pointer to next edge

华中科技大学软件学院 Polygon Scan Conversion Active edge list when Y=8 xymax Δx next

华中科技大学软件学院 Polygon Scan Conversion Improved Scan-line Polygon-Fill Algorithm — Built of ET  Construct a list, the length of which is (y max -y min ),I.e. the maximum number of scan lines crossing the polygon. Each node of the list, called bucket, represent each scan line crossing the polygon;  Put information (Deal with special cases) of each edge into the bucket which corresponds to the minimum y value of that edge;  Data of each edge forms a node of the edge table;  In the same bucket, edges are sorted by x|y min from minimum to maximum, and if two edges have the same x|y min value, they are sorted by the value of 1/k

华中科技大学软件学院 Polygon Scan Conversion One method for implementing the adjustment to the vertex- intersection count is to shorten some polygon edges to split those vertices that should be counted as one intersection. Scan line y+1 Scan line y Scan line y-1 The y coordinate of the upper endpoint of the current edge is decreased by 1 The y coordinate of the upper endpoint of the next edge is decreased by 1

华中科技大学软件学院 Polygon Scan Conversion One method for implementing the adjustment to the vertex- intersection count is to shorten some polygon edges to split those vertices that should be counted as one intersection. Shorten the lower edge scan line y+1 scan line y+1 scan line y scan line y scan line y-1 scan line y-1 Shorten the upper edge Which is better?

华中科技大学软件学院 Polygon Scan Conversion Edge Table of Polygon

华中科技大学软件学院 Polygon Scan Conversion Edge Table of Polygon Scan line yB Scan line yC Scan line yE Scan line yD Scan line yA

华中科技大学软件学院 Polygon Scan Conversion Edge Table of Polygon scan line y C scan line y B scan line y A ABC C’ D E yCyCyCyC yByByByB yAyAyAyA 1 0 xCxCxCxC yByByByB 1/m CB xDxDxDxD y c’ 1/m DC xDxDxDxD yEyEyEyE 1/m DE xAxAxAxA yEyEyEyE 1/m AE xAxAxAxA yByByByB 1/m AB Edge Table : x y max 1/m next

华中科技大学软件学院 Polygon Scan Conversion Improved Scan-line Polygon-Fill Algorithm  Procedure:  Initialization: Build ET, Set AET to empty   Combine AET with edges of the first ET which is not empty   Take intersection-pairs out of AET and apply fill colors to each section   y i+1 =yi+1, x i+1 =xi+1/k, Compute and modify AET, combine edges in bucket y=yi+1, then sort and insert these edges into AET to form a new ET   If AET is not empty, go to (3), else go to end

华中科技大学软件学院 Polygon Scan Conversion Improved Scan-line Polygon-Fill Algorithm  Disadvantages  Maintain and sorting of various tables is much time consuming.  It can not easily realized by hardware. 边缘填充算法

华中科技大学软件学院 Polygon Scan Conversion Definitions General Scan-line Polygon-Fill Algorithm( X- 扫描线算法 ) Improved Scan-line Polygon-Fill Algorithm( Y- 连贯线算法 ) Edge-Fill Algorithm( 边缘填充算法 )

华中科技大学软件学院 Polygon Scan Conversion Edge-Fill Algorithm  Theory: Deal with each polygon edge in arbitrary order. For each edge, first compute the intersections of the edge with scan lines  then set values of the pixels that are right to the intersection and are above the scan line  If all polygon edges have been processed, go to end

华中科技大学软件学院 Polygon Scan Conversion Edge-Fill Algorithm

华中科技大学软件学院 Polygon Scan Conversion Edge-Fill Algorithm  Disadvantages: For complex graphics, each pixel may be processed several times which brings much more efforts to the algorithm than to Improved Scan-line Polygon-Fill Algorithm 栅栏填充算法 边标志算法

华中科技大学软件学院 3.6 Fill-Area primitives Two basic approaches  Polygon Scan Conversion  Region Fill

华中科技大学软件学院 3.6 Fill-Area primitives Overview Polygon Scan Conversion Region Fill Polygon Scan Conversion vs Region Fill Inside-Outside Tests

华中科技大学软件学院 Region Fill Definitions Boundary-Fill Algorithm Flood-Fill Algorithm

华中科技大学软件学院 Region Fill Region Fill refers to the process that starts at an inside position, called Seed point, and “paint” the interior, point by point, out to the boundary. This is particularly useful for filling areas with irregular borders

华中科技大学软件学院 Region Fill Two basic representations of regions  By boundary ( 边界表示 )  By interior points ( 内点表示 ) 4-connected

华中科技大学软件学院 Region Fill Two basic representations of regions 8-connected  By boundary ( 边界表示 )  By interior points ( 内点表示 )

华中科技大学软件学院 Region Fill Two basic representations of regions  By boundary ( 边界表示 )  By interior points ( 内点表示 ) Two basic approaches to fill an area  Boundary-Fill Algorithm  Flood-Fill Algorithm

华中科技大学软件学院 Region Fill Two methods for processing neighboring pixels from a current test position  4-connected  8-connected 4-connected area 8-connected area Q1:How to differ 4- connected from 8-connected?

华中科技大学软件学院 Region Fill Definitions Boundary-Fill Algorithm Flood-Fill Algorithm

华中科技大学软件学院 Region Fill Boundary-Fill Algorithm  Theory:The boundary of some region is specified in a single color, we can fill the interior of this region, pixel by pixel, until the boundary color is encountered  Inputs:  Coordinates of the seed  Boundary color  Fill color

华中科技大学软件学院 Region Fill Boundary-Fill Algorithm  Procedure: Starts from an interior point (x,y) and tests the color of neighboring positions. If a tested position is not displayed in the boundary color, its color is changed to the fill color and its neighbors are tested. This procedure continued until all pixels are processed up to the designated boundary color for the area  Interior and exterior boundaries can be specified at the same time  A recursive methods is used

华中科技大学软件学院 Region Fill void boundaryFill4( int x, int y, int fill, int boundary ) { int current=getPixel(x,y); if( (current != boundary) && (current != fill) ) { setColor( fill ); setPixel( x,y ); boundaryFill4( x+1, y, fill, boundary ); boundaryFill4( x-1, y, fill, boundary ); boundaryFill4( x, y+1, fill, boundary ); boundaryFill4( x, y-1, fill, boundary ); }

华中科技大学软件学院 Region Fill Boundary-Fill Algorithm  Properties: Can deal with areas with holes  Disadvantages  Encountering a pixel with the fill color can cause a recursive branch to terminate, leaving other interior pixels unfilled  Requires considerable stacking of neighboring points

华中科技大学软件学院 Region Fill Boundary-Fill Algorithm Solutions to disadvantages:  First change the color of any interior pixels that are initially set to the fill color before applying the boundary-fill procedure.  Fill horizontal pixel spans across scan lines, instead of proceeding to 4-connected or 8- connected neighboring points

华中科技大学软件学院 Region Fill Boundary-Fill Algorithm Filled Pixel Spans Stacked Positions Initial scan line with a filled pixel span, showing the position of the initial point (hollow) and the stacked positions for pixel spans on adjacent scan lines

华中科技大学软件学院 Region Fill Boundary-Fill Algorithm Filled pixel span on the first scan line above the initial scan line and the current contents of the stack Filled Pixel Spans Stacked Positions

华中科技大学软件学院 Region Fill Boundary-Fill Algorithm Filled pixel spans on the first two scan lines above the initial scan line and the current contents of the stack Filled Pixel Spans Stacked Positions

华中科技大学软件学院 Region Fill Boundary-Fill Algorithm Completed pixel spans for the upper –right portion of the defined region and the remaining stacked positions to be processed Filled Pixel Spans Stacked Positions

华中科技大学软件学院 Region Fill Definitions Boundary-Fill Algorithm Flood-Fill Algorithm

华中科技大学软件学院 Region Fill Flood-Fill Algorithm  Theory:Point such areas as bordered by several different color regions by replacing a specified interior color  Inputs:  Coordinates of the seed  Interior color  Fill color

华中科技大学软件学院 Region Fill Flood-Fill Algorithm  Procedure: Starts from a specified interior point (x,y) and reassign all pixel values that are currently set to a given interior color with the desired fill color.  A recursive methods is used

华中科技大学软件学院 Region Fill void floodFill4( int x, int y, int fillColor, int oldColor ) { if( getPixel(x,y)==oldColor ) { setColor( fillColor ); setPixel( x,y ); floodFill4 ( x+1, y, fill, boundary ); floodFill4 ( x-1, y, fill, boundary ); floodFill4 ( x, y+1, fill, boundary ); floodFill4 ( x, y-1, fill, boundary ); }

华中科技大学软件学院 Region Fill We can modify the above procedure to reduce the storage requirements of the stack by filling horizontal pixel spans, as discussed for the boundary-fill algorithm. I.e., stack only the beginning positions for those pixel spans having the value interiorColor

华中科技大学软件学院 Region Fill Limitations  For Boundary-fill Algorithms, 4-connected fill algorithm can only fill 4-connected fill area, and 8-connected fill algorithm can only fill 8-connected fill area  For Flood-fill Algorithms, 4-connected fill algorithm can only fill 4-connected fill area, and 8-connected fill algorithm can fill both 4-connected and 8-connected fill area Q2: Why?

华中科技大学软件学院 3.6 Fill-Area primitives Overview Polygon Scan Conversion Region Fill Polygon Scan Conversion vs Region Fill Inside-Outside Tests

华中科技大学软件学院 Comparison Polygon Scan Conversion and Region Fill can be inter-transformed under certain conditions  当已知顶点表示的多边形内一点作为种子点，并 用扫描转换直线段的算法将多边形的边界表示成 8 连 通区域后，多边形扫描转换问题便可转化为区域填充 问题。  若已知给定区域是多边形区域，并且通过一定的 方法求出它的顶点坐标，则区域填充问题便可转化为 多边形扫描转换问题。

华中科技大学软件学院 Comparison Differences between Polygon Scan Conversion and Region Fill  基本思想不同 —— 多边形扫描转换将多边形的顶点表 示转换成点阵表示；而区域填充只改变了区域的填充颜色， 未改变区域的表示方法。  对边界的要求不同 —— 多边形扫描转换中，多边形边 界可以不封闭；而区域填充时，要求 4 连通区域的边界是封 闭的 8 连通区域， 8 连通区域的边界为封闭的 4 连通区域。  基于的条件不同 —— 多边形扫描转换从多边形顶点信 息出发，利用连贯性填充；区域填充要求给定区域内一点 作为种子点，从该点根据连通性将新颜色扩散到整个区域。

华中科技大学软件学院 3.6 Fill-Area primitives Overview Polygon Scan Conversion Region Fill Polygon Scan Conversion vs Region Fill Inside-Outside Tests

华中科技大学软件学院 Inside-Outside Tests Standard polygons Polygons with intersecting edges Interior Exterior Interior

华中科技大学软件学院 Inside-Outside Tests Odd-even rule Nonzero winding number rule For complex shapes of polygons, a point be either be an interior point or an exterior point according to different rules

华中科技大学软件学院 Inside-Outside Tests Odd-even rule The number of line- segment crossed by the line is odd, the P is an interior point Attention:Be sure that the line path does not intersect any line-segment endpoints. p q

华中科技大学软件学院 Inside-Outside Tests Nonzero winding number rule Sort the vertices to turn edges to vectors  Set winding number to 0  Draw a line… If the winding number is nonzero, P is considered to be an interior point p q

华中科技大学软件学院 Chap3 Output Primitives Raster-scan displays Line-drawing algorithms Circle-generating algorithms Ellipse-generating algorithms Fill-Area primitives Character primitives Summary

华中科技大学软件学院 3.7 Character Primitives Letters, numbers and other characters can be displayed in a variety of sizes and styles Typefaces (or fonts) can be divided into  Serif  Sans serif Two representations are used for storing computer fonts  Bitmap font (raster font)  Outline font (stroke font)

华中科技大学软件学院 3.7 Character Primitives Bitmap fontOutline font Represen tations Set up a pattern of binary values on a rectangular grid Use straight-line and curve sections Display Form a pixel pattern of characters Explain stroke information of characters Propertie s Are the simplest to define and display Requires less storage, can be increased in size without distorting the character shapes Disadvan tages Require considerable storage space Takes more time to process the outline fonts, since they must be scan converted into the frame buffer

华中科技大学软件学院 Chap3 Output Primitives Raster-scan displays Line-drawing algorithms Circle-generating algorithms Ellipse-generating algorithms Fill-Area primitives Character primitives Summary

华中科技大学软件学院 3.8 Summary The output primitives discussed in this chapter provide the basic tools for constructing pictures with individual points, straight lines, curves, filled color areas and text  Requirements of line-generation algorithms?  DDA algorithm to locate pixel positions along a straight-line path: Theory, procedure and properties  Midpoint algorithm: Theory, procedure and properties

华中科技大学软件学院 3.8 Summary  Theory of three kinds of Parallel line algorithms  Be able to efficiently and accurately scan convert curves using Midpoint Algorithm  Improved Scan-line polygon-fill algorithm(y- 连贯线算 法 ):Theory, procedure, active edge list, edge table  Boundary-fill algorithm vs Flood-fill algorithm: 4- connected, 8-connected  Inside-Outside Test: Odd-even rule and nonzero winding-number rule  Two representations for storing computer fonts

华中科技大学软件学院 Homework for Today Q1:How to differ 4-connected from 8- connected? 4-connected area 8-connected area

华中科技大学软件学院 Homework for Today Q2:Explain such limitations  For Boundary-fill Algorithms, 4-connected fill algorithm can only fill 4-connected fill area, and 8-connected fill algorithm can only fill 8-connected fill area  For Flood-fill Algorithms, 4-connected fill algorithm can only fill 4-connected fill area, and 8-connected fill algorithm can fill both 4-connected and 8-connected fill area

华中科技大学软件学院 Homework for Today Q3: Using the Improved Scan-line Polygon-Fill Algorithm to fill a polygon Requirements:  Give the Edge Table of the polygon  Give the Active Edge List of the scan line: y=3  Give the intersection pair of the scan line: y=3

华中科技大学软件学院 Homework for Today x y y

华中科技大学软件学院 Thank you!