화가 알고리즘

컴퓨터 그래픽스 게임 개발 마지막 수정: 2026-09-01 04:31:08

1. 개요[편집]

화가는 지우개를 쓰지 않는다. 뒤에 있는 것부터 칠하고, 앞에 있는 것으로 덮는다.

화가 알고리즘(painter’s algorithm), 또는 깊이 정렬 알고리즘(depth sort)은 장면의 면들을 시점에서 먼 것부터 가까운 것 순으로 정렬한 뒤 그 순서대로 화면에 덧그려, 나중에 그린 것이 앞선 것을 덮게 하는 방식으로 가시성을 해결하는 은면 제거 기법이다. 유화를 그리는 화가가 배경을 먼저 칠하고 그 위에 인물을 얹는 순서를 그대로 흉내 냈다고 해서 붙은 이름이다.

발상이 워낙 소박해서 「알고리즘」이라 부르기 민망할 정도지만, 이 소박함 안에 그래픽스의 중요한 교훈이 하나 들어 있다. 가시성을 순서 문제로 환원하면 대부분의 경우 잘 풀리지만, 그 순서가 존재하지 않는 배치가 실제로 존재한다. 화가 알고리즘의 역사는 이 반례를 어떻게 다루느냐의 역사이고, 그 답이 각각 BSP 트리와 깊이 버퍼라는 서로 다른 두 자료구조를 낳았다.

2. 뉴얼–뉴얼–산차 절차[편집]

1972년 뉴얼 형제와 산차가 제시한 깊이 정렬 절차가 이 알고리즘의 표준형이다.¹ 순진하게 「중심 깊이로 정렬해서 그린다」로 끝내지 않고, 정렬한 뒤에 애매한 쌍을 실제로 검사한다는 것이 요점이다.

모든 다각형을 최대 깊이( $z_{\max}$ , 즉 시점에서 가장 먼 정점) 기준으로 정렬한다.
가장 먼 다각형 $P$ 를 꺼낸다. $P$ 의 깊이 구간과 겹치는 다각형 $Q$ 가 없으면 그냥 그린다.
겹치는 $Q$ $Q$ 가 있으면, 점점 비싸지는 검사를 차례로 돌려 「 $P$ $P$ 를 먼저 그려도 안전한가」를 확인한다.
- 화면상 $x$ 구간이 안 겹치는가?
- $y$ 구간이 안 겹치는가?
- $P$ 의 모든 정점이 $Q$ 의 평면 기준으로 시점 반대쪽에 있는가?
- $Q$ 의 모든 정점이 $P$ 의 평면 기준으로 시점 쪽에 있는가?
- 두 다각형의 화면 투영이 실제로는 안 겹치는가?
하나라도 통과하면 $P$ 를 그린다. 전부 실패하면 $Q$ 를 목록 앞으로 옮기고 표시해 둔 뒤 다시 시도한다.
이미 옮긴 적 있는 $Q$ 가 또 걸리면 순서가 존재하지 않는다는 뜻이다. 이때는 $Q$ 의 평면으로 $P$ 를 잘라 두 조각으로 만들고 다시 넣는다.

앞의 세 검사는 싸고 자주 통과하며, 마지막 절단은 비싸지만 거의 안 걸린다 — 실용적 알고리즘 설계의 전형이다. 그리고 5번 단계가 이 문서의 핵심이다. 화가 알고리즘은 자기가 못 푸는 경우가 있다는 걸 알고 있고, 그때는 기하를 잘라 버린다.

3. 정렬 기준이 애매하다[편집]

“먼 것부터”라는 말은 다각형이 점이 아닌 이상 애매하다. 하나의 다각형은 깊이 구간 $[z_{\min}, z_{\max}]$ 를 차지하므로, 대표값을 무엇으로 잡느냐에 따라 순서가 달라진다.

기준	성질	전형적 실패
중심(centroid) $z$	가장 흔하고 가장 싸다	크기 차가 큰 두 면. 큰 바닥면의 중심이 멀리 잡혀 작은 물체보다 뒤로 감
최대 $z$	뉴얼 등의 원안	길게 기울어진 면의 뒤끝 하나가 정렬을 지배
최소 $z$	전–후 순회에 자연스러움	대칭적으로 같은 문제
구간 겹침 판정	정확	대표값 하나로 정렬이 안 되므로 부분순서만 얻음

근본 문제는 「 $P$ 가 $Q$ 를 가린다」는 가리기 관계가 대표값 하나로 표현되는 전순서가 아니라는 것이다. 깊이 구간이 겹치는 순간 관계는 화면상 어디를 보느냐에 따라 달라지고, 대표값 정렬은 그 관계의 조잡한 근사에 불과하다. 실무에서 큰 바닥 평면 위의 작은 소품이 갑자기 바닥 밑으로 꺼져 보이는 버그는 거의 언제나 중심 $z$ 정렬 탓이다.

