Computer graphics �subject code(22318)

BY A.I.MUSHRIF

Syllabus

Weightage of marks

Chapter 4�Windowing and Clipping

Contents

• Windowing and clipping concepts: window to viewport transformations
• Line clipping algorithms: Cohen Sutherland algorithm,mid-point algorithm
• Polygon clipping:Sutherland-hodgeman
• Text clipping

Clipping Concept

• Any procedure that eliminates those portion of a picture that are either inside or outside a specified region is referred to as a clipping algorithm

World Coordinates

Clipping Concept

• When we display a scene only those objects within a particular window are displayed

wy_max

wy_min

wx_min

wx_max

Window or Clipping Region

World Coordinates

Clipping Concept

• Because drawing things to a display takes time we clip everything outside the window

wy_max

wy_min

wx_min

wx_max

World Coordinates

Window or Clipping Region

Clipping

• For the image below consider which lines and points should be kept and which ones should be clipped

wy_max

wy_min

wx_min

wx_max

Window

P₁

P₂

P₃

P₆

P₅

P₇

P₁₀

P₉

P₄

P₈

Point Clipping

• wx_min ≤ x ≤ wx_max AND wy_min ≤ y ≤ wy_max

​

wy_max

wy_min

wx_min

wx_max

Window

P₁

P₂

P₅

P₇

P₁₀

P₉

P₄

P₈

Clipped

Points Within the Window are Not Clipped

Clipped

Clipped

Clipped

Easy - a point (x,y) is not clipped if:

Line Clipping

• Harder - examine the end-points of each line to see if they are in the window or not

Cohen-Sutherland Clipping Algorithm

• An efficient line clipping algorithm
• The key advantage of the algorithm is that it vastly reduces the number of line intersections that must be calculated

Dr. Ivan E. Sutherland co-developed the Cohen-Sutherland clipping algorithm. Sutherland is a graphics giant and includes amongst his achievements the invention of the head mounted display.

Cohen is something of a mystery – can anybody find out who he was?

Window to viewport transformation

• Window to Viewport Transformation is the process of transforming a 2D world-coordinate objects to device coordinates. Objects inside the world or clipping window are mapped to the viewport which is the area on the screen where world coordinates are mapped to be displayed.

Window to viewport transformation

• General Terms:
• World coordinate – It is the Cartesian coordinate w.r.t which we define the diagram, like Xwmin, Xwmax, Ywmin, Ywmax
• Device Coordinate –It is the screen coordinate where the objects is to be displayed, like Xvmin, Xvmax, Yvmin, Yvmax
• Window –It is the area on world coordinate selected for display.
• ViewPort –It is the area on device coordinate where graphics is to be displayed.

​

Window to viewport transformation

• Mathematical Calculation of Window to Viewport:
• It may be possible that the size of the Viewport is much smaller or greater than the Window.
• In these cases, we have to increase or decrease the size of the Window according to the Viewport and for this, we need some mathematical calculations.
• (xw, yw): A point on Window
• (xv, yv): Corresponding point on Viewport
• we have to calculate the point (xv, yv)

​

​

Window to viewport transformation

Now the relative position of the object in Window and Viewport are same.

​

For x coordinate,

​

​

For y coordinate,

​

Window to viewport transformation

• So, after calculating for x and y coordinate, we get

​

​

​

​

​

​

• where, sx is scaling factor of x coordinate and sy is scaling factor of y coordinate

Window to viewport transformation

• Example:
• Lets assume,
• for window, Xwmin = 20, Xwmax = 80, Ywmin = 40, Ywmax = 80.
• for viewport, Xvmin = 30, Xvmax = 60, Yvmin = 40, Yvmax = 60.
• Now a point ( Xw, Yw ) be ( 30, 80 ) on the window. We have to calculate that point on viewport
• i.e ( Xv, Yv ).
• First of all, calculate scaling factor of x coordinate Sx and scaling factor of y coordinate Sy using above mentioned formula.
• Sx = ( 60 - 30 ) / ( 80 - 20 ) = 30 / 60
• Sy = ( 60 - 40 ) / ( 80 - 40 ) = 20 / 40
• So, now calculate the point on viewport ( Xv, Yv ).

​

