클리핑 알고리즘과 동차좌표

클리핑 알고리즘

클리핑은 그래픽스 시스템에서 2차원 또는 3차원 객체가 주어진 뷰포트(viewport) 또는 뷰잉 볼륨(viewing volume) 내에 위치하거나, 이를 벗어나는 부분을 잘라내는 과정이다. 대표적인 클리핑 알고리즘은 다음과 같다.

Cohen-Sutherland 알고리즘

Cohen-Sutherland 알고리즘은 간단한 직사각형(viewport) 내부의 클리핑을 처리하기 위해 사용된다. 기본적으로 경계 영역을 기준으로 9개의 영역으로 나누고, 각 점을 이진 코드로 표현하여 클리핑 여부를 결정한다.

Liang-Barsky 알고리즘

Liang-Barsky 알고리즘은 Cohen-Sutherland 알고리즘과 유사하지만, 직선 구간이 직사각형 경계와 교차하는 지점을 찾아 더 효율적으로 클리핑을 수행한다.

Sutherland-Hodgman 알고리즘

이 알고리즘은 다각형의 클리핑을 처리하는 데 사용된다. 다각형의 각 변을 클리핑 영역의 경계와 교차시켜 새로운 다각형을 형성한다.

동차좌표

동차좌표계(homogeneous coordinate system)는 3차원 그래픽스에서 객체의 변환을 보다 쉽게 처리하기 위해 사용하는 좌표계다. 동차좌표는 기존의 3차원 좌표에 하나의 추가 차원을 더한 형태로 표현된다.

$\mathbf{p} = (x, y, z, w)$

여기서 $w$ 는 동차 좌표의 추가 차원이다. 기본 3차원 좌표로 변환하려면 이를 다음과 같이 변환한다:

$(x', y', z') = \left( \frac{x}{w}, \frac{y}{w}, \frac{z}{w} \right)$

동차좌표와 변환

동차좌표계를 사용하면 3차원 변환(번역, 스케일링, 회전)을 행렬 곱셈으로 통합하여 처리할 수 있다.

변환 행렬

번역(Translation):

$\mathbf{T} = \begin{bmatrix} 1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}$

스케일링(Scaling):

$\mathbf{S} = \begin{bmatrix} s_x & 0 & 0 & 0 \\ 0 & s_y & 0 & 0 \\ 0 & 0 & s_z & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}$

회전(Rotation):
X축 회전:

$\mathbf{R_x} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos{\theta} & -\sin{\theta} & 0 \\ 0 & \sin{\theta} & \cos{\theta} & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}$

Y축 회전:

$\mathbf{R_y} = \begin{bmatrix} \cos{\theta} & 0 & \sin{\theta} & 0 \\ 0 & 1 & 0 & 0 \\ -\sin{\theta} & 0 & \cos{\theta} & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}$

Z축 회전:

$\mathbf{R_z} = \begin{bmatrix} \cos{\theta} & -\sin{\theta} & 0 & 0 \\ \sin{\theta} & \cos{\theta} & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}$

동차좌표와 클리핑

동차좌표를 이용해 뷰잉 볼륨을 정의하고 클리핑을 개선할 수 있다. 뷰 볼륨은 동차 좌표로 표기된 4차원 공간에서 정의되며, 클리핑은 이 뷰 볼륨 내에 객체를 포함시키기 위해 수행된다.

동차 좌표계를 이용한 클리핑의 변환 과정

동차 좌표 시스템으로 변환:
객체의 삼각형 또는 폴리곤 정점은 동차 좌표계를 사용하여 표현된다. 모든 변환(예: 뷰 변환, 투영 변환 등)은 동차 좌표계를 통해 처리된다.
뷰 변환(View Transformation):
3D 객체를 관찰자(카메라)의 시점에서 볼 수 있도록 변환한다. 변환 행렬은 시점(view point)에서 보기 편하게 객체를 이동하고 회전시킨다.
투영 변환(Projection Transformation):
3D 공간의 객체를 2D 뷰 포인트로 투영한다. 이 과정에서 바람직한 클리핑 면으로 객체가 변환된다. 일반적으로 원근 투영(perpective projection)과 직교 투영(orthogonal projection)이 있다.
클리핑(Clipping):
클리핑은 클리핑 면의 내외부를 결정하여, 뷰 포인트(viewpoint) 또는 뷰 잉 볼륨(viewing volume) 안에 있는 부분만 남기고, 나머지를 잘라낸다. 이러한 클리핑 을 통해 랜더링 성능을 향상시키고 계산 부하를 줄인다.
Clipping은 주로 프러스텀 클리핑(Frustum Clipping)으로 수행되며 이는 뷰 포인트에서 뻗어나가는 홍합 껍질 형태의 뷰 볼륨을 따른다.
정규화 뷰 좌표계(Normalized Device Coordinates, NDC) 변환:
클리핑 후, 객체들은 NDC로 변환된다. NDC는 -1에서 1 범위를 가지며, 이 범위 내에 있는 모든 객체가 시각화 가능하다.
윈도우 변환(Window Transformation):
NDC 좌표는 디스플레이 장치 상의 실제 픽셀 좌표로 변환되어, 최종적으로 화면에 렌더링 된다. 이는 객체의 정밀한 위치를 결정하는 과정이다.

클리핑 알고리즘:
객체를 지정된 뷰 포인트 또는 뷰잉 볼륨 내에 포함시키기 위해 사용된다.
대표적인 클리핑 알고리즘은 Cohen-Sutherland, Liang-Barsky, Sutherland-Hodgman 등이 있다.
동차 좌표계:
3차원 그래픽스 변환을 쉽게 하기 위해 추가 차원(w)을 포함한 좌표계이다.
변환 행렬을 사용하여 번역, 스케일링, 회전 등의 변환을 통합적으로 처리할 수 있다.
동차 좌표를 이용한 클리핑:
객체를 동차 좌표계로 변환하고 일련의 변환을 통해 클리핑을 수행한다.
프러스텀 클리핑과 NDC 변환 그리고 윈도우 변환을 통해 최종적으로 디스플레이 장치에 렌더링 된다.

이와 같은 프로세스를 통해 그래픽스 시스템은 더 효과적으로 객체를 렌더링하고 처리할 수 있게 된다.