물리 시뮬레이션 (Physics Simulation)

정의

물리 시뮬레이션 (Physics Simulation) 은 뉴턴 역학의 운동 방정식 (F=ma, 속도, 가속도) 을 수치적으로 적분하여 시간 경과에 따른 물체의 위치와 속도를 계산하는 기법. 게임 엔진, 로봇 공학, 과학 계산에서 실제 물리 현상을 모의하는 데 사용.

문제 상황과 동기

N 개의 물체가 있고, 각 물체는 위치, 속도, 가속도를 가진다. 매 시간 단계마다 힘을 받아 가속도가 결정되고, 속도와 위치가 갱신된다. 추가로 물체 간 충돌을 감지하고 반응해야 한다.

• naive: 매 시간 단계마다 모든 물체 쌍을 확인. O(N^2) 충돌 검사. N=1000 이면 10^6 번 거리 계산, 초당 60 프레임이면 6·10^7 연산. 느림.
• 핵심 통찰: 시간을 작은 dt 로 이산화하고, 각 단계에서 상태 (위치, 속도) 를 갱신. 공간 분할 (grid, quadtree) 로 충돌 검사를 O(N log N) 으로 가속.

시각화

시뮬레이션 루프 흐름

flowchart TD
    A["초기화: 위치 p, 속도 v, 질량 m"] --> B[시뮬레이션 루프]
    B --> C["힘 계산: 중력 + 외부힘"]
    C --> D["가속도 a = F / m"]
    D --> E["속도 갱신: v += a * dt"]
    E --> F["위치 갱신: p += v * dt"]
    F --> G{"충돌 감지"}
    G -->|충돌 있음| H[충돌 반응 처리]
    H --> I{"종료 조건 도달"}
    G -->|충돌 없음| I
    I -->|계속| B
    I -->|종료| J[결과 반환]

핵심 아이디어

Euler 적분: 현재 상태 (위치 p, 속도 v) 에서 다음 상태로 진행.

a = F / m                    (뉴턴 제2법칙)
v_new = v + a * dt           (속도 갱신)
p_new = p + v_new * dt       (위치 갱신)

Verlet 적분: 속도를 명시적으로 저장하지 않고, 이전 위치를 기억. 스프링이나 천 시뮬레이션에서 더 안정적.

p_new = 2 * p - p_old + a * dt^2

충돌 감지: 원형 물체는 거리 비교. 축 정렬 경계 상자 (AABB) 는 각 축 범위 겹침 확인.

충돌 반응: 운동량 보존. 두 물체가 충돌하면 속도를 교환하거나, 반발 계수 (restitution) 를 곱해 에너지 손실 표현.

알고리즘

simulate(bodies, forces, dt, gravity):
    for each body in bodies:
        a = (forces[body] + gravity) / mass[body]
        v[body] += a * dt
        p[body] += v[body] * dt
    
    for i = 0 to N-1:
        for j = i+1 to N-1:
            if collides(bodies[i], bodies[j]):
                resolve_collision(bodies[i], bodies[j])

탄성 충돌 반응 공식

1D 탄성 충돌에서 운동량과 에너지 보존:

m1, m2: 충돌하는 두 물체의 질량
v1, v2: 충돌 전 속도

v1' = (m1 - m2) / (m1 + m2) * v1 + 2*m2 / (m1 + m2) * v2
v2' = 2*m1 / (m1 + m2) * v1 + (m2 - m1) / (m1 + m2) * v2

비탄성 충돌은 반발 계수 e 도입:

v_rel' = -e * v_rel    (e=1: 완전 탄성, e=0: 완전 비탄성)

적분 방법 비교

구현

// 1D 낙하 + 바닥 충돌, Euler 적분
#include <bits/stdc++.h>
using namespace std;
int main() {
  double y = 300, v = 0, g = -9.8, dt = 0.1;
  double ground = 400, restitution = 0.8;
  int steps = 50;
  
  for (int i = 0; i < steps; i++) {
      v += g * dt;
      y += v * dt;
      
      if (y >= ground) {
          y = ground;
          v = -v * restitution;
      }
      
      cout << fixed << setprecision(2) << "t=" << i*dt 
           << " y=" << y << " v=" << v << "\n";
  }
  return 0;
}

