Study on Fundamentals of Raster Scan Graphics

Study on Fundamentals of Raster Scan Graphics

1. Unit 2: Raster Scan Graphics Mr. C. P. Divate

2. Line generation Algorithm in Computer Graphics In any 2-Dimensional plane if we connect two points ( x1, y1) and ( x2, y2), we get a line segment . But in the case of computer graphics we can not directly join any two coordinate points, for that we should calculate intermediate point’s coordinate and put a pixel for each intermediate point, of the desired color with help of functions like putpixel (x, y, K ) in C, where ( x,y ) is our co-ordinate and K denotes some color . Examples: Input: For line segment between (3, 2) and (6, 5) : we need (3, 2),(4, 2) (4, 3) ….. (5, 5) as our intermediate points.

3. Line generation Two-point form equation of line Computer Graphics Let P( x,y ) be the general point on the line L which passes through the points  A(x1,y1) and B(x2,y2 )

4. Basic properties of line drawing in Computer Graphics The primary design criteria are as follows. Straight lines appear as straight lines. Straight lines start and end accurately. Displayed lines should have constant brightness along their length, independent of the line length and orientation. Lines should be drawn rapidly .

5. Basic mathematics to draw line drawing in Computer Graphics Method-1 : Direct Method : In this algorithm, we have two endpoints.  We find the slope of the line by using both the points, and we put the slope in the line equation y = mx + b.

6. Basic properties of line drawing ALGORITHMS in Computer Graphics An algorithm should be precise:  Each step of the algorithm must be adequately defined. Finiteness:  An algorithm must contain finiteness. It means the algorithm stops after the execution of all steps. Easy to understand:  An algorithm must help learners to understand the solution in a more natural way. Correctness:  An algorithm must be in the correct manner. Effectiveness:  Thesteps of an algorithm must be valid and efficient. Uniqueness:  All steps of an algorithm should be clearly and uniquely defined, and the result should be based on the given input. Input:   A good algorithm must accept at least one or more input. Output:  An algorithm must generate at least one output.

7. DDA Line G eneration Two-point form equation of line Computer Graphics

8. DDA Line generation Two-point form equation of line Computer Graphics DDA Algorithm: Step 1 : Start Algorithm Step 2 : Declare x1,y1,x2,y2,dx,dy,x,y as integer variables. Step 3: Enter value of x1,y1,x2,y2. Step 4: if ABS (x2-x1) > ABS (y2-y1) Then step = abs (x2-x1) else step = abs (y2-y1 ) Step 5: dx=(x2-x1)/step dy =(y2-y1)/step assign x = x1 + 0.5 assign y = y1 + 0.5 i=1 Step 6: Set pixel (x, y) Step 7: while( i <= step ) x = x + dx y = y + dy i=i+1 Set pixels (Round (x), Round (y)) Step 8: End Algorithm Example draw line from (0,0) to (4,6) dx=0.7 dy =1 step=6

9. DDA Line generation Two-point form equation of line Computer Graphics DDA Algorithm: Step 1 : Start Algorithm Step 2 : Declare x1,y1,x2,y2,dx,dy,x,y as integer variables. Step 3: Enter value of x1,y1,x2,y2. Step 4: if ABS (x2-x1) > ABS (y2-y1) Then step = abs (x2-x1) else step = abs (y2-y1 ) Step 5: dx=(x2-x1)/step dy =(y2-y1)/step assign x = x1 + 0.5 assign y = y1 + 0.5 i=1 Step 6: Set pixel (x, y) Step 7: while( i <= step ) x = x + dx y = y + dy i=i+1 Set pixels (Round (x), Round (y)) Step 8: End Algorithm Example draw line from p1(2,3) to p2(6,6) i ( x , y ) x y

10. DDA Line generation Two-point form equation of line Computer Graphics Advantages : It is simple and easy to implement algorithm. It avoid using multiple operations which have high time complexities. It is faster than the direct use of the line equation because it does not use any floating point multiplication and it calculates points on the line . Disadvantages : It deals with the rounding off operation and floating point arithmetic so it has high time complexity. As it is orientation dependent, so it has poor endpoint accuracy. Due to the limited precision in the floating point representation it produces cumulative error.

