볼록 분해

컴퓨터 그래픽스 게임 개발 마지막 수정: 2026-08-18 04:36:19

1. 개요[편집]

볼록 분해 Convex Decomposition
문제	오목 다각형·다면체를 볼록 조각들로 쪼개기
2D 최소 조각 수	반사정점 r 에 대해 ⌈r/2⌉+1 이상, r+1 이하
2D 최적해	다항 시간(구멍 없을 때) — 구멍이 있으면 NP-난해
2D 근사	Hertel–Mehlhorn — 삼각분할 후 대각선 제거, 최적의 4배 이내
3D	Ω(r²) 조각 필요, 슈타이너 점 없는 사면체 분할 판정은 NP-완전
실무 표준	근사 볼록 분해 — V-HACD, CoACD

볼록 분해는 오목한 다각형이나 다면체를 볼록한 조각들의 모임으로 쪼개는 문제다. 조각들이 내부를 공유하지 않으면 분할(partition), 겹쳐도 되면 덮개(cover)라 부르고, 원래 도형의 꼭짓점 외에 새 점을 찍어도 되면 슈타이너 점(Steiner point)을 허용한다고 말한다.

왜 필요한가는 한 줄로 끝난다. 기하 알고리즘의 거의 전부가 볼록성을 전제로 한다. GJK 알고리즘과 분리축 정리는 볼록체에서만 성립하고, 지지함수 오라클에 오목 메시를 넣으면 조용히 볼록 껍질의 답이 나오며, 민코프스키 합도 볼록끼리면 $O(n+m)$ 인데 오목이 섞이면 최악 $\Theta(n^2m^2)$ 로 폭발한다. 그러니 오목 입력을 만나면 선택지는 셋이다 — 볼록 껍질로 통째로 감싸 정확도를 버리거나, 볼록 조각으로 쪼개거나, 아예 다른 알고리즘을 쓰거나. 실무는 압도적으로 두 번째를 고른다.

2. 얼마나 쪼개야 하는가[편집]

다각형의 오목함은 반사정점(reflex vertex, 내각이 $180^\circ$ 를 넘는 정점)의 개수 $r$ 로 잰다. $r = 0$ 이면 이미 볼록이다.

한 반사정점은 그 정점에서 뻗는 자름선 하나로 해소된다. 자름선이 반사정점에서 출발해 반대편 어딘가에 닿게 하면 되므로, 조각 수는 최대 $r+1$ 개면 충분하다. 반대로 하한이 재미있다. 자름선 하나가 해소할 수 있는 반사정점은 최대 두 개다(선분의 양 끝이 각각 하나씩). 따라서

\#\{\text{볼록 조각}\} \;\ge\; \left\lceil \frac{r}{2} \right\rceil + 1

이고, 이 하한을 실제로 달성하려면 양 끝이 모두 반사정점에 꽂히는 자름선을 많이 만들어야 한다. 그런 자름선을 자유롭게 놓으려면 도형 내부에 새 점을 찍는 것 — 즉 슈타이너 점 — 이 필요할 수 있다. 슈타이너 점을 허용하면 조각 수가 대략 절반으로 줄 수 있다는 것이 이 문제의 첫 번째 구조적 사실이다.¹

3. 다각형 — 정확해와 근사해[편집]

3.1. 최소 분할[편집]

샤젤과 도브킨(1979, 1985)은 구멍 없는 단순다각형에 대해 슈타이너 점을 허용한 최소 볼록 분할을 다항 시간에 구할 수 있음을 보였다. 반사정점 $r$ 에 대한 동적 계획법으로 $O(n + r^3)$ 규모에 끝난다. 슈타이너 점 없이 대각선만 쓰는 최소 분할도 다항 시간이며(카일 1985 계열의 동적 계획법), 두 문제의 최적값이 다르다는 점이 위의 하한 논의와 맞물린다.

경계선은 구멍이다. 링가스(1982)는 구멍이 있는 다각형의 최소 볼록 분할이 NP-난해임을 보였다. 구멍 하나가 문제의 계급을 바꾼다는 것은 계산기하에서 여러 번 반복되는 패턴이다.

3.2. Hertel–Mehlhorn 근사[편집]

정확한 최적해는 구현이 길고, 조각 수를 몇 개 줄이자고 그 노동을 하는 경우가 드물다. 그래서 실무의 국룰은 헤르텔-멜호른(1983)의 두 줄짜리 근사다.

다각형을 삼각분할 한다. 결과는 $n-2$ 개 삼각형과 $n-3$ 개 대각선.
대각선을 하나씩 보며, 지우더라도 반사정점이 새로 생기지 않으면 지운다. 이런 대각선을 “불필요”(inessential)하다고 부른다.

한 반사정점에는 최대 두 개의 필요한 대각선만 남을 수 있다는 관찰에서, 남은 조각 수가 최적의 4배를 넘지 않는다는 보장이 따라 나온다. 삼각분할 이후 단계는 $O(n)$ 이고, 각 대각선 검사는 방향 판정 술어 두 번이면 끝난다. 최적성 4배를 상수 시간에 사는 이 교환비가 워낙 좋아서, 게임·그래픽스 도구의 2D 볼록 분해는 대부분 이 계열이거나 그 변종(Bayazit 의 탐욕적 분할 등)이다.

