600.457 Lecture Week 7

Clipping, Hidden Surface Elimination

2D Line Clipping

We are primarily interested in determining the part of geometry that lie inside the window. The simplest algorithm to eliminate such parts is to scan-convert the full geometry and at each computed pixel position, test if the pixel lies in the appropriate range. If the computed pixel is outside the window, discard it. This technique, called scissoring, is highly inefficient. Ideally we would like to find the points of intersection of the geometry with the window boundaries and compute modified geometry that does not jut out of the window -- which, then, can be rasterized directly using the algorithms discussed earlier. The only extra time is spent in modifying the geometry in this case. Point clipping is trivial. If each coordinate of the point lies in the proper range (of the window), the point lies inside the window, otherwise it is outside it. In order to clip line segment against a clip-window, we need to find intersections of the line with the window boundary. A simple line clipping algorithm can be based on point clipping. For example, if both points of a line segment lie inside a window, the line segment must lie inside the window, if the window is convex. Cohen and Sutherland formalized this idea for an upright window by dividing the region around this window in 9 regions. Each region is identified by a four bit code called outcode -- one bit for each boundary of the window as shown below.

If both outcodes are 0000, the entire line-segment must be inside the window. Similarly, if both end-points lie on the right of the window (i.e. have an outcode of xx10), the segment can be trivially discarded. In general if the logical AND of the outcodes of the end points is not 0000, the line segment can be discarded. If the logical OR is 0000, the segment is ready to be rasterized. outcode is simple as well. If the window limits are given by xl <= x <= xr and yb <= y <= ya. The four outcodes, from left to right, are the signs of x-xl, xr-x, y-yb and ya-y, respectively. Trivial rejections and acceptances are relatively simple. In case none of the two (AND, OR) tests succeed, the line may or may not intersect the window (see lines 1 and 2). Cohen and Sutherland devised the following recursion to perform clipping for non-trivial cases:

Start with a point outside the window (at least one point must be outside).
Test the line segment against the edges of window in a fixed order.
If the two end-points of the line segment lie on different sides of the edge, compute the intersection of the line with that edge and clip the part outside the window.
Replace the clipped end-point with the intersection point, compute its outcode, and start again.

To find the point of intersection between two lines, we need to solve their equations simultaneously. Another techniques is by using parametric equations. The equation of a line between points P1 and P2 is given by a a function of an arbitrary parameter p(t): (1-t)*P1 + t*P2. At t=0, p(t) = P1 and at t=1, p(t) = P2. Each point between P1 and P2 corresponds to a value of t between 0 and 1. p(t) for values of t outside [0,1] still lie on the same line, but not on the line segment P1-P2. Similar algorithms by Liang & Barsky and Cyrus & Beck use parametric equations to perform clipping which is more efficient for lines that are not trivially accepted or rejected. Here is the idea:

Consider the window edge E_i and the point p_i on it. Consider end-points P0 and P1 of the line segment to be clipped. N_i is the normal to the edge E_i, pointing outwards. It is easy to see

that at the point of intersection, p(t), of the line with the edge E_i,
N_i.[p(t)-p_i] = 0. Thus the value of t at which the intersection occurs is: N_i.[p(t)-p_i] / -N_i.[P1-P0] (Substitute the expression for p(t) in Eq 1.)

Of course, we need to check that the denominator is not equal to 0. (What does it mean for the denominator to be 0?)

We know now, how to find the point of intersection -- what about the rest of clipping? For this we classify each intersection as PE (potentially entering) or PL (potentially leaving). If moving from P0 to P1 (i.e. lower value of t to higher value of t), if we enter the window we call the intersection PE, and if we leave the window, we call the intersection PL. (PE implies N_i.[P1-P0] > 0 and vice-versa.) To find the clipped line-segment, we must identify the "inner-most" PE-PL pair. We find all intersections of the (infinite) line P0P1 with the window edges and select the PL intersection with the minimum t value and the PE intersection with the maximum t value. We select the clipped segment if both the PE and PL t values are in the range [0,1] and the value for PE is lower than that for PL.

Polygon Clipping

Line clipping can be extended to polygon clipping by clipping each edge of the polygon with each edge of the window. The algorithm by Sutherland and Hodgeman does just that. For each clip-edge, it starts at a vertex of the polygon and follows the vertices in the polygon order, deleting old or introducing new ones. At each stage it has a valid polygon, with some parts clipped out. There are four cases to consider at each step of moving from vertex v0 to v1 (assume we have already processed v0):

v0 is inside and v1 is inside the window: Retain v1, move to next vertex.
v0 is inside and v1 is outside the window: Discard v1, replace with the point of intersection between v0v1 and the clip-edge.
v0 is outside and v1 is inside the window: Add the point of intersection between v0v1 and the clip edge to the output.
v0 is outside and v1 is outside the window: Discard v1.

Note that thin spurious lines may be generated along the window edges by this algorithm if concave polygons are clipped. This can be handled by splitting input polygons into more than one smaller polygons. If the input polygon is clockwise, splitting is needed when moving outside to inside the window Similarly, for counter-clockwise polygons, outside-to-inside movement causes a split. Splitting is achieved by following the window (clip-polygon) vertices back to the last intersection point.

3D clipping is a simple extension of 2D clipping -- we perform each operation for three coordinates, rather than two coordinates. Note that we can simplify clipping against perspective view-frustums by clipping in the three-dimensional screen coordinates -- one obtained after perspective division.

Clipping in homogeneous Coordinates

Recall that for convenience and efficiency, we represent our vertices using four coordinates -- the fourth one being the homogeneous coordinate. The real three dimensional point represented by [x, y, z, w] is [x/w, y/w, z/w]. We can perform this division before clipping but that results in wasted work in division for points clipped out. We can perform clipping directly in homogeneous coordinates by making our window extents homogeneous. Here is the idea:

Suppose we want to find if x/w < x_min, we can compute this by testing if x < w_min, assuming w > 0. (What if w < 0?).