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) {
c := readPixel(x, y);
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
R^2 = X^2 + Y^2
Y = +/- sqrt(R^2 - X^2)
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:
- 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
- Analytically: compute the new geometry of clipped line or
polygon
- line: compute new endpoints
- polygon: compute new polygon(s) vertices and edges
- 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...
- 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)
- Supersampling: compute scan conversion than higher resolution
than display
- then average 9 surrounding pixels. (Bryce technique)
- 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
Copyright © 2004 Brian J. Ross
(Except noted figures).
http://www.cosc.brocku.ca/Offerings/3P98/course/lectures/2d/
Last updated: October 15, 2004