은면 제거

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

1. 개요[편집]

은면 제거 Hidden Surface Removal
다른 이름	가시면 결정(visible surface determination), 은면 소거
문제	시점에서 각 방향으로 가장 먼저 만나는 표면을 고르기
고전 분류	물체공간 / 이미지공간 / 목록 우선순위
표준 서베이	Sutherland, Sproull, Schumacker (1974)
현대의 승자	깊이 버퍼 + 컬링 계층

렌더링의 절반은 “무엇을 그릴까”가 아니라 **“무엇을 안 그려도 되는가”**다.

은면 제거(hidden surface removal, HSR)는 3차원 장면을 2차원 화면에 투영할 때, 시점에서 각 방향으로 가장 먼저 만나는 표면만 남기고 그 뒤에 가려진 표면들을 결과에서 배제하는 문제이자 그 알고리즘의 총칭이다. 불투명한 물체는 뒤에 있는 것을 가린다는 지극히 당연한 사실을 컴퓨터에게 납득시키는 일인데, 그래픽스에서 이 문제가 반세기 넘게 연구된 이유는 답이 어려워서가 아니라 싸게 구하기가 어려워서다. 원리만 따지면 픽셀마다 광선을 쏘아 가장 가까운 교차를 고르면 끝이지만, 그 순진한 계산은 1970년대의 하드웨어로도 2020년대의 프레임 예산으로도 그대로는 감당이 안 된다.

선 그림만 다루던 시절에는 같은 문제를 은선 제거(hidden line removal)라 불렀다. 면을 칠하기 시작하면서 이름이 은면 제거로 옮겨왔고, 오늘날 실시간 렌더링에서 이 문제는 「깊이 버퍼가 최종 심판을 보고, 그 앞단에서 여러 겹의 컬링이 일감을 미리 줄인다」는 계층 구조로 정착했다.

2. 가시성은 정렬 문제다[편집]

서덜랜드·스프룰·슈마커가 1974년에 낸 서베이 「A Characterization of Ten Hidden-Surface Algorithms」는 당시 난립하던 알고리즘 열 편을 한 틀 안에 세운 문헌이고, 지금도 이 분야를 읽는 표준 렌즈를 제공한다.¹ 그 틀의 첫 문장이 이것이다.

은면 제거는 본질적으로 정렬(sorting) 문제다.

$x, y$ 로 정렬하면 「화면에서 겹치는 것들」이 추려지고, $z$ 로 정렬하면 그중 「누가 앞인가」가 결정된다. 알고리즘들이 서로 다른 이유는 문제가 달라서가 아니라 세 축을 어떤 순서로, 어떤 공간에서, 어떤 코히런스(coherence)를 써서 정렬하느냐가 달라서다. 코히런스란 「이웃한 것은 대개 비슷하다」는 성질로, 서베이는 이를 물체·면·스캔라인·에지·깊이·프레임 코히런스로 분류했다. 한 스캔라인에서 보이던 면이 다음 스캔라인에서도 대개 보인다든가, 이번 프레임의 가시성이 다음 프레임과 거의 같다든가 하는 것들이다. 정렬을 매번 처음부터 하지 않고 이 관성을 재활용하는 것이 고전 알고리즘들의 성능 비결이었다.

3. 물체공간과 이미지공간[편집]

같은 서베이가 남긴 두 번째 유산이 어느 공간에서 답을 내는가에 따른 분류다.

물체공간(object space) 알고리즘. 화면 해상도와 무관하게, 기하 자체를 잘라 「보이는 부분」의 정확한 다각형을 구한다. 결과가 해상도에 독립적이라 확대해도 계단이 생기지 않고 벡터 출력으로 뽑을 수 있다. 대신 모든 면 쌍을 따져야 하므로 면 수 $n$ 에 대해 대략 $O(n^2)$ 이고, 부동소수점 오차에 취약하다. 로버츠(1963)의 은선 제거, 구성적 입체 기하의 정확한 불리언이 이쪽 계열이다.
이미지공간(image space) 알고리즘. 화면의 표본점(픽셀)마다 「여기서 보이는 게 뭐냐」만 답한다. 화소 수 $p$ 에 대해 비용이 대략 $O(np)$ 로 면 수에 선형이고, 정밀도가 표본 격자에 갇히는 대신 구현이 압도적으로 단순하고 병렬화가 자명하다. 깊이 버퍼와 레이 트레이싱이 여기 속한다.
목록 우선순위(list-priority) 알고리즘. 그 중간에 있는 하이브리드로, 물체공간에서 그리는 순서만 미리 계산해 두고 실제 합성은 이미지공간에서 덧그리기로 처리한다. 화가 알고리즘과 BSP 트리가 대표 주자다.

