Rasterization: a Practical Implementation Rasterization Algorithm Overview

Rasterization은 두 개의 step으로 나눌 수 있다.

첫 번째, 3d vertices를 perspective projection을 이용하여 screen에 project한다.

두 번째, image의 모든 픽셀을 순회하면서 픽셀이 project된 도형에 속해있는지 확인한다.

 

rasterizaion 알고리즘은 object centric이다. scene에서 시작하기 때문이다.

pseudo code로 간단히 구현해보자.

// rasterization algorithm
for (each triangle in scene) { 
    // STEP 1: project vertices of the triangle using perspective projection
    Vec2f v0 = perspectiveProject(triangle[i].v0); 
    Vec2f v1 = perspectiveProject(triangle[i].v1); 
    Vec2f v2 = perspectiveProject(triangle[i].v2); 
    for (each pixel in image) { 
        // STEP 2: is this pixel contained in the projected image of the triangle?
        if (pixelContainedIn2DTriangle(v0, v1, v2, x, y)) { 
            image(x,y) = triangle[i].color; 
        } 
    } 
}

 

project 도형의 bounding box 만 순회하여 위 방법을 조금 더 optimize할 수 있다.

// convert the vertices of the current triangle to raster space
Vec2f bbmin = INFINITY, bbmax = -INFINITY; 
Vec2f vproj[3]; 
for (int i = 0; i < 3; ++i) { 
    vproj[i] = projectAndConvertToNDC(triangle[i].v[i]); 
    // coordinates are in raster space but still floats not integers
    vproj[i].x *= imageWidth; 
    vproj[i].y *= imageHeight; 
    if (vproj[i].x < bbmin.x) bbmin.x = vproj[i].x); 
    if (vproj[i].y < bbmin.y) bbmin.y = vproj[i].y); 
    if (vproj[i].x > bbmax.x) bbmax.x = vproj[i].x); 
    if (vproj[i].y > bbmax.y) bbmax.y = vproj[i].y); 
}

box의 minimum 좌표와 maximum좌표를 구한다.

bounding box를 구하고 순회하기 전 주의할 점이 있다. bounding box는 float형이다. 우리 canvas의 좌표를 벗어날 수 있다. 벗어나지 않도록 clamping 한다.

... 
uint xmin = std::max(0, std:min(imageWidth - 1, std::floor(min.x))); 
uint ymin = std::max(0, std:min(imageHeight - 1, std::floor(min.y))); 
uint xmax = std::max(0, std:min(imageWidth - 1, std::floor(max.x))); 
uint ymax = std::max(0, std:min(imageHeight - 1, std::floor(max.y))); 
for (y = ymin; y <= ymin; ++y) { 
    for (x = xmin; x <= xmax; ++x) { 
        // check of if current pixel lies in triangle
        if (pixelContainedIn2DTriangle(v0, v1, v2, x, y)) { 
            image(x,y) = triangle[i].color; 
        } 
    } 
}

같은 픽셀에 그리려는 도형이 겹쳐 어떤 도형을 보여줘야 하는지 결정해야 하는 문제를 visibility problem이라고 한다.

이를 해결하기 위해 z-buffer를 사용한다.

z-buffer는 canvas에서 가장 가까운 도형의 depth를 저장한 canvas와 같은 2D array이다.

// A z-buffer is just an 2D array of floats
float buffer = new float [imageWidth * imageHeight]; 
// initialize the distance for each pixel to a very large number
for (uint32_t i = 0; i < imageWidth * imageHeight; ++i) 
    buffer[i] = INFINITY; 
 
for (each triangle in scene) { 
    // project vertices
    ... 
    // compute bbox of the projected triangle
    ... 
    for (y = ymin; y <= ymin; ++y) { 
        for (x = xmin; x <= xmax; ++x) { 
            // check of if current pixel lies in triangle
            float z; // distance from the camera to the triangle 
            if (pixelContainedIn2DTriangle(v0, v1, v2, x, y, z)) { 
                // If the distance to that triangle is lower than the distance stored in the
                // z-buffer, update the z-buffer and update the image at pixel location (x,y)
                // with the color of that triangle
                if (z < zbuffer(x,y)) { 
                    zbuffer(x,y) = z; 
                    image(x,y) = triangle[i].color; 
                } 
            } 
        } 
    } 
}

위 코드에서, zbuffer에 저장된 depth보다 현재 픽셀의 depth가 더 작으면 작은 값을 저장하고 image에 현재 픽셀의 color를 저장한다.

 

참조 : Rasterization: a Practical Implementation (An Overview of the Rasterization Algorithm) (scratchapixel.com)