16 Stability And Optimization

16 Stability And Optimization
우리가 이제까지 만든 물리엔진은 완벽히 쓸만하다. 그러나, 그것이 나타내듯이, 조정될 수 있는 두 가지 비판이 있다.

• 때대로, 이상한 효과들이 보인다 - 예를들어, 오브젝트들은 으깨지거나 비틀어진 것처럼 보이거나, 오브젝트들이 중력에도 불구하고 아래로 미끄러지는 것처럼 보이거나, 또는 빠르게 움직이는 오브젝트들은 믿을만하게 행동하지 않을지도 모른다.
• 매우 많은 오브젝트들의 개수에 대해, 그 시뮬레이션은 느릴 수 있다.

우리는 우리의 최종 물리엔진 구현에서 도달할 이러한 문제들을 다룰 수 있다, 다양한 범위의 게임에서 사용되기에 충분히 강력하고 튼튼한 것. 이 책의 나머지 챕터들은 엔진을 적용하거나 확장시키는 방법들을 보지만, 이 챕터에서, 우리는 우리의 구현을 안정되고 빠른 시스템으로 광내는 것을 목표로 한다.

16.1 Stability

우리의 엔진에서 안정성 문제들은, 모든 게임 소프트웨어에서 그렇듯이, 몇 가지 방향으로부터 발생한다:

• 합리적으로 개별적으로 행동하는 다른 소프트웨어 사이의 좋지 않은 interactions
• 사용된 방정식의 부정확성 또는 우리가 만든 가정의 부정적인 효과
• 컴퓨터에 의해 수행되는 수학의 내재된 부정확성

이러한 안정성 문제는 시각적으로 잘못된 행동을 통해 명백해질 수 있다, 알고리즘들은 때대로 작동하지 않고 , 심지어 갑자기 망한다.

특히, 물리엔진에 대해, 너가 거의 개발동안 보도록 보장되는 몇 가지 흔한 bugbears가 있다: 갑작스럽고, 예상치못ㅎ산 움직임 - 한 오브젝트가 땅에서 도약할 때, 예를들어 - 오브제트들이 사라진다. 코드는 이러한 중요한 문제들 중 어떠한 것도 보여주지 않을 것이지만, 너가 만약 변화하고 수정하기전에 둘 다를 만날지도 모른다.

우리에게 남아있는 안정성 문제들은 좀 더 작을 것이지만, 그것들의 원인은 모두 세 가지 카테고리에 들어간다. 조심히 그 엔진을 테스트하여, 나는 상대적으로 쉬운 안정성 fixes를 가진 5개의 문제들을 확인했었따.

• Transform 행렬들은 잘못 형성될 수 있고, 회전과 평행이동 외에도, skews를 수행할 수 있다.
• 빠르게 움직이는 오브젝트들은 가끔씩 충돌에 이상하게 반응한다 (이것은 충돌이 실제로 탐지되는 것과 독립적이다: 빠르게 움직이는 오브젝트는 충돌이 탐지되는 것 없이 또 다른 오브젝트를 통과해서 지나갈 수 있다.)
• 경사가 있는 평면에서 resting하는 오브젝트들은 (또는 경사진 표면이 있는 또 다른 오브젝트 위에서 resting하는), 느리게 미끄러지는 경향이 있따.
• rapid successing에서 높은 스피드의 충돌의 한 쌍을 경험하는 오브젝트들은 갑자기 땅을 관통할 수 있다.
• 그 시뮬레이션은 크고 작은 양이 섞여있을 때 비현실적으로 보일 수 있다: 크고 작은 질량, 크고 작은 속도, 크고 작은 회전, 등등.

이러한 안정성 문제에 대해 고치는 것들은 나의 테스트가 발생시킨 이상한 행동들을 해결했다. 물론, 어떠한 테스트도 철저하지는 않을 것이다. 나는 몇 가지 새로운 이슈 또는 에러를 눈치채기전에 몇년간 물리 시스템을 사용했다.

모든 소프트웨어 유지에 대해, 너는 결코 몇 가지 변화가 언제 만들어질 필요가 있다는 것을 모른다. 그리고 같은 이유로, 너가 너의 엔진에 작동시키는 테스트 시나리오의 복사본을 유지하는 것은 좋은 아이디어이다. 그래서 너는 뒤로 돌아갈 수 있고, 너의 새로운 향상이 어떠한 것도 망가뜨리지 않았는지를 점검할 수 있따.

16.1.1 Quaternion Drift

Transform 행렬들은 rigid bodies의 위치 벡터와 방향 쿼터니언으로부터 생성된다. 두 position과 orientation은 (사실, 수학적 조작에 참여하는 모든 값들) 처리되는 동안 numerical errors를 겪는다.

위치 벡터에서의 에러들은 한 오브젝트를 잘못된 장소에 둔다. 이것은 보통 어떤 잛은 시간 주기에서 눈치챌 수 없는 작은 에러이다. 만약 그 위치가 느리게 충분히 변한다면, 그 viewer는 어떠한 에러도 눈치채지 못할 것이다.

그 같은 것이 어느정도로 orientation vector에도 해당한다. 그러나 추가 문제가 있따: 우리는 쿼터니언에서 부가적인 자유도를 갖는다. 만약 그 4개의 쿼터니언 컴포넌트들인 sync가 맞지 않다면 (즉, 만약 그 쿼터니언들이 더 이상 표준화 되지 않는다면)그러면 그것은 어떻나 유효한 방향에 부합하지 않을지도 모른다. 우리의 엔진에서 어떠한 코드도 특히 이것에 민감하지 않지만, 오브젝트들이 시각적으로 squashed 되도록 유발할 수 있따. 우리가 chapter 9에서 보았듯이 그 솔루션은 그 쿼터니언을 renormalize 하는 것이다. 만약 우리가 할 필요 없다면, 그것은 시간 낭비기 때문에 이것을 하길 원하지 않는다.

나는 쿼터니언이 velocity에 의해 업데이트 된 후에, 그리고 transform matrix가 만들어지기 전에, rigid-body update routine에서 쿼터니언 표준화 단계를 추가했었다. 이것은 그 transform matrix가 유효한 회전 컴포넌트를 갖는 것을 보장한다.

나는 이 안정성 fix가 조금 성사된 것을 인정한다. 내가 처음에 integration routine을 썼을 때 쿼터니언 표준화에 대해 그것은 좋은 장소인 것이 나에게 명백한 것처럼 보였다. 그래서 나는 그것을 추가했다.