$n$ 이 커질수록 $O(n^2)$ 보다 $O(np)$ 가 유리해지고, 화면 해상도는 어차피 고정이라는 사실 — 이 한 줄이 이후 30년의 승부를 결정했다.

4. 고전 알고리즘 지도[편집]

알고리즘	공간	정렬 순서	핵심 아이디어
로버츠(1963)	물체	$z$ 우선	볼록 입체 단위로 자기 가림을 대수적으로 소거
워녹(1969)	이미지	면적 재귀	화면을 사분면으로 쪼개 「단순해질 때까지」 분할
왓킨스(1970)	이미지	$y \to x \to z$	스캔라인마다 활성 에지 목록으로 구간을 나눔
뉴얼–뉴얼–산차(1972)	목록	$z \to$ 덧그리기	깊이로 정렬해 뒤에서 앞으로 칠함
슈마커(1969) / 푹스 외(1980)	목록	전처리된 트리	분리 평면으로 순서를 미리 구움
캣멀·슈트라서(1974)	이미지	없음	픽셀마다 최소 깊이를 기억
에이플(1967) / 위티드(1980)	이미지	광선당 $z$	시점에서 광선을 쏘아 최근접 교차

**워녹 알고리즘**의 발상은 은근히 현대적이다. 화면 영역 하나를 놓고 「이 영역이 자명하게 단순한가」를 묻는다. 영역 안에 다각형이 없거나, 하나뿐이거나, 어느 하나가 영역 전체를 덮으면서 가장 앞이면 즉시 색을 정하고 끝낸다. 애매하면 영역을 네 조각으로 쪼개 같은 질문을 재귀한다. 픽셀 하나 크기까지 내려가면 그때는 무조건 최근접을 고른다. 화면 쿼드트리를 그때그때 만들어 가며 면적 코히런스를 먹는 셈이고, 오늘날 타일 기반 렌더러와 계층적 깊이 판정이 하는 일과 정신적 조상이 같다.

스캔라인 방식은 $y$ 를 바깥 루프로 잡아 문제를 1차원으로 낮춘다. 한 줄에 걸치는 에지들을 활성 에지 목록으로 유지하고, 에지들이 $x$ 축을 자르는 구간마다 「이 구간에서 가장 앞인 면」 하나만 정하면 그 구간 전체를 그 면의 색으로 칠할 수 있다. 다음 줄로 내려갈 때 목록을 통째로 다시 만들지 않고 증분 갱신한다는 점이 핵심이고, 프레임버퍼를 통째로 살 메모리가 없던 시절에 줄 단위로만 메모리를 쓰고도 정확한 답을 낸다는 것이 결정적 장점이었다.

**광선 추적**은 은면 제거를 가장 정직하게 푼다. 픽셀마다 광선을 쏘고 최근접 교차를 취하면 그게 곧 답이다. 순서도 정렬도 필요 없고, 서로 뚫고 지나가는 면이든 순환 겹침이든 자연히 처리된다. 문제는 비용뿐이라, 경계 볼륨 계층과 표면적 휴리스틱으로 교차 후보를 로그 규모로 줄이는 것이 곧 이 계열의 역사가 됐다.

5. 깊이 버퍼의 완승[편집]

캣멀의 1974년 박사학위 논문과 슈트라서의 같은 해 학위논문에서 독립적으로 등장한 z-버퍼는, 위의 어떤 알고리즘보다도 무식하다. 정렬을 아예 포기하고 픽셀마다 「지금까지 본 것 중 최소 깊이」를 하나씩 적어 둔 다음, 새 조각이 그보다 가까울 때만 덮어쓴다. 알고리즘 전체가 비교 한 줄이다.

z_{\text{frag}} < z_{\text{buf}} \;\Rightarrow\; \text{덮어쓰기}, \qquad \text{아니면 폐기}

이 무식함이 곧 미덕이었다. 그리는 순서에 전혀 의존하지 않으므로 관통 삼각형도 순환 겹침도 특수 처리가 필요 없고, 픽셀마다 완전히 독립이라 하드웨어로 넓게 병렬화된다. 전처리가 없으니 장면이 매 프레임 통째로 바뀌어도 상관없다. 유일한 대가가 화면 해상도만큼의 메모리였는데, 1974년에는 그게 파산 선고였고 1995년에는 그냥 램 몇 메가였다. 하드웨어가 싸지는 방향으로만 흐르는 세계에서 메모리로 알고리즘의 영리함을 사 버린 사례이고, 그래픽스에서 몇 번이고 반복되는 패턴이다.² 알고리즘·정밀도·early-Z 같은 z-버퍼 자체의 내부 사정은 깊이 버퍼 문서가 자세히 다룬다.

