- 우리는 정확히 constraints를 해결한 충분한 cycles를 갖지 않는다. constraints를 정확히 푸는 것은 cubic time과 quadratic space를 요구한다. 겡미에 대해서, 우리는 linear time과 space의 제한을 둔다. 그래서 우리는 끊임없이 우리의 solvers와 씨름한다. 너가 constraint solver에 대해 더 잘 이해할수록, 너의 게임에서 튼튼한 시뮬레이션을 만들 더 좋은 기회를 가지게 될 것이다.
- 너는 ragdolls와 destruction을 만들기위해 표준 constraints와 solvers를 사용할 수 있다. 만약 너가 너 깊게 공부한다면, 너는 motorized ragdolls과 soft constraints를 만들 수 있다. 그러나 너는 심지어 더 갈 수 있다: 너는 block solvers, position solvers, character solvers를 만들 수 있다.
- 2005년 이후로 나는 GDC에서 constraints에 대해서 말해왔다. 그래서 나는 너가 constraints와 그것들의 재료와 친숙하기를 바란다. 그럼에도 불구하고, 나는 조금의 리뷰를 할 것이다. 모든 것은 position constraint function과 시작한다. skateboarder가 이 half-pipe에 타고있는 것을 상상해라. 그 스케이트 보드는 그 ramp의 surface에 제한되어있찌만, 그것은 그 surface를 따라 자유롭게 움직일 수 있따. 이것이 position constraint이다.
- ramp의 바닥에 대해 position constraint C를 구성하자.
간단함을 위해, 그 스케이트보드가 위치 p에서의 파티클이라고 고려하자. 그 position constraint C는 p의 scalar function이다. 그 constraint가 만족될 때, 그것은 zero와 동일해야만 한다. 그렇지 않다면 그것은 0이 아니여야 한다. 그 ramp의 bottom은 평평하다. 그래서 나는 C를 평면으로부터의 파티클의 양의 거리로 정의했다. p가 평면 위에 있다면, C는 양수이고, 평면의 아래에 있다면 음수이다.
- position constraint는 ramp의 곡선 부분에 다른 형태를 가진다. 이제 그 점 p는 p0에 중심을 둔 원에 제한된다. 그래서 나는 C가 p0에서 p의 거리에 반지름 r를 뺀 것으로 정의했다. 대부분의 경우에, C는 implicit surface라고 생각하는 것은 유용하다. 이 경우에, C는 한 원의 implicit representation이다.
- 이제 게임 물리 어디에서나 존재한느 constraint를 봐보자: the contact constraint. 나는 고정된 평면 A 위에 box B를 가진다. 나는 그 contact constraint를 lower left corner에 대해 만들 것이다. 그 contact constraint는 닿고있는 bodies에서 contact points가 서로를 기준으로 contact normal vector n을 따라 움직이지 않는다고 말한다. 이제, 나는 이것을 bilateral constraint로 다룰 것이다. 나중에 나는 inequality constraints에 대해 이야기 할 것이다.
- 그래서 우리는 position constraint를 가지지만, 너가 보게 되듯이, 나는 또한 solver에 대해 velocity constraint가 필요하다. 나는 velocity constraint를 얻기위해 position constraint의 시간 미분을 연산한다. 미분의 연쇄법칙은 두 개의 항을 만들어낸다. 한 변수위의 점은 시간에 대한 미분을 나타낸다.
- 나는 이제 두 가지 것을 간단하게 할 수 있다. body A가 ground라고 가정하자. 그러고나서 A의 속도는 0이다. 나는 또한 pA와 pB가 일치하기 때문에 두 번째 항을 없앨 수 있다.
- 그 solver는 center of mass velocity를 다룬다. 그러므로, 나는 그 contact velocity constraint를 center of mass velocity c의 관점에서 표현할 필요가 있다. 나는 angular velocity omega와 그 반지름 벡터 r를 사용하는 이 표준 공식을 사용하여 center of mass velocity의 관점에서 그 contact point의 velocity를 표현할 수 있다.
- Constraint impulse
linear impulse
Angular impulse
이제 나는 contact velocity constraint를 가졌다. 그리고 나는 velocity constraint가 만족되도록 하는 방법이 필요하다. 그 solver는 velocity constraints가 만족되도록 velocities를 조정하는 impulses를 적용하여 작동한다. 그래서 그 contact impulse를 설정하자. 그래서 우리는 그것을 solver에 줄 수 있다.
그 contact impulse는 contact point p에서 contact normal을 따라 적ㅇ요된다. 그 impulse의 signed magnitude가 lambda이다.
나는 velocity constraint가 만족되도록 lambda에 대한 값을 연산할 필요가 있다. 이것은 그 박스가 바닥에 가라앉는 것을 막는데 도움 줄 것이다.
그 contact impulse는 center of mass와 일렬로 세워지지 않는다. 그래서 그 박스는 linear impulse와 angular impulse를 겪는다.
- Solving the constraint
Newton's Law : impulse form
Velocity Constraint(즉 v2와 w2에서의(다음 프레임) constraint가 0이 되어야 한다)
질문은 이제 어떻게 그 velocity constraint가 만족되도록 lambda 값을 연산하느냐이다.
나는 lambda에 대해 푸기위해 Newton의 운동법칙을 사용할 필요가 있다. 첫 번째 방정식은 linear velocity에서의 변화를 impulse와 관련시킨 것이다. 그 두 번째 방정식은 inertia tensor와 angular velocity의 변화와 관련된 움직임의 angular equation이다. 세 번째 방정식은 v2와 omega2 관점에서 velocity constraint이다.
- Solution by substitution
From Newton:
Substitute into velocity constraint
이전 슬라이드의 방정식들으 사용해서, v2와 omega2에대해 lambda에 대해 풀자. 다음으로, 나는 v2와 omega2를 세 번째 방정식에서 제거할 수 있다. 이것은 lambda가 유일한 미지수인 방정식을 만든다. 그래서 나는 lambda에 대해 풀 수 있다.
- Impulse formula and effective mass
impulse = mass * velocity
effective mass
나는 이제 초기 velocity constraint error와 effective mass라고 불리는 새로운 용어의 그룹의 관점에서 lambda를 연산하는공식을 가진다. 그 effective mass는 constraint axis에 사영된 inertia이고, constraint impulse에 의해 보여지는 inertial resistance를 나타낸다. effective mass는 단위 질량을 갖는다는 것을 주의해라. (Chris Hecker Article 참조하면 이해 됌)
- Global solvers vs local solvers
그래서 이제 우리는 어떻게 단일의 constraint를 해결할지를 안다. 많은 constraints는 어떤가? 많은 constraints를 푸는 것은 어렵다. 왜냐하면 한 constraint effect에 적용된 impulses가 다른 constraints에 에러를 미치기 때문이다. constraints는 globally하게 일관되어야 한다. 그러나, global solution을 연산하는 것은 한 행렬을 구성하고 그것을 factoring하는 것을 요구한다. 만약 100개의 constraint가 있다면, 너는 100x100 행렬을 구성해서 factor해야한다. 이것은 대부분의 게임에 대해 너무 느릴 것이다.
그러므로 많은 물리 프로그래머들은 local solvers를 사용한다. local solvers는 한 번에 한 constraint를 푸는데, global solution이 주어진 충분한 횟수로 converge할 것이라는 희망을 갖고있다.
Iterative solvers는 linear space와 time을 쓴다. 그래서 그것들은 게임에 유용하다. 그러나, 우리는 종종 그 solver에게 수렴할(정답에) 충분한 횟수를 주지 못한다. 우리는 10개 또는 그 이하로 반복횟수를 허용한다. 이것은 종종 우리에게 낮은 정확성의 솔루션을 준다.
우리는 종종 더 좋은 결과를 얻기위해 global and local solvers를 섞는다. 나는 이것에 대해 block solvers의 맥락에서 나중에 이야기할 것이다.
- Sequential Impulses local solver
나는 Sequential Impulses라고 불리는 local solver를 사용한다. 여기에 그 Sequential Impulses가 어떻게 작동하는지에 대한 예시가 있다. 우리가 모두 쉬고있는 circles의 한 스택을 가지고 있다고 가정하자. Gravity는 그 circles을 아래로 누르고 있지만, 그 stack은 ground plane에 의해 막혀있다. 그래서 우리는 gravity를 상쇄하는 contact impulse를 연산할 필요가 있다.
그 time step의 초기에, 나는 gravity를 적용하고, 각 circle은 같은 속도를 가지고 아래로 움직이기 시작한다.
- Iteration 1
각 contact impulse는 (dashed line으로 표기된) 위의 circles의 무게를 지지할만큼 충분히 클 필요가 있다.
그 SI algorithm은 임의의 순서로 한 번에 한 consraint를 해결한다. 한 iteration후에, 그 contact impulses는 중대하 ㄴ에러가 있다. 나는 그 impulses를 해결하기 위해 계속해서 반복한다.
- Low Accuracy leads to overlap
내가 impulse가 수렴하기전에 반복을 끝냈다고 가정하자. 이것은 그 circles들이 서로에 대해 여전히 움직이고 있고, ground plane으로도 움직이고 있다는 것을 가정하자. 이것은 내가 positions을 업데이트하 눟에 중첩을 만들어낸다.
- Understanding convergence
우리는 게임 물리를 위해 iterative solvers를 사용하는 경향이 있기 때문에, 우리는 convergence를 이해할 필요가 있다. 나는 보통 convergence를 multiplicative decay와 연관짓는다. 각 iteration마다, 그 solver는 어떤 fraction alpha로 에러를 줄인다. convergence는 어떤 경우에 (작은 알파) 빠를지도 모르고, 다른 경우에 (큰 알파) 느릴지도 모른다. 물리 프로그래머로서, 우리는 large alpha case들을 찾을 필요가 있다.
- Circle stack : single circle
나는 circles를 쌓아서 convergence를 알아볼 것이다. Circle stacks이 좋은데 왜냐하면 그것들은 그 문제를 1차원으로 줄이기 때문이다.
단일 single circle로 우리는 오직 한 번의 반복만이 필요하다. 왜냐하면 어떠한 경쟁하는 constraints가 없기 때문이다.
- Circle stack : two circles
두 circles에 대한 convergence를 봐보자. 나는 circles의 vertical stack에 SI algorithm을 작동시키는 Matlab script를 만들었다. 너는 이 script를 box2d.org로부터 다운받을 수 있고, 너는 그것을 무료 소프트웨어 Octave에서 실행시킬 수 있다.
이 경우에 그 script는 SI가 95% 정확도를 얻기위해 5번의 반복이 필요하다고 보여준다. 나쁘지 않다.
- Circle stack : light on heavy
Convergence는 circles의 상대적인 질량에 의존한다. 1kg circle위에 0.5kg circle를 고려해라.
Convergence 는 더 나아진다! SI는 오직 95%의 정확도로 3번의 반복만이 필요하다.
- Circle stack : heavy on light
만약 그 이전 slide가 너에게 희망을 주었다면, 현재의 것은 너를 슬프게 만들 것이다. 만약 내가 0.5kg circle위에 1kg circle을 쌓는다면, convergence는 더욱 악화된다. 이제 너는 내가 SI가 왜 별로라고 말했는지를 알게된다. 그것의 convergence가 정말 나빠지는 시나리오가 있다.
- Circle stack : very heavy on light
10:1의 질량 비율에 대해, 나는 95% convergence를 위해 50번의 iterations가 필요하다.
- Iterations grow linearly with mass ratio
그래서 어떻게 convergence가 mass ratio와 변하는가? 나는 많은 질량 비율에 대해 95%의 convergence를 얻는데 필요한 iterations의 횟수를 연산한 많은 시뮬레이션을 돌렸다. 그 결과는 linear graph이다!
나는 데이터에 대해 선형 회귀를 돌렸고, 놀랍게도 간단한 결과를 발견했다: 필요한 반복의 횟수는 3 * 질량비율 + 2이다. 그래서 어떤 경우에 필요한 최소 횟수는 2이다. 만약 너가 mass ratio를 둡 ㅐ 한다면, 너는 대강 반복 횟수를 두배 할 것이다.
- Why is convergence slow?
왜 어떤 경우들에서 convergence에서 느리고, 다른 경우에서 빠른가?
light case에 대한 무거운것을 자세히 봐보자. upper contact point의 정확한 부하는 큰 circle의 무게이다. 더 아래에 있는 contact point의 정확한 부하는 두 circles의 결합된 무게이다. 만약 우리가 큰 circle를 제거한다면, 그 lower contact point에서의 부하는 작은 circle의 무게이다. 이것은 더 낮은 부하이다.
그러나 그 더 낮은 부하는 그 더 아래에 있는 contact point가 기대하는 것이다. 그 lower contact point는 위에 있는 큰 circle에 대해서 모른다.
초기에 두 circles들은 중력아래에서 같은 속도로 내려간다. 반복마다, 내가 더 아래에 있는 contact를 처음에 해결하고 그러고나서 위에 있는 contact를 두 번째로 해결한다고 가정하자. 내가 그 lower contact를 해결할 때, 나는 작은 circle의 움직임을 막을 작은 impulse를 연산한다.
그러고나서 나는 upper contact를 푼다. 그 큰 circle은 작은 circle이 가졌던 중력에 의해 같은 아래로 가는 velocity를 가진다. 또한, 그 upper contact는 그 small circle이 ground plane에 제한되어있는지를 모른다. 그래서 내가 그 upper contact를 풀 때, 그 small circle은 아래로 가는 속도를 받고, 그 large circle은 조금 느려진다.
- Tall stacks are challenging too
만약 single circle이 한 번의 iteration을 요구한다면, 두 개의 circles들은 5번의 iterations을 요구한다. 그러면 네 개의 circles에 대해 우리는 얼마나 많은 반복이 필요한느가? 이 그래프에 따르면, 95%의 정확도를 얻기 위해 나는 20번의 반복이 필요하다.
그것은 각 circle의 무게가 그 stack에 전파되도록 하기 위해 더 많은 반복이 필요하다.
- Warm starting can boost convergence
지금까지, 상황은 local solver에게 좋아보이지 않는다. 그러나, 희망이 있다. 우리는 한 프레임을 고립하여 해결하지 않는다. 우리는 일반적으로 프레임마다 어떤 coherence(일관성)을 가진다. 우리는 그 솔루션을 개선시키기위해 이것을 이용할 수 있다. 아이디어는 우리가 몇 가지 time steps 동안 convergence에 필요한 많은 iterations을 분배할 수 있다는 것이다. 이것을 하기 위해서, 우리는 warm starting이라고 불리는 기법을 사용할 필요가 있다.
- Warm starting requires us to accumulate impulses
우리가 SI를 반복시킬 때, 우리는 축적된 frame impulse에 더하는 많은 작은 impulses를 적용한다. 우리는 이 축적된 impulse를 보존할 수 있고, warm starting을 위해 사용할 수 있다.
time step의 끝에서 각 constraint에 대해 축적된 impulse를 가지고 있기 때문에, 우리는 다음 time step에 SI를 초기화하기 위해 이것을 사용할 수 있다. 처음에 우리는 이전 TIME STEP으로부터 축적된 impulse를 적용한다. 그러고나서 우리는 그 solution을 개선시키기 위해 증가하는 impulses를 적용하기 시작한다.
- Warm starting doesn't react well to quick load changes
전반적으로 warm starting은 convergence를 개선한다. 그러나, 그것은 부작용을 가진다. 만약 큰 부하가 적용된다면, 축적된 impulse는 큰 값으로 축적될 것이다. 그 부하가 갑자기 제거된다면, 축적된 impulse를 충분히 제거할 single time step에서의 충분한 반복이 없을지도 모른다. 이 경우에, 영향을 받는 rigid bodies는 bounce할지도 모른다
- Understanding inequality constraints
Inequality constraints같은 contacts들은 특별한 처리를 요구한다. 이 경우에, 그 constraint는 밀어낼 수 있지만, 잡아당길 수 없다. SI의 맥락에서, inequality constraints를 처리하는 것은 어렵지 않다. 우리는 그것이 결코 음수가 되지 않도록 impulse를 clamp해야한다.
- Inequalities are handled with clamping
SI iteration동안, 우리는 각 constraint에서 증가하는 impulses를 연산한다. 우리는 inequality constraints에 대해 증가하는 impulse를 clamp해야하는가? 아니다! 우리는 그 축적된 impulses를 clamp해야한다. 이것은 incremental impulses가 음수가 되도록 허용한다.
{
Box2d-lite version에서 이부분. Pn이 축적된 impulse이다.
if (chLiteWorld::accumulateImpulses) { // Clamp the accmulated impulse ChReal Pn0 = c->Pn; c->Pn = Max(Pn0 + dPn, ChReal(0.0)); dPn = c->Pn - Pn0; } else { dPn = Max(dPn, ChReal(0.0)); }
- Clamping the accumulate impulse
oldImpulse = constraint.impulse;
delta = constraint.ComputeImpulse();
constraint.impulse += delta;
constraint.impulse = max(0, constraint.impulse);
delta = constraint.impulse - oldImpulse;
constraint.ApplyImpulse(delta);
여기에 너가 어떻게 그 축적된 impulse를 clamp하는지가 있다. 처음에, 축적된 impulse를 복사해라. 다음에, constraint를 해결하여 incremental impulse를 연산해라. 이제, 그 incremental impulse를 축적된 impulse에 더해라. 그러고나서 그 accumulated impulse를 clamp해라. 마지막으로, 축적된 impulse에서 실제 변화를 설명한 incremental impulse를 다시 연산한다. 우리는 그러고나서 constraint와 관련된 bodies에 incremental impulse를 적용한다.
- Why Accumulate? Overshoot!
accumulated impulse를 clamping하는 것은 accumulated impulse가 양수인 동안 그 incremental impulse가 음수가 되는 것을 허용한다.
만약 우리가 warm starting을 사용한다면, 우리는 명백히 그 accumulated impulse를 clamp할 필요가 있다. 왜냐하면 그 contact impulse는 objects가 떨어질 때 zero로 줄어들 필요가 있기 때문이다.
우리가 warm starting을 사용하지 않은 경우에는 어떤가? 이것은 다음의 질문이 핵심이다: accumulated impulse는 한 time step동안 overshoot하는가? 만약 그것이 overshoot하면, 우리는 어떤 negative incremental impulses가 그 onvershoot를 줄이게 할 필요가 있다.
{
이제 내가 궁금해하던 것이 풀렸다. Impulse를 Iteration을 여러번 적용할 때, Impulse가 추가되어 Bounce가 심하게 일어나야 할 텐데 왜 그게 해결되는지 몰랐는데. 여기에서 Inequality Constraint를 해결하는 과정에서 accumulated impulse를 clamping하여 incremental impulse가 overshoot된 impulse를 다시 줄이게 해준다.
}
- In search of overshoot: box on a plane
overshoot를 찾아보자!
한 평면위에 있는 한 박스를 고려하자. 만약 우리가 몇 번의 iterations에 대해 impulses를 그래프로 그린다면, 우리는 그 accumulated impulses가 단조로 증가한다는 것을 본다 (결코 그것들은 줄어들지 않는다). 그래서 이 경우에, 우리는 그 축적된 impulse를 clamp할 필요가 없다.
실제로 우리는 만약 warm starting이 사용되지 않는다면, 어떠한 clamping도 필요하지 않는다 (우리의 초기 추측은 zero 이다).
Demo : 나는 이 그래프를 생성하기 위해 Matlab/Octave script를 썼다.
- Box on a pole
이제 내가 narrow pole위에 박스를 놓았다고 가정하자. 그 pole이 매우 줄어듬에 따라, 그 시나리오는 한 점에서 쉬고있는 box와 가깝게 된다. 만약 single point가 있었다면, 그 box의 모든 무게는 그 single point에 의해 지지되어질 것이다. 그러나, narrow pole로 두 개의 contact points가 있다.
그래서 내가 그 첫 번째 contact point를 해결할 때, 그것은 그 box의 모든 무게를 거의 지지하려고 한다. 이것은 왜냐하면 첫 번째 point가 그 두 번째 point를 모르기 때문에 발생한다. 내가 그 두 번째 contact point를 해결할 때, 그것은 그 box가 거의 완전히 지지되어있는 것을 보지만, 작은 회전이 있다. 그래서 오직 작은 impulse가 적용된다. 그러나 정확한 솔루션에서, 각 contact point는 그 box의 무게의 절반을 견뎌야한다. 그래서 그 첫 번째 accumulated impulse가 second accumulated impulse가 증가하는 반면에 줄어들어야 한다. 그렇지 않다면 그 박스는 회전하기 시작할 것이다.
- Box on a pole, b = 0.75 * a;
심지어 a의 75%에 있는 b로, 어떤 overshoot가 있다. 그러나, 나는 2회의 iterations으로 좋은 convergence를 얻는다.
- Box on a pole, b = 0.5 * a
a의 50%를 가진 b로, 좀 더 많은 overshot가 있다. 나는 convergence를 위해 두 배 더 많은 iterations을 필요하다.
- Box on a pole, b = 0.25 * a
a의 25%를 가진 b로, 더 큰 overshoot가 있고, 나는 convergence 약 12번의 반복이 필요하다. 그래서 이 경우에 overshoot가 중요할 뿐만아니라, 우리는 또한 또 다른 시나리오를 발견하게 된다. sequential impulse의 convergence가 좋지 않다는 것이다.
- Improve Sequential with block solvers
Global solvers는 너무 비싸지만, 그것들은 훌륭한 결과들을 준다.
우리는 SI를 개선시키기 위해 작은 수의 constraints를 동시에 해결할 수 있다. 예를들어, convex shapes 사이의 2D 충돌에서, 한 개 또는 두 개의 contact points가 있다. 두 개의 contact points의 경우에, 우리는 두 개의 normal constraints를 동시에 해결하여 많은 안정성을 얻을 수 있다.
Inequality constraints는 active or inactive 할 수 있다. active contact point는 positive load를 갖지만, inactive contact point는 zero load를 갖는다. 그래서 2개의 contact points로 우리는 4개의 경우를 갖는다. 그래서 처음에 나는 두 개의 contact points를 active로서 해결하려고 한다. 만약 한 lambda가 음수라면, 나는 lambda1를 0으로 설정하고, lambda2에 대해 해결한다. 만약 lambda2가 음수로 나온다면, 그러면 나는 lamb2를 0으로 설정하고, lambda1에 대해 푼다. 만약 lambda1이 음수라면, 나는 두 개의 lambda를 0으로 설정한다.
나는 이것에 대한 세부사항을 다룰 시간이 없지만, 너는 Box2D 코드에서 그것을 찾을 수 있다.
- Understanding acceleration constraints, then not using them
Newton의 운동 법칙은 가속도를 사용한다. 가속도에 constraints가 있는가? 그렇다 있다!
- Acceleration constraints are associated with forces
이 이미지는 collision force의 실직적인 묘사를 보여준다. 이것은 충돌이 작은 시간 주기 동안 발생한 경우에 대해 그려졌다. rigid body simulation에서, 충돌은 순간적으로 발생하고, 이것은 infinite forces를 이끈다. 그래서 우리는 충돌에 대해 가속도를 사용할 수 없고, 오직 resting contact에 대해 사용할 수 있다.
그러나 상황윽 더욱 악화된다. 심지어 충돌 없이, friction forces는 무한으로 튈 수 있다. 미끄러지는 막대를 고려해라. 그 막대가 미끄러질 때, 마찰은 그 rod가 땅에 들어가게 만들고, normal force를 증가시킨다. 그러나 이것은 마찰이 증가하도록 하고, friction이 엄청 커져버리는 positive feedback loop를 만든다.
이 이유 때문에, 게임 물리 프로그래머들은 오래전에 acceleration constraints를 포기했었다.
- Switch to velocity constraints
만약 우리가 velocity constraints로 전환한다면, 그 friction impulse는 유한하게 남는다. 왜냐하면 velocity constraints는 collision과 sustained contact사이를 구분하지 않기 때문이다. 그 friction impulse는 유한한 동안 one time step에서 완전히 contact point를 멈출 수 없다.
- Are Velocity constraints best?
Velocity constraints는 rigid body simulation에 대해 달콤한 지점인 것처럼 보인다. 우리가 연산한 그 impulses는 항상 유한하고, friction은 재현하기에 쉽다. 왜냐하면 friction은 오직 velocity만 constraint하기 때문이다. position이 아니라.
- We still must account for position error
우리는 결코 rotation의 nonlinearity에 의해 완벽한 velocity solution을 가질 수 없다. 심지어 회전 없이도, 우리는 velocity solution이 converge할 만큼 충분한 iterations을 허용하지 않을지도 모른다. 그래서 우리는 position constraints에서 어떤 에러를 얻을지도 모른다. 그 Sequential Impulse algorithm은 이러한 position errors를 신경쓰지 않는다. 그래서 우리는 position errors를 다루기 위해 어떤 부가적인 시스템이 필요하다.
- Solving position errors by velocity steering
Regular contact constraint
Biased contact constraint
position errors를 수정하는 일반적인 기법은 position errors를 velocity constraint solver에 넣는 것이다. 우리는 rigid bodies가 더 작은 position error를 가진 설정으로 가게끔 velocity bias를 추가할 수 있다. 그 velocity bias는 tuning factor beta, 양의 거리 s 그리고 time step을 포함한다.
이것은 많은 경우에 잘 작동하지만, 부작요을 가지고 있다. 첫 번째, 우리는 그 velocity bias를 scale down해야만 한다. 그래서 그 bodies가 position target을 overshoot하지 않는다. 이것은 scaling factor beta로 처리된다. 둘 째로, velocity bias는 그 시뮬레이션에 kinetic energy를 추가하고, 이것은 불안정성을 발생시킬지도 모른다.
- Solving position errors using pseudo velocity
Pseudo Newton's law
Pseudo velocity constraint
velocity를 움직이는 것은 position error를 수정하는 것에 효과적이다. 우리는 position correction에서 pseudo velocities를 사용하여 안정성 문제를 제거할 수 있따. 이러한 pseudo velocities는 상태의 일부가 아니고, 프레임들에 걸쳐서 지속되지 않는다.
position correction에 대해, 나는 pseudo velocities를 연산하기 위해 같은 제한이 있는 운동 방정식을 사용한다. 내가 진짜 velocities를 연산하기 위해 하는 것처럼, 다음을 제외하고 : 어떠한 외부 forces가 없다 (예를들어 중력이 없다), 그리고 나는 friction or motors같은 velocity only constraints를 포함하지 않는다. pseudo velocities를 연산하는 과정에서, 나는 pseudo impulses를 연산한다. 나는 이러한 pseudo impulses에 대해 warm starting이 필요하지 않다. 왜냐하면 그것들은 external forces에 의해 영향을 받지 않기 때문이다. 그 pseudo impulses는 position error가 zero일 때 zero가 된다.
- Why not work with positions directly?
velocity > acceleration
position > velocity?
나는 이미 acceleration constraints를 제거하는 것이 증가된 robustness를 어떻게 이끄는지를 이야기 했었다 (contact forces가 무한하게 될 수 있기 때문에). Box2D에서 나는 두 가지 solvers를 가진다: velocity constraints를 해결하는 것과, position constraint를 해결하는 것. 그래서 velocity constraints를 제거하고 position constraints로 작업하면 안되는가?
- Example: cloth solver
일반적인 cloth solver는 position constraints와 작동한다. cloth에서 중요한 position constraints는 distance constraints이다. 비록 distance constraints가 non-linear일지라도, 우리는 정확히 그 점들과 함꼐 움직이거나 필요한 connecting line을 따라서 분리하여 그것들을 해결할 수 있다. 보통 adjustments는 질량에 따라 가중되는데, 가벼운 파티클들은 무거운 파티클들보다 더 많이 움직인다.
- Cloth particle velocity
Cloth solvers는 velocity를 부작용으로서 다룬다. time step의 쵝에, 나는 particle positions을 캐싱한다. 그러고나서 나는 gravity와 distance constraints를 적용한다. 그 constraint solver iterations가 끝났을 때, 나는 time step으로 나누어진 실제 particle movement 사용하여 particle velocity를 업데이트 한다.
Cloth solvers는 매우 튼튼하지만, velocity constraints가 없기 때문에 friction을 어떻게 적용하는지가 명백하지 않다. position만 가지는 solver의 또 다른 문제는 너가 더 큰 position errors를 얻을 수 있다는 것이다. 그 velocity solver는 상호 관통이 발생하기 전에 방지할 수 있다.
- Example: character solver
Character solvers는 game world에서 player avatars를 움직이기 위해 사용된다. 그 character solver의 주된 일은 캐릭터가 벽과 다른 solid objects를 움직이는 것을 막는 것이다. 보통 그 캐릭터는 구 또는 캡슐 같은 단순한 collision shape로 둘러 싸여진다. Character solvers는 physics에 대해 agnostic하다. Character physics는 게임플레이의 이유로 비현실적인 주관적인 주제이다. 예를들어, 캐릭터들은 끊임없이 방향을 바꿀지도 모르고, 또는 점핑할 때 심지어 movement control을 가진다
- Character movement: velocity solver
많은 게임에서, 그 캐릭터는 sphere 또는 capsule같은 symmetric shape로서 나타내어진다. 그러하듯이, 우리는 보통 캐릭터를 회전시킬 필요가 없다. 그러므로, 그 character solver는 오직 translation만 다룰 필요가 있다. 게다가, 우리는 보통 plane constraints만을 사용하는 것으로 해 나갈 수 있다. 각 time step 마다, 우리는 그것이 장애물에 움직일 때 까지 character를 움직이고, 그러고나서 그 contact plane에 대해 해결한다. 이 과정은 time step의 끝까지 반복된다.
많은 게임들은 characters에 대해 velocity type solver를 사용한다. 그것들은 어떤 초기 velocity로 시작한다. 그러고나서 그 velocity를 plane이 만날 때 마다 clip한다. solver의 이러한 종류는 numerical precision issues를 겪을 수 있다. 예를들어, 그 clipped velocity는 small error를 가질지도 모르고, 그 캐릭터는 contact plane으로 다소 계속 움직인다.
- Character movement : position solver
또 다른 접근법은 characters에 대해 position solver를 사용하는 것이다. 나는 Tomb Raider에 작업하여 이 기법을 개발했었다. 나는 shape casts를 사용하여 캐릭터가 움직일 때 collision planes를 모은다.
Shape cats는 ray cast같은 것이고, 한 긴 line으로 한 점을 움직이고 충돌을 찾는 대신에, shape cast는 한 shape를 충돌을 찾기위해 한 line을 따라 움직인다. 너는 generic shape casts를 위해 작년에 내가 이야기 한 time of impact algorithm을 사용할 수 있다.
여기에 그 알고리즘이 어떻게 작동하는지가 있다. 나는 처음에 어떤 overlaps이 있는지에 대해 환경을 scan한다. 이것들은 collision planes의 list를 만들기 위해 사용된다. 나는 그러고나서 그 캐릭터를 target point로 움직이고, 그러고나서 캐릭터가 많이 움직이지 않을 때 까지 NGS를 적용한다. 이것이 solver point1 이다. 그러고나서 나는 start point에서 point1를 풀기위해 sweep을 수행한다. 어떤 새로운 collision planes이 그 리스트에 더해진다. 또 다시 나는 그 캐릭터를 target point까지 움직이고, 그러고나서 solve point 2를 얻기 위해 collision planes의 새로운 집합에 대해 NGS를 적용한다. 나는 연속하는 solve points가 가까워질 때 까지 이 과정을 반복한다. 바라건데, 너는 이 방법이 기하학적으로 velocity method보다 더 튼튼하다고 볼 수 있다.
- A Plane Solver
그래서 그 plane solver는 어떻게 작동하는가? character solver에 대한 입력 데이터는 target position과 constraint planes이다. 우리는 character의 현재 position이 필요하지 않다! character의 현재 position은 contact planes를 모으기 위해서만 사용된다.
나는 character solver의 일을 이제 말할 수 있다: contact plane constraints를 만족시키는 target position과 가장 가까운 위치를 찾아라. 우리는 이것을 해결하기 위해 간단한 NGS solver를 사용할 수 있다. 그것은 엄청 간단한데, 왜냐하면 회전하지 않는 한 개의 움직이는 오브젝트만 있을 때 질량이 중요하지 않기 때문이다. 또한, 그 constraints는 모두 linear이다. 두 개의 planes으로, 우리는 정확한 솔루션을 계산할 수 있다. 그러나, 우리가 많은 contact planes을 얻음에 따라, 이것은 좀 더 어려워진다. 그래서 나는 approximate solution을 얻기위해 iterative solve를 사용한다. 또한, 우리는 정확한 solution을 필요하지 않는다. 우리는 valid solution이 필요하다.
- Character solver: acute angles
Acute angles(예각)은 charcter solver에 대해 convergence trouble을 일으킬 수 있다. 너가 볼 수 있듯이, corner의 vertex에 접근하기 위해 꽤 많은 iterations가 필요하다. 운 좋게도, 그 solver는 빠르고, iteration cost는 보통 collision detection보다 더 작다.
이 그래프를 생성하는 코드에 대해 Character.m Matlab script를 보아라.
- Acute angle ping pong
여기에 그 iterations이 acute angle을 어덯게 찾는지가 있다. 그것은 모든 iterative solver가 단점을 가진 것처럼 보인다. Global solvers도 그것들의 단점을 가진다 또한. 예를들어, 만약 우리가 중복되는 collision planes를 가진다면, 그 global sovler는 그 행렬을 역행렬 시키는데 문제를 가질 것이다. Local solvers는 redundant constraints에 문제가 없다.
댓글 없음:
댓글 쓰기