코딩 어드벤처: 소프트웨어 래스터라이저 (Software Rasterizer)

비디오: 코딩 어드벤처: 소프트웨어 래스터라이저 (Software Rasterizer)
채널: Sebastian Lague
길이: 50분 9초
출처: 자막 (수동, en-GB)

안녕하세요 여러분, Coding Adventures의 새로운 에피소드에 오신 것을 환영합니다. 과거에 우리는 레이트레이싱 (Raytracing)을 조금 다뤄본 적이 있습니다. 최근 점점 더 많은 게임들이 특히 그림자나 반사와 같은 요소들을 위해 레이트레이싱을 사용하기 시작했지만, 3D 그래픽의 대다수는 여전히 래스터라이제이션 (Rasterization)이라고 알려진 다른 방식으로 처리됩니다.

그래서 오늘은 간단한 소프트웨어 래스터라이저 (Software Rasterizer)를 직접 만들어보고자 합니다. 엄청나게 빠르거나 화려한 것은 아니며, 그저 CPU에서 처음부터 렌더링되는 소박한 3D 그래픽일 뿐입니다.

우선 저는 여기에 3개의 부동 소수점 (Floating point) 값을 담고 있는 구조체를 사용하기 시작했습니다. 꽤 창의적으로 float3라고 불리는데, 이는 우리 색상의 빨강(Red), 초록(Green), 파랑(Blue) 채널을 나타낼 것입니다. 참고로 이 값들은 x, y, z 변수에 매핑되어 있어, 위치 등을 나타내는 3D 벡터 (3D vector)로 더 범용적으로 사용할 수 있습니다. 하지만 지금은 우선 이러한 float3들의 그리드 (Grid)를 정의하고, 그 그리드의 모든 셀, 즉 픽셀 (Pixel)을 루프 (Loop) 돌며 색상을 할당함으로써 이미지를 만들어 보겠습니다.

예를 들어, 여기서는 이미지의 각 축을 따라 우리가 얼마나 진행했는지를 0과 1 사이의 값으로 계산한 다음, 이를 빨강과 초록의 강도 (Intensities)로 사용했습니다. 만약 우리가 이것을 볼 수만 있다면, 아마 벌써 매우 멋져 보일 것입니다.

이제 우리의 작업물을 이미지 파일로 써보겠습니다. 이를 위해 저는 비트맵 (Bitmap) 형식을 살펴보고 있었는데, 적어도 Windows에서는 별도의 특수 소프트웨어 없이도 열 수 있는 가장 단순한 형식입니다.

기본적으로 우리는 예를 들어 너비(width)와 높이(height)를 지정하고, 오늘은 압축(compression)은 신경 쓰지 않겠다는 내용을 담은 작은 헤더(header)를 작성하기만 하면 됩니다. 그 모든 과정이 끝나면, 이미지를 루프(loop) 돌면서 각 색상 채널(colour channel)을 단일 바이트(single byte)로 파일에 기록합니다.

좋아요 — 한번 시도해 봅시다... 그리고 여기 우리 파일이 방금 생성되었습니다. 자, 파일을 열어보죠. 확실히 아름다운 바이트(bytes) 덩어리처럼 보이긴 하네요 — 물론 우리는 이것이 텍스트로 해석되는 것을 원하는 게 아니라... bmp로 해석되기를 원합니다.

매우 유망해 보이네요! 하지만... 제가 예상했던 것보다 빨간색이 좀 적네요. 잠깐만요, 제가 따라 하던 예제를 자세히 살펴볼게요. 어... 빨간색 픽셀(pixel)이 0, 0, 255... 그리고 여기 파란색 픽셀은 255, 0, 0이네요 — 그러니까 그냥 반대로 되어 있는 겁니다.

좋습니다 — 빠르게 그것을 바꿔주고, 이제.... 우리의 멋진 이미지가 있습니다. 이제 남은 것은 그 위에 3D 그래픽을 그리는 것뿐입니다.

이를 위해서 삼각형(triangles)이 필요할 것입니다. 그래서 여기 이미지의 너비와 높이 사이 어딘가에 2차원(2-dimensional) 점 3개를 정의했고, 현재 픽셀이 삼각형 내부에 있다면 파란색으로 칠하도록 설정했습니다.

