Basic Raster Graphics Algorithms for Drawing 2D Primitives Prof Lizhuang Ma Shanghai Jiao Tong University
Basic Raster Graphics Algorithms for Drawing 2D Primitives Prof. Lizhuang Ma Shanghai Jiao Tong University
Contents Architecture of a Raster Display Scan Converting lines Filling Rectangles Filling Polygons Clipping lines Clipping Polygons Antialiasing
Contents • Architecture of a Raster Display • Scan Converting Lines • Filling Rectangles • Filling Polygons • Clipping Lines • Clipping Polygons • Antialiasing
Architecture of a Raster display Video Interface with host computer (Display commands)(Interaction data) Display controller Keyboard (DC) Mouse 0000000000000000000111000 000000000000000011100000 000o00000000000001100000 000000000000000000011000 000000000001110000000000 0000ooo011111111111000000 00111111111111111111111 Video controller 0001111111000000011111110 0001111111111111111111110 001111111110001111111110 001111111110001111111110 001111111110001111111110 001111111110001111111110 0001111111111111111111110 Refresh buffer
Architecture of a Raster Display Video
Definitions Pixel: a screen consists ofn x m pixels Bilevel=monochrome, 1 bit/pixel · Color:RGB/ CYK/LU∨ Bitmap / pixmap Frame buffer: an array of data in memory mapped to screen
Definitions • Pixel: a screen consists of N x M pixels • Bilevel = monochrome, 1 bit / pixel • Color: RGB/CYK/LUV… • Bitmap / pixmap • Frame buffer: an array of data in memory mapped to screen
Scan Converting line A scan-converted line showing intensified pixels as black circles
Scan Converting Line • A scan-converted line showing intensified pixels as black circles
The Basic Incremental algorithm Desired line (X; +1, Round (y +m) (X,y) (x+1,y+ (x, Round(yi)) Val=mx +B=m(x+Ar)+b=y, mAr A scan-converted line showing intensified pixels as black circles
The Basic Incremental Algorithm • A scan-converted line showing intensified pixels as black circles
The Basic Incremental Algorithm void Line(into, intyo, intx1, inty 1, value)i Int x Float dy, dx, y, m; dy=y1-y0: dxex1-XO m≡dydx; y=y0; for(X=X0; X<=X1; X++)i WritePixel(x, (int floor(y+0. 5), value +=m y
The Basic Incremental Algorithm void Line (intx0, inty0, intx1, inty1, value) { Int x; Float dy, dx, y, m; dy=y1-y0; dx=x1-x0; m=dy/dx; y=y0; for(x=x0; x<=x1; x++) { WritePixel(x, (int)floor(y+0.5), value); y+=m; } }
Midpoint line algorithm d y y=x+B LNE dx F(x,y)=dy.x-dx y+B dx=0 M a·x+by+c 。.● →F(M)=F(xp+1,yp+)=d Previous Choices for Choices for pixel current pixel next pixel
Midpoint Line Algorithm
Midpoint line algorithm dold= F(xp +l,yp +o=a(xp+l)+b(p+)+c F(xp +2,yp +o=a(xp+2)+b(p +o)+c forE new F(xp +2, yp +x=a(xp +2)+b(p +x)+c forNE I d old +a forE +a+b forNe
Midpoint Line Algorithm
Midpoint line algorithm void midpointLine (into, intyO, intx1, inty 1, value) int dx, dy, incrE, incrNE, d, x, y dy=y1y0;dX=×1-×0;d=dy*2-dX incrE=dy *2; incrNE=(dy-dx) *2 XEX0; y=yO: WritePixel(x, y, value) while(X<x1)i if(d<=0)d+=incrE; X++ else d+=incrNE, X++; y++ Write Pixel(x, y, value)
Midpoint Line Algorithm void MidpointLine(intx0, inty0, intx1, inty1, value) { int dx, dy, incrE, incrNE, d, x, y; dy=y1-y0;dx=x1-x0;d=dy*2-dx; incrE=dy*2;incrNE=(dy-dx)*2; x=x0;y=y0; WritePixel(x, y, value); while(x<x1) { if(d<=0) {d+=incrE;x++; } else {d+=incrNE;x++;y++; } WritePixel(x, y, value); } }