CG - Clipping

Clipping

CLIPPING OPERATIONS

Generally, any procedure that identifies those portions of a picture that is eitherinside or outside
of a specified region of space is referred to as a clipping algorithm,or simply clipping. The region
against which an object is to clipiscalled a clip window.

Types of Clipping:

Generally we have Clipping algorithm for the following primitive type:

• Point Clipping
• Line Clipping
• Area Clipping (Polygon)
• Curve Clipping
• Text Clipping

Point Clipping

 The Clip window is a rectangle to the standard position, we save a point P=(x,y) for
display if the following inequalities are satisfied:

xwmin<=x<=xwmax
ywmin<=y<=ywmax

Where the edges of the clip window (xwmin ,xwmax) and (ywmin, ywmax), can be either the
coordinate window boundaries. If any one of these four inequalities is not satisfied , the point is
clipped.

Line Clipping

Line that do not intersect the clipping window are either completely inside the window or
completely outside the window. In the case of line clipping , four different cases are possible.

1. Both endpoints of the line lie with in the clipping area. This means that the line is
included completely in the clipping area, so that the whole line must be drawn.
2. One end point of the line lies with inthe other outside the clipping area. It is necessary to
determine the intersection point of the line with the bounding rectangle of the clipping
area. Only a part of the line should be drawn.
3. Both end points are located outside the clipping area and the line do not intersect the
clipping area. In the case , the line lies completely outside the clipping area and can be
neglected for the scene.

DEPARTMENT OF INFORMATION TECHNOLOGY

FATIMA COLLEGE (Autonomous), MADURAI-18. Page 1
 CG - Clipping

4. Both endpoints are located outside the clipping area and the line intersect the clipping
area. The two intersection points of the line with the clipping are must be determined.
Only the part of the line between these two intersection points should be drawn.

Cohen-Sutherland Line Clippings

This algorithm uses the clipping window as shown in the following figure. The minimum
coordinate for the clipping region is (XW_min,YW_min)and the maximum coordinate for the
clipping region is (XWmax,YWmax)

We will use 4-bits to divide the entire region. These 4 bits represent the Top, Bottom, Right, and
Left of the region as shown in the following figure. Here, the TOP and LEFT bit is set to 1
because it is the TOP-LEFT corner.

DEPARTMENT OF INFORMATION TECHNOLOGY

FATIMA COLLEGE (Autonomous), MADURAI-18. Page 2
 CG - Clipping

Bit 1=x-xw min (TOP)

Bit 2= xw max-x (BOTTOM)
Bit3=y-yw min (RIGHT)
Bit 4= yw max-y(LEFT)

There are 3 possibilities for the line −

 Line can be completely inside the window (This line will be completely removed from
the region).
 Line can be completely outside of the window (This line will be completely removed
from the region).
 Line can be partially inside the window (We will find intersection point and draw only
that portion of line that is inside region).

Algorithm

Step 1 − Assign a region code for each endpoints.

Step 2 − If both endpoints have a region code 0000 then accept this line.

Step 3 − Else, perform the logical ANDoperation for both region codes.

Step 3.1 − If the result is not 0000, then reject the line.

Step 3.2 − Else you need clipping.

Step 3.2.1 − Choose an endpoint of the line that is outside the window.

Step 3.2.2 − Find the intersection point at the window boundary (base on region code).

Step 3.2.3 − Replace endpoint with the intersection point and update the region code.

Step 3.2.4 − Repeat step 2 until we find a clipped line either trivially accepted or trivially
rejected.

Step 4 − Repeat step 1 for other lines.

Liang Barsky line clipping algorithm

1) Read two end points of line P1 (x1, y1) and P2 (x2, y2)
2) Read two corner vertices, left top and right bottom of window: (Xw min, Yw max) and (Xw max, Y
DEPARTMENT OF INFORMATION TECHNOLOGY
FATIMA COLLEGE (Autonomous), MADURAI-18. Page 3
 CG - Clipping

w min)
3) Calculate values of parameters pi and qi for I =1, 2, 3, 4 such that
p1 = -Δx
q1 = x1 – Xw min

p2 = Δx
q2 = Xw max – x1

p3= – Δy
q3 = y1 – Yw min

p4 = Δy
q4 = Yw max – y1

4) If pi = 0 then,(boundary condition checking)

{
Line is parallel to ith boundary.
If qi < 0 then,
{
Line is completely outside the boundary. Therefore, discard line segment and Go to Step 10.
}
else
Check line is horizontal or vertical and accordingly check line end points with corresponding
boundaries. If line endpoints lie within the bounded area then use them to draw line. Otherwise
use boundary coordinates to draw line. Go to Step 10.
}
}
5) Initialize t1 = 0 and t2 = t1
6) Calculate values for qi/pi for i= 1,2,3,4
7) Select values of qi/pi where pi<0 and assign maximum out of them as t1.
8) Select values of qi/pi where pi>0 and assign maximum out of them as t2.
9) If (t1 < t2)
{
Calculate endpoints of clipped line:
xx1 = x1 + t1 Δx
xx2 = x1 + t2 Δx
yy1 = y1 + t1 Δy
yy2 = y1 + t2 Δy
Draw line (xx1, yy1, xx2, yy2)
}
10) Stop.
DEPARTMENT OF INFORMATION TECHNOLOGY
FATIMA COLLEGE (Autonomous), MADURAI-18. Page 4
 CG - Clipping

Nicholl – Lee – Nicholl Line Clipping:

1. It avoids multiple clipping

2. Disadvantage – only applicable to two dimensional clipping.
 For a line with endpoint P1 and P2, we have to determine the position of P1.
 There are 9 possible regions for P1, but we will consider the 3 regions. They areP1 in
window, P1 in edge position, P1 in corner region.

 If p1 lies in any one of the other six regions, we have to move P1 in to these three regions.
 For each of these cases one determines the regions with the property that no matter where
in the region the second point P2 is, the segment will have to be intersected with the same
boundaries of the window. These regions are determined by drawing the rays from P1
through the four corners of the window. The following abbreviations were used:

T – ray intersects top boundary LT – ray intersects left and top boundary
L – ray intersects left boundary LR – ray intersects left and right boundary
B – ray intersects bottom boundary LB – ray intersects left and bottom boundary
R – ray intersects right boundary TR – ray intersects top and right boundary
TB – ray intersects top and bottom boundary

These regions determines the unique boundary for the line segment.

DEPARTMENT OF INFORMATION TECHNOLOGY

FATIMA COLLEGE (Autonomous), MADURAI-18. Page 5
 CG - Clipping

To determine the region in which P2 is located, we compare slope and lines to the slopes of the
boundaries of the clip regions.

If P1 is left of clipping rectangle then P2 is in region LT if

Y intersection position is

X intersection position is

Line Clipping using Nonrectangular Polygon Clip Windows

• Can add additional edges to a concave clipping regions to make it into a set of convex ones.

• Then can use an extension of Liang-Barsky to clip in these convex regions

Polygon Clipping

Collection of connected lines is considered as Polygon. A polygon clipper takes as input the
vertices of a polygon and returns one(ormore) polygons.Polygon is alled convex if the line
joiningany two interior points of the polygon liescompletely inside the polygon. A non-
convexpolygon is said to be concave.

SUTHERLAND-HODGMAN ALGORITHM

Each edge of the polygon must be testedagainst each edge of the clip rectangle; newedges must
be added, and existing edges mustbe discarded, retained, or divided. Multiplepolygons may
result from clipping a singlepolygon. We need an organized way to dealwith all these cases.

DEPARTMENT OF INFORMATION TECHNOLOGY

FATIMA COLLEGE (Autonomous), MADURAI-18. Page 6
 CG - Clipping

Steps of Sutherland-Hodgman's polygonclipping algorithm

First the polygon is clipped against the left edge of the polygon window to get new vertices of
the polygon. These new vertices are used to clip the polygon against right edge, top edge, bottom
edge, of the clipping window as shown in the following figure.

While processing an edge of a polygon with clipping window, an intersection point is found if
edge is not completely inside clipping window and the a partial edge from the intersection point
to the outside edge is clipped. The following figures show left, right, top and bottom edge
clippings −

DEPARTMENT OF INFORMATION TECHNOLOGY

FATIMA COLLEGE (Autonomous), MADURAI-18. Page 7
 CG - Clipping

Four Cases of polygon clipping against one edge

 Case 1 : Wholly inside visible region - save endpoint

 Case 2 : Exit visible region - save the intersection
 Case 3 : Wholly outside visible region - save nothing
 Case 4 : Enter visible region - save intersection and endpoint

DEPARTMENT OF INFORMATION TECHNOLOGY

FATIMA COLLEGE (Autonomous), MADURAI-18. Page 8
 CG - Clipping

Weiler- Atherton Polygon Clipping

The basic idea in the algorithm is that instead of always proceeding around the polygon edges are
vertices are processed, We sometime want to follow the window boundaries . Which path we
follow depends on the polygon processingdirection(Clock wise or counterclockwise)We have
the following rule for this:

 For an outside to inside pair of vertices, follow the polygon boundary.

 For an inside to outside pair of vertices, follow the window boundary in the clock wise
direction.

Curve Clipping

Curve clipping procedure will invoke nonlinear equation.

The boundary rectangle for a circle or other curved object can be used first to test for overlap
with a rectangular boundary window. If the bounding rectangle for the object is completely
inside the window , we save the object. If the rectangle is determined to be completely outside
the window , we discard the object.

DEPARTMENT OF INFORMATION TECHNOLOGY

FATIMA COLLEGE (Autonomous), MADURAI-18. Page 9
 CG - Clipping

Text Clipping

Text clipping can be of two types:

1. All or none string -clipping : In this clipping if all the string is inside a clip window, we
keep it. Otherwise, the string is discarded.

2. All or none character -clipping: in this clipping we discard only those characters that are
not completely inside the window

DEPARTMENT OF INFORMATION TECHNOLOGY

FATIMA COLLEGE (Autonomous), MADURAI-18.Page 10
 CG - Clipping

Exterior clipping

 In exterior clipping, the picture parts are to be saved are those that are outside the region.
This is referred to as exterior clipping.

 Applications
• Multiple window systems
• The design of page layouts in advertising or publishing.
• Adding labels or design patterns to a picture

DEPARTMENT OF INFORMATION TECHNOLOGY

FATIMA COLLEGE (Autonomous), MADURAI-18.Page 11