chan blog: Erin Catto – Fast and Simple Physics using Sequential Impulses

https://box2d.org/downloads/

Erin Catto – Fast and Simple Physics using Sequential Impulses

* Physics Engine Checklist
- Collision and Contact
- Friction : static and dynamic
- Stacking
- Joints
- Fast, simple, and robust

* Fast and Simple Physics
Impulse - answer
Penalty method, Linear complementarity(LCP), - no
Joint Coordinates(Featherstone), Particles(Jakobsen) - no

* Why Impulse?
- 대부분의 사람들은 impulse 싫어하지 않음
- 그 수학은 거의 이해가능 함
- 직관력이 종종 작동함
- Impulses는 robust할 수 있다.

* Making impulses not Suck
- Impulses는 물건들이 bounce하게 만드는데 잘한다.
- impulses를 사용하는 많은 시도들은 bouncy simulations(jitter라고 하는)을 이끈다.
- static friction을 잊고
- stacking을 잊어라.

* Impulses without the Bounce
- 잠시동안 bounces를 잊어라.
- 상황을 정지시키는 것에 집중하자.
- 그 bounce에 뒤에 더하는 것이 항상 쉽다.

* The 5 Step Program (for taking the jitter out of impulses)
- Accept penetration
- Remeber the past
- Apply impulses early and often
- Pursue the true impulse
- update position last

* Penetration
- Performance
- Simplicity
- Coherence
- Game logic
- Fewer cracks

* Algorithm Overview
- contact points 연산
- forces(gravity) 적용
- impulses 적용
- position 업데이트
- Loop

* Contact Points
- Position, normal, and penetration
- Box-box using the SAT
- Find the axis of minimum penetration
- Find the incident face on the other box
- Clip

* Box-Box SAT
- 처음에 minimum penetration이 있는 separating 축을 찾아라.
- 2D에서 그 separating axis는 face normal이다.

* Box-Box Clipping Setup
- reference face를 확인해라
- incident face를 확인해라.

* Box-Box Clipping
- reference face side planes에 대해 (그러나 reference face가 아닌) incident face를 clip해라
- 양수의 penetration을 가진 clip points를 고려해라.

* Feature Filp-Flop
- 어떤 normal이 separating axis인가?
- 다른 것에 대해 한 축을 선호하는 가중치를 적용해라
- 개선된 coherence

* Apply Forces
- Newton법칙 -> 개선된 안정성을 위해 회전에 대한 항을 무시해라
- Euler 법칙을 사용해라
$\textbf{v}_2 = \textbf{v}_1 + \Delta t m^{-1}\textbf{F} \\ \textbf{w}_2 = \textbf{w}_1 + \Delta t m^{-1}\textbf{T} \\$

* Impulses
- Impulses는 각 contact point에 적용된다.
- Normal impulses는 penetration을 방지한다.
- Tangent impulses는 마찰을 부과한다.
$P_n \geq 0 \\ |P_t| <= \mu P_n$

* Computing the impulse

* Linear Momentum
- 그 normal impulse는 속도에서 끊임없는 변화를 발생시킨다
- 우리는 normal impulse의 방향을 안다. 우리는 오직 그것의 크기만 필요하다

* Relative Velocity
$\Delta \textbf{v} = \textbf{v}_2 + \textbf{w}_r \times \textbf{r}_2 - \textbf{v}_1 - \textbf{w}_1 \times \textbf{r }_1$
- Normal을 따라서 :
$v_n = \Delta \textbf{v} \cdot \textbf{n}$

* The Normal Impulse
- 원하는 것 v_n = 0, P_n >= 0
- 얻는 것
$P_n = max\bigl(\begin{smallmatrix} \frac{-\Delta \bar{\textbf{v}} \cdot \textbf{n}}{k_n}, 0 \end{smallmatrix}\bigr)$

