ColorAdminRecap: Rasterizing TrianglesOptimize This!Edge Equations: Speed HacksEdge Equations: Interpolating ColorSlide 7Edge Equations: Interpolating ColorTriangle Rasterization IssuesGeneral Polygon RasterizationSlide 11Slide 12Slide 13Faster Polygon RasterizationActive Edge TableSlide 16Slide 17David Luebke 1 01/14/19ColorCS 445/645Introduction to Computer GraphicsDavid Luebke, Spring 2003David Luebke 2 01/14/19Admin●Drop deadline imminent!David Luebke 3 01/14/19Recap: Rasterizing Triangles●Edge walking: ■Use DDA approach to “walk” down edges of triangle■At each scanline, walk the span from one edge to another●Edge equations: ■Compute bounding box■Edge equations: compute from vertices (numerical issues!)■Orientation: ensure area is positiveDavid Luebke 4 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 5 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 valuesDavid Luebke 6 01/14/19Edge Equations: Interpolating Color●Given colors (and later, other parameters) at the vertices, how to interpolate across?●Idea: triangles are planar in any space:■This is the “redness” parameter space■Note:plane follows formz = Ax + By + C■Look familiar?David Luebke 7 01/14/19Edge Equations: Interpolating Color●Given redness at the 3 vertices, set up the linear system of equations:●The solution works out to:David Luebke 8 01/14/19Edge Equations:Interpolating Color●Notice that the columns in the matrix are exactly the coefficients of the edge equations!●So the setup cost per parameter is basically a matrix multiply●Per-pixel cost (the inner loop) cost equates to tracking another edge equation value (which is?)■A: 1 addDavid Luebke 9 01/14/19Triangle Rasterization Issues●Exactly which pixels should be lit?●A: Those pixels inside the triangle edges●What about pixels exactly on the edge? (Ex.)■Draw them: order of triangles matters (it shouldn’t)■Don’t draw them: gaps possible between triangles●We need a consistent (if arbitrary) rule ■Example: draw pixels on left or top edge, but not on right or bottom edgeDavid Luebke 10 01/14/19General Polygon Rasterization●Now that we can rasterize triangles, what about general polygons?●We’ll not take an edge-equations approach (why?)David Luebke 11 01/14/19General Polygon Rasterization●Consider the following polygon:●How do we know whether a given pixel on the scanline is inside or outside the polygon?ABCDEFDavid Luebke 12 01/14/19General Polygon Rasterization●Does it still work?ABCDEFGIHDavid Luebke 13 01/14/19General Polygon Rasterization●Basic idea: use a parity testfor each scanline edgeCnt = 0; for each pixel on scanline (l to r) if (oldpixel->newpixel crosses edge) edgeCnt ++; // draw the pixel if edgeCnt odd if (edgeCnt % 2) setPixel(pixel);●Why does this work?●What assumptions are we making?David Luebke 14 01/14/19Faster Polygon Rasterization●How can we optimize the code?for each scanline edgeCnt = 0; for each pixel on scanline (l to r) if (oldpixel->newpixel crosses edge) edgeCnt ++; // draw the pixel if edgeCnt odd if (edgeCnt % 2) setPixel(pixel);●Big cost: testing pixels against each edge●Solution: active edge table (AET)David Luebke 15 01/14/19Active Edge Table●Idea: ■Edges intersecting a given scanline are likely to intersect the next scanline■Within a scanline, the order of edge intersections doesn’t change much from scanline to scanlineDavid Luebke 16 01/14/19Active Edge Table●Algorithm:■Sort all edges by their minimum y coord■Starting at bottom, add edges with Ymin= 0 to AET■For each scanline:○Sort edges in AET by x intersection○Walk from left to right, setting pixels by parity rule○Increment scanline○Retire edges with Ymax < Y○Add edges with Ymin > Y○Recalculate edge intersections and resort (how?)■Stop when Y > Ymax for last edgesDavid Luebke 17 01/14/19Color●Next topic: ColorTo understand how to make realistic images, we need a basic understanding of the physics and physiology of vision. Here we step away from the code and math for a bit to talk about basic
View Full Document
Unlocking...