제약 해결기

제약 해결기 Constraint Solver
분야	물리 시뮬레이션 × 게임 개발
목적	조인트·접촉 등 제약 조건 만족
주요 기법	순차 임펄스, PGS, PBD/XPBD
수학적 배경	선형 상보성 문제(LCP)
관련 문서	물리 엔진, 강체 동역학

1. 개요[편집]

제약 해결기(Constraint Solver)는 물리 시뮬레이션에서 물체들이 지켜야 할 조건 — 관절이 빠지지 않고, 물체끼리 서로 파고들지 않으며, 밧줄이 늘어나지 않는 등 — 을 매 프레임 강제로 만족시키는 물리 엔진의 핵심 모듈이다. 자유롭게 날아다니려는 물체들에게 “너희는 이렇게 연결되어 있어야 해”라고 규칙을 강제하는 심판 역할을 한다.

강체 동역학에서 물체의 자유로운 운동은 뉴턴-오일러 방정식으로 잘 정의된다. 하지만 경첩으로 연결된 문, 바닥에 놓인 상자, 서로 부딪힌 두 공처럼 물체가 다른 물체에 구속되면, 그 구속을 유지하기 위한 반력을 매 순간 계산해야 한다. 이 반력 계산이 제약 해결기의 존재 이유다.¹

2. 제약의 종류[편집]

제약은 크게 등식 제약과 부등식 제약으로 나뉜다. 이 구분이 알고리즘 전체의 성격을 결정한다.

• 등식 제약(equality): 항상 정확히 만족해야 하는 조건. 관절(joint)이 대표적이다. 힌지 조인트는 두 물체가 한 축을 공유하도록, 볼-소켓 조인트는 한 점을 공유하도록 강제한다.
• 부등식 제약(inequality): 한쪽 방향으로만 작동하는 조건. 접촉(contact)이 대표적이다. “파고들지 마라”는 강제하지만 “떨어지지 마라”는 강제하지 않는다. 즉 밀 수는 있어도 당길 수는 없다.

부등식 제약은 “제약이 활성인가 아닌가”를 매 순간 판단해야 해서 본질적으로 선형 상보성 문제(LCP)가 된다. 이것이 접촉 처리가 조인트보다 훨씬 까다로운 이유다.

3. 페널티 방식 vs 라그랑주 방식[편집]

제약을 강제하는 철학은 크게 두 갈래다.

방식	원리	장점	단점
페널티(penalty)	위반량에 비례하는 스프링 힘	구현이 단순	강성 커지면 불안정, 뻣뻣함
라그랑주(Lagrange)	제약을 정확히 만족시키는 반력 계산	정확·안정	연립 문제를 풀어야 함

페널티 방식은 제약을 어긴 만큼 강한 스프링으로 되밀어주는 방식이라 직관적이지만, 스프링을 딱딱하게 만들수록 시간 적분이 불안정해지는 강성(stiffness) 문제에 시달린다.² 그래서 진지한 물리 엔진은 대부분 라그랑주 승수 기반 접근을 택한다. 제약이 정확히 지켜지도록 하는 반력(라그랑주 승수)을 직접 구하는 것이다.

4. 순차 임펄스와 PGS[편집]

문제는 라그랑주 방식으로 얻은 연립방정식(LCP)을 실시간에 정확히 푸는 것이 너무 비싸다는 점이다. 그래서 게임 물리 엔진은 반복법으로 근사한다. 그 핵심이 프로젝티드 가우스-자이델(Projected Gauss-Seidel, PGS)이다.

PGS는 모든 제약을 한꺼번에 풀지 않고, 제약을 하나씩 순서대로 풀되 방금 계산한 결과를 즉시 다음 제약 계산에 반영하는 방식이다. 이를 반복(iteration)하면 해가 점차 전체 만족 상태로 수렴한다. 여기에 부등식 제약을 위해 매 단계 값을 유효 범위로 잘라내는(projection) 연산이 붙어 “projected”라는 이름이 된다.

