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.
Search WWH ::




Custom Search