나는 그것을 여기 예증의 방식으로 포함했다. 그 쿼터니언의 normal size는 우리가 엔진의 개발 초기에 했던 가정이다. 그것은 쉽게 잊혀지고, 우리가 완전한 엔진을 오랜 시간 동안 작동시킨 후에 이상한 효과들을 발생하는 것으로 돌아올 수 있다. 문제들은 나타날지도 모른다, QA testing 동안에, 그리고 그것들은 미세할 수 있따. 너의 가정을 성능을 해치지 않는 방식으로 체크하고 강화하는 것은 안정성에 대한 열쇠이고, 그 엔진을 최적화하는 열쇠이다.

16.1.2 Interpenetration On Slopes

다음 문제는 좀 더 중요하다. 그림 16.1은 경사에서 resting하는 한 블럭을 보여준다. 그 경사는 기울어진 평면 또는 또 다른 오브젝트의 평면이 될 수 있다. 중력은 아래 방향으로 작용한다.

rigid bodies의 한 번의 업데이트 후에, 그리고 충돌 resolution이 수행되기 전에, 그 오브젝트들은 평면으로 조금 떨어진다. 이것은 그림의 두 번째 부분에서 보여진다. 그 평면 contact는 그 오브젝트의 움직임과 다른 방향이기 때문에, 그 interpenetration resolution은 그 블락이 위치에서 벗아나게 한다, 그림의 세 번째 부분에서 보이듯이. 시간에 따라, 높은 마찰에도 불구하고, 그 블럭은 경사아래로 조금씩 내려갈 것이다.

이것은 우리가 chapter 15의 끝에서 보았던 것과 유사한 문제이다. 그 drifting이 다른 contacts 사이의 상호작용에 의해서 발생한다는 점에서. 이 경우에, 어떠한 interaction도 없다: 같은 것은 오직 하나의 contact만을 가진 오브젝트들에게 발생한다. 그것은 그러므로 해결하기에 더 쉽다.

그 솔루션은 그 contat의 relative velocity의 계산에 놓여있따. 우리는 contact plane에서 forces에 의해 축적되는 어떤 velocity를 제거하고 싶다. 이것은 그 오브젝트가 contact normal의 방향으로 slope안으로 움직이게 하지만, 그것을 따라서 움직이게 하지 않는다.

이것을 하기 위해서, 우리는 calculateLocalVelocity method에 가속도에 의한 속도의 계산을 추가한다:

그 코드는 가속도를 찾고, 그것을 duration을 곱하는데, rigid-body integration step에서 도입된 velocity를 찾기 위해서이ㅏㄷ. 그것은 이것을 contact coordinates로 변환하고, contact normal의 방향에 있는 컴포넌트를 제거한다. 그 resulting velocity는 contact velocity에 더해지고, velocity resolution에서 제거된다. 그렇게 할 충분한 마찰이 있다면. 만약 충분한 마찰이 없다면, 그러면 그 오브젝트는 정확히 그것이 그래야 하듯이 경사아래로 미끄러질 것이다.

16.1.3 Integration Stability

이 강화는 몇 가지 배경 설명이 필요하다, 그래서 우리는 chapter 3과 10의 적분 알고리즘으로 돌아갈 것이다.

파티클과 rigid bodies 둘 다에 대해, 나는 같은 적분 알고리즘을 사용했었따. 그것은 linear and angular acceleration을 계산하고, velocity와 rotation에 이러한 것들을 적용한다, 그리고 그것들은 차례로 position과 orientation에 적용된다. 이 적분 알고리즘은 Newton-Euler 라고 불려진다. 뉴턴은 linear component를 언급했고 (그것은 Newton의 운동 법칙에 기반을 둔다), Euler는 angular component를 언급했다 (오일러는 회전의 우리의 이해에 중요한 수학자였다).

우리의 integrator는 다음의 방정식들을 쓴다

(그것들의 회전의 동등한 것에 따라), 그것들 각가은 오직 미분의 한 단계를 의존한다. 그러므로 그것들은 "first-order"라고 이름 지어진다. 그 전체 방법은 좀 더 완전히 "first-order Newton-Euler" 또는 Newton-Euler 1이라고 불려진다.

Newton-Euler 2

우리가 chapter 3에서 보았듯이, Newton-Euler 2는 근사이다. 고등학교 물리에서, 방정식

이것이 가르쳐진다. 이것은 미분의 두 단계에 의존한다. angular updates에 대해 동일한 식과 함께, 우리는 second-order Newton-Euler integrator를 갖는다.

Newton-Euler 2는 Newton-Euler 1보다 더 정확하다. 그것은 업데이트된 position을 결정할 때 가속도를 고려한다. 우리가 chapter 3에서 보았듯이, 그 t^2 항은 높은 프레임 율에 대해 너무 작아서, 우리는 그 가속도 항을 무시하는게 낫다. 그러나 이것은 가속도가 매우 클 때 사실이 아니다. 이 경우에 그 항은 중요할지도 모르며, Newton-Euler 2로 이동하는 것은 매우 이익이 될 수 있다.

Runge-Kutta 4

두 개의 Newton-Euler integrators는 가속도가 전체 업데이트 동안 상수로 남아 있을거라고 가정한다. 우리가 chapter 6에서 보았듯이, 우리가 스프링들을 볼 때, 가속도가 update의 과정동안에 변하는 방식은 매우 중요할 수 있다. 사실, 가속도가 변하지 않는다는 것을 가정하여, 우리는 극적인 불안정성과 시뮬레이션의 완전한 고장에 들어갈 수 있다.

스프링들은 가속도가 빠르게 변할 수 있는 유일한 것은 아니다. 몇 가지 resting contacts의 패턴들 (특히, simultaneous velocity resolution algorithm이 사용될 때) 은 유사한 효과를 가질 수 있고, 오브젝트 stack의 vibration 또는 dramatic explosion을 이끈다.

두 문제에 대해, 부분적인 솔루션은 중간 단계에 필요한 가속도를 처리하는 것에 놓여이 ㅆ다. 그 fourth-order Runga-Kutta algorithm (or 간단히 RK4)는 이것을 한다.

만약 너가 물리엔진에서 그것을 읽게 된다면, 너는 Runga-Kutta 적분의 언급을 볼 것이다. 나는 몇 개발자들이 성공적으로 꽤 그것을 사용하는 것을 안다. 개인적으로 나는 그 필요성을 가진 적이 없었다. 그것은 Newton-Euler보다 훨씬 더 느리고, 그 이익은 경미하다. 그것은 매우 stiff springs를 다룰 때 가장 유용하지만, 우리가 chapter 6에서 보았듯이, 그 같은 행동을 fake하는 더 간단한 방법들이 있다.

