Sequential Impulse Solver

Oct. 2011 written by 이주형 (Lee Ju Hyung)

Sequential Impulse Solver 는 충돌하는 두 물체의 모든 충돌점 마다 impulse 를 반복 적용하여 충돌을 해결하는 방식이다. 누적된 impulse 는 캐싱하여 다음 프레임에도 계속 누적한다. 이렇게 누적된 impulse 는 여러 충돌점들로 인해 발생하는 진짜 impulse 에 수렴한다.

Normal Impulse

충돌점의 normal impulse 를 구해보자.

relative-velocity

운동량 보존 법칙 (conservation of momentum) 에 의해서 충돌 전의 운동량과 충돌 후의 운동량은 같고, impulse 벡터의 방향은 contact normal 이므로..

    \[\begin{aligned} m_a v_a' &= m_a v_a - j \hat{n} \\ v_a' &= v_a - \frac{j \hat{n}}{m_a} \\ m_b v_b' &= m_b v_b + j \hat{n} \\ v_b' &= v_b + \frac{j \hat{n}}{m_b} \\ \end{aligned}\]

여기서 m 은 질량, v 는 충돌 전 속도, v' 는 충돌 후 속도, j 는 normal impulse.

마찬가지로 각 운동량 (angular momentum) 에 대해서 나타내면,

    \[\begin{aligned} I_a \omega_a' &= I_a \omega_a - r_a \times j \hat{n} \\ \omega_a' &= \omega_a - I_a^{-1} (r_a \times j \hat{n}) \\ I_b \omega_b' &= I_b \omega_b + r_b \times j \hat{n} \\ \omega_b' &= \omega_b + I_b^{-1} (r_b \times j \hat{n}) \\ \end{aligned}\]

여기서 I 는 관성 모멘트, \omega 는 충돌 전 각속도, \omega' 는 충돌 후 각속도, r 은 충돌점의 질량 중심으로 부터의 거리.

