3. 2D Raster algorithms

Brock University
COSC 3P98 Computer Graphics
Instructor: Brian J. Ross

2d Raster algorithms

• OpenGL definitions: application programmer's view of graphics
• we will now look at (OpenGL) graphic library implementor's view
• What happens when you use OpenGL: 2D primitives

• scan conversion: converting mathematical geometric object into pixel information
• To implement 2d graphics, need a way to scan convert 2d geometric shapes into pixel information
• This can be done via:
• software: using conventional RAM for video memory using computer CPU to do conversions
• graphics coprocessor/ graphics card
• dedicated graphics chip does all conversions
• video memory resident on card
• need software driver for CPU to communicate &control graphics card
• eg. ATI Rage II graphics chips on 3D video cards
• Hardware approach obviously faster: frees CPU to do application program. (hopefully more about hardware later in course)

2d basics

• Converting individual pixels:
• standard 2d array address calculation
• Location(pixel(X,Y)) = StartAddr + (X* MaxY + Y) * #bytes/pixel
• (assuming column major ordering in RAM) Drawing Lines: 1. basic algorithm

• an incremental algorithm
• idea: plot the pixels that appriximately fall on the "real" line • presume slope of line |m| <= 1 (simplifies discussion)
• draw from (x0, y0) to (x1, y1), and presume x0 < x1 • Code: draw line from (x0, y0) to (x1, y1): following works if slope < 1, and x0 < x1
```dy := y1-y0;        /* x, y increments of line */
dx := x1-x0;
m := dy / dx;       /* slope of line */
y := y0;
for x:=x0 to x1 {
write_pixel(x, round(y), colour);
y := y + m;
}```

Lines: basic alg

• To generalize this algorithm for all lines:
• a) if X0 > X1, then swap the points (always draw from lower to higher x)
• b) if the slope > 1, then include another loop that increments from y0 to y1 by 1, and increments X in steps (must interchange y's as in (a) )
• c) horizontal & vertical lines: add special cases, as its much faster to draw them directly w/o incrementing Y and X resp (because Y and X don't change)
• d) lines at a 45 degree angle (slope = 1) can also have a special case made for them (questionable whether such lines are common enough however)
• Problems with this approach:
• need floating point / fractional arithmetic
• computing "round" takes time

