Clipping: Line

Cohen Sutherland's Line Clipping Algorithm

The Cohen–Sutherland algorithm is a line clipping algorithm used in computer graphics. After dividing a 2D space into 9 regions, the algorithm effectively identifies the lines and line segments that are visible in the viewport, which is the center region of interest.
The division of regions is based on a window defined by its maximum (x_max, y_max) and minimum (x_min, y_min) coordinates. One region represents the window itself, while the other 8 regions surround it, identified using a 4-digit binary code.

Each endpoint of a line segment is assigned a 4-bit binary region code based on its position relative to the clipping window:
- Bit-1 (Top): 1 if y > y_max , 0 otherwise.
- Bit-2 (Bottom): 1 if y < y_min , 0 otherwise.
- Bit-3 (Right): 1 if x > x_max , 0 otherwise.
- Bit-4 (Left): 1 if x < x_min , 0 otherwise.

For example:

If a point (x, y) lies in top-right of the clipping window, its region code will be 1010.

Trivial Acceptance and Rejection:

Trivial Acceptance: When both endpoints have a region code of 0000, it means both points are inside the clipping window. This is because:
- Bit-1 (Top) = 0: Both points are below or at y_max
- Bit-2 (Bottom) = 0: Both points are above or at y_min
- Bit-3 (Right) = 0: Both points are to the left or at x_max
- Bit-4 (Left) = 0: Both points are to the right or at x_min Therefore, the entire line segment must lie within the window.
Trivial Rejection: When the bitwise AND of both endpoint codes is not 0000, it means both points lie in regions that are completely outside the window. This is because:
- If any bit position has 1 in both codes, both points are on the same side of the window (both above, both below, both left, or both right)
- For example, if both points have bit-1 = 1, they are both above the window
- Therefore, the line segment cannot intersect the window and can be rejected

When a line segment needs to be clipped, we need to find its intersection points with the window boundaries. Let's derive these equations:

Line Equation: For a line segment from (x₁, y₁) to (x₂, y₂):
- Slope m = (y₂ - y₁) / (x₂ - x₁)
- Point-slope form: y - y₁ = m(x - x₁)
Intersection with Horizontal Boundaries:
- For y = y_max:
  - Substitute y = y_max in point-slope form
  - y_max - y₁ = m(x - x₁)
  - x = x₁ + (1/m)(y_max - y₁)
- For y = y_min:
  - Substitute y = y_min in point-slope form
  - y_min - y₁ = m(x - x₁)
  - x = x₁ + (1/m)(y_min - y₁)
Intersection with Vertical Boundaries:
- For x = x_max:
  - Substitute x = x_max in point-slope form
  - y - y₁ = m(x_max - x₁)
  - y = y₁ + m(x_max - x₁)
- For x = x_min:
  - Substitute x = x_min in point-slope form
  - y - y₁ = m(x_min - x₁)
  - y = y₁ + m(x_min - x₁)

Assign region codes to both endpoints points (A(x1, y1) and B(x2, y2)) of the line segment.
Perform a bitwise OR operation on both endpoints:
- If OR == 0000,
  - The line is completely inside the window (Trivially accepted).
- Else,
  - Perform a bitwise AND operation on both endpoints:
    - If AND != 0000,
      - The line is not inside the window, it cannot be clipped (Trivially rejected).
    - Else,
      - The line is partially inside the window and can be considered for clipping.
After confirming the line is partially inside the window:
- Find the intersection with the boundary of the window:
  - Calculate the slope of the line: m = (y2 - y1) / (x2 - x1).
  - Determine the intersection point based on the region code:
    - If the line intersects with the top boundary:
      - x = x1 + (1 / m) * (y_max - y1)
      - Update the intersection point (x, y_max)
    - If the line intersects with the bottom boundary:
      - x = x1 + (1 / m) * (y_min - y1)
      - Update the intersection point (x, y_min)
    - If the line intersects with the left boundary:
      - y = y1 + m * (x_min - x1)
      - Update the intersection point (x_min, y)
    - If the line intersects with the right boundary:
      - y = y1 + m * (x_max - x1)
      - Update the intersection point (x_max, y)
Overwrite the endpoint with the new intersection point and update its region code.
Repeat step 2-4 until a trivial accept or reject occurs.
Repeat the entire process for other lines as needed.

This pseudo code outlines the steps of the Cohen–Sutherland line clipping algorithm, detailing how line segments are processed and clipped against a defined clipping window in 2D space.