Drawing TrianglesAdminRasterizing PolygonsSlide 4Convex ShapesSlide 6Decomposing Polys Into TrisRasterizing TrianglesRecursive Triangle SubdivisionRecursive Screen SubdivisionEdge WalkingEdge Walking: NotesSlide 13Edge EquationsSlide 15Slide 16Slide 17Using Edge EquationsSlide 19Computing a Bounding BoxComputing Edge EquationsSlide 22Computing Edge Equations: Numerical IssuesComputing Edge Equations: Numerical IssuesSlide 25Edge Equations: CodeOptimize This!Edge Equations: Speed HacksEdge Equations: Interpolating ColorSlide 30Edge Equations: Interpolating ColorTriangle Rasterization IssuesDrawing TrianglesCS 445/645Introduction to Computer GraphicsDavid Luebke, Spring 2003David Luebke 2 01/13/19Admin●Homework 1 graded, will post this afternoonDavid Luebke 3 01/13/19Rasterizing Polygons●In interactive graphics, polygons rule the world●Two main reasons:■Lowest common denominator for surfaces○Can represent any surface with arbitrary accuracy○Splines, mathematical functions, volumetric isosurfaces…■Mathematical simplicity lends itself to simple, regular rendering algorithms○Like those we’re about to discuss… ○Such algorithms embed well in hardwareDavid Luebke 4 01/13/19Rasterizing Polygons●Triangle is the minimal unit of a polygon■All polygons can be broken up into triangles○Convex, concave, complex■Triangles are guaranteed to be:○Planar○Convex■What exactly does it mean to be convex?David Luebke 5 01/13/19Convex Shapes●A two-dimensional shape is convex if and only if every line segment connecting two points on the boundary is entirely contained.David Luebke 6 01/13/19Convex Shapes●Why 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!David Luebke 7 01/13/19Decomposing Polys Into Tris●Any convex polygon can be trivially decomposed into triangles■Draw it●Any concave or complex polygon can be decomposed into triangles, too■Non-trivial!David Luebke 8 01/13/19Rasterizing Triangles●Interactive graphics hardware commonly uses edge walking or edge equation techniques for rasterizing triangles●Two techniques we won’t talk about much:■Recursive subdivision of primitive into micropolygons (REYES, Renderman)■Recursive subdivision of screen (Warnock)David Luebke 9 01/13/19Recursive Triangle SubdivisionDavid Luebke 10 01/13/19Recursive Screen SubdivisionDavid Luebke 11 01/13/19Edge Walking●Basic idea: ■Draw edges vertically■Fill in horizontal spans for each scanline■Interpolate colors down edges■At each scanline, interpolate edge colors across spanDavid Luebke 12 01/13/19Edge Walking: Notes●Order vertices in x and y■3 cases: break left, break right, no break●Walk down left and right edges■Fill each span■Until breakpoint or bottom vertex is reached●Advantage: can be made very fast●Disadvantages: ■Lots of finicky special cases■Tough to get right■Need to pay attention to fractional offsetsDavid Luebke 13 01/13/19Edge Walking: Notes●Fractional offsets:●Be careful when interpolating color values!●Also: beware gaps between adjacent edgesDavid Luebke 14 01/13/19Edge Equations●An 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 < 0David Luebke 15 01/13/19Edge Equations●Edge equations thus define two half-spaces:David Luebke 16 01/13/19Edge Equations●And 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 > 0David Luebke 17 01/13/19Edge Equations●So…simply turn on those pixels for which all edge equations evaluate to > 0:+++---David Luebke 18 01/13/19Using Edge Equations●An 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?David Luebke 19 01/13/19Using Edge Equations●Which pixels: compute min,max bounding box●Edge equations: compute from vertices●Orientation: ensure area is positive (why?)David Luebke 20 01/13/19Computing a Bounding Box●Easy to do●Surprising number of speed hacks possible■See McMillan’s Java code for an exampleDavid Luebke 21 01/13/19Computing Edge Equations●Want 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 = 0●Notice: two equations, three unknowns●Does this make sense? What can we solve?●Goal: solve for A & B in terms of CDavid Luebke 22 01/13/19Computing Edge Equations●Set 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 111100CBAyxyx01010110xxyyyxyxCBADavid Luebke 23 01/13/19Computing Edge Equations: Numerical Issues●Calculating 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 magnitude○Example: 1.234x104 - 1.233x104 = 1.000x101○We 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 problemDavid Luebke 24 01/13/19Computing Edge Equations:Numerical Issues●We 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 - By1●Why is this better?●Which should we choose?■Trick question! Average the two to avoid bias:C = -[A(x0+x1) + B(y0+y1)] / 2David Luebke 25 01/13/19Edge
View Full Document
Unlocking...