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:

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.

Last changed May 13, 1998, G. Scott Owen, owen@siggraph.org