Polygon Clipping
[Hill: p. 202-204. Foley & van Dam: p.
124-127]
The Sutherland-Hodgman algorithm can be used to clip any
polygon (convex or concave) against any convex clipping polygon. The algorithm
clips against one edge at a time, producing a new vertex list each time. The
following figure assumes the most common case, a rectangular clipping window.
The algorithm can be summarized as follows:
for each side of clipping window
for each edge of polygon
output points based upon the following table
Example
Using Outcodes for Trivial Accept and Reject
[Hill: p.
96-98]
In many cases, two trivial tests can be used to quickly determine
whether a polygon is completely inside or outside the viewing window. This then
allows us to skip the above clipping procedure. The trivial tests require
first computing outcodes.
A vertex outcode consists of four bits: TBRL, where:
- T is set if y > top,
- B is set if y < bottom,
- R is set if x > right, and
- L is set if x < left.
Trivial accept: all vertices are
inside (all outcodes are 0000)
Trivial
reject: all vertices are outside with respect
to any given side(bitwise AND is not 0000)
