Graphics Reference
In-Depth Information
Figure 3.10.
A Sutherland-Hodgman polygon-clipping example.
the clip polygon. Eliminating such edges from the final result would be a nontrivial
effort, but normally they do not cause any problems. We run into this bogus edge
problem with other clipping algorithms also.
An implementation of the Sutherland-Hodgman algorithm can be found in
[PokG89].
3.3.2
Weiler Polygon Clipping
Another early polygon clipping algorithm was developed in the context of the visible
surface determination algorithm in [WeiA77]. Weiler and Atherton needed a new algo-
rithm because the Sutherland-Hodgman algorithm would have created too many aux-
iliary polygons. An improved version of the algorithm can be found in [Weil80]. Here
is a very brief description of the algorithm:
The boundaries of polygons are assumed to be oriented so that the inside of
the polygon is always to the right as one traverses the boundary. Note that inter-
sections of the subject and clip polygon, if any, occur in pairs: one where the
subject
enters
the inside of the clip polygon and one where it
leaves
.
Step 1:
Compare the borders of the two polygons for intersections. Insert ver-
tices into the polygons at the intersections.
Step 2:
Process the nonintersecting polygon borders, separating those contours
that are outside the clip polygon and those that are inside.
Step 3:
Separate the intersection vertices found on all subject polygons into two
lists. One is the
entering list,
consisting of those vertices where the
polygon edge enters the clip polygon. The other is the
leaving list,
con-
sisting of those vertices where the polygon edge leaves the clip polygon.
Step 4:
Now clip.