주의할 점은 이 절차의 강건성이 통째로 삼각분할과 반사정점 판정에 달려 있다는 것이다. 둘 다 방향 판정 술어 하나로 돌아가므로, 정확 술어 없이 짜면 “볼록 조각”이 미세하게 오목해지고 그 결과가 그대로 물리 엔진에 들어간다. 조각이 $10^{-9}$ 만큼 오목해도 GJK 알고리즘의 심플렉스 갱신이 순환에 빠질 수 있다.

4. 3차원 — 여기서부터 곤란해진다[편집]

평면의 직관은 3차원에서 대부분 무너진다.

첫째, 삼각분할이 항상 되는 게 아니다. 단순다각형은 언제나 대각선만으로 삼각분할되지만, 다면체는 그렇지 않다. 쇤하르트 다면체(1928) — 삼각기둥의 위 삼각형을 살짝 비튼 여섯 꼭짓점짜리 도형 — 는 슈타이너 점 없이는 사면체로 분할할 수 없다. 네 꼭짓점을 어떻게 골라도 그 사면체가 도형 밖으로 삐져나가기 때문이다. 여섯 개 점으로 이루어진 도형에서 이런 일이 생긴다는 사실이 3차원의 난이도를 요약한다.²

둘째, 판정 자체가 어렵다. 루퍼트와 자이델(1992)은 “주어진 비볼록 다면체를 슈타이너 점 없이 사면체 분할할 수 있는가”가 NP-완전임을 보였다. 최소 조각 수를 구하는 건 고사하고 가능 여부조차 어렵다는 뜻이다.

셋째, 조각 수가 이차로 폭발한다. 샤젤(1984)은 반사 모서리가 $r$ 개인 다면체가 $\Omega(r^2)$ 개의 볼록 조각을 요구할 수 있음을 보였고, 같은 논문에서 $O(r^2)$ 조각을 만드는 최악 최적 알고리즘을 제시했다. 평면에서 $r+1$ 이던 것이 공간에서 $r^2$ 이 된다 — 조각 100개면 될 것 같은 모델이 만 개가 되는 일이 원리적으로 가능하다.

여기에 실무의 네 번째 문제가 겹친다. 입력 메시가 더럽다. 아티스트가 만든 게임 에셋은 비다양체 모서리, 뒤집힌 법선, 자기교차, 열린 구멍을 기본 옵션으로 달고 있다. 정확 분해 알고리즘은 전부 위상적으로 깨끗한 입력을 요구하므로, 이론적으로 옳은 알고리즘이 실제 데이터에서는 첫 줄에서 죽는다.

5. 근사 볼록 분해 — 실무의 승자[편집]

그래서 물리 엔진 쪽은 문제를 아예 다시 정의했다. 정확히 볼록한 조각을 최소로 구하지 말고, “충분히 볼록한” 조각을 적게 구하자.

리엔과 아마토(2004, 2007)의 근사 볼록 분해(approximate convex decomposition)가 그 틀이다. 조각의 오목도(concavity) — 흔히 조각과 그 볼록 껍질 사이의 최대 거리나 부피 차 — 를 정의하고, 오목도가 임계값 $\tau$ 이하가 될 때까지만 재귀적으로 쪼갠다. $\tau$ 를 키우면 조각이 적고 거칠어지고, 줄이면 정확하지만 많아진다. 조각 수와 근사 오차를 사용자가 손잡이 하나로 맞바꾸는 구조가 핵심이다.

이 발상을 산업 표준으로 만든 것이 마무(K. Mamou)의 HACD(2009)와 그 후속 V-HACD다. V-HACD 의 흐름은 대략 이렇다.

복셀화. 메시를 3차원 격자에 채워 넣는다. 이 한 단계가 자기교차·비다양체·구멍을 전부 무의미하게 만든다 — 위상이 아니라 부피만 보기 때문이다. 더러운 입력에 강한 이유가 전적으로 여기 있다.
재귀 분할. 복셀 덩어리를 축 정렬 평면들로 잘라 보며, 자른 뒤 두 조각의 오목도 합이 가장 작아지는 평면을 고른다. 목표 조각 수나 오목도 임계에 도달할 때까지 재귀.
볼록 껍질. 각 조각의 볼록 껍질을 구하고 정점 수를 상한(보통 32~64)까지 단순화한다.³

결과물은 원본을 조금 부풀린 볼록체 수십 개다. 물리적으로는 캐릭터가 벽에 $2\text{cm}$ 덜 붙는 정도의 차이인데, 그 대가로 충돌 감지 내로 페이즈가 전부 볼록-볼록 질의로 통일된다. Bullet·PhysX·Unity·Blender 가 모두 V-HACD 를 번들하거나 임포터에 내장하면서, “오목 메시를 물리에 넣기 = V-HACD 돌리기”가 사실상의 표준 절차가 됐다.

