Output primitives in Computer Graphics

This slide contain description about the line, circle and ellipse drawing algorithm in computer graphics. It also deals with the filled area primitive.

1. Output Primitives Points and Lines Line Drawing Algorithms DDA Algorithm Bresenham’s Line Algorithm Midpoint Circle Algorithm Midpoint Ellipse Algorithm Filled Area Primitives

2. Points and Lines Point is the fundamental element of picture representation. It is the position in the plan defined as either pair or triplets of number depending upon the dimension. Two points represent line or edge and 3 or more points a polygon. Curved lines are represented by the short straight lines.

3. Line Drawing Algorithms Slope-Intercept Equation Slope Intercept Interval Calculation

4. Line Drawing Algorithm

5. DDA Algorithm  Digital Differential Analyzer Sample the line at unit intervals in one coordinate Determine the corresponding integer values nearest the line path in another co-ordinate

6. DDA Algorithm (left to right) Slope For |m|<1 (| Δ y|< | Δ x|) Sample line at unit interval in x co-ordinate For |m|>1 (| Δ y|> | Δ x|) Sample line at unit interval in y co-ordinate

7. DDA Algorithm (right to left) Slope For |m|<1 (| Δ y|< | Δ x|) Sample line at unit interval in x co-ordinate For |m|>1 (| Δ y|> | Δ x|) Sample line at unit interval in y co-ordinate

8. DDA Algorithm Input the two line endpoints and store the left endpoint in (x ,y ) Plot first point (x ,y ) Calculate constants Δ x, Δ y If | Δ x| > | Δ y| steps = | Δ x| else steps = | Δ y| Calculate XInc = | Δ x| / steps and Y Inc = | Δ y| / steps At each x k along the line, starting at k=0, Plot the next pixel at (xk + XInc, yk + YInc) Repeat step 6 steps times

9. Pseudo Code Void lineDDA(int xa, int ya, int xb, int yb) { int dx = xb – xa, dy = yb – ya, steps, k; float xIncrement, yIncrement, x = xa, y = ya; if( abs (dx) > abs (dy) ) steps = abs (dx); else steps = abs (dy); xIncrement = dx / (float) steps; yIncrement = dy / (float) steps; setPixel (ROUND (x), ROUND (y)); for (k=0; k<steps; k++){ x += xIncrement; y += yIncrement; setPixel (ROUND(x), ROUND(y)); } }

10. Use DDA algorithm for rasterizing line (0,0) to (6,6). Use DDA algorithm for rasterizing line (0,0) to (4,6).

11. Bresenham’s Line Algorithm Uses only incremental integer calculations Which pixel to draw ? (11,11) or (11,12) ? (51,50) or (51,49) ? Answered by Bresenham

12. For |m|<1 Start from left end point (x ,y ) step to each successive column (x samples) and plot the pixel whose scan line y value is closest to the line path. After (x k ,y k ) the choice could be (x k +1,y k ) or (x k +1,y k +1)

13. Then And Difference between separations

14. Defining decision parameter [ 1] Sign of p k is same as that of d 1 -d 2 for Δ x>0 (left to right sampling) For Recursive calculation, initially Constant=2 Δ y + Δ x(2b-1) Which is independent of pixel position c eliminated here because x k+1 = x k + 1 y k+1 -y k = 0 if p k < 0 y k+1 -y k = 1 if p k ≥ 0 Substitute b = y – m.x and m = Δ y / Δ x in [1]

15. Algorithm Steps (|m|<1) Input the two line endpoints and store the left endpoint in (x ,y ) Plot first point (x ,y ) Calculate constants Δ x, Δ y, 2 Δ y and 2 Δ y- 2 Δ x, and obtain p = 2 Δ y – Δ x At each x k along the line, starting at k=0, perform the following test: If p k <0, the next point plot is (x k +1,y k ) and P k+1 = p k + 2 Δ y Otherwise, the next point to plot is (x k + 1, y k +1) and P k+1 = p k + 2 Δ y - 2 Δ x Repeat step 4 Δ x times

