DOC PREVIEW
Berkeley COMPSCI 184 - Scan Conversion

This preview shows page 1-2-23-24 out of 24 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Berkeley COMPSCI 184 - Scan Conversion

Documents in this Course
Load more
Download Scan Conversion
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Scan Conversion and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Scan Conversion 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?