231114 Hidden Surface Removal

• Line clipping과 유사하다. 안 보이는 애들은 쳐내는 게 목적. 대신 이번엔 region 대신에 각 오브젝트들 간 가려짐을 고려한다.

• 두 가지 관점이 있다.
  1) Object space algorithm: 어느 물체가 더 앞에 있는가? 를 판별
  2) Image space algorithm: 그 픽셀에서는 어느 물체가 보이는가? 를 판별

• Back face culling
  

  일단 내적해서 음수인지 양수인지 판별. 눈을 $z$축 상에 놓으면 $z$ 값에 대해서만 음수/양수를 판별하는 것으로도 충분하다. 단순한 물체는 잘 작동하지만 열린 물체, 펄럭이는 물체, 투명 물체 등과는 궁합이 나쁘다.
  

• Hidden surface removal
  

  그냥 단순 비교해서 하는 것도 좋지만, 물체가 많으면 $O(n^2)$의 시간 복잡도가 요구된다. 그럼 처음부터 물체들의 순서를 '정렬' 해놓고 뒤에서부터 앞으로 렌더링 하도록 하면(Painter's algorithm) 시간 복잡도도 $O(n \log{n})$ 으로 줄어든다. 이 방식을 sort-based algorithm이라 부른다. 합리적인 비용이지만 overlapping 오브젝트에 대해서는 처리가 뛰어나지 못하다.
  

• Depth Sort Algorithm
  Painter's algorithm에서 overlapping 오브젝트에 대한 문제를 개선한 방법. Binary Space Partition(BSP) Tree를 사용한다. 하나의 장면을 오브젝트들의 집합이라고 생각하고, 하나의 기준 평면을 잡아서 화면을 반으로 나눈다. 이 과정을 반복하며 BSP Tree를 초기화 하고 화면에 그릴 떄는 In-order traverse (L C R) 를 해서 화면에 그려질 순서를 결정 짓는다.
  

1) 먼저 눈이 어디에 있는지 판단해서 child node로 넣는다.
2) root부터 시작해서 (안보이는 면) -> (루트) -> (보이는 면)을 재귀적으로 수행한다.
3) 2)에서 수행한 traverse 순서를 그대로 기록해서 렌더링 순서로 활용한다.

• Split 하는 것이 좀 까다롭게 보일 수도 있다.
  

  

  실제로도 번거롭고 귀찮다. 1) 선과 면의 접점을 계산하고 2) 알파벳 오더링 순서(시계 방향, 반시계 방향)도 맞춰서 새롭게 삼각형을 정의해야 한다. 그리고 항상 $c$가 분리되는 꼭지점이라 가정하고 알고리즘이 전개되기 때문에, $c$가 분리되는 점이 아니면 별도로 돌리는 pre-processing을 거쳐야 한다.
  

• BSP tree는 만드는데 시간도 안들고 트리 탐색하는데도 $O(N)$밖에 안걸리며, 눈을 어디에 둬도 바로 적용이 가능한 좋은 방법론이다. 대신 실시간으로 오브젝트가 수정되면 알고리즘은 매우 비효율적으로 변한다.

• Image space approach
  지금까지는 object space approach였다면, 이제는 픽셀 단위로 살펴보는 image space approach를 볼 것이다.

• Z-buffering
  

  같은 크기의 두 개 버퍼 Frame buffer와 Z-buffer를 지속적으로 관리하는 것으로 구현. 만약 이전 프레임의 Z-buffer의 값에 저장된보다 현재 프레임의 Z값이 더 가깝다면 그 색깔로 교체.

  

  여기서 z-value는 색상을 의미하며, 색은 이전에 배운 것처럼 interpolate 된 것으로 사용한다. interpolate 과정에서 스캔라인을 사용해서(한줄씩 한줄씩 검사) $z$값을 본다면, 이 $z$ 값의 변화는 다항식으로 표현이 가능하다.

  $a \Delta x + b \Delta y + c \Delta z = 0$

  

• Z-buffering은 쉽고 빠른 방식으로 동적으로 변화하는 환경을 표현할 때 좋지만, 추가 메모리를 필요로 하고 앨리어싱이 발생할 수 있다.