1、1Attributes of Geometric Primitives幾何圖元的屬性2Outlinen(Hearn & Baker, P141: Chapter 4)n1. Fill-Area （4.10,4.13 P159-162. P163-167）n2. Antialiasing （4.17 P175-182）31. Area Fill Algorithms(區域填充算法)( Hearn & Baker, Section 4-10/13, P159-162. P163-167)4Area FillnFill or colorize a bounded area using

2、 a color or patternnExamples: bar chart, surfaces, solid objects, etc.5Description of AreanThe description of the area to be filled is given geometrically:n1. by edges, lines, polygons, circles, etc. (邊界定義區域, boundary-defined)n2. by a set of pixels defining a boundary (內部定義區域，interior-defined)6Comme

3、nts on Filling AlgorithmsnTechniques for rastering a polygon or an area:3. Scan-line Seed Fill Method （掃描線種子填充算法）（掃描線種子填充算法）2. Seed fill method（種子填充算法）（種子填充算法）1. Scan-line method(掃描線填充算法）掃描線填充算法） 自學自學7Scan-line filling methods (掃描線填充算法)8Scan-line methods (掃描線填充算法)nWorks row by row from top to bottom

4、nA pixel inside the current scan line is only drawn if it is located inside the polygon.逐點判斷法逐點判斷法 判斷點在多邊形的內外關系判斷點在多邊形的內外關系: 射線法9如何區分點在多邊形的內部與外部？n射線法n比較常用n從一點p引射線，如果與多邊形邊界交點數為偶數，則p在多邊形外，否則在多邊形內部n如果交點為頂點，需要特別處理n通常射線就是掃描線10Scan-line methodsnWorks for geometrically as well as pixel-wise defined areasnG

5、reedy approach very slow! Improvements possible by exploiting coherence! (連貫性連貫性):11Scan-line methodsnThe approach is based on scan-line coherence (連貫性連貫性):nNeighboring pixels are very likely to get the same intensity/color values assigned.nThe pixel characteristics, i.e. color/intensity values, onl

6、y change where an edge of the polygon intersects the scan line,n i.e. the part of the scan-line between two intersection points is either completely inside or completely outside of the polygon. (掃描線的連貫性)12Scan-line methods: ExampleExample: Scan line y=2: - intersection with polygon at x = 1,8 - we c

7、an subdivide the scan line into 3 sections: x8: outside the polygon13Scan-line methods: ExampleExample:Scan line y=4: - intersection with polygon at x = 1,4,6,8 - we can subdivide the scan line into 5 sections: x1: outside the polygon1x4: inside the polygon 4x8: outside the polygon14Scan-line method

8、snSingularities are Problematic: ni.e. locations where the scan line intersects with a vertex of the polygon. consider local extremes15Local extremes of PolygonnDefinition of Local extremes: nthose y-values of the corner of the polygon where these values are greater or smaller than both vertices (wi

9、th respect to the y-value) at the opposite side of the edge.nDistinguish two cases:- If the vertex is a local extreme, the intersection counts twice- If the vertex is not local extreme, the intersection counts once only16Scan-line methodsnThe simple ordered edge list algorithm (有序邊表算法)nMethod: prepr

10、ocessing + scan conversion17Ordered Edge List AlgorithmnPreprocessing(1) Determine for every edge of the polygon the intersections with the scan lines at the pixel centers; ignore horizontal edges.(2) Store every intersection (x, y) in a list.(3) Sort list from top to bottom, left to right.18Ordered

11、 Edge List AlgorithmnScan conversion(1) Consider pairs of subsequent intersections (x1, y1) and (x2, y2) in the list, i.e. list element 1 and 2, list element 3 and 4, )(2) Due to the preprocessing step, we know that for every scan line y: y=y1=y2, x1x2(3) Draw all pixels along the scan line y for wh

12、ich:x1xx2 for every integer number x.19Example: Preprocessing 20Example： Scan Conversion21Seed fill methods (種子填充算法種子填充算法)22Seed fill methods (種子填充算法種子填充算法)nSeed fill methods fill the area bounded by the polygon starting from an initial pixel (seed) and are suitable for pixel-wise defined areas, hen

13、ce also for raster displays.seed point23Connectedness of Areasn4-connected: connected horizontally or vertically （四連通）n8-connected: additionally diagonally connected （八連通）n(區域的連通性)24ConnectednessnDifference between 4- and 8-connectn連通性： 4連通可看作8連通區域，但對邊界有要求不同n依據區域內點能否訪問到區域外的點，對邊界的要求是:n4連通區域，邊界只要8連通即可

14、n8連通區域，邊界必須是4連通n例：如右圖（1）4連通區域，邊界為像素（2）8連通區域，邊界為和像素25Examples for 4- and 8-connected26n4 directions of movementnare defined by boundarynFILO/LIFONote: some pixels may be stored in the stack (and also colored) multiple times.Simple Seed Fill Algorithm27 void FloodFill4 (int x, int y, int new, int old)

