왜 화면 밖의 도형까지 계산하면 안 되는가

그래픽스 응용 프로그램은 보통 실제 세계 좌표(예: 지도 데이터, 3D 장면)로 도형을 정의한 뒤, 화면의 일부 사각형 영역에만 그 일부를 보여줍니다. 이때 두 가지 사각형을 구분해야 합니다. 윈도우(window)는 사용자가 보고 싶은 세계 좌표 안의 관심 영역이고, 뷰포트(viewport)는 그 내용을 실제로 표시할 화면(또는 화면 안의 한 영역) 좌표입니다. 예를 들어 지도 프로그램에서 위도·경도로 정의된 특정 구역(윈도우)을 골라, 그 구역을 1920×1080 픽셀 창(뷰포트)에 맞춰 그리는 것과 같습니다.

또한 윈도우 경계를 완전히 벗어난 도형까지 좌표 변환하고 픽셀을 계산하는 것은 낭비입니다. 화면에 보이지도 않을 도형을 끝까지 계산하면 성능이 크게 떨어지므로, 윈도우 경계를 기준으로 도형을 미리 잘라내는 절차가 필요합니다. 이것이 이번 편의 두 번째 주제인 클리핑(Clipping, 잘라내기)입니다.

쉽게 말하면: 윈도우-뷰포트 변환은 “보고 싶은 영역을 화면 크기에 맞게 늘이거나 줄이는 것”이고, 클리핑은 “그 영역 밖으로 나간 부분을 미리 잘라내는 것”입니다.

1. 윈도우-뷰포트 변환

세계 좌표계의 윈도우 범위를 $x_{w,\min}, x_{w,\max}, y_{w,\min}, y_{w,\max}$라 하고, 화면(또는 화면 안 특정 영역)의 뷰포트 범위를 $x_{v,\min}, x_{v,\max}, y_{v,\min}, y_{v,\max}$라고 하면, 윈도우 안의 점 $(x_w, y_w)$를 뷰포트 좌표 $(x_v, y_v)$로 옮기는 식은 다음과 같습니다.

• $x_w - x_{w,\min}$: 윈도우의 왼쪽 경계로부터 점이 얼마나 떨어져 있는지(윈도우 안에서의 상대 위치)
• $\dfrac{x_{v,\max} - x_{v,\min}}{x_{w,\max} - x_{w,\min}}$: 윈도우 너비와 뷰포트 너비의 비율(배율). 이 비율을 상대 위치에 곱하면 뷰포트 안에서의 상대 위치가 된다.
• $x_{v,\min}$: 뷰포트의 왼쪽 경계 좌표를 더해 절대 좌표로 바꾼다.

$y$좌표도 같은 구조로 계산합니다.

세계 좌표 윈도우가 $x_{w,\min}=0, x_{w,\max}=100, y_{w,\min}=0, y_{w,\max}=100$이고, 이것을 $640 \times 480$ 화면 전체(뷰포트 $x_{v,\min}=0, x_{v,\max}=640, y_{v,\min}=0, y_{v,\max}=480$)에 매핑한다고 하겠습니다. 윈도우 안의 점 $(25, 50)$이 뷰포트의 어느 좌표로 매핑되는지 계산해 보겠습니다.

• 윈도우 너비 $100$이 뷰포트 너비 $640$으로 매핑되므로 배율은 $6.4$이고, 윈도우 높이 $100$이 뷰포트 높이 $480$으로 매핑되므로 배율은 $4.8$이다.
• 결과: 윈도우 좌표 $(25, 50)$은 뷰포트 좌표 $(160, 240)$에 그려진다.

자주 틀리는 점: 윈도우와 뷰포트의 가로세로 배율이 다르면($x$ 배율 $6.4$, $y$ 배율 $4.8$처럼) 도형이 원래 비율과 다르게 찌그러져 보입니다. 원래 형태를 유지하려면 두 배율을 같게 만들거나(가로세로 비율, 종횡비를 유지), 종횡비를 맞추기 위해 여백을 두는 처리가 추가로 필요합니다.

2. Cohen-Sutherland 알고리즘 — 리전 코드로 빠르게 걸러내기

쉽게 말하면: Cohen-Sutherland는 각 점이 클리핑 윈도우의 위·아래·왼쪽·오른쪽 중 어느 쪽 바깥에 있는지를 4비트 코드로 표시해, 계산 없이 바로 판정할 수 있는 경우를 먼저 걸러내는 방법입니다.

