Line drawing algorithm and antialiasing techniques

AA

1. AMITY UNIVERSITY, HARYANA
COMPUTER GRAPHICS
AnkIT GARG
ASSISTAnT PROfESSOR
AMITy UnIvERSITy, HARyAnA

2. Module 1& 2
•Module I: Introduction to Graphics and Graphics Hardware System
•Application of computer graphics, Video Display Devices, Raster Scan
Display, Random Scan Display, Input Devices, Graphic Software and
graphics standards, Numerical based on Raster and Random scan display,
Frame buffer, Display processor.
•Module II: Output Primitives and Clipping operations
•Algorithms for drawing 2D Primitives lines (DDA and Bresenham‘s line
algorithm), circles (Bresenham‘s and midpoint circle algorithm), ellipses
(midpoint ellipse algorithm), Antialiasing (Supersampling method and
Area sampling method), Line clipping (cohen-sutherland algorithm), Curve
clipping algorithm, and polygon clipping with Sutherland Hodgeman
algorithm, Area fill algorithms for various graphics primitives: Scanline fill
algorithm, boundary fill algorithm, flood fill algorithm, Polygon
representation, various method of Polygon Inside test: Even-Odd method,
winding number method, Character generation techniques.

3. Module-II
Line Drawing Algorithms

4. Line Drawing Algorithm
•DDA Line drawing algorithm
•Breshenham’s Line drawing algorithm (Also
called Antialiasing Algorithm)
•These Line drawing algorithms are used for
scan conversion of graphic object i.e. Line.

5. Line Drawing Algorithm
•Scan conversion is a process to represent
graphics objects as a collection of pixels.
•Various algorithm and mathematical
computations are available for this purpose.
•Rasterization-Process of determining which
pixels give the best approximation to a desired
line on the screen.

8. Lines with slope magnitude |m| <1, ∆y = m ∆x
∆x> ∆y
Lines with slope magnitude |m| >1, ∆x = ∆y /m
∆y> ∆x
P1
P2
P1
P2

9. Digital Differential Algorithm(DDA)
•Scan conversion algorithm based on
calculating either ∆x or ∆y.
•Sample the line at unit intervals in one
coordinate and determine the corresponding
integer values nearest the line path for the other
coordinate.
Case 1
Line with positive slope less than or equal to 1,
we sample at unit x intervals (∆x =1) and
determine the successive y value as
Y
k+1
=
Yk
+ m
∆y=m ∆x
Yk+1- Yk =m ∆x
Yk+1- Yk =m (∆x =1)

10. •k takes integer values starting from 1 and
increases by 1 until the final point is reached.
•m can be any number between 0 and 1.
•Calculated y values must be rounded off to
the nearest integer.
•For lines with positive slope greater than 1,
sample at unit y intervals (∆y = 1) and
calculate each successive x value as
x
k+1
= x
k
+ 1/m

11. Steps
P1 ( xa,ya) and P2 (xb,yb) are the two end points.
2. Horizontal and vertical differences between the
endpoint positions are computed & assigned to
two parameters namely dx and dy.
3. The difference with greater magnitude
determines the ‘value’ of increments to be done.
That means the number of times sampling has to
be done. This value is assigned to a parameter
called ‘steps’.

12. 4. Starting from the 1
st
pixel ,we determine the
offset needed at each step to generate the
next pixel position along the line path. Call
the offset value as x
increment
and y
increment
.
The starting points are xa and ya.
Assign x =xa and y=ya
x= x+ x
incr
& y= y+ y
incr
5. Loop through the process steps times, till
the last point xb, yb is reached.
P1
(xa,ya)
P2
(xb,yb)

13. DDA Pseudo-code
// assume that slope is gentle
DDA(float x0, float x1, float y0, float y1) {
float x, y;
float xinc, yinc;
int numsteps;
numsteps = Round(x1) – Round(x0);
xinc = (x1 – x0) / numsteps;
yinc = (y1 – y0) / numsteps;
x = x0;
y = y0;
putpixel(Round(x),Round(y));

for (int i=0; i<numsteps; i++) {
x += xinc;
y += yinc;
putpixel(Round(x),Round(y));
}
}

