Triangle Filling and the Depth Buffer

한국어 원문으로 표시합니다.

목표

무게중심 좌표로 삼각형을 채우고, 꼭짓점 값을 보간하고, 깊이 버퍼로 앞뒤를 정하고, 뒷면을 걸러 냅니다. 이 실습이 끝나면 래스터라이저 한 벌의 핵심이 손에 들어옵니다.

왜 중요한가

화면은 픽셀 격자이고 삼각형의 변은 격자에 맞지 않습니다. 어떤 픽셀이 이 삼각형의 것인지 정하는 규칙이 필요한데, 무게중심 좌표가 그 규칙과 값 보간을 한꺼번에 해결합니다. 세 계수가 모두 0 이상이면 안쪽이고, 같은 계수로 색·법선·텍스처 좌표·깊이를 섞으면 됩니다.

깊이 버퍼는 그보다 더 큰 것을 줍니다. 픽셀마다 지금까지의 최소 깊이를 기억해 두면 그리는 순서와 무관하게 같은 그림이 나옵니다. 삼각형을 정렬할 필요가 없어지고, 서로 관통하는 물체도 자연스럽게 처리됩니다. 하드웨어가 화가 알고리즘 대신 이쪽을 고른 이유입니다.

단계

/root/raster 에 도구 상자를 놓습니다.
/root/raster/bary.py 에 무게중심 좌표를 만듭니다.
/root/raster/out/tri.png 에 삼각형을 채웁니다.
/root/raster/out/tri_rgb.png 에 꼭짓점 색을 보간해 그립니다.
/root/raster/out/zbuffer.png 에 깊이 버퍼로 두 삼각형을 그립니다.
깊이만 맞바꾸어 /root/raster/out/zswap.png 를 만듭니다.
/root/raster/tris.txt 를 읽어 뒷면을 버리고 /root/raster/out/cull.png 와 /root/raster/out/07-cull.txt 를 만듭니다.

참고

그림은 nohup python3 -m http.server 8080 -d /root/raster/out & 로 띄운 뒤 웹 미리보기 에서 http://localhost:8080/ 을 열어 봅니다. zbuffer.png 와 zswap.png 를 나란히 보는 것이 이 실습의 핵심 장면입니다.
픽셀 중심은 (x+0.5, y+0.5) 입니다. 정수 좌표로 판정하면 경계가 한 줄 밀립니다.
흔한 실수 하나: 깊이 비교는 했는데 깊이 버퍼를 갱신하지 않는 것입니다. 그러면 나중에 그린 것이 언제나 이깁니다.
흔한 실수 둘: 경계 상자를 잡지 않고 화면 전체를 도는 것입니다. 결과는 같지만 파이썬에서는 몇 배 느립니다.

그리기 도구 상자를 놓는다

/root/raster/gfxlib.py 를 예시 그대로 저장하고, /root/raster/check.py 로 시험 무늬를 그려 /root/raster/out/00-check.png 를 만드십시오. 무늬는 64x64 검은 배경에 (0,0)에서 (63,63)까지 흰색(255,255,255) 대각선을 긋고, 그 뒤에 (0,32)에서 (63,32)까지 빨강(255,0,0) 가로선을 겹쳐 그은 것입니다.

이 실습부터는 PNG 인코더를 다시 만들지 않습니다. 첫 실습에서 손으로 만든 것과 같은 코드를 도구로 내려 줍니다 — 여기서 배울 것은 파일 형식이 아니기 때문입니다.

실습 파드에는 볼륨이 없어서 앞 실습에서 만든 파일이 남아 있지 않습니다. 그래서 실습마다 도구 상자를 다시 놓는 것으로 시작합니다.

Canvas(w, h, bg) 를 만들고 line(x0, y0, x1, y1, rgb) 로 두 선을 그은 뒤 write_png(path) 로 저장하십시오. 가로선을 나중에 그어야 교차점 (32,32) 가 빨강이 됩니다.

무게중심 좌표

/root/raster/bary.py 에 barycentric(a, b, c, p) 를 만드십시오. a·b·c·p 는 2차원 점이고, p = u*a + v*b + w*c 가 되는 (u, v, w) 세 실수를 돌려줍니다.

분모는 삼각형 넓이의 두 배(부호 있음)입니다.

d = (b1-c1)*(a0-c0) + (c0-b0)*(a1-c1)
u = ((b1-c1)*(p0-c0) + (c0-b0)*(p1-c1)) / d
v = ((c1-a1)*(p0-c0) + (a0-c0)*(p1-c1)) / d
w = 1 - u - v

확인은 꼭짓점으로 합니다. p 가 a 면 (1,0,0), b 면 (0,1,0), c 면 (0,0,1) 이어야 합니다. 그리고 세 값의 합은 어디서든 항상 1 입니다.

세 값이 모두 0 이상이면 삼각형 안쪽입니다. 이 성질 하나가 안팎 판정과 값 보간을 동시에 해결합니다.

삼각형을 칠한다