게임 물리의 사실상 표준인 순차 임펄스(Sequential Impulse) 방법은 이 PGS를 속도 수준에서 임펄스로 구현한 것이다. 에린 카토(Erin Catto)가 Box2D에서 대중화했으며, 각 접촉·조인트에 필요한 순간 충격량을 순차적으로 적용해 속도를 보정한다.³ 반복 횟수(보통 4~10회)를 늘리면 정확해지지만 느려지므로, 실무는 늘 이 타협의 줄타기다.

5. 위치 기반 동역학 (PBD / XPBD)[편집]

2007년 뮐러(Müller) 등이 제안한 위치 기반 동역학(Position-Based Dynamics, PBD)은 접근을 완전히 뒤집었다. 힘이나 임펄스로 속도를 고치는 대신, 물체의 위치를 직접 조작해 제약을 만족시킨 뒤 속도를 위치 변화로부터 역산하는 것이다.⁴

$$\mathbf{v}_{n+1} = \frac{\mathbf{x}_{n+1} - \mathbf{x}_n}{\Delta t}$$

PBD의 매력은 무조건적으로 안정하다는 점이다. 위치를 직접 강제하니 폭발할 일이 없다. 게임에서 천 시뮬레이션, 밧줄, 소프트바디, 심지어 유체까지 PBD로 처리하는 이유가 이것이다. 다만 순수 PBD는 강성이 반복 횟수와 타임스텝에 의존한다는 약점이 있었는데, 이를 고친 것이 XPBD(Extended PBD)다. XPBD는 컴플라이언스(compliance) 개념을 도입해 물리적으로 의미 있는 강성 계수를 타임스텝과 무관하게 지정할 수 있게 했다.

6. 안정화와 실무의 함정[편집]

반복법 제약 해결기에는 몇 가지 고질병이 있으며, 이를 다루는 노하우가 엔진 품질을 가른다.

• 관통 보정: 물체가 이미 서로 파고든 상태를 되돌릴 때, 너무 급하게 밀어내면 튕겨나간다. Baumgarte 안정화나 Split Impulse로 위치 오차를 부드럽게 보정한다.
• 적층 안정성: 상자를 여러 개 쌓으면 반복 부족으로 아래층이 짓눌려 떨리는(jitter) 현상이 생긴다. 반복 횟수 부족이 주범.
• 웜 스타팅(warm starting): 지난 프레임의 임펄스 값을 이번 프레임 초기값으로 재사용하면 수렴이 훨씬 빨라진다. 안 하면 눈에 띄게 물러진다.

이런 이유로 물리 엔진 개발자들 사이에는 “제약 해결기는 예술의 영역”이라는 말이 돈다. 이론은 LCP지만 실전은 튜닝이다.

7. 관련 문서[편집]

• 강체 동역학
• 물리 엔진
• 천 시뮬레이션
• 베를레 적분
• 선형 상보성 문제
• 충돌 감지

8. Footnotes[편집]

1. 제약이 없다면 세상 모든 물체는 자유낙하하는 점 질량일 뿐이다. 문이 경첩에 붙어 있고, 자동차 바퀴가 차축에 붙어 있고, 캐릭터의 팔이 몸통에서 떨어지지 않는 것 — 이 모든 “붙어 있음”이 제약이다. ↩

2. 페널티 스프링을 무한히 딱딱하게 만들면 이상적으로는 완벽한 제약이 되지만, 그 순간 방정식은 강성 미분방정식(stiff ODE)이 되어 명시적 적분기가 폭발한다. “딱딱하게 만들수록 정확하지만 딱딱하게 만들수록 터진다”는 딜레마. ↩

3. Catto, E. (2006). “Fast and Simple Physics using Sequential Impulses”. GDC 발표. Box2D와 이 자료는 게임 물리 입문자의 성경으로 통한다. Erin Catto라는 이름은 이 바닥에서 거의 브랜드다. ↩

4. Müller, M. et al. (2007). “Position Based Dynamics”. Journal of Visual Communication and Image Representation. NVIDIA의 FleX, Unity의 여러 소프트바디 솔루션이 이 계보에서 나왔다. “속도는 잊어라, 위치가 진리다”가 PBD의 정신. ↩