[CGs] Clipping Lines

💻 What is Clipping ?

✍️ Clipping : Clip window가 제시되었을 때 clip window를 기준으로해서 window의 내부인지 외부인지 판단하여 결과적으로 내부에 속하는 부분만 나타낸 것.

Clipping Endpoint

✍️ clip window가 그림처럼 rectangle일 경우, 4가지 부등식을 만족해야 한다

• $x_{min}$ ≤ $x$ ≤ $x_{max}$

• $y_{min}$ ≤ $y$ ≤ $y_{max}$

ㅁ만약 4가지 부등식을 만족 못한다면, point는 clip rectangle 바깥 쪽이라는 것이다

Clipping Lines - 3 categories

• Trivially accepted : endpoint 두개가 clip rectangle 안에 존재할 때 ex) AB

• Clipped : 한 endpoint가 안에 있고, 다른 endpoint가 바깥에 있을때 혹은 endpoint 두개가 둘다 clip rectangle 바깥에서 존재하면서 clip rectangle에 교차점을 생성할 때 ex) GH

• Trivially rejected : endpoint 두개가 clip rectangle 바깥에 존재하면서 clip rectangle과 교차점을 만들지 않을 때 ex) EF

---

💻 Cohen-Sutherland Algorithm(Line Clipping)

4bit region outcodes

1	2	3	4
top bit	bottom bit	right bit	left bit

• 1st bit : top edge 위쪽 면, 위는 1, 아래는 0으로 설정

• 2nd bit : bottom edge 아래쪽 면, 위는 0, 아래는 1으로 설정

• 3rd bit : right edge 오른쪽 면, 오른쪽은 1, 왼쪽은 0으로 설정

• 4rd bit : left edge 왼쪽 면, 왼쪽은 1, 오른쪽은 0으로 설정

C-S Algorithm

1. 두 끝점의 code가 0000이라면 trivially accepted이므로 표현한다.
   두 끝점이 window 내부에 존재

2. 두 끝점의 code를 logical And했을 때 값이 0이 아니라면 trivially rejected 이므로 버린다
   두 끝점이 window 외부에 존재하면서 clip window와 교차점을 생성하지 않는다

3. 두 끝점의 code를 logical And했을 때 값이 0이라면 Clipped.
   두 끝점이 window 외부에 존재하거나 끝점 한개는 외부, 한개는 내부에 존재하면서 clip window와 교차점을 생성

4. 만약 3의 상황이라면, 선의 방향에 따라 code가 0이 아닌 끝점 한개를 선택한다

   • 만약 끝점의 코드가 둘 다 0이 아니라면 선분의 방향을 보고 첫번째 점을 기준으로 한다

   • 선택 후 code에서 top,bottom,right,left 비트 순서대로 확인해서, 각 비트 중 1이 존재 한다면, 그 비트의 edge와 선분이 만난다는 교차점이 생긴다는 뜻이다

   • 이 교차점을 받아서 기존의 선택한 정점을 이 교차점으로 바꾼다

5. window 내부에 두 점이 존재할때까지 위의 과정을 반복한다

Example

• A[0000] & D[1001] = [0000]이므로 Clipped

• D의 비트 1이 처음 나오는 edge는 top edge이므로 top edge와 선분이 만나는 점을 찾는다

• 만나는 점은 B, 기존 D 정점을 B정점으로 바꾼다. (Window 경계선 상은 내부로 판단)

• 정점 A[0000] B[0000] 은 둘다 0, trivially accepted이므로 표현한다

1. E[0100] & I[1010] = [0000]이므로 Clipped

2. 선분의 방향은 E→I이고 정점 E[0100]가 0이 아니므로 선택한다

• E의 비트 1이 처음 나오는 edge는 bottom edge이므로 bottom edge와 선분이 만나는 점을 찾는다

• 만나는 점을 F라 하면, 기존 E 정점을 F정점으로 바꾼다

3. F[0000] & I[1010] = [0000]이므로 Clipped

4.선분의 순서는 F→I이고, 정점 I[1010]가 0이 아니므로 선택한다

• I의 비트 1이 처음 나오는 edge는 top edge이므로 top edge와 선분이 만나는 점을 찾는다

• 만나는 점을 H라 하면, 기존 I 정점을 H정점으로 바꾼다

5. F[0000] & H[0010] = [0000]이므로 Clipped

6.선분의 순서는 F→H이고, 정점 H[0010]가 0이 아니므로 선택한다

• H의 비트 1이 처음 나오는 edge는 right edge이므로 right edge와 선분이 만나는 점을 찾는다

• 만나는 점을 G라 하면, 기존 H 정점을 G정점으로 바꾼다

7. 정점 F[0000] G[0000] 둘다 0, trivially accepted이므로 표현한다

---

✍️ 만약 AB선분이 Clip window 바깥에 존재한다면?

1. 두 끝점 모두 윈도우 밖에 존재하지만 logical And하면 [0000] 나온다.

2. 선분의 순서는 A→B이므로, 끝점 A[0001]은 비트 1이 처음 나오는 edge가 left edge이므로 left edge와 선분이 만나는 점을 C로 정하고, 기존 B점을 C로 바꾼다.

3. B[0100] & c[0100] = [0100]이므로 Trivially rejected로 버린다.

---

Summary

✍️ C-S Algorithm

• 장점 : 간단하면서도 효율적이다.
• 단점 : 여러 번의 반복실행이 필요하거나 불필요한 실행이 필요할 경우도 있다.