Subject : COMPUTER GRAPHICS
Class Notes
MODULE 4 : Viewing and Clipping
● Viewing transformation
● Window to Viewport coordinate transformation,
● Line Clipping Algorithms:
○ Cohen Sutherland,
○ Liang Barsky,
● Polygon Clipping Algorithms:
○ Sutherland Hodgeman,
○ Weiler Atherton
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
● Viewing transformation
● Window to Viewport coordinate transformation (matrix)
Viewing Transformation is the mapping of coordinates of points and lines that form the picture
into appropriate coordinates on the display device.
World coordinate system (WCS) is the right handed cartesian coordinate system where we
define the picture to be displayed. A finite region in the WCS is called the Window. The
corresponding coordinate system on the display device where the image of the picture is
displayed is called the physical coordinate system. Mapping the window onto a subregion of the
display device called the viewport is called the Viewing Transformation. Normalized device
coordinate (NDC) is the display area of the virtual display device corresponding to a unit square.
The lower left handed corner is the origin of the coordinate system. Mapping the window in the
world coordinate space to the viewport in NDC space is called the Normalization Transformation,
N.
● Class Whiteboarding :
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Row Major
Column Major
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Numericals:
Refer Numericals_Window&[Link]
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
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. The clipping point of
intersection of a line with the window is determined.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
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
Applications of clipping:
● It will extract the 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 coordinates. The contents inside the window will be mapped to
device coordinates. Another alternative is a complete world coordinates picture is assigned to device
coordinates, and then clipping of viewport boundaries is done.
Types of Clipping:
● Point Clipping
● Line Clipping
● Area Clipping (Polygon)
● Curve Clipping
● Text Clipping
● Exterior Clipping
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Point Clipping:
Point Clipping is used to determine whether the point is inside the window or not. For this the
following conditions are checked.
1. x ≤ xmax
2. x ≥ xmin
3. y ≤ ymax
4. y ≥ ymin
The (x, y) is the 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.
Class Whiteboarding:
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
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
The Cohen-Sutherland line clipping algorithm is a computer graphics algorithm used to clip lines
to a rectangular window. The window represents the visible area, and the algorithm determines
which parts of a line segment lie inside the window and should be displayed.
In the algorithm, first of all, it is detected whether the 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.
xmin,xmax are coordinates of the window.
ymin,ymax are also coordinates of the window.
x1>xmax
x2>xmax
y1>ymax
y2>ymax
x1<xmin
x2<xmin
y1<ymin
y2<ymin
3. Clipping Case: If the line is neither visible case nor invisible case. It is considered to be a clipped
case. First of all, the category of a line is found based on the nine regions given below. All nine
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
regions are assigned codes. Each code is 4 bits. If both endpoints of the line have end bits zero, then
the line is considered to be visible.
Steps in the Cohen-Sutherland Algorithm:
1. Define the Window and Boundaries: The window is defined by its four boundaries:
left, right, top, and bottom. For example, let's say the window boundaries are:
○ Left = x_min
○ Right = x_max
○ Bottom = y_min
○ Top = y_max
2. Assign Region Codes (Outcodes): Every endpoint of a line segment is assigned a 4-bit
code, known as a region code or outcode. Each bit of the code represents whether the
point lies outside the window in a particular direction:
○ Bit 1: Above the top boundary.
○ Bit 2: Below the bottom boundary.
○ Bit 3: Right of the right boundary.
○ Bit 4: Left of the left boundary.
3. If the point is inside the window, all bits are 0. Each bit corresponds to whether the point
lies outside the window along the four boundaries.
For example:
○ If the point is to the left of the window, its code would be 1000.
○ If the point is below the window, its code would be 0100, and so on.
4. Clipping Decisions:
○ Case 1: Both endpoints have a region code of 0000: This means the line is
completely inside the window, and it is trivially accepted without further checks.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
○ Case 2: Logical AND of the region codes of both endpoints is not 0000: This
means the line is completely outside the window and can be rejected because it
lies entirely outside the clipping area.
○ Case 3: One endpoint is inside the window, and the other is outside: In this
case, the line must be clipped. To do this, the intersection of the line with the
window boundary is calculated, and the outside endpoint is replaced with the
intersection point. The new clipped line is then processed again until it is either
accepted or rejected.
5. Intersection Calculation: When a line needs to be clipped, the intersection point
between the line and the window boundary is calculated using the parametric equation of
a line. The intersection points can be calculated as:
For a vertical boundary (left or right):
Left:
Right:
For a horizontal boundary (top or bottom):
Top:
Bottom:
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
5. Repeat: The process is repeated after clipping, either accepting or rejecting the line
until it fits within the clipping window.
Advantages:
● Simple and efficient for rectangular clipping windows.
● Best Suitable for the lines fully inside or outside.
● It can quickly reject or accept lines using region codes without calculating intersections
for every line.
Limitations:
● Works only for rectangular windows.
● May not be as efficient for more complex clipping regions like polygons or curves.
Class Notes:
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
All Equations:
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Liang-Barsky Line Clipping Algorithm
BACKGROUND WORK:
=====================================================================
NOTE: YOU can use parameter (variable) as t or u
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
The Liang-Barsky algorithm is a line clipping algorithm. This algorithm is more efficient than
Cohen–Sutherland line clipping algorithm and can be extended to 3-Dimensional clipping. This
algorithm is considered to be the faster parametric line-clipping algorithm. The following
concepts are used in this clipping:
● The parametric equation of the line.
● The inequalities describing the range of the clipping window which is used to determine
the intersections between the line and the clip window.
The parametric equation of a line can be given by,
X = x1 + t(x2-x1)
Y = y1 + t(y2-y1)
Where, t is between 0 and 1. Then, writing the point-clipping conditions in the parametric form:
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
NUMERICAL:
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Polygon CLIPPING
- Requires more attention
- Output of Line Clipping - Point or Line
- Output of Polygon Clipping - Point, Line or Polygon
ISSUES:
● Open Polygon
● Each edge needs to be tested against each edge of the clipping region.
This process may add new edges, may delete existing edges, may
retain or divide the edges.
● Clipping of convex polygon yields at most one polygon
● Clipping of concave polygon yields at multiple polygon
● For the same polygon, the different number of edges may be
generated depending on its orientation and location.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
● May add new edges.
● Edges may be discarded or divided.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Sutherland Hodgeman Polygon Clipping
Algorithm
It is performed by processing the boundary of a polygon against each window corner or edge. First of all,
the entire polygon is clipped against one edge, then the 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 outside the window, the second vertex is inside the window. Then a second vertex is
added to the output list. The point of intersection of the window boundary and polygon side (edge) is also
added to the output line.
If both vertices are inside the window boundary. Then only the 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
the window is added to the output list.
If both vertices are the outside window, then nothing is added to the output list.
Following figure shows the original polygon and the clipping of the 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 their
original form. Then clipping against the left edge is done and output is stored. Then clipping against the
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
right edge is done, then the 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.
Sutherland-Hodgeman Polygon Clipping Algorithm:-
1. Read coordinates of all vertices of the Polygon.
2. Read coordinates of the clipping window
3. Consider the left edge of the window
4. Compare the vertices of each edge of the polygon, individually with the clipping
plane.
5. Save the resulting intersections and vertices in the new list of vertices according
to four possible relationships between the edge and the clipping boundary.
6. Repeat the steps 4 and 5 for remaining edges or the clipping window. Each time
the resultant list of vertices is successively passed to process the next edge of
the clipping window.
7. Stop.
Class Whiteboarding:
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
EXAMPLE 1
Given Polygon:
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Left Boundary Clipping
Output of Left Boundary Clipping
Right Boundary Clipping
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Output of Right Boundary Clipping
Bottom Boundary Clipping
Output of Bottom Boundary
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Top Boundary Clipping
Output of Top Boundary
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
FINAL OUTPUT
EXAMPLE 2
Disadvantages:
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Weiler Atherton Polygon Clipping Algorithm
When the clipped polygons have two or more separate sections, then it is the concave polygon
handled by this algorithm. The vertex-processing procedures for window boundaries are
modified so that concave polygon is displayed.
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
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
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.
Class Whiteboarding:
● Capable of clipping concave polygon with interior holes to the boundaries of another
concave polygon
● Polygon to be clipped - SUBJECT Polygon (SP)
● Clipping Region - CLIPPED Polygon(CP)
● SP and CP are defined by a circular list of vertices.
● Exterior boundaries are described in clockwise and interior boundaries in anticlockwise.
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
OUTPUT :
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.
Weiler Atherton – Polygon Clipping Algorithm:
[Link]
Compiled by : Ms. Chandana K., Assistant Professor, TCET.
This document is only meant for Academic Purpose and Internal Circulation only.