구성적 입체 기하

컴퓨터 그래픽스 소프트웨어 마지막 수정: 2026-09-01 04:47:52

1. 개요[편집]

구성적 입체 기하 Constructive Solid Geometry
약칭	CSG
표현	원시 입체를 잎으로, 불리언 연산을 내부 노드로 갖는 트리
연산	정규화 합집합 · 교집합 · 차집합
기원	로체스터 대학 Production Automation Project (1970년대 후반)
평가 방식	점 분류 · 광선 구간 병합 · 부호거리장 · 메시 불리언

조각가는 돌을 깎고, 기술자는 구멍을 뚫는다. 형상을 「무엇을 더하고 무엇을 뺐는가」의 역사로 기록하자.

구성적 입체 기하(Constructive Solid Geometry, CSG)는 구·직육면체·원기둥·원뿔 같은 소수의 원시 입체(primitive)를 잎으로, 합집합·교집합·차집합 같은 불리언 연산을 내부 노드로 갖는 트리로 3차원 형상을 표현하는 방식이다. 형상 데이터가 곧 「만드는 절차」라는 점이 핵심이다. 볼트 구멍이 뚫린 블록은 표면 정보의 나열이 아니라 「블록 빼기 원기둥」이라는 두 노드짜리 식으로 저장되고, 구멍 지름을 바꾸려면 잎의 반지름 파라미터 하나만 고치면 된다.

1970년대 후반 로체스터 대학의 Production Automation Project에서 레퀴차와 뵐커가 이론을 정리하고 PADL 시스템으로 구현하면서 이름을 얻었다.¹ 오늘날 CAD의 표면 표현 자리는 경계 표현(B-rep)에 내줬지만, 파라메트릭 모델링의 피처 트리, 레이 트레이서의 형상 정의, 부호거리장 기반 렌더링과 절차적 형상 생성에서 CSG는 여전히 일급 시민이다.

2. 표현이자 계산 모형[편집]

CSG 트리의 강점은 「형상을 저장한다」가 아니라 **「형상에 대한 질문을 트리 순회로 환원한다」**는 데 있다. 임의의 점 $\mathbf{p}$ 가 입체 안에 있는지(레퀴차의 용어로 점 분류, point membership classification)를 물으면, 잎에서 원시 입체마다 안/경계/밖을 판정한 뒤 내부 노드에서 다음 규칙으로 합치면 끝난다.

$A \cup B$ : 둘 중 하나라도 안이면 안.
$A \cap B$ : 둘 다 안이어야 안.
$A \setminus B$ : $A$ 안이고 $B$ 밖이어야 안.

원시 입체의 판정은 대개 부등식 하나이므로, 임의의 복잡한 형상에 대한 내부 판정이 트리 깊이에 선형인 비용으로 끝난다. 메시로 표현했다면 광선을 쏘아 교차 수의 홀짝을 세거나 감김수를 계산해야 하는 일이다. 같은 원리가 광선 교차·거리 계산·부피 적분에도 그대로 적용되고, 그래서 CSG는 표현 형식이라기보다 평가 가능한 계산 모형에 가깝다.

3. 정규화 불리언 연산[편집]

순진하게 집합론의 $\cup, \cap, \setminus$ 를 쓰면 곧바로 병리가 나온다. 정육면체 두 개를 면끼리 딱 붙여 놓고 교집합을 취하면 결과는 두께 0의 사각형 한 장이고, 모서리끼리 붙이면 선분, 꼭짓점끼리 붙이면 점이다. 이것들은 「입체」가 아니다 — 부피가 0이고, 표면이 닫혀 있지 않으며, 제조도 렌더링도 불가능하다. 차집합에서도 같은 일이 생겨서, 잘라 낸 자리에 두께 없는 막이나 튀어나온 지느러미가 남는다. 이 차원 축퇴(dimensional degeneracy)를 없애기 위해 CSG는 보통 집합 연산 대신 정규화 불리언 연산(regularized boolean operation)을 쓴다.