- 세세한 항목
$\Delta \textbf{v} = \textbf{v}_2 + \textbf{w}_r \times \textbf{r}_2 - \textbf{v}_1 - \textbf{w}_1 \times \textbf{r }_1$
$k_n = \frac{1}{m_1} + \frac{1}{m_2} + [\textbf{I}^{-1}_1 (\textbf{r}_1 \times \textbf{n}) \times \textbf{r}_1 + \textbf{I}^{-1}_2 (\textbf{r}_2 \times \textbf{n}) \times \textbf{r}_2] \cdot \textbf{n}$

* Bias Impulse
- normal impulse에 몇 가지 추가 값을 주어라.
- penetration에 비례해서
- 어떤 slop을 허용해라.
- Be gentle?

* Bias Velocity
- Slop : &_slop
- Bias Factor :
$\beta \approx [0.1, 0.3]$
- Bias Velocity:
$\textbf{v}_{bias} = \frac{\beta}{\Delta t} max(0, \delta - \delta_{slop})$

* Bias Impulse
- with bias velocity, this:
$P_n = max\bigl(\begin{smallmatrix} \frac{-\Delta \bar{\textbf{v}} \cdot \textbf{n}}{k_n}, 0 \end{smallmatrix}\bigr)$
- becomes:
$P_n = max(\frac{-\Delta \bar{\textbf{v}} \cdot \textbf{n} + \textbf{v}_{bias}}{k_n}, 0)$

* Friction Impulse
- Tangent Velocity:
$v_t = \Delta \textbf{v} \cdot \textbf{t}$
- Want :
$v_t = 0 \;\;\;\;\; -\mu P_n \leq P_t \leq \mu P_n$
- Get :
$P_t = clamp(\frac{- \Delta \bar{\textbf{v}} \cdot t}{k_t}, -\mu P_n, \mu P_n)$
- Fine Print:
$k_t = \frac{1}{m_1} + \frac{1}{m_2} + [I^{-1}_1 (\textbf{r}_1 \times \textbf{t}) \times \textbf{r}_1 + I^{-1}_2 (\textbf{r}_2 \times \textbf{t}) \times \textbf{r}_2] \cdot \textbf{t}$

* Sequential Impulses
- 각 contact point에 한 impulse 적용
- 몇 번의 반복에 대해 impulse를 계속해서 적용
- 다음 후에 종료 :
- fixed number of iterations
- impulses가 작아지고 나서

* Naive Impulses
- 각 impulse는 별개로 연산되고, 이것은 jitter를 만들게 된다.

* Where Did We Go Wrong?
- 각 contact point는 그것의 impulse history를 잊는다.
- 각 contact point는 모든 impulse가 positive여야 하는 것을 요구한다.
- 나쁜 impulse로 부터 회복할 방법이 없다.

* Accumulated Impulses
- 각 impulse는 total에 더해진다. Increments는 음수가 될 수 있다.

* The True Impulse
- 각 impulse는 각 contact point에 대해 accumulated impulse에 더한다.
- 그 accumulated impulse는 true impulse에 접근한다 (바라건데).
- True Impulse : 정확한 global solution

* Accumulated Impulse
- Clamp the accumulated impulse, not the incremental impulses

Accumulated impulses:
$P_{\sum n} \;\;\;\;\; P_{\sum t}$

* Correct Clamping
- Normal Clamping :
$temp = P_{\sum n} \\ P_{\sum n} = max(P_{\sum n} + P_n, 0) \\ P_n = P_{\sum n} - temp$

- Friction Clamping:
$temp = P_{\sum t} \\ P_{\sum t} = max(P_{\sum t} + P_t, -\mu P_{\sum n}, \mu P_{\sum n}) \\ P_t = P_{\sum t} - temp$

* Position Update
- positions을 integrate하기 위해 새로운 velocities 사용
- time step은 complete

* Extras
- Coherence
- Feature-based Ccontact points
- Joints
- Engine Layout
- Loose Ends
- 3D Issues