/root/raster/fill.py 로 /root/raster/out/tri.png(256x256, 검은 배경)에 꼭짓점 (30,30), (220,60), (120,230) 인 삼각형을 빨강(255,60,60) 으로 채우십시오. 픽셀 (x, y) 의 중심은 (x+0.5, y+0.5) 로 보고, 무게중심 좌표 셋이 모두 0 이상일 때 칠합니다.

화면 전체를 훑지 말고 경계 상자 안만 도십시오. 세 꼭짓점의 x 최소·최대, y 최소·최대로 상자를 잡으면 됩니다. GPU 도 같은 일을 타일 단위로 합니다.

픽셀 중심을 (x+0.5, y+0.5) 로 두는 것이 중요합니다. 정수 좌표로 판정하면 경계에서 한 줄이 밀립니다.

칠해진 픽셀 수가 삼각형 넓이와 비슷해야 합니다. 신발끈 공식으로 넓이를 구해 비교해 보십시오.

꼭짓점 색을 섞는다

/root/raster/interp.py 로 같은 삼각형을 /root/raster/out/tri_rgb.png 에 그리되, 꼭짓점 A(30,30) 은 빨강(255,0,0), B(220,60) 은 초록(0,255,0), C(120,230) 은 파랑(0,0,255) 으로 두고 픽셀 색을 u*A색 + v*B색 + w*C색 으로 섞으십시오.

무게중심 좌표는 안팎 판정에만 쓰는 것이 아닙니다. 꼭짓점에 붙은 아무 값이나 같은 계수로 섞으면 됩니다. 색, 텍스처 좌표, 법선, 깊이 모두 같은 방식입니다.

채널마다 따로 섞습니다. r = u*255 + v*0 + w*0 처럼요.

무게중심 셋이 각각 1/3 인 곳(삼각형의 무게중심)에서는 세 채널이 모두 85 안팎이 되어 회색으로 보입니다. 확인해 보십시오.

깊이 버퍼로 앞뒤를 정한다

/root/raster/zbuf.py 로 /root/raster/out/zbuffer.png(256x256, 검은 배경)를 만드십시오. 삼각형 A 는 (30,30),(200,30),(30,200) 에 파랑(60,60,255) 이고 깊이 0.2, 삼각형 B 는 (60,60),(230,60),(60,230) 에 노랑(255,220,60) 이고 깊이 0.8 입니다. 픽셀마다 깊이 버퍼를 두고 더 작은 깊이가 이깁니다.

깊이 버퍼는 화면과 같은 크기의 실수 배열입니다. 처음에는 아주 큰 값(예: float("inf"))으로 채웁니다.

픽셀을 칠하기 전에 z < zbuf[y][x] 인지 보고, 그럴 때만 색과 깊이를 함께 씁니다. 깊이를 갱신하지 않으면 나중에 그린 것이 무조건 이깁니다.

여기서는 삼각형마다 깊이가 일정하지만 실제 렌더러는 깊이도 무게중심 좌표로 보간합니다. 이 단계의 요점은 그리는 순서와 무관하게 같은 그림이 나온다는 것입니다.

깊이만 맞바꾼다

삼각형의 위치와 색은 그대로 두고 깊이만 맞바꿔(A 를 0.8, B 를 0.2) /root/raster/out/zswap.png 를 만드십시오.

코드는 거의 그대로입니다. 깊이 값 두 개만 서로 바꾸면 됩니다.

두 그림을 나란히 놓고 보십시오. 겹치는 영역의 색만 바뀌고 나머지는 똑같습니다. 깊이 버퍼가 하는 일이 정확히 그것입니다 — 픽셀 단위로 앞뒤를 정합니다.

삼각형을 그리는 순서를 바꿔도 결과가 같은지 시험해 보십시오. 같아야 정상입니다. 그 순서 독립성이 z-버퍼를 쓰는 진짜 이유입니다.

뒷면을 골라 버린다

/root/raster/tris.txt 의 삼각형 여섯 개를 읽어, 화면 좌표의 부호 있는 넓이가 음수인 것만 /root/raster/out/cull.png(256x256, 검은 배경)에 자기 색으로 채우고, /root/raster/out/07-cull.txt 에 total=, drawn=, culled= 와 t1=front|back 부터 t6= 까지 아홉 줄을 적으십시오.

부호 있는 넓이는 이렇게 구합니다.

signed_area = ((Bx-Ax)*(Cy-Ay) - (Cx-Ax)*(By-Ay)) / 2

음수면 앞면(front), 양수면 뒷면(back) 으로 봅니다. 화면 좌표는 y 가 아래로 자라기 때문에 부호가 수학 시간의 관례와 반대로 읽힙니다.

tris.txt 의 각 줄은 x0 y0 x1 y1 x2 y2 r g b 아홉 개의 정수입니다. split() 으로 잘라 쓰면 됩니다.

닫힌 물체에서는 뒷면이 어차피 앞면에 가려지므로, 이 부호 하나로 삼각형의 절반을 래스터라이즈 전에 버릴 수 있습니다.