16. What’s the advantage? Answer: involves only the calculation of constants Δ x, Δ y, 2 Δ y and 2 Δ y- 2 Δ x once and integer addition and subtraction in each steps

17. Example Endpoints (20,10) and (30,18) Slope m = 0.8 Δ x = 10, Δ y = 8 P = 2 Δ y - Δ x = 6 2 Δ y = 16, 2 Δ y-2 Δ x = -4 Plot (x ,y ) = (20,10)

18. Use Bresenham’s algorithm for rasterizing the line (5,5) to (13,9)

19. Digitize a line with endpoints (15,18) and (10,15) using BLA.

20. Digitize a line with endpoints (15,15) and (10,18) using BLA.

21. Algorithm Steps (| m|>1 ) Input the two line endpoints and store the left endpoint in (x ,y ) Plot first point (x ,y ) Calculate constants Δ x, Δ y, 2 Δ x and 2 Δ x- 2 Δ y, and obtain p = 2 Δ x – Δ y At each x k along the line, starting at k=0, perform the following test: If p k <0, the next point plot is ( x k , y k +1) and P k+1 = p k + 2 Δ x Otherwise, the next point to plot is ( x k + 1, y k +1) and P k+1 = p k + 2 Δ x - 2 Δ y Repeat step 4 Δ x times

22. Use BLA algorithm for rasterizing line (0,0) to (4,6).

23. Circle-Generating Algorithms (Basic Foundations) Circle Equation: Points along circumference could be calculated by stepping along x-axis:

24. Problem (in above method) Computational complexity Spacing: Non-uniform spacing of plotted pixels

25. Adjustments (To fix problems) Spacing problem (2 ways): Interchange the role of x and y whenever the absolute value of the slope of the circle tangent > 1 Use polar co-ordinate: Equally spaced points are plotted along the circumference with fixed angular step size. step size chosen for θ depends on the application and display device. Computation Problem: Use symmetry of circle; i.e calculate for one octant and use symmetry for others.

26. Circle Symmetry

27. Bresenham’s Algorithm Could Be Adapted ?? Yes How ? Setting decision parameter for finding the closest pixel to the circumference And what to do For Non-linear equation of circle ? Comparison of squares of the pixel separation distance avoids square root calculations

28. Midpoint Circle Algorithm Circle function defined as: Any point (x,y) satisfies following conditions

29. Decision parameter is the circle function; evaluated as:

30. y k+1 = y k if p k <0 y k+1 = y k -1 otherwise Thus P k+1 = P k + 2x k+1 +1 if pk<0 P k+1 = P k + 2x k+1 +1-2y k+1 otherwise Also incremental evaluation of 2x k+1 and 2y k+1 2x k+1 = 2x k + 2 2y k+1 = 2y k – 2 if p k >0 At start position (x ,y ) = (0,r) 2x = 0 and 2y = 2r

31. Initial decision parameter For r specified as an integer, round p to P = 1-r (because all increments are integers)

32. Algorithm Input radius r and circle center (x c , y c ) and obtain the first point on the circumference of a circle centered on the origin as (x ,y ) = (0,r) Calculate the initial value of the decision parameter as P = 5/4 – r At each x k position, starting at k = 0, perform the following test: If p k < 0 , the next point along the circle centered on (0,0) is (x k+1 ,y k ) and P k+1 = p k + 2x k+1 + 1 Otherwise, the next point along the circle is (x k +1,y K -1) and P k+1 = p k + 2x k+1 + 1 -2y k+1 Where 2x k+1 = 2x k + 2 and 2y k+1 = 2y k -2 Determine the symmetry points in the other seven octants. Move each calculated pixel position (x,y) onto the circular path centered on (x c ,y c ) and plot the co-ordinate values: x = x + x c , y = y+y c Repeat steps 3 through 5 until x ≥ y