11. Basis of the algorithm: A B Start position From start position decide A or B next A more efficient approach It is suited for implementation on CRT device . The algorithm seeks to select optimum(accurate) raster location to draw straight line. For this algorithm increments either x or y by one depending on slope of line.

12. Basis of the algorithm: A B Start position From start position decide A or B next The increment in other variable ,either 0 or 1is determined by actual line and distance between the actual line and nearest grid location . This distance is called error e

13. For a given value of x If the slope of line is greater than or equal to ½ then line intercept at x=1 is closer to y=1. If the slope of line is less than ½ then line intercept at x=1 is closer to y=0. Reason is, one pixel lies at distance t i above the line, and one pixel lies at distance s i below the line True line t i s i The increment in other variable ,either 0 or 1is determined by actual line and distance between the actual line and nearest grid location . This distance is called error e          

14. For a given value of x If the slope of line is greater than or equal to ½ then line intercept at x=1 is closer to y=1. If the slope of line is less than ½ then line intercept at x=1 is closer to y=0. Reason is, one pixel lies at distance t i above the line, and one pixel lies at distance s i below the line True line t i s i The increment in other variable ,either 0 or 1is determined by actual line and distance between the actual line and nearest grid location . This distance is called error e          

15. For a given value of x If the slope of line is greater than or equal to ½ then line intercept at x=1 is closer to y=1. If the slope of line is less than ½ then line intercept at x=1 is closer to y=0. Reason is, one pixel lies at distance t i above the line, and one pixel lies at distance s i below the line True line t i s i The increment in other variable ,either 0 or 1is determined by actual line and distance between the actual line and nearest grid location . This distance is called error e          

16. Bresenham Line Algorithm The algorithm start with error term with following error term equation, e = m - ½ Subsequent increments in e will be e = e + m

17. LineBres ( int x 1 , int y 1 , int x 2 , int y 2 ) // line for |m| < 1 { Step 1: Start Algorithm Step 2: Declare x1 , y1, x2, y2, dx, dy , x, y as integer variables. Step 3: dx = x 2 – x 1, d y = y 2 – y 1, x=x1, y=y1 m= dy /dx e = m – ½ Step 4: for i= 0 to dx { setpixel ( x,y ) while( e >0) { y = y+1 e=e-1 } x=x+1 e= e+m next I Setp 5: Finish Floating point Bresenham’s Line Algorithm :

18. e = m – ½ e = - ( where m= ) e = 2 dx e = 2 dy - dx - ( I ) Here let, ê = 2 dx e - ( II ) Hence, ê = 2 dy - dx - ( III )   Integer Bresenham’s Line Algorithm : e = e + m e = e + e = e dx = e dx + dy Multiply both side by 2 2e dx = 2e dx + 2 dy – (IV) Use eq n ( III ) in ( IV ) ê = ê + 2 dy - ( V )   Convert following floating point equations to integer equation to run algorithm fast, e = m – ½ e= e+m e=e-1

19. e=e-1 - ( V ) Multiply both side of ( V ) by 2. dx 2 dx e = 2 dx e - 2dx - ( V ) As, ê = 2 dx e - ( II ) Hence, ê = ê - 2dx - ( III ) Integer Bresenham’s Line Algorithm : Convert following floating point equations to integer equation to run algorithm fast, e = m – ½ e= e+m e=e-1

20. LineBres ( int x 1 , int y 1 , int x 2 , int y 2 ) // line for |m| < 1 Step 1 : Declare x1 , y1, x2, y2, dx, dy , x, y as integer variables. Step 2: dx = x 2 – x 1, d y = y 2 – y 1, x = x1, y = y1 ê = 2 dy - dx Step 3: for i= 0 to dx step i = i + 1 { setpixel ( x,y ) while( ê >0) { y = y+1 ê = ê - 2dx } x=x+1 ê = ê + 2 dy } Setp 5: Finish LineBres Integer Bresenham’s Line Algorithm :

