Open Mobile Map

Line Clipping

It is desirable to restrict the effect of graphics primitives to a subregion of the canvas, to protect other portions of the canvas.

All primitives are clipped to the boundaries of this clipping rectangle; that is, primitives lying outside the clip rectangle are not drawn.

The default clipping rectangle is the full canvas (the Window), and it is obvious that we cannot see any graphics primitives outside the screen.

So, if we clip lines outside the window we may have the result as Fig (b) below:

Before we discuss clipping lines, let’s look at the simpler problem of clipping individual points.

If the x coordinate boundaries of the clipping rectangle are Xmin and Xmax, and the y coordinate boundaries are Ymin and Ymax, then the following inequalities must be satisfied for a point at (X,Y) to be inside the clipping rectangle:

Xmin < X < Xmax and Ymin < Y < Ymax

If any of the four inequalities does not hold, the point is outside the clipping rectangle. From now we will study actual clipping algorithms.

Cohen-Sutherland Clipping

To clip a line, we need to consider only its endpoints, not its infinitely many interior points.

If both endpoints of a line lie inside the clip rectangle, the entire line lies inside the clip rectangle and can be trivially accepted.

If one endpoint lies inside and one outside, the line intersects the clip rectangle and we must compute the intersection point.

If both endpoints are outside the clip rectangle, the line may or may not intersect with the clip rectangle, and we need to perform further calculations to determine whether there are any intersections.

To do this, Cohen-Sutherland Clipping Algorithm first encode the line endpoints. Encoding is done by four criteria. So, four bit is need to each endpoint.

1)Is the point Above the window? (Top)

2)Is the point Under the window? (Bottom)

3)Is the point on the Left side of the window? (Left)

4)Is the point on the Right side of the window? (Right)

1 for True, 0 for False.

After encoding, we may accept if the line is fully inside the window, or discard if the line is fully outside the window.

Four Clipping Cases

There can be four cases.

First, see the line AB. Both endpoints can be encoded as 0000. So, it means that the line is fully inside the window, So Accept all.

Second, see the line EF (0010 , 1010) Result of logical and operation is not 0000 (0010), and it means the it is fully outside the window, so discard.

Third, see the line CD(0000, 1010). This is the case of one endpoint inside the window and the other is not. In this case the line may be shorten.

Forth, see the line GH and IJ (0001, 1000). We can not make a decision only with outcodes. Because it may be fully outside the window like line GH, and it may have some intersections like line IJ. So in this case, the line may be discarded or shorten.

Overall Steps for Cohen-Sutherland Clipping Algorithm

This is the overall algorithm of Cohen-Sutherland Clipping Algorithm.

If the line enters and if the line is fully inside the window –> Accept & End.

If the line fully outside the window –> Reject & End.

If the line intersecting on a point –> Compute an intersected point and split the line on that point.

Change the outcode & loop again.

Detail Steps for Cohen-Sutherland Clipping Algorithm

End-points pairs are check for trivial acceptance or trivial rejected using the outcode.

If not trivial-accepance or trivial-rejected, divided into two segments at a clip edge.

Iteratively clipped by testing trivial-acceptance or trivial-rejected, and divided into two segments until completely inside or trivial-rejected.

Trivial acceptance/reject test

To perform trivial accept and reject tests, we extend the edges of the clip rectangle to divide the plane of the clip rectangle into nine regions. Each region is assigned a 4-bit code deteermined by where the region lies with respect to the outside halfplanes of the clip-rectangle edges. Each bit in the outcode is set to either 1 (true) or 0 (false); the 4 bits in the code correspond to the following conditions:

* Bit 1 : outside halfplane of top edge, above top edge

Y > Ymax

* Bit 2 : outside halfplane of bottom edge, below bottom edge

Y < Ymin

* Bit 3 : outside halfplane of right edge, to the right of right edge

X > Xmax

* Bit 4 : outside halfplane of left edge, to the left of left edge

X < Xmin

Conclusion

In summary, the Cohen-Sutherland algorithm is efficient when outcode testing can be done cheaply (for example, by doing bitwise operations in assembly language) and trivial acceptance or rejection is applicable to the majority of line segments .(For example, large windows - everything is inside , or small windows - everything is outside).

Pseudo-code of Cohen-Sutherland Algorithm.

procedure CohenSutherlandLineClipAndDraw(

x0,y0,x1,y1,xmin,xmax,ymin,ymax : real ; value: integer);

/* Cohen-Sutherland clipping algorithm for line P0=(x1,y0) to

P1=(x1,y1) and clip rectangle with diagonal from (xmin,ymin) to

(xmax,ymax).*/

type

edge = (LEFT,RIGHT,BOTTOM,TOP);

outcode = set of edge;

var

accept,done : boolean;

outcode0,outcode1,outcodeOut : outcode;

/*Outcodes for P0,P1, and whichever
point lies outside the clip rectangle*/

x,y : real;

procedure CompOutCode(x,y: real; var
code:outcode);

/*Compute outcode for the point (x,y) */

begin

code := [];

if y > ymax
then code := [TOP]

else if y <
ymin then code := [BOTTOM];

if x > xmax
then code := code +[RIGHT]

else if x <
xmin then code := code +[LEFT]

end;

begin

accept := false; done := false;

CompOutCode (x0,y0,outcode0);
CompOutCode (x1,y1,outcode1);

repeat

if(outcode0=[]) and
(outcode1=[]) then /*Trivial accept and exit*/

begin accept := true; done:=true end

else if
(outcode0*outcode1) <> [] then

done := true /*Logical intersection is
true, so trivial reject and exit.*/

else

/*Failed both tests, so calculate the line segment to clip;

from an outside point to an intersection with clip edge.*/

begin

/*At least one endpoint is outside the clip rectangle; pick it.*/

if outcode0 <> [] then

outcodeOut := outcode0 else outcodeOut := outcode1;

/*Now find intersection point;

use formulas y=y0+slope*(x-x0),x=x0+(1/slope)*(y-y0).*/

if TOP in outcodeOut then

begin /*Divide line at top of
clip rectangle*/

x := x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);

y := ymax

end

if BOTTOM in outcodeOut then

begin /*Divide line at bottom
of clip rectangle*/

x := x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);

y := ymax

end

else if RIGHT in outcodeOut then

begin /*Divide line at right
edge of clip rectangle*/

y := y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);

x := xmax

end

else if LEFT in outcodeOut then

begin /*Divide line at left
edge of clip rectangle*/

y := y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);

x := xmin

end;

/*Now we move outside point to intersection point to clip, and get
ready for next pass.*/

if (outcodeOut = outcode0) then

begin

x0 := x; y0 := y; CompOutCode(x0,y0,outcode0)

end

else

begin

x1 := x; y1 := y; CompOutCode(x1,y1,outcode1);

end

end /*subdivide*/

until done;

if accept then
MidpointLineReal(x0,y0,x1,y1,value) /*Version for real coordinates*/

end; /*CohenSutherlandLineClipAndDraw*/