上海交通大学：Basic Raster Graphics Algorithms for Drawing 2D Primitives

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); } }