21. General Bresenham’s Line Algorithm : Depending on quadrant the increment / decrement in x and y will be as above

22. General Bresenham’s Line Algorithm :

23. General Bresenham’s Line Algorithm :

24. Advantages / disadvantages of Bresenham Line Algorithm : The advantages of Bresenham Line Drawing Algorithm are- It is easy to implement. It is fast and incremental. It executes fast but less faster than DDA Algorithm. The points generated by this algorithm are more accurate than DDA Algorithm. It uses fixed points only. The disadvantages of Bresenham Line Drawing Algorithm are- Though it improves the accuracy of generated points but still the resulted line is not smooth. This algorithm is for the basic line drawing. It can not handle diminishing jaggies .

25. Basic Concepts in Circle Drawing Circle is a symmetrical figure. The shape of the circle is similar in each quadrant It has eight-way symmetry Plot (x,y) Plot ( y,x ) Plot (-x,-y) Plot (-y,-x ) Plot (- x,y ) Plot (y, -x) Plot (x,-y) Plot (- y,x )

26. Polynomial Method x 2 + y 2 = r 2 Trigonometric Method x= r cos Ө Y = r sin Ө Methods to Represent a Circle r r

27. General Bresenham’s Circle Algorithm : Most efficient algorithm to draw circle is Bresenham’s Circle Algorithm . The Bresenham’s circle drawing algorithm considers the eight way of the symmetry of the circle to generate it .

28. General Bresenham’s Circle Algorithm : At the beginning only one octant of the circle generation is needed. Other parts of circles are drawn by successive reflections. e.g. if circle has drawn in first octant (0 to 45 ccw ) The s econd octant is obtained by reflection through the line y=x to yield first quadrant. The results(pixels) in first quadrant are reflected through the line x=0 to obtain the second quadrant pixels. The combined results (pixels ) of upper semicircles are reflected through the line y = 0 to complete the circle.

29. Bresenham’s Circle drawing Algorithm: It plots 1/8 th part of the circle i.e. from 90ᵒ to 45ᵒ. As circle is drawn from 90ᵒ to 45ᵒ , the x moves in positive e direction and y moves in the negative direction .

30. Bresenham’s Circle drawing Algorithm Actual Distance of raster pixel A and B from origin

31. Bresenham’s Circle drawing Algorithm X i Y i Δ i

32. Bresenham’s Circle drawing Algorithm X i Y i Δ i 1) If Δ i < 0 then, diagonal point is inside the actual circle, either pixel at ( x i +1 , y i ) i.e. m H or that at ( x i +1 , y i -1) i.e. m D must be chosen. To decide which own calculate δ A = m H - m D A ---------- ( I ) ----- ( II ) A A  

33. Bresenham’s Circle drawing Algorithm Let us simplify, δ A = m H - m D - R 2 | - | ( - R 2 ) |   - | ( - R 2 ) | + (2 + 1)   + 2 + 1   + 2 + 1   2 - 1 - R 2 | - | ( - R 2 ) | + (2 + 1)   + ) + 1 ---------[ III ]   ( 2 + 1) - R 2 | - | ( - R 2 ) | + (2 +1)    

34. Bresenham’s Circle drawing Algorithm X i Y i Δ i 2 ) If Δ i > 0 then, diagonal point is outside the actual circle, either pixel at ( x i +1 , y i -1) i.e. m D or that at i.e. ( x i y i + 1) m V must be chosen. To decide which own calculate δ B = m D - m V   B B B

35. Bresenham’s Circle drawing Algorithm Let us simplify, δ A = m D - m V - R 2 | - | ( x - R 2 ) |   - | ( - R 2 ) | 2 1   - 2 - 1   2 1   - | ( - R 2 ) | 2 x 1   ) - 1 ---------[ IV ]   - | ( - R 2 ) | (2 x +1)    