# 1D 낙하 + 바닥 충돌, Euler 적분
y, v = 300, 0
g, dt = -9.8, 0.1
ground, restitution = 400, 0.8
steps = 50
​
for i in range(steps):
  v += g * dt
  y += v * dt
  
  if y >= ground:
      y = ground
      v = -v * restitution
  
  print(f"t={i*dt:.1f} y={y:.2f} v={v:.2f}")

// 1D 낙하 + 바닥 충돌, Euler 적분
public class Physics {
  public static void main(String[] args) {
      double y = 300, v = 0, g = -9.8, dt = 0.1;
      double ground = 400, restitution = 0.8;
      int steps = 50;
      
      for (int i = 0; i < steps; i++) {
          v += g * dt;
          y += v * dt;
          
          if (y >= ground) {
              y = ground;
              v = -v * restitution;
          }
          
          System.out.printf("t=%.1f y=%.2f v=%.2f%n", 
              i*dt, y, v);
      }
  }
}

초기: y=300, v=0, g=-9.8, dt=0.1, restitution=0.8

t=0.0 y=300.00 v=0.00
t=0.1 y=299.95 v=-0.98
t=0.2 y=299.80 v=-1.96
t=0.3 y=299.55 v=-2.94
t=0.4 y=299.21 v=-3.92

복잡도

변형 / 활용

• Verlet 적분: 속도 명시 저장 없음. 천, 스프링 시뮬레이션에 안정적.
• RK4 (Runge-Kutta 4차): 더 높은 정확도. 계산 비용 4배.
• Impulse-based 충돌: 운동량 보존으로 정확한 반응.
• Penalty method: 침투 깊이에 비례한 복원력. 간단하지만 부정확.
• Spatial partitioning: Grid, Quadtree, BVH 로 충돌 검사 가속.

공간 분할 전략

충돌 검사를 O(N²) 에서 줄이는 세 가지 주요 방법:

flowchart LR
    A["N 개 물체"] --> B{"공간 분할 방법"}
    B -->|정적 그리드| C["O(N) 구축 / O(1) 셀 조회"]
    B -->|Quadtree| D["O(N log N) 구축 / 밀도 적응"]
    B -->|BVH| E["O(N log N) 구축 / 계층적 구조"]
    C --> F[후보 쌍만 정밀 검사]
    D --> F
    E --> F
    F --> G["전체 O(N log N) 수렴"]

• 정적 그리드: 물체 크기가 균일할 때 최고. 셀 크기 = 물체 최대 반지름 * 2.
• Quadtree: 밀도 불균형 분포에 유리. 군집 + 희소 혼재 시나리오.
• BVH: 게임 엔진 표준. 동적 물체와 복잡한 형상에 강함.

함정

1. dt 너무 크면 불안정 (tunneling)

dt 가 크면 물체가 한 프레임에 벽을 뚫고 지나갈 수 있다. 연속 충돌 감지 (CCD) 필요.

2. 부동소수점 오차 누적

오래 시뮬레이션하면 위치 오차가 누적. 주기적으로 정규화 필요.

3. 충돌 반응 후 중복 충돌

물체가 벽에 박혀 있으면 매 프레임 충돌 감지. 충돌 상태 플래그 필요.

4. 적분 방법 선택 오류

RK4 가 항상 더 좋다는 오해. dt 가 작으면 Euler 와 큰 차이 없고, 4배 연산 낭비. 목적에 맞는 방법 선택 필요.

5. 동시 다중 충돌 순서 문제

N 개 물체가 동시에 충돌할 때 처리 순서가 결과를 바꿈. impulse accumulation 방식으로 한 프레임의 모든 충돌을 모아서 한 번에 처리.

BOJ 연습 문제

참고

• 시뮬레이션
• 스위핑
• 기하 알고리즘
• 너비 우선 탐색 (격자 시뮬레이션)