그런데 이 삼각형 내부 판정 함수(point in triangle function)가 불길할 정도로 빨간색으로 표시되네요 — 이는 잠시 수학적인 접근이 필요하다는 뜻입니다.

여기 우리가 고민해 볼 3개의 점이 있습니다. 점들 사이에 작은 화살표를 그려서 a에서 b로, c로, 그리고 다시 a로 향하는 선분(segments)의 방향을 표시할 수 있습니다. 이 각각의 선분이 왼쪽(left side)과 오른쪽(right side)을 가지고 있다고 생각하면 도움이 되겠지만, 저는 쉽게 헷갈리곤 하니, 머리를 약간 기울여서 여기 있는 선분이 똑바로 위를 향하게 만든 다음, 작은 화살표로 왼쪽과 오른쪽을 표시해 봅시다.

그다음, 다음 선분이 똑바로 서 있도록 머리를 조금 더 기울여서, 다시 한번 왼쪽과 오른쪽을 표시할 수 있습니다.
좋습니다, 마지막으로 한 번 더 비틀어 보죠 — 이쪽은 왼쪽이고, 이쪽은 오른쪽입니다. 이렇게 머리를 한 바퀴 뱅글 돌리고 나면, 우리는 다시 시작했던 곳으로 돌아오게 됩니다.
이제 우리는 어떤 점이 이 삼각형 내부에 있는지 알고 싶습니다. 그러니 여기에 점 P를 도입해 봅시다. 현재 이 점은 두 개의 선분에 대해서는 오른쪽에 있고, 나머지 하나의 선분에 대해서는 왼쪽에 있다는 것을 알 수 있습니다. 그리고 이 점이 외곽을 따라 조금씩 움직이는 것을 관찰해 보면, 점이 항상 선분 중 하나에 대해 서로 다른 쪽에 위치한다는 것을 볼 수 있습니다.
물론 점 P가 마침내 용기를 내어 안으로 돌진할 때에만, 선분들이 점을 완전히 둘러싸게 됩니다. 즉, 점이 모든 선분에 대해 동일한 쪽에 있게 된다는 뜻입니다.
따라서 이것이 우리가 테스트하고자 하는 조건입니다. 우리는 단지 '점이 실제로 선분의 어느 쪽에 있는가'라는 하위 문제 (sub problem)를 해결하기만 하면 됩니다.
그럼 점 A에서 우리의 점 P로 향하는 화살표를 상상해 봅시다. 그리고 언제나 유용한 내적 (dot product)을 사용하여, 이 두 화살표가 같은 방향을 더 많이 향하고 있는지 — 내적이 양수(+)인 경우 — 또는 반대 방향을 더 많이 향하고 있는지 — 내적이 음수(-)인 경우 —를 계산할 수 있습니다.
결과적으로 우리는 공간을 '위'와 '아래'로 나누게 되었는데, 이는 우리가 원했던 것과는 다소 반대되는 결과입니다. 하지만 걱정할 필요 없습니다. 이제 벡터 중 하나를 90도 회전시키기만 하면, '위'와 '아래'를 우리가 찾던 '왼쪽'과 '오른쪽'으로 변환할 수 있습니다.
자, 그럼 이러한 개념들을 빠르게 코드로 옮겨보겠습니다. 여기 두 벡터의 내적 (dot product)을 구하는 함수가 있습니다. 이 함수는 두 벡터의 길이와 그 사이각의 코사인 (cosine) 값을 곱합니다.

비록 수학적으로는 단순히 각 x축 값들의 곱과 y축 값들의 곱을 더하는 것으로 아주 멋지게 단순화되지만 말입니다. 그런 다음 2D 벡터를 90도 회전시키는 것은 아주 쉽고 간단합니다. x와 y를 서로 바꾸고, 시계 방향(clockwise) 또는 반시계 방향(counterclockwise)을 위해 둘 중 하나를 음수로 만들기만 하면 됩니다. 이 두 가지를 바탕으로, 우리는 PointOnRightSideOfLine 함수를 갖게 됩니다. 이 함수는 방금 전 살펴보았던 두 벡터를 계산합니다. 즉, 그중 하나를 90도 회전시킨 다음, 그 내적 (dot product)이 양수인지 테스트하는 것입니다. 그것이 마침내 우리의 PointInTriangle 테스트로 이어지는데, 이 테스트는 점이 세 개의 모서리 각각에 대해 어느 쪽에 위치하는지 확인하고, 그 결과가 모두 동일한지 확인합니다. 이제 코드를 실행하여 우리가 만든 삼각형을 감상해 봅시다.