클리핑 윈도우를 $x_{\min}, x_{\max}, y_{\min}, y_{\max}$라고 할 때, 평면 전체를 이 윈도우를 기준으로 9개의 영역(윈도우 내부 1개 + 주변 8개)으로 나눕니다. 각 영역에 4비트 리전 코드(region code)를 부여하는데, 각 비트는 다음을 의미합니다(왼쪽부터 위·아래·오른쪽·왼쪽 순서).

예를 들어 윈도우보다 왼쪽에 있으면서 위쪽에도 있는 점은 1001(위=1, 아래=0, 오른쪽=0, 왼쪽=1)이 되고, 윈도우 내부에 있는 점은 네 조건이 모두 거짓이므로 0000이 됩니다.

두 점의 리전 코드를 구했으면 다음 두 가지 빠른 판정을 먼저 시도합니다.

• 완전히 안쪽(trivial accept): 두 코드를 OR(비트별 논리합) 했을 때 0000이 나오면, 두 점 모두 내부에 있다는 뜻이므로 선분 전체가 보이는 상태다. 클리핑 계산 없이 그대로 그린다.
• 완전히 바깥쪽(trivial reject): 두 코드를 AND(비트별 논리곱) 했을 때 0000이 아니면, 두 점이 같은 쪽 바깥에 함께 있다는 뜻이므로 선분 전체가 보이지 않는다. 계산 없이 버린다.

두 판정 모두 해당하지 않으면(OR가 0000이 아니고 AND도 0000인 경우), 선분이 윈도우 경계와 실제로 교차할 가능성이 있으므로 교차점을 계산해 선분을 잘라내야 합니다.

클리핑 윈도우를 $x_{\min}=10, x_{\max}=50, y_{\min}=10, y_{\max}=40$이라 하고, 선분의 두 끝점을 $P_1 = (5, 20)$, $P_2 = (30, 60)$이라고 하겠습니다.

리전 코드 계산. $P_1=(5,20)$: $x=5 < x_{\min}=10$이므로 왼쪽 비트만 1, 나머지는 0 → 코드 0001. $P_2=(30,60)$: $y=60 > y_{\max}=40$이므로 위쪽 비트만 1, 나머지는 0 → 코드 1000.

• OR가 0000이 아니므로 완전히 안쪽은 아니다.
• AND가 0000이므로 완전히 바깥쪽도 아니다.
• 따라서 실제 교차점을 계산해야 한다.

교차점 계산. 코드가 0000이 아닌 점부터 처리합니다. 먼저 $P_1$의 왼쪽 비트가 켜져 있으므로 왼쪽 경계 $x = x_{\min} = 10$과의 교차점을 구합니다. 직선의 기울기는 다음과 같습니다.

• $x=10$일 때 $y=28$이므로 새 점 $P_1' = (10, 28)$을 얻는다. $P_1'$의 리전 코드를 다시 계산하면 $x=10$은 $x_{\min}$과 같아 왼쪽 조건을 만족하지 않고(x < xmin 조건이므로 등호는 포함되지 않음), $y=28$도 윈도우 안에 있으므로 코드는 0000이 되어 내부로 판정된다.

이제 $P_2 = (30, 60)$의 위쪽 비트가 켜져 있으므로 위쪽 경계 $y = y_{\max} = 40$과의 교차점을 구합니다. 이번에는 갱신된 점 $P_1' = (10, 28)$과 $P_2 = (30, 60)$을 잇는 선분을 기준으로 계산합니다.

• 새 점 $P_2' = (17.5, 40)$을 얻는다. 리전 코드를 다시 계산하면 $y=40$은 $y_{\max}$와 같아 위쪽 조건(등호 제외)을 만족하지 않고 $x=17.5$도 윈도우 안에 있으므로 코드는 0000이 되어 내부로 판정된다.

두 점 모두 0000이 되었으므로(OR = 0000), 클리핑이 끝났습니다. 최종적으로 화면에 그려지는 선분은 원래의 $(5,20)$–$(30,60)$이 아니라, 잘려진 $(10, 28)$–$(17.5, 40)$입니다.

자주 틀리는 점: 교차점을 계산한 뒤 리전 코드를 다시 계산하지 않고 바로 다음 경계로 넘어가는 실수가 흔합니다. 한 번 잘라낸 뒤에는 반드시 새 점의 리전 코드를 다시 구해, 아직 밖에 있는지 이제 안에 들어왔는지 확인한 다음 절차를 반복해야 합니다.

3. Liang-Barsky 알고리즘 — 매개변수 방정식으로 한 번에 계산

