1Greg HumphreysCS445: Intro GraphicsUniversity of Virginia, Fall 2003Scan Conversion 1: Lines, Circlesand FractalsDrawing• Most computer generated images made up ofgeometric primitives (polygons, lines, points)• Application draws them by setting bits in theframebuffer• Most graphics applications involve scene databasemanagementSceneDatabaseGraphicsApplicationDeviceDriverFramebufferDisplayA DDA Line Drawing FunctionLine(int x1, int y1, int x2, int y2){ int dx = x1 - x2, dy = y2 - y1; int n = max(abs(dx),abs(dy)); float dt = n, dxdt = dx/dt, dydt = dy/dt; float x = x1, y = y1; while (n--) { DrawPoint( round(x), round(y) ); x += dxdt; y += dydt; }}What’s bad about this?We Can Do Better Than That...• Get rid of all those nasty floating point operations• The idea: find the next pixel from the current one• So which of the green pixels is next?The Key• We’re only ever going to go right one pixel, or up andright one pixel (if the slope of the line is between 0and 1). Call these two choices “E” and “NE”• Let’s think of pixels as “lattice points” on a grid• Given an X coordinate, we only need to choosebetween y and y+1 (y is the Y coordinate of the lastpixel)The Midpoint Test• Look at the vertical grid line that our line intersects• On which side of the midpoint (y+1/2) does theintersection lie?• If it’s above the midpoint, go NE, otherwise go E2Our Exampley+1y+2y+3yxx+1x+2x+3 x+4 x+5 x+6 x+7Implicit Functions• Normally, a line is defined as• Instead, define , and let the linebe everywhere where• Now, if , we’re “above” the line, and if , we’re “below” the lineWho Cares?• We can evaluate the implicit line function at themidpoint to figure out where to draw next!• In fact, we can use the last function evaluation to findthe next one cheaply!• For ANY :Midpoint AlgorithmLine(int x1, int y1, int x2, int y2){ int dx = x2 - x1, dy = y2 - y1; int e = 2*dy - dx; int incrE = 2*dy, incrNE = 2*(dy-dx); int x = x1, y = y1; DrawPoint( x, y ); while (x < x2) { x++; if ( e <= 0 ) { e += incrE; } else { y++; e += incrNE; } DrawPoint( x, y ); }}• “e” holds theimplicit functionevaluation ateach x value(actually, it’smultiplied by 2,but all we careabout is the sign).• Easy extensionfor lines witharbitrary slopes.Midpoint Algorithm for Circles• Only consider the second octant (the others aresymmetric anyhow)• Midpoint test still works: do we go right, or right anddown?ESEMore Midpoint Circle Drawing• The circle’s implicit function (r is the radius):• Once we know the value of the implicit function atone midpoint, we can get the value at the nextmidpoint by the same differencing technique: If we’re going E: If we’re going SE:3Drawing the 2nd Octantvoid Circle( int cx, int cy, int radius ){ int x = 0, y = radius, e = 1-radius; DrawPoint( x + cx, y + cy ); while (y > x) { if (e < 0) // Go “east” { e += 2*x + 3; } else // Go “south-east” { e += 2*(x-y) + 5; y--; } x++; DrawPoint( x + cx, y + cy ); }}• Look at all thoseexpensive multiplies!Can we get rid of themtoo?• How about doing finitedifferencing on the “e”variable itself? If we go E: If we go SE:Final Circle Drawervoid Circle( int cx, int cy, int radius ){ int x = 0, y = radius, e = 1-radius; int incrE = 3, incrSE = -2*radius + 5 DrawPoint( x + cx, y + cy ); while (y > x) { if (e < 0) // Go “east” { e += incrE; incrE += 2; incrSE += 2; } else // Go “south-east” { e += incrSE; incrE += 2; incrSE += 4; y--; }x++; DrawPoint( x + cx, y + cy ); }}This looks pretty fast!Flood Fill• The idea: fill a “connected region” with a solidcolor• Term definitions:• The center “1” pixel is 4-connected to the pixelsmarked “4”, and 8-connected to the pixelsmarked “8”44448 8881Simple 4-connected Fill• The simplest algorithm to fill a 4-connected region isa recursive one:FloodFill( int x, int y, int inside_color, int new_color ){ if (GetColor( x, y ) == inside_color) { SetColor( x, y, new_color ); FloodFill( x+1, y , inside_color, new_color ); FloodFill( x-1, y , inside_color, new_color ); FloodFill( x, y+1, inside_color, new_color ); FloodFill( x, y-1, inside_color, new_color ); }}A Span-based Algorithm• Definition: a run is a horizontal span of identicallycolored pixelsStart at pixel “s”, the seed. Find the run containing “s” (“b”to “a”). Fill that run with the new color. Then search everypixel above that run, looking for other pixels of the interiorcolor. For each one found, find the right side of that run(“c”), and push that on a stack. Do the same for the pixelsbelow (“d”). Then pop the stack and repeat the procedurewith the new seed. The algorithm finds runs ending at “e”,“f”, “g”, “h”, and “i”sbacdefghiFractals• Fractal: any curve or shape exhibiting self-similarityat any scale• Fractals appear in nature all the time• Part of the general science of chaos4The Koch Curve• Start with a line• Replace the line with four lines, and repeat:Properties of the Koch Curve• It occupies a finite area in the plane• It has infinite length• It is self-similar• It has a dimension of• It’s easier to draw in polar coordinates (hint, hint…)Non-Integral Dimension???• Let’s look at other “self-similar” shapes:Shape #Parts Scale Dimension2 2 14 2 28 2 34 3 ?Self Similar Curves in Nature• How long is a coastline? Measure on a map Walk around big boulders Measure each grain of sand• Cellular structure of leaves• Blood vessel structure• Ethernet packet traffic (okay, that’s not really Nature)Drawing Fractal Trees#define ANGLE 45void tree (float X1, float Y1, float R, float Theta, int Level){ float SX, SY, EX, EY; if (Level > 0) { EX = X1 + (R * cos(Theta)); EY = Y1 + (R * sin(Theta));line (X1, Y1, EX, EY); SX = X1 + ((R * 0.5) * cos(Theta)); SY = Y1 + ((R * 0.5) * sin(Theta)); tree (SX, SY, R*0.8, Theta-ANGLE, Level-1); tree (SX, SY, R*0.8, Theta+ANGLE, Level-1); }}Fractal Trees5Better Fractal Trees#define RT_ANGLE 45#define LFT_ANGLE 65 void non_sym_tree (float X1, float Y1, float R, float Theta, int Level) { float SX, SY, EX, EY; if (Level > 0) { EX = X1 + (R * cos(Theta)); EY = Y1 + (R * sin(Theta)); line (X1, Y1, EX, EY);
View Full Document
Unlocking...