Upload
simpleok
View
33
Download
1
Embed Size (px)
Citation preview
Computer Graphics Lab
Muhammad Ali
RIPHAH UNIVERSITY FAISALABAD
Lecture 01Line Algorithms
07 November 2016
About Me
FAST National UniversityLab 3 or Server RoomOffice Hours – When ever I am available and Free
Some Rules
• – Never ever miss a class– Never use mobile phones in the class– Don’t come in the class after 20minutes– Above all, whatever you do, please do not disturb others
• All parties involved in any kind of cheating or plagiarism in any exam (Lab Tasks, Quizzes, Assignments) will get zero
Raster and Vector Images
• Raster and vector are the two basic data structures for storing and manipulating images and graphics data on a computer
Vector Raster (Bitmap)
• Mathematical calculations that form shapes
• Made of pixels
• Vector programs best for creating logos, drawings and illustrations, technical drawings. For images that will be applied to physical products.
• Raster programs best for editing photos and creating continuous tone images with soft color blends
• Can be scaled to any size without losing quality
• Do not scale up optimally - Image must be created/scanned at the desired usage size or larger
• Resolution-independent: Can be printed at any size/resolution
• Common raster programs: photo editing / paint programs such as Photoshop & Paint Shop, GIMP
• Common vector programs: drawing programs such as Illustrator, CorelDraw, Inkscape.
Rasterization
• A fundamental computer graphics function• Determine the pixels’ colors, illuminations, textures,
etc.
• Rasterization algorithms– Lines – Circles– Triangles – Polygons
Rasterization Operations
• Drawing lines on the screen• Manipulating pixel maps (pixmaps): copying,
scaling, rotating, etc• Compositing images, defining and modifying
regions• Drawing and filling polygons
Line drawing algorithm• Programmer specifies (x,y) values of end pixels• Need algorithm to figure out which intermediate pixels are
on line path• Pixel (x,y) values constrained to integer values• Actual computed intermediate line values may be floats• Rounding may be required. E.g. computed point (10.48, 20.51) rounded to (10, 21)• Rounded pixel value is off actual line path (jaggy!!) • Sloped lines end up having jaggies• Vertical, horizontal lines, no jaggies
Line Drawing Algorithm
0 1 2 3 4 5 6 7 8 9 10 11 12
87654321
Line: (3,2) -> (9,6)
? Which intermediate pixels to turn on?
Line Drawing Algorithm
• Slope-intercept line equation– y = mx + b – Given two end points (x0,y0), (x1, y1), how to compute m
and b?
(x0,y0)
(x1,y1)
dx
dy
0101xxyy
dxdym
0*0 xmyb
Line Drawing Algorithm
• Numerical example of finding slope m:• (Ax, Ay) = (23, 41), (Bx, By) = (125, 96)
5392.010255
231254196
AxBxAyBym
Digital Differential Analyzer (DDA): Line Drawing Algorithm
(x0,y0)
(x1,y1)
dx
dy
Walk through the line, starting at (x0,y0) Case a: x is incrementing faster (m < 1)
Step in x=1 increments, compute and round yCase b: y is incrementing faster (m > 1)
Step in y=1 increments, compute and round x
DDA Line Drawing Algorithm (Case a: m < 1)
(x0, y0)
x = x0 + 1 y = y0 + 1 * m
Illuminate pixel (x, round(y))
x = x + 1 y = y + 1 * m
Illuminate pixel (x, round(y))
…
Until x == x1
(x1,y1)
x = x0 y = y0
Illuminate pixel (x, round(y))myy kk 1
DDA Line Drawing Algorithm (Case b: m > 1)
y = y0 + 1 x = x0 + 1 * 1/m
Illuminate pixel (round(x), y)
y = y + 1 x = x + 1 /m
Illuminate pixel (round(x), y)
…
Until y == y1
x = x0 y = y0
Illuminate pixel (round(x), y)(x1,y1)
(x0,y0)
mxx kk
11
15
We will use the simple DDA algorithm to draw a line with starting point (2,0) and ending point (7,4) on a pixel based display. Firstly, we compute the slope m:m =(Yend–Ystart)/(Xend–Xstart)=(4–0)/(7–2)=4/5 = 0.8y = Ystart = 0 x = Xstart + 1 = 2 + 1 =3
x y Round(y) 2 03 y = y + m = 0 +
0.8=0.8 1
4 y = y + m = 0.8 + 0.8=1.6 2
5 y = y + m = 1.6 + 0.8=2.4 2
6 y = y + m = 2.4 + 0.8=3.2 3
7 4
16
We will use the simple DDA algorithm to draw a line with starting point (2,2) and ending point (6,7) on a pixel based display. Firstly, we compute the slope m:m =(Yend–Ystart)/(Xend–Xstart)=(7–2)/(6–2)=5/4m=1/m = 0.8, y = Ystart + 1 = 2 + 1 = 3 , x= Xstart =2
y x Round(x) 2 23 x = x + m = 2 +
0.8=2.8 3
4 x = x + m = 2.8 + 0.8=3.6 4
5 x = x + m = 3.6 + 0.8=4.4 4
6 x = x + m = 4.4 + 0.8=5.2 5
7 6
DDA Line Drawing Algorithm Pseudocode
compute m;if m < 1:{
float y = y0; // initial valuefor(int x = x0;x <= x1; x++, y += m)
setPixel(x, round(y));}else // m > 1{
float x = x0; // initial valuefor(int y = y0;y <= y1; y++, x += 1/m)
setPixel(round(x), y);}• Note: setPixel(x, y) writes current color into pixel in column x and row y in
frame buffer
Line Drawing Algorithm Drawbacks
• DDA is the simplest line drawing algorithm– Not very efficient – Round operation is expensive
• Optimized algorithms typically used. – Integer DDA– E.g.Bresenham algorithm
Task for next lab
• Add Glut and OpenGL libraries in Visual Studio• Link for Setting up OpenGL in Visual Studio• http://in2gpu.com/2014/10/15/setting-up-opengl-
with-visual-studio/