Michener s Algorithm An efficient scheme for drawing circles and filling circular disks on a raster graphics display Scan 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 minimized Graphics 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 game Eight fold symmetry x y x y y x y x y x y x x y x y Compute only one octant Subroutine draw octant points Arguments 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 R2 Decision at n th stage Pn 1 An yn 1 Bn xn 1 xn 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 10 Algorithm initialization We start with the point P0 x0 y0 where x0 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 2R Michener s Algorithm int 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 y x y x y x y x x y x y Subroutine draw segments Arguments 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 set In 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 mode Animation 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 offscreen 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 extensions VESA 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 routine Using off screen video memory CRT Controller s Start Address default 0 Visible screen The currently displayed image is defined in this region of VRAM while an alternative image is prepared for display in this region of VRAM When the alternate memory region is ready to be displayed the CRT Start Address register is rewritten instantaneously changing what the user sees on the display monitor The technique is called page flipping Alternate screen VRAM VBE service 0x07 This ROM BIOS service can be called to obtain or modify the CRT Start Address It isn t instantaneous because of all the parameter passing and changing of CPU execution mode and transitions back and forth from user space to kernel space But it might be fast enough to cure the image tearing we saw in bouncing demo In class exercise 2 Look at documentation for VESA service 7 See if you can modify the main animation loop in our bouncing cpp program so the image frames are alternately drawn in two different pages of the video memory i e implement the page flipping idea while one frame is being viewed by the user the …
View Full Document
Unlocking...