36. Bresenham’s Circle drawing Algorithm X i Y i Δ i 3) If Δ i = 0 then, δ A = m H – m D Here m D = Δ i = 0, hence δ A = m H which means δ A >=0 hence diagonal pixel ) is selected i.e movement is m D OR 3) If Δ i = 0 then, δ B = m D - m V Here m D = Δ i = 0, hence δ B = - m V which means δ B < 0 hence diagonal pixel ) is selected i.e movement is m D    

37. Bresenham’s Circle drawing Algorithm X i Y i Δ i

38. Bresenham’s Circle drawing Algorithm Letus make some simplification to obtain values for x, y, δ A, and δ B to increment or decrement during the loop of algorithm.   1) For Horizontal m H Pixel selection

39. Bresenham’s Circle drawing Algorithm Letus make some simplification to obtain values for x, y, δ A, and δ B to increment or decrement during the loop of algorithm.   2 ) For Diagonal m D Pixel selection 3) For Diagonal m V Pixel selection

40. Bresenham’s Circle drawing Algorithm Letus make some simplification to obtain values for x, y, δ A, and δ B to increment or decrement during the loop of algorithm.   4) Initial stage or pixel from where Bresenham’s circle algorithm works X=0 Y=R   r (0,R)

41. Bresenham’s Circle drawing Algorithm Flowchart

42. Bresenham’s Circle drawing Algorithm

43. Example on Bresenham’s Circle Algorithm

44. Bresenham’s Circle drawing Algorithm Advantages of Bresenham's Circle Drawing Algorithm The Bresenhem’s circle drawing algorithm uses integer arithmetic which makes the implementation less complex. Due to its integer arithmetic, it is less time-consuming. This algorithm is more accurate than any other circle drawing algorithm as it avoids the use of round off function . Disadvantages of Bresenham's Circle Drawing Algorithm This algorithm does not produce smooth results due to its integer arithmetic as it fails to diminish the zigzags completely. The Bresenhem’s circle drawing algorithm is not accurate in the case of drawing of complex graphical images.

45. P o lygo n Polyline is a chain of connected line segments. It is specified by giving the vertices P , P 1 , P 2 ..and so on. The first vertex is called initial point and last is called terminal point. P P 2 P1 P 3 P 4 P 5 P 6

46. P o lygon When initial point and terminal point of any polyline is same (when polyline is closed) then it is called polygon.

47. Polygon is a representation of the surface . It is primitive which is closed in nature . It is formed using a collection of lines . It is also called as many-sided figure . The lines combined to form polygon are called sides or edges. The lines are obtained by combining two vertices. About P o lygon

48. Types of Polygon 1. Regular Polygon a regular polygon is a polygon that is equiangular (all angles are equal in measure) and equilateral (all sides have the same length). Regular polygons may be either convex or star.

49. Types of Polygon 2 . Convex polygon is a polygon in which the line segment joining any two points within the polygon lies completely inside the polygon

50. 3 . Concave polygon is a polygon in which the line segment joining any two points within the polygon may not lie completely inside the polygon. Types of Polygon

51. 4 . Complex polygon is a concave type polygon with number of edges and the edges are intersected . Types of Polygon

52. Polygon Representation The polygon can be represented by listing its n vertices in an ordered list. P = {(x 1 , y 1 ), (x 2 , y 2 ), ……., (x n , y n )} . The polygon can be displayed by drawing a line between (x 1 , y 1 ), and (x 2 , y 2 ) , then a line between (x 2 , y 2 ), and (x 3 , y 3 ) , and so on until the end vertex. In order to close up the polygon, a line between (x n , y n ), and (x 1 , y 1 ) must be drawn. One problem with this representation is that if we wish to translate the polygon, it is necessary to apply the translation transformation to each vertex in order to obtain the translated polygon.

