Graphics Reference
In-Depth Information
A point will be inside the clip volume if and only if all of its boundary coordinates are
nonnegative. If the ith boundary coordinate of a point is nonnegative, then we shall
call the point
i-inside
; otherwise, it is
i-out
. Let BC = BC(
p
) = (BC
1
(
p
),BC
2
(
p
),...,
BC
6
(
p
)) denote the vector of boundary coordinates.
Next, let
p0
and
p1
be two points and set BC0 = BC(
p0
) and BC1 = BC(
p1
). The
next table shows the relationship of the segment [
p0
,
p1
] with respect to the ith bound-
ary:
Sign bit
Sign bit
BC0
i
BC1
i
Meaning
0
0
Entire segment is i-inside
1
0
Segment straddles boundary,
p0
is i-out
0
1
Segment straddles boundary,
p1
is i-out
1
1
Entire segment is i-out
It will be convenient to record the sign information of a point
p
into a six-bit word
called its
outcode
and denote it by CODE(
p
). More precisely, the ith bit of CODE(
p
)
will be the sign bit of BC
i
(
p
). Let CODE0 = CODE(
p0
) and CODE1 = CODE(
p1
).
Simple logical operations on CODE0 and CODE1 now give us a lot of information
about the location of the segment. For example, the segment will be inside the clip
volume if (CODE0
or
CODE1) is zero. The segment will be entirely outside the
clip volume if (CODE0
and
CODE1) is nonzero. (Compare this with the Cohen-
Sutherland clipping algorithm.)
Whenever the segment crosses the ith clipping plane, we need to find the inter-
section. This is easy to do if we parameterize the segment, and we have done this sort
of thing before. We need to find the t so that
(
(
)
)
∑=
p0
+
t
p1
-
p0
B
0.
i
With our notation, t = BC0
i
/(BC0
i
- BC1
i
). The segment will intersect the plane only
if this t lies in [0,1]. The expression shows that this can only happen if BC0
i
and BC1
i
have different signs.
Now, the clipping algorithm we are in the process of describing is intended for
situations where we want to do a sequence of “DrawTo” and “MoveTo” commands.
The flag parameter in the “Clip” procedure is used to distinguish between the two
cases and will save us having to write a separate “Clip” procedure for both. The
abstract programs are given in Algorithm 4.6.1 with the ViewPt procedure represent-
ing the next stage of the graphics pipeline after clipping, namely, the clip-space-to-
pixel-space map. A more efficient procedure using goto's, assuming that the trivial
rejects are the most common cases, is shown in Algorithm 4.6.2.
Next, we describe the nontrivial stuff that happens when a segment straddles a
boundary. We basically use the Liang-Barsky algorithm here. In Algorithm 4.6.3, the
variables a0 and a1 keep track of the still-visible part of a segment. MASK is used to
select one boundary at a time. Blinn points out that he does the operation CODE0
or
CODE1
again
on the theory that it will not get done often and we save storing an