33. Given radius =10 use mid-point circle drawing algorithm to determine the pixel in the first quadrant. Solution: P = 1-r = - 9 (x , y )=(0,10) 2x =0 2y =20

34. Digitize the circle (x-2)^2+(y-3)^2=25 in first quadrant. Solution: P0=(1-r)= - 4 (x , y )=( 0,5) 2x =0 2y =10

35. Ellipse Generating Algorithms Equation of ellipse: F1 (x 1 ,y 1 ), F2(x 2 ,y 2 ) General Equation Simplified Form In polar co-ordinate

36. Ellipse function

37. From ellipse tangent slope: At boundary region (slope = -1): Start from (0,r y ), take x samples to boundary between 1 and 2 Switch to sample y from boundary between 1 and 2 ( i.e whenever ) Slope=-1

38. In the region 1 For next sample Thus increment For increment calculation; Initially: Incrementally: Update x by adding 2r y 2 to first equation and update y by subtracting 2r x 2 to second equation

39. Initial value (0,r y )

40. In the region 2 For next sample Initially For simplification calculation of p2 can be done by selecting pixel positions in counter clockwise order starting at (r x ,0) and unit samples to positive y direction until the boundary between two regions

41. Algorithm Input r x ,r y , and the ellipse center(x c ,yc) and obtain the first point on an ellipse centered on the origin as (x ,y ) = (0,r y ) Calculate the initial value of the decision parameter in region 1 as At each x k position in region 1, starting at k = 0, perform the following test: If p1 k < 0, the next point along the ellipse centered on (0,0) is (x k+1 ,y k ) and Otherwise, the next point along the ellipse is (x k +1,y k -1) and With and continue until

42. Calculate the initial value of decision parameter in region 2 using the last point (x ,y ) calculated in region 1 as At each y k position in region 2, starting at k = 0, perform the following test: If p2k>0, the next point along the ellipse centered on (0,0) is (x k ,y k -1) and Otherwise the next point along the ellipse is (x k +1,y k -1) and Using the same incremental calculations for x and y as in region 1. Determine the symmetry points in the other three quadrants. Move each calculated pixel position (x,y) onto the elliptical path centered on (x c ,y c ) and plot the co-ordinate values: X = x + x c , y = y+ y c Repeat the steps for region 1 until

43. Digitize the ellipse with parameter r x =8 and r y =6 in first quadrant. Solution:

44. Filled Area Primitives Two basic approaches for area filling: By determining overlap intervals for scan lines Start from given interior position and filling outwards

45. Scan Line P olygon F illed A lgorithm I ntersection points of scan line with the polygon edge are calculated. Points are sorted from left to right. Corresponding frame buffer position between each intersection pair are set by specified color.

46. A scan line pass through vertex, intersect two polygon edges.

47. Scan line y’ Intersect even number of edges 2 pairs of intersection points correctly find the interior span Scan line y Intersect an odd number of edges(5) Must count the vertex intersection as only one point

48. How to distinguish these cases? Scan line y Intersecting edges are on the opposite side Scan line y’ Intersecting edges are on the same side. By tracing around the boundary, If the endpoint y values of two consecutive edges monotonically increases or decreases count middle vertex as single

49. Implementation

50. In determining edge intersection, we can set up incremental set up calculation using fact that slope of edge is constant.

51. Inside Outside test Odd Even rule: Odd edge means interior Non zero winding number rule Non zero winding number means interior

52. Scan line fill for Curved Area Require more works than polygon filling due to non-linear boundary. We calculate the scan line intersection and fill all the interior points. Symmetries between the quadrant can be used to reduce the calculation.

53. Boundary fill algorithm Fill the region starting from the interior point until the appropriate color boundary is reached. Two ways: 4 connected 8 connected

54. 4 connected

55. 8 connected

56. Using 4 connected flood fill algorithm