Line Clipping in Computer Graphics
The line clipping is a process in which we can cut the part of the line, which lies outside the view pane. Only those lines are visible, which lie inside the view pane.
The line clipping process is implemented by following line clipping algorithms-
- Cohen Sutherland Line Clipping Algorithm
- Liang-Barsky Line Clipping Algorithm
- Midpoint Subdivision Line Clipping Algorithm
Cohen Sutherland Line Clipping Algorithm
This algorithm was named by “Danny Cohen” and “Ivan Sutherland.”
The algorithm will work in the following steps:
- In this algorithm, we will divide the view pane into nineequal segments (as shown in the below figure) that only serve the viewport.
- Now, we will represent the top, bottom, left, and right corner of the window with 4 bits. This 4bit can be described with the following point that:
- If an object lies within any particular corner position, that corner value will be 1, else it will be 0.
- The allocation of bits depends on “TBRL” (Top, Bottom, Right, Left) rule.
- Suppose, if the point of a line appears in the top-left corner, then according to TBRL, the value is 1001. We will allot the bits as-
- For the top corner, because the object is present at the top corner.
- For the bottom corner, because the object does not lie at the bottom.
- For the right corner, because the object does not lie at the right side.
- For the left corner, because the object lies at the top-left corner.
- In this way, we check TBRL for each segment and allot the bits accordingly.
In Cohen- Sutherland Algorithm we will divide the lines into following Sections-
- Visible Line: When both points (starting and ending) of the line are entirely situated inside the window.
- Invisible Line: When both points (Starting and ending) of the line are completely situated outside the window.
If we have (xmin, xmax) and (ymin, ymax) coordinates of the view pane (window).
Then, it should be described as-
x0, x1 > xmax
y0, y1 > ymax
x0, x1 < xmin
y0, y1 < ymin
- Clipped Line: Everyline has two endpoints. Let (x0, y0) and (x1, y1) are points of the line. If one point of the line situated inside the window and the other one is outside the window, then the line is known as Clipped Line.
Algorithm of Cohen-Sutherland Line Clipping:
Step 1: Assign the bit code for both endpoints of the line.
Step 2: Now,implement OR operation on both endpoints of the line.
Step 3: If the OR = 0000,
Then
{The line is acceptable (Visible)}
Else
{Implement AND operation on endpoints}
Then
If AND ? 0000
Then
{The line is not acceptable (Invisible)}
Else
AND = 0000
{The line needs to be clip}
Step 4: If a line needs to be clipped, first find an intersection point of all boundaries with the following formula-
m = (y1-y0) (x1-x0)
Step 4.1: When the line intersects the left side boundary of the window port.
y0 = y1+ m(x-x1)
Here x = xwmin (Minimum value of x coordinate)
Step 4.2: When the line intersects the right-side boundary of the window port.
y0 = y1+m(x-x1)
Here x = xwmax (Maximum value of x coordinate)
Step 4.3: When the line intersects Top side boundary of the window port.
x0 = x1+(y-y1)/m
Here y = ywmax (Maximum value of y coordinate)
Step 4.4: When the line intersects the bottom side boundary of the window port.
x0 = x1+(y-y1)/m
Here y = ywmin (Minimum value of y coordinate)
Example: In the below-mentioned example, we have different lines. The different category of the line-
Line AB is a clipped case.
The line CD is completely visible.
Line EF is completely invisible.
Line GH is a clipped case.
Line KL is completely invisible.
Line IJ is a clipped case.
The endpoints of lines are lies as follows-
A ? 0000
B ? 1010
C ? 0000
D ? 0000
E ? 0100
F ? 0100
G ? 0001
H ? 0000
I ? 0000
J ? 0010
K ? 1000
L ? 1000
Advantages:
- It is easy to use and implement.
- We can perform clipping and testing in a particular manner.
- It is a fast algorithm.
Disadvantages:
- Sometimes it performs needless clipping.
Liang-Barsky Line Clipping Algorithm:
The algorithm was introduced by “You-Dong Liang” and “Brian A. Barsky.” It is used for line clipping. It is a more powerful algorithm than the Cohen-Sutherland algorithm.
We use the following concepts in this algorithm-
- We can use the parametric equation of line and inequalities.
- These are used to describe the range of windows to find out the intersection points between the line and the clipping window.
- The parametric line is also known as “Cyrus-Beck.”
In this algorithm, we have to find the intersection point based on a time interval.
Time interval (t) can be defined as travelling time between initial position (0) to final position (1). Then we have,
0 < t < 1 (Here, t lies between 0 and 1)
We have the formula to find x and y points of the line-
x= x1 + t. ?x (For point x)
y= y1 + t. ?y (For point y)
To check that the point lies between the window or outside the equation is-
Xwmin <= x1 + t. ?x <= Xwmax
Ywmin <= y1 + t. ?y <= Ywmax
These two conditions can be written as-
x1 + t. ?x >= Xwmin
x1 + t. ?x <= Xwmax
y1 + t. ?y >= Ywmin
y1 + t. ?y <= Ywmax
We can take a common expression for above four conditions. It will be-
t.pk <= qk (Here the value of k is multiple)
t = qk / pk
p1 = -?x q1 = x1 - xwmin (For left boundary)
p2 = ?x q2 = xwmax - x1 (For right boundary)
p3 = -?y q3 = y1 - ywmin (For bottom boundary)
p4 = ?y q4 = ywmax – y1(For top Boundary)
Algorithm of Liang-Barsky Line Clipping:
Step 1: Set the endpoints of the line (x1, y1) and (x2, y2).
Step 2: Calculate the value of p1, p2,p3, p4 and q1, q2, q3,q4.
Step 3: Now we calculate the value of t
t1 = 0 (For initial point)
t2 = 1 (For final point)
Step 4: Now, we have to calculate the value of pk and qk
If
pk = 0
then
{The line is parallel to the window}
If
Qk < 0
then
{The line is completely outside the window}
Step 5: If we have non zero value of pk -
If
pk < 0
then
t1 = max (0, qk / pk)
If
pk > 0
then
t2 = min (1, qk / pk)
Now, if t1 < t2 {If t1 value is changed
Then the first point is outside the window.
If t2 value is changed
Then the second point is outside the window}
else
t1 > t2
then
{Line is completely outside the window}
Step 6: Stop.
Example:
Let a rectangular window size with (5, 9). The points of the line are (4, 12) and (8, 8). Use the Liang- Barsky algorithm to clip the line and find the intersection point.
Solution:
We have,
The initial point of the line (p1) = (4, 12)
The ending point of the line (p2) = (8, 8)
x1 = 4, x2 = 8
y1 = 12, y2 = 8
xwmin = 5, xwmax = 9
ywmin = 5, ywmax = 9
Step 1: We have to calculate the value of ?x and?y-
?x = x2- x1= 8-4 = 4
?y = y2- y1= 8-12 = -4
Step 2: Now, we will calculate-
p1 = -4 q1 = 4-5 = -1
p2 = 4 q2 = 9-4 = 5
p3 = 4 q3 = 12-5 = 7
p4 = -4 q4 = 9-12 = -3
Step 3: Now we will calculate t1 value-
If p1, p4 < 0
Then t1 =max (0, qk /pk)
=max (0, q1 /p1, q4 /p4)
=max (0, 1/4, 3/4)
t1 = 3/4
If p2, p3 > 0
Then t2 = min (1, qk /pk)
= min (1, q2 /p2, q3 /p3)
= min (1, 5/4, 7/4)
t2 = 1
Step 4: Now, we have to calculate the intersection point.
x = x1 + t1. ?x= 4+ 3/4 * 4 = 7
y = y1 + t1. ?y= 12+ 3/4 *(-4) = 9
The coordinates intersection point = (7, 9)
Midpoint Subdivision Line Clipping Algorithm:
The midpoint subdivision algorithm is used to clip the line. The algorithm is based on finding the midpoint of the line. We can divide the line into two equal parts. There should be following categories of the line-
Visible line
Invisible line
Partially visible
We can calculate the midpoint of the line by the following formula-
pm = (p1 + p2)/2
Algorithm Midpoint Subdivision Line Clipping:
Step 1: Assign the bit code for both endpoints of the line.
Step 2: Now,implement OR operation on both endpoints of the line.
Step 3: If the OR = 0000,
Then
{The line is Visible}
Else
{Implement AND operation on endpoints}
Then
If AND ? 0000
Then
{The line is Invisible}
Else
AND = 0000
{The line is the partially visible}
Step 4: For partially visible line, we need to find the midpoint.
Xm = (x1 + x2)/2 (For x coordinate)
Ym = (y1 + y2)/2 (For y coordinate)
Step 5: Weneed to check that the line is near to the boundary of the window or not.
Step 6: If the line is visible or invisible, then repeat steps 1 to 5.
Step 7: Stop.
Example: A window contains the size (0, 50, 0, 50). A line PQ has the coordinates (-10, 40) and (30, -20). Find the visible point of the line using midpoint subdivision.
Solution: We have,
The coordinates for x and y = P (-10, 40)
The coordinates for x and y = Q (30, -20)
Now,
Step 1: We have to compute the midpoint of the line segment PQ.
Q = [(-10 + 30) /2, (40 - 20)/2]
= (10, 10)
Now the new coordinates of Q = (10, 10)
Step 2: Now, we will find
Q’’ = midpoint of the Q’ and Q
Q’’ = [(10 + 30) /2, (10 + (-20))/2]
= (20, -5)
Now the new coordinates of Q’’ = (20, -5)
Here (20, -5) is much better than (10, 10)
Now we have to find Q’’’ then,
Q’’’ = [(20 + 30) /2, (-5 + (-20))/2]
= (25, -12.5)
Now the new coordinates of Q’’’ = (25, -12.5)
We can clip the line from Q’’ to Q from the top side.
Step 3: Now, we will take left hand side part. The endpoints are P and Q’’’
We will find the midpoint of P and Q’’’
P (-10,40) and Q’’’ (25, -12.5)
P’ = [(-10 + 25) /2, (40 + (-12.5))/2]
= (7.5, 27.5)
Now we will find the midpoint of P and P’’
P (-10, 40) and P’ (7.5, 27.5)
P’’ = [(-10 + 7.5) /2, (40 + (27.5))/2]
= (-1.25, 33.75)
Now we will find midpoint of P’’ and P
P’’’ = P (-10, 40) and P’’ (-1.25, 33.75)
= [(-10 + (-1.25)) /2, (40 + 33.75)/2]
= (5.62, 36.87)
Now we will clip the line from P to P’’’
Finally, we have P’’’ = (5.62, 36.87)
Q’’’ = (25, -12.5)
Related Posts:
- Midpoint Circle Drawing Algorithm in Computer Graphics
- Mid-Point Line Drawing Algorithm in Computer Graphics
- Bresenham’s Line Drawing Algorithm in Computer Graphics
- Bresenham’s Circle Drawing Algorithm in Computer Graphics
- Line Drawing Algorithm in Computer Graphics
- DDA line Drawing Algorithm in Computer Graphics
- Line Clipping in Computer Graphics
- Color Models in Computer Graphics
- Image Representation in Computer Graphics
- Projection in Computer Graphics