BSP Tree Hierarchies - Real-Time Collision Detection - page 368

E

E

F

A

A

D D

C

B

B

Figure 8.12 Clipping the polygon ABDE illustrates the four cases of the Sutherland-Hodgman
polygon-clipping algorithm. The points of the output polygon BCFA are shown in gray in the
cases in which they are output.

one polygon edge at a time and has four cases based on what sides of the clip-
ping plane the edge startpoints and endpoints lie. The four cases are illustrated in
Figure 8.12. In the first case, when both points lie in front of the plane the endpoint
is output. The second case is the edge going from in front of the plane to behind the
plane, for which the intersection point of the edge with the plane is output. The third
case is when both points lie behind the plane, for which nothing is output. Finally,
the forth case is when the edge goes from behind the plane to in front of the plane.
In this case, both the intersection point and the endpoint are output.
With the Sutherland-Hodgman algorithm, only the portion of the polygon in front
of the plane is retained. Because both pieces of the polygon must be retained for
the BSP tree construction, the algorithm must be extended accordingly. In addition,
because the clipping plane has been made thick one or more rules dealing with
vertices lying on the plane must be added. One commonly used set of rules is outlined
in Table 8.1, to which a fifth case has been added to the original four to deal with
points on the plane.
One reason for working with thick planes was previously mentioned: inherent
floating-point inaccuracies in computing the intersection point I means it will not lie
exactly on the mathematical plane. Another related benefit of working with a thick

Table 8.1 Output rules for the modified Sutherland-Hodgman clipping algorithm dealing
with a thickened plane and retaining both parts of the polygon. The rules are given in terms
of the directed segment AB . I represents the intersection point of AB with the clipping plane.

Front Polygon Back Polygon

A (previous vertex) B (current vertex) Output Output

In front In front B None

Behind In front I, B I

In front Behind I I, B

Behind Behind None B

Any On B B