Slide 1AdminDemoRasterizing PolygonsSlide 5Convex ShapesSlide 7Decomposing Polys Into TrisRasterizing TrianglesRecursive Triangle SubdivisionRecursive Screen SubdivisionEdge WalkingEdge Walking: NotesSlide 14Edge EquationsSlide 16Slide 17Slide 18Using Edge EquationsSlide 20Computing a Bounding BoxComputing Edge EquationsSlide 23Computing Edge Equations: Numerical IssuesComputing Edge Equations: Numerical IssuesSlide 26Edge Equations: CodeOptimize This!Edge Equations: Speed HacksEdge Equations: Interpolating ColorSlide 31Edge Equations: Interpolating ColorTriangle Rasterization IssuesCS 445: Introduction to Computer GraphicsDavid LuebkeUniversity of VirginiaRasterization: TrianglesAdminCall rollClipping assignment!–Show Spring 2003 assignment–Needs to be adapted for this semesterIf this happens tonight, due in two weeks (March 1)Otherwise, due March 3.DemoVideosRasterizing PolygonsIn interactive graphics, polygons rule the worldTwo main reasons:–Lowest common denominator for surfacesCan represent any surface with arbitrary accuracySplines, mathematical functions, volumetric isosurfaces…–Mathematical simplicity lends itself to simple, regular rendering algorithmsLike those we’re about to discuss… Such algorithms embed well in hardwareRasterizing PolygonsTriangle is the minimal unit of a polygon–All polygons can be broken up into trianglesConvex, concave, complex–Triangles are guaranteed to be:PlanarConvex–What exactly does it mean to be convex?Convex ShapesA two-dimensional shape is convex if and only if every line segment connecting two points on the boundary is entirely contained.Convex ShapesWhy do we want convex shapes for rasterization?One good answer: because any scan line is guaranteed to contain at most one segment or span of a triangle–Another answer coming up later–Note: Can also use an algorithm which handles concave polygons. It is more complex than what we’ll present here!Decomposing Polys Into TrisAny convex polygon can be trivially decomposed into triangles–Draw itAny concave or complex polygon can be decomposed into triangles, too–Non-trivial!Rasterizing TrianglesInteractive graphics hardware commonly uses edge walking or edge equation techniques for rasterizing trianglesTwo techniques we won’t talk about much:–Recursive subdivision of primitive into micropolygons (REYES, Renderman)–Recursive subdivision of screen (Warnock)Recursive Triangle SubdivisionRecursive Screen SubdivisionEdge WalkingBasic idea: –Draw edges vertically–Fill in horizontal spans for each scanline–Interpolate colors down edges–At each scanline, interpolate edge colors across spanEdge Walking: NotesOrder vertices in x and y–3 cases: break left, break right, no breakWalk down left and right edges–Fill each span–Until breakpoint or bottom vertex is reachedAdvantage: can be made very fastDisadvantages: –Lots of finicky special cases–Tough to get right–Need to pay attention to fractional offsetsEdge Walking: NotesFractional offsets:Be careful when interpolating color values!Also: beware gaps between adjacent edgesEdge EquationsAn edge equation is simply the equation of the line containing that edge–Q: What is the equation of a 2D line?–A: Ax + By + C = 0–Q: Given a point (x,y), what does plugging x & y into this equation tell us?–A: Whether the point is:On the line: Ax + By + C = 0 “Above” the line: Ax + By + C > 0 “Below” the line: Ax + By + C < 0Edge EquationsEdge equations thus define two half-spaces:Edge EquationsAnd a triangle can be defined as the intersection of three positive half-spaces:A1x + B1y + C1 < 0A2x + B2y + C2 < 0A3x + B3y + C3 < 0A1x + B1y + C1 > 0A3x + B3y + C3 > 0A2x + B2y + C2 > 0Edge EquationsSo…simply turn on those pixels for which all edge equations evaluate to > 0:+++---Using Edge EquationsAn aside: How do you suppose edge equations are implemented in hardware?How would you implement an edge-equation rasterizer in software?–Which pixels do you consider?–How do you compute the edge equations?–How do you orient them correctly?Using Edge EquationsWhich pixels: compute min,max bounding boxEdge equations: compute from verticesOrientation: ensure area is positive (why?)Computing a Bounding BoxEasy to doSurprising number of speed hacks possible–See McMillan’s Java code for an exampleComputing Edge EquationsWant to calculate A, B, C for each edge from (xi, yi) and (xj, yj)Treat it as a linear system:Ax1 + By1 + C = 0Ax2 + By2 + C = 0Notice: two equations, three unknownsDoes this make sense? What can we solve?Goal: solve for A & B in terms of CComputing Edge EquationsSet up the linear system:Multiply both sidesby matrix inverse:Let C = x0 y1 - x1 y0 for convenience–Then A = y0 - y1 and B = x1 - x0 111100CBAyxyx01010110xxyyyxyxCBAComputing Edge Equations: Numerical IssuesCalculating C = x0 y1 - x1 y0 involves some numerical precision issues–When is it bad to subtract two floating-point numbers?–A: When they are of similar magnitudeExample: 1.234x104 - 1.233x104 = 1.000x101We lose most of the significant digits in result–In general, (x0,y0) and (x1,y1) (corner vertices of a triangle) are fairly close, so we have a problemComputing Edge Equations:Numerical IssuesWe can avoid the problem in this case by using our definitions of A and B:A = y0 - y1B = x1 - x0 C = x0 y1 - x1 y0 Thus:C = -Ax0 - By0or C = -Ax1 - By1Why is this better?Which should we choose?–Trick question! Average the two to avoid bias:C = -[A(x0+x1) + B(y0+y1)] / 2Edge EquationsSo…we can find edge equation from two verts. Given three corners C0, C1, C0 of a triangle, what are our three edges?How do we make sure the half-spaces defined by the edge equations all share the same sign on the interior of the triangle?A: Be consistent (Ex: [C0 C1], [C1 C2], [C2 C0])How do we make sure that sign is positive?A: Test, and flip if needed (A= -A, B= -B, C= -C)Edge Equations: CodeBasic structure of code:–Setup: compute edge equations, bounding box–(Outer loop) For each scanline in bounding box... –(Inner loop) …check each pixel on scanline, evaluating edge equations and drawing the pixel if all three are positiveOptimize
View Full Document
Unlocking...