On-Line Computer Graphics Notes

CLIPPING

# Overview

The primary use of clipping in computer graphics is to remove objects, lines or line segments that are outside the viewing volume. The viewing transformation is insensitive to the position of points relative to the viewing volume - especially those points behind the viewer - and it is necessary to remove these points before generating the view. Clipping can be done either in three-dimensional space, or in image space. The algorithms are nearly identical.

In this paper, we concentrate on clipping methods for polygons, clipping them against planes. We first develop an inside/outside'' test for points against a plane. This test is used to construct a clipping algorithm for line segments, and the line-segment clipping is used to develop the polygon-clipping algorithm. These methods are then applied to generate an algorithm that clips polygons in the viewing operation.

# Inside/Outside Tests for Points Against a Plane

Given a plane defined by the normal vector and the point .

This plane separates three-dimensional space into two half-spaces: one in the direction of the normal vector, which we will call the in'' side of the plane; and another in the opposite direction of the normal vector, which we will call the out'' side. If we have a point in the plane then the vector is perpendicular to the normal vector , that is

For an arbitrary point in three-dimensional space, this dot product satisfies

where is the angle between the vectors and . So if the point is on the in'' side of the plane, the angle must satisfy , and must be positive. Since the dot product is positive if and only if is positive, this says that the point is on the in'' side of the plane if and only if the dot product is positive. This case is illustrated in the figure below, where the figure has been drawn with the eyepoint on the surface of the plane.

Alternatively if the point is on the out'' side of the plane, then the angle between the vectors and satisfies , and is negative. It follows that the point is on the out'' side of the plane if and only if the dot product is negative.

These facts can be combined to form an inside/outside test for points against a plane:

• A point is defined to be on the in'' side of the plane (the side of the plane to which the normal vector points) if

• A point is defined to be on the out'' side of the plane if

• A point is on'' the plane if

We note that the third case happens infrequently when using floating point arithmetic on computer systems. Normally this must be approximated by

where is a predetermined (small) constant.

# Clipping Line Segments Against a Plane

The inside/outside test forms the basis for clipping line segments against a plane. Let be a plane defined by the normal vector and the point and let be the line segment defined by the two points and , as is shown in the following figure

Let and . We can determine how the line segment is clipped by examining four cases:

1.
Both points and are on the in'' side on the plane - that is, the line segment is completely in''.
2.
Both points and are on the out'' side on the plane - that is, the line segment is completely out''.
3.
is on the in'' side of the plane and is on the out'' side - in which case the line segment crosses the plane. (This is the case for the figure above.)
4.
is on the in'' side of the plane and is on the out'' side - so again, the line segment crosses the plane.

We analyze these cases one at a time. Clearly the side of the plane on which lies is determined by the sign of d1, and similarly, the sign of d2 determines the side of the plane on which lies.

• Case I - d1 >= 0 and d2 > 0, or d1 > 0 and d2 >= 0.

In this case the line segment is on the in'' side of the plane.

• Case II - d1 <= 0 and d2 < 0, or d1 < 0 and d2 <= 0.

In this case the line segment is on the out'' side of the plane.

• Case III - d1 > 0 and d2 < 0

In this case, lies on the in'' side of the plane, and lies on the out'' side of the plane (the case shown in the illustration). Calculate the intersection of the line and the plane by first noting that is a point on the line , and can be represented in the form

To determine t, we first subtract the identity

from both sides of the equation for , giving

Since an are both in the plane, is a vector perpendicular to . So dotting both sides with the normal vector gives

and solving for t, we see that

Once we have calculated , we can say that the line segment lies on the in'' side of the plane and the line segment lies on the out'' side of the plane.

• Case IV - d1 < 0 and d2 > 0

In this case, lies on the out'' side of the plane, and lies on the in'' side of the plane. Calculate the intersection of the line and the plane by

and with calculations similar to those above, we obtain

Once we have calculated , we can state that the line segment lies on the out'' side of the plane and the line segment lies on the in'' side of the plane.

There is one additional case that should be considered. This happens when d1=0 and d2=0. In this case, the line segment lies in'' the plane.

If we examine this closely, we see that the quantities

make sense. When we write the equation , lies on the line between and when , and indeed the values are numbers between zero and one. For example, in case III we have that d1>0 and d2<0, so the denominator of the fraction is greater than the numerator. In case IV, d1<0 and d2>0, so the denominator of the fraction is less than the numerator in value, but the signs on both are negative and the denominator is greater in absolute value, again implying that the result is between zero and one.

# Clipping a Convex Polygon

We can utilize the inside/outside test and the line-clipping algorithm to develop an algorithm for clipping a convex polygon. If we consider the vertices of the polygon one-at-a-time and keep track of when the edges of the polygon cross the plane, the algorithm is actually quite simple.

To implement this polygon clipping algorithm, we usually keep a list of points, commonly called the in'' list, which holds the resulting clipped polygon. The algorithm then iterates through the vertices of the polygon, and has the following steps:

