Liang–Barsky Algorithm

The Liang–Barsky algorithm [9] (named after You-Dong Liang and Brian A. Barsky) uses the parametric equation of a line and inequalities describing the range of the clipping box to determine the intersections between the line and the clipping box. With these intersections it knows which portion of the line should be drawn. This algorithm is significantly more efficient than Cohen–Sutherland.

The idea of the Liang-Barsky clipping algorithm is to do as much testing as possible before computing line intersections. Consider first the usual parametric form of a straight line:

(5.1)

A point is in the clip window, if

(5.2)

which can be expressed as the 4 inequalities

(5.3)

were

(5.4)

To compute the final line segment we must perform following steps:

1. A line parallel to a clipping window edge has p_k = 0 for that boundary.

2. If for that k, q_k < 0, the line is completely outside and can be eliminated.

3. When p_k < 0 the line proceeds outside to inside the clip window and when p_k > 0, the line proceeds inside to outside.

4. For nonzero p_k, u=qk/pk gives the intersection point.

5. For each line, calculate u₁ and u₂. For u₁, look at boundaries for which p_k < 0 (outside -> in). Take u₁ to be the largest among (0, qk/pk). For u₂, look at boundaries for which p_k > 0 (inside -> out). Take u₂ to be the minimum of (1, qk/pk). If u₁ > u₂, the line is outside and therefore rejected.

Поиск по сайту: