Visibility problem

canvas에 물체를 그릴 때 어떤 부분은 보이게 하고 어떤 부분은 감춰야 하는지 결정하는 방법을 알아보자.

다음의 두 가지 방법이 있다.

  - ray tracing

  - rasterization

 

raterization은 ray tracing보다 빠르지만 실제 이미지처럼 render하는 더 쉬운 방법은 ray tracing이다.

 

rasterization 방법에 대해 알아보자.

실제 물체 점을 canvas에 projection 한 점의 원래 좌표체계를 screen space라고 한다. canvas 중앙에 원점이 위치한다. 모든 좌표축의 길이는 unit length 인 1이다. 점이 y축 왼쪽에 있거나 x축 아래에 있으면 음의 값을 갖는다.

그리드 형태의 좌표로 원점이 왼쪽 위에 위치한 좌표체계를 raster space라고 한다. 해당 좌표축 역시 unit length를 가지며 크기는 실제 canvas의 width, height pixel로 표현한다.

 

screen space에서 raster space로 변환하는 방법을 알아보자.

rasterspace 값은 모두 양수이다. 따라서 먼저, screen space 점을 normalize한다. normalize한 좌표가 속한 좌표 시스템을 NDC라고 한다. NDC에서 raster space로 변환한다. NDC 좌표에 raster space width, height를 곱하고 정수가 되도록 반올림 한다.

screen space 좌표가 [-1, 1]이라고 가정하고 screen space 한 점을 raster space로 변환하는 pseudo code는 아래와 같다.

int width = 64, height = 64; // dimension of the image in pixels 
Vec3f P = Vec3f(-1, 2, 10); 
Vec2f P_proj; 
P_proj.x = P.x / P.z; // -0.1 
P_proj.y = P.y / P.z; // 0.2 
// convert from screen space coordinates to normalized coordinates
Vec2f P_proj_nor; 
P_proj_nor.x = (P_proj.x + 1) / 2; // (-0.1 + 1) / 2 = 0.45 
P_proj_nor.y = (1 - P_proj.y ) / 2; // (1 - 0.2) / 2 = 0.4 
// finally, convert to raster space
Vec2i P_proj_raster; 
P_proj_raster.x = (int)(P_proj_nor.x * width); 
P_proj_raster.y = (int)(P_proj_nor.y * height); 
if (P_proj_raster.x == width) P_proj_raster.x = width - 1; 
if (P_proj_raster.y == height) P_proj_raster.y = height - 1;

위 코드에서 눈여겨 봐야할 사항 몇 가지가 있다.

첫째는 space, ndc space 좌표가 각 Vec2f로 표현한 반면 raster space 좌표는 vec2i인 정수로 표현했다.

둘째, raster space 좌표는 0부터 시작하고 width, height보다 1작은 크기가 최대이다. 이를 확인하고 clamp하는 코드가 있다.

셋째, raster space y축은 screen space y축과 반대방향이다. 따라서,  ndc y 점 구할 때, x 점 구할 때와 다르게 구한다.

 

이렇게 모든 점을 raster space로 변환하고 각 점의 depth를 저장한 list를 만든다. 이 list를 오름차순으로 정렬한다. 정렬한 list를 이용하여 visiblity problem을 해결한다.

 

이번엔, ray tracing 방법을 알아보자.

눈에서 부터 시작하여 canvas 위 점을 지나 선을 연장하여 따라 갔을 때, 선이 물체와 만나면 render하는 방법이다.

ray와 물체가 만나는지 test 하는 것을 ray test라고 한다. 물체 모양 타입별로 ray test하는 것이 아닌 모든 물체를 triangle로 바꾸고 triangle만 ray test하는 방법을 많이 사용한다. 훨씬 간단하기 때문이다.

 

컴퓨터 성능이 발전하고 ray tracing으로 reflection과 같은 것을 표현하기 훨씬 쉽기 때문에 오늘날 visibility problem을 해결하기 위해, rasterization보다 ray tracing 방법을 더 많이 사용한다.

 

참조 : Rendering an Image of a 3D Scene: an Overview (The Visibility Problem) (scratchapixel.com)