4. 어떤 순서로도 못 푸는 경우[편집]

정렬 기준을 아무리 정교하게 다듬어도 원리적으로 정답 순서가 없는 배치가 있다. 두 종류다.

관통(interpenetration). 두 삼각형이 서로를 뚫고 지나가면, 화면의 어떤 영역에서는 $P$ 가 앞이고 다른 영역에서는 $Q$ 가 앞이다. 어느 쪽을 먼저 그리든 절반은 틀린다.

순환 겹침(cyclic overlap). 서로 뚫지 않는데도 순서가 없을 수 있다. 길쭉한 삼각형 셋을 바람개비처럼 비스듬히 배치하면, $P$ 가 $Q$ 의 일부를 가리고 $Q$ 가 $R$ 의 일부를 가리고 $R$ 이 다시 $P$ 의 일부를 가리는 구성이 만들어진다. 가리기 관계가

P \prec Q, \quad Q \prec R, \quad R \prec P

로 순환하므로 위상 정렬 자체가 불가능하다. 세 개면 충분하고, 특별히 병리적인 형상도 필요 없다 — 삼각형 세 장을 손으로 겹쳐 보면 금방 만들어진다.

이 두 반례는 「정렬을 더 잘하자」로는 절대 사라지지 않는다. 탈출로는 정확히 두 갈래뿐이다. 기하를 잘라서 순환을 없애든가, 정렬을 포기하든가.

5. 자르는 쪽 — BSP 트리[편집]

BSP 트리는 첫 번째 탈출로를 자료구조로 굳힌 것이다. 공간을 초평면으로 재귀 분할하면서, 평면에 걸치는 다각형을 분할 시점에 미리 잘라 둔다. 그러면 어떤 잎에 있는 다각형도 다른 잎의 다각형과 순환 관계를 맺을 수 없고, 트리를 한 번 순회하는 것만으로 그 시점에 대한 정확한 후–전 순서가 나온다. 비교 정렬이 아니라 순회라 $O(n)$ 이고, 시점이 움직여도 트리는 그대로다.

즉 BSP는 「화가 알고리즘의 절단 단계(위 절차의 5번)를 런타임에서 전처리로 옮긴 것」이라고 읽으면 정확하다. 뉴얼 등이 순환을 만날 때마다 그 자리에서 잘랐다면, 푹스·케뎀·네일러(1980)는 미리 다 잘라 놓고 순환이 생길 여지 자체를 없앴다. 대가는 다각형 수 증가이고, 3차원 최악의 경우 $\Theta(n^2)$ 까지 터질 수 있다. Doom과 Quake가 이 거래를 받아들여 90년대를 지배했다.

6. 포기하는 쪽 — 깊이 버퍼[편집]

두 번째 탈출로가 깊이 버퍼다. 정렬을 아예 하지 않고 픽셀마다 최소 깊이를 기억하면, 관통이든 순환이든 문제 자체가 소멸한다. 픽셀 하나의 관점에서는 언제나 「여기 도달한 조각들 중 최소 깊이」라는 유일한 답이 있기 때문이다. 화가 알고리즘의 반례는 「면 단위로 순서를 매기려 했기 때문에」 생긴 것이지 기하 자체의 모순이 아니었던 셈이다.

1990년대 후반 소비자 GPU에 깊이 버퍼가 기본 탑재되면서 불투명 기하의 화가 알고리즘은 사실상 은퇴했다. 그런데 완전히 죽지는 않았다.

7. 뒤집으면 오버드로가 죽는다[편집]

정렬 방향을 뒤집은 전–후(front-to-back) 순회는 깊이 버퍼 시대에 오히려 더 중요해졌다. 불투명 기하를 가까운 것부터 그리면, 나중에 오는 조각들이 이미 채워진 깊이 버퍼에 걸려 early-Z에서 무더기로 탈락한다. 픽셀 셰이더가 무거울수록 이득이 커서, 요즘 엔진의 불투명 패스는 재질별 묶음과 대략적 전–후 정렬을 함께 고려해 드로 순서를 짠다. “정렬이 필요 없다”던 z-버퍼가 성능을 위해 정렬을 다시 불러온 셈이다.

볼륨 렌더링에서는 전–후 합성이 아예 표준이다. 누적 투과도를 들고 광선을 앞에서 뒤로 적분하다가 투과도가 충분히 작아지면 나머지 표본을 통째로 버리는 조기 광선 종료(early ray termination)가 가능하기 때문이다. 후–전으로 하면 이 최적화가 불가능하다.

8. 반투명 — 여기서는 여전히 필수[편집]