A \;\mathrm{op}^{*}\; B \;=\; \mathrm{cl}\bigl(\mathrm{int}(A \;\mathrm{op}\; B)\bigr)

내부(interior)를 취해 저차원 부스러기를 날린 뒤 폐포(closure)를 취해 경계를 복원한다는 뜻이다. 이 정의는 「입체」를 위상적으로 규정하는 것과 한 몸인데, 레퀴차는 유효한 입체를 정칙 집합(regular set), 즉 $S = \mathrm{cl}(\mathrm{int}(S))$ 를 만족하는 유계 집합으로 정의했다. 이 조건이 곧 “두께 없는 조각도, 고립점도, 안쪽에 빠진 균열도 없다”는 요구다. 정규화 연산은 정칙 집합을 정칙 집합으로 보내므로, CSG 트리의 어느 부분식을 평가해도 결과가 항상 유효한 입체임이 보장된다. 이론적 깔끔함이 실무의 안전장치로 직결된 드문 사례다.²

물론 이론이 보장한다고 구현이 보장되는 것은 아니다. 실제로 「딱 붙은 면」을 판정하는 것은 부동소수점 비교이고, 그 판정이 한 번 흔들리면 정규화도 함께 무너진다. 아래 강건성 절에서 다시 본다.

4. B-rep과의 분업[편집]

	CSG	경계 표현(B-rep)
저장하는 것	연산의 역사	면·모서리·정점의 위상과 기하
유효성	구조적으로 보장	위상 무결성을 따로 검사해야 함
편집	파라미터 수정이 자명	국소 수정이 자유로움
표면 질의	매번 평가해야 함	즉시 조회
자유곡면	원시 입체에 갇힘	NURBS·스플라인 자유
렌더링	광선 기반이면 직접 가능	삼각형화가 직접적

현대 CAD 커널(Parasolid, ACIS, OpenCASCADE 등)의 내부 형상 표현은 사실상 전부 B-rep이다. 자유곡면을 다뤄야 하고, 면 하나에 필렛을 걸거나 모따기를 하는 국소 편집이 CSG 트리에서는 표현되지 않기 때문이다. 그런데 사용자가 보는 화면은 여전히 CSG다 — 스케치를 돌출시키고, 그 위에 구멍을 뚫고, 다시 리브를 더하는 피처 히스토리 트리는 정확히 CSG 트리의 후손이다. 즉 오늘날의 파라메트릭 CAD는 UI와 편집 이력은 CSG, 내부 형상은 B-rep으로 분업하며, 파라미터를 고치면 트리를 위에서부터 다시 실행해 B-rep을 재생성한다. 실무자가 치를 떠는 “리빌드 실패”는 이 재실행이 중간 어딘가에서 위상적으로 말이 안 되는 상태를 만났다는 뜻이다.

5. 광선으로 직접 푸는 CSG[편집]

CSG 트리를 삼각형으로 바꾸지 않고 그대로 렌더링하는 고전적 방법이 광선 캐스팅이다. 로스(1982)가 정리한 이 알고리즘은 놀랍도록 우아하다.³

광선 $\mathbf{r}(t) = \mathbf{o} + t\mathbf{d}$ 하나를 잡으면, 각 원시 입체는 그 광선 위에서 입체 내부에 해당하는 1차원 구간들의 목록을 준다. 구는 최대 한 구간 $[t_{\text{in}}, t_{\text{out}}]$ , 볼록 다면체도 한 구간, 원기둥은 뚜껑까지 고려하면 여전히 한 구간이다. 그러면 3차원 불리언 문제가 1차원 구간 집합의 불리언 문제로 내려앉는다.

$A \cup B$ → 두 구간 목록의 합집합(겹치면 병합)
$A \cap B$ → 구간 목록의 교집합
$A \setminus B$ → $A$ 의 구간에서 $B$ 의 구간을 빼기