쉽게 말하면: Liang-Barsky는 선분을 매개변수 $t$로 표현한 뒤, 네 변과 만나는 $t$ 값의 범위를 구해 교집합만 남기는 방법입니다.

선분 위의 점을 매개변수 $t$($0 \le t \le 1$)로 표현하면 다음과 같습니다.

• $dx = x_2 - x_1$, $dy = y_2 - y_1$
• $t=0$이면 시작점 $P_1$, $t=1$이면 끝점 $P_2$를 가리킨다.

이 선분이 윈도우의 네 변(왼쪽·오른쪽·아래쪽·위쪽)과 어디서 만나는지를 각각 $t$ 값으로 구하고, 그 중 “선분이 윈도우 안으로 들어가는 지점들” 중 가장 늦게 들어가는 $t$를 $t_{\min}$, “윈도우 밖으로 나가는 지점들” 중 가장 먼저 나가는 $t$를 $t_{\max}$로 잡습니다. 네 변에 대해 다음 값을 계산합니다.

• $p_i < 0$인 항목은 “선분이 윈도우 안으로 들어가는 방향”이므로 $t=q_i/p_i$가 $t_{\min}$ 후보가 된다.
• $p_i > 0$인 항목은 “선분이 윈도우 밖으로 나가는 방향”이므로 $t=q_i/p_i$가 $t_{\max}$ 후보가 된다.

앞서 Cohen-Sutherland에서 사용한 같은 값(윈도우 $x_{\min}=10, x_{\max}=50, y_{\min}=10, y_{\max}=40$, 선분 $P_1=(5,20)$–$P_2=(30,60)$, $dx=25, dy=40$)으로 계산해 보겠습니다.

• $t_{\min}=0.2 \le t_{\max}=0.5$이므로 선분의 $t \in [0.2, 0.5]$ 구간이 윈도우 안에 보인다. 만약 $t_{\min} > t_{\max}$였다면 선분 전체가 윈도우 밖에 있다는 뜻이므로 버린다.

이제 $t=0.2$와 $t=0.5$를 원래 매개변수 방정식에 대입해 실제 좌표를 구합니다.

• 결과: 클리핑된 선분은 $(10, 28)$에서 $(17.5, 40)$까지다. 이는 앞서 Cohen-Sutherland 알고리즘으로 구한 결과와 정확히 일치한다. 두 알고리즘 모두 같은 기하학적 문제를 풀기 때문에 계산 과정은 다르지만 최종 결과는 같아야 하며, 서로 다른 방법으로 검산하는 습관은 실전 계산 문제에서 실수를 줄여준다.

자주 틀리는 점: $p_i = 0$인 경우(선분이 해당 변과 평행한 경우)를 빠뜨리는 실수가 있습니다. $p_i=0$이면서 $q_i < 0$이면 선분이 그 변의 바깥쪽과 평행하다는 뜻이므로 선분 전체를 버려야 하고, $q_i \ge 0$이면 그 변에 대한 제약이 없다는 뜻이므로 해당 항목은 $t$ 범위 계산에서 제외합니다.

4. Cohen-Sutherland와 Liang-Barsky 비교

두 알고리즘 모두 “완전 내부”, “완전 외부”, “부분적으로 겹침”이라는 세 가지 상황을 구분해서 처리한다는 공통점이 있습니다. 실전에서는 리전 코드 방식이 이해하기 쉬워 먼저 배우고, 매개변수 방식은 사각형 클리핑 외에 다른 볼록 다각형 클리핑으로 확장할 때 더 유리한 구조를 가집니다.

핵심 정리

• 윈도우-뷰포트 변환은 세계 좌표의 윈도우 범위를 화면의 뷰포트 범위로 비율에 맞춰 매핑하며, 가로세로 배율이 다르면 도형이 찌그러진다.
• Cohen-Sutherland는 위·아래·오른쪽·왼쪽 4비트 리전 코드를 이용해 완전 내부(OR=0000)와 완전 외부(AND≠0000)를 빠르게 판정하고, 나머지는 경계와의 교차점을 반복 계산한다.
• Liang-Barsky는 선분을 매개변수 $t$로 표현하고, 네 변에 대한 $t_{\min}, t_{\max}$를 구해 교집합 구간만 남긴다.
• 같은 선분에 두 알고리즘을 적용하면 결과가 일치해야 하며, 이는 계산을 검산하는 좋은 방법이다.

마무리 복습

참고 자료

• MDN - CanvasRenderingContext2D: clip() method 
• MIT OCW - Graphics Pipeline and Rasterization 
• KAIST Rendering Book