• A vertex is on the in'' side of the plane is retained in the in'' list.
• A vertex is on the out'' side of the plane is discarded.
• If a vertex is on the in'' side of the plane, and the previous vertex in our iteration was on the out'' side, the point-of-intersection of the edge and the plane is calculated and placed on the in'' list. The vertex is then placed on the in'' list.
• If a vertex is on the out'' side of the plane, and the previous vertex in our iteration was on the in'' side, the point-of-intersection of the edge and the plane is calculated and placed on the in'' list. The vertex is discarded.
This algorithm can be implemented with a single loop through the points of the polygon. The only problem is that the edges are defined by two points, and so we must retain two dot products to make our comparisons. The algorithm is illustrated in the following pseudo-code algorithm.

Clipping Algorithm
Given a plane defined by  n and P
Given vertices Q[0], Q[1], ..., Q[length-1]
Let pd = 0

for each vertex i

Let d = n dot (Q[i] - P)

if d times pd < 0 then
calculate I = Q[i-1] + t ( Q[i] - Q[i-1] )
with t = pd / ( pd - d )
insert I into the "in" list
endif

if d >= 0 then
insert Q[i] into the "in" list
endif

Let pd = d
end for loop

Let d = n dot (Q[0] - P)

If d times pd < 0 then
calculate I = Q[length-1] + t ( Q[0] - Q[length-1] )
with t = pd / ( pd - d )
insert I into the "in" list
endif