최근에는 CoACD(2022) 처럼 오목도를 “충돌 관점에서 문제가 되는 오목함”으로 다시 정의하고 몬테카를로 트리 탐색으로 자름 평면을 고르는 접근이 나왔다. 손잡이·컵 구멍처럼 위상적으로 중요한 오목함은 보존하면서 조각 수는 줄이는 것이 목표다. 복셀 기반 V-HACD 가 격자 해상도 때문에 얇은 구조를 메워 버리는 약점을 겨냥한 셈이다.

5.1. 왜 정확 분해가 지는가[편집]

항목	정확 볼록 분해	근사 볼록 분해
입력 요구	깨끗한 다양체 메시	아무거나(복셀화가 흡수)
조각 수	최악 Ω(r²), 실측도 수천 개	사용자가 지정(보통 8~64)
조각 모양	얇은 슬리버가 대량 발생	뚱뚱한 볼록체
결과 정확도	원본과 동일	부풀어남(오목도 τ 만큼)
런타임 비용	조각 수에 비례해 폭증	예산 안에 고정

실시간 물리에서 조각 하나는 곧 경계 볼륨 계층 노드 하나이자 좁은 단계 질의 하나다. 조각 수가 프레임 예산을 직접 먹는다. 슬리버 조각은 여기에 더해 접촉 법선을 불안정하게 만들어 물체가 떨리게 한다. 그래서 “원본과 정확히 같지만 조각 3000개”보다 ” $2\text{cm}$ 부풀었지만 조각 24개”가 거의 항상 이긴다. 근사가 이긴 것이 아니라, 문제 정의가 틀렸던 것에 가깝다.

6. 응용[편집]

충돌 감지. 위에서 본 그대로. 정적 지형은 삼각형 수프 그대로 두고 동적 강체만 볼록 분해하는 것이 흔한 절충이다.
민코프스키 합 계산. 오목 다각형의 합은 $\bigcup_{i,j}(A_i \oplus B_j)$ 로 분해해서 구한다. 조각 수의 곱만큼 볼록합과 불리언 유니온을 돌려야 하므로, 분해 품질이 곧 이 계산의 비용이다. 조각을 절반으로 줄이면 쌍 수가 4분의 1이 된다.
경로 계획. 구성공간 장애물을 명시적으로 만들려면 로봇과 장애물을 각각 볼록 분해해야 한다. 볼록 조각으로 나눈 자유공간은 그 자체로 로드맵의 노드가 되며, 내비게이션 메시의 볼록 폴리곤 셀도 같은 발상이다(에이전트가 셀 안에서는 직선으로 움직여도 안전하다는 보장이 볼록성에서 나온다).
로봇 파지와 시뮬레이션. 로보틱스 물리 시뮬레이터는 URDF 메시를 그대로 못 쓰므로 임포트 단계에서 볼록 분해를 돌린다. 파지 계획에서 손가락이 물체 오목부에 걸리는지를 보려면 오목함을 정확히 보존해야 하는데, 이것이 CoACD 류의 동기다.
부피·관성 계산. 볼록 조각으로 나누면 각 조각의 부피·질량중심·관성 텐서가 닫힌 형태로 나오고, 전체는 그 합이다. 강체 동역학 초기화가 이렇게 이루어진다.

7. 관련 문서[편집]

직관적으로는 “새 점을 찍을 수 있으면 자름선을 아무 데나 놓을 수 있으니 이득”인데, 정작 그 이득이 상수배(대략 2배)에 그친다는 것이 재미있다. 슈타이너 점은 조각 수의 차수를 바꾸지 못한다. 계산기하에서 슈타이너 점이 판을 뒤집는 건 오히려 3차원 쪽인데, 거기서는 “가능/불가능”을 가르기 때문이다. ↩
쇤하르트 다면체는 삼각기둥의 윗면을 조금 돌려서 옆면 사각형 세 개가 각각 안쪽으로 접히게 만든 것이다. 꼭짓점 여섯 개 중 어떤 넷을 골라도 그 사면체가 도형 밖을 지난다는 걸 손으로 확인해 볼 수 있는데, 종이로 만들어 보면 대개 “이게 왜 안 되지”에서 “아 진짜 안 되네”까지 10분쯤 걸린다. 3차원 격자 생성기가 슈타이너 점을 뿌리지 않고는 못 사는 이유가 이 도형 하나로 설명된다. ↩
V-HACD 파라미터 중 실무자를 가장 많이 괴롭히는 건 복셀 해상도다. 낮추면 컵의 구멍이 메워져 물이 안 담기는(라기보다 물체가 컵 안에 못 들어가는) 콜라이더가 나오고, 올리면 임포트가 몇 분씩 걸린다. “일단 돌려” 놓고 커피 마시러 갔다가 조각 수 상한을 잘못 준 걸 깨닫는 것이 이 도구의 국룰 사용법. ↩