그러나, RK4가 가진 가장 큰 문제는, 그것은 step의 중간에 full set of forces를 요구하는 것이다. collision resolution system과 결합 할 때, 이것은 매우 더러워질 수 있다. 우리의 경우에, 우리는 직접적으로 contacts에 의한 forces를 결정하지 않는다. 우리는 full collision detection routine을 중간 단계에 작동시키길 원하지 않는다. 그래서 RK4는 제한되어 사용 될 수 있다. 심지어 force-based engines에 대해, mid-update forces를 계산하는 것의 추가 오버헤드는 큰 성능 타격을 준다.

나는 개발자들이 rigid-body update를 위해 RK4를 사용하고, 그러고나서 끝에서 개별적인 collision resolution step 하는 것을 봤다. 이것은 쉽게 우리의 엔진에서 rigid body의 integrate 함수를 대체하여 구현될 수 있따. 불행하게도, collision resolution이 참여하지 않고, RK4는 대부분의 그것의 힘을 잃고, 나는 그 결과가 만약 너가 stubborn spring problems를 가질 때에만 오직 유용하다고 느낀다.

16.1.4 The Benefit of Pessimistic Collision Detection

우리의 엔진에 있는 모든 수학들을 제한된 수학적 정확도를 가지고 수행된다. Floating-point numbers들은 두 부분으로 저장된다 : 일련의 significant digits ("mantissa"라고 불려지는)와 exponent. 이것은 매우 다른 크기를 가진 수들이 다른 정확도를 가진다는 것을 의미한다.

일반적인 floating-point numbers에 대해 (즉, 32bit on 32bit machine), 1에 0.00001을 더하는 것은 너에게 정확한 답을 아마 줄 것이다; 그러나 10,000,000,000에 0.0001을 더하는 것은 그렇지 않을 것이다. 너가 매우 다른 스케일의 수를 포함한 계산을 가질 때, 그 효과는 매우 안좋을 수 있다. 예를들어, 만약 너가 한 오브젝트를 조금 움직이고, 그것이 원점에 가까울 때 (즉, 그것의 좌표가 0에 가깝다), 그 오브젝트는 정확히 움직여질 것이다. 만약 너가 그 같은 오브젝트를 같은 거리로 움직이지만, 그것이 원점에서 멀리있다면, 그러면 너는 어떠한 움직임도 없거나 또는 너무 큰 움직임을 가질 것이다, 너의 수학적 연산의 순서에 의존하여.

너가 넓은 범위의 질량, 속도 또는 위치를 가진 물리엔진을 사용할 때, 이것은 한 문제가 될 수 있다. 시각적으로 그것은 땅으로 가라앉은 오브젝트부터 또는 효과를 갖지않는 충돌, 갑자기 사라지는 bodies와 완전히 잘못된 방향으로 발생하는 충돌까지 다양하다. 충돌 탐지 알고리즘에서 또한 흔한 문제이다. 거기에서 오브젝트들은 그것들이 떨어져 있을 때 닿고있다고 보고되어질 수 있다. 역으로도.

이 문제에 대한 명백한 솔루션은 없지ㅏㅁㄴ, 너는 수행될 수학의 정확성을 증가시킬 수 있따. C++에서, 너는 floats를 doubles로 바꿀 수 있다, 그런데 그것은 두 배의 메모리 양을 차지하고, 처리 시간의 두 배보다 작게 걸리지만, 몇백만 배의 정확성을 갖는다.

나는 엔진의 정확성을 다루는 코드를 precision.h file에 두었다. 이것은 real data type을 정의하는데, 그것은 모두 floating-point numbers를 위해 사용된다. 그 real data type은 float 또는 double로 정의될 수 있다. data type 뿐만 아니라, 나는 몇 가지 표준 C 라이브러리에서의 수학 함수에 대한 aliases를 주었다. 이러한 것은 정확한 precision version을 호출하기 위해 재설정될 필요가 있다.

그 단일 정밀도 코드는 지금까지 써왔다. double precision mode에서 컴파일 할 때, 이러한 정의는 다음과 같이 된다.

너는 이 코드를 precision header에서 볼 수 있다, 너가 필요한 정의를 선택하기 위해 ifdef가 있는.

나는 기본적으로 double precision으로 컴파일하는 경향이 있따. PC에서, 퍼포먼스 타격은 상대적으로 작다. 매우 강하게 32-bit인 콘솔에서, 그 64-bit 수학은 매우 느리다 (그것들은 하드웨어보다는 소프트웨어에서 수학을 수행한다, 그래서 대부분의 경웨 두 배 더 느리다), 그래서 단일 정밀도가 중요하다. 유사한 질량, 낮은 속도, 그리고 원점 근처의 위치를 가진 오브젝트들에 대해, 단일 정밀도는 완벽히 사용하기에 좋다. CD에서 데모 프로그램들은 둘 중 하나의 정밀도에서 다 잘 작동한다.

16.2 Optimization

우리의 엔진의 중요한 문제들을 안정화 한 후에, 우리는 우리의 관심을 최적화로 돌릴 수 있다. 현명한 프로그래밍 격언이 있다: 항상 premature(시가상조의) 최적화를 피해라. 이 격언이 게임에서 보다 더 중요한데가 없다.

게임 개발자로서, 우리는 빠르고 효율적인 코드에 대한 압박적인 필요성을 가지고 있고, 이것은 너가 너가 쓴 코드를 최적화하하는데 박차를 가할 수 있다. 이것은 어느정도로 중요하지만, 나는 그 최적화가 많은 양의 프로그래밍 시간을소비하고, 결국에는 코드 성능에서 무시할만한차이를 만들어내는 많은 경우들을 보아왔다. 모든 코드 최적화와 함께, 프로파일러를 가지고, 무엇이 느리고, 왜 느린지를 아는 것이 중요하다. 그러고나서, 너는 burning time보다는 성능을 개선할 문제에 집중할 수 있다.

이 책에서 보여지는 엔진은 최적화에 대한 많은 기회들을 갖는다. 몇 번 계산되는 양들, 낭비되는 데이터 저장공간, 그리고 축약되거나 최적화될 수 있는 관련없는 계산들이 있다. 이 책을 위해서 구성된 엔진 버전은 성능을 위해서 완전히 최적화 되기보다는 가능한한 명백하고 간결해지는 것이 의도된다.

이 섹션의 끝에서, 나는 스피드 또는 메모리 layout을 위해서 개선되어질 수 있는 몇 가지 영역들을 간단히 볼 것이다. 나는 좀 더 복잡한 것들의 세부사항에 대해서 하지 않을 것이지만, 만약 너의 프로파일러가 너에게 그것이 도음이 될 것이라고 말한다면 그것들을 exercise로서 남겨놓을 것이다.

우리가 처음에 그러한 극적인 효과를 전반 성능에 가질 수 있는 한 가지 주된 최적화가 있는데, 그것은 세부적으로 볼 가치가 있다. 이것은 코드 최적확가 아니라 (그것이 좀 더 효율적인 방식으로 같은 것을 하지 않는다는 의미에서), 물리엔진의 작업량을 줄이는 global optimization이다.