트리를 잎에서 뿌리로 올라가며 구간 목록을 병합하고, 뿌리에서 나온 목록의 첫 구간 시작점이 곧 최근접 교차점이다. 그 지점이 어느 원시 입체의 표면에서 왔는지를 함께 나르면 법선도 공짜로 얻는다. 3차원의 표면 교차선을 명시적으로 계산하는 일 없이 정확한 불리언 결과가 나온다는 것이 이 방법의 매력이고, POV-Ray를 비롯한 고전 레이 트레이서들이 CSG를 기본 기능으로 제공할 수 있었던 이유다. 은면 제거 관점에서 보면, 레이 트레이싱이 가시성을 광선당 정렬로 푸는 방식이 불리언 평가와 그대로 맞물린 셈이다.

래스터라이저 위에서도 비슷한 일을 할 수 있다. CSG 트리를 「교집합들의 합집합」 형태(분리 정규형)로 펼친 뒤, 깊이 버퍼와 스텐실 버퍼로 각 항의 앞면·뒷면을 세어 가며 표면 조각을 걸러내는 이미지공간 CSG 렌더링이 1980년대부터 연구됐다. 다만 트리를 정규형으로 펼치면 항 수가 지수적으로 늘 수 있고, 결과가 화면 해상도에 갇힌다는 이미지공간 알고리즘의 숙명을 그대로 물려받는다.

6. 부호거리장 위의 CSG[편집]

현대적 재해석은 부호거리장(SDF)에서 나온다. 형상을 경계에서 0, 안에서 음수, 밖에서 양수인 함수 $\phi(\mathbf{p})$ 로 두면 CSG 연산이 산술 한 줄로 표현된다.

\phi_{A \cup B} = \min(\phi_A, \phi_B), \qquad \phi_{A \cap B} = \max(\phi_A, \phi_B), \qquad \phi_{A \setminus B} = \max(\phi_A, -\phi_B)

여집합이 부호 반전이라는 점까지 포함해 완벽하게 대칭적이다. 이 세 줄과 원시 입체의 거리 함수 몇 개만 있으면 셰이더 안에서 임의의 CSG 트리를 평가할 수 있고, 하트의 스피어 트레이싱(1996)으로 $\phi$ 값만큼씩 광선을 전진시키면 렌더링까지 끝난다.⁴ 데모신과 셰이더 커뮤니티가 몇십 줄짜리 셰이더로 복잡한 장면을 뽑아내는 레이 마칭의 골격이 정확히 이것이다.

다만 min/max는 거리를 보존하지 않는다. 정확히 말하면 이렇다.

합집합의 $\min$ 은 외부에서 정확하다. 닫힌 집합 밖의 점에서 집합까지의 거리는 두 거리의 최솟값과 정확히 같다.
교집합·차집합의 $\max$ 는 과소추정이다. 두 반공간이 만나는 모서리 바깥에서 실제 거리는 $\sqrt{d_A^2 + d_B^2}$ 인데 $\max(d_A, d_B)$ 를 반환한다. 값이 실제보다 작으므로 스피어 트레이싱은 표면을 뛰어넘지 않는다 — 틀리지는 않지만, 모서리 근처에서 전진 폭이 쪼그라들어 반복 횟수가 폭증한다. 오목한 모서리가 많은 형상의 레이 마칭이 유독 느린 이유다.
내부의 값은 합집합에서도 틀린다. 두 입체가 겹친 안쪽에서 $\min$ 은 실제 침투 깊이보다 얕은 값을 준다. SDF를 물리 충돌의 침투 깊이나 밀어내기 벡터로 쓸 때 이것이 직접 오차가 된다.
결과 필드를 다시 입력으로 쓰면 오차가 번진다. 라운딩( $\phi - r$ )이나 쉘 만들기( $|\phi| - t$ ) 같은 후속 연산은 $\phi$ 가 진짜 거리임을 전제한다. $\max$ 로 만든 근사 필드에 라운딩을 걸면 모서리 반경이 자리마다 달라진다.