If are the n vertices of a polygon, we must insure that the last edge of the polygon, , is checked. This is the reason for the last four statements of the algorithm. We must test to see if the last line segment (the one between and crosses the plane, and if so, insert the intersection point into the in list.

This algorithm is guaranteed to work with convex polygons only - non-convex polygons can cause the algorithm to produce some false edges.

# Clipping to a Convex Polyhedra

The three-dimensional analog of a polygon is a polyhedron (e.g., a cube, a truncated pyramid, a dodecahedron). A convex polyhedron can be defined by a finite set of bounding planes and we can clip against the polyhedron by clipping against each plane in turn and using the output polygon of one step as the input polygon to the next. If, at any step, the output polygon is empty, then the process terminates.

We must define the planes so that the normal vectors point toward the inside of the polyhedron.

# Clipping to the Viewing Pyramid

The viewing pyramid is a convex polyhedron - as is the image-space cube. The algorithm for clipping a single convex polygon against a plane can be utilized to clip a polygon against multiple planes of these regions. We simply clip against the planes one at a time, taking the output polygon of one clipping step as the input polygon to the next step.

The planes that bound the truncated viewing pyramid are defined by the following:

1.
the top plane, defined by

2.
the left plane, defined by

3.
the bottom plane, defined by

4.
the right plane, defined by

5.
the near plane defined by

6.
the far plane defined by

Given a polygon, the polygon is clipped against each plane in turn utilizing the result of one clipping operation as the input to the next. Clipping is terminated if all points are clipped out at any one stage.

# Clipping against the Image Space Cube

It is useful to see how the clipping operation simplifies when we clip against the image space cube. Consider the figure below, where we represent the top face of the image space cube.

The top plane is defined by the point and the normal vector . If we consider the point , the in/out test tells us that is in if

That is,

or equivalently that is in'' when y < 1 - which in retrospect, is obvious.

But the dot product that corresponds to the in'' test for the top plane is just y-1 for any point (x,y,z). Similarly, the dot product for the other planes are as follows:

• x-1 for the plane defined by point (1,0,0) and the normal vector <-1,0,0>,
• z-1 for the plane defined by point (0,0,1) and the normal vector <0,0,-1>,
• x+1 for the plane defined by point (-1,0,0) and the normal vector <1,0,0>,
• y+1 for the plane defined by point (0,-1,0) and the normal vector <0,1,0>,
• z+1 for the plane defined by point (0,0,-1) and the normal vector <0,0,-1>,
and so the inside/outside'' test for clipping in these cases contain dot products that do not require multiplies - which makes the algorithm very efficient.

# Clipping in Projective Space

If we are careful, we can also clip in projective space. Here line segments are represented in the same form as in three-dimensional coordinates - that is,

represents a line in projective space, where and are points in four-dimensional projective space. To find the three-dimensional line that corresponds to this four-space line, we project the line onto the w=1 plane, dividing by the w coordinate. This is illustrated in the figure below, where the two w coordinates are assumed positive.

In this case, a line in projective space simply projects to a line in three-dimensional space. However if one of the w coordinates, say w2, is negative then the line projected back into three dimensional space passes through infinity'' as is shown in the next illustration.

The viewing transform produces this second case frequently, for when a polygon is behind the viewer, the viewing transform produces points with a negative w coordinate. So these lines are produced whenever a polygon has vertices both in front of, and behind the viewer.

But we can still clip in projective space. Consider the following illustration, where the line lies on both sides of the w=0 space.

We can find the intersection of this line with the w=0 space by calculating the intersection point , where

and since is in the w=0 space, we must have that the w coordinate of is zero, that is

0 = w1 + t ( w2 - w1 )

and this implies that

 (1)

So, we can calculate the intersection of a line in projective space with the w=0 space, and clip.

A second example is given by the following figure. Here we have the space w=y and a line crossing this space.

Here we can again calculate the intersection of the line with the space by

and since is in the space w=y, we have

w1 + t ( w2 - w1 ) = y1 + t ( y2 - y1 )

which can be solved for t, giving

 (2)

Since we can calculate the intersection, we can clip polygons against this space.

# Clipping in the Viewing Operation

In the viewing operation, the camera transformation transforms points from world space to image space. To implement this transformation we implemented a viewing transformation that produces points in projective space such that, when we project the point back to three-dimensional space, we obtain points in the image-space cube.

The problem, of course, is this projection. The viewing transform can produce points with a negative w coordinate - for when a polygon is behind the viewer, the viewing transform produces points with a negative w coordinate. These points, when projected produce the line segments that pass through infinity'' in three-dimensional space - highly undesirable in computer graphics renderings. So the problem when clipping in the viewing operation is that the points must remain in projective space, but we must still clip on the image-space cube in three-dimensional space.

But we have all the machinery now: We have shown how to clip line segments when our planes and points are in three-dimensional space and have shown how to clip against the image-space cube; and we have also seen that we can (at least in a few cases) clip in projective space. So how do we combine these operations and clip line segments against the image-space cube when our points are in projective space? It's not too difficult.

Let's reexamine the case where we clipped on the top plane of the image space cube, but lets consider a point that has been projected back from projective space.

Here, our three-dimensional inside/outside'' test tells us that the points is in'' if

or

which states, in the case that w is positive, that the point is in'' only if

Now consider a line that crosses the plane y=1 and assume that this line has the two endpoints

both of which have been projected back from projective space.

Any point

that projects to the plane at the top of the image-space cube has the property that y=w, and so clipping the line segment is equivalent to clipping the projective-space line segment defined by the two points

against the space w=y in projective space.

But we have done this in the sections above! We can calculate the intersection by

where t is the value

and then the point projected back to image space is the intersection of the line .

One should notice that the t used to calculate the intersection in homogeneous space is not the same as if the t were calculated in three-dimensional space. In the above figure, we can see that the t in projective space is close to one-half, but the intersection in three-dimensional space is not close to the midpoint.

Now we can do the whole job. We can utilize the clipping method for simple planes in projective space to clip against the image space cube.

1.
In order to first remove the points with a negative w coordinate we clip our projective coordinates against the w=0 space. If we have a point (x,y,z,w), we use the distance measure w, and if given two points (x1,y1,z1,w1) and (x2,y2,z2,w2), we use the ratio

to calculate the intersection with the space.
2.
To remove those points beyond the top plane of the image-space cube, we clip our projective coordinates against the w=y space. If we have a point (x,y,z,w), we use the distance measure y-w, and if given two points (x1,y1,z1,w1) and (x2,y2,z2,w2), we use the ratio

to calculate the intersection with the space.
3.
To remove those points beyond the bottom plane of the image-space cube, we clip our projective coordinates against the w=-y space. If we have a point (x,y,z,w), we use the distance measure y+w, and if given two points (x1,y1,z1,w1) and (x2,y2,z2,w2), we use the ratio

to calculate the intersection with the space.
4.
To remove those points beyond the left plane of the image-space cube, we clip our projective coordinates against the w=-x space. If we have a point (x,y,z,w), we use the distance measure x+w, and if given two points (x1,y1,z1,w1) and (x2,y2,z2,w2), we use the ratio

to calculate the intersection with the space.
5.
To remove those points beyond the right plane in our image-space cube, we clip our projective coordinates against the w=x space. If we have a point (x,y,z,w), we use the distance measure x-w, and if given two points (x1,y1,z1,w1) and (x2,y2,z2,w2), we use the ratio

to calculate the intersection with the space.
6.
To remove those points beyond the front plane of the image-space cube (which corresponds to clipping on the near plane), we clip our projective coordinates against the w=z space. If we have a point (x,y,z,w), we use the distance measure z-w, and if given two points (x1,y1,z1,w1) and (x2,y2,z2,w2), we use the ratio

to calculate the intersection with the space.
7.
To remove those points beyond the back plane of our image-space cube (which corresponds to clipping on the far plane), we clip our projective coordinates against the w=-z space. If we have a point (x,y,z,w), we use the distance measure z+w, and if given two points (x1,y1,z1,w1) and (x2,y2,z2,w2), we use the ratio

to calculate the intersection with the space.
A polygon is clipped against each plane in turn, utilizing the output of one clipping operation as the input to the next. Clipping is terminated if all points are clipped out at any one stage.

It should be noted that we do not necessarily clip against the front and back planes of the image-space cube, as there are frequently applications in which we will wish to see the points outside of the area enclosed by these planes.

One final important fact.

If we examine the viewing transformation, we note that the points behind the viewer get transformed to points with a negative w coordinate. We have already seen that these points cause line segments to pass through infinity'' in homogeneous space. This could cause these line segments to appear to wrap around the screen, which is undesirable in our pictures. The reason for our first clip (of the seven total clips) is to eliminate these problem points by first clipping so that no points will have a negative w coordinate.

This document maintained by Ken Joy