53. Polygon Filling Algorithm • An ordered list of vertices forms a polygon . • Polygon Filling :- The pixels that fall on the border of the polygon are determined and the pixels that fall inside are determined in order to color the polygon . • Polygons are easier to fill since they have linear boundaries. • Filling the polygon means highlighting all the pixels which lie inside the polygon with any color other than the background color .

54. Point Inside Test – Even-Odd Method • Once the polygon is entered, we can draw the outline of the polygon using drawpoly () command in c/ c++ . • To show polygon as a solid object, it is needed to set the pixel inside the polygon as well as pixels on the boundary of it. • Now the question is, to determine whether the point /pixel is inside or outside of a polygon.

55. Point Inside Test – Even-Odd Method • One simple method of doing this is to draw a horizontal line segment from left to the pixel and count how many intersections of the line segment with the polygon boundary occur. • If there are an odd number of intersections, then the point is inside, otherwise it is outside. • This method is called the even-odd method of determining polygon inside points. • This inside test or Even-Odd method is used in scan line method of polygon filling. .

56. Types of Polygon Filling Algorithm There are two basic approaches used to fill the polygon. Ordered Edge List Algorithm Edge Flag algorithm Edge fill algorithm Fence Fill algorithm

57. Scanline Polygon Filling Algorithm • Scanline filling is basically filling up of polygons using horizontal lines or scanlines . • The purpose of the SLPF algorithm is to fill ( color ) the interior pixels of a polygon for each scanline . • This algorithm works by intersecting scanline with polygon edges and fills the polygon between pairs of intersections. • These intersection points are then sorted from left to right, and the corresponding positions between each intersection pair are set to the specified fill color .

58. Requirements of all Scanline Fill Algorithm Find Polygon Bounding box for, selection number of scanlines for scanning polygon Selection of boundry limit for x co-ordinate for each scanline

59. 1. Ordered Egde List Scanline Algorithm Start with Ymax and move to Ymin or vice versa For each scan line: Find the intersections of the scan line with all edges of the polygon. Sort the intersections by increasing x coordinate. Fill in all pixels between pairs of intersections Note For scan line number 8 the sorted list of x-coordinates is (2, 4, 9, 13) Therefore draw line b/w (2,4) & (9,13) Y max Y min

60. 1 . Ordered Egde List Scanline Fill Algorithm Challenges in filling the polygon selection number of scanlines for scanning polygon Selection of boundry limit for x co-ordinate for each scanline Scan line 7 Scan line 6 Scan line 3 Scan line 1 One intersection Three intersections Three intersections Number of intersections 7 3 1 SL7: 1 SL6 : 1, 2, 8 SL4 : 1, 4, 6, 8 SL3 : 1, 5, 8 SL2 : 1, 8 SL1 : 1, 2,3,4,5,6,7, 8 Ordered edge list of X for Scan Line It will no support or work if scan line intersects for odd number of times to polygon For horizontal line of polygon this algorithm give maximum no of intersections to scanline hence fail

61. Scanline Fill Algorithm Challenges in filling the polygon selection number of scanlines for scanning polygon Selection of boundry limit for x co-ordinate for each scanline One intersection One intersection

62. Scanline Fill Algorithm Challenges in filling the polygon We know that for every scan line we have to calculate x intersection with every polygon side. We can determine the next x intersection value as Bounding Box (x1,y1) (x2,y2) Intersecting point (x, y) Scan line y  

63. 2. Egde Flag Scanline Algorithm Before Edge Flag Fill After Edge Flag Fill negate

64. 2. Egde Flag Scanline Algorithm Y max Y min Xmin =0 Xmax

65. 3. Egde Fill Scanline Algorithm For each Scan line intersecting a polygon edge at(x, y), Complement all pixels to the right of (x, y). Next Scan line go to step 1.

66. 4 . Fence Fill Scanline Algorithm For each Scan line intersecting a polygon edge at(x, y), If the intersection is to the left of fence, Complement all pixels to the right of (x, y) of scan line and edge and to the left of fence. If the intersection is to the right of fence, b) Complement all pixels to the left of (x, y) of scan line and edge and to the right of fence. 2. Next Scan line go to step 1.

