Graphics Reference
In-Depth Information
To simplify the notation, we introduce variables c
k
and q
k
and rewrite these equations
as
ct q
ct q
ct q
ct q
£
£
£
£
1
1
2
2
3
3
.
4
4
Set t
k
= q
k
/c
k
whenever c
k
π 0. Let
B
1
,
B
2
,
B
3
, and
B
4
denote the left, right, bottom,
and top boundary lines of the window, respectively. With this notation we can make
the following observations:
(1) If c
k
> 0, then
L
goes from the “inside” to the “outside” of the boundary line
B
k
as t increases and we shall call t
k
an
exit
value.
(2) If c
k
< 0, then
L
goes from the “outside” to the “inside” of the boundary line
B
k
as t increases and we shall call t
k
an
entry
value.
(3) If c
k
= 0, the
L
is parallel to
B
k
, which is outside the window if q
k
< 0.
The clipping algorithm now proceeds by analyzing the three quantities q
k
, c
k
, and t
k
.
Algorithm 3.2.3.1 is a high-level version of the Liang-Barsky algorithm. Algorithm
3.2.3.2 gives the code for the actual Liang-Barsky algorithm.
3.2.3.1 Example.
Consider the segment [
P
1
,
P
2
] in Figure 3.6. We see that c
1
, c
4
<
0 and c
2
, c
3
> 0. In other words, t
1
and t
4
are entry values and t
2
and t
3
are exit values.
The picture bears this out. One can also easily see that t
1
< 0 < t
2
< t
4
< 1 < t
3
. There-
fore, there is an entry value (t
4
) that is larger than an exit value (t
2
). Using the algo-
rithm we conclude that the segment lies entirely outside the window, which is correct.
Reject the segment as soon as
an entry value is larger than 1 or
an exit value is less than 0 or
an entry value is larger than an exit value
Otherwise, the segment meets the window. We need to compute an intersection
only if t0 > 0 and t1 < 1, where
t0 = max (0, max { entry values t
k
} ), and
t1 = min (1, min { exit values t
k
} ).
(The case where t0 = 0 or t1 = 1 means that we should use the endpoint, that is,
no clipping is necessary.)
Algorithm 3.2.3.1.
High-level Liang-Barsky line-clipping algorithm.