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

### 클리핑 알고리즘

**클리핑**은 그래픽스 시스템에서 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차원 변환(번역, 스케일링, 회전)을 행렬 곱셈으로 통합하여 처리할 수 있다.

**변환 행렬**

1. **번역(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}
$$

2. **스케일링(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}
$$

3. **회전(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차원 공간에서 정의되며, 클리핑은 이 뷰 볼륨 내에 객체를 포함시키기 위해 수행된다.

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

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

***

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

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