67. 4 . Fence Fill Scanline Algorithm

68. 5. Boundary Fill Algorithm Boundary Fill Algorithm starts at a pixel inside the polygon to be filled and paints the interior proceeding outwards towards the boundary. This algorithm works  only if  the color with which the region has to be filled and the color of the boundary of the region are different. If the boundary is of one single color , this approach proceeds outwards pixel by pixel until it hits the boundary of the region.

69. 5. Boundary Fill Algorithm Boundary Fill Algorithm is recursive in nature. It takes an interior point(x, y), a fill color , and a boundary color as the input. The algorithm starts by checking the color of (x, y). If it’s color is not equal to the fill color and the boundary color , then it is painted with the fill color and the function is called for all the neighbours of (x, y ) recursively. This process continues until all points up to the boundary color for the region have been tested.

70. 5. 4-connected pixels Boundary Fill Algorithm 4-connected pixels Boundary Fill Algorithm : After painting a pixel, the function is called for four neighboring points . These are the pixel positions that are right, left, above and below the current pixel. Areas filled by this method are called 4-connected . void boundaryFill4( int x, int y, int fill_color,int boundary_color ) { if( getpixel (x, y) != boundary_color && getpixel (x, y) != fill_color ) { putpixel (x, y, fill_color ); boundaryFill4(x + 1, y, fill_color , boundary_color ); boundaryFill4(x, y + 1, fill_color , boundary_color ); boundaryFill4(x - 1, y, fill_color , boundary_color ); boundaryFill4(x, y - 1, fill_color , boundary_color ); } }

71. 5. 8-connected pixels Boundary Fill Algorithm 8-connected pixels : More complex figures are filled using this approach. The pixels to be tested are the 8 neighboring pixels, the pixel on the right, left, above, below and the 4 diagonal pixels . Areas filled by this method are called 8-connected.

72. 5. 8-connected pixels Boundary Fill Algorithm Below given is the algorithm : void boundaryFill8( int x, int y, int fill_color,int boundary_color ) { if( getpixel (x, y) != boundary_color && getpixel (x, y) != fill_color ) { putpixel (x, y, fill_color ); boundaryFill8(x + 1, y, fill_color , boundary_color ); boundaryFill8(x, y + 1, fill_color , boundary_color ); boundaryFill8(x - 1, y, fill_color , boundary_color ); boundaryFill8(x, y - 1, fill_color , boundary_color ); boundaryFill8(x - 1, y - 1, fill_color , boundary_color ); boundaryFill8(x - 1, y + 1, fill_color , boundary_color ); boundaryFill8(x + 1, y - 1, fill_color , boundary_color ); boundaryFill8(x + 1, y + 1, fill_color , boundary_color ); } }

73. 6. Flood Fill Algorithm or Seed fill Algorithm Sometimes it is required to fill in an area that is not defined within a single color boundary. In such cases we can fill areas by replacing a specified interior color instead of searching for a boundary color . This approach is called a flood-fill algorithm. Like boundary fill algorithm, here we start with some seed and examine the neighboring pixels However , here pixels are checked for a specified interior color instead of boundary color and they are replaced by new color . Using either a 4-connected or 8-connected approach , we can stop through pixel positions until all interior point have been filled .

74. 6. Flood Fill Algorithm or Seed fill Algorithm Recursive algorithm for seed fill methods have difficulty as - The first difficulty is that if some inside pixels are already displayed in fill color then recursive branch terminates, leaving further internal pixels unfilled. If the image size increases the complexity increases in recurssion . To avoid this difficulty, we have to first change the color of any internal pixels that are initially set to the fill color before applying the seed fill procedures Disadvantage: Very slow algorithm May be fail for large polygons Initial pixel required more knowledge about surrounding pixels.

