Sutherland-Cohen Line Clipping

Mid-Point Subdivision (Binary Search)

Algorithm

1. Compute region codes for endpoints.

2. Check for trivial accept or reject.

3. If step 2 -> no then compute midpoint of line segment

xm = (x1 + x2) / 2 ym = (y1 + y2) / 2

4. Redo step 1 -> 3 for each 1/2 of line.

Example 1 1) P1 -> 1000 2) no 3) Compute Pm P2 -> 0000 for Pm -> P2 1) Pm -> 0000 , P2 -> 0000 2) yes accept & display
Example 2 for P1 -> Pm 1) P1 -> 1000; Pm -> 0000 2) no 3) Compute new midpoint P Do step 1, 2 for P1 -> P and reject. for P -> Pm, compute P , etc.

With integers, Midpoint Subdivision requires only addition, right shift (/ 2). So it is a good method if perform clipping after viewing transformation to PDC (use integers). But it is not efficient for clipping against window (floating point numbers).

Advantages of clipping against window:

• May be able to completely reject some lines ( Do not have to do viewing transformation [WC -> NDC] on them.)
• Device independence if clip to either viewport or window.

But a disadvantage is that we must do real number arithmetic and division and hence, it is slower.

HyperGraph Table of Contents.
HyperGraph Home page.