Michener’s AlgorithmScan conversionGraphics AnimationsEight-fold symmetryCompute only one octantSubroutine: draw_octant_pointsThe “best” pixel to draw?Decision at n-th stageFormula: sum of error-termsDifference EquationAlgorithm initializationSlide 12ReferenceCircle ‘fill’ also exploits symmetrySubroutine: draw_segmentsdraw_horiz( int xlo, xhi, y, color );Demo-programIn-Class Exercise #1Animation with ‘image tearing’What can we do about it?SuperVGA’s hardwareVESA’s BIOS-ExtensionsUsing ‘off-screen’ video memoryVBE service 0x07In-class exercise #2Michener’s AlgorithmAn efficient scheme for drawing circles (and filling circular disks) on a raster graphics displayScan conversion•Geometric objects possess implicit parameters•Example: A circle has a ‘center’ and a ‘radius’•Its equation is: (x – xc)2 + (y - yc)2 = R2 •x and y are from the continuum of real numbers•CRT display is a discrete 2D array of ‘pixels’•So drawing a circle requires a conversion, from something continuous into something discrete•In computer graphics it’s called scan conversion•Imperfections: unavoidable, but to be minimizedGraphics Animations•Fast drawing is essential for animations•Some guidelines for speed: –eliminate all redundant computations–prefer integer arithmetic to floating-point –prefer add and subtract to multiply or divide•Famous example: ‘Michener Algorithm’ •We can use it later with our ‘pong’ gameEight-fold symmetry(x, y)(-x, y)(x, -y)(-x, -y)(y, x)(y, -x)(-y, -x)(-y, x)Compute only one octantSubroutine: draw_octant_pointsArguments: int x, y, xcent, ycent, color; draw_pixel( xcent + x, ycent + y, color );draw_pixel( xcent + y, ycent + x, color );draw_pixel( xcent - x, ycent + y, color );draw_pixel( xcent - y, ycent + x, color );draw_pixel( xcent + x, ycent - y, color );draw_pixel( xcent + y, ycent - x, color );draw_pixel( xcent - x, ycent - y, color );draw_pixel( xcent - y, ycent - x, color );The “best” pixel to draw?Blue pixel: too far from center ( E > 0 )Red pixel: too near the center ( E < 0 )Error-term: E = (x2 + y2) – R2Decision at n-th stageyn-1xn-1xnPn-1An ?Bn ?Algorithm: compute sum = error( An ) + error( Bn ); If ( sum < 0 ) choose A n; otherwise choose B n.Formula: sum of error-terms•Assume circle has radius R, center (0,0)•error( An) = (xn-1+1)2 + (yn-1)2 – R2•error( Bn) = (xn-1+1)2 + (yn-1 – 1)2 – R2•sumn = 2(xn-1+1)2 + 2(yn-1)2 –2(yn-1) + 1-2R2•Now, how is sumn different from sumn+1:–If An is chosen at the n-th step?–If Bn is chosen at the n-th step?Difference Equation•Observe that: sumn+1 – sumn =4xn-1 + 6 + 2(yn2 – yn-12) – 2(yn – yn-1)•When An is selected at n-th stage: –we will have yn = yn-1–thus: sumn+1 = sumn + 4xn-1 + 6 •When Bn is selected at n-th stage: –we will have yn = yn-1 - 1–thus: sumn+1 = sumn + 4(xn-1 – yn-1) + 10Algorithm initialization•We start with the point P0 = (x0,y0), wherex0 = 0 and y0 = R•In this case: A1 = (1, R) and B1 = (1, R-1)•So the initial ‘sum-of-errors’ term will be:sum1 = error(A1) + error(B1) = [(12 + R2) – R2] + [(12 + R2–2R+1) – R2] = 3 – 2RMichener’s Algorithmint x = 0, y = R, sum = 3 – 2*R;while ( x <= y ) {draw_octant_points( x, y, xc, yc, color );if ( sum < 0 ) sum += 4*x + 6;else { sum += 4*(x - y) + 10; --y; }++x;}Reference•Francis S. Hill, jr., “Computer Graphics,” Macmillan (1990), pp. 433-435.•NOTE: Michener’s circle-drawing method owes its inspiration to a famous algorithm for efficient line-drawing, devised in 1965 by J. E. Bresenham (see the IBM Systems Journal, vol 4, pp. 305-311).Circle ‘fill’ also exploits symmetry(x, y)(-x, y)(x, -y)(-x, -y)(y, x)(y, -x)(-y, -x)(-y, x)Subroutine: draw_segmentsArguments: int x, y, xc, yc, color; draw_horiz( xc – x, xc + x, yc + y, color );draw_horiz( xc – x, xc + x, yc - y, color );draw_horiz( xc – y, xc + y, yc + x, color );draw_horiz( xc – y, xc + y, yc - x, color );draw_horiz( int xlo, xhi, y, color );Clipping to screen boundaries:If (( y < ymin )||( y > ymax )) return;if ( xlo < xmin ) xlo = xmin;if ( xhi > xmax ) xhi = xmax;Drawing the horizontal segment:for (x = xlo; x <= xhi; x++) draw_pixel( x, y, color );Demo-program•Try the ‘michener.cpp’ demo•It uses VESA graphics-mode 0x0103•Screen resolution is 800x600•Color depth is 8 bits-per-pixel (8bpp)•SVGA’s Linear Frame Buffer is enabled by calling VESA’s Set Display Mode service with bit #14 of the mode ID-number setIn-Class Exercise #1•Modify the ‘michener.cpp’ demo:–Use the standard ‘rand()’ function–Draw lots of color-filled circles–Stop if user hits <ESCAPE> key•NOTE: For this latter feature, we need to recall how to set up the terminal keyboard so it uses a ‘non-canonical’ input-modeAnimation with ‘image tearing’•We used Michner’s Algorithm in a graphics animation demo (named ‘bouncing.cpp’)•But you will see undesirable ‘tearing’ of the bouncing ball’s image – because we drew a large number of pixels, and computed a large number of pixel-locations – twice for each displayed frame (erase, then redraw)•Not enough drawing time during ‘retrace’!What can we do about it?•One idea is to draw a smaller-sized ball•Another idea is to draw only once – i.e. include enough extra pixels around the new ball’s perimeter to hide the old one•Also we could ‘pre-compute’ coordinates•An important general technique is to use off-screen display memory to ‘prepare’ a new screen-image, and then do a ‘bitblit’SuperVGA’s hardware•The graphics processor has the capability to switch the CRTC’s ‘start_address’, so we see a new full-screen image displayed almost instantly (i.e., just one or two CPU instructions), instead of a copying a screen•But doing this for higher-resolution SVGA display-modes requires accessing one or more of the nonstandard VGA extensionsVESA’s BIOS-Extensions•Video Electronics Standards Association defines a ROM-BIOS service that can be invoked to reprogram CRT Start_Address in a standard way for compliant systems•For a particular vendor’s graphics card, we can discover how to directly reprogram the CRT’s Start-Address, by ‘trapping’ the I/O instructions used in the ROM-BIOS routineUsing ‘off-screen’ video memoryVisible screenAlternatescreenCRT Controller’s Start-Address (default=0)VRAMThe currently
View Full Document
Unlocking...