은면 제거를 픽셀 단위로 푸는 깊이 버퍼와 폴리곤 단위로 푸는 정렬을 132×76 오프스크린 버퍼에서 같은 프레임에 대질시킨다. 막대 3개가 순환 겹침을 이뤄 뒤→앞 순서 6가지를 전부 그려도 최선이 52~106 px 틀리는 반면, z-버퍼는 그리는 순서를 40번 섞어도 결과가 비트 단위로 같다. 깊이를 10비트로 깎으면 벽에 붙은 데칼 414 px 중 238 px가 z-파이팅으로 뒤집히고, 16비트부터 0이 된다.

6. 정밀도 — z-파이팅[편집]

깊이 버퍼의 유일한 구조적 약점은 저장되는 깊이가 $z$ 에 선형이 아니라는 것이다. 원근 투영 후 정규화 장치 좌표의 깊이는 근평면 $n$ , 원평면 $f$ 에 대해

z_{\text{ndc}} \;=\; \frac{f + n}{f - n} \;+\; \frac{1}{z_{\text{view}}} \cdot \frac{-2fn}{f-n}

꼴로, 즉 $1/z$ 에 아핀이다. 정밀도의 대부분이 카메라 코앞에 몰리고 먼 곳은 성기게 표현된다는 뜻이고, 그 결과 멀리 있는 거의 같은 두 평면(겹친 벽, 지형 위의 도로, 데칼)이 유한 정밀도 안에서 구분되지 않아 프레임마다 앞뒤가 깜빡이는 z-파이팅이 난다.³ 흔한 오해와 달리 범인은 원평면이 멀다는 사실 자체가 아니라 $f/n$ 비율이다 — 근평면을 0.01에서 0.1로 밀면 원평면을 열 배 당기는 것과 같은 효과가 난다. 처방은 세 가지로 정리된다.

근평면을 최대한 밀어낸다. 공짜인 데다 효과가 가장 크다. 요구 사항이 허락하는 한 이것부터 한다.
역-Z(reversed-Z). 깊이 매핑을 뒤집어 먼 곳을 0 근처로 보낸 뒤 부동소수점 깊이 버퍼를 쓴다. 부동소수점이 0 근처에서 촘촘하다는 성질과 원근 왜곡이 서로 상쇄되어 정밀도가 거리 전반에 고르게 퍼진다. 대규모 장면의 사실상 표준.
로그 깊이(logarithmic depth). $\log$ 를 씌운 값을 깊이로 쓴다. 행성 규모처럼 $f/n$ 이 $10^7$ 을 넘는 경우에 동원되지만, 프래그먼트 셰이더에서 깊이를 직접 써야 하는 구현이 많아 early-Z가 꺼진다는 큰 비용이 붙는다. 역-Z로 해결되면 굳이 갈 이유가 없다.

7. 그리기 전에 버린다 — 컬링 계층[편집]

현대 파이프라인에서 z-버퍼는 최후의 심판이지 유일한 심판이 아니다. z-버퍼에 도달한 조각은 이미 정점 변환과 래스터화 비용을 다 치른 뒤라, 버려질 게 뻔한 기하는 그 전에 걸러내는 편이 훨씬 싸다. 그래서 실무 엔진은 점점 정밀해지는 체를 여러 겹 쌓는다.

백페이스 컬링. 닫힌 불투명 물체라면 시점을 등진 면은 어차피 자기 앞면에 가려진다. 삼각형 법선 $\mathbf{n}$ 과 시선 $\mathbf{d}$ 에 대해 $\mathbf{n} \cdot \mathbf{d} > 0$ 이면(혹은 화면 투영 후 부호 있는 면적이 음이면) 버린다. 판정이 삼각형당 내적 한 번인데 평균적으로 삼각형의 절반이 날아간다. 가성비로는 이길 것이 없다.
프러스텀 컬링. 시야 절두체 여섯 평면 바깥의 물체를 통째로 버린다. 물체 단위·계층 단위로 하는 것이 요령이라, 경계 볼륨 계층이나 옥트리와 짝지어 쓴다.
오클루전 컬링. 시야 안에 있고 앞면을 보이는데도 다른 물체에 가려 안 보이는 경우를 잡는다. 물체 사이의 관계를 알아야 해서 셋 중 가장 비싸고, 그래서 하드웨어 오클루전 쿼리·소프트웨어 저해상도 래스터화·정적 장면의 PVS 같은 우회로가 잔뜩 생겼다. 이 우회로 중 BSP 트리 잎 사이의 개구부를 이용하는 포털 컬링이 90년대 실내 엔진의 국룰이었다.
셰이딩 전 걸러내기. early-Z는 픽셀 셰이더 실행 전에 깊이 판정을 끝내 탈락 조각의 셰이딩을 통째로 건너뛴다. 계층적 Z(Hi-Z)는 깊이 버퍼를 밉맵처럼 다단 축소해 타일 단위로 한 번에 기각하고, 깊이 프리패스는 첫 패스에서 깊이만 그려 버퍼를 완성한 뒤 두 번째 패스의 모든 조각이 early-Z 혜택을 받게 한다.