Lines: 2. Midpoint algorithm (Bresenham's)

• Advantage: no floating point arithmetic! Therefore much faster than basic algorithm.
• Graphics cards implement this algorithm.
• See text for derivation.
• this algorithm is what is actually implemented in graphics cards & libraries
• general idea: when you are drawing in a particular direction / slope, the coordinate which is changing fractionally either stays the same, or changes by 1 pixel coordinate, on each iteration
• midpoint algorithm derives a fast way to compute when to increase the fractional coordinate, and when to leave it Midpoint program

• draws line from (x0,y0) to (x1,y1), x0 < x1, slope < 1
• (must be generalized as with basic algorithm)
```dx := x1 - x0;
dy := y1 - y0;
d := dy * 2 - dx;
incrE := dy * 2;
incrNE := (dy - dx) * 2;
x := x0;
y := y0;
drawPixel(x, y, colour);
while (x < x1) {
if (d <= 0) {
d += incrE;
x++;
} else {
d += incrNE;
x++; y++;
}
drawPixel(x, y, colour);
}```

Drawing Solid Rectangles

• Solid rectangles are common, and special routines to draw them are used
```for y=ymin to ymax       /* by scan line */
for x = xmin to xmax  /* by pixel in rectangle span */
writepixel(x, y, colour);```
• issue: what if 2 rectangles (and more generally, polygons) share an edge (possibly embedded)?
• if they have different colours, it will look strange
• applies to both filled and unfilled polygons Shared edges

• don't want to rescan same edge twice; order that rectangles drawn can cause flickering (esp in animation)
• solution: point sampling: given rectangle to draw, don't include its top or right edges
• decrement loop extrema by 1
```for y=ymin to ymax-1       /* by scan line */
for x = xmin to xmax-1  /* by pixel in rectangle span */
writepixel(x, y, colour);```

Polygons

• Edge: a line segment, defined by two vertices (end points)
• Polygon: collection of edges in which each vertex shared by 2 (and only 2) edges
• Simple polygons: no intersecting edges • 2 techniques...
• 1. Drawing solid polygons from scratch ("glBegin(GL_POLYGON)" in OpenGL)
• 2. Filling in a hollow or existing solid polygon
• akin to "paint fill" command in Macpaint
• Both techniques need to know where the interior of a polygon resides

Polygon interior test

• Question: given a point P and a simple polygon, is P inside or outside the polygon?
• To determine this, use the Parity Test:
• draw a horizontal line from P to -infinity (ie. as long as necessary)
• count the number of times the line cuts through an edge of polygon
• odd # times? --> P is interior
• even # times? --> P is exterior Polygon interior: special cases

• what if line passes through horizontal edge? --> Collapse it! • What if line passes through a vertex (other than horiz. line)? • Count incremented for vertex intersections as follows, depending on orientation: • Counts: 1, 1, 2, 0 respectively

Scan converting solid polygons

• We will concern ourselves with simple polygons
• OpenGL will handle non-simple ones, with unpredictable results
• First, find edge with minimum Y coord --> call it Ymin
• find edge with max. Y coord --> Ymax
• For Y = Ymin to Ymax
• find intersections of Y with all edges of polygon
• sort these intersections in increasing X values
• use parity check to draw (fill) those regions at Y that are in the interior

Scan converting solid polygons

• Note: computing intersection is expensive: X = (Y - y0)/m + x0
• better solution: for each edge, save where next X intersection will occur based on last X intersection value obtained
• So, for each edge of polygon:
• save inverse of slope: minv = 1/m (compute once per edge)
• save the previous X intersecion coordinate obtained
• In scan converting loop, use this expression to find intersection quickly:
• X_intersection = X_OldInter + minv
• Obviously, need a data structure to be used by scan conversion routine • Because (delta Y)/(delta X) = (1 / V),
v = (delta X)/(delta Y) = (1/m) (m is the slope)

Filling Polygons

• Given: a solid or hollow polygon on the screen
• Task: fill it with a different colour
• Connectivity • 4-connected: every 2 pixels are joined in up, down, left, right directions
• 8-connected: ditto, but including diagonal directions too

Filling Poly's

• Boundary-defined region: largest connected region of pixels for a starting pixel P, whose value is not some boundary value B
• Interior-defined region: largest connected region for starting pixel P that has same value as P
• 1. Flood fill: fill interior-defined region
• 2. Boundary fill: fills boundary-defined region
• Algorithms are very simple.
• weakness: highly recursive, so they can use up stack space fast
• solution: optimize recursive calls
• appearance: fill colours recursively fill up interiors, moving around nooks and crannies (like the game "Qix") Floodfill

• (x,y) is an interior point given to routine...
```FloodFill(x, y, oldColour, newColour) {
if (readPixel(x, y) == oldColour) {
writePixel(x, y, newColour);
FloodFill(x, y-1, oldColour, newColor);
FloodFill(x, y+1, oldColour, newColor);
FloodFill(x-1, y, oldColour, newColor);
FloodFill(x+1, y, oldColour, newColor);
}
}```

Boundary Fill

```BoundaryFill(x, y, boundaryColour, newColour) {
if (c <> boundaryColour and c <> newColour) {
writePixel(x, y, newColour);
BoundaryFill(x, y-1, oldColour, newColor);
BoundaryFill(x, y+1, oldColour, newColor);
BoundaryFill(x-1, y, oldColour, newColor);
BoundaryFill(x+1, y, oldColour, newColor);
}
}```

Pattern filling

• Given an M x N bitmap (pixmap):
• (i) draw a solid polygon with that pattern
• (ii) fill an existing polygon with pattern
• To do this, use previous solid drawing/filling algorithms, but use the bitmap to determine what you draw at each pixel • issue: where to start (anchor) the pattern?
• (a) a set corner of polygon (eg. rectangle corner?) (pattern stationary wrt poly.)
• (b) screen origin? pattern is stationary wrt screen/window
• (c) graphics window origin? "" " (ditto)
• Transparent bitmap: see through 0's, else draw colour; anchor at world coordinates
• if pattern[ x mod M, y mod N] then write_pixel(x,y, pattern[ x mod M, y mod N])
• Opaque pixmap: draw colour set in pixmap, anchor at world coordinates
• write_pixel(x, y, pattern[x mod M, y mod N ])
• Anchor at corner (x1, y1) of polygon:
• write_pixel(x, y, pattern[(x-x1) mod M, (y-y1) mod N ])

Scan converting circles

• Circle equation:

R^2 = X^2 + Y^2

Y = +/- sqrt(R^2 - X^2)

• A. Simple:
```glBegin(GL_POINTS);
loop x=0 to R {
y = sqrt(r*r-x*x);
v2i(x, y);
v2i(x, -y);
v2i(-x, y);
v2i(-x, -y)
glEnd();```
• Problems: expensive; dots printed (use lines for solid circum); undercomputes some portions
• B. Variation:
```glBegin(GL_POINTS);
loop A=0 to 90 {
x = R * cos(A);
y = R * sin(A);
v2i(x, y);
v2i(x, -y);
v2i(-x, y);
v2i(-x, -y);
}
glEnd();
```
• all circum. evenly computed, but more expensive (sin, cos... ouch!)

Circles

• C. Enhancement: compute one 45 degree segment, and copy mirrors
• cuts down math computations by half • D. Bresenham's: Use midpoint approach (like line alg)
• E. NURBS

Clipping

• clipping: only scan convert pixels within a certain region (eg. window)
• graphics hardware has to do this too, to avoid writing to illegal memory locations
• Three ways:
1. Brute force: "scissoring"
• test each pixel as its about to be drawn to see if its within bounds or not
• can be efficient if hardware supported
2. Analytically: compute the new geometry of clipped line or polygon
• line: compute new endpoints
• polygon: compute new polygon(s) vertices and edges
3. Generate entire drawing on a scratch canvas, and then cut and copy visible portion to the screen
• simple to do (especially for text), but wasteful

Clipping lines

• Note: polygons are produced from lines, so they can be clipped edge by edge by clipping lines
• many specialized approaches
• clipping points: • if point not in range, don't plot it
• could do this test for anything you draw

Clipping lines

A. Find new endpoints that intersect window boundary lines

• if both line endpoints within window, then leave as is
• else find new endpoint(s) on window boundary
• because window boundaries are really line segments (not infinite line) use parametric equations
• line endpoints (x0, y0) & (x1, y1):
• x = x0 + T (x1-x0)
• y = y0 +T (y1-y0)
• ( 0 =< T =< 1 )
• Then: set parametric equations for each of 4 window boundaries
• set parametric equation for line segment
• solve for x, y, T edge , T line for each boundary + line
• if T edge and T line both between 0 and 1, then intersection has occurs
• ---> very expensive: lots of division & multiplication when solving 4 sets equations

Clipping Lines

B. Cohen-Sutherland

• fast approach: trivial accept/reject done quickly
• 4 bit code for each endpoint of line segment
• bit represents sign of following, where 1 is negative, 0 is positive
• for one endpoint (X, Y), bit code is: b1 b2 b3 b4
(above, below, right, left)
• b1: sign of (Ymax - Y)
• b2: sign of (Y - Ymin)
• b3: sign of (Xmax - X)
• b4: sign of (X - Xmin) Line Clipping

• if both codes are 0000, line is within window -- don't clip
• do a logical AND for codes for each initial endpoint:
• --> if not equal 0000 then line cannot be in window: leave it
• Else iterate:
• find one bit set to '1'
• eg. 1st bit: then Y > Ymax
• intersect line with Ymax: x = x0 + (1/m) * (Ymax-y0)
• replace old endpoint with this new computed boundary endpoint Clipping polygons

• A polygon is defined by a set of edges (line segments)
• you can apply line clipping to each edge
• but you still need to redefine the clipped polygon (sometimes more than one polygon can be created when clipping) Clipping Polygons

• to clip polygons, we need to clip all four sides of the window Antialiasing

• Aliasing: a sampling error caused by representing a continous quantity with discrete signals
• eg. representing a mathematical line using pixels --> "Jaggies" • if pixel center covered, turn on; else turn off
• Antialiasing: minimize effects of aliasing
• eg. graduate the edges of lines to minimize staircasing
• note that a line to be drawn on screen is really a rectangle with an area (can't have perfect line!)
• pixels also have areas: they are squares
• Types...
1. Pre-filtering
• unweighted area sampling: to antialias the line, draw each pixel covered by this line rectangle with an intensity proportional to the area of the pixel covered
• If distance greater than pixel square's width, then ignore it (it has area intensity of 0)
• weighted area sampling: distance from pixel centre to the line (pixels define circles)
2. Supersampling: compute scan conversion than higher resolution than display
• then average 9 surrounding pixels. (Bryce technique)
3. Post-filtering: weight matrix on rendered image References:

• Computer Graphics Principles and Practice, Foley, van Dam, et al, Addison Wesley 1990, ISBN 0-201-12110-7.

Back to COSC 3P98 index

COSC 3P98 Computer Graphics
Brock University
Dept of Computer Science