16.2.1 Sleep
가장 빠른 폴리곤들은 너가 그리지 않는 것들이라고 그래픽스 엔진 프로그래밍에서의 속담이 있다. 빠르게 어떤 오브젝트들을 사용자가 볼 수 있는지 결정하고, 그러한 것들만 렌더링하는 것이 렌더링 기술의 주된 부분이다. 이 목적을 위해 사용되는 수십개의 공통된 기법드링 있따 (우리가 이 책에서 본 것들도 포함하여, BSP트리와 quad-trees 같은).

우리는 정확히 물리에서 같은 것을 할 수 없다: 만약 그렇지 않는다면, 만약 그 플레이어가 멀리바라보고, 뒤로 바라본다면, 오브젝트들은 정확히 그것들이 마지막에 본대로 되어있을것이다, 비록 그것이 mid-collaps일지라도. 물리 엔진에 대한 동등한 최적화는 안정되고 움직이지 않는 오브젝트들을 재현하는 것을 피하는 것이다. 사실, 이것은 일반적인 시뮬레이션에서 대다수의 오브젝트들을 수반한다. 오브젝트들은 안정된 환경에 고정되는 경향이 있을 것이다: 땅에서 resting하거나 그것들의 스프링들이 평형점에 있다거나. drag 때문에, 일관된 force의 input을 갖는 시스템들만이 고정시키는 것에 실패한다 그러나, 그 힘은 중력일지도 모른다 - 무한히 긴 경사를 굴러내려가는 한 공은 결코 멈추지 않을 것이다, 예를들어).

rest상탵의 오브젝트들의 시뮬레이션을 멈추는 것은 그것들을 "sleep"들게 한다고 불려진다. 강력한 sleep system은 평균 게임 수준에 대해, 수백배로 한 물리 시뮬레이션의 성능을 향상시킬 수 있다.

sleep system에 대해 두 가지 컴포넌트들이 있다: 오브젝트들을 sleep하게 하는 한 알고리즘과, 그것들을 다시 깨우는 다른 알고리즘. 우리는 그것들을 지원하는 몇 가지 기본 구조를 제자리에 넣은 후에, 그 둘 다를 볼 것이다.

Adding Sleep State
sleep을 지원하기 위해, 우리는 RigidBody class에 세 가지 데이터 멤버들을 추가할 필요가 있다:

• isAwake는 우리에게 그 body가 현재 잠들었는지 말해주고 그러므로 그것이 처리될 필요가 있는지를 말해주는 boolean 변수이다.
• canSleep은 그 오브젝트가 잠에 들 수 있는지를 말해주는 boolean 변수이다. 사용자의 끊임없는 통제하에 있는 오브젝트들 (즉, 사용자는 그것들에 언제든지 힘을 추가할 수 있다)은 아마도 sleeping 되는 것이 방지되어야만 한다, 성능의 이유보다는 비쥬얼을 위해.
• motion은 그 오브젝트의 현재 movement speed를 추적할 것이다 (linear and angular둘 다). 이것은 그 오브젝트가 잠에 들어야 하는지 아닌지를 결정하기 위해 중요하다.

RigidBody class에서,이것은 다음으로 구현된다.

우리가 rigid-body update할 때, 우리는 body를 체크하고, 그것이 잠들어 있다면 처리하지 않고 반환한다:

그 충돌 탐지기는 여전히 잠들어 있는 오브젝트들 사이의 contacts를 반환해야한다, 우리는 이 섹션의 나중에 볼 것이다. 이러한 dormant collisions는 stack에 있는 한 오브젝트가 깨어있는 body로부터 knock을 받을 때 중요하다.

생성될 충돌에도 불구하고, 두 오브젝트들이 잠들어 있을 때, 그것들은 어떠한 velocity나 rotation이 없다. 그래서 그것들의 contact velocity는 0이 될 것이고, 그것들은 velociy resolution algorithm에서 생략될 것이다. 그 같은 것은 interpenetration과도 발생한다. 이것은 collision response system에서 속도 향상을 제공한다.

우리는 RigidBody class에 한 오브젝트의 isAwake member의 현재 상태를 바꿀 수 있는 메소드를 추가할 필요가 있다.

이 코드는 isAwake의 현재 값을 toggles한다. 만약 그 body가 sleep에 들어가져 있다면, 그것은 어떠한 motion이 없다는 것을 보장한다: linear and angular velocity 둘 다 0으로 설정된다. 이것은 (우리가 이전에 보았듯이) 충돌들이 어떠한 closing velocity를 갖지 않도록 보장하고, 이것은 contact에 있는 sleeping bodies에 대한 성능을 개선한다.

만약 body가 깨어있다면, 그러면 그 motion 변수는 한 값이 주어져있다. 우리가 다음 섹션에서 보게 되듯이, 한 오브젝트는 이 motion값이 어떤 threshold아래로 떨어질 때 sleep에 들게 된다. 만약 이 변수 값이 그 threshold 아래이고 그 오브젝트가 깨어나져 있으면, 그것은 다시 즉시 잠들 것이다. 그것에게 threshold의 두 배의 값을 주는 것은 이것을 예방하고, 그 오브젝트가 어떤 흥미로운 것을 할 만큼 충분히 길게 깨어있도록 보장한다 (아마, 그 setAwake method가 호출되고, 그래서 그 오브젝트는 흥미로운 어떤것을 하기 위해서 깨어나고, 곧 바로 잠들지 않는다).

마지막으로, 우리는 한 오브젝트가 잠들었는지를 점검하고, canSleep의 값을 설정하고 체크할 수 있는 함수들을 추가한다. 이러한 것들은 CD에 구현되어져있고, 그것들 어떠한 것도 여기에 있는 분석들을 요구할 만큼 충분히 복잡한 것은 아니다.

Putting Objects to Sleep
오브젝트들을 잠에 들게 하는 알고리즘은 간단하다. 각 프레임에서, 우리는 그것들의 motion을 감시한다. 그것들의 motion이 몇 프레임에 걸쳐 안정화되고, 그것들의 속도가 0에 가까워질 때, 우리는 그것들을 잠들게 한다.

"near zero"라는 것은 sleepEpsilon라고 불려지는 파라미터로 통제된다. motion data member의 값이 이 threshold 아래로 떨어질 때, 그 body는 잠에 들게 된다:

if(motion < sleepEpsilon)
{
    setAwake(false);
}

CD에 있는 코드에서, 그 sleep epsilon value는 전체 시뮬레이션 동안 공유된다. 그것은 함수들의 한쌍을 통해 접근되는 global 변수이다: setSleepEpsilon과 getSleepEpsilon. 너는 너가 원한다면, body-specific thresholds를사용해서 그 값을 미세조정할수 있다.