14. DDA Example
•Suppose we want to draw a
line starting at pixel (2,3) and
ending at pixel (12,8).
numsteps = 12 – 2 = 10
xinc = 10/10 = 1.0 X1-X0= 10
yinc = 5/10 = 0.5 Y1- y0= 5
Iterationx y Round(x) Round(y)
0 2 3 2 3
1 3 3.53 4
2 4 4 4 4
3 5 4.55 5
4 6 5 6 5
5 7 5.57 6
6 8 6 8 6
7 9 6.59 7
8 107 10 7
9 117.511 8
10 128 12 8
// assume that slope is gentle M<=1
DDA(float x0, float x1, float y0, float y1)
{
float x, y;
float xinc, yinc;
int numsteps;
numsteps = Round(x1) – Round(x0);
xinc = (x1 – x0) / numsteps;
yinc = (y1 – y0) / numsteps;
x = x0;
y = y0;
putpixel(Round(x),Round(y));

for (int i=0; i<numsteps; i++) {
x += xinc;
y += yinc;
putpixel(Round(x),Round(y));
}}

15. DDA Example
•Suppose we want to draw a
line starting at pixel (15,4) and
ending at pixel (20,17).
numsteps =
xinc = X1-X0=
yinc = Y1- y0=
Iterationx y Round(x) Round(y)
0
1
2
3
4
5
6
7
8
9
10
// assume that slope is gentle M>1
DDA(float x0, float x1, float y0, float y1)
{
float x, y;
float xinc, yinc;
int numsteps;
numsteps = Round(y1) – Round(y0);
xinc = (x1 – x0) / numsteps;
yinc = (y1 – y0) / numsteps;
x = x0;
y = y0;
putpixel(Round(x),Round(y));

for (int i=0; i<numsteps; i++) {
x += xinc;
y += yinc;
putpixel(Round(x),Round(y));
}}

16. DDA Example
•Suppose we want to draw a
line starting at pixel (6,3) and
ending at pixel (8,10).
numsteps = ?
xinc = ? X1-X0=
yinc = ? Y1- y0=
Iterationx y Round(x) Round(y)
0
1
2
3
4
5
6
7
8
9
10
// assume that slope is gentle M>1
DDA(float x0, float x1, float y0, float y1)
{
float x, y;
float xinc, yinc;
int numsteps;
numsteps = Round(y1) – Round(y0);
xinc = (x1 – x0) / numsteps;
yinc = (y1 – y0) / numsteps;
x = x0;
y = y0;
putpixel(Round(x),Round(y));

for (int i=0; i<numsteps; i++) {
x += xinc;
y += yinc;
putpixel(Round(x),Round(y));
}}

17. DDA Example
•Suppose we want to draw a
line starting at pixel (2,3) and
ending at pixel (5,12).
numsteps = ?
xinc = ? X1-X0=
yinc = ? Y1- y0=
Iterationx y Round(x) Round(y)
0
1
2
3
4
5
6
7
8
9
10

18. DDA Algorithm (continued)
This DDA algorithm suffers from two reasons.
Floating point calculations and rounding operations are expensive and time
consuming.
•Due to limited precision and Rounding operations calculated points will not
be displayed at its original point.
Y_inc
X_inc

19. Bresenham’s Algorithm
•Uses only integer calculations
•Requires less time to generate line due to
elimination of floating point calculations.

20. Bresenham’s Algorithm m<=1
1.Input the two line endpoints and store left endpoint as (x0,y0)
2.Pre-calculate the values dx, dy
3.Color pixel (x0,y0)
4.Let p0 = 2dy –dx, Here P0 is decision parameter which tells us which next
pixel will glow.
5. At each xk along the line, starting with k=0:
6. Repeat Step-5 Until we does not reach up to final point.
Remember! The algorithm and derivation above assumes slopes are less
than or equal to 1. for other slopes we need to adjust the algorithm slightly.
If pk<0, then the next point to plot is (xk + 1,yk),
and pk+1 = pk + 2dy
Otherwise, the next point to plot is (xk + 1, yk + 1),
and pk+1 = pk + 2dy – 2dx

