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.
htmladdimg../icons/pdficonsmall.gif For a pdf version of these notes look here.
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
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:
We note that the third case
happens infrequently when using floating point arithmetic on computer systems. Normally this must be approximated by
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:
We analyze these cases one at a time. Clearly the side of the plane on which lies is determined by the sign of d_{1}, and similarly, the sign of d_{2} determines the side of the plane on which lies.
In this case the line segment is on the ``in'' side of the plane.
In this case the line segment is on the ``out'' side of the plane.
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
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
There is one additional case that should be considered. This happens when d_{1}=0 and d_{2}=0. In this case, the line segment lies ``in'' the plane.
If we examine this closely, we see that the quantities
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:
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 endifIf 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.
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.
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:
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
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:
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,
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 w_{2}, 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
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
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
Any point
But we have done this in the sections above! We can calculate the
intersection
by
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.
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.
Return to
the Graphics Notes Home Page
Return
to the Geometric Modeling Notes Home Page
Return
to the Visualization Notes Home Page
Return
to the UC Davis Visualization and Graphics Group Home Page
This document maintained by Ken Joy
All contents copyright (c) 1996, 1997, 1998,
1999
Computer Science Department
University of California, Davis
All rights reserved.