sleep epsilon을 설정하는 것은 trial-and-error process이다. 그 collision-handling system은 motion을 각 프레임에 있는 오브젝트들에게 도입한다. 만약 너가 sleep epsilon을 너무 낮게 설정한다면, 오브젝트들은 잠드는데 결코 실패할지도 모른다. 만약 너가 이러한 문제들을 갖지 않는 resolution system을 사용한다면, 너무 낮은 값은 도달하기에 너무 오래 걸릴지도 모른다. 만약 너가 그 값을 너무 높게 잡는다면, 그러면 명백히 움직이는 오브젝트들이 잠에 들 수 있고, 이상해 보일 수 있다. 나는 이상한 mid-motion freezes가 명백해지기 전에 가능한한 높게 나의 sleep threshold를 설정하는 경향이 있다.

그 알고리즘은 간단하지만, 그것은 motion의 값을 계산하는데 의존한다. 그 motion 값은 그 오브젝트의 linear and angular velocity를 단일 스칼라에 캡슐화할 필요가 있다. 이것을 하기 위해서, 우리는 그 오브젝트의 total kinetic energy를 사용한다. chapter 3에서, 우리는 한 파티클의 kinetic energy가 다음으로 주어진 것을 보았다



여기에서 m은 body의 질랴이고, dot(p)는 그것의 linear velocity이다. 한 유사한 식이 회전하는 rigid body의 kinetic energy에 대해 유효하다:



여기에서 i_m은 그 몸의 회전축에 대한 관성모멘트이고 (즉, 그것은 스칼라 양이다), dot(theta)는 그것의 angular velocity이다.

우리는 motion에 대한 값으로서 그 kinetic energy를 사용할 수 있지만, 그것은 다른 질량과의 한 문제를 만들 것이다: 두 개의 동일한 오브젝트들은 그것들의 질량에 의존하여 다른 시간에 잠들 것이다. 이것을 피하기 위해서, 우리는 다음을 얻기위해 식으로부터 질량을 제거한다



코드에서 이것은 다음처럼 보인다

currentMotion = glm::dot(velocity, velocity) + glm::dot(rotation, rotation);

두 벡터의 스칼라곱은 그것들의 길이가 서로 곱해진것과 같고, 그것들 사이의 각의 코사인으로 곱해진 것이기 때문이다. 만약 우리가 한 벡터의 스칼라 곱 자체를 받아들인다면, 그 코사인은 1이다. 그리고 그 결과는 그 벡터의 길이의 제곱이다.

몇 개발자들은 이것에 대한 변형을 사용한다: 그들은 그것들을 제곱하지 않고 두 컴포넌트들을 함께 더하거나, full kinetic energy를계산하고, 그러고나서 질량으로 나눈다.

둘 중 하나의 경우에, 이것은 우리에게 그 오브젝트에 대한 motion값을 준다. 최종 단계는 이 값이 안정적인지를 점검하는것이다. 우리는 몇 프레임에 걸쳐 현재 모션의 기록을 유지하고 그것이 얼마나 변하는지를 봐서 이것을 한다. 이것은 recency-weighted average(RWA)에 의해 깔끔히 추적된다. 그것은 프로그래밍 레파토리에서 가장 유용한 도구중의 하나이다.

recency-weighted average는 다음으로 업데이트 된다

rwa = bias * rwa + (1 - bias) * newValue;

그것은 지난 몇 개의 값들의 평균을 추적한다, 좀 더 최근의 값들을 좀 더 중요성을 가지고. 그 bias parameter는 이전 값에 비해 얼마나 중요한지를 통제한다. 0의 bias는 그것이 업데이트 될 때마다 RWA에가 새로운 값과 같게 만든다. (즉, 어떠한 평균도 없다). 1의 bias는 새로운 값을 전적으로 무시한다.

그 RWA는 입력을 smoothing하거나, 입력이 안정화되었는지를 체크하는 훌륭한 장치이다. 우리의 경우에 대해, 우리는 다음을 갖는다

motion = bias * motion + (1 - bias) * currentMotion;

만약 currentMotion이 sleep epsilon value 아래로 떨어지지만, 이전 몇 개의 프레임에서 그 오브젝트가 많은 양을움직이고 있다면, 그러면 그 전체 motion value는 여전히 높을 것이다. 한 오브젝트가 잠깐의 시간을 소비할 때, 움직이지 않는것은 recency-weighted average를 epsilon value 아래로 떨어지게 할 것이다.

오브젝트들은 매우 high speeds로 움직일 수 있기 때문에 (그리고 우리가 이러한 속도들의제곱으로 작업하고 있기 때문에), speed의 brief burst는 RWA를 매우 높게 만들수 있고,그것이 합리적인 levels로 돌아오게 하는데 오랜 시간이 걸릴 것이다. 이것을 방지하기 위해, 그리고 오브젝트들이 더 빠르게 잠드는 것을 허용하기 위해, 나는 RWA의 값을 제한하는 코드를 추가했다:

if (motion > 10 * sleepEpsilon) motion = 10 * sleepEpsilon;

RWA의 bias는 frame의 duration에 의존적이여야 한다. 더 긴 프레임에대해서, 현재 값이 RWA에 더 짧은 프레임보다 더 많이 영향을 미치도록 해야한다. 만약 그렇지 않다면, 오브젝트들은 더 빠른 프레임 율에서 더 빠르게 잠이 들 것이다.

우리는 이것은 우리가 damping에 대해 했던 것과 같은 방식으로 할 수 있다.

real bias = real_pow(baseBias, duration);

여기에서 baseBias는 우리가 one-second frames에대해 기대하는 bias이다. 나는일반적으로 0.5 ~ 0.8의 값을여기서 사용하지만, 또 다시 몇 가지 실험이 필요하다.

Waking Objects Up
우리는 이미 오브젝트들이 수동으로 깨워질 수 있는 것을 보았었다. 우리는 또한 그것들이 새로운 충돌에 반응해야만 할 때, 오브젝트들을 깨울 필요가 있다. 우리가 보았듯이, 잠자는 오브젝트들 사이의 충돌들은 생성되고, 자동적으로 collision resolution system에 의해 무시된다.

한 새로운 오브젝트 (예를들어 플레이어 또는 발사체)가 따라 오고, 잠자는 오브젝트와 충돌할 때, 우리는 그 충돌에 의해 영향 받을 수 있는 모든 오브젝트들이 깨어나기를 원한다. 어떤 특정한 충돌에 대해, 이것은 만약 연관된 한 body가 잠들어 있고, 다른 것이 깨어있다면, 그러면 그 잠자는 body가 깨어질 필요가 있다는 것을 의미한다. 우리는 이것을 하기 위해 Contact class에 한 method를 추가한다:


