Mid Point Subdivision Line Clipping

It is a method used for clipping. But Instead of calculating the boundaries of the window like cohen sutherland algorithm we subdivide the line at it's endpoints until the line segment is of either visible or invisible category.

The midpoints of two endpoints (x1,y1) and (x1,y2) is found by:

• (x1+x2)/2
• and (y1+y2)/2

First we find x3=(x1+x2)/2. The line segment x3x2 is completely invisible. whereas the  line segment x1x3 is partially visible.

So we further divide it in to two ie, x4=(x1+x3)/2. Now the line segment x1x4 is completely visible.

while the line segment x4x3 is partially visible.

On further dividing the line segment x4x3 we get the point x5 which is on the  point of intersection of window boundary.

Algorithm:

Step1: Calculate the position of both endpoints of the line.
            Assign four bit region codes for the two end points.

Step2: Perform OR operation on both of these endpoints.

Step3: If the OR operation gives 0000
            then
                    Line is guaranteed to be visible go to step 7
          else
                  Perform AND operation on both endpoints.
                  If AND ≠ 0000
            then the line is invisible go to step 7
      else
            then the line is a clipped case.

Step4: if the line segment is partially visible. Find midpoint
            X_m=(x₁+x₂)/2
            Y_m=(y₁+y₂)/2
            X_mis midpoint of X coordinate.
            Y_mis midpoint of Y coordinate.

Step6: until  the line segments  is totally visible or totally invisible , repeat step 1 to. 6.

Step7: Stop algorithm.

Advantages:

• It is suitable in machine in which multiplication and division is not possible because it can be performed by introducing clipping divides in hardware.

Disadvantages:

• As midpoint sub division involves repeated division It is slower than cohen sutherland clipping  as it directly finds the intersection points.