public class Clip
extends java.lang.Object
Clip any (projected) line segment that sticks out of the view rectangle
in the view plane. Interpolate vertex color from the clipped off vertex
to the new vertex.
This clipping algorithm is a simplification of the Liang-Barsky Parametric
Line Clipping algorithm.
This algorithm assumes that all LineSegment objects have been projected onto
the camera's view plane, z = -1. This algorithm also assumes that the camera's
view rectangle in the view plane is
-1 <= x <= +1 and
-1 <= y <= +1.
If a line segment's projected vertex has an x or y coordinate with absolute
value greater than 1, then that vertex "sticks out" of the view rectangle.
This algorithm will clip the line segment so that both of the line segment's
vertices are within the view rectangle with -1 <= x <= +1 and -1 <= y <= +1.
Here is an outline of the clipping algorithm.
Recursively process each line segment, using the following steps.
1) Test if the line segment no longer needs to be clipped, i.e., both of
its vertices are within the clipping rectangle. If this is the case,
then return true.
2) Test if the line segment should be "trivially rejected". A line segment
is "trivially rejected" if it is on the wrong side of any of the four
lines that bound the view rectangle (i.e., the four lines x = 1, x = -1,
y = 1, y = -1). If so, then return false (so the line segment will not
be rasterized into the framebuffer).
Notice that a line like the following one is trivially rejected because it
is on the "wrong" side of the line x=1.
x=1
| v1
| /
+----------+ /
| | /
| | /
| | /
| | /
| | /
+----------+ /
| /
| v0
But the following line is NOT trivially rejected because, even though it
is completely outside of the view rectangle, this line is not entirely on
the wrong side of any one of the four lines x = 1, x = -1, y = 1, or y = -1.
The line below will get clipped at least one time (either on the line x = 1
or the line y = -1) before it is (recursively) a candidate for "trivial rejection".
Notice that the line below could even be clipped twice, first on y = 1, then
on x = 1, before it can be trivially rejected (by being on the wrong side
of y = -1).
x=1
| v1
| /
+----------+ /
| | /
| | /
| | /
| | /
| | /
+----------+ /
| /
| /
/
/
v0 |
|
3) If the line segment has been neither accepted nor rejected, then it needs
to be clipped. So we test the line segment against each of the four clipping
lines, x = 1, x = -1, y = 1, and y = -1, to determine if the line segment
crosses one of those lines. We clip the line segment against the first line
which we find that it crosses. Then we recursively clip the resulting clipped
line segment. (Notice that we only clip against the first clipping line which
the segment is found to cross. We do not continue to test against the other
clipping lines. This is because it may be the case, after just one clip, that
the line segment is now a candidate for trivial accept or reject. So rather
than test the line segment against several more clipping lines (which may be
useless tests) it is more efficient to recursively clip the line segment,
which will then start with the trivial accept or reject tests.)
When we clip a line segment against a clipping line, it is always the case that
one endpoint of the line segment is on the "right" side of the clipping line and
the other endpoint of the line segment is on the "wrong" side of the clipping
line. In the following picture, assume that v0 is on the "wrong" side of the
clipping line (x = 1) and v1 is on the "right" side. So v0 needs to be clipped
off the line segment and replaced by a new endpoint.
x=1
|
v1 |
\ |
\ |
\
| \
| \
| v0
Represent points p(t) on the line segment between v0 and v1 with the
following parametric equation.
p(t) = (1-t) * v0 + t * v1 with 0 <= t <= 1
Notice that this equation parameterizes the line segment starting with v0
at t=0 (on the "wrong side") and ending with v1 at t=1 (on the "right side").
We need to find the value of t when the line segment crosses the clipping
line x = 1. Let v0=(x0, y0) and let v1=(x1, y1). Then the above parametric
equation becomes the two component equations
x(t) = (1-t) * x0 + t * x1,
y(t) = (1-t) * y0 + t * y1, with 0 <= t <= 1.
Since the clipping line in this example is x = 1, we need to solve the
equation x(t) = 1 for t. So we need to solve
(1-t) * x0 + t * x1 = 1
for t. Here are a few algebra steps.
x0 - t * x0 + t * x1 = 1
x0 + t * (x1 - x0) = 1
t * (x1 - x0) = 1 - x0
t = (1 - x0)/(x1 - x0)
We get similar equations for t if we clip against the other clipping lines
(x = -1, y = 1, or y = -1) and we assume that v0 is on the "wrong side" and
v1 is on the "right side". With the above value for t, the new point p(t)
that replaces v0 can easily be computed.
x=1
|
v1 |
\ |
\ |
v0=p( (1 - x0)/(x1 - x0) )
|
|
|
Finally, the new line segment between v1 and the new v0 is recursively
clipped so that it can be checked once again to see if it can be trivially
accepted, trivially rejected, or clipped again.