Experts

Experts

Pricing

Pricing

Papers

Papers

Blogs

Blogs

Cohen Sutherland Algorithm in Computer Graphics

Cohen Sutherland Algorithm in Computer Graphics

The Cohen-Sutherland algorithm is a method used in computer graphics for line-clipping.
It helps determine which parts of a line segment should be visible or invisible in a given window or viewport.

What is Line Clipping?

  • Imagine you have a picture, and you want to show only a specific part of it within a frame on your computer screen.
  • In the context of lines, you might have a line that goes beyond the boundaries of your screen, and you need to decide which portion of that line should be displayed.

Window and Regions

  • In the Cohen-Sutherland algorithm, the screen is divided into several regions. These regions help quickly identify the position of the line concerning the window.
  • There are three regions above the window, three below, three to the right, and three to the left.

Coding the Regions

  • Each region is assigned a code.
  • For example, if a point is above the window, it gets a code indicating "above."
  • The codes are like a binary language, representing whether a point is above, below, to the left, or to the right of the window.
Example: If a point is both above and to the right of the window, its code might be 1010 in binary, where the first digit represents being above, the second being below, the third is to the left, and the fourth is to the right.

Example of Cohen-Sutherland Algorithm in Action

Imagine you have a computer screen, and you want to draw a line from point A to point B.
The screen has a defined window, and anything outside this window should not be displayed.

Step 1: Assigning Region Codes

Point A: (x = 8, y = 12) Point B: (x = 2, y = 4) Given
  • The idea is to assign a 4-bit binary code to each point based on its position relative to the window.
  • The 4 bits represent whether the point is above, below, to the left, or to the right of the window.
  • The bits are set to 1 if the point is outside that particular boundary and 0 if it's inside.
Let's assume the window is defined by the following boundaries:

• Top Boundary: Y_top=10
• Bottom Boundary: Y_bottom=0
• Left Boundary: X_left = 0
• Right Boundary: X_right= 6

For Point A (8, 12):

  • Above (bit 1): Check if Y > (Y_top).
  • Given Y = 12, and Y_top = 10.
  • Check if 12 > 10.
  • Result: Yes. So, set bit 1 to 1.
  • Below (bit 2): Check if Y < (Y_bottom).
  • Given Y = 12, and Y_bottom = 0.
  • Check if 12 < 0.
  • Result: No. So, set bit 2 to 0.
  • Left (bit 3): Check if X < (X_left).
  • Already given in the Q as X = 8, and X_left = 0 as we assumed above.
  • Check if 8 < 0.
  • Result: No. So, set bit 3 to 0.
  • Right (bit 4): Check if X > (X_right).
  • Given X = 8, and X_right = 6.
  • Check if 8 > 6.
  • Result: Yes. So, set bit 4 to 1.

So, the region code for Point A is 1001.

For Point B (2, 4):

  • Above (bit 1): Check if Y > (Y_top).
  • Given Y = 4, and Y_top = 10.
  • Check if 4 > 10.
  • Result: No. So, set bit 1 to 0.
  • Below (bit 2): Check if Y < (Y_bottom).
  • Given Y = 4, and Y_bottom = 0.
  • Check if 4 < 0.
  • Result: No. So, set bit 2 to 0
  • Left (bit 3): Check if X < (X_left).
  • Given X = 2, and X_left = 0.
  • Check if 2 < 0.
  • Result: No. So, set bit 3 to 0.
  • Right (bit 4): Check if X > (X_right).
  • Given X = 2, and X_right = 6.
  • Check if 2 > 6.
  • Result: No. So, set bit 4 to 0.

So, the region code for Point B is 0000.

  • These region codes help in determining the relative position of each point with respect to the window boundaries.
  • In the subsequent steps of the Cohen-Sutherland Algorithm, these codes are used to decide whether the line segment connecting the two points lies completely inside, outside, or partially inside the window.

Step 2: Checking for Trivial Acceptance or Rejection

  • In this step, we check whether there's a common bit set to 1 in the region codes of both points.
  • If there is no common bit, it means the line segment may intersect the window boundaries.
  • For Point A (Region Code: 1001) and Point B (Region Code: 0000), there is no common bit set to 1, so the line segment may intersect the window boundaries.

Step 3: Clipping Process

This step involves adjusting the line to fit within the window by calculating the intersection points with the window boundaries.

For Point A (8, 12):

Since Point A is above the window's top boundary and to the right of the window's right boundary, we need to adjust it to fit within the window.
formula for intersection with top boundary:
1Y' =   Y  -  (Y - Y_top) *  (X_right - X_left)
2            -------------------------------------
3              (Y_bottom - Y_top)
So for the point A -:
1Y' = 12 - (12-10) X (6-0) / (0-10)
2
312 - 12/-10
4
5Y' = 12 + 1.2 = 13.2

Y adjusted = min (Y ', Y_top)
min (13.2, 10)
so, Y adjusted is 10
the formula for intersection with the right boundary with the solution:
1X' = X + (X - X_right) * (Y_bottom - Y_top) / (X_right - X_left)
2
3
4Given:
5X = 8
6X_right = 6
7X_left = 0
8Y_top = 10
9Y_bottom = 0
10
11X' = 8 + (8 - 6) * (0 - 10) / (6 - 0)
12X' = 8 - 20 / 6
13X' = 8 - 3.33
14X' = 5.33
X adjusted = max (X ', X_left)
max (5.33, 0)
so, X adjusted is 5.33
so the adjusted point is A (5, 10)

Conclusion

  • In summary, the Cohen-Sutherland algorithm is like a digital assistant that quickly decides which parts of a line should be visible on your computer screen.
  • By using region codes and a systematic process, it efficiently determines how to clip or adjust a line so that it fits within a specified window, providing a clear and optimized visual representation.