여기에 부드러운 최소(smooth minimum, smin)를 쓰면 두 형상이 만나는 자리에 유기적인 이음매가 생긴다. 대표적인 다항식 형태는 보간 계수 $h = \mathrm{clamp}\!\left(\tfrac12 + \tfrac{\phi_B - \phi_A}{2k},\, 0,\, 1\right)$ 를 써서

\mathrm{smin}_k(\phi_A, \phi_B) \;=\; \phi_B + h\,(\phi_A - \phi_B) \;-\; k\,h\,(1-h)

로 쓴다. 마지막 항이 이음매를 안쪽으로 끌어당기는 살이다. 값이 $\min$ 보다 항상 작으므로 스피어 트레이싱은 여전히 안전하지만, 대가는 분명하다. 결과는 더 이상 거리장이 아니고( $\|\nabla\phi\| \ne 1$ ), 블렌드 폭 $k$ 가 월드 단위라 비균등 스케일을 걸면 의미가 깨지며, 무엇보다 결합법칙이 성립하지 않는다 — $\mathrm{smin}(\mathrm{smin}(A,B),C)$ 와 $\mathrm{smin}(A,\mathrm{smin}(B,C))$ 가 다른 형상을 준다. 트리에 노드를 하나 끼워 넣으면 상관없던 자리의 이음매가 바뀌는 것이 SDF 모델링의 고질적 짜증이다. 도메인 자체를 비트는 변형(twist, bend)을 얹으면 립시츠 상수가 1을 넘어가 광선이 표면을 실제로 뛰어넘을 수 있고, 그래서 실무 레이 마칭 셰이더는 전진 폭에 0.5~0.8 정도의 안전계수를 곱한다.

7. 강건성 — 진짜 적은 부동소수점[편집]

CSG 구현이 죽는 자리는 대부분 알고리즘이 아니라 술어(predicate)다. 「이 정점이 저 평면 위인가, 앞인가, 뒤인가」, 「이 두 면이 같은 평면인가」 같은 판정 하나가 엡실론 비교로 갈리는데, 여기서 서로 모순되는 답이 나오면 결과 메시가 닫히지 않는다. 조각 사이에 폭 0의 틈이 생기거나, 같은 모서리를 공유해야 할 두 면이 서로를 못 찾는 식이다.

문제를 어렵게 만드는 것은 정확히 축퇴된 입력이 예외가 아니라 표준이라는 점이다. CAD 사용자는 원기둥을 블록 면에 정확히 맞춰 놓고, 두 상자를 정확히 같은 좌표에 붙인다. 무작위 입력이라면 확률 0인 경우들이 실무에서는 거의 모든 입력이다. 대응은 세 갈래로 정리된다.

정확 술어. 부호 판정만은 오차 없이 계산한다. 부동소수점 필터로 대부분을 빠르게 처리하고 애매할 때만 다중정밀도로 넘어가는 적응 방식이 표준이며, 이때 술어들 사이의 일관성이 보장된다는 것이 핵심 이득이다.
정확한 산술로 전환. 유리수 좌표나 정수 격자 위에서 계산해 애초에 오차를 없앤다. 느리고 좌표가 폭발하지만 결과는 확실하다.
BSP 트리 기반 메시 불리언. 한 입체의 다각형을 다른 입체의 BSP에 통과시켜 안/밖을 순회로 판정하는 티보–네일러(1987) 방식. 판정이 「평면 대 정점의 부호」 하나로 좁혀지므로 강건성 문제도 그 한 점으로 집중된다.

CGAL 같은 계산기하 라이브러리가 정확 산술을 기본값으로 두는 이유, 그리고 3D 프린팅 슬라이서가 “메시가 닫혀 있지 않습니다”를 그렇게 자주 뱉는 이유가 모두 여기 있다. 자세한 배경은 계산기하학과 부동소수점 연산 참고.

