Drawing PolygonsRecap: TrianglesRecap: Edge EquationsSlide 4Slide 5Slide 6Using Edge EquationsSlide 8Computing Edge EquationsSlide 10Computing Edge Equations: Numerical IssuesComputing Edge Equations: Numerical IssuesEdge EquationsEdge Equations: CodeOptimize This!Edge Equations: Speed HacksDrawing PolygonsCS 445/645Introduction to Computer GraphicsDavid Luebke, Spring 2003David Luebke 2 01/14/19Recap: Triangles●We often draw polygons by breaking them into triangles●Two basic methods for drawing triangles:■Edge walking○Use DDA algorithm to compute edges (edge setup)○Fill in pixels between edges○Finicky, lots of special cases○Touches only pixels involved in triangle■Edge equationsDavid Luebke 3 01/14/19Recap: Edge Equations●An edge equation is simply the equation of the line containing that edge■Ax + By + C = 0■Given a point (x,y), plugging x & y into this equation tells us 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 4 01/14/19Recap: Edge Equations●Edge equations thus define two half-spaces:David Luebke 5 01/14/19Recap: Edge 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 6 01/14/19Recap: Edge Equations●So…simply turn on those pixels for which all edge equations evaluate to > 0:+++---David Luebke 7 01/14/19Using Edge Equations●Can implement edge equations in hardware by associating a simple processor with every pixel■Processor need only evaluate linear expressions■In practice, use a tile of (say) 16x16 pixel processors, “stamp out” larger polygons●Implementing an edge-equation rasterizer:■Which pixels do you consider?■How do you compute the edge equations?■How do you orient them correctly?David Luebke 8 01/14/19Using Edge Equations●Which pixels: compute min,max bounding box●Edge equations: compute from vertices●Orientation: ensure area is positive (why?)David Luebke 9 01/14/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 10 01/14/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 11 01/14/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 12 01/14/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 13 01/14/19Edge Equations●So…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)David Luebke 14 01/14/19Edge Equations: Code●Basic 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 positiveDavid Luebke 15 01/14/19Optimize This!findBoundingBox(&xmin, &xmax, &ymin, &ymax);setupEdges (&a0,&b0,&c0,&a1,&b1,&c1,&a2,&b2,&c2);/* Optimize this: */for (int y = yMin; y <= yMax; y++) {for (int x = xMin; x <= xMax; x++) {float e0 = a0*x + b0*y + c0;float e1 = a1*x + b1*y + c1;float e2 = a2*x + b2*y + c2;if (e0 > 0 && e1 > 0 && e2 > 0) setPixel(x,y);}}David Luebke 16 01/14/19Edge Equations: Speed Hacks●Some speed hacks for the inner loop:int xflag = 0;for (int x = xMin; x <= xMax; x++) {if (e0|e1|e2 > 0) {setPixel(x,y);xflag++;} else if (xflag != 0) break;e0 += a0; e1 += a1; e2 += a2;}■Incremental update of edge equation values (think DDA)■Early termination (why does this work?)■Faster test of equation
View Full Document
Unlocking...