prev

next

of 25

Published on

28-Mar-2015View

214Download

2

Transcript

- Slide 1

5.1 Si23_03 SI23 Introduction to Computer Graphics Lecture 5 Drawing A Line Slide 2 5.2 Si23_03 Course Outline Image Display URL GIMP colour n Vector graphics Line drawing Area filling n Graphical interaction SVG Viewer 2D vector graphics URL lines., areas graphics algorithms interaction Slide 3 5.3 Si23_03 Line Drawing n Line drawing is a fundamental operation in computer graphics n Demanding applications require very fast drawing speeds - say, 1 million lines per second n Hence the algorithm for converting a line to a set of pixels will be implemented in hardware - and efficiency is vital Want to use integer arithmetic Want to use additions rather than multiplications Slide 4 5.4 Si23_03 Line Drawing - The Problem n To draw a line from one point to another on a display - which pixels should be illuminated? Suppose pt1 = (0,1) and pt2 = (5,4) 0123456 0 1 2 3 4 5 Where to draw the line? Slide 5 5.5 Si23_03 Line Drawing - By Hand n In a simple example, one can do by eye 0123456 0 1 2 3 4 5... but we would like an algorithm! Slide 6 5.6 Si23_03 Equation of a Line n Line equation is: y = m x + c If line joins (x 1,y 1 ) to (x 2,y 2 ), then m = (y 2 -y 1 )/(x 2 -x 1 ) and c = y 1 - m x 1 Suppose pt1 = (0,1) and pt2 = (5,4) 0123456 0 1 2 3 4 5 Then m = (4-1)/(5-0) ie 0.6 and c = 1 Thus: y = 0.6 x + 1 Slide 7 5.7 Si23_03 Drawing a Line From Its Equation n We can use the equation to draw the pixels y = 0.6 x + 1 x = 0 -> y =1y =1 x = 1 -> y = 1.6y = 2 x = 2 -> y = 2.2y = 2 x = 3 -> y = 2.8y = 3 x = 4 -> y = 3.4y = 3 Calculate y for x = 0,1,2,3,4,5 and round to nearest integer 0123456 0 1 2 3 4 5 Slide 8 5.8 Si23_03 The Line Drawn y = 0.6 x + 1 x = 0 -> y =1y =1 x = 1 -> y = 1.6y = 2 x = 2 -> y = 2.2y = 2 x = 3 -> y = 2.8y = 3 x = 4 -> y = 3.4y = 3 Calculate y for x = 0,1,2,3,4,5 and round to nearest integer 0123456 0 1 2 3 4 5 This gives us (after 1 multiplication, 1 addition, and 1 rounding operation per step): How do we make more efficient? Slide 9 5.9 Si23_03 DDA Algorithm n We can do this more efficiently by simply incrementing y at each stage y* = y + q where q = (y 2 -y 1 )/(x 2 -x 1 ) 0123456 0 1 2 3 4 5 y = 1.0y = 1 y = 1.0 + 0.6 = 1.6y = 2 y = 1.6 + 0.6 = 2.2y = 2 y = 2.2 + 0.6 = 2.8y = 3 y = 2.8 + 0.6 = 3.4y = 3 Here q = 0.6 One addition, one rounding Slide 10 5.10 Si23_03 Slope of Line n We have assumed so far that slope of line (m) lies between -1 and 1 n When slope of line is greater than 1 in absolute value, then we increment y by 1 at each step, and x by: d = (x 2 -x 1 )/(y 2 -y 1 ) 0123456 0 1 2 3 4 5 Exercise: calculate the pixels to draw line from (1,0) to (4,5) Slide 11 5.11 Si23_03 Efficiency n The DDA (Digital Differential Analyser)algorithm just described has the problem: floating point operations (real numbers) are expensive - add and round at each step 0123456 0 1 2 3 4 5 Yet really all we need to decide is whether to move horizontally or diagonally (for a line of slope < 1). Can we do this in integer arithmetic? Slide 12 5.12 Si23_03 Bresenhams Algorithm n One of the classic algorithms in computer graphics is the Bresenham line drawing algorithm Published in 1965 Still widely used Excellent example of an efficient algorithm Jack Bresenham Slide 13 5.13 Si23_03 Bresenhams Algorithm - First Step n Look in detail at first step: 012 We have choice of a move to (1,1) or (1,2) Exact y-value at x=1 is: y* = 0.6 + 1 = 1.6 Since this is closer to 2 than 1, we choose (1,2) 0 1 2 d2 d1 Decision based on d1>d2, ie d1-d2>0 0.6 0.4 Slide 14 5.14 Si23_03 Bresenhams Algorithm n In general, suppose we are at (x k,y k ) - slope of line, m, is between 0 and 1 n Next move will be to (x k +1, y k ) or (x k +1, y k +1) d2 d1 xkxk x k +1 ykyk y k +1 d1 = [m(x k + 1)+c] - y k d2 = y k + 1 - [m(x k + 1)+c] d1 - d2 = 2m(x k + 1) - 2y k + 2c -1 >0 indicates (x k +1, y k +1) 5.15 Si23_03 Bresenhams Algorithm d1 - d2 = 2m(x k + 1) - 2y k + 2c -1 : d1-d2 >0 diagonal Let m = Dy/Dx and multiply both sides by Dx, setting Dx(d1 d2) = p k p k = 2Dy x k - 2Dx y k + b (b a real constant) Decision is still p k >0 - but can we work only in integers? How does p k change at next step to p k+1 ? We know that x k increases by 1, and y k either increases by 1 or stays the same. So . Slide 16 5.16 Si23_03 Bresenhams Algorithm p k = 2Dy x k - 2Dx y k + b p k+1 = p k + 2Dy - 2Dx - if y increases p k+1 = p k + 2Dy - if y stays the same Thus we have a decision strategy that only involves Integers, no multiplication and no rounding.. we start things off with p 0 = 2Dy - Dx Slide 17 5.17 Si23_03 Bresenhams Algorithm - A Summary n To draw from A to B with slope 0 5.18 Si23_03 Bresenhams Algorithm - Example 0123456 0 1 2 3 4 5 (x 0,y 0 ) = (0,1) Dx = 5, Dy = 3 - p 1 = p 0 + 2Dy -2Dx = -30 hence plot (1,2) And so on Slide 19 5.19 Si23_03 Bresenhams Algorithm - Other Slopes and Other Shapes n There are straightforward variations for lines with slopes: m > 1 -1 < m < 0 m < -1 n There are similar algorithms for drawing circles and ellipses efficiently - see Hearn & Baker textbook Slide 20 5.20 Si23_03 Other Ways of Drawing Lines n Over past 38 years, researchers have strived to improve on Bresenhams incremental algorithm for example, think how to parallelise the algorithm n Alternative structural approach comes from recognition that horizontal (0) and diagonal (1) moves come in runs n We had: 10101 n One of the moves occurs singly, and is evenly spread within the sequence - the other occurs in up to two lengths (consecutive numbers) 01001000100100010 ie 1 occurs singly, 0 occurs in twos and threes decision is now which length of run 0123456 0 1 2 3 4 5 Slide 21 5.21 Si23_03 Aliasing n Lines on raster displays suffer from aliasing effects - especially noticeable with lines near to horizontal This is caused because we are `sampling the true straight line at a discrete set of positions. Called `aliasing because many straight lines will have the same raster representation. More noticeable on screen than laser printer - why? Slide 22 5.22 Si23_03 Supersampling Bresenham on Finer Grid 012 0 1 2 3 Each pixel is divided into 9 sub pixels. Either 0,1,2 or 3 sub-pixels can be set in any pixel. This can be used to set the intensity level of each pixel. Slide 23 5.23 Si23_03 Supersampling 0123456 0 1 2 3 4 5 21 32 This shows the intensity levels for the pixels in the previous slide. We are really using intensity levels to compensate for lack of resolution. Slide 24 5.24 Si23_03 Antialiased Line 0123456 0 1 2 3 4 5 The end result is a thicker line, with the intensity spread out over a larger area. To the eye, the line appears much sharper and straighter. Slide 25 5.25 Si23_03 d1 - d2 = 2m(x k + 1) - 2y k + 2c -1 : d1-d2 >0 diagonal Let m = Dy/Dx and multiply both sides by Dx, setting Dx(d1 d2) = p k p k = 2Dy x k - 2Dx y k + b (b a constant) Decision is still p k >0 - but can we work only in integers? p k+1 = 2Dy x k+1 - 2Dx y k+1 + b... So p k+1 = p k + 2Dy - 2Dx(y k+1 - y k ) - where (y k+1 - y k ) = 0 or 1 Thus we have a decision strategy that only involves integers.. we start things off with p 0 = 2Dy - Dx Bresenhams Algorithm