이 메소드는 우리가 collision을 resolve를 막 하려할 때 마다 호출된다. sleeping object와 awake object사이에 발생하지만 고려되어지지 않고있는 충돌들은 그 자고있는 오브젝트들이 깨어나는 것을 요구하지 않는다. 만약 그 contact가 resolve될 필요가 있을 만큼 충분히 severe하지 않다면, 우리는그것이 그 잠자는 오브젝트를깨울만큼 심각하지 않다고 가정할 수 있다.

만약 우리가 연쇄된 일련의 collisions들을 가진다면, 그림 16.3에서 보이듯이, 그 첫 번째 충돌들은 object B를 깨워서 처리될 것이다. 그러고나서 그 velocity update algorithm은 그 두 번째 contact가 해결될 필요가 있는지, object C를 깨울 필요가 있는지를결정한다. 등등. 결국에 속도 또는 position change가 필요한 모든 오브젝트들은 깨어날 것이다, 요구되는대로.

contact resolver의 adjustPositions와 adjustVelocities 메소드들은 그것들이 단일 contact에 resolution을 수행하기전에, 그호출이 더해지도록한다. 여기에서 penetration resolution에 대한 축약된 코드가 여기 있다.

우리가 한 rigid body를 깨울 필요가 있는 두 번째 상황이 있다. 그것은 한 force가 그것에 적용될 때 이다 (항상 존재하는 힘을제외하고, 중력같은). 이것은 수동으로 처리될 수 있다, 한 force가 적용될 때 마다 setAwake 호출을 더해서. 그러나 이것은 기억하기에 어렵다. 그래서 나는 한 force or torque가 적용될 때 마다 그 오브젝트를 자동으로 깨우는 것을 선택했다. RigidBody class에 있는 addForce, addForceAtPoint, 그리고 addTorque 함수들은 자동적으로 setAwake를 호출한다.

우리는 이제 완전히 functinoal sleep system을 가진다, 이것은 극적으로 엔진의 성능을 개선할 수 있다.

일반적으로, 게임 level이 로드되었을 때, 모든 rigid bodies는 그것들이 그것들의 rest position에 있도록 배치된다. 그것들은 그러고나서 게임이 시작할 때 모두 sleep으로 설정될 수 있다. 이것은 물리 시뮬레이션 코드를 정말로 빠르게 만든다. 오브젝트들은 물리 시뮬레이션을 그것들이 충돌되고나서야 요구한다. 심지어 그때, 우리가 희망하듯이, 그것들은 또 따른 equilibrium position에 도달할 것이고, sleep으로 빠르게 돌아갈 것이다.

16.2.2 Margins of Error For Penetration And Velocity
 만들 가치가 있는 또 다른 최적화는 penetration과 velocity resolution algorithm을 극적으로 속도를 향상시키는 것이다. 그림 16.4는 우리의 이제 평면 위에 있는 블럭의 상황을 보여준다. 만약 우리가 이 시뮬레이션을 작동시키고, 수행되는 resolution을 바라본다면, 우리는 두 개의 contacts들 (3D 시뮬레이션에서는 4개) 가 반복적으로 고려되는 것을 본다. penetration을 취하여, 만약 우리가 각 iteration에서 penetration depths를 본다면, 우리는 (그림에서 보여지듯이) 그 첫 번째 penetration resolution이 우리를 거의  올려놓고 그러고나서 나중의 resolutions이 그것들이 한 플레이어에 의해 보여질 수 없는 아주 작은 adjustments를 만드는 것을 볼 수 있다. 이러한 종류의 sub-visual adjustment의 종류는 순수한 시간 낭비이다.

이 상황을 피하기 위해서, 우리는 velocity와 penetration collisions의 tolerance limit을 추가할 수 있따. 이 limit보다 더 좀 더 심각한 충돌만이 고려될 것이다. 그 방식으로 한 contact가 resolved되는 처음에, 그것은 limit  안으로 가져와져야하고, 그러고나서 결코 재 고려되어서는 안된다, 만약 다른 contact의 resolution이 그것을 크게 건드리지 않는한.

이 limit은 우리가 고려할 가장 severe contact를 찾을 때 간단히 구현되어질 수 있다. 0의 worstPenetration value로 시작하기보다는 오히려 (chapter 14의 코드인), 우리는 우리가 허용하는 tolerance와 동일한 값에서 시작한다:

그 상황은 velocity에 대해서 유사하다. 이제 이 epsilon value보다 아래에 있는 penetration을 가진 어떠한 contact도 선택되지 않을 것이다.  이 값은 충분히 작아서 그 contact가 쉽게 플레이어에 의해 눈치챌만하지 않아야 한다. 그 contact가 resolved되는 처음에, 그 resolution은 그 contact의 penetration을 이 limit 아래로 가져와야한다, 그래서 그것은 다시 고려되지 않을 것이다. 다시 Tuning은 필수적인 것이다. 데모에 대해, 나는 각각에 대해 0.01의 값을 사용했다. 만약 너의 오브젝트들이 더 크거나 더 빠르다면, 그러면 더 높은 값들이 사용되어야 한다. 만약 그것들이 더 작거나, 더 느리다면, 그러면 더 낮은 값을 사용해라.

velocityEpsilon과 penetrationEpsilon 값들 둘 다 collision resolver class의 properties이다. 코드에서 나는 그것들의 현재 값을 설정하고 얻는 메소드들을 포함했다.

내가 이 간단한 변화를 엔진에 추가했을 때, 나는 즉시 5배정도의 speed-up을 얻었다.  복잡한 오브젝트들의 stacks에 대해, 그 개선은 심지어 훨씬 중요했다.

sleep system과 이 tolerances 쌍 사이에서, 우리는 real production work에 대해 충분히 빠른 물리 시뮬레이션을 갖는다. 이후의 최적화는 code manipulation와 speed에 대한 memory tradeoff 의해 물리코어에서 얻어질 수 있다. 나는 이 섹션의 마지막에서 그것에 대해 간단히 몇 가지를 말할 것이다.

그러나, contacts와 collisions가 탐지되고 다뤄지는 방법과 관련하여 중요한 성능 문제가 남아있다.

16.2.3 Contact Grouping
chapter 14에서, 나는 성능이 contacts의 그룹을 batching하여 개선되어질 수 있다고 언급했다. 우리의 엔진에 대해서, 이것은 유용항 속도 향상을 제공한다. simultaneous resolution을 하는 엔진들에 대해, 그 속도 향상은 중요할 수 있다.

