December 7, 2009

Polygon Clipping

Clipping Faces

Before we start filling polygons, we must clip them to the edges of the view volume. We can do this with the Sutherland-Hodgeman polygon clipping algorithm. This process involves clipping individual edges against the sides of the 'clipping polygon'. A separate algorithm is available for edge clipping, this is called the Cohen-Sutherland algorithm.

Cohen-Sutherland Edge Clipping

As with most graphics procedures, edge clipping needs to be very efficient, as there are typically thousands of edges in a scene. Edge clipping involves testing a line segment against a clipping rectangle and then clipping the line segment until it lies entirely within the clipping rectangle.

We must first determine if the end points of the edge lie inside or outside the clipping rectangle (window). Each edge of the window defines an infinite line that divides the plane in to an inside and outside half-space.

Inside-Outside Half-Spaces

For each end-point (x,y), we associate a 4-bit code, with one bit for each edge of the window. This code will be used to record if the end-point is in any of the 4 outside half-spaces. The bits will be set as follows;

$bit_{0}$ set if $y>y_{top}$
$bit_{1}$ set if $y<y_{bottom}$
$bit_{2}$ set if $x>x_{right}$
$bit_{3}$ set if $x<x_{left}$

This allows us to make the following two tests;

If all bits are zero, the point lies entirely inside the window. If both end-points lie inside the window, then the line-segment lies within the widow and does not need to be clipped, no further processing is required.
If both end-points lie within the same outside half-space (corresponding bits are set), then the line segment lies entirely outside the window and can be rejected without further processing.

In all other cases, the line-segment needs to be clipped against the window. A divide and conquer strategy is used. The line segment is clipped against one of the edges, this produces a new line segment. The new line segment is the subjected to the tests above. This process continues until the line-segment is rejected or accepted according to the tests above. A line segment needs to be clipped against an edge, if the corresponding bit has been set for one of its end-points.

Clipping an line against an edge

In the figure above, we wish to clip the line segment $P_{1}(x_{1},y_{1}), P_{2}(x_{2},y_{2})$ to the clipping edge given as $x_{right}$ . The desired line segment is $A(x_{a}, y_{a}), P_{2}$ . We know that$ x_{a}\equiv x_{right}$ . Using the equation of a line where $m$ is the slope;

\[ a_{y}=m(x_{right}-x_{2})+y_{2} \]

We can use similar reasoning in order to clip against other edges. The full clipping algorithm can now proceed as follows;

Construct inside-outside codes for both end points$ (P_{1} \& P_{2})$ .
If both codes are zero, accept line segment and exit.
If both codes are set for same outside half-space, reject line and exit.
If $P_{1}$ is inside the window, swap $P_{1}$ and $P_{2}$ (the following tests only applies to $P_{1}$ ).
If $P_{1}$ is outside right edge, clip to right edge and return to step 1.
If $P_{1} $ is outside left edge, clip to left edge and return to step 1.
If $P_{1}$ is outside top edge, clip to top edge and return to step 1.
$P_{1}$ must be outside bottom edge, clip and return to step 1.

Sutherland-Hodgeman Polygon Clipping

This algorithm, like the Cohen-Sutherland edge clipping algorithm, uses a divide an conquer approach and uses the edges of the clipping rectangle to divide space into inside and outside half space.

Result of Sutherland-Hodgeman clipping

The basic operation is to clip the polygon against one edge of the clipping rectangle, this operation produces a new (clipped) polygon (see figure below), which we then clip against the remaining edges in turn. To clip the polygon against one edge, we simply clip all the edges of the polygon against the edge of the clipping rectangle. As each edge is clipped, new vertices are output according to certain rules. Each edge has and start point $s$ , and an end point $f$ , there are 4 possible configurations between and edge and the inside/outside half-spaces;

both $s$ and $f$ are inside: output $f$ .
$s$ is inside and $f$ is outside: output the intersection point , $i$ .
both $s$ and $f$ are outside: output nothing.
$s$ is outside and $f$ is inside: output intersection $i$ and then $f$ .

Possible intersection Configurations

The set of vertices output after traversing the polygon becomes the new (partially clipped polygon) for the next clipping edge.

Result of Clipping against one edge