On-Line Computer Graphics Notes
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.
For a postscript 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
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:
is defined to be on the ``in'' side of the plane (the side
of the plane to which the normal vector points) if
is defined to be on the ``out'' side of the plane if
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.
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:
and 
are on the ``in'' side on the plane - that is,
the line segment is completely ``in''.
and 
are on the ``out'' side on the plane -
that is, the line segment is completely ``out''.
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.)
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 
, and
similarly, the sign of 
determines the side of the plane on which 
lies.
and 
, or 
and 
.
In this case the line segment 
is
on the ``in'' side of the plane.
and 
, or 
and 
.
In this case the line segment is on the ``out'' side of the plane.
and 
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.
and 
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 
and 
. 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 
and 
,
so the denominator of the fraction is greater than the numerator.
In case IV,
and 
, 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.
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:
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.
of the edge and the plane is
calculated and placed on the ``in'' list.
The vertex is discarded.
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.
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
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:
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 
, 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
and this implies that
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
which can be solved for t, giving
Since we can calculate the intersection, we can clip polygons against
this space.
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.
and
, we use the ratio
and
, we use the ratio
and
, we use the ratio
and
, we use the ratio
and
, we use the ratio
and
, we use the ratio
and
, we use the ratio
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
All contents copyright (c) 1996, 1997 |
|
