CS-184: Computer GraphicsLecture #9: Scan Conversion Prof. James O’BrienUniversity of California, BerkeleyV2009-F-09-1.02Today•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 ∈ [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 ∈ [u0...u1]22Drawing Curvesx = f(u)u ∈ [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 ∈ [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 ∈ [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
View Full Document