15、 int color; getPixel (x, y, color); if (color = old) setPixel (x, y); FloodFill4 (x+1, y, new, old); / right FloodFill4 (x, y+1, new, old); / up FloodFill4 (x1, y, new, old); / left FloodFill4 (x, y1, new, old); / down Simple Flood-Fill Algorithm28Seed fill methods: Example-1 (numbers indicate locat

16、ion of pixels within the stack)29Seed fill methods: Example-1 (numbers indicate location of pixels within the stack)travel: RULDstack: FILOsome pixels may be stored in the stack (and also colored) multiple times.30Seed fill methods: Example-2narea with hole315. Antialiasing (反走樣)(Hearn & Baker,

17、Section 4-17, P175-182)32Aliasing and Antialiasingnwhat is aliasing? nwhat is the reason for aliasing?nwhat can we do against it?33AliasingnGenerally, aliasing effects are erroneous reconstruction of a (continuous) signal due sampling rate with a too low frequency (see also Nyquist theorem).n用離散量(像素

18、)表示連續的量(圖形)而引起的失真，稱為走樣走樣或稱為混淆混淆。34Reasons for aliasingerrors that are caused by the discretization of analog data to digital data too bad resolution too few colors too few images/sec geometric errors numeric errors35AliasingnThe term aliasing in the area of computer graphics is used, besides visual

19、effects resulting from the above (e.g. aliasing when rendering a checker board), to describe visual artifacts resulting from the process of scan conversion. (e.g. stair casing when drawing diagonal lines).36AliasingnAliasing artifacts in computer graphicsnTexture artifacts (e.g. checker board)nStair

20、 casing artifacts when rastering curves jagged linesnDisappearance of objects which are smaller than a pixelnDisappearance of small, skinny objectsnLoss of detail in complex imagesn“Flipping” small objects during motion / animation37AliasingnStair casing artifacts, jagged edgesThe previously discuss

21、ed techniques for rastering straight lines and curves result in stair casing artifacts (left) since it is only possible to draw points at fixed raster locations. These locations are generally not identical to the real/ideal locations of these points.階梯狀的、鋸齒狀的38Various Aliasing Effects39Aliasing from

22、 too few Colorsartificial color borders can appear40Aliasing in Animationsnjumping imagesnworming41AntialiasingnAntialiasing (反走樣反走樣) methods are techniques (e.g. over-sampling, filtering) that try to minimize the aliasing effect.nEliminating the aliasing effect is often NOT possible (already from a

23、 theoretical point of view).42Shannon Sampling Theorem43Shannon Sampling Theorem44Antialiasing: Nyquist Sampling Frequency45Solutions against Aliasing?n1. improve the devicesnhigher resolutionnmore color levelsnfaster image sequencen2. improve the images = antialiasingnpost-processingnpre-filterings

24、oftwareexpensive 46Antialiasing Strategiesnsupersampling straight-line segmentsnarea sampling straight-line segmentsnfiltering techniquesncompensating for line-intensity differencesnantialiasing area boundariesn(adjusting boundary pixel positions)nadjusting boundary pixel intensity47Antialiasing: Su

25、persampling LinesnSupersampling (超級采樣)48Antialiasing: Supersampling Lines49Antialiasing: Area Sampling Linesncalculate the pixel coverage exactlyncan be done with incremental schemes unweighted area sampling (非加權區域采樣) weighted area sampling (加權區域采樣)50Unweighted Area Sampling nSetting intensity propo

26、rtional to the amount of area covered. nthe intensities of neighboring pixels change continuously51Unweighted Area Sampling n兩點認識兩點認識:n(1) 像素不是點，一個小區域，形狀由硬件決定(如正方形)；n(2) 直線有寬度。n掃描轉換時兩點假設掃描轉換時兩點假設:n(1) 象素是數學上抽象的點，它的面積為0，它的亮度由覆蓋該點的圖形的亮度所決定；n(2) 直線段是數學上抽象直線段，它的寬度為0。n反走樣方法反走樣方法: 把像素看作一個平面區域進行采樣n(1) 將直線段

27、看作具有一定寬度的狹長矩形；n(2) 當直線段與像素有交時，求出兩者相交區域的面積；n(3) 根據相交區域的面積，確定該象素的亮度值。相鄰兩個象素的灰度之間有一個平緩的過渡，淡化了鋸齒狀的邊界。52Weighted Area Samplingn權函數： 或經驗值，可自定義；n直線與像素相交，相交區域為A，則直線對象素的亮度的貢獻為：dAYXWA),()2exp(21),(222yxyxWW(X,Y)=1：非加權情形。53Weighted Area Sampling加權區域采樣算法（直線段情形加權區域采樣算法（直線段情形）：）：n求直線段與像素的相交區域A；n計算 的值；n用上面的值乘以像素的最大灰度值，即為像素的顯示灰度值。dAYXWA),(54Weighted Area Sampling加權區域采樣的離散算法：加權區域采樣的離散算法：n分割像素成n個子像素Ai, 面積為 1/n，每個子像素對原像素的亮度的貢獻為 將各權值保存在一張加權表中。n求所有子像素中心落在直線段內的子像素集；n計算這些子像素對原像素亮度的和 dAYXWwiAi),(iw例：加權表的取法例：加權表的取法wwwwwwwww12345678911612124