• Xv = 30 + ( 30 - 20 ) * ( 30 / 60 ) = 35
• Yv = 40 + ( 80 - 40 ) * ( 20 / 40 ) = 60

​

• So, the point on window ( Xw, Yw ) = ( 30, 80 ) will be ( Xv, Yv ) = ( 35, 60 ) on viewport.

​

​

Cohen-Sutherland: World Division

• World space is divided into regions based on the window boundaries
• Each region has a unique four bit region code
• Region codes indicate the position of the regions with respect to the window

Cohen-Sutherland: Labelling

• Every end-point is labelled with the appropriate region code

Cohen-Sutherland: Lines In The Window

Lines completely contained within the window boundaries have region code [0000] for both end-points so are not clipped

The OR operation can efficiently check this

Cohen-Sutherland: Lines Outside The Window

Any lines with a common set bit in the region codes of both end-points can be clipped

• The AND operation can efficiently check this

AND operation and OR operation

• Case I: Line P5 and P6
• As the line completely lies inside the window so according to rule we have to perform the OR operation
• Point P5: 0000
• OR (+)
• Point P6: 0000
• Result: 0000
• Case II: Line P9 and P10
• As the line partially inside the window so according to rule we have to perform the AND operation
• Point P9: 0000
• AND(x)
• Point P10: 0100
• Result: 0000

​

Cohen-Sutherland: Other Lines

• Lines that cannot be identified as completely inside or outside the window may or may not cross the window interior
• These lines are processed as follows:
• Compare an end-point outside the window to a boundary (choose any order in which to consider boundaries e.g. left, right, bottom, top) and determine how much can be discarded
• If the remainder of the line is entirely inside or outside the window, retain it or clip it respectively

Cohen-Sutherland: Other Lines (cont…)

• Otherwise, compare the remainder of the line against the other window boundaries
• Continue until the line is either discarded or a segment inside the window is found
• We can use the region codes to determine which window boundaries should be considered for intersection
• To check if a line crosses a particular boundary we compare the appropriate bits in the region codes of its end-points
• If one of these is a 1 and the other is a 0 then the line crosses the boundary

Cohen-Sutherland Examples

• Consider the line P₉ to P₁₀ below
• Start at P₁₀
• From the region codes �of the two end-points we �know the line doesn’t �cross the left or right �boundary
• Calculate the �intersection of the line with the bottom boundary to generate point P₁₀’
• The line P₉ to P₁₀’ is completely inside the window so is retained

Cohen-Sutherland Examples (cont…)

• Consider the line P₇ to P₈ below
• Start at P₇
• From the two region �codes of the two �end-points we know �the line crosses the �left boundary so �calculate the �intersection point to �generate P₇’

Cohen-Sutherland Examples (cont…)

• Consider the line P₇’ to P₈
• Start at P₈
• Calculate the �intersection with the �right boundary to �generate P₈’
• P₇’ to P₈’ is inside �the window so is �retained

Cohen-Sutherland Worked Example

wy_max

wy_min

wx_min

wx_max

Window

Calculating Line Intersections

• Intersection points with the window boundaries are calculated using the line-equation parameters
• Consider a line with the end-points (x₁, y₁) and (x₂, y₂)
• The y-coordinate of an intersection with a vertical window boundary can be calculated using:

y = y₁ + m (x_boundary - x₁)

where x_boundary can be set to either wx_min or wx_max

Calculating Line Intersections (cont…)

• The x-coordinate of an intersection with a horizontal window boundary can be calculated using:

x = x₁ + (y_boundary - y₁) / m

where y_boundary can be set to either wy_min or wy_max

• m is the slope of the line in question and can be calculated as m = (y₂ - y₁) / (x₂ - x₁)

Difference

• The Sutherland algorithm requires the floating point calculation
• i.e. to find the intersection point on window edges
• These calculations can be avoided by using Mid point subdivision Algorithm
• The Mid point Subdivision algorithm repetitively subdivides the line at its mid point.

Midpoint Subdivision Algorithm

• The mid point subdivision algorithm uses same technique as Cohen-Sutherland
• This algorithm is used to compute visible areas of lines that are present in viewport.
• It follows the principle of bisection method and works by bisecting the lines into equal halves
• Similarly like Sutherland It uses the line end-point codes and test the visibility of line.
• If both the end points are codes are 0000 then line is completely visible. Else line is partially visible or invisible.

