231109 Clipping

화면 밖에 있는 선분과 평면들은 아예 렌더링을 안해도 된다. 어떻게 하면 이걸 계산할 수 있을까?

Line Clipping: Cohen-Sutherland
1) Both endpoints가 ($P_x > x_{min}\quad or\quad P_y > y_{min}$) or ($P_x < x_{max}\quad or\quad P_y < y_{max}$): accept
2) Both endpoints가 ($P_x < x_{min}\quad or\quad P_y < y_{min}$) or ($P_x > x_{max}\quad or\quad P_y > y_{max}$): reject

Bitwise 연산으로 매우 간단하게 요약된다. 첫번째 if는 두 점 다 내부에 있는 경우, 두번째 elif는 두 점 다 외부에 있는 경우, 그 외에 경우는 애매한 경우(한 점만 내부인 경우, 두 점 다 외부인데 내부를 경유하는 경우) 이다. 이 경우에는 Clip and Restart 알고리즘이라는 서브 루틴으로 이동한다.

이 Clip and Restart 알고리즘은 별 거 없고, 먼저 외부 점 하나 잡고 통일된 방식으로(bottom-up, left-right) intersection에 대해서 자른 다음, 그 잘린 절단점을 새로운 endpoint로 삼는 과정을 반복하는 것이다.

6비트 코드로 확장해서 3차원에서도 잘 활용할 수 있다.

Normalized Form (2회독 때 추가 예정)

Polygon Clipping

Line clipping의 연장선 상에 있다. 각 좌표축에 대해서 독립적으로 수행한다.
1) 비어있는 꼭지점 목록을 output으로써 초기화 한다.
2) input으로 꼭지점 목록을 초기화 한다.
3) input 내의 꼭지점을 하나씩 돌면서 output을 초기화 한다.
내부에 있으면 그대로 output에 추가, 교차점이 존재하면 그 교차점을 output에 추가.
두 개를 한번에 검사한다: Region 내부에 있는가? $v_{i+1}$로 연결했을 때 교차점이 있는가?
검사 결과에 따라 $v_i$만 추가할 지, $v_i$와 $p_j$ 두개를 추가할지 결정된다.
4) 이 과정을 $x, y$ 축에 각각 수행하고 적절히 후처리를 한다.

다 좋은데, Concave 한 도형을 자르면 여러 개의 도형이 나올 수도 있다. 이걸 Convex로 바꾼 다음 수행해서 post processing을 아예 안하는 방법이 있는데, 이 과정을 Tessellation이라 한다.

Pipeline Clipping

그냥 Region의 상하좌우 지점에 대해서 일단 독립적으로 검사한 뒤 값을 할당하는 것으로 자르는 것도 가능하다. 병렬 처리를 도입할 경우 매우 유용한 방법

Bounding Boxes: 물체가 매우 복잡할 경우, 이것의 vertex를 일일이 검사하기 보다는 그냥 박스를 먼저 씌워서 reject/accept 여부만 판별하는게 더 낫다.