충돌 후 상대 속도 (relative velocity) 벡터 \Delta v' 는 아래와 같이 나타낼 수 있다.

    \[\Delta v' = v_a' + \omega_a' \times r_a - v_b' - \omega_b' \times r_b\]

반사 속도와 입사 속도의 관계는 \Delta v' \cdot \hat{n} = -\epsilon \Delta v \cdot \hat{n} 이므로1 위의 식들을 풀어 normal impulse 를 구할 수 있다.

    \[j_n = \frac{ \Delta v \cdot \hat{n} + \epsilon \Delta \bar{v} \cdot \hat{n} }{ k_n }\]

    \[k_n = \left( \frac{1}{m_a} + \frac{1}{m_b} \right) + \left( I_a^{-1} (r_a \times \hat{n}) \times r_a + I_b^{-1} (r_b \times \hat{n}) \times r_b \right) \cdot \hat{n}\]

여기서 \epsilon 는 반발 계수 (coefficient of restitution), \Delta \bar{v} 는 초기 상대 속도 벡터.

j_n 을 두 부분으로 나누면,

    \[\begin{aligned} j_n &= j_{n}^1 + j_{n}^2 \\ j_{n}^1 &= \frac{ \Delta v \cdot \hat{n} }{ k_n } \\ j_{n}^2 &= \frac{ \epsilon \Delta \bar{v} \cdot \hat{n} } { k_n } \end{aligned}\]

j_{n}^1 은 normal 방향의 입사 속도를 0 으로 만드는 non-penetration impulse 고, j_{n}^2 은 초기 입사 속도를 기준으로 튕겨나가게 하는 restitution impulse 다. 물체끼리 더 파고드는 impulse 가 되지 않기 위해, 누적되는 impulse 가 0 이상이 되도록 j_n 을 clamp 해줘야 한다.

Frictional (Tangential) Impulse

normal impulse 는 마찰을 고려하지 않는다. 마찰을 구현하기 위해 tangential impulse 를 도입한다.

tangential impulse 는 normal impulse 와 비슷한 방법으로 구할 수 있다. 마찰로 인해 미끄러지지 않으려면 tangential velocity 가 0 이 되야 하고, 식으로 쓰면 \Delta v' \cdot \hat{t} = 0 이다. 이것을 풀어 tangential impulse 를 구할 수 있다.

    \[j_t = \frac{ \Delta v \cdot \hat{t} }{ k_t }\]

    \[k_t = \left( \frac{1}{m_a} + \frac{1}{m_b} \right) + \left( I_a^{-1} (r_a \times \hat{n}) \times r_a + I_b^{-1} (r_b \times \hat{n}) \times r_b \right) \cdot \hat{t}\]

쿨롱 마찰력 법칙2 에 의해서 누적되는 tangential impulse 의 최대 크기는 \mu j_n 로 제한해야 한다. 여기서 \mu 는 마찰 계수 (frictional coefficient)

Correction Impulse

충돌 후 normal impulse 는 더 이상 파고들지 못하게 하고, 추가적으로 튕겨나가는 속도를 더해주지만 penetration 은 해결하지 못한다. penetration 을 해결하기 위한 한가지 방법은 correction impulse 를 도입하는 것이다.

    \[j_c = \frac{\delta}{\Delta t} \frac{1}{k_n}\]

여기서 \delta 는 penetration depth.

한꺼번에 j_c 를 적용하면 jittering 이 생길 수 있으므로, 파고드는 걸 허용하고 조금씩 밀어내기 위해 몇가지 tweak 을 한다.3

    \[j_c = \beta \, max \left( \frac{\delta - \delta_{bias}}{\Delta t}, 0 \right) \frac{1}{k_n}\]

여기서 \beta 는 correction coefficient, \delta_{bias} 는 penetration allowing bias.

물체끼리 더 파고드는 impulse 가 되지 않기 위해, 누적되는 correction impulse 가 0 이상이 되도록 j_c 를 clamp 해준다.

물체가 빠른 속도로 움직일 경우엔 penetration 이 더 심해진다. penetration 이 심할 수록 correction 이 어색하게 동작할 수 있다. 이럴 땐 CCD (Continuous Collision Detection) 를 적용하는 방법이 있다.

penetration

위 그림은 원이 빠른 속도로 움직여 상자와 충돌하여 튕겨나오는 상황을 step 별로 나타낸 것이다. 빨간색 원은 correction 으로 처리하는 과정을 나타낸다. step 2 에서 파고들었고, step 3 에서 파고든걸 밀어내고 튕겨나왔다. (사실 조금씩 correction 하는 구조이므로 그림처럼 다 밀어내지도 못한다.) 반면 녹색 원은 CCD 를 적용하여 step 2 에서 time of impact 를 구해서 정상적으로 튕겨냈다.

References

1. Essential Mathematics For Games & Interactive Applications 2nd Edition
Chapter 13 – Rigid Body Dynamics
James M. Van Verth & Lars M. Bishop
http://www.essentialmath.com/book.htm

2. Fast and Simple Physics using Sequential Impulses
Erin Catto

  1. 이 식은 입사속도와 반사속도에 대한 제한조건식 (constraint equation) 이다.
    C = \Delta v' \cdot \hat{n} + \epsilon \Delta v \cdot \hat{n} = 0
  2. 쿨롱 마찰력 법칙: 마찰력은 접촉 면적과 상관없이 수직 항력 (normal force) 에 비례한다는 법칙. 여기서는 수직 항력의 힘 대신 normal impulse 를 적용.
  3. 파고드는 걸 허용하기 때문에 물리적으로 정확하진 않지만, 안정적인 시뮬레이션을 위해 적당히 조절한다. Fast and Simple Physics using Sequential Impulses – Erin Catto 문서 참고.

Leave a Reply

Your email address will not be published. Required fields are marked *