어... 수학 계산을 틀린 것 같습니다.

아, 사실은 코드가 문제였네요. 프로그래밍이 어떻게 작동하는지 잠시 잊었습니다. 세 가지가 같은지 테스트하는 방법은 그런 식이 아니거든요. 좋습니다, 다시 되돌려서 실행해 보죠. 이번에는... 완벽합니다! 적어도 이 특정한 하나의 케이스에 대해서는 말이죠. 더 다양한 경우를 테스트하기 위해, 무작위로 초기화된 수많은 삼각형을 빠르게 설정했습니다. 이 삼각형들은 또한 무작위 속도와 색상을 가지고 있으며, 재미를 위해 화면 안에서 그냥 이리저리 튕겨 다니도록 설정했습니다. 그런 다음 이미지 루프 (image loop)에서, 각 세 개의 점 집합에 대해 루프를 돌며 — 해당 점들에 대해 삼각형 테스트를 실행하고 — 당연히 테스트를 통과하면 픽셀에 색을 채웁니다. 이제 이것이 렌더링 (render)될 때까지 기다리기만 하면 됩니다...

드디어, 완료되었습니다! 하지만 매 프레임마다 배경을 검은색으로 지우는 것을 잊은 것 같아서 조금 엉망이 되었네요. 뭐, 그럼 다시 렌더링해야겠군요.

좋습니다 — 이 프레임들을 살펴보면, 이미지에 이를 제대로 해상(resolve)할 만큼의 픽셀이 충분하지 않아 발생하는 이 아주 얇은 삼각형 파편(triangle slivers)과 같은 몇 가지 아티팩트(artifacts)를 발견할 수 있는데, 이는 예상 가능한 범위라고 생각합니다. 더 걱정스러운 점은 — 조금 뒤로 넘어가 보자면 — 배경이 갑자기 색칠되어 버린다는 것입니다.

좋아요, 약간의 디버깅(debugging) 끝에 삼각형 중 하나가 어떤 이유에서인지 하나의 점으로 붕괴되었음을 발견했습니다. 이로 인해 우리의 테스트가 오작동하여 모든 곳이 해당 삼각형 내부에 있다고 말하게 된 것입니다.

이를 해결하는 방법은 여러 가지가 있겠지만, 모든 삼각형에 대해 수행하던 루프를 렌더링 코드의 상단으로 옮기는 간단한 방법을 시도해 보기로 했습니다. 핵심은 현재 삼각형의 경계 상자(bounding box)를 먼저 계산하고, 렌더링 범위를 그 안에 있는 픽셀로만 제한하는 것입니다.

이는 최적화(optimization)이기도 하여 — 이제 프레임이 빠르게 지나가는 것을 볼 수 있습니다 — 동시에 우리의 문제를 해결해 줍니다. 만약 삼각형이 하나의 점으로 붕괴된다면 1x1 픽셀의 경계 상자를 갖게 될 것이고, 이는 단일 픽셀로 그려지게 된다는 의미인데, 이 정도면 합리적이라고 생각합니다.

어쨌든, 이제 상태가 좋아 보이는군요. 그러니 — 2차원에서 꾸물거리는 것은 이쯤 하고 — 많은 이들이 앞서 걸어갔던 곳으로 대담하게 나아가 큐브(cube)를 그려봅시다.

하지만 그 전에, 이 3D 오브젝트 파일의 데이터를 파싱(parse)해야 합니다. 다행히 이 파일은 꽤 자명합니다 — 'v'로 표시된 정점 위치(vertex positions)가 있고, 그다음 정점 법선(vertex normals)과 텍스처 좌표(texture coordinates)가 있는데, 이는 나중에 고민해도 됩니다. 그 뒤에는 아직 그 중요성을 파악하지 못한 신비로운 's'가 나오고, 마지막으로 면 인덱스(face indices)가 나옵니다.