​

​

Midpoint Subdivision Algorithm

• If the is partially visible then it subdivided into two equal parts
• The visibility test is applied on each half
• The subdivision process is repeated until we get completely visible or invisible process

​

Mid point subdivision

• Condition 1: if both region the endpoints are zero the line is completely.
• Condition 2: if region code for both endpoints are not zero and logical ANDing of them is also Non-zero then the line is invisible so reject it completely.
• Condition 3: if region code do not satisfy above two conditions then line is partially visible

​

Mid point Subdivision Algorithm

Mid point Subdivision Algorithm

Mid point Subdivision Algorithm

Polygon clipping algorithm

• Polygon clipping is a process in which we only consider the part which is inside the view pane or window.
• We will remove or clip the part that is outside the window.
• Sutherland-Hodgeman polygon clipping algorithm is used.

​

Sutherland-Hodgeman polygon clipping algorithm�

Sutherland-Hodgeman polygon clipping algorithm�

• The polygon clipping algorithm deals with four different clipping cases. The output of each case is input for the next case.
• Case1) Left clip: In the left side polygon clipping, we only remove the left part of the polygon, which is outside the window. We only save the portion which is inside the window.

Sutherland-Hodgeman polygon clipping algorithm�

Sutherland-Hodgeman polygon clipping algorithm�

• Case2) Right clip: In the right-side polygon clipping, we only remove the right part of the polygon, which is outside the window. We only save the portion which is inside the window.

Sutherland-Hodgeman polygon clipping algorithm�

• Case3) Top clip: On the top side polygon clipping, we only remove the top part of the polygon, which is outside the window. We only save the portion which is inside the window.

Sutherland-Hodgeman polygon clipping algorithm�

• Case4) Bottom clip: In the bottom side polygon clipping, we only remove the bottom part of the polygon, which is outside the window. We only save the portion which is inside the window.

�Sutherland-Hodgeman polygon clipping algorithm�

• Four Cases of polygon clipping against one Edge:
• The clip boundary determines a visible and invisible region. The edges from vertex can be one of four types:
• Case 1: If the first vertex is outside the window boundary and the second vertex is inside the window, then the intersection point with the boundary edge of window and vertex which is inside the window is stored in a output vertex list.

​

Sutherland-Hodgeman polygon clipping algorithm�

• Case 2: If both, first and second vertexes of a polygon are lying inside the window, and then we have to store the second vertex only in output vertex list.
• Case 3: If the first vertex is inside the window and second vertex is outside the window then we have to store only intersection point of that edge of polygon with window in output vertex list.
• Case 4: If both the vertex first and second vertex of a polygon is lying outside the window then no vertex is stored in output vertex list.

​

Sutherland-Hodgeman polygon clipping algorithm�

Text clipping

• “Text Clipping is a process in which we remove those part (portion) of string that is outside the view pane (window).”
• Various methods and techniques can do the text clipping. These techniques depend on the character generation method.
• It means we can select text clipping techniques according to the text generation technique.

Text clipping

• Method of Text Clipping
• There are three following methods to perform text clipping.
• All or none string clipping
• All or none character clipping
• Text Clipping

​

Text clipping

• All or None String Clipping method –
• In this method, if the whole string is inside the clip window then we consider it. Otherwise, the string is completely removed.
• Text pattern is considered under a bounding rectangle.
• The boundary positions of the rectangle are then compared to the window boundaries.
• String is rejected if there is any overlapping between the string and the window. This method produces the fastest text clipping.

​

​

Text clipping

Text clipping

• All or None Character Clipping method –
• In this method, we keep the characters of the string which lies inside clip window and remove all the characters which lie outside the clip window.
• The boundary limits of individual characters are compared to the window.
• In case of overlapping of character with the clip window, we remove the character.

Text clipping

• Text Clipping method –
• In this method, we keep the characters of the string which lies inside the clip window and remove all the characters which lie outside the clip window.
• If a character overlaps the window boundary then we keep that part of the character which lies inside the window and discard that part which lies outside the clip window.

​

​

​