75. 6. Flood Fill Algorithm or Seed fill Algorithm Procedure floodfill (x, y,fill _ color , old_color : integer) If ( getpixel (x, y)= old_color ) { setpixel (x, y, fill_color ); fill (x+1, y, fill_color , old_color ); fill (x-1, y, fill_color , old_color ); fill (x, y+1, fill_color , old_color ); fill (x, y-1, fill_color , old_color ); } }

76. Terminologies in Computer Graphics Scree/Display Resolution: The number of horizontal and vertical pixels on a display screen. Also known as   display  mode. OR Screen resolution is the number of pixels a screen can show, both horizontally and vertically.  The more pixels, the more information is visible without scrolling . Screen resolutions have a pixel count such as 1600x1200, which means 1600 horizontal pixels & 1200 vertical pixels .

77. Terminologies in Computer Graphics The aspect ratio of a display device is the proportional relationship between the width and the height of the display. It is expressed as two numbers separated by a colon ( x:y ). Common aspect ratios for displays, past and present, include 5:4, 4:3, 16:10 and 16:9.

78. Frame Buffer A frame buffer is large contiguous piece of computer memory which is used to store the display image . The diff kinds of memory used for frame buffers are disk , IC shift registers, drums etc. To display a pixel on raster display, minimum 1 bit is used in frame buffer for text to maximum 24 bit in a frame buffer for graphics. When 1 bit is used to generate a pixel, the picture will be Black and white(0 & 1). A frame buffer stores information in digital form while raster display requires voltage to generate pixel. A single bit frame buffer raster CRT display is as following fig .

79. Frame Buffer Single Bit Frame Buffer

80. Frame Buffer Continued If the bits are increased from 1 to n then 2n intensity level can be achieved, for this, all the n bits are checked and resulting value is calculated. This value is given to DAC to generate appropriate voltage to set intensity of the pixel on the raster

81. Frame Buffer N- Bit plane Gray level Frame Buffer

82. Frame Buffer N- Bit plane Gray level Frame Buffer

83. Frame Buffer N- Bit plane Gray level Frame Buffer

84. Frame Buffer Simple color Frame Buffer

85. Color Frame Buffer 24-bit Plane color Frame Buffer

86. Frame Buffer Continued Rotating memory Frame Buffer Drums and disks were widely used in frame buffers to store the image information. It is required to be refreshed continuously. Thus, it is necessary to read the disk or drum again and again to refresh display. For this the rotating speed is made to coincide with the refresh rate of the screen . To generate a pixel of desired intensity or colour, it is first necessary to read the disk or drum.

87. Frame Buffer Continued Rotating memory Frame Buffer Continued The information stored in disk or drum is in digital form, hence it is necessary to convert it into analog form using DAC and then this analog signal is used to generate the pixel. If only one bit is used to generate the pixel then only black and white picture is possible. Disadvantage :- 1) the cost of the memory is high. 2) It requires more time due to latency problem .

88. Frame Buffer Continued Shift register Frame Buffer •It is IC, the problem with the rotating memory is that it is slow and expensive while IC-shift register can perform the same task with better speed and is less expensive. •In this circuit, when pulse is applied, the content of memory are shifted by one place removing the last bit and inserting it into the starting bit. •It is rotating the information in a circular form .

89. Frame Buffer Continued Shift register Frame Buffer •In this, one bit of memory is used as an intensity value. •For color or gray scale display more than one IC, shift register can be used in parallel. • Disadvantage: 1) It requires more time due to latency problem . 2)In shift-register, even small changes requires more time.

90. Frame Buffer Continued Random Access Frame Buffer Frame buffers are made up of random access circuit, and the color or gray scale of the pixel can be set by 1,2,4,8 or more bits. 1 bit is generally used in text generation and any simple 2-D graphics figures like square, triangle . To fill up the graphics figure, 2 to 4 bits of information are required for diff types of shading effects while 8 or more bits are used for high quality graphics . In color display 3 guns are used for 3 primary colors .E.g.- Red, Green, Blue, one for each.

91. Character Generation Techniques