따라서 제 생각에 이것은 정점 (vertex) 위치인 1, 5, 7, 3번을 가져온다는 뜻이며, 이것이 우리의 첫 번째 면 (face)이 될 것입니다. 비록 네 개의 점은 삼각형이 아니라는 사실이 유명하지만, 그래서 우리는 그 변환을 직접 수행해야 합니다.

그리고, 지금까지 제가 생각해낸 방식은 이렇습니다. — 우리는 단순히 파일을 한 줄씩 읽으며 모든 점을 읽어 들여 리스트에 추가합니다. 그러다 면 (faces) 정보에 도달하면, 각 점의 인덱스 (point index)를 읽고 그에 해당하는 점을 이 삼각형 점 리스트에 추가합니다.

만약 한 면에 3개보다 많은 점이 있다면, 우리는 다음과 같이 삼각형 팬 (triangle fan)을 만들 수 있습니다. 따라서 면에 점이 몇 개가 있든 상관없이 — 처음 3개를 첫 번째 삼각형으로 잡고, 네 번째 점을 추가할 때는 면의 첫 번째 점의 복사본 하나와 이전 삼각형의 마지막 점을 먼저 추가합니다. 그리고 전체가 채워질 때까지 이 과정을 반복합니다.

이것은 면이 볼록 (convex)하다는 상식적인 가정을 전제로 합니다. 만약 오목 (concavity)한 경우를 처리하고 싶다면, 이어 클리핑 알고리즘 (ear-clipping algorithm)과 같이 약간 더 정교한 무언가가 필요할 것입니다.

어쨌든 — 현재 설정은 이렇습니다. 우리는 큐브 (cube) 데이터를 불러옵니다. 삼각형들을 위한 무작위 색상을 생성하여 이 모델 (model) 클래스에 저장합니다. 추가로, 그릴 대상인 렌더 타겟 (render target)을 생성하는데, 이는 전혀 특별한 것이 아니며 이전에 만들었던 이미지와 똑같이 색상 배열을 보유하고 너비와 높이에 편리하게 접근할 수 있게 해줍니다.

모델 클래스는... 훨씬 더 흥미가 없습니다. 이제 이 데이터는 이전에 삼각형 수프 (triangle soup)를 위해 사용했던 것과 동일한 렌더링 함수 (rendering function)로 전달될 수 있습니다. 다만, 현재 그 함수는 삼각형 점들이 이제 3차원 (3 dimensional)이 되었고 이를 어떻게 처리해야 할지 전혀 모르기 때문에 패닉 상태에 빠져 있습니다.

그러니 먼저 점들을 우리에게 익숙한 2D 픽셀 좌표 (pixel coordinates)로 변환하는 함수를 통과시켜 도움을 줍시다. 이를 스크린 공간 (screen-space)이라고 부를 수 있습니다. 이제 우리의 정점 (vertices)들이 미터 (meters) 등으로 측정될 수 있는 세상 어딘가에 있다고 상상해 본다면, 미터와 픽셀 사이의 변환 계수 (conversion factor)를 계산할 수 있도록 우리 이미지에 몇 미터가 들어가는지 정의해야 합니다. 특별한 이유는 없지만 저는 5를 선택했습니다. 그런 다음 3차원을 2차원으로 아주 교묘하게 평면화하되, 마치 z가 존재하지 않는 것처럼 가정한다면, 이를 픽셀 단위로 변환하고 마지막으로 화면 중심 (screen centre)에 더해줄 수 있습니다. 그래야 세상에서의 0 지점에 있는 점이 화면의 중앙에 예쁘게 매핑 (mapping)될 수 있으니까요. 자, 이것을 빠르게 실행해 보겠습니다. 드디어 우리의 아름다운 상자를 볼 수 있겠군요. 뭐, 어쨌든 상자의 한 면이긴 하지만요. 그러니 모든 각도에서 감상할 수 있도록 상자를 회전시켜 봅시다. 이제 우리의 세상에서 오른쪽, 위쪽, 그리고 앞쪽을 향하는 x, y, z 축을 생각해 봅시다. 만약 우리의 정육면체가...