깊이 버퍼가 못 푸는 유일한 문제가 알파 합성의 순서 의존성이다. 소스 색 $C_s$ , 알파 $\alpha_s$ 를 배경 $C_d$ 위에 얹는 표준 「over」 연산은

C_o \;=\; \alpha_s C_s + (1-\alpha_s)\, C_d

인데, 이 연산은 결합적이지만 가환이 아니다. $A$ 를 $B$ 위에 얹은 것과 $B$ 를 $A$ 위에 얹은 것이 다르다는 말이고, 따라서 반투명 표면들은 반드시 정해진 순서로 합성해야 한다. 깊이 버퍼는 픽셀당 표면 하나만 기억하므로 이 정보를 애초에 담지 못한다. 그래서 오늘날 모든 실시간 엔진의 렌더 루프는 다음 모양이다.

불투명 기하를 전–후로, 깊이 쓰기를 켠 채 그린다.
반투명 기하를 후–전으로, 즉 화가 알고리즘으로 정렬해 깊이 테스트는 켜고 깊이 쓰기는 끈 채 그린다.

2단계에서 쓰는 정렬은 보통 물체(또는 파티클) 단위 중심 $z$ 정렬이고, 위에서 본 모든 병리를 그대로 물려받는다. 유리창 두 장이 교차하면 어느 쪽을 먼저 그려도 틀리고, 연기 파티클 시스템은 카메라가 회전하는 순간 정렬 순서가 뒤집히며 팝핑을 낸다. 게임에서 반투명이 유독 버그가 많은 것은 게을러서가 아니라 1972년의 미해결 문제를 그대로 안고 있기 때문이다.² 이 순서 의존을 근본적으로 없애려는 것이 순서 독립 투명도 계열 기법으로, 픽셀마다 조각을 여러 겹 벗겨 내는 깊이 벗기기(depth peeling)나 깊이에 따른 가중 평균으로 근사하는 방식 등이 있다. 디퍼드 셰이딩이 반투명을 못 다루고 별도의 포워드 패스를 두는 이유도 정확히 같은 곳에서 온다 — G-버퍼는 픽셀당 표면 하나만 담는다.

9. 2D에서는 아직도 현역[편집]

3차원에서 밀려난 화가 알고리즘은 2차원으로 내려오면 여전히 정의 그 자체다. 깊이가 없는 대신 그리기 순서가 곧 의미이기 때문에, 애초에 반례가 생길 여지가 없다.

벡터 그래픽스 렌더링 모델. 포스트스크립트·PDF·SVG·HTML 캔버스는 모두 「도형을 문서 순서대로 덧칠한다」는 화가 모델을 규격으로 못박고 있다. CSS의 z-index와 쌓임 맥락(stacking context)은 이 순서를 사용자가 직접 조작하는 인터페이스다.
스프라이트와 타일. 2D 게임의 레이어 순서, 쿼터뷰에서 캐릭터를 $y$ 좌표로 정렬해 아래쪽 것을 나중에 그리는 관행이 전부 화가 알고리즘이다.³ 실제로 이런 정렬은 3D의 순환 겹침에 해당하는 배치를 아주 드물게 만들어 내고, 그러면 캐릭터가 기둥을 뚫고 나온 것처럼 보인다.
UI 합성. 윈도 매니저와 UI 툴킷의 위젯 합성 역시 뒤에서 앞으로 덧그리기이며, 여기에 알파 합성이 붙는 순간 위의 「over 연산자는 가환이 아니다」가 그대로 적용된다.

10. 관련 문서[편집]

Newell, Newell, Sancha (1972), “A solution to the hidden surface problem”, Proc. ACM National Conference. 제목이 “a solution”인 게 은근히 정직하다. “the solution”이 아니었고, 저자들 스스로 순환 겹침에서는 자르는 수밖에 없다는 걸 논문 안에서 인정했다. ↩
그래서 게임 업계에는 「유리창은 한 번에 한 장만」이라는 암묵적 미술 가이드가 있다. 유리창 두 장이 겹쳐 보이는 각도를 아예 레벨 디자인에서 막아 버리는 것이, 순서 독립 투명도를 켜서 프레임을 갈아 넣는 것보다 싸기 때문이다. 알고리즘으로 못 푸는 문제를 아트 디렉션으로 푸는 유서 깊은 전통. ↩
쿼터뷰 게임의 $y$ 정렬은 사실 「바닥에 발이 닿는 점이 아래일수록 카메라에 가깝다」는 가정에 기댄 근사다. 그래서 캐릭터가 점프하거나 계단에 올라서면 가정이 깨지고, 갑자기 벽 앞으로 튀어나오거나 뒤로 숨는다. 2D 게임 버그 리포트의 스테디셀러. ↩