물리 시뮬레이션 (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) 으로 가속.

시각화

핵심 아이디어

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 낙하 + 바닥 충돌, 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 로 충돌 검사 가속.

함정

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

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

2. 부동소수점 오차 누적

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

3. 충돌 반응 후 중복 충돌

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

BOJ 연습 문제

참고

• 시뮬레이션
• 스위핑