CS-184: Computer GraphicsLecture #10: Scan Conversion Prof. James O’BrienUniversity of California, BerkeleyV2011-F-09-1.0With additional slides based on those of Maneesh Agrawala 2Today•2D Scan Conversion•Drawing Lines•Drawing Curves•Filled Polygons•Filling Algorithms3Drawing a Line•Basically, its easy... but for the details•Lines are a basic primitive that needs to be done well...4Drawing a Line•Basically, its easy... but for the details•Lines are a basic primitive that needs to be done well...From “A Procedural Approach to Style for NPR Line Drawing from 3D models,”by Grabli,!Durand, Turquin, Sillion5Drawing a Line6Drawing a Line7Drawing a Line•Some things to consider•How thick are lines?•How should they join up?•Which pixels are the right ones?For example:8Drawing a LineInclusiveEndpoints9Drawing a Liney = m · x + b, x 2 [x1, x2]m =y2 y1x2 x1b = y1 m · x110Drawing a LineΔx = 1Δy = m · Δxx=x1y=y1while(x<=x2) plot(x,y) x++ y+=Dy11Drawing a LineΔx = 1Δy = m · ΔxAfter rounding12Drawing a LineΔx = 1Δy = m · ΔxAccumulation ofroundoff errorsHow slow is float-to-int conversion?y+= Δy13Drawing a Line|m|1|m| > 114Drawing a Linevoid drawLine-Error1(int x1,x2, int y1,y2) ! float m = float(y2-y1)/(x2-x1) int x = x1 float y = y1 while (x <= x2) setPixel(x,round(y),PIXEL_ON) x += 1 y += mNot exact mathAccumulates errors15No more roundingDrawing a Linevoid drawLine-Error2(int x1,x2, int y1,y2) ! float m = float(y2-y1)/(x2-x1) int x = x1 int y = y1 float e = 0.0 while (x <= x2) setPixel(x,y,PIXEL_ON) x += 1 e += m if (e >= 0.5) y+=1 e-=1.016Drawing a Linevoid drawLine-Error3(int x1,x2, int y1,y2) ! int x = x1 int y = y1 float e = -0.5 while (x <= x2) setPixel(x,y,PIXEL_ON) x += 1 e += float(y2-y1)/(x2-x1) if (e >= 0.0) y+=1 e-=1.017Drawing a Linevoid drawLine-Error4(int x1,x2, int y1,y2) ! int x = x1 int y = y1 float e = -0.5*(x2-x1) // was -0.5 while (x <= x2) setPixel(x,y,PIXEL_ON) x += 1 e += y2-y1 // was /(x2-x1) if (e >= 0.0) // no change y+=1 e-=(x2-x1) // was 1.018Drawing a Linevoid drawLine-Error5(int x1,x2, int y1,y2) ! int x = x1 int y = y1 int e = -(x2-x1) // removed *0.5 while (x <= x2) setPixel(x,y,PIXEL_ON) x += 1 e += 2*(y2-y1) // added 2* if (e >= 0.0) // no change y+=1 e-=2*(x2-x1) // added 2*19Drawing a Linevoid drawLine-Bresenham(int x1,x2, int y1,y2) ! int x = x1 int y = y1 int e = -(x2-x1) while (x <= x2) setPixel(x,y,PIXEL_ON) x += 1 e += 2*(y2-y1) if (e >= 0.0) y+=1 e-=2*(x2-x1) FasterNot wrong|m|1x1 x220Drawing Curvesy = f (x)Only one value of y for each value of x...21Drawing Curves•Parametric curves•Both x and y are a function of some third parametery = f (u)x = f (u)x = f(u)u 2 [u0...u1]22Drawing Curvesx = f(u)u 2 [u0...u1]23•Draw curves by drawing line segments•Must take care in computing end points for lines•How long should each line segment be?Drawing Curvesx = f(u)u 2 [u0...u1]24•Draw curves by drawing line segments•Must take care in computing end points for lines•How long should each line segment be?•Variable spaced pointsDrawing Curvesx = f(u)u 2 [u0...u1]25Drawing Curves•Midpoint-test subdivision|f(umid) l(0.5)|26Drawing Curves•Midpoint-test subdivision|f(umid) l(0.5)|27Drawing Curves•Midpoint-test subdivision|f(umid) l(0.5)|28Drawing Curves•Midpoint-test subdivision•Not perfect•We need more information for a guarantee...|f(umid) l(0.5)|29Filled Polygons30Filled Polygons31Filled Polygons32Filled Polygons33Filled Polygons34Filled Polygons35Filled Polygons36Filled PolygonsTreat (scan y = vertex y) as (scan y > vertex y)37Filled PolygonsHorizontal edges38Filled PolygonsHorizontal edges39•“Equality Removal” applies to all vertices•Both x and y coordinatesFilled Polygons40•Final result:Filled Polygons41•Who does this pixel belong to?Filled Polygons12345642Drawing a Line•How thick?•Ends?ButtRoundSquare43Drawing a Line•Joining?UglyBevelRound Miter44Inside/Outside TestingThe PolygonNon-exteriorNon-zero winding ParityOptimize for Triangles•Spilt triangle into two parts•Two edges per part•Y-span is monotonic•For each row•Interpolate span•Interpolate barycentric coordinates4546Flood Fill47Flood FillSpan-Based AlgorithmDefinition: a run is a horizontal span of identically colored pixels1. Start at pixel “s”, the seed. 2. Find the run containing “s” (“b” to “a”). 3. Fill that run with the new color. 4. Search every pixel above run, looking for pixels of interior color 5. For each one found,6. Find left side of that run (“c”), and push that on a stack. 7. Repeat lines 4-7 for the pixels below (“d”). 8. Pop stack and repeat procedure with the new seedThe algorithm finds runs ending at “e”, “f”, “g”, “h”, and
View Full Document