21. Bresenham’s Algorithm Example
Where m<=1
•Suppose we want to draw a line starting at
pixel (2,3) and ending at pixel (12,8).
dx = 12 – 2 = 10
dy = 8 – 3 = 5
p0 = 2dy – dx = 0
t p P(x)P(y)
0 0 2 3
1 -10 3 4
2 0 4 4
3 -10 5 5
4 0 6 5
5 -10 7 6
6 0 8 6
7 -10 9 7
8 0 10 7
9 -10 11 8
10 0 12 8
2dy = 10
2dy – 2dx = -10
Algorithm
1.Input the two line endpoints and
store left endpoint as (x0,y0)
2.Pre-calculate the values dx, dy,
2dy and 2dy -dx
3.Color pixel (x0,y0)
4.Let p0 = 2dy –dx
5.At each xk along the line,
starting with k=0:
6.Repeat Step-4 dx times
If pk<0, then the next point to plot is (xk + 1,yk),
and pk+1 = pk + 2dy (Down pixel will be selected)
Otherwise, the next point to plot is (xk + 1, yk + 1),
and pk+1 = pk + 2dy – 2dx (Upper pixel will be
selected)

22. Anti-aliasing and filtering
techniques

23. Anti-aliasing
•Anti-aliasing is a method of fooling the eye
that a jagged edge is really smooth.
•Due to low resolution aliasing effect will
occur, which can be removed by increasing
the screen resolution.
Circle after applying antialiasing
Jagged edges due to aliasing

24. Some more Examples

25. Reducing Aliasing
•By increasing Resolution
The aliasing effect can be minimized by
increasing resolution of the raster display.

26. Disadvantage of improving resolution
•More memory requirement (Size of frame buffer will become Large)
•More scan conversion time

27. Anti-aliasing Methods
•Super-sampling method or post filtering
•Area sampling or Pre filtering

28. Super-sampling Method
(Cont….)
•In this method every individual pixel is
subdivided in to sub-pixel.
•In this method we count the number of
pixel which are overlapped by the object.
•The intensity value of a pixel is the
average of the intensity values of all the
sampled sub-pixels with in that pixel.
•In this method every pixel on the screen
have different intensity.

29. Super-sampling for a line object
having Non-Zero width.

30. Super-sampling Method (Cont….)
•Pixel at upper right corner is assigned 7/9 because
seven of its nine-sub pixels are inside the object
area.
•Suppose the color of object is RED(1,0,0), and the
background color is light yellow (.5,.5,.5).
•At what intensity the pixel will glow?
(1 X 7/9 +.5 X 2/9, 0X7/9+ 0.5 X 2/9, 0X7/9+.5X2/9)
R G B
Blending of background color and object color will occur
only in area of pixel where object overlaps.
Question-
1. What will be the intensity of center pixel?
Answer- (1 X 1+.5X0, 0X1+.5X0, 0X1+.5X0)
2. What will be the intensity of lower right side pixel?
Answer- (1X1/9 + .5X8/9, 0X1/9+.5X8/9, 0X1/9+.5X8/9)

31. Intensity Variation on pixels after Super sampling method

32. Write Formula for Blending of Colors for following Conditions
1.Object Background is (.5,.5,.5)
2.Object Color is (1,1,0)
Ans:
Write Formula for Blending of Colors for following Conditions
1.Object Background is (.5,.5,.5)
2.Object Color is (1,1,1)

33. Area Sampling Method
•This figure shows how line with a non-Zero width have
different intensity value at each pixel on the screen
•In this Area sampling method intensity value is
determined according to area covered by the object.
90%
15%
65%
50%

34. Thank you!!