그림 16.5는 간단한 장면을 보여준다. 씬에서 몇 가지 contacts들이 있는데, 충돌 탐지기에 의해서 생성되었따. collision resolution system에서, contacts A, B, and C가 모두 서로에게 영향을 줄 수 있다: contact A를 해결하는 것은 contact B와의 문제를 일으킬 수 있다, B를 해결하는 것은 A와 C 둘 다에 영향을 미칠 수 있따. Contacts D와 E는 마찬가지로 관련되어 있다. 그러나, A, B, and C가 D, E, 또는 F에 영향을 줄 수 없다는 것에 유의해라; D와 E는 A,B,C에 또는 F에 영향을 줄 수 없다; F는 어떠한 다른 것에도 영향을 줄 수 없다.

사실, 두 개의 contacts들은 만약 그것들이 일련의 rigid bodies와 다른 contacts를 통해 연결된다면 오직 서로에게만 영향을 줄 수 있다. 그래서 contact A와 C는 서로에게 영향을 줄 수 있다. 왜냐하면 그것들이 bodies 2와 3 그리고 contact B를 통해 연결되어있기 때문이다.

우리의 resolution algorithm은 그것들이 이전의 resolution에 영향을 받았는지를 보기 위해 모든 가능한 contacts들을 체크한다. 그것은 또한 해결해야할 현재의, 가장 심각한 contact를 찾기 위해 모든 contacts를 통해 검사한다. 이러한 연산들은 더 긴 contacts의 lists에 대해 더 오래 걸린다.

더 좋은 솔루션은 contacts를 groups으로 해결하는 것이다. Contacts A, B, and C는 처음에 resolver로 보내질 수 있고; 그러고나서 D와 E가, 그러고나서 F가. 이 방식을 사용하여, 그 contact resolver는 contacts D와 E를 A, B, and C의 해결하는 것의 결과를 기반으로 변경하는 방법을 갖지 않는다. 그러나 이것은 괜찮다, 왜냐하면 우리는 이러한 contacts들이 가급적 상호작용할 수 없다고 알기 때문이다.

이 batching은 일반적으로 두 장소들 중 하나에서 처리된다. 그것은 contacts의 그룹을 반환하는 collision detector의 일이 될 수 있다. 또는 contacts의 전체 리스트가 collision resolution system에 의해 분리되어, batches로 처리될 수 있따.

만약 구현될 수 있다면, 그 첫 번째 접근법이 가장 좋다. 일반적으로 collision detector는 오브젝트들이 서로에게 길게 있는지를 결정하고 그것들을 batch 시킬 수 있다. 만약 그것이 coarse collision detection system을 사용한다면, 예를들어, 그것은 game level의 각 distinct area에 대해 contact batches를 생성할 수 있다. 그러나, 닿고 있지 않는 근처의 오브젝트들의 집합에 대해, 그 collision detector는 일반적으로 너무 큰 batches를 반환할 것이다 (즉, 서로에게 영향을 줄 수 없는 contacts를 포함하는 batches). 만약 그 게임 level이 많은 그러한 상황을 가진다면, 그것은 collision detection batching뿐만 아니라 resolver에 batching processor를 추가하여 성능을 개선시킬 수 있다.

batching processor는 contacts의 전체 리스트를 batches로 분리한다. 그것은 한 contact에서 시작하고, contacts와 rigid bodies의 조합을 따라서 한 batch에 있는 모든 contacts를 발견하기 위해서 이것을 한다. 이것은 그러고나서 processing을 위해 보내진다. 그것은 그러고나서 아직 한 batch에 들어가지 않은 또 다른 contact를 찾고, 또 다른 batch를 구성하기 위해 그 contacts들을 따라간다. 이것은 아직 처리되지 않은 contacts들이 있는 한 반복된다.

batching processor를 구현하는 것은 각 contact에서 관련된 rigid bodies를 빠르게 발 견할 수 있는 것을 포함하고 (우리는 벌써 contact data structure가 rigid bodies를 저장하기 때문에 그 데이터를 가지고 있다), 그리고 각 rigid body에 있는 contacts를 찾을 수 있는 것을 포함한다. 이것은 엔진의 현재 상태에서는 없다. 왜냐하면 rigid bodies는 그것들에 영향을 주는 contacts들을 추적할 수 없기 때문이다. 한 rigid body에 속하는 것들을 찾기 위해, 모든 가능한 contacts들을 탐색하는 것은 너무 오래 걸릴 거싱고, 최적화의 목적을 없앨 것이다.

챕터 14에서 우리는 contacts들의 정렬된 리스트가 보유되는 것을 허용하는 contact processing에 대한 수정을 보았었다. 그래서 그것들은 매번 정렬될 필요가 없다. 이 알고리즘의 update part에서, 한 resolution step의 효과는 그 contacts들을 통해 전파된다. 이것은  batching을 효율적으로 구현하기 위해 우리가 필요한 같은 자료구조를 사용한다: 각 rigid body에 소유된 contacts의 링크드 리스트.

16.2.4 Code Optimizations
내가 고려하고 싶은 최종 최적화 단계는 코드 최적화이다. 코드 최적화는 알고리즘을 변경하지 않지만, 그것을 좀 더 효율적으로 처리하게 만드는 tweaks이다. 소스 코드에 적용될 수 있는 다양한 범위의 코드 최적화가 있다. 나는 부가적인 성능을 더 쓰려고해서 일부러 코드를 좀 더 복잡하게 만드는 것을 피했다.

이 섹션은 몇 가지 일반 포인터를 주려고 의도된다. 그 충고는 내가 개발했던 commercial engine을 기반으로하고, cyclone이 기반이다. 너가 어떤 최적화 노력에 들어가기전에, 나는 강하게 너가 좋은 profiler를 갖는 것을 충고할 것이다 (나는 PC work를 위해 인텔의 VTune을 사용한다) 그리고 성능 문제를 유발한다고 너가 증명할 수 있는 소프트웨어의 부분만을 최적화해라.

Caching Contact Data
상대적으로 간단한 최적화는 contact resolution 동안 contact class에서 data로서 수행되는 계산을 보유하는 것이다. 한 contact를 여러번 resolve할 때, 우리는 현재 그것의 deltaVelocity와 다른 값들을 재계산한다. 이러한 것은 대신에 contact data structure에 저장되어질 수 있고, 처음에 필요할 때만 계산되어질 수 있다.

이것은 speed에 대한 memory의 tradeoff이다. 만약 너가 오직 한 번만 고려될 가능성이 높은 많은 contacts를 가진다면, 그러면 그 알고리즘을 그대로 두는 것이 더 나을지도 모른다.

Vectorizing Mathematics
다음 최적화는 PC와 대부분의 콘솔에서의 수학적 하드웨어를 이용한다 이 하드웨어는 동시에 한 개 이상의 floating-point number를 처리할 수 있다. 일련의 floating-point 연산으로서 모든 우리의 벡터와 행렬 조작을 수행하기 보다는, 우리는 그것이 전체 벡터를 한 번에 처리하도록 할 수 있다.

