(틈틈이 물리 엔진 공부를 하자! 첫 시작은 이것 번역부터이다.)
How Physics Engines Work
Introduction, Motivation, and Goals
내 이름은 Burak Kanber이다. 나는 1999년도에 프로그래밍을 시작했으며, 2001년에 Perl로 나의 첫 MMORPG를 만들었다. 몇 년후에, 나는 명망있는 (그리고 수업료가 무료인) Cooper Union에 들어갔고, 거기에서 자동차 유지 공학을을 공부했다. 나는 hybrid cars의 powertrain에서 물리학을 재현하는 공학에서 나의 석사 학위를 얻었다. 나는 현재 기업가이고, Tidal Labs의 공동 창립자이고 CTO이다. 이것은 뉴욕에서 bootstrapped된 startup으로서의 어떤 것들을 할 수 있다는 것을 증명한다. 나는 가르치는 것을 사랑하고, 여전히 물리학을 사랑한다. 나는 JavaScript로 물리학하기라 불리는 나의 블로그의 연재를 시작하여 그러한 가려움을 둘 다 긁어주었다.
결국, Build New Games는 나에게 비디오 게임을 위한 물리학에 대한 자료를 써달라고 부탁했다. 게임 개발은 오직 취미이다 - 나의 전문분야 가 아니다 - 그래서 나는 유일한 의미있는 것만 했고, 연구로서 native JavaScript로 그럴듯한 물리엔진을 구현하기 시작했다.
이 자료는 너에게 게임 엔진의 필수적인 물리학을 관통하여 가르쳐 줄 것이다. 이것은 A-Z "how-to" guide이다. 나는 몇 가지 중요한 최적화와 구현 세부사항을 제외했다; 한 개의 자료가 너무 많이 다룰 수도 있다. 나의 진정한 목적은 너에게 옳은 방향을 가르쳐주고, 너가 나중에 구현하는데 필요할 개념들을 가르치는 것이다. 다음 단계 너에게 달려있다. 나는 너가 이 자료를 점프판으로서 사용하고 너 자신의 게임 엔진을 가서 쓰기를 희망한다. 그리고 그 과정에서 고급 개념들을 연구하기를 희망한다.
나는 너에게 이 자료의 끝에 매우 도움되는 to-do list를 남겨놓았다. 만약 너가 여기에서 너가 배울 필요가 있는 요약을 찾는다면.
A Vector State of Mind
나의 물리엔진을 구현할 때 내가 배웠던 첫 번째 것은 너는 정말 벡터 수학 (선형 대수)를 포옹해야만 한다는 것이다. 나는 벌써 너가 신음 소리 내는 것을 들을 수 있다. 몇 가지 이유 때문에, 선형대수는 항상 사람들로부터 본능적인 반응을 끌어낸다. 그러나 제발 내가 너를 흔들 기회를 주도록 해라.
뉴턴의 운동 방정식 - 기본적으로 우리가 막 해야할 모든 것을 말하는 것 - 은 매우 도움이 되는 수학의 퀄리티를 가진다. 너는 운동 방정식을 더 작은 식들로 나눌 수 있다: x, y, and z축에 대한 각각의 것으로.
이것이 의미하는 것은 너가 야구공을 던질 때 (편의성을 위해 2D에서), 너는 그것이 수직으로 움직이는 방법과 그것이 수평으로 움직이는 방법에 대해 두 개의 별개의 방정식을 풀 수 있다. 너는 야구공을 던질 때, 그것은 상수의 속도로 앞으로 움직인다. 그러나 그것이 또한 동시에 수직으로 움직인다. 그리고 그것의 수직 운동은 결코 상수가 아니다. 그것은 중력에 영향을 받는다! 뉴턴의 방정식은 너가 이러한 두 가지 측면을 별개로 보도록 하는 것을 허용한다: "그 야구공은 앞으로 90mph로 움직이지만, 그것은 또한 중력의 영향하에 위아래로 움직이고 있다."
많은 사람들에 대해, 그것이 물리학이 가는 방식이다. 너는 각 차원 (forward and vertical motion)을 개별적으로 해결할 수 있다. 그러나 나는 너가 그것을 그렇게 하지 않는 것을 격려한다. 왜 우리는 한 개를 가질 수 있을 때 세 개의 방정식을 가져야 하는가? 물론이다. vector 수학과 편해지는 것은 (또 다시, 선형 대수로 불려지는) 더욱 가파른 학습 곡선을 가지지만, 나는 그것이 매우 작업하기에 더 좋다는 것을 알았다. 그것은 그럴 가치가 있다.
Points as Vectors
나는 모든 나의 생각들을 vector로 바꾸기로 결정했다. 벡터들은 화살과 같다 - 그것들은 길이와 방향을 가진다. 그것들은 공간에서 절대 위치를 가지지 않는다. 그 벡터 [5,3]은 북동쪽을 가리키지만, 그것은 "시작점"을 가지고 있지 않다. 그것 때문에, 내가 개별 점들을 벡터로 모델링 하기로 결정했다는 것은 낯설지도 모른다. 언제든지 나는 (5,3)에 하나의 코너가 있는 사각형을 만들고, 나는 실제로 그 점을 vector [5,3]으로 모델링한다. 한 점을 벡터로서 모델링 할 때, 간단히 그 벡터의 꼬리가 (0,0)의 점에 있다고 가정해라.
왜 이것이 유용한가? 답은 두 가지이다. 첫 번째로, 더 적은 데이터 타입들을 가지는 것이 좋다. 나는 오히려 Vector와 Point class보다는 하나의 Vector class를 가지는 게 좋다. 그러나 더 중요하게, 그것은 수학이 추상적인 것들에 훌륭하기 때문이다.
여기에서 내가 의미하는게 있다: 만약 너가 어떤 기하학을 했다면, 너는 아마 점 A와 B에 대해 말해왔다. 너는 선분 AB를 얻기 위해 점 A와 B를 함께 연결 할 수 있다. 그리고 너가 pen-and-paper math를 할 때, 그것은 그렇게 쉽다. 너는 "AB"를 쓰고 너는 신비하게 선분을 갖게 된다. 그러나 프로그래머는 그것이 그리 쉽지 않다는 것을 안다. 우리는 간단히 선분을 명시하지 않는다. 운좋게도, 벡터 수학이 여기에 들어온다. 만약 너가 A와 B 점을 벡터로 모델링 한다면, 너는 선분 AB를 간단히 벡터 뺄셈 B-A를 해서 얻을 수 있다.
벡터들은 물리엔진을 쓰는 동안 너가 할 필요가 있는 많은 흔한 일들을 간단하게 한다. 선형 대수가 분리된 차원을 개별적으로 해결해야만 하는 것을 제거할 뿐만 아니라, 그것은 또한 너가 "2D vs 3D"로부터 추상화하는 것을 도와준다 (왜냐하면 너는 "positionX" and "positionY" and "positionZ" 같은 변수들을 개별적으로 사용하지 않기 때문이다). 벡터를 사용하는 것은 또한 너가 벡터들을 더 하고 뺴는 것 과 같은 직관적인 것들을 하는 데 도움을 준다 - 너가 점들을 벡터들로 모델링할 수 있다는 것을 명심해라. 그래서 너가 벡터에 대해 할 수 있는 어떤 수학이든 점에서도 또한, 어떤 다른 점 주변의 회전을 포함해서.
요약 : 벡터와 친해져라. 너가 해야할 첫 번째 것은 vector 덧셈, 뺄셈, 곱셈, 내적, 외적, 회전을 하는 간단한 벡터 클래스를 쓰는 것이다. 그것이 너가 할 필요가 있는 모든 것이다. 너의 물리엔진의 나머지는 벡터들 위에 구현될 것이다.
Newton's 2nd Law of Motion
뉴턴의 운동 제 2법칙, 너가 고등학교로부터 기억할지도 모르는, 은 한 오브젝트의 가속도를 그 오브젝트에 가해진 힘의 양과 관련 짓는다. 그 공식은 그 자체로는:
F = ma
이다.
그 "F"와 "a"는 여기에서 벡터들을 나타낸다. 이것은 만약 너가 원했다면 너는 이 방정식을 세 부분으로 분리하여 각각을 분리해서 쓸 수 있다는 것을 의미한다:
F_x = ma_x
F_y = ma_y
F_z = ma_z
내가 이전에 언급했듯이, 오브젝트들은 그것들의 자유로운 degrees의 각각에서 독립적으로 움직이기 때문이다. 하늘을 나는 야구공은 "y" 방향에서 중력에 굴복하고 (아래쪽으로 가속하게 만드는) 그리고 "x" 방향으로 꾸준한 속도로 나아간다. 그러한 두 가지 효과들은 생각되어질 수 있고, 심지어 계산될 수 있다. 완전히 개별로. 너가 너의 결과를 "y"축에 대한 운동과 함께 "x"축에 대한 운동을 합칠 때, 너는 너가 공이 취하길 기대하는 친숙한 곡선의 경로를 얻는다.
뉴턴의 제 2법칙은 우리에게 매우 귀중하고 거의 모든 오브젝트들의 상호작용을 만들어 낸다. (충돌 반응에 대해 이야기할 때 몇 가지 예외가 있다). 이 공식이 매우 강력한 이유는 두 가지가 있다: 첫 쨰로, 힘들은 오브젝트들이 실제 세계에서 서로 어떻게 상호작용하는지에 대한 방법이다; 둘 째로, 만약 너가 한 오브젝트의 가속도를 안다면, 너는 그것의 속도와 그것의 위치 둘 다를 계산할 수 있다.
한 오브젝트의 움직임을 재현하는 과정은 이것처럼 된다:
- 한 오브젝트에 힘이 무엇인지 알아내라
- 그러한 힘들을 단일의 "결과로 생긴" or "순수" 힘을 얻기 위해 합쳐라.
- 그러한 힘들 때문에 생긴 오브젝트의 가속도를 계산하기 위해 F = ma 를 사용해라
- 그 오브젝트의 속도를 계산하기 위해 오브젝트의 가속도를 사용해라
- 오브젝트의 위치를 계산하기 위해 오브젝트의 속도를 사용해라
- 오브젝트의 힘들은 순간순간 바뀔지도 모르기 때문에, 이 프로세스를 #1부터 반복해라. 영원히.
꽤 쉽다! 여섯개 간단한 단계들이 어떤 차원에서든지 이동할 간단한 오브젝트를 모델링하는데 필요한 모든 것이다.
물론, 여기에 몇 가지 조심해야 할 것들이 (caveats) 있다. 위는 translation (왼/오, 위/아래/ 뒤/앞으로 움직이는 것) 에 대해서 작동하지만, 우리의 회전을 알아내기 위해, 우리는 그것을 조금 수정할 필요가 있다. 나는 그것에 대해 잠시 뒤에 말할 것이다.
다른 caveat은 가끔씩 오브젝트에 대해 그 힘들이 정확히 무엇이 되어야 할지를 알아내기가 어렵다는 것이다. 운 좋게도, 게임 물리학은 일반적으로 너무 광적이지 않고, 우리는 오직 중력, 스프링 로켓, 그리고 상대적으로 간단한 것들만 생각할 필요가 있다. 너가 자기장 또는 어떤 고급의 것들을 모델링 할 것인지에는 의심스럽다. 비록 MIT game Lab이 빛의 속도가 걸어가는 속도랑 같은 것처럼 특별한 상대성 효과를 모델링한 게임을 출시했을지라도.
Calculating Velocity and Position
가속도, 속도, 그리고 위치는 적분과 매우 연관되어있다. 구체적으로 말하자면, 속도는 위치의 "시간에 대한 변화율" 이다. - 적분에서, 이것은 "시간 미분"이라고 불리고 또는 짧게 해서 "미분"이라고 불려진다. 우리가 속도를 측정하는 방식을 생각해라: 시간당 마일 또는 초당 미터. 속도는 시간 기준으로 여행되는 거리의 기준이다. 유사하게, 가속도는 시간 기준으로 변화된 속도의 기준이다.
위치, 속도, 그리고 가속도 사이의 관계는 우리에게 매우 도움이 된다. 만약 우리가 오브젝트의 위치의 history를 안다면, 우리가 이 오브젝트가 지난 second에서 얼만큼 움직였는가를 물어서 그것의 속도를 설정할 수 있기 때문이다. 우리는 가속도를 유사하게 계산한다.
좀 더 중요하게, 우리는 뒤로 작업할 수 있다. 만약 우리가 오브젝트의 가속도를 안다면, 우리는 그 속도가 초당 얼마나 변해야하는지를 알아낼 수 있다. 그리고 만약 우리가 속도를 안다면, 우리는 위치가 초당 얼만큼 변해야 하는지를 알아낼 수 있다. 이 기법은 "적분"이라고 불려진다. 우리가 하려는 것은 numerical integration이다 - 연필, 종이, 그리고 적분 교과서를 요구하는 analytical integration과 대조적으로.
뉴턴의 법칙에 대해 numerical 적분의 모든 방식은 시간에서 아주 작은 snapshots에 대해 시간을 유지하고 계싼으 하는 방식을 포함한다. 게임 엔진은 가끔식 그래픽스 엔진을 30fps로 작동시키고, 물리엔진을 60fps로 작동시킨다 - 그 경우에, numerical integration은 1/60초의 timestep을 사용하는 중이다. (16 milliseconds).
numerical integration을 수행하는 가장 간단한 방법은 Euler's method이다. 여기에 몇 가지 슈도코드가 있다 (가속도, 속도, 그리고 위치가 모두 0에서 시작한다고 가정해라). 이 예제에서, 힘, 가속도, 속도, 그리고 위치는 모두 벡터들이다 - 그래서 이 슈도코드는 2D와 3D 똑같이 다룬다.
Euler's method는 개념적 이해를 구성하는데 훌륭하지만, 끔직하게 정확하지 않다. 많은 상황에서, 이 기법은 불안정하고, 몇 가지 불쾌한 결과들을 낳을 수 있다. 그래서 우리는 한 단계 더 들어갈것이고, Velocity Verlet integeration이라고 불리는 것을 사용한다. 위의 것 대신에 우리는 다음의 것을 할 수 있다:
두 방식의 가장 중요한 차이점은 이전 프레임과 현재 프레임 사이의 평균 가속도의 사용이다. 이것은 우리에게 상당한 정확도의 장점을 준다. 부가적으로 0.5 * last_acceleratino * time_step^2은 조금 도움을 주지만, 제곱된 time-step 수치는 보정을 작게한다 : (1/60)^2은 1/3600이다 결국.
너는 또한 새로운 가속도가 position이 업데이트 된 후에 계산된다는 것에 주목해야 한다; 너는 그러므로 새로운 힘들을 계산하기 위해 현재 frame의 위치를 사용하는 중이다. 새로운 힘들을 계산하기 위해 지난 프레임의 위치를 사용하기 보다는.
Checkpoint #1
우리는 여전히 다뤄야할 많은 주제들을 가지고 있다. 그래서 나는 너에게 숙제를 줄 것이다: 어떻게 다양한 physical forces들을 모델링하는지 찾아보아라. 특정하게, weight force, spring force, viscous damping force, 그리고 아마도 air drag를 찾아보아라. 너는 매우 현실적인 scenarios를 만들기위해 서로서로를 조합하여 이러한 힘들 전부 또는 어떤 것이든 상요할 수 있다.
물리를 모델링하는 것에 있어서 훌륭한 것은 이것이다: 만약 너가 그 힘들을 정확히 모델링한다면, 너는 현실적으로 행동하는 오브젝트들을 얻을 것이다. 너는 복잡한 상호작용들을 직접적으로 모델링하는 것에 생각할 필요는 없다. 만약 너가 하늘로부터 떨어지길 원하는 공을 가지고 있고 그것이 terminal velocity에 도달하기르 바란다면, 그냥 weight와 air drag forces를 모델링해라. 너는 그 공이 terminal velocity에 도달하도록 만드는 미치게 손으로쓰인 로직에 대해 생각할 필요가 없다; 그 물리학은 너를 위해 그것을 다룬다. 그리고 만약 너가 공중에서 물로 환경을 바꾸기를 결정한다면, 그러면 너는 tweens 또는 animation을 전혀 다시 재조정할 필요가 없을 것이다; 너는 그냥 air drag formula에서 "density"의 값을 바꾼다. 물리학이 나머지를 신경쓴다.
이 예제 - 중력과 air drag(공기저항, 대기항력)의 영향하에서 하늘로부터 떨어지는 공 -는 내가 벡터를 사용하지 않는 유일한 것이다. 나는 너가 그 프로세스에 쉽게 빠져들기를 원하고, 한 번에 한 단계식 나가기를 원한다. 그래서 이 예쩨는 오직 vertical (1D) motion을 가질 것이다. 너는 그것을 간단히 x 방향에 대해 계산을 반복하여 2D로 할 수 있다.
나는 너가 아래의 JSFiddle fork하고 다른 질량을 가진 오브젝트들의 air drag의 효과를 보기를 추천한다. 1의 질량은 돌처럼 떨어지지만, 만약 너가 그 질량을 0.01로 바꾼다면, 그 공은 빠르게 low terminal velocity에 도달하고 아래로 흐른다. 너는 또한 그 공이 다른 유체에서 어떻게 행동하는 지를 보기 위해 density variable을 바꿀 수 있다. 물이나 또는 헬륨처럼.
Rigid Bodies
d우리는 필수적으로 "particle"을 모델링 해왔다. 파티클은 모양 또는 크기를 갖지 않는 point-masses이다. 그리고 그것들은 방향을 갖지 않는다 (회전하지 않는 다는 것을 의미한다). 파티클들은 모델링하기에 가장 간단한 물리적 entity이다.
모양이 있는 어떤 것을 모델링 하는 것은 우리의 작업에 복잡성의 전체 정도를 더한다. 모양이 있는 것들은 회전할 수 있어야만 하기 때문이다. 이것은 우리를 "rigit body physics"의 영역에 넣는다. Rigid bodies는 모양과 방향을 가진다. 그것들은 회전할 수 있고, 서로에게 충돌할 수 있다.
우리는 우리 자신을 이제 2D에 제한하고 있었다. 그래서 우리는 오직 2개의 자유도를 다뤘어야만 했다. 나는 이제 3번쨰 자유도를 도입할 것이다: z-axis에 대한 회전. z축은 screen에 딱 붙어있고 너의 얼굴을 가리킨다. 내가 "z축에 대한 회전"이라는 것을 말할 때, 너는 너의 스크린에 딱 붙어있는 한 뾰족한 것에 찔려지는 한 모양을 상상할 수 있고, 그 오브젝트는 그 뽀족한 것에 대해 회전한다.
만약 우리가 full 3D에서 작업한다면, 우리는 다뤄야 할 6개의 자유도를 가질 것이다: x, y, and z에서의 translation(평행이동 ("sway, "heave", and "surge"라고 불려지는), 그리고 x, y, z에 대한 회전 ("pitch", "yaw", "roll").
너가 우리가 여기에서 하고 있는 2D 예제를 이해하기만 한다면, full 6DoF (six degrees of freedom)으로 가는 것은 너무 많은 확장은 아니다. 2D와 full 3D 사이의 한 차이점은 6DoF motion에 대해 변환 행렬의 잠재적 포함이다; 여기에서 우리는 평행이동과 회전 다루기 위해 벡터 함수를 사용하지만, full 6DoF motion은 하나의 (일종의) 깔끔한 행렬 연산으로 평행이동과 회전 둘 다를 다루는 단일의 transformation matrix operation에 의해 좋게 다뤄질 수 있다. 너는 여전히 벡터만을 사용하여 6DoF motion을 해낼 수 있지만, 같은 방식에서 우리는 2D에 대해 베겉를 사요하는 것의 쉬움에 감사하게 된다, 너는 3D에서 transformation matrix를 사용하는 것의 편함을 감사하게 될 것이다.
너의 미래에 Three.js로 3D physics를 위해 너의 눈을 내 블로그를 주시하도록 해라.
Rotation
뉴턴의 운동 제 2법칙은 상대적으로 간단한 방식으로 회전에 확장되어질 수 있다. 우리는 오직 회전을 해결하기 위해 다소 변수들을 업데이트만을 할 필요가 있을 것이다.
첫 번쨰로, 위치, 속도, 그리고 가속도에 대한 우리의 상태 변수들은 변화한다. 우리는 이제 rotation angle, angular velocity, and angular acceleration에 대해 생각할 필요가 있다. 우리는 Greek symbol theta (θ), omega(ω), and alpha (ɑ)를 이러한 것들에 대해 개별적으로 사용할 것이다. 우리의 예제는 오직 z-axis에 대한 회전만을 허용하기 때문에, 이러한 값들은 그것들의 linear counterparts 같은 벡터가 아닌 스칼라 일 것이다. 그 angle theta는 dimensionless이고, 일반적으로 radians으로 측정된다. Angular velocity는 radians per second로 측정되고, 가속도는 radians per second-squared로 측정된다.
다음으로, 우리는 "mass"를 "moment of inertia(관성 모멘트)"로 대체한다. Mass - or inertia -는 가속도를 저항하는 한 오브젝트의 고유한 특징이다 (한 오브젝트가 더 많은 질량을 가질수록, 고정된 힘 영향 아래에서 가속하는 것은 더 느려진다). 그러므로, 관성 모멘트는 angular acceleration을 저항하는 한 오브젝트의 특성이다.
다른 모양들은 다른 관성 모멘트들을 갖는다. 비록 그것들이 같은 질량을 가질지라도. 예를들어, 3ㅏ파운드의 디스크를 회전시키는 것은 같은 크기의 3파운드 훌라후프를 회전시키는 것보다 더 쉽다. 왜냐하면 그 훌라후프는 모든 그것의 질량을 바깥 edge를 향하여 갖기 때문이다. 문제를 좀 더 복잡하게 만들기 위해, 너가 회전시키려는 한 오브젝트의 점 과 축이 무엇인지에 따라 관성 모멘트는 바뀔 수 있다. 이러한 이유 때문에, 우리는 간단한 사각형을 사용할 것이다. 그래서 우리는 관성 모멘트의 적분에 잡혀있게 되지 않는다. 너는 moments of inertia of common shapes를 볼 수 있다; 만약 너가 복잡한 모형을 모델링 할 필요가 있다면, 그러면 너는 몇 가지 heavy-handed 적분과 세번의 적분 함수로 그렇게 할 수 있다.
마지막으로, 우리는 force를 "torque"로 대체한다. Torque는 한 오브젝트를 회전시키려는 경향을 가진 힘이다. Torque는 한 힘이 한 오브젝트의 회전의 중심으로부터 얼마나 멀리 적용될 수 있는지를 알아내어 계산될 수 있다. - 그러나 우리는 또한 우리의 오브젝트의 중심점에 대해 90도 각으로 누르는 힘의 component만을 봐야만 한다.
예를들어, 만약 너가 1 foot 길이의 wrench를 사용하고있고 너가 5 파운드의 힘으로 정확히 90도로 그것을 누른다면, 그 bolt에 대한 torque는 5 foot-pounds이다. 만약 너가 다른 각도로 누른다면, 그 torque는 더 작을 것이다. 만약 너가 wrench에 끝에서 bolt를 쪽으로 직접 누른다면, 그 torque는 0이 될 것이고, 그 wrench는 움직이지 않을 것이다.
그래서 우리는 회전에 대한 뉴턴의 운동 제 2법칙을 다시 쓸 수 있다. 나는 이것을 스칼라로 써왔다. 왜냐하면 우리는 오직 오늘날 z-axis에 대한 회전만을 생각하기 때문이다.
T = Ja
너무 쉬운 것처럼 보인다! 우리는 또한 정확히 translation에서 사용했던 같은 기법을 사용하여 이것을 적분할 수 있따. 초심자에게 이것에 대해 가장 어려운 부분은 일반적으로 힘이 torques를 만들어내는 방식을 알아내는 것이지만, 몇 가지 hard work, diagrams, and a linear algebra refresher로, 그것은 빠르게 사소한 일이 된다. Hint : vector cross proudct를 review해라. force vector과 "displacement" vector (힘이 적용된 곳에 대한 오브젝트의 센터로부터 거리)의 외적은 너에게 그 오브젝트에 대한 최종 torque를 준다. 너는 또한 너가 projecting vectors과 determining vector compompontes와 친숙해지도록 하기 위해 너의 삼각법을 닦기를 원할 것이다.
Checkpoint #2
이 예제는 rigid body rectangle을 모델링 한다. 그 사각형은 스프링으로 그것의 모서리 중의 하나에서 천장에 붙여져 있다. 그리고 떨어지는 것이 허용된다. 그 스프링은 펼쳐지고 모서리를 잡는다. 이것은 사각형이 튀기고 회전하게 한다.
이 예제에서 모델링된 다양한 힘들이 있다. 사각형의 무게는 힘으로 모델링 되었다. 스프링은 힘으로서 모델링 되었다. 그 힘은 사각형의 중심에 적용되지 않기에, 우리는 또한 사각혀을 회전하게 하는 torque를 계산할 필요가 있다. 만약 너가 스프링을 박스의 중심에 연결한다면, 그것은 전혀 회전하지 않을 것이다 (완전한 세계에서). 나는 또한 평행이동과 회전에 대해 둘 다 viscous damping(점성의, 끈적거리는 + 제동)을 모델링 했다. Viscous damping은 다른 물질들의 다양한 종합 마찰 손실들을 모델링하는 좋은 방법이다. 우리의 스프링은 완벽하지 않다. 그래서 그것은 영원히 튕기지 않을 것이다. Viscous damping은 결국 그 박스가 튀기고 회전하는 것을 멈추게 한다.
너는 또한 이 예제에서 Vector class와 Rectangle class를 볼 것이다. 모든 물리학은 벡터로 처리되고, 각 time-step마다 vector math를 또한 사용하여 그 박스를 회전시키고 평행이동 시킨다.
Collision Detection
물리 엔진의 가장 복잡한 측면은 collision detection이다. Collision detection은 일반적으로 매우 비싼 연산이고, 게임이 수십 또는 수백개의 오브젝트들을 가질지 모르기 때문에, 많은 노력이 collision detection 알고리즘을 최적화하는데 들어간다.
회전할 수 있는 오브젝트들이 충돌할 때 또 다른 복잡도가 나타나게 된다. 그러나, 또 다른 복잡도는 너가 복잡한 모양을 가진 오브젝트들을 충돌시키려 할 때 발생한다. 두 원이 충돌하는지를 체크하는 것은 쉽다; 너는 그것들의 중심 사이의 거리가 그것들의 반지름의 합보다 작은지를 확인하면 된다. 두 사각형이 충돌하는 것을 확인하는 것은 조금 까다롭다, 하지만 힘든 것 아니다. 만약 그것들이 회전하는 것이 허용되지 않는다면 (이러한 것들은 가끔 "AABB" 또는 "axis-aligned bounding boxes"라고 불려진다). 그 사각형이 일단 회전하는 것이 허용된다면, 그 문제는 까다로워지고, 삼각형, 오각형, 그리고 임의의 폴리곤들과 같은 다른 모양들에 대해서 계속 까다로워진다.
그래서 이 논의로는 끝낼 수 없으니, 우리는 convex polygons만을 고려할 것이다. 만약 너가 한 모양을 관통하는 어떤 선을 그릴 수 있고, 그것이 그 모양을 통해 자를 수 있다면, 그것은 convex polygon이다. 만약 너가 그 모양을 관통하여 자르는 한 직선을 두 번 이상 그릴 수 있다면, crescent moon 또는 별과 같은, 그러면 그 폴리곤은 concave(오목)하고, 우리는 그런 것들에 대해서 이야기 하지 않을 것이다.
사실, 대부분의 엔진들은 concave (어려운) 모양을 convex (더 쉬운) 모양의 한 묶음으로 쪼갠다. 그래서 우리가 오목 모양을 여기에서 이야기 하지 않더라도, 너는 이러한 이론들을 어떤 프로그램에 거의 맞게 확장할 수 있다.
전체 책들이 collision detection에 대해 쓰여져 왔기 때문에 (그리고 여전히 그것을 정의롭게 할 수 없다), 우리는 collision detection의 한 가지 측면에만 공 들일 것이다. 한 collision detection routine은 이것처럼 보일지도 모른다:
Separating Axis Theorem
두 가지 우세한 collision detection 방식이 있다. GJK라고 불려지는 한 가지 방식은 3D collision detection을 위해 좀 더 흔히 사용된다. 왜냐하면 우리가 사용할 알고리즘은 3D에서 쓰일 때 비싸기 때문이다. 그러나, 그 separating axis theorem은 2D collision detection을 위해 널리 사용되고, 우리에게 운좋게도 개념화하고 시각화하는 것은 더욱 쉽다.
두 오브젝트들이 스크린에 있는 것을 상상하고, 우리가 그것들을 top-down perspective로 바라보고 있다고 상상해라 (예를들어, 우리는 헬리콥터에서 빌딩들의 지붕을 보고 있다). 그러한 두 오브젝트들이 충돌하는지를 테스트할 한 가지 방식은 아래로 내려가서 스크린에 오브젝트들과 같이 서는 것이다 (말하자면, street level에서), 그리고 그것들 주위에 원을 그리며 걸어간다. 만약 우리가 두 오브젝트들 사이의 한 틈(gap)을 본다면, 우리는 확실히 그것들이 충돌하지 않고 있다는 것을 안다. 만약 우리가 걸어가는 것을 끝내고, 그것들 사이에 어떠한 gap도 보지 못했다면, 그것들은 충돌하고 있음에 틀림없다. 왜냐하면 우리는 모든 가능한 각도로부터 그것들을 봤고, 두 오브젝트가 분리되었다는 것을 결코 못봤기 때문이다.
우리가 이것을 하기 위해 코드를 쓰려고 할 때, 우리는 오브젝트들 주변의 수백만개의 각도로부터 view를 체크할 수 없다. 그래서 우리는 그 절차를 간단하게 할 방식이 필요하다. 운좋게도, 우리는 오직 몇 가지 주요 지점들로부터의 view를 검사해야만 한다: 우리의 두 모형들에서 그 옆면들에 대해 각각 하나씩. 만약 우리가 한 삼각형과 heptagon (7개의 면을 가진)이 교차하는지 보려고 한다면, 우리는 10개의 다른 각도의 view를 체크해야만 한다.
좀 더 구체적으로, 우리가 하려는 것은 많은 다른 축들에 대해 오브젝트들의 그림자(사영)을 보는 것이다. 그리고 그것들의 그림자들이 중첩되는지를 보기위해 테스트하는 것이다. 만약 우리가 삼각형/7각형 예제에서 모든 10개의 축들을 점검하고, 그 그림자가 모든 10개의 축에서 겹친다면, 그러면 우리는 충돌을 갖게 된다. 만약 심지어 한 개의 축에 gap이 있다면, 우리는 즉시 보는 것을 멈춘다. 왜냐하면 두 오브젝트들이 명백히 충돌하고 있지 않기 때문이다.
게다가, 만약 우리가 사각형을 사용한다면, 우리는 상황을 더욱 간단하게 할 수 있다. 사각형은 평행한 변의 두 집합을 가지고 있고, 우리는 각 변에 대해 사영을 할 것이기 때문에, 우리는 각 사각형에 대해 복사 결과물의 두 집합을 갖을 것이다. 그러므로 우리는 사각형을 볼 때, 8개에서 4개의 축들을 검사하도록 숫자를 줄일 수 있다. text axes로서 사용할 각 사각형의 left and top side를 골라라 (또는 두 개의 수직한 변들).
벡터 수학은 separating axis theorem을 매우 쉽게 만든다. 우리는 우리의 테스트 축들을 간단히 대응되는 사각형 정점들에서 뺄셈하여 얻을 수 있고, "shadows"를 그러한 축들에 사영시키는 것은 각 사각형의 정점의 내적과 text axis를 찾는 것의 문제이다.
Collision Response
두 오브젝트들이 충돌하고 있는 것을 결정하는 것은 절반의 싸움이다. 오브젝트들이 충돌하는 것이 보였다면, 그것들은 어떤 방식으로 그것에 대해 반응할 필요가 있다. 이것의 많은 것은 너의 게임 메카닉에 의존할 것이다. 한 캐릭터에 의해 발포된 총알은 데미지를 줘야 한다. 한 미사일은 데미지를 주고 폭발해야만 한다.그러나 오늘날, 우리는 매우 물리적 반응을 볼 것이다: 두 박스들이 서로 부딪히고 튀기는 것들.
회전이 없는 두 간단한 모양들에 대해 Collision Response는 꽤 쉽다. Momentum(운동량), 또는 mass * velocity는 여기에서 우리를 도와준다. 두 개의 hard objects가 부딪힐 때, 두 오브젝트들의 총 운동량은 변하지 않는다. 실제 오브젝트들은 완벽히 hard하지 않다. 그래서 우리는 coefficient of restitution(복구)이라고 불리는 fudge factor(임시방편 요소)를 도입한다. 이것은 기본적으로 충돌의 탄성을 모델링 한다.
불행하게도, 우리의 회전하는 오브젝트들은 좀 더 복잡하다. 그 두 개의 오브젝트들은 서로 튕길 뿐만 아니라, 그것들의 회전은 오브젝트에 대해 충돌과 어떤 점이 관련되었는지에 따라 바뀔 것이다. 게다가, 실제 세계의 오브젝트들은 결코 그것들이 컴퓨터 시뮬레이션에서 할 수 있는 방식으로 "중첩"되지 않기에, 우리는 일반적으로 그것들의 위치를 역추적하고 수정한다. 그것들이 서로 닿고있고 중첩되지 않기 위해서.
이것은 우리에게 collision에 대해 좀 더 알도록 하는 필요성을 남겨둔다. 우리는 두 모양 사이의 중첩의 몇 가지 특징을 알고싶다. 만약 우리가 그것들이 닿는 순간 지점까지 그 충돌을 "되감기"한다면, 우리는 그 점의 위치를 알고싶다. 여러번, 우리는 또한 한 오브젝트가 다른 것을 "관통하는 깊이"를 알고 싶어할 것이다.
Collision detection과 collision response의 압도적인 복잡성 때문에, 우리는 여기에서 너무 깊게 들어갈 수 없다. 간단히 해서, 우리가 충돌을 되돌릴 필요가 없고, 우리가 어느정도 충돌과 연관된 한 점을 얻는 한, 우리는 무언가 할 것이라고 결정하자. 이용가능한 많은 좀 더 정교한 방식들이 있고, 이러한 것들을 배우는 가장 ㅈ호은 방식은 Box2d 또는 Bullet같은 존재하는 physics engines을 공부하는 것이다. Bullet과 Box2d는 JavaScript로 포트되어졌지만, 나는 너가 어떻게 그것을 읽는지 안다면, 원래 C++ source를 체크하기를 추천할 것이다; 몇 가지 포팅들은 자동적으로 수행되고 가독성을 위해 최적화되지 않았다.
일단 우리가 충돌과 관련된 한 지점을 발견한다면 (내가 그것을 어떻게 했는지 보기위해 다음 코드 예제를 보아라), collision response에서 그 정보를 우리가 사용할 수 있는 두 가지 방식이 있다. 우리는 충돌의 depth에 대한 정보를 사용하고 두 오브젝트들에 작용하는 매우 큰 힘을 생성할 수 있다 (어떤 것이 다른 것을 관통할 때 오브젝트의 물질의 "압축" 때문에 매우 뻣뻣한 스프링 처럼), 또는 좀 더 흔하게, 우리는 impulse response를 사용할 수 있다. 이것은 우리가 간단히 관계되는 힘과 상관없이 그 오브젝트의 속도 (기술적으로, 운동량)를 수정하는 것을 의미한다.
Checkpoint #3
우리의 최종 checkpoint는 고정된 박스와 부딪히고 떨어지는 회전하는 박스를 보여준다. separating axis theorem의 demo가 완전하지만, 그 collision response는 좀 더 정교한 기법이 되도록 남겨둔다.
그러나, 그 separating axis theorem test의 이 구현은 확실히 명백하지 않다. 그래서 너는 너의 사용에 맞게 너의 것을 만들어야만 한다. 이 예제는 일찍 끝나지 않는다. 만약 중첩되는 축이 없다면: 일찍 끝나는 것은 훌륭한 성능 최적화이다. 부가적으로 이 예제는 충돌과 가장 관련된 사각형의 정점을 추출하는 몇 가지 heuristics를 사용한다.
좀 더 정교한 구현들은 충격의 순간에 충돌을 되돌리고 또한 접촉 점과 normal를 반환하는 것을 포함한다. 부가적으로, 여기에서 collision response는 원시적이고, 물리적으로 정확하지 않다; separating axis theorem이 작동하는지를 보여주기 위해서인 것이다.
Conclusion
너는 이제 물리엔진을 구현하는데 요구되는 것을 더 잘 이해해할 것이다. 너의 여정은 여기에서 끝나지 않는다. 너의 편리성을 위해 내가 아래에 to-do list를 준다. 먄악 너가 이 자료를 즐겼다면, 부디 @bkanber on Twitter를 팔로우하고, 나의 블로그를 체크해라. 거기에서 나는 물리학, 머신러닝, 그리고 다른 흥미로운 것들을 이야기 한다.
To-Do:
위치, 속도, 그리고 가속도 사이의 관계는 우리에게 매우 도움이 된다. 만약 우리가 오브젝트의 위치의 history를 안다면, 우리가 이 오브젝트가 지난 second에서 얼만큼 움직였는가를 물어서 그것의 속도를 설정할 수 있기 때문이다. 우리는 가속도를 유사하게 계산한다.
좀 더 중요하게, 우리는 뒤로 작업할 수 있다. 만약 우리가 오브젝트의 가속도를 안다면, 우리는 그 속도가 초당 얼마나 변해야하는지를 알아낼 수 있다. 그리고 만약 우리가 속도를 안다면, 우리는 위치가 초당 얼만큼 변해야 하는지를 알아낼 수 있다. 이 기법은 "적분"이라고 불려진다. 우리가 하려는 것은 numerical integration이다 - 연필, 종이, 그리고 적분 교과서를 요구하는 analytical integration과 대조적으로.
뉴턴의 법칙에 대해 numerical 적분의 모든 방식은 시간에서 아주 작은 snapshots에 대해 시간을 유지하고 계싼으 하는 방식을 포함한다. 게임 엔진은 가끔식 그래픽스 엔진을 30fps로 작동시키고, 물리엔진을 60fps로 작동시킨다 - 그 경우에, numerical integration은 1/60초의 timestep을 사용하는 중이다. (16 milliseconds).
numerical integration을 수행하는 가장 간단한 방법은 Euler's method이다. 여기에 몇 가지 슈도코드가 있다 (가속도, 속도, 그리고 위치가 모두 0에서 시작한다고 가정해라). 이 예제에서, 힘, 가속도, 속도, 그리고 위치는 모두 벡터들이다 - 그래서 이 슈도코드는 2D와 3D 똑같이 다룬다.
acceleration = force / mass velocity += acceleration * time_step position += velocity * time_step
Euler's method는 개념적 이해를 구성하는데 훌륭하지만, 끔직하게 정확하지 않다. 많은 상황에서, 이 기법은 불안정하고, 몇 가지 불쾌한 결과들을 낳을 수 있다. 그래서 우리는 한 단계 더 들어갈것이고, Velocity Verlet integeration이라고 불리는 것을 사용한다. 위의 것 대신에 우리는 다음의 것을 할 수 있다:
last_acceleration = acceleration position += velocity * time_step + (0.5 * last_acceleration * time_step^2) new_acceleration = force / mass avg_acceleration = (last_acceleration + new_acceleration) / 2 velocity += avg_acceleration * time_step
두 방식의 가장 중요한 차이점은 이전 프레임과 현재 프레임 사이의 평균 가속도의 사용이다. 이것은 우리에게 상당한 정확도의 장점을 준다. 부가적으로 0.5 * last_acceleratino * time_step^2은 조금 도움을 주지만, 제곱된 time-step 수치는 보정을 작게한다 : (1/60)^2은 1/3600이다 결국.
너는 또한 새로운 가속도가 position이 업데이트 된 후에 계산된다는 것에 주목해야 한다; 너는 그러므로 새로운 힘들을 계산하기 위해 현재 frame의 위치를 사용하는 중이다. 새로운 힘들을 계산하기 위해 지난 프레임의 위치를 사용하기 보다는.
Checkpoint #1
우리는 여전히 다뤄야할 많은 주제들을 가지고 있다. 그래서 나는 너에게 숙제를 줄 것이다: 어떻게 다양한 physical forces들을 모델링하는지 찾아보아라. 특정하게, weight force, spring force, viscous damping force, 그리고 아마도 air drag를 찾아보아라. 너는 매우 현실적인 scenarios를 만들기위해 서로서로를 조합하여 이러한 힘들 전부 또는 어떤 것이든 상요할 수 있다.
물리를 모델링하는 것에 있어서 훌륭한 것은 이것이다: 만약 너가 그 힘들을 정확히 모델링한다면, 너는 현실적으로 행동하는 오브젝트들을 얻을 것이다. 너는 복잡한 상호작용들을 직접적으로 모델링하는 것에 생각할 필요는 없다. 만약 너가 하늘로부터 떨어지길 원하는 공을 가지고 있고 그것이 terminal velocity에 도달하기르 바란다면, 그냥 weight와 air drag forces를 모델링해라. 너는 그 공이 terminal velocity에 도달하도록 만드는 미치게 손으로쓰인 로직에 대해 생각할 필요가 없다; 그 물리학은 너를 위해 그것을 다룬다. 그리고 만약 너가 공중에서 물로 환경을 바꾸기를 결정한다면, 그러면 너는 tweens 또는 animation을 전혀 다시 재조정할 필요가 없을 것이다; 너는 그냥 air drag formula에서 "density"의 값을 바꾼다. 물리학이 나머지를 신경쓴다.
이 예제 - 중력과 air drag(공기저항, 대기항력)의 영향하에서 하늘로부터 떨어지는 공 -는 내가 벡터를 사용하지 않는 유일한 것이다. 나는 너가 그 프로세스에 쉽게 빠져들기를 원하고, 한 번에 한 단계식 나가기를 원한다. 그래서 이 예쩨는 오직 vertical (1D) motion을 가질 것이다. 너는 그것을 간단히 x 방향에 대해 계산을 반복하여 2D로 할 수 있다.
나는 너가 아래의 JSFiddle fork하고 다른 질량을 가진 오브젝트들의 air drag의 효과를 보기를 추천한다. 1의 질량은 돌처럼 떨어지지만, 만약 너가 그 질량을 0.01로 바꾼다면, 그 공은 빠르게 low terminal velocity에 도달하고 아래로 흐른다. 너는 또한 그 공이 다른 유체에서 어떻게 행동하는 지를 보기 위해 density variable을 바꿀 수 있다. 물이나 또는 헬륨처럼.
Rigid Bodies
d우리는 필수적으로 "particle"을 모델링 해왔다. 파티클은 모양 또는 크기를 갖지 않는 point-masses이다. 그리고 그것들은 방향을 갖지 않는다 (회전하지 않는 다는 것을 의미한다). 파티클들은 모델링하기에 가장 간단한 물리적 entity이다.
모양이 있는 어떤 것을 모델링 하는 것은 우리의 작업에 복잡성의 전체 정도를 더한다. 모양이 있는 것들은 회전할 수 있어야만 하기 때문이다. 이것은 우리를 "rigit body physics"의 영역에 넣는다. Rigid bodies는 모양과 방향을 가진다. 그것들은 회전할 수 있고, 서로에게 충돌할 수 있다.
우리는 우리 자신을 이제 2D에 제한하고 있었다. 그래서 우리는 오직 2개의 자유도를 다뤘어야만 했다. 나는 이제 3번쨰 자유도를 도입할 것이다: z-axis에 대한 회전. z축은 screen에 딱 붙어있고 너의 얼굴을 가리킨다. 내가 "z축에 대한 회전"이라는 것을 말할 때, 너는 너의 스크린에 딱 붙어있는 한 뾰족한 것에 찔려지는 한 모양을 상상할 수 있고, 그 오브젝트는 그 뽀족한 것에 대해 회전한다.
만약 우리가 full 3D에서 작업한다면, 우리는 다뤄야 할 6개의 자유도를 가질 것이다: x, y, and z에서의 translation(평행이동 ("sway, "heave", and "surge"라고 불려지는), 그리고 x, y, z에 대한 회전 ("pitch", "yaw", "roll").
너가 우리가 여기에서 하고 있는 2D 예제를 이해하기만 한다면, full 6DoF (six degrees of freedom)으로 가는 것은 너무 많은 확장은 아니다. 2D와 full 3D 사이의 한 차이점은 6DoF motion에 대해 변환 행렬의 잠재적 포함이다; 여기에서 우리는 평행이동과 회전 다루기 위해 벡터 함수를 사용하지만, full 6DoF motion은 하나의 (일종의) 깔끔한 행렬 연산으로 평행이동과 회전 둘 다를 다루는 단일의 transformation matrix operation에 의해 좋게 다뤄질 수 있다. 너는 여전히 벡터만을 사용하여 6DoF motion을 해낼 수 있지만, 같은 방식에서 우리는 2D에 대해 베겉를 사요하는 것의 쉬움에 감사하게 된다, 너는 3D에서 transformation matrix를 사용하는 것의 편함을 감사하게 될 것이다.
너의 미래에 Three.js로 3D physics를 위해 너의 눈을 내 블로그를 주시하도록 해라.
Rotation
뉴턴의 운동 제 2법칙은 상대적으로 간단한 방식으로 회전에 확장되어질 수 있다. 우리는 오직 회전을 해결하기 위해 다소 변수들을 업데이트만을 할 필요가 있을 것이다.
첫 번쨰로, 위치, 속도, 그리고 가속도에 대한 우리의 상태 변수들은 변화한다. 우리는 이제 rotation angle, angular velocity, and angular acceleration에 대해 생각할 필요가 있다. 우리는 Greek symbol theta (θ), omega(ω), and alpha (ɑ)를 이러한 것들에 대해 개별적으로 사용할 것이다. 우리의 예제는 오직 z-axis에 대한 회전만을 허용하기 때문에, 이러한 값들은 그것들의 linear counterparts 같은 벡터가 아닌 스칼라 일 것이다. 그 angle theta는 dimensionless이고, 일반적으로 radians으로 측정된다. Angular velocity는 radians per second로 측정되고, 가속도는 radians per second-squared로 측정된다.
다음으로, 우리는 "mass"를 "moment of inertia(관성 모멘트)"로 대체한다. Mass - or inertia -는 가속도를 저항하는 한 오브젝트의 고유한 특징이다 (한 오브젝트가 더 많은 질량을 가질수록, 고정된 힘 영향 아래에서 가속하는 것은 더 느려진다). 그러므로, 관성 모멘트는 angular acceleration을 저항하는 한 오브젝트의 특성이다.
다른 모양들은 다른 관성 모멘트들을 갖는다. 비록 그것들이 같은 질량을 가질지라도. 예를들어, 3ㅏ파운드의 디스크를 회전시키는 것은 같은 크기의 3파운드 훌라후프를 회전시키는 것보다 더 쉽다. 왜냐하면 그 훌라후프는 모든 그것의 질량을 바깥 edge를 향하여 갖기 때문이다. 문제를 좀 더 복잡하게 만들기 위해, 너가 회전시키려는 한 오브젝트의 점 과 축이 무엇인지에 따라 관성 모멘트는 바뀔 수 있다. 이러한 이유 때문에, 우리는 간단한 사각형을 사용할 것이다. 그래서 우리는 관성 모멘트의 적분에 잡혀있게 되지 않는다. 너는 moments of inertia of common shapes를 볼 수 있다; 만약 너가 복잡한 모형을 모델링 할 필요가 있다면, 그러면 너는 몇 가지 heavy-handed 적분과 세번의 적분 함수로 그렇게 할 수 있다.
마지막으로, 우리는 force를 "torque"로 대체한다. Torque는 한 오브젝트를 회전시키려는 경향을 가진 힘이다. Torque는 한 힘이 한 오브젝트의 회전의 중심으로부터 얼마나 멀리 적용될 수 있는지를 알아내어 계산될 수 있다. - 그러나 우리는 또한 우리의 오브젝트의 중심점에 대해 90도 각으로 누르는 힘의 component만을 봐야만 한다.
예를들어, 만약 너가 1 foot 길이의 wrench를 사용하고있고 너가 5 파운드의 힘으로 정확히 90도로 그것을 누른다면, 그 bolt에 대한 torque는 5 foot-pounds이다. 만약 너가 다른 각도로 누른다면, 그 torque는 더 작을 것이다. 만약 너가 wrench에 끝에서 bolt를 쪽으로 직접 누른다면, 그 torque는 0이 될 것이고, 그 wrench는 움직이지 않을 것이다.
그래서 우리는 회전에 대한 뉴턴의 운동 제 2법칙을 다시 쓸 수 있다. 나는 이것을 스칼라로 써왔다. 왜냐하면 우리는 오직 오늘날 z-axis에 대한 회전만을 생각하기 때문이다.
T = Ja
너무 쉬운 것처럼 보인다! 우리는 또한 정확히 translation에서 사용했던 같은 기법을 사용하여 이것을 적분할 수 있따. 초심자에게 이것에 대해 가장 어려운 부분은 일반적으로 힘이 torques를 만들어내는 방식을 알아내는 것이지만, 몇 가지 hard work, diagrams, and a linear algebra refresher로, 그것은 빠르게 사소한 일이 된다. Hint : vector cross proudct를 review해라. force vector과 "displacement" vector (힘이 적용된 곳에 대한 오브젝트의 센터로부터 거리)의 외적은 너에게 그 오브젝트에 대한 최종 torque를 준다. 너는 또한 너가 projecting vectors과 determining vector compompontes와 친숙해지도록 하기 위해 너의 삼각법을 닦기를 원할 것이다.
Checkpoint #2
이 예제는 rigid body rectangle을 모델링 한다. 그 사각형은 스프링으로 그것의 모서리 중의 하나에서 천장에 붙여져 있다. 그리고 떨어지는 것이 허용된다. 그 스프링은 펼쳐지고 모서리를 잡는다. 이것은 사각형이 튀기고 회전하게 한다.
이 예제에서 모델링된 다양한 힘들이 있다. 사각형의 무게는 힘으로 모델링 되었다. 스프링은 힘으로서 모델링 되었다. 그 힘은 사각형의 중심에 적용되지 않기에, 우리는 또한 사각혀을 회전하게 하는 torque를 계산할 필요가 있다. 만약 너가 스프링을 박스의 중심에 연결한다면, 그것은 전혀 회전하지 않을 것이다 (완전한 세계에서). 나는 또한 평행이동과 회전에 대해 둘 다 viscous damping(점성의, 끈적거리는 + 제동)을 모델링 했다. Viscous damping은 다른 물질들의 다양한 종합 마찰 손실들을 모델링하는 좋은 방법이다. 우리의 스프링은 완벽하지 않다. 그래서 그것은 영원히 튕기지 않을 것이다. Viscous damping은 결국 그 박스가 튀기고 회전하는 것을 멈추게 한다.
너는 또한 이 예제에서 Vector class와 Rectangle class를 볼 것이다. 모든 물리학은 벡터로 처리되고, 각 time-step마다 vector math를 또한 사용하여 그 박스를 회전시키고 평행이동 시킨다.
Collision Detection
물리 엔진의 가장 복잡한 측면은 collision detection이다. Collision detection은 일반적으로 매우 비싼 연산이고, 게임이 수십 또는 수백개의 오브젝트들을 가질지 모르기 때문에, 많은 노력이 collision detection 알고리즘을 최적화하는데 들어간다.
회전할 수 있는 오브젝트들이 충돌할 때 또 다른 복잡도가 나타나게 된다. 그러나, 또 다른 복잡도는 너가 복잡한 모양을 가진 오브젝트들을 충돌시키려 할 때 발생한다. 두 원이 충돌하는지를 체크하는 것은 쉽다; 너는 그것들의 중심 사이의 거리가 그것들의 반지름의 합보다 작은지를 확인하면 된다. 두 사각형이 충돌하는 것을 확인하는 것은 조금 까다롭다, 하지만 힘든 것 아니다. 만약 그것들이 회전하는 것이 허용되지 않는다면 (이러한 것들은 가끔 "AABB" 또는 "axis-aligned bounding boxes"라고 불려진다). 그 사각형이 일단 회전하는 것이 허용된다면, 그 문제는 까다로워지고, 삼각형, 오각형, 그리고 임의의 폴리곤들과 같은 다른 모양들에 대해서 계속 까다로워진다.
그래서 이 논의로는 끝낼 수 없으니, 우리는 convex polygons만을 고려할 것이다. 만약 너가 한 모양을 관통하는 어떤 선을 그릴 수 있고, 그것이 그 모양을 통해 자를 수 있다면, 그것은 convex polygon이다. 만약 너가 그 모양을 관통하여 자르는 한 직선을 두 번 이상 그릴 수 있다면, crescent moon 또는 별과 같은, 그러면 그 폴리곤은 concave(오목)하고, 우리는 그런 것들에 대해서 이야기 하지 않을 것이다.
사실, 대부분의 엔진들은 concave (어려운) 모양을 convex (더 쉬운) 모양의 한 묶음으로 쪼갠다. 그래서 우리가 오목 모양을 여기에서 이야기 하지 않더라도, 너는 이러한 이론들을 어떤 프로그램에 거의 맞게 확장할 수 있다.
전체 책들이 collision detection에 대해 쓰여져 왔기 때문에 (그리고 여전히 그것을 정의롭게 할 수 없다), 우리는 collision detection의 한 가지 측면에만 공 들일 것이다. 한 collision detection routine은 이것처럼 보일지도 모른다:
- world를 grid 또는 quadtree (3D에서는 octree)를 통해 쪼개라.
- 만약 두 오브젝트들이 그 그리드의 같은 섹션에 있다면, 너가 더 조사할지 보기위해 간단한 collision routine을 사용해라. 일반적으로 너는 이것에 대해 AABB testing을 사용할 것이다.
- 만약 너가 그 오브젝트가 충돌하고 있다고 생각한다면, 그것들이 충돌하는지에 대해 최종 답을 얻기위해 좀 더 철저한 알고리즘을 사용해라.
- 만약 그들이 충돌하고 있다면, 충돌에 대한 정보를 추출하고 그 오브젝트들이 어떻게 반응할지를 알아내어라.
그리고 불행하게도, 여기에 숨겨진 또 다른 복잡성이 있다: 만약 너가 매우 빠르게 움직이는 오브젝트들 (총알 같은), 그것들이 한 프레임에서 다음으로 갈 때 그것들의 타겟을 뛰어넘을 것이라는 것이 가능하다, 비록 그 총알이 타겟을 관통할지라도. 이것을 고치는 것은 continuous collision detection이라고 불려지는데, 지금, 우리는 discrete collision detection에 대해서만 이야기 할 것이다.
이제, 우리는 위의 세 가지 단계에 대해서만 이야기 할 것이다: 두 오브젝트들이 충돌하고 있는지를 어떻게 구분할지. 우리는 (steps 1과 2) 최적화를 제외할 것이지만, 운 좋게도 Build New Games는 이미 broad-phase collision detection에 대한 훌륭한 자료를 가지고 있다. 그리고 이것은 위의 steps 1과 2를 다룬다. 우리는 오직 매우 기본적인 collision response (step 4)를 수행할 것이고, continuous collision detection은 제외할 것이다- 그래서 너가 작거나 또는 빠른 오브젝트들에 대해 사용하려 한다면 우리의 솔루션은 버그가 있을지도 모른다.
Separating Axis Theorem
두 가지 우세한 collision detection 방식이 있다. GJK라고 불려지는 한 가지 방식은 3D collision detection을 위해 좀 더 흔히 사용된다. 왜냐하면 우리가 사용할 알고리즘은 3D에서 쓰일 때 비싸기 때문이다. 그러나, 그 separating axis theorem은 2D collision detection을 위해 널리 사용되고, 우리에게 운좋게도 개념화하고 시각화하는 것은 더욱 쉽다.
두 오브젝트들이 스크린에 있는 것을 상상하고, 우리가 그것들을 top-down perspective로 바라보고 있다고 상상해라 (예를들어, 우리는 헬리콥터에서 빌딩들의 지붕을 보고 있다). 그러한 두 오브젝트들이 충돌하는지를 테스트할 한 가지 방식은 아래로 내려가서 스크린에 오브젝트들과 같이 서는 것이다 (말하자면, street level에서), 그리고 그것들 주위에 원을 그리며 걸어간다. 만약 우리가 두 오브젝트들 사이의 한 틈(gap)을 본다면, 우리는 확실히 그것들이 충돌하지 않고 있다는 것을 안다. 만약 우리가 걸어가는 것을 끝내고, 그것들 사이에 어떠한 gap도 보지 못했다면, 그것들은 충돌하고 있음에 틀림없다. 왜냐하면 우리는 모든 가능한 각도로부터 그것들을 봤고, 두 오브젝트가 분리되었다는 것을 결코 못봤기 때문이다.
우리가 이것을 하기 위해 코드를 쓰려고 할 때, 우리는 오브젝트들 주변의 수백만개의 각도로부터 view를 체크할 수 없다. 그래서 우리는 그 절차를 간단하게 할 방식이 필요하다. 운좋게도, 우리는 오직 몇 가지 주요 지점들로부터의 view를 검사해야만 한다: 우리의 두 모형들에서 그 옆면들에 대해 각각 하나씩. 만약 우리가 한 삼각형과 heptagon (7개의 면을 가진)이 교차하는지 보려고 한다면, 우리는 10개의 다른 각도의 view를 체크해야만 한다.
좀 더 구체적으로, 우리가 하려는 것은 많은 다른 축들에 대해 오브젝트들의 그림자(사영)을 보는 것이다. 그리고 그것들의 그림자들이 중첩되는지를 보기위해 테스트하는 것이다. 만약 우리가 삼각형/7각형 예제에서 모든 10개의 축들을 점검하고, 그 그림자가 모든 10개의 축에서 겹친다면, 그러면 우리는 충돌을 갖게 된다. 만약 심지어 한 개의 축에 gap이 있다면, 우리는 즉시 보는 것을 멈춘다. 왜냐하면 두 오브젝트들이 명백히 충돌하고 있지 않기 때문이다.
게다가, 만약 우리가 사각형을 사용한다면, 우리는 상황을 더욱 간단하게 할 수 있다. 사각형은 평행한 변의 두 집합을 가지고 있고, 우리는 각 변에 대해 사영을 할 것이기 때문에, 우리는 각 사각형에 대해 복사 결과물의 두 집합을 갖을 것이다. 그러므로 우리는 사각형을 볼 때, 8개에서 4개의 축들을 검사하도록 숫자를 줄일 수 있다. text axes로서 사용할 각 사각형의 left and top side를 골라라 (또는 두 개의 수직한 변들).
벡터 수학은 separating axis theorem을 매우 쉽게 만든다. 우리는 우리의 테스트 축들을 간단히 대응되는 사각형 정점들에서 뺄셈하여 얻을 수 있고, "shadows"를 그러한 축들에 사영시키는 것은 각 사각형의 정점의 내적과 text axis를 찾는 것의 문제이다.
Collision Response
두 오브젝트들이 충돌하고 있는 것을 결정하는 것은 절반의 싸움이다. 오브젝트들이 충돌하는 것이 보였다면, 그것들은 어떤 방식으로 그것에 대해 반응할 필요가 있다. 이것의 많은 것은 너의 게임 메카닉에 의존할 것이다. 한 캐릭터에 의해 발포된 총알은 데미지를 줘야 한다. 한 미사일은 데미지를 주고 폭발해야만 한다.그러나 오늘날, 우리는 매우 물리적 반응을 볼 것이다: 두 박스들이 서로 부딪히고 튀기는 것들.
회전이 없는 두 간단한 모양들에 대해 Collision Response는 꽤 쉽다. Momentum(운동량), 또는 mass * velocity는 여기에서 우리를 도와준다. 두 개의 hard objects가 부딪힐 때, 두 오브젝트들의 총 운동량은 변하지 않는다. 실제 오브젝트들은 완벽히 hard하지 않다. 그래서 우리는 coefficient of restitution(복구)이라고 불리는 fudge factor(임시방편 요소)를 도입한다. 이것은 기본적으로 충돌의 탄성을 모델링 한다.
불행하게도, 우리의 회전하는 오브젝트들은 좀 더 복잡하다. 그 두 개의 오브젝트들은 서로 튕길 뿐만 아니라, 그것들의 회전은 오브젝트에 대해 충돌과 어떤 점이 관련되었는지에 따라 바뀔 것이다. 게다가, 실제 세계의 오브젝트들은 결코 그것들이 컴퓨터 시뮬레이션에서 할 수 있는 방식으로 "중첩"되지 않기에, 우리는 일반적으로 그것들의 위치를 역추적하고 수정한다. 그것들이 서로 닿고있고 중첩되지 않기 위해서.
이것은 우리에게 collision에 대해 좀 더 알도록 하는 필요성을 남겨둔다. 우리는 두 모양 사이의 중첩의 몇 가지 특징을 알고싶다. 만약 우리가 그것들이 닿는 순간 지점까지 그 충돌을 "되감기"한다면, 우리는 그 점의 위치를 알고싶다. 여러번, 우리는 또한 한 오브젝트가 다른 것을 "관통하는 깊이"를 알고 싶어할 것이다.
Collision detection과 collision response의 압도적인 복잡성 때문에, 우리는 여기에서 너무 깊게 들어갈 수 없다. 간단히 해서, 우리가 충돌을 되돌릴 필요가 없고, 우리가 어느정도 충돌과 연관된 한 점을 얻는 한, 우리는 무언가 할 것이라고 결정하자. 이용가능한 많은 좀 더 정교한 방식들이 있고, 이러한 것들을 배우는 가장 ㅈ호은 방식은 Box2d 또는 Bullet같은 존재하는 physics engines을 공부하는 것이다. Bullet과 Box2d는 JavaScript로 포트되어졌지만, 나는 너가 어떻게 그것을 읽는지 안다면, 원래 C++ source를 체크하기를 추천할 것이다; 몇 가지 포팅들은 자동적으로 수행되고 가독성을 위해 최적화되지 않았다.
일단 우리가 충돌과 관련된 한 지점을 발견한다면 (내가 그것을 어떻게 했는지 보기위해 다음 코드 예제를 보아라), collision response에서 그 정보를 우리가 사용할 수 있는 두 가지 방식이 있다. 우리는 충돌의 depth에 대한 정보를 사용하고 두 오브젝트들에 작용하는 매우 큰 힘을 생성할 수 있다 (어떤 것이 다른 것을 관통할 때 오브젝트의 물질의 "압축" 때문에 매우 뻣뻣한 스프링 처럼), 또는 좀 더 흔하게, 우리는 impulse response를 사용할 수 있다. 이것은 우리가 간단히 관계되는 힘과 상관없이 그 오브젝트의 속도 (기술적으로, 운동량)를 수정하는 것을 의미한다.
Checkpoint #3
우리의 최종 checkpoint는 고정된 박스와 부딪히고 떨어지는 회전하는 박스를 보여준다. separating axis theorem의 demo가 완전하지만, 그 collision response는 좀 더 정교한 기법이 되도록 남겨둔다.
그러나, 그 separating axis theorem test의 이 구현은 확실히 명백하지 않다. 그래서 너는 너의 사용에 맞게 너의 것을 만들어야만 한다. 이 예제는 일찍 끝나지 않는다. 만약 중첩되는 축이 없다면: 일찍 끝나는 것은 훌륭한 성능 최적화이다. 부가적으로 이 예제는 충돌과 가장 관련된 사각형의 정점을 추출하는 몇 가지 heuristics를 사용한다.
좀 더 정교한 구현들은 충격의 순간에 충돌을 되돌리고 또한 접촉 점과 normal를 반환하는 것을 포함한다. 부가적으로, 여기에서 collision response는 원시적이고, 물리적으로 정확하지 않다; separating axis theorem이 작동하는지를 보여주기 위해서인 것이다.
Conclusion
너는 이제 물리엔진을 구현하는데 요구되는 것을 더 잘 이해해할 것이다. 너의 여정은 여기에서 끝나지 않는다. 너의 편리성을 위해 내가 아래에 to-do list를 준다. 먄악 너가 이 자료를 즐겼다면, 부디 @bkanber on Twitter를 팔로우하고, 나의 블로그를 체크해라. 거기에서 나는 물리학, 머신러닝, 그리고 다른 흥미로운 것들을 이야기 한다.
To-Do:
- 기본 벡터 수학 함수를 배우고 그것들을 구현해라 : 덧셈, 곱셈, 내적, 외적, 회전, 길이는 모두 계산하기에 유용하다.
- 너가 할 수 있는 가능한 많은 다른 힘들에 대해 배워라 : 무게 (즉, gravity on Earth), spring force, viscous damping, air drag, static and dynamic friction, and gravitation (즉, 공간에서 중력)
- numerical integration tehniques을 배워라 : Euler's method (개념적 이해를 위해), velocity verlet (대부분의 심플 게임/kinematics), midpoint method (대부분의 간단한 프로그램들/일반 힘들), Runge-Kutta methods (고급의 그리고 정확한 시뮬레이션을 위한).
- rigid body에 적용될 때, 힘이 어떻게 torques가 되는지에 대해 이해를 증진시켜라. 이것은 checkpoint #2에서의 spring force와 함께 보여지지만, 너는 어떻게 힘이 torques가 되는지와, 회전할 때 오브젝트가 어떻게 행동하는지에 대한 이해를 개발하는데 목표를 두어야 한다.
- separating axims theorem을 배우고, 그것에 대해 철저한 직관적 이해를 개발해라. 이것은 collision detection에 대해서도 중요할 뿐만 아니라 벡터 수학을 학습하는 것을 강화하는데 도움이 된다. 이 기법은 그것의 구현에 있어서 몇 가지 벡터 개념을 사용하기 때문이다.
- 기본 AABB test로 separating axis theorem을 어떻게 간단하게 하는지 배워라. 너는 이것을 너의 collision detection algorithm의 값 싼 first-pass로서 사용할 수 있다.
- 너의 collision detection algorithms에서 좀 더 효과적인 first-pass로서 quadtrees에 대해 조사해라. 또한 quadtrees와 simple fixed grid를 사용하는 것 사이의 차이에 대해 생각해라. 너의 프로그램에 더 잘 어울리는 어떤 것이드 ㄴ선택해라; 너의 오브젝트들은 게임 월드 도처에 고르게 분산되어있는가? 아니면 그것들은 함꼐 뭉쳐있는가?
- continuous (discrete와 반대인) collision detection algorithms을 배워라. 너는 여전히 separating axis theorem 또는 AABB tests를 사용할 수 있지만, 너가 오브젝트를 테스트 하는 방식은 조금 다르다.
- 좀 더 정교한 collision response techniques을 배워라. force-based methods와 impulse-based methods가 있다. 너가 선택하는 route는 너가 어떻게 오브젝트를 모델링 할지와 너의 collision detection algorithm이 무슨 정보를 반환할지 달려있다. collision normals, angle of reflection and momentum에 대해 배워라.
- GJK algorithm을 이해해라. 만약 너가 3D쪽으로 작업한다면, 이것이 매우 도움이 될 것이다. 하지만 비록 너가 2D에서만 작업한다 할지라도, 그것은 노력할 가치가 있다. GJK 알고리즘은 매우 추상적이고 그것에 대한 직관력을 얻기에 어렵지만, 내가 본 것중에 가장 흥미로운 알고리즘들 중 하나이다. 그리고 그것은 똑같이 흥미로운 수학적 개념들에 기반을 둔다.
댓글 없음:
댓글 쓰기