CSci 480 Lecture Notes
(Fall) Week Four, Monday: Basic Raster Graphics Algorithms
Clipping algorithms let us deal with a subset of the model world. Rather than
operate on the whole model space, we can manipulate and raster scan a smaller
portion for improved performance in both display and operations on the model.
Line Clipping: Examining line clipping gives an idea of the types of
problems encountered in clipping in general.
Polygon Clipping: Polygons can be clipped using half-planes. The
method extends to general convex polygonal clip regions. This
method also extends to 3D: polyhedra can be clipped using half-spaces.
Clipping Circles
First we do the trivial accept/reject test. If the circle lies completely
inside or outside the clip rectangle, we deal with it trivially. Also if
the clip region lies completely inside the circle's radius, there is a
trivial solution.
If the circle intersects the rectangle, we divide it into quadrants and
do the trivial test for each, followed by tests for octants if necessary.
Then compute the arc intersections with the clip rectangle edges analytically.
Then scan convert the arcs. Scissoring can be used in hardware implementations:
test each pixel against the boundary before it is written.
For a filled circle, spans of pixels on each scan line can be filled by clipping
each span against the clip rectangle.
Generating Characters
Defining and Clipping Characters
There are two basic ways to display text characters. One is to define outline
primitives for each character in each font and then size and raster scan the
outlines on the fly. This is the method used for Microsoft and Macintosh
True Type fonts. This character method looks the same on both the screen and
printed hard copy because the same outline is used to generate raster images
for both outputs.
The other way is to pre-build font caches. A font cache is required for each
font, size, and style (bold, italic, etc.) to be used. If a particular point
size is not pre-generated, it won't be available to the application. Separate
font caches for the screen and printer are required.
Implementing a Text Output Primitive
Programs 3.10 and 3.11.
Advanced Topics
Clipping
Improved algorithms. General polygon-polygon clipping.
Scan-converting primitives
More complicated primitives: elipses, eliptical arcs, cubic curves, general
conic sections. Thick primitives, joining thick line sements. Self-intersecting
polygon fill.
Antialiasing
Numerous situations requiring antialiasing.
Text
Specialized techniques for displaying text including antialiasing.
Filling Algorithms
Flood fill: flood a region within a boundary defined by a specified color.
The MS Windows API has a flood fill function built in.
This page established September 19, 1998; last updated September 17, 1999.