32-bit PC에서의 엔진의 단일 정밀도 구성에 대해 (double precision에 대해 상황이 상당히 훨씬더 복잡해지니, 우리는 그것을 무시할 것이다), 우리는 전체 벡터를 SSE 레지스터들 중의 하나에 맞출 수 있다. SSE 수학을 사용하여, 우리는 한 벡터의 행렬 transform을 오직 4번의 연산에 수행할 수 있따. 벡터 외적, 덧셈, 다른 조작들은 똑같이 가속된다. 대부분의 콘솔들 (오래된 것들은 예외이고)은  같은 facilities를 제공한다. 예를들어, 소니 플레이스테이션 2에서, 너가 같은 효과를 위해 사용할 수 있는 내장된 벡터 수학 unit이 있따.

나는 vectorizing 수학에 대해 세부적으로 들어가지 않을 것이다. 윈도우 PC를 위한 비쥬얼 스튜디오에서 이용가능한 합리적은 문서가 있고, 그 주제에 대해 온라인으로 훌륭한 introductions들이 있다. 진지한 PC 개발을 위해, 나는 인텔의 Software Optimization Cookbook [Gerber, 2002]를 추처한다 (너가 Inter processors를 타겟팅하든 아니든).

Twizzling Rigid-Body Data
PC에서 벡터 수학 하드웨어는 동시에 다양한 데이터 비트에 대해 같은 프로그램을 작동시키기 위해 최적화 된다. rigid body 당 한 알고리즘을 하기보다, 동시에 한 그룹의 bodies에 대해 같은 알고리즘을 작동시키는 것이 더 좋다.

그 rigid-body integration algorithm은 이것에 대해 특별한 후보이다. 우리는 동시에 4개의 오브젝트들을 처리하게 하여 속도 향상을 할 수 있다. 그러나, 이것을 하기 위해서, 우리는 각 rigid body에 대해 데이터가 보유되는 방법을 다시 배치할 필요가 있을 것이다.

OOP 스타일을 위해서, 우리는 한 rigid body에 대해 모든 데이터를 포함하는 클래스를 썼다. simultaneous processing을 이용하기 위해, 우리는 그 데이터를 "twizzle"한다, 그래서 그것은 함께 그룹지어진다: 한 배열에 있는 각 오브젝트에 대한 position 다음에 모든 속도들이 나온다 등등. 이것은 한 번에 4개의 rigid bodies를 보유하는 새로운 자료구조를 사용하여 성취될 수 있따.

개인적으로 나는 내가 만든 물리 엔진에서 이것을 결코 구현하지 않았다. 그러나, 내가 관련된 AI 엔진 개발 몇 가지는 이 구조를 사용했고, 4개의 캐릭터들이 한 번에 업데이트 된다.

Grouping Data For Areas of the Level
메모리 관리는 게임 기술을 최적화하는데 있어서 중요한 부분이다. 물리학에 대해 대부분의 게임 머신에서 이용가능한 많은 메모리가 있지만, 그것의 최적화는 slow-downs을 발생시킬 수 있다.

프로세섣르은 모든 메모리의 부분들에 대해 동등한 접근을 갖지 않는다. 그것들은 메인 메모리부터 data in chunks를 가지고 오고, 높은 속도의 caches에 그것을 유지한다. cache로부터 데이터를 접근하는 것은 빠르다. 만약 필요한 데이터가 cache에 있지 않다면, 그러면 그것은 메인 메모리로 부터 가져와져야만 하는데, 이것은 매우 시간을 소모할 수 있다. 다른 머신들은 다른 캐시 사이즈들을 가질 수 있고, 몇 가지는 cache의 몇 단계를 가진다.

끊임없이 새로운 데이터를 캐시로 가져오는 것을 피하기 위해, 데이터는 함께 그룹지어져야 한다. 몇 가지 게임 levels에 대해, 모든 물리 데이터는 쉽게 함께 유지되어질 수 있다. medium-size game levels에 대해, 물리 데이터가 간단히 다른 자료구조에 더해지지 않도록 하는 care가 취해져야 한다. 예를들어:

class MyObject
{
     AIData ai;
     Geometry geometry;
     Material material;
     Texture textures[4];
     RigidBody physics;
     CollisionGeometry collisionGeom;
};

MyObject objects[256];

이것은 쉽게 연속적인 오브젝트들에 대한 rigid-body data가 메모리에서 길게 늘어 뜨리도록 할 수 있다. 많은 오브젝트들 중에서 충돌들을 해결할 때, 데이터는 대부분의 resolution steps에서 캐시로 쉽게 가져와질 필요가 있을 수 있고, 이것은 재앙적인 퍼포먼스 문제들을 발생시킨다.


더 좋은 솔루션은 모든 데이터 집합들을 별개의 배열로 유지하는 것이다:

AIData ai[256];
Geometry geometry[256];
Material material[256];
Texture textures[4][256];
RigidBody physics[256];
CollisionGeometry collisionGeom[256];

큰 게임 levels에 대해, 이것은 여전히 충분하지 않을 것이다. 이 경우에, 게임 level의 다른 지역에 있는 오브젝트들이 함께 유지되도록 하기 위해, rigid bodies의 집합을 순서짓는 것은 가치가 있다. 그 방식으로, contacts가 처리될 때, 관련된 bodies는 캐시에 함께 나타날 가능성이 높다. Contacts는 서로로부터 level을 넘어서 오브젝트들 사이에서 발생되어지질 않을 것이다. 그래서 그것들은 배열에 분리되어질 수 있다.

캐시 미스는 악명높에 진단하기에 어렵다, 그리고 그것들의 prevalence는 너가 디버깅 코드를 추가하거나 겉보기에 관련없는 adjustments들을 만들 때 극적으로 변화하는 경향이 있따. 좋은 profiler가 필수적이다.

16.3 Summary

간단히 sleeping objects와 near-collisions에 대해 tolerance를 추가하여, 너는 합리적으로 효율적인 물리 엔진을 가질 것이다. 이제 그것이 몇 가지 실제 게임 프로그램에서 어떻게 사용될 수 있는지를 볼 시간이다. 만약 너가 이 책을 따라오면서 너만의 엔진을 만들고 있따면, 그것을 이제 걸어가게 할 시간이다. 만약 너의 profiler가 성능 문제를 발견한다면, 너는 이 챕터로 돌아와서 몇 가지 다른 최적화를 시도할 수 있다.

Chapter 17은 우리가 가진것을 리뷰하고, 많은 최근의 게임에서 보이는 그 주된 물리 이펙트들이 어떻게 성취되는지를 본다.