우리는 지금까지 우리의 물리 엔진을 개발했다. 너가 그것에 추가할 수 있는 것들이 있다: force generators, joints 등등. 너는 그것은 너가 그것의 한계를 이해하고 그것들을 처리하려고 의지가 있는 한, 여러 다양한 게임 장르들에서 그것을 사용할 수 있다.
나는 이 책에서 어떤 다른 것보다 이 챕터를 더 많이 언급했다. 우리가 그 엔진을 구성했을 때, 나는 내가 사용할 근사, 가정, 구현 옵션들에 대해 결정을 했었다. 각 경우에, 다른 대안들이 있었다. 내가 구현한 엔진은 좋고 유용하지만, 동등하게 좋고, 다른 한계를 가질 수 있는 몇 개의 다른 접근법들이 있다.
이 챕터에서, 우리의 물리엔진과 그러한 다른 접근법들 사이의 주된 차이를 본다. 그것은 그러한 엔진 또는 어떤 상세한 구현 충고에 대해 단계별 가이드를 제공하지 않을 것이다. 한 엔진을 구성하는 것은 전반적인 상호 의존적인 결정을 포함하기 때문에, 만약 우리가 각 접근법을 처리하려고 한다면, 이 챕터는 그 책의 두 배가 될 것이다. 대신에, 나는 그것이 너에게 대안을 이해하고 만약 너가 그 길로 가기 원한다면 너가 시작하게끔 해주는 충분한 정보를 주기를 바란다.
18.1 Simultaneous Contact Resolution
우리의 엔진에서, 우리는 한 time에 한 번씩 contacts를 해결한다. 이것은 빠르지만, 우리가 그것을 보았듯이, 한계를 가진다. 특히, 우리는 한 contact를 해결하기 위해 우리가 취한 행동이 다른 contacts가 비현실적인 방법으로 움직일지에 대해 알 방법이 없다. 우리의 엔진에서, 이것은 마찰과 함께 연결된 contacts들의 한 집합이 서로에게 떨어져서 미끄러지기 시작할 때 보인다.
그 대안은 contacts들의 한 집합을 동시에 해결하는 것이다. 각각의 impulse를 차례로 계산하기 보다는, 우리는 모든 것의 impulses를 동시에 발견할 필요가 있다.
이 simultaneous calculation을 수행하는 대부분의 물리 엔진들은 impulses보다 force calculations를 기반으로 한다. 다시 말해서, resting contact에 있는 두 개의 오브젝트들은 contact force에 의해 떨어진다, 우리가 했던 것처럼 일련의 single-frame impulses에 의해서가 아니라. 그래서 그 resolution calculation은 각 contact에 적용할 forces와 impulses를 찾으려고 노력한다, 모든 contacts들의 상호작용을 고려하여.
이것을 하는 가장 흔한 접근법은 "linear-complementary problem"이라고 불려진다. 그것은 Jacobian이라고 불려지는 수학 구조를 구성하는 것을 포함한다, 그것은 다른 contacts 사이의 상호작용을 인코딩한다. 이것은 그러고나서 적용할 (보통) forces의 단일의 집합으로 전환될 수 있다.
이것이 그러한 공통의 그리고 중요한 접근법이기 때문에, 우리는 이 챕터에서 하이레벨로 그것을 볼 것이다. 그러나, 나는 구현의 세세한 지점까지 들어가지 않을 것이다. 그 알고리즘들을 안정적인 방식으로 작동시키는 것은 수 많은 스페셜 케이스 문제와 특이한 복잡성을 포함하기 때문이다.
18.1.1 The Jacobian
Jacobian은 한 contact가 다른 것에 영향을 주는 방법에 대해 말하는 수학적 construct이다. 그것은 어떤 tweak의 부작용에 대한 완전한 지식과 함께 만들어진 adjustments의 올바른 balance를 결정하기 위해 사용된다.
모든 오브젝트들에 대한 모든 forces와 torques는 하나의 매우 긴 벡터에 통합된다. 각 rigid body에 대해 세 개의 force entries와 세 개의 torque entries가 있을 것이다. 그래서 그 vector는 6n entries를 가질 거시다. 거기에서 n은 rigid bodies의 개수이다. 같은 방식으로 모든 오브젝트들에 대한 모든 가속도 (linear and angular)들은 하나의 긴 벡터로서 다루어진다 (또 다시, 6n의 entries를 갖는다).
Jacobian 행렬에 있는 entries는 그 두 개를 함께 연관짓는다. 행렬에서 행a와 열 b에 있ㄴ느 값은 우리에게 방향 b에 이쓴 단위 force or torque가 발생시킬 component a에 있는 가속도의 양을 말해준다. 행렬에 있는 몇 가지 entries는 매우 간단하다: 그것들은 우리가 한 오브젝트의 움직임을 결정하기 위해서 우리가 사용한 방정식이다. 예를들어, X방향에 있는 한 force는 m^-1의 크기의 가속도를 발생시킬 수 있따 (F = ma로부터); 그래서 Jacobian 에서, X방향의 force를 X방향의 가속도로 연관짓는 값은 m^-1이될 것이다.
Jacobian에서 많은 값들은 간단한 운동 법칙에 기반을 두지만, 몇몇은 contact points에서 오브젝트들의 상호작용에 의한 것이다. 행렬의 각 값은 열의 컴포넌트에서 단위 변화로 주어진 행의 컴포넌트에서 발생할 변화를 준다.
Jacobian에서 그 entries를 계산하는 것은 서로의 contact에서 단위 force가 주어진 each contact에서의 forces를 처리하는 것을 포함한다. 그 과정은 다른 것에 대해 한 contact resolution의 효과를 계싼하기 위해서 우리의 엔진에서 했던 것과 유사하다.
Jacobian의 entries만이 존재 하지 않는다. 왜냐하면 한 contact가 다른 것에 영향을 미치기 때문이다. 한 contact의 한 축이 다른 것에 영향을 미치는 것도 또한 가능하다. 마찰이 있는 한 contact에 대해, 그 발생된 friction force는 normal reaction force에 의존할 것이다. reaction force가 한 방향으로 증가함에 따라, 그 friction force 또한 증가할 것이다. 그러므로 이 연결성을 나타내는 Jacobian에서 entry가 있다.
오브젝트 사이의 상호작용을 나타내고, 뿐만 아니라 오브젝트의 기본 운동 자체를 나타내는, Jacobian의 유연성은 그것이 더 큰 범위의 joints를 만들기 위해서 사용되는 것을 허용한다. 우리의 엔진에서 joints는 explicitly하게 명시되고, 그것 자신의 코드로 다뤄진다. Jacobian은 어떤 두 오브젝트들의 움직임을 시뮬레이션에서 연결하는 메커니즘을 제공한다. 사실, 그것은 각 오브젝트의 다른 원소들을 연결시킬 수 있다, 그래서 예를들어, 한 축을 따라 한 오브젝트의 움직임이 고정되어질 수 있다 (쯕, 이 joint를 부수려는 어떤 힘은 한 동등하고 반대의 reaction force에 의해 저항된다). 게다가, 자동차들은 어떤 것이 진행되는 것과 상관없이 forces를 발생시키는 Jacobian에 대해 원소를 추가하여 구현될 수 있다. 만약 너가 ODE 같은 (그리고 몇 가지 상업 middleware package) 물리 엔진을 본다면, 그것들은 매우 유여한 joints와 motors가 Jacobian에 직접적으로 entries를 추가하여 만들어지는 것을 허용한다.
대부분의 force components들은 직접적으로 서로 상호작용하지 않을 것이다. 그래서 그 Jacobian은 대응되는 위치에 0을 가질 것이다. 사실 대부분의 그 행렬은 0으로 채워져 있을 것이다. 그 Jacobian은 이 이유 때문에 가끔씩 "sparse matrix"라고 불려진다. sparse matrices의 수학은 regular matrices보다 극적으로 더 간단해 질 수 있다. 하지만 그 알고리즘들은 종종 더 복잡하다.
너는 Lagrange multipliers, the Lagrange method, or Featherstone's algorithm에 대해 말하는 게임 엔진에 대한 책이나 논문들을 만날지도 모른다. 이러한 것들 각각은 여기에서 보여지는 메소드와 관련있다. 그 Lagrange method는 우리의 것보다 좀 더 복잡한 방정식과 작업을 하는데, 거기에서 그 Jacobian은 몇 가지 부분으로 분해되고, 그 부분들 중 하나는 오브젝트들 사이의 연결성을 명시하고 다른 것은 (소위 Lagrange multipliers) 상호작용의 양을 명시한다. 대부분의 게임 엔진들은 보여지듯이 raw Jacobian을 사용하지만, 너는 Lagrange method에 대해 읽는 것이 유용하다는 것을 알지도 모른다. 물리의 수학에 대한 많은 교재들은 게임과 관련하여 쓰여있지 않다. 그래서 그것들은 Lagrange formulation을 광범위하게 사용한다. 그것이 어떻게 작용하는지를 이해하는 것이 유용할 수 있다.
18.1.2 The Linear Complementary Problem
Jacobian으로 무장하여, 우리는 모든 contacts들을 동시에 resolving하는 것의 수학적 문제를 공식화할 수 있다. 그것은 다음의 기본 형태를 갖는다
여기에서 f는 모든 rigid bodies에 대한 force와 torque components의 벡터이고, ddot(p)는 최종 가속도이다. 그러나 f는 두 개의 컴포넌트들로 구성된다.
여기에서 f_known은 우리가 아는, 적용할 forces와 torques의 집합이고 (중력에 의한 forces 또는 다른 force generators에 의한 힘들), 그리고 f_contacts는 contacts에서 생성된 forces의 집합인데, 그것이 우리가 찾으려고 하는 것이다.
대개 종종, 너는 다음으로 쓰여진 방정식을 보게 된다
(삐록 Jf + b = a같은 다른 기호로 종종 주어질 지라도). 다시 말해서, 그 Jacobian은 known acceleration을 얻기 위해 known force vector에 의해 곱해진다. 이것은 내가 이전에 명시적으로 말하지 않은 행렬 곱의 한 사실에 의존한다 -이름하여, 분배법칙이다. 어떤 유효한 행렬곱에 대해, A X ( B + C) = A X B + A X C이다.
ddot(p)_known을 계산하는 것은 contact resolution의 전의 한 단계이다. 왜냐하면 이 값은 우리가 contact forces를 처리하려고 할 때 변하지 않을 것이기 때문이다.
그것 스스로, 방정식 18.1은 Jacobian의 역을 처리하여 해결될 수 있다 (시간을 소모하는 문제이고, 해결책이 없는 것도 있따). 그러나 설상가상으로, 우리는 부가적인 제약을 갖는다:
여기에서 r는 그 forces가 얼마나 클 수 있는지에 대한 한계에 대한 벡터이다. Normal reaction forces는 그것들이 필요한 만큼 클 수 있지만, friction forces는 제한된다. force vector에서 특별한 entry는 friction force를 나타낼지도 모르고, 그러므로 제한될 필요가 있다.
그것이 두 방정식을 수행하기 위해 f를 찾는 그 최종 계싼은 "linear complementary problem" (or 짧게 해서 LCP)라고 불려진다. 대안의 접근법은 f contacts에서 components에 대한 가장 작은 가능한 값을 찾으려고 하는 것이다. 이것은 "quadratic programming" (or QP)라고 불려지는 최적화 문제가 된다. 몇 가지 물리 시스템은 QP를 구성하고 해결하지만, LCP로 작업하는 것이 좀 더 흔하다.
LCP를 해결하는 것에 대해 좀 더 흔히 사용되는 알고리즘은 "pivot algorithm"이라고 불려진다. 그것은 f에 있는 컴포넌트들에 대해 추측을하고 결과를 점검하여 작동한다. 한 추측의 집합으로부터 나온 에러들은 한 번에 하나씩 컴포넌트들을 수정하기 위해 사용될 수 있고, 해에 수렴할 수 있다. rigid body simulation에서 흔히 충족되는 몇 가지 가정하에, 그 추측들은 항상 해에 수렴할 것이다. 그 pivot algorithm ("Lemke pivot"이라고 불려지는 한 알고리즘에 기반을 둔)은 David Baraff에 의해 인기 있어졌다: Baraff and Witkin [1997]을 보아라, 그 접근법에 대해 단계별 introduction을 위해.
복잡성을 numerical instability와 고정 길이 time step의 근사 때문에 발생한다. rigid body simulation이 물리적으로 불가능항 상황에 있게 되는 것이 가능하다, 거기에서 LCP에 대한 어떠한 해결책도 없다. 이 경우에 그 pivot algorithm은 무한히 루프를 돌 수 있다. 튼튼한 구현은 이러한 종류의 문제를 고려할 필요가 있고, 대안을 제공할 필요가 있다. 흔한 대안은 impulses를 부과하는 것이다, 어떠한 유요한 force solution이 없을 때. 효율적이면서 그것을 옳게하는 것은 매우 어려울 수 있다. 내 경험으로 (나는 두 개의 pivot-based engines을 만들었고, 몇 가지 중요한 복잡성 중 하나인), 어떤 것을 작동시키는 것은 쉽지만, 일반적인고 튼튼한 엔진으로 끝내는데 몇 달이 걸린다.
How It Is Used
force-based pivot algorithm은 우리가 이 책에서 구성한 엔진과 다른 방식으로 작동한다. 우리의 엔진에서, forces는 축적되고 적용된다, 그러고나서 충돌 탐지와 반응이 발생한다.
그러나, 그 Jacobian은 forces를 적용하는 것에 대해 계산을 포함한다. 그래서 모든 것이 한 번에 해결된다: contact forces가 계산되고, 그 forces의 나머지와 함께 그에 따라 적용된다.
그러나, 이것이 제기하는 세 가지 문제가 있다: 우리는 언제 충돌 탐지를 하는가? 우리는 어떻게 interpenetration을 하는가? non-resting contacts에 대해 어떤가?
다른 물리엔진의 architecture는 다른 방식들로 이러한 단계뜰을 처리한다. 그 두 번째에서 두 개의 문제들은 우리가 우리의 엔진에서 가졌떤 방식과 똑같이 접근되어진다 (그러나, micro-collisions을 제거하여: 만약 두 오브젝트들이 resting contact에 있다고 결정된다면, 그러면 그것들은 force system으로 처리된다). 별개의 collision and interpenetration steps는 forces가 적용된 후에 취해진다.
몇 엔진들에서, collision response가 처음에 수행되고, 그리고 그것의 결과들은 known force vector에 삽입되고, 이전에 이야기된 force calculations에 통합된다. 이것은 만약 우리가 한 update frame t에 대해 시간의 길이를 안다면, 공식을 이용하여 우리가 impulse g를 force f로 바꿀 수 있는 사실에 의존한다.
f = gt
이 공식은 우리가 계산된 collision impulse를 마치 rigid body에 적용된 또 다른 힘처럼 나타내도록 해준다.
그 첫 번째 문제는 좀 더 어렵다: 언제 우리는 collision detection을 하는가? 만약 우리가 force calculation저에 그 프레임의 시작에 collision detection을 한다면, 그러면 forces를 적요하는 것의 결과는 그 오브젝트들이 다음에 그려질 때, 여전히 눈에 보일 새로운 충돌들을 발생시킬지도 모른다.
만약 우리가 force calculation 후에 collision detection을 한다면, 우리는 사용자가 그 frame을 보기전에 모든 interpenetration을 제거할 수 있다. 그러나 어떻게 우리는 frame의 시작에서 그 Jacobian에 채울 필요가 있는 contacts들을 결정하는가?
우리는 둘 다 할 수 있지만, 그것은 매우 시간을 소모할 것이다. 사실, 그 두 번째 해결책이 일반적으로 사용되는 것이다.
그 collision detection은 interpenetration이 resolved되기 전에 수행되고, 그 사용자는 non-interpenetrating bodies를 본다. 그 같은 collision data는 그러고나서 다음 업데이트까지 저장되고, Jacobian을 채우기 위해 사용된다. 이것은 효율성과 (추가 데이터가 프레임 사이에 저장된다) 과 눈에 보이는 interpentration을 제거하는 것(일반적으로 viewer에게 명백한) 사이의 좋은 타협을 내준다.
내가 chapter 12에서 언급했듯이, commercial systems는 종종 frame coherence를 사용하여 더 효율성을 개선한다: 이 프레임에서 collision checks를 가속하기 위해 지난 프레임의 충돌을 추적한다. 만약 그 collision detector가 이것을 한다면, 그러면 그 데이터는 이미 저장되어있고, 물리엔진에게 이용가능하게 만들어질 수 있다.
18.2 Reduced Coordinate Approaches
게임 개발 서클들에서 종종 언급되는 또 다른 기법은 (비록 거의 구현되지 않지만) reduced coordinate approach이다.
우리의 물리엔진에서, 우리는 12개의 자유도를 가진 각각의 rigid body가 주어진다: position, orientation, velocity, and rotation에 대해 세 개씩. 그 orientation은 4개의 값을 사용하지만 오직 세 개의 자유도를 가진다: 그 네 번째 갑은 항상 다른 세 개의 것으로부터 결정될 수 있따 (왜냐하면 그 쿼터니언의 사이즈가 1이여야만 하기 때문이다).
오브젝트가 contact에 있거나, 그것들 사이에 joints를 가질 때, 그것들은 제약된다. 그것들은 더 이상 12개의 자유도 각각에 대해 어떠한 값을 가질 수 없다. 예를들어, 한 들 수 없는 block이 flat ground에 배치된다면, 그것은 오직 두 개의 방향으로 눌려질 수 있ㄱ, 오직 한 축을 따라 방향을 향해질 수 있다. 그것은 오직 6개의 실제의 자유도를 갖는다 (position에 대해 2개, orientation에 대해 1개, velocity에 대해 두개, rotation에 대해 한 개).
우리가 이 책에서 구성한 물리 시스템은 모든 오브젝트들이 12개의 자유도로 움직이게 하는 것을 허용한다; 그러고나서 그것은 그것들이 적절히 행동하는 것을 보장하기 위해서 impulses와 non-penetration code를 사용한다. 대안은 정확히 그 오브젝트가 얼마나 많은 자유도를 가졌고 그러한 것들이 어떻게 변하는지를 허용하는 방법을 처리하는 것이다.
땅 위에 있는 블럭에 대해, 이것은 간단하고, 한 예제는 Eberly [2204]를 통해 완전히 처리된다. 이것은 이 시리즈의 다른 물리 책이다.
그것은 남은 자유도의 관점에서 뉴턴의 운동법칙을 사용하여 움직임의 방정식을 처리하는 것을 포함한다. 한 평면 위의 한 블럭 너머에 있는 어떤 것에 대해, 이것은 꽤 연관되어질 수 있다. 그 constraints가 joints를 나타낼 때, 자유도들은 회전화 위치의 조합이 될 수 있다. 움직임의 방정식을 찾는 것은 정마로 어려울 수 있다. 움직임의 방정식이 계산되기만 한다면, 그러면 그것들은 매우 빠르게 해결될 수 있다. 그러므로 그 자유도가 변하지 않을 때 그것은 유용한 접근법이고, 그 방정식들은 사전에 하드코드되어 빠르게 풀어질 수 있따 (Eberly[2004]에서의 예쩨에 대해 사실이다).
joints에 의해 연결된 bodies의 어떤 조립체에 대해 (bones와 joints가 어떠한 loops가 없는 branching tree가 있는 ragdoll같은), 자유도와 움직임의 해당 방정식을 계산하는 잘 알려진 방법들이 있다. 이 접근법을 사용한 내가 본 단일 목적의 ragdoll simulators가 두개 있었지만, 그것들은 production games에서 보다는 technical demos에 있었다. joints의 일반적인 집합에 대해, 그 procedure는 더 어려울 수 있고, 모든 의도와 목적에 대해, 비실용적이다. 특히 한 게임에서 constraints가 다른 시간에 나타나고 사라질지도 모르기 때문이다 (특히 contact constraints가 있는 case).
이 기법은 또한 general force generator를 도입할 때 더 여렵다. ragdoll이 물위에 뜨게 한다던가 바람에 의해 싸워지게 하는 것은 중요한 복잡성을 각 자유도에 대한 운동 방정식을 계산하는데 도입한다.
이 이유 때문에, 나는 reduced coordinate approaches를 기반으로 한 어떤 일반 목적의 게임 물리엔진을 못보았다. 너는 특별한 효괄르 얻기 위해 reduced coordinate 접근법을 보길 원할지도 모르지만, 그것들은 일반적인 솔루션이 되지 않을 가능성이 높다.
18.3 Summary
다른 접근법에 대한 회오리바람 tour의 목적은 너에게 기본 어휘와 이해를 주는 것이다. 어리둥절하게 만드는 여러가지 물리들과 인터넷에서 이용간으한 시뮬레이션 자료들을 볼 때, 너는 이제 그것들이 전체 그림에 어떻게 들어가야하는지를 이해할 수 있어야 하고, 우리의 엔진이 그것들과 어떻게 연관되는지를 이해해야만 한다.
너는 우리가 만든 엔진과 비교할 수 있는 Net에 몇 가지 오픈 소스 물리 시스템들이 있다. ODE(the Open Dynamics Engine)은 특히, hobby projects에서 널리 사용된다. 그것은 튼튼한 구현이지만, 그 코드가 어떻게 작동시키는지에 대해 너의 방식을 찾는 것은 어려울 수 있다. 우리의 엔진처럼, 그것은 속도를 위해서 주로 만들어지지 않았다.
게임에 유용한 다른 물리 기법의 좀 더 포괄적인 수학의 조사를 위해, 나는 Eberly [2004]를 추처한다. David는 내가 여기에서 가진 것보다 좀 더 많은 수학적 지식을 가정하지만, 만약 너가 이 책을 따라왔따면, 너는 아마도 시작할 준비가 되어있다. 그 Eberly 책은 완전한 일반 목적의 엔진을 어떻게 구성하는지를 다루지 않지만, 우리의 엔진에 통합되거나 그것들 스스로 사용될 수 있는 고아범위한 기법들과 트릭들을 본다.
David Baraff는 물리학에 Jacobian-based approaches에 대한 정보를 퍼뜨리는데 어느 누구보다 많이 했다. 그의 작품은 내가 아는 많은 물리 개발자의 책상 위에 있다. 그의 작품에 대한 좋은 introduction은 Baraff and Witkin [1997]이다.
댓글 없음:
댓글 쓰기