* Coherence
- step의 초기에 old accumulated impulses를 적용
- less iterations and greater stability.
- old and new contacts를 매치시킬 방법 필요

* Feature-Based Contact Points
- 각 contact point는 clipping의 결과이다.
- 그것은 두 다른 edges의 연결이다.
- 한 edge는 둘 중 하나의 box로부터 온다.
- 두 edge numbers를 각 contact point와 함께 저장 - 이것이 Contact ID

* Joints
- 움직임의 (constraint) part를 명시
- 그 제약을 달성하는데 필요한 impulse 연산
- true impulse를 추구하기 위해 accumulator 사용
- separation을 방지하는 Bias impulse

* Revolute Joint
- 두 bodies는 common point를 공유
- 그것들은 그 점에 대해 자유롭게 회전
- 그 joint는 두 bodies에 대해 local anchor point를 안다.

* Relative Velocity
- 그 anchor points의 relative velocity는 0이다.
$\Delta \textbf{v} = \textbf{v}_2 + \textbf{w}_2 \times \textbf{r}_2 - \textbf{v}_1 - \textbf{w}_1 \times \textbf{r}_1$
- 한 impulse는 그 두 bodies에 적용된다.

* Linear Momentum
- 다음을 얻기 위해 relative velocity에 linear momentum을 적용
$K \textbf{P} = - \Delta \bar {\textbf{v}}$
- Fine Print
$K = (\frac{1}{m_1} + \frac{1}{m_2})1 - \tilde{\textbf{r}_1}\textbf{I}^{-1}_1 \tilde{\textbf{r}_1} - \tilde{\textbf{r}_2}I^{-2}_2 \tilde{\textbf{r}_2}$
- Tilde(~)는 cross-product matrix를 나타냄.

* K Matrix
- 2D에서 2-by-2 matrix, 3D에서 3-by-3.
- Symmetric positive definite
- K를 constraint의 inverse mass matrix라고 생각해라
$M_c = K^{-1}$

* Bias impulse
- error는 anchor points 사이의 separation
$\Delta \textbf{p} = \textbf{x}_2 + \textbf{r}_2 - \textbf{x}_1 - \textbf{r}_1$
- Center of mass : x
- Bias velocity and impulse:
$\textbf{v}_{bias} = - \frac{\beta}{\Delta t}\Delta \textbf{p}$
$K \textbf{P} = -\Delta \bar{\textbf{v}} + \textbf{v}_{bias}$

* Engine Layout
- 그 World class는 모든 bodies와 contacts, joints를 포함
- Contacts는 Arbiter class에 의해 유지된다.

* Arbiter
- 한 arbiter는 모든 boxes의 touching pair에 대해 존재한다.
- coherence를 제공한다.
- Contact ID를 사용하여 new and old contact points를 매치시킨다.
- accumulated impulses를 유지

* Collision Coherence
- separating axis를 저장하는 arbiter를 사용
- 메모리 사용하여 성능 개선
- broad-phase와 사용

* More on Arbiters
- Arbiters는 ordered body pointers를 따라서 한 집합에 저장된다.
- 오래된 arbiters를 제거하기 위해 time-stamping 사용
- Joints는 permanent arbiters
- Arbiters는 game logic을 위해 사용될 수 있다.

* Loose Ends
- Ground는 inverse mass가 zero인 bodies로 나타내진다.
- Contact mass는 pre-step으로서 연산될 수 있다.
- Bias impulses는 그 velocity state에 영향을 미쳐서는 안된다 (TODO).

* 3D Issues
- 마찰은 두 개의 축을 요구
- 만약 그것이 non-zero라면 그 축들을 velocity와 정렬
- contact patch (manifold)를 확인하고, 그 center에 friction 적용
- 이것은 twist friction 요구
- 큰 CPU 절감

chan blog

Post Lists

2019년 1월 13일 일요일

Erin Catto – Fast and Simple Physics using Sequential Impulses

댓글 없음:

댓글 쓰기