컬링 계층 전체가 하는 일을 한 숫자로 요약하면 깊이 복잡도(depth complexity), 즉 픽셀 하나에 몇 개의 조각이 도착하느냐다. 이 값이 1에 가까워질수록 셰이딩 낭비(오버드로)가 사라진다. 반대로 불투명 기하를 앞에서 뒤로 대충 정렬해 그리면 나중 조각들이 early-Z에 줄줄이 걸려 죽으므로, 정렬이 필요 없다던 z-버퍼 시대에도 정렬이 성능 최적화로 돌아온다는 것이 재미있는 대목이다.

8. 깊이 버퍼가 못 푸는 것[편집]

z-버퍼는 「픽셀당 표면 하나」라는 가정 위에 서 있다. 그 가정이 깨지는 곳에서 은면 제거 문제는 아직 안 끝났다.

반투명. 알파 합성은 순서 의존 연산이라 「가장 가까운 것 하나」로 환원되지 않는다. 그래서 반투명 기하는 오늘날에도 화가 알고리즘으로 뒤에서 앞으로 그린다.
경계 픽셀의 부분 덮임. 표면이 픽셀을 절반만 덮으면 깊이 값 하나로는 표현이 안 된다. MSAA가 서브표본마다 깊이를 따로 들고, 카펜터의 A-버퍼(1984)가 픽셀마다 조각 목록을 유지한 것이 이 문제에 대한 답이었다. 자세한 것은 안티앨리어싱.
참여 매질과 볼륨. 연기·구름은 애초에 표면이 아니라 적분해야 할 매질이다. 볼륨 렌더링의 영역.
해상도 독립 출력. 화면 해상도에 답이 묶이므로 벡터 출력이 안 나온다. CAD 도면의 은선 제거가 여전히 물체공간 알고리즘을 쓰는 이유다.

9. 관련 문서[편집]

Sutherland, Sproull, Schumacker (1974), ACM Computing Surveys 6(1). 제목이 「열 가지 은면 알고리즘의 특징 규명」인데, 오해하기 쉬운 게 열 가지 분류가 아니라 열 편의 알고리즘을 한 틀로 비교한 서베이라는 점이다. 분류축은 물체공간·이미지공간·목록 우선순위 셋. 55쪽짜리 이 논문이 반세기 뒤에도 인용되는 이유는, 여기 실린 알고리즘 열 편 중 아홉 편이 죽고 나서도 「가시성 = 정렬 + 코히런스」라는 프레임만은 그대로 살아남았기 때문이다. ↩
워녹의 재귀 분할, 왓킨스의 활성 에지 목록, 슈마커의 분리 평면은 전부 「메모리가 없으니 머리를 쓰자」의 산물이었다. 그리고 전부 「메모리를 사자」 한 방에 정리됐다. 그래픽스에서 우아한 알고리즘이 무식한 병렬 하드웨어에 지는 것은 거의 전통이라, 요즘도 새 기법을 볼 때는 “이거 5년 뒤에 그냥 메모리로 때워지는 거 아닌가”를 한 번씩 의심하게 된다. ↩
데칼(총알 자국, 도로 표시)은 벽 표면에서 $10^{-3}$ 도 안 되는 거리에 붙는 별도 기하라 z-파이팅의 단골 손님이다. 그래서 깊이 바이어스(polygon offset)로 살짝 당겨 놓는데, 이 오프셋을 크게 잡으면 비스듬히 볼 때 데칼이 벽에서 떠 보이고 작게 잡으면 지글거린다. 기울기에 비례하는 슬로프 스케일 바이어스가 있는 이유이자, 요즘 엔진들이 아예 데칼을 화면공간에서 투영해 버리는 이유다. ↩