8. 삼각형으로 내려오기[편집]

결국 GPU에 넣거나 유한요소법 해석기에 넘기려면 표면 메시가 필요하다. CSG를 다각형화하는 길은 둘이다.

함수를 격자에 샘플링해 등가면을 뽑는 길. CSG 트리를 SDF나 음함수로 평가해 3차원 격자에 굽고 마칭 큐브를 돌린다. 구현이 단순하고 어떤 트리든 통과하지만, CSG가 만들어 내는 날카로운 모서리가 격자 해상도에 뭉개진다는 치명적 약점이 있다. 볼트 구멍의 모서리가 계단이 되거나 둥글게 깎여 나온다. 듀얼 컨투어링은 교차점의 위치뿐 아니라 법선까지 함께 표본(Hermite 데이터)해서 셀 내부 정점을 이차형식 최소화로 배치하는데, 덕분에 모서리와 꼭짓점이 살아남는다. CSG와 궁합이 좋은 것은 이쪽이다. 옥트리로 적응적으로 세분하면 평평한 곳의 삼각형도 아낄 수 있다.

메시끼리 직접 자르는 길. 각 원시 입체를 먼저 삼각형화한 뒤 삼각형 대 삼각형 교차선을 모두 구하고, 그 선을 따라 면을 다시 삼각분할한 다음 각 조각을 안/밖으로 분류해 취사선택한다. 날카로운 모서리가 정확히 보존되고 삼각형 수도 적지만, 앞 절에서 본 강건성 지옥이 그대로 열린다. 상용 CAD와 진지한 메시 불리언 라이브러리가 가는 길이며, 그래서 그들이 정확 술어에 그만큼 투자한다.

9. 관련 문서[편집]

레퀴차와 뵐커의 PADL(Part and Assembly Description Language) 시리즈가 CSG를 처음으로 제대로 구현한 시스템이다. 재미있는 건 이 프로젝트의 목표가 그래픽스가 아니라 공작기계 자동화였다는 점 — 형상을 「어떻게 깎아 내는가」로 기술하면 NC 가공 경로가 자연히 따라 나온다는 발상이었다. CSG가 절삭 가공과 궁합이 좋은 것은 우연이 아니라 태생이다. ↩
“두께 0인 조각을 없앤다”는 요구는 순수 수학에서는 사소해 보이지만 제조업에서는 생사가 걸린다. 부피 0의 면 하나가 결과에 남으면 CAM 소프트웨어가 존재하지 않는 살을 깎으려 들거나, 3D 프린터 슬라이서가 두께 0인 벽을 만나 무한 루프에 빠진다. 위상수학 교과서의 cl(int(·)) 가 공장에서 사고를 막고 있는 셈. ↩
Roth (1982), “Ray casting for modeling solids”, Computer Graphics and Image Processing 18(2). 3차원 불리언을 1차원 구간 불리언으로 떨어뜨리는 이 아이디어는, 어려운 문제를 광선 하나로 잘라 차원을 낮춘다는 점에서 몬테카를로적 발상과 정신이 닮았다. 광선마다 독립이라 병렬화도 자명해서, 40년이 지난 지금 GPU 위에서 오히려 더 잘 돌아간다. ↩
Hart (1996), “Sphere tracing”. 이름 그대로 “현재 위치에서 가장 가까운 표면까지의 거리를 반지름으로 하는 구 안에는 아무것도 없다”는 보장을 이용해 그만큼 안심하고 전진하는 방법이다. 거리장이 거리의 하한이기만 하면 정확성이 보장된다는 게 이 방법의 관대한 점인데, 사람들이 smin이며 도메인 왜곡이며 온갖 것을 얹다가 결국 그 하한 조건을 깨뜨리고 “왜 표면에 구멍이 뚫리지”로 고통받는 것이 셰이더 씬의 전통 행사다. ↩