92. Characters Generation in CG In computer graphics character can be generated using software . In hardware implementation of character generation limited faces of character can be generated. A wide variety of faces of character can be generated with software implementation. There are three methods for generating characters using software implementation:- Stroke method Vector method or bitmap method. Star bust method

93. Stroke Method In this method we use a sequence of line drawing function and arc functions to generate characters . We can generate a sequence of character by assigning starting and end point of line or arc . By using this method various faces of character can be generated by changing the values (parameters) in line and arc function . We can build our own stroke method character generator by calls to the line drawing algorithm.  Here it is necessary to decide which line segments are needed for each character and then drawing these s egments using line drawing algorithm. Eg:-

94. Starbust Method In this method a fixed pattern of line is used to generate the character. In this method we use a combination of 24 bit line segment . In 24 bit line segment code each bit represent a single line . Out of these 24 line segments, segments required to display for particular character are highlighted. To highlight a line we put corresponding bit 1 in 24 bit line segment code and 0 otherwise.

95. Representaion of Starbust Method: The starbust patterns for characters A and M. the patterns for particular characters are stored in the form of 24 bit code, each bit representing one line segment. The bit is set to one to highlight the line segment; otherwise it is set to zero. For example, 24-bit code for Character A is 0011 0000 0011 1100 1110 0001 and for character M is 0000 0011 0000 1100 1111 0011.

96. Representaion of Starbust Method: This method of character generation has some disadvantages. They are 1. The 24-bits are required to represent a character. Hence more memory is required 2. Requires code conversion software to display character from its 24-bit code 3. Character quality is poor. It is worst for curve shaped characters. 4. In Starbust method, 24 bit segment code is required to put in memory for generating character. Hence extra memory is required in this method .

97. Bitmap Method This method is suitable for producing various character. Font size of character can be increased by increasing the size of array. This method uses an array of 1’s & 0’s to represent pixels . It is also called dot matrix because in this method characters are represented by an array of dots in the matrix form. It is a two dimensional array having columns and rows. An 5x7 array is commonly used to represent characters. However 7x9 and 9x13 arrays are also used. Higher resolution devices such as inkjet printer or laser printer may use character arrays that are over 100x100.

98. Example of an Bitmap Array:

99. All the mentioned methods creates aliased characters:

100. P o lygo n  Polyline is a chain of connected line segments. It is specified by giving the vertices P , P 1 , P 2 ..and so on.  The first vertex is called initial point and last is called terminal point. P P 2 P1 P 3 P 4 P 5 P 6

101. P o lygon  When initial point and terminal point of any polyline is same (when polyline is closed) then it is called polygon.

102. Polygon is a representation of the surface . It is primitive which is closed in nature . It is formed using a collection of lines . It is also called as many-sided figure . The lines combined to form polygon are called sides or edges. The lines are obtained by combining two vertices. About P o lygon

103. Types of Polygon 1. Regular Polygon a regular polygon is a polygon that is equiangular (all angles are equal in measure) and equilateral (all sides have the same length). Regular polygons may be either convex or star.

104. Types of Polygon 2 . Convex polygon is a polygon in which the line segment joining any two points within the polygon lies completely inside the polygon

105. 3 . Concave polygon is a polygon in which the line segment joining any two points within the polygon may not lie completely inside the polygon. Types of Polygon

106. 4 . Complex polygon is a concave type polygon with number of edges and the edges are intersected . Types of Polygon

107. Polygon Representation The polygon can be represented by listing its n vertices in an ordered list. P = {(x 1 , y 1 ), (x 2 , y 2 ), ……., (x n , y n )} . The polygon can be displayed by drawing a line between (x 1 , y 1 ), and (x 2 , y 2 ) , then a line between (x 2 , y 2 ), and (x 3 , y 3 ) , and so on until the end vertex. In order to close up the polygon, a line between (x n , y n ), and (x 1 , y 1 ) must be drawn. One problem with this representation is that if we wish to translate the polygon, it is necessary to apply the translation transformation to each vertex in order to obtain the translated polygon.