Clipping:
When we have to display a large portion of the picture, then not only scaling & translation is necessary, the visible part of picture is also identified. This process is not easy. Certain parts of the image are inside, while others are partially inside. The lines or elements which are partially visible will be omitted. For deciding the visible and invisible portion, a particular process called clipping is used. Clipping determines each element into the visible and invisible portion. Visible portion is selected. An invisible portion is discarded.
Types of Lines:
Lines are of three types:
- Visible: A line or lines entirely inside the window is considered visible
- Invisible: A line entirely outside the window is considered invisible
- Clipped: A line partially inside the window and partially outside is clipped. For clipping point of intersection of a line with the window is determined.
Clipping can be applied through hardware as well as software. In some computers, hardware devices automatically do work of clipping. In a system where hardware clipping is not available software clipping applied.
Following figure show before and after clipping
The window against which object is clipped called a clip window. It can be curved or rectangle in shape.
Applications of clipping:
- It will extract part we desire.
- For identifying the visible and invisible area in the 3D object.
- For creating objects using solid modeling.
- For drawing operations.
- Operations related to the pointing of an object.
- For deleting, copying, moving part of an object.
Clipping can be applied to world co-ordinates. The contents inside the window will be mapped to device co-ordinates. Another alternative is a complete world co-ordinates picture is assigned to device co-ordinates, and then clipping of viewport boundaries is done.
Types of Clipping:
- Point Clipping
- Line Clipping
- Area Clipping (Polygon)
- Curve Clipping
- Text Clipping
- Exterior Clipping
Point Clipping:
Point Clipping is used to determining, whether the point is inside the window or not. For this following conditions are checked.
- x ≤ xmax
- x ≥ xmin
- y ≤ ymax
- y ≥ ymin
The (x, y) is coordinate of the point. If anyone from the above inequalities is false, then the point will fall outside the window and will not be considered to be visible.
Program1:
To implement Point Clipping:
- #include<stdio.h>
- #include<conio.h>
- #include<graphics.h>
- inttlx,tly,brx,bry,px,py;
- void point_clip()
- {
- intwxmin,wymin,wxmax,wymax;
- wxmin=tlx;
- wxmax=brx;
- wymin=tly;
- wymax=bry;
- if(px>=wxmin&&px<=wxmax)
- if(py>=wymin&&py<=wymax)
- putpixel(px,py,RED);
- getch();
- closegraph();
- }
- void main()
- {
- intgd=DETECT,gm,xc,yc,r;
- clrscr();
- printf(“Enter the top left coordinate”);
- scanf(“%d%d”,&tlx,&tly);
- printf(“Enter the bottom right coordinate”);
- scanf(“%d%d”,&brx,&bry);
- printf(“\n Enter the point”);
- scanf(“%d%d”,&px,&py);
- initgraph(&gd,&gm,“c:\\tc\\bgi”);
- setbkcolor(BLUE);
- setcolor(RED);
- rectangle(tlx,tly,brx,bry);
- point_clip();
- }
Output:
Line Clipping:
It is performed by using the line clipping algorithm. The line clipping algorithms are:
- Cohen Sutherland Line Clipping Algorithm
- Midpoint Subdivision Line Clipping Algorithm
- Liang-Barsky Line Clipping Algorithm
Cohen Sutherland Line Clipping Algorithm:
In the algorithm, first of all, it is detected whether line lies inside the screen or it is outside the screen. All lines come under any one of the following categories:
- Visible
- Not Visible
- Clipping Case
1. Visible: If a line lies within the window, i.e., both endpoints of the line lies within the window. A line is visible and will be displayed as it is.
2. Not Visible: If a line lies outside the window it will be invisible and rejected. Such lines will not display. If any one of the following inequalities is satisfied, then the line is considered invisible. Let A (x1,y2) and B (x2,y2) are endpoints of line.
3. Clipping Case: If the line is neither visible case nor invisible case. It is considered to be clipped case. First of all, the category of a line is found based on nine regions given below. All nine regions are assigned codes. Each code is of 4 bits. If both endpoints of the line have end bits zero, then the line is considered to be visible.
The center area is having the code, 0000, i.e., region 5 is considered a rectangle window.
Following figure show lines of various types
Line AB is the visible case
Line OP is an invisible case
Line PQ is an invisible line
Line IJ are clipping candidates
Line MN are clipping candidate
Line CD are clipping candidate
Advantage of Cohen Sutherland Line Clipping:
- It calculates end-points very quickly and rejects and accepts lines quickly.
- It can clip pictures much large than screen size.
Algorithm of Cohen Sutherland Line Clipping:
Step1:Calculate positions of both endpoints of the line
Step2:Perform OR operation on both of these end-points
Step3:If the OR operation gives 0000
Then
line is considered to be visible
else
Perform AND operation on both endpoints
If And ≠ 0000
then the line is invisible
else
And=0000
Line is considered the clipped case.
Step4:If a line is clipped case, find an intersection with boundaries of the window
m=(y2-y1 )(x2-x1)
(a) If bit 1 is “1” line intersects with left boundary of rectangle window
y3=y1+m(x-X1)
where X = Xwmin
where Xwminis the minimum value of X co-ordinate of window
(b) If bit 2 is “1” line intersect with right boundary
y3=y1+m(X-X1)
where X = Xwmax
where X more is maximum value of X co-ordinate of the window
(c) If bit 3 is “1” line intersects with bottom boundary
X3=X1+(y-y1)/m
where y = ywmin
ywmin is the minimum value of Y co-ordinate of the window
(d) If bit 4 is “1” line intersects with the top boundary
X3=X1+(y-y1)/m
where y = ywmax
ywmax is the maximum value of Y co-ordinate of the window
Example of Cohen-Sutherland Line Clipping Algorithm:
Let R be the rectangular window whose lower left-hand corner is at L (-3, 1) and upper right-hand corner is at R (2, 6). Find the region codes for the endpoints in fig:
The region code for point (x, y) is set according to the scheme
Bit 1 = sign (y-ymax)=sign (y-6) Bit 3 = sign (x-xmax)= sign (x-2)
Bit 2 = sign (ymin-y)=sign(1-y) Bit 4 = sign (xmin-x)=sign(-3-x)
Here
So
A (-4, 2)→ 0001 F (1, 2)→ 0000
B (-1, 7) → 1000 G (1, -2) →0100
C (-1, 5)→ 0000 H (3, 3) → 0100
D (3, 8) → 1010 I (-4, 7) → 1001
E (-2, 3) → 0000 J (-2, 10) → 1000
We place the line segments in their appropriate categories by testing the region codes found in the problem.
Category1 (visible): EF since the region code for both endpoints is 0000.
Category2 (not visible): IJ since (1001) AND (1000) =1000 (which is not 0000).
Category 3 (candidate for clipping): AB since (0001) AND (1000) = 0000, CD since (0000) AND (1010) =0000, and GH. since (0100) AND (0010) =0000.
The candidates for clipping are AB, CD, and GH.
In clipping AB, the code for A is 0001. To push the 1 to 0, we clip against the boundary line xmin=-3. The resulting
intersection point is I1 (-3,3
). We clip (do not display) AI1 and I1 B. The code for I1is 1001. The clipping category for I1 B is 3 since (0000) AND (1000) is (0000). Now B is outside the window (i.e., its code is 1000), so we push the 1
to a 0 by clipping against the line ymax=6. The resulting intersection is l2 (-1
,6). Thus I2 B is clipped. The code for I2 is 0000. The remaining segment I1 I2 is displayed since both endpoints lie in the window (i.e., their codes are 0000).
For clipping CD, we start with D since it is outside the window. Its code is 1010. We push the first 1 to a 0 by clipping against the line ymax=6. The resulting intersection I3 is (,6),and its code is 0000. Thus I3 D is clipped and the remaining segment CI3 has both endpoints coded 0000 and so it is displayed.
For clipping GH, we can start with either G or H since both are outside the window. The code for G is 0100, and we push the 1 to a 0 by clipping against the line ymin=1.The resulting intersection point is I4 (2
,1) and its code is 0010. We clip GI4 and work on I4 H. Segment I4 H is not displaying since (0010) AND (0010) =0010.
Program to perform Line Clipping using Cohen Sutherland Algorithm:
-
#include <iostream.h> #include <conio.h> #include <graphics.h> #include <dos.h> class data { int gd, gmode, x, y, xmin,ymin,ymax,xmax; int a1,a2; float x1, y1,x2,y2,x3,y3; int xs, ys, xe, ye; float maxx,maxy; public: void getdata (); void find (); void clip (); void display (float, float,float,float); void checkonof (int); void showbit (int); }; void data :: getdata () { cout<<"Enter the minimum and maximum coordinate of window (x, y) "; cin >>xmin>>ymin>>xmax>>ymax; cout<<"Enter the end points of the line to be clipped"; cin >>xs>>ys>>xe>>ye; display (xs, ys, xe,ye); } void data :: display (float, xs, float, ys,float xe, float ye) { int gd=DETECT; initgraph (&gd,&gmode, ""); maxx=getmaxx(); maxy=getmaxy(); line (maxx/2,0,maxx/2,maxy); line (0, maxy/2,maxx,maxy/2); rectangle (maxx/2+xmin,maxy/2-ymax,maxx/2+xmax,maxy/2-ymin); line (maxx/2+xs,maxy/2-ys,maxx/2+xe,maxy/2-ye); getch(); } void data :: find () { a1=0; a2=0; if ((ys-ymax)>0) a1+=8; if ((ymin-ys)>0) a1+=4; if ((xs-xmax)>0) a1+=2; if ((xmin-xs)>0) a1+=1; if ((ye-ymax)>0) a2+=8; if ((ymin-ye)>0) a2+=4; if ((xe-xmax)>0) a2+=2; if ((xmin-xe)>0) a2+=1; cout<<"\nThe area code of Ist point is "; showbit (a1); getch (); cout <<"\nThe area code of 2nd point is "; showbit (a2); getch (); } void data :: showbit (int n) { int i,k, and; for (i=3;i>=0;i--) { and =1<<i; k = n? k ==0?cout<<"0": cout<<"1\""; } } void data ::clip() { int j=a1&a2; if (j==0) { cout<<"\nLine is perfect candidate for clipping"; if (a1==0) { else { checkonof(a1); x2=x1;y2=y1; } if (a2=0) { x3=xe; y3=ye; } else { checkonof (a2); x3=x1; y3=y1; } xs=x2; ys=y2;xe=x3;ye=y3; cout << endl; display (xs,ys,xe,ye); cout<<"Line after clipping"; getch () } else if ((a1==0) && (a2=0)) { cout <<"\n Line is in the visible region"; getch (); } } void data :: checkonof (int i) { int j, k,l,m; 1=i&1; x1=0;y1=0; if (1==1) { x1=xmin; y1=ys+ ((x1-xs)/ (xe-xs))*(ye-ys); } j=i&8; if (j>0) { y1=ymax; x1=xs+(y1-ys)/(ye-ys))*(xe-xs); } k=i & 4; if (k==1) { y1=ymin; x1=xs+((y1-ys)/(ye-ys))*(xe-xs); } m= i&2; if (m==1) { x1=xmax; y1=ys+ ((x1-xs)/ (xe-xs))*(ye-ys); } main () { data s; clrscr(); s.getdata(); s.find(); getch(); closegraph (); return (); }
Output:
Mid Point Subdivision Line Clipping Algorithm:
It is used for clipping line. The line is divided in two parts. Mid points of line is obtained by dividing it in two short segments. Again division is done, by finding midpoint. This process is continued until line of visible and invisible category is obtained. Let (xi,yi) are midpoint
x5lie on point of intersection of boundary of window.
Advantage of midpoint subdivision Line Clipping:
It is suitable for machines in which multiplication and division operation is not possible. Because it can be performed by introducing clipping divides in hardware.
Algorithm of midpoint subdivision Line Clipping:
Step1: Calculate the position of both endpoints of the line
Step2: Perform OR operation on both of these endpoints
Step3: If the OR operation gives 0000
then
Line is guaranteed to be visible
else
Perform AND operation on both endpoints.
If AND ≠ 0000
then the line is invisible
else
AND=6000
then the line is clipped case.
Step4: For the line to be clipped. Find midpoint
Xm=(x1+x2)/2
Ym=(y1+y2)/2
Xmis midpoint of X coordinate.
Ymis midpoint of Y coordinate.
Step5: Check each midpoint, whether it nearest to the boundary of a window or not.
Step6: If the line is totally visible or totally rejected not found then repeat step 1 to 5.
Step7: Stop algorithm.
Example: Window size is (-3, 1) to (2, 6). A line AB is given having co-ordinates of A (-4, 2) and B (-1, 7). Does this line visible. Find the visible portion of the line using midpoint subdivision?
Solution:
Step1: Fix point A (-4, 2)
Step2: Find b”=mid of b’and b
So (-1, 5) is better than (2, 4)
Find b”&bb”(-1, 5) b (-1, 7)
So B””to B length of line will be clipped from upper side
Now considered left-hand side portion.
A and B””are now endpoints
Find mid of A and B””
A (-4, 2) B “”(-1, 6)
Liang-Barsky Line Clipping Algorithm:
Liang and Barsky have established an algorithm that uses floating-point arithmetic but finds the appropriate endpoints with at most four computations. This algorithm uses the parametric equations for a line and solves four inequalities to find the range of the parameter for which the line is in the viewport.
Let P(x1, y1), Q(x2, y2) is the line which we want to study. The parametric equation of the line segment from gives x-values and y-values for every point in terms of a parameter that ranges from 0 to 1. The equations are
x=x1+(x2-x1 )*t=x1+dx*t and y=y1+(y2-y1 )*t=y1+dy*t
We can see that when t = 0, the point computed is P(x1, y1); and when t = 1, the point computed is Q(x2, y2).
Algorithm of Liang-Barsky Line Clipping:
1. Set tmin=0 and tmax=1
2. Calculate the values tL,tR,tT and tB(tvalues).
If t<tmin or t<tmax? ignore it and go to the next edge
Otherwise classify the tvalue as entering or exiting value (using inner product to classify)
If t is entering value set tmin=t if t is exiting value set tmax=t.</t</t
3. If tmin< tmax? then draw a line from (x1 + dx*tmin, y1 + dy*tmin) to (x1 + dx*tmax?, y1 + dy*tmax? )
4. If the line crosses over the window, you will see (x1 + dx*tmin, y1 + dy*tmin) and (x1 + dx*tmax? , y1 + dy*tmax?) are intersection between line and edge.
Text Clipping:
Several methods are available for clipping of text. Clipping method is dependent on the method of generation used for characters. A simple method is completely considered, or nothing considers method. This method is also called as all or none. If all characters of the string are inside window, then we will keep the string, if a string character is outside then whole string will be discarded in fig (a). Another method is discarded those characters not completely inside the window. If a character overlap boundary of window. Those will be discarded in fig (b).In fig (c) individual character is treated. Character lies on boundary is discarded as which it is outside the window.
Curve Clipping:
Curve Clipping involves complex procedures as compared to line clipping. Curve clipping requires more processing than for object with linear boundaries. Consider window which is rectangular in shape. The circle is to consider against rectangle window. If circle is completely inside boundary of the window, it is considered visible. So save the circle. If a circle is in outside window, discard it. If circle cut the boundary then consider it to be clipping case.
Exterior Clipping:
It is opposite to previous clipping. Here picture which is outside the window is considered. The picture inside the rectangle window is discarded. So part of the picture outside the window is saved.
Uses of Exterior Clipping:
- It is used for displaying properly the pictures which overlap each other.
- It is used in the concept of overlapping windows.
- It is used for designing various patterns of pictures.
- It is used for advertising purposes.
- It is suitable for publishing.
- For designing and displaying of the number of maps and charts, it is also used.
Polygon Clipping:
Polygon clipping is applied to the polygons. The term polygon is used to define objects having outline of solid. These objects should maintain property and shape of polygon after clipping.
Polygon:
Polygon is a representation of the surface. It is primitive which is closed in nature. It is formed using a collection of lines. It is also called as many-sided figure. The lines combined to form polygon are called sides or edges. The lines are obtained by combining two vertices.
Example of Polygon:
- Triangle
- Rectangle
- Hexagon
- Pentagon
Following figures shows some polygons.
Types of Polygons
- Concave
- Convex
A polygon is called convex of line joining any two interior points of the polygon lies inside the polygon. A non-convex polygon is said to be concave. A concave polygon has one interior angle greater than 180°. So that it can be clipped into similar polygons.
A polygon can be positive or negative oriented. If we visit vertices and vertices visit produces counterclockwise circuit, then orientation is said to be positive.
Sutherland-Hodgeman Polygon Clipping:
It is performed by processing the boundary of polygon against each window corner or edge. First of all entire polygon is clipped against one edge, then resulting polygon is considered, then the polygon is considered against the second edge, so on for all four edges.
Four possible situations while processing
- If the first vertex is an outside the window, the second vertex is inside the window. Then second vertex is added to the output list. The point of intersection of window boundary and polygon side (edge) is also added to the output line.
- If both vertexes are inside window boundary. Then only second vertex is added to the output list.
- If the first vertex is inside the window and second is an outside window. The edge which intersects with window is added to output list.
- If both vertices are the outside window, then nothing is added to output list.
Following figures shows original polygon and clipping of polygon against four windows.
Disadvantage of Cohen Hodgmen Algorithm:
This method requires a considerable amount of memory. The first of all polygons are stored in original form. Then clipping against left edge done and output is stored. Then clipping against right edge done, then top edge. Finally, the bottom edge is clipped. Results of all these operations are stored in memory. So wastage of memory for storing intermediate polygons.
Weiler-Atherton Polygon Clipping:
Let the clipping window be initially called clip polygon and the polygon to be clipped the subject polygon. We start with an arbitrary vertex of the subject polygon and trace around its border in the clockwise direction until an intersection with the clip polygon is encountered:
1. If the edge enters the clip polygon, record the intersection point and continue to trace the subject polygon.
2. If the edge leaves the clip polygon, record the intersection point and make a right turn to follow the clip polygon in the same manner (i.e., treat the clip polygon as subject polygon and the subject polygon as clip polygon and proceed as before).
Whenever our path of traversal forms a sub-polygon we output the sub-polygon as part of the overall result. We then continue to trace the rest of the original subject polygon from a recorded intersection point that marks the beginning of a not-yet traced edge or portion of an edge. The algorithm terminates when the entire border of the original subject polygon has been traced exactly once.
For example, the number in fig (a) indicates the order in which the edges and portion of edges are traced. We begin at the starting vertex and continue along the same edge (from 1 to 2) of the subject polygon as it enters the clip polygon. As we move along the edge that is leaving the clip polygon, we make a right turn (from 4 to 5) onto the clip polygon, which is now considered the subject polygon. Following the same logic leads to the next right turn (from 5 to 6) onto the current clip polygon, this is the original subject polygon. With the next step done (from 7 to 8) in the same way, we have a sub-polygon for output in fig (b). We then resume our traversal of the original subject polygon from the recorded intersection point where we first changed our course. Going from 9 to 10 to 11 produces no output. After skipping the already traversed 6 and 7, we continue with 12 and 13 and come to an end. The fig (b) is the final result.