Page 144 - DCAP504_Computer Graphics

Unit 9: Clipping I

The Midpoint subdivision algorithm is written as below:
1. Read two endpoints of the line: A(x1, y1) and A(x2, y2).
2. Read two regions of the window (left top and right bottom): (Wx1, Wy1 and Wx2 and Wy2).
3. Assign 4-bit region codes for the two endpoints. Initialize code with bits 0000.

Set Bit 1 if (x < Wx 1)
Set Bit 2 if (x > Wx 2)
Set Bit 3 if (y < Wy 1)
Set Bit 4 if (y > Wy 2)
4. Check for line visibility
(a) If the region codes for both the endpoints of the line are 0000 then the line is within the
window and completely visible.
Go to step 6
(b) If the region codes for endpoints of the line are not 0000 and the bitwise logical AND is also
not 0000, then the line is outside the window and completely invisible.

Go to step 6
(c) If the region codes for endpoints do not satisfy any of the above two conditions then that line
intersects any one of the window boundaries, and only a segment of the line inside the
window frame is visible.

5. The partially visible line is divided into two equal parts. Repeat step 3 through 5 until the line is
completely visible or completely invisible.
6. Stop.
As Midpoint Subdivision algorithm involves repeated subdivision of the line segments, it is slower
compared to Cohen Sutherland algorithm, which directly performs the calculations to determine the co-
ordinates where the line intersects the window boundaries.
9.3.3 Liang-Barsky Algorithm

Many line clipping algorithms have been developed that perform more line testing in an effective way
before proceeding to the intersection calculations. Cyrus and Beck developed a line clipping algorithm
that performed a quick line testing and then proceeded to the intersection calculations. The algorithm
was based on the analysis of the parametric line equations. Later in 1984, Liang and Barsky
independently devised an even faster algorithm that used inequalities derived from basic parametric
line equations. This algorithm determines and differentiates the clipping region and the visible region of
the window.

Parametric equations are the equations where co-ordinates of points appear dependent
on the parameters.

Consider a line segment with endpoints (x 0, y 0) and (x end, y end). The parametric form of the line is given
as:
x = x 0 + u ∆ x

y = y 0 + u ∆ y 0 ≤ u ≤ 1
where, ∆ x = x end - x 0 and ∆ y = y end - y 0.

LOVELY PROFESSIONAL UNIVERSITY 137