Class Clip_Line
- java.lang.Object
-
- renderer.pipeline.Clip_Line
-
public class Clip_Line extends Object
Clip a (projected)LineSegment
that sticks out of the view rectangle in the image plane. InterpolateVertex
color from any clipped offVertex
to the newVertex
.This clipping algorithm is a simplification of the Liang-Barsky Parametric Line Clipping algorithm.
This algorithm assumes that all
Vertex
objects have been projected onto theCamera
's image plane,z = -1
. This algorithm also assumes that the camera's view rectangle in the image plane is-1 <= x <= +1 and -1 <= y <= +1.
If a line segment's projected vertex has an
x
ory
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.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 view rectangle. If this is the case, then return true.
x=-1 x=+1 | | | | ----+----------+----- y = +1 | v1 | | / | | / | | / | | v0 | ----+----------+----- y = -1 | | | |
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 returnfalse
(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
.
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 linesx=1 | v1 | / +----------+ / | | / | | / | | / | | / | | / +----------+ / | / | v0
x = 1
,x = -1
,y = 1
, ory = -1
. The line below will get clipped at least one time (either on the linex = 1
or the liney = -1
) before it is (recursively) a candidate for "trivial rejection". Notice that the line below could even be clipped twice, first ony = 1
, then onx = 1
, before it can be trivially rejected (by being on the wrong side ofy = -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
, andy = -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 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
) andv1
is on the "right" side. Sov0
needs to be clipped off the line segment and replaced by a new vertex.
Represent pointsx=1 v1 | \ | \ | \| \ |\ | \ | \ | v0
p(t)
on the line segment betweenv0
andv1
with the following parametric equation.
Notice that this equation parameterizes the line segment starting withp(t) = (1-t) * v0 + t * v1 with 0 <= t <= 1
v0
att=0
(on the "wrong side") and ending withv1
att=1
(on the "right side"). We need to find the value oft
when the line segment crosses the clipping linex = 1
. Letv0 = (x0, y0)
and letv1 = (x1, y1)
. Then the above parametric equation becomes the two component equations
Since the clipping line in this example isx(t) = (1-t) * x0 + t * x1, y(t) = (1-t) * y0 + t * y1, with 0 <= t <= 1.
x = 1
, we need to solve the equationx(t) = 1
fort
. So we need to solve
for1 = (1-t) * x0 + t * x1
t
. Here are a few algebra steps.
We get similar equations for1 = x0 - t * x0 + t * x1 1 = x0 + t * (x1 - x0) 1 - x0 = t * (x1 - x0) t = (1 - x0)/(x1 - x0)
t
if we clip against the other clipping lines (x = -1
,y = 1
, ory = -1
) and we assume thatv0
is on the "wrong side" andv1
is on the "right side".Let
t0
denote the above value fort
. With this value fort
, we can compute the y-coordinate of the new vertexp(t0)
that replacesv0
.
Here is the algebra.x=1 v1 | \ | \ | \ | p(t0)=(1, y(t0)) | | |
Finally, the new line segment betweeny(t0) = (1-t0) * y0 + t0 * y1 = y0 + t0 * (y1 - y0) = y0 + (1 - x0)*((y1 - y0)/(x1 - x0))
v1
and the new vertexp(t0)
is recursively clipped so that it can be checked to see if it should be trivially accepted, trivially rejected, or clipped again.
-
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static Optional<Primitive>
clip(Model model, LineSegment ls)
If theLineSegment
sticks out of the view rectangle, then return a clipped version that is contained in the view rectangle.
-
-
-
Method Detail
-
clip
public static Optional<Primitive> clip(Model model, LineSegment ls)
If theLineSegment
sticks out of the view rectangle, then return a clipped version that is contained in the view rectangle. The new, clippedLineSegment
object is returned wrapped in anOptional
object.At least one new clipped
Vertex
will be added to theModel
's vertex list (and as many as four new vertices may be added to theModel
's vertex list).If the
LineSegment
is completely outside of the view rectangle, then return an emptyOptional
object to indicate that theLineSegment
should be discarded.- Parameters:
model
-Model
that theLineSegment
ls
comes fromls
-LineSegment
to be clipped- Returns:
- a clipped version of
ls
wrapped in anOptional
object
-
-