Advanced Character Physics
Abstract
이 글은 상호적인 사용에 잘 적합한 physically-based modeling에 대한 접근법의 기본 요소를 설명한다. 그것은 간단하고, 빠르고, 그리고 꽤 안전하다. 그리고 그것의 기본적인 버전에서, 그 방식은 고급 수학 주제의 지식을 요구하지 않는다 (비록 그것이 탄탄한 수학적 기초를 기반에 둘지라도). 그것은 두 개의 직물의 시뮬레이션을 할 수 있게 한다; 바로 soft and rigid bodies이다; 그리고 심지어 forward and inverse kinematics 둘 다를 사용한 articulated or constrained bodies까지도.
그 알고리즘들은 IO Interactive의 게임 Hitman: Codename 47을 위해서 개발 되었다. 다른 것들 중에서, 물리 시스템은 옷, 식물, rigid bodies의 움직임을 책임지고, 몸이 어디를 맞았는지에 따라서 독특한 방식으로 죽은 인간의 몸이 떨어지도록 만드는 것과, 완전히 환경과 상호작용하는 것을 책임진다 (press oxymoron의 "살아있는 것 같은 death animations"같은 것을 만들어낸다).
그 자료는 또한 penetration test optimization(관통 검사 최적화)과 friction handling(마찰 다루기)와 같은 세부요소들을 다룬다.
1. Introduction
좋게 보이는 animation을 만드는 physically-based modeling을 사용하는 것은 어떤 시간동안 고려되어져 왔고, 많은 존재하는 기법들은 꽤 정교해졌다. 다른 접근법들은 문헌에서 제안되어왔고, 많은 노력이 정확하고 신뢰할만한 알고리즘들을 구성하기위해 들어갔다. 실제로, 물리와 역학의 정확한 시뮬레이션 방식은 공학으로부터 꽤 오랫동안 알려져 있었다. 그러나, 게임과 상호작용 사용을 위해서, 정확성은 정말 우선적인 걱정이 아니다 (비록 그것이 가지기에 좋을지라도) - 오히려, 여기에서 중요한 목표는 believability(신뢰성)과(프로그래머는 만약 플레이어가 여전히 집중해있다면 그가 원하는 만큼 속일 수 있다) 그리고 실행 속도 이다. (frame당 오직 어떤 시간이 물리엔진에 허용되어질 것이다) 물리 시뮬레이션의 경우에, believability라는 단어는 또한 안정성을 포함한다; 만약 오브젝트들이 여전히 누워있을 때 장애물들 사이에서 표류하는 것처럼 보이거나 진동하는 것처럼 보인다면, 또는 옷 particles들이 날아가버리는 경향이 있다면, 그 방식은 좋지 않은 것이다.
이 글에서 보여지는 방식들은 이러한 목표들을 달성하는 시도로 만들어졌다. 그 알고리즘들은 IO Interactive의 컴퓨터 게임 Hitman: Codename 47에서 사용하기 위해 그 저자들에 의해 개발되고 구현되었다. 그리고 그 알고리즘들은 IO의 in-house game engine Glacier에 통합되어왔다. 그 방식들은 구현하기에 꽤 쉽다고 증명되었고 (적어도 다른 전략과 비교해서) 그리고 높은 성능을 가진다.
그 알고리즘은 반복적이다. 어떤 지점으로부터 그것이 어떤 시간에 멈출 수 있도로 ㄱ하기 위해서이다. 이것은 우리에게 매우 유용한 time/accuracy trade-off를 준다: 만약 부정확성이 어느정도 받아들여진다면, 그 코드는 더 빠르게 작동하도록 허용될 수 있다; 이 error margin은 심지어 run-time에 적응적으로(adaptively) 조절되어질 수 있다. 어떤 경우에, 그 방식은 다른 존재하는 방식들보다 더 빠른 크기의 순서를 가진다. 그것은 또한 같은 framework에서 충돌과 resting contact를 처리하고, 쌓아진 박스들을 잘 처리하고, 물리엔진을 강조하는 다른상황들도 잘 처리한다.
전반적으로, 그 방식의 성공은 서로로부터 이득이 되는 몇 가지 기법들의 옳은 조합으로부터 온다:
- 소위 Verlet integration scheme (Verlet 적분 전략)
- projection(사영)으로 충돌과 관통 처리하기
- relaxation(휴식)을 사용하는 간단한 constraint solver
- 튼튼한 속도 향상을 주는 좋은 square root 근사
- rigid bodies를 constraints를 가진 파티클로 모델링
- 관통 깊이를 계산하는 능력을 가진 최적화된 충돌 엔진
위의 주제들 각각은 짧게 설명될 것이다. 이 문서를 쓸 때, 그 저자는 구현에 필수적인 중요한 정보를 잃지 않고, 가장 넓고 가능한 청중들이 접근가능하게 만들려고 노력해왔다. 이것은 기술적 수학 설명과 개념들이 최소한으로 되었다는것을 의미한다. 만약 그렇게 하는 것이 그 주제를 이해하는데 중요하지 않다면. 목적은 많은 수학적 복잡성을 다루지 않고 꽤 고급의 그리고 안정적인 물리 시뮬레이션을 구현하는 가능성을 보여주는 것이다.
내용은 다음과 같이 구성된다. 처음에, Section 2에서, particle system의 "velocity-less" 표현이 설명될 것이다. 그것은 몇 가지 장점들을 가지는데, 안정성이 가장 눈에듸고, constraints가 구현하기에 쉽다는 사실이 있다. Section 3는 어떻게 충돌 처리가 발생하는지 설명한다. 그러고나서, Section 4에서, particle system은 우리가 cloth를 모델링하게 허용하는 constraints와 함꼐 확장된다. Section 5는 rigid body를 모방하기 위해 적절히 constrained particle system을 어떻게 설정하는지를 설명한다. 다음으로, Section 6에서, 그 관절 몸체를 하기위해 그 시스템을 어떻게 더 확장시키는지가 보여진다 (즉, angular and other constraints가 있는 상호 연결된 rigid bodies의 시스템을 말한다). Section 7은 다양한 메모를 포함하고, 마찰을 구현하는데 있어서의 몇 가지 경험을 공유한다 등등. 마지막으로, Section 8에서 간단한 결론을 짓는다.
다음으로, bold typeface는 vectors를 가리킨다. Vector components는 subscript를 사용해서 인덱싱된다. 즉, x = (x_1, x_2, x_3).
2. Verlet integration
시뮬레이션의 심장은 particle system이다. 일반적으로, 파티클 시스템의 구현에 있어서, 각 파티클은 두 가지 주된 변수를 갖는다: 그것의 위치 x와 그것의 속도 v. 그러고나서 time-stepping loop에서, 새로운 위치 x'와 새로운 속도 v'는 종종 이 규칙을 적용하여 계산된다.
여기에서 delta_t는 time step이고, a는 뉴턴의 법칙 f = ma (여기에서 f는 파티클에 작용하는 축적된 힘이다)을 사용하여 계산된 가속도이다. 이것은 간단한 Euler integration (오일러 적분)이다.
여기에서, 그러나 우리는 velocity-less 표기법과 다른 적분 전략을 선택한다: 각 파티클의 위치와 속도를 저장하는 대신에, 우리는 그것의 현재 포지션 x와 그것의 이전 포지션 x*을 저장한다. time step이 고정되게 유지하고, 그 업데이트 규칙 (또는 적분 단계)는 이렇게 된다.
이것은 Verlet integration이라고 불리고, 분자 역학을 시뮬레이션 할 때 집중적으로 사용된다. 속도가 implicitly하게 주어지기 때문에 꽤 안정적이고, 결과적으로 속도와 위치가 sync가 안맞기가 더 어려워 진다. (부가적인 메모로서, 물에서 물결을 만드는 잘 알려진 데모 효과는 비슷한 접근법을 사용한다.) 그것은 다음의 사실 때문에 작동한다. 2x-x* = x + (x-x*)이고 x-x*는 현재 속도의 근사이다 (실제로, 그것은 지난 time step에서 이동한 거리이다). 그것은 항상 매우 정확한 것은 아니지만 (에너지가 그 시스템을 떠날지도 모른다, 즉, 소멸한다), 빠르고 안정적이다. 그 업데이트 규칙을 x' = 1.99x - 0.99x* + a*・△t^2과 같은 것으로 바꾸는 것은 작은 양의 drag(공기저항)을 또한 시스템에 도입할 수 있다.
각 step의 끝에서, 각 파티클에 대해, 현지 위치 x는 대응되는 변수 x*에 저장된다. 많은 파티클들을 조작할 떄, 유용한 최적화는 간단히 배열 포인터들을 swap하여 가능하다.
최종 코드는 이것처럼 보일 것이다 (Vector3 class는 적절한 멤버 함수와 벡터를 다루기 위해 오버로드된 연산자를 포함해야 한다)
#ifndef __PARTICLE_SYSTEM_H__ #define __PARTICLE_SYSTEM_H__ #include <vector> #include <glm/glm.hpp> #include <glm/gtc/matrix_transform.hpp> #include <glm/gtc/type_ptr.hpp> #define NUM_PARTICLES 2 class ParticleSystem { public: ParticleSystem(std::vector<glm::vec3>& position, float timestep); glm::vec3 m_position[NUM_PARTICLES]; // Current positions void TimeStep(); private: void Verlet(); void SatisfyConstraints(); void AccumulateForces(); glm::vec3 m_oldPosition[NUM_PARTICLES]; // Previous positions glm::vec3 m_acceleration[NUM_PARTICLES]; // Force accumulators glm::vec3 m_vGravity = glm::vec3(0.f, -0.098f, 0.0); // gravity for temporary test float m_fTimeStep; }; #endif
#include "ParticleSystem.h" ParticleSystem::ParticleSystem(std::vector<glm::vec3>& position, float timestep) : m_fTimeStep(timestep) { for (unsigned int i = 0; i < position.size(); ++i) m_position[i] = m_oldPosition[i] = position[i]; } void ParticleSystem::Verlet() { for (int i = 0; i < NUM_PARTICLES; ++i) { glm::vec3 temp = m_position[i]; // x' = 2x - x* + a * dt^2 m_position[i] = m_position[i] + (m_position[i] - m_oldPosition[i]) + m_acceleration[i] * m_fTimeStep * m_fTimeStep; // x* = x m_oldPosition[i] = temp; } } void ParticleSystem::AccumulateForces() { // All particles are influenced by gravity for (int i = 0; i < NUM_PARTICLES; ++i) m_acceleration[i] = m_vGravity; } void ParticleSystem::SatisfyConstraints() { // Ignore this function for now } void ParticleSystem::TimeStep() { AccumulateForces(); Verlet(); SatisfyConstraints(); }
particleSystem.TimeStep(); for (unsigned int i = 0; i < firstP.size(); ++i) { simpleShader.use(); simpleShader.setMat4("projection", projection); simpleShader.setMat4("view", view); model = glm::mat4(1.0); model = glm::translate(model, parti.m_position[i]); model = glm::scale(model, glm::vec3(0.8)); simpleShader.setMat4("model", model); glActiveTexture(GL_TEXTURE0); glBindTexture(GL_TEXTURE_2D, containerTexture); renderCube(); }
{ timestep을 60frame에 맞게하기위해 1.0/60.0으로 맞춰주었고, OpenGL에게도 Vsync하도록하여 60frame에 맞추었다. 그리고 링크에 제공된 소스를 OpenGL 환경에서 렌더링하기 위해서, 조금 수정을 가했다. 실행 결과는:
아주 간단히 그냥 천천히 내려가는 것 뿐이다. 이제 여기서 자료를 따라 더욱 좋은 파티클 시스템을 확장해나가자 }
위의 코드는 속도가 아니라 명확성을 위해 쓰여진 것이다. 한 가지 최적화는 state representation에 대해 Vector3 대신에 float의 배열을 사용할 것이다. 이것은 vector processor에서 시스템을 구현하기에 더 쉽게 만든다.
이것 아마도 아직 획기적이게 들리지 않는다. 그러나, 그 이점들은 우리가 constraints를 사용하고 rigid bodies로 전환할 때 곧 명백해진다. 위의 적분 전략이 증가된 안정성을 이끌고 다른 접근법과 비교해서 줄어든 연산의 양을 이끈다는 방식이 그러고나서 보여질 것이다.
예를들어 a = (0,0,1)로 설정하고, x = (1,0,0), x* = (0,0,0)으로 시작 조건을 사용해라. 그러고나서 직접 몇 번 반복하고 무엇이 일어나는지 보아라.
3. Collision and contact handling by projection
소위 penalty-based 전략들은 관통점(penetration points)에 스프링을 삽입하여 접촉(contact)를 처리한다. 이것이 구현하기에 매우 간단하지만, 그것은 많은 심각한 단점들을 갖는다. 예를들어, 한 편으로 오브젝트들이 너무 많이 관통하지 않도록하고, 다른 한편으로는 최종 결과가 불안정하지 않도록 적절한 스프링 상수를 고르는 것이 어렵다. 물리 시뮬레이션의 다른 전략에서, 충돌은 정확한 충돌의 지점에 대한 시간으로 되감아서 처리 된다 (예를들어 이분 탐색으로), 그리고 이것은 거기로부터 충돌을 analytically하게 처리하고, 그 시뮬레이션을 재시작한다 - 이것은 real-time 관점에서는 실용적이지 않다. 왜냐하면 많은 충돌이 있을 때 그 코드는 잠재적으로 느리게 돌아간다.
여기에서, 우리는 다른 전략을 사용한다. Offending points(부딪히는 점)들은 간단히 장애물 밖으로 사영된다. 사영으로, 대강 말해서, 우리는 그 점을 장애물 밖으로 가능한한 적게 움직이는 것을 의미한다. 보통, 이것은 그 점을 충돌하는 표면쪽으로 수직으로 점을 움직이는 것을 의미한다. 한 예제를 봐보자. 우리의 세계가 큐브안에 (0,0,0) - (1000, 1000, 1000)에 있다고 가정하고, 또한 그 파티클의 restitution coefficient(복구 계수)가 0이라고 가정하자 (즉, 파티클들은 충돌할 때 표면에 튕기지 않는다). 모든 점들이 유요한 간격(범위)에 있도록 하기 위해서, 대응되는 사영 코드는 이렇게 될 것이다.
// Implements particles in a box void ParticleSystem::SatisfyConstraints() { for (int i = 0; i < NUM_PARTICLES; ++i) // for all particles { glm::vec3& x = m_position[i]; x = glm::min(glm::max(x, glm::vec3(0.f, 0.f, 0.f)), glm::vec3(100.f, 100.f, 100.f)); } }
)
(vmax는 component 순으로 최대인 것을 취하여 vectors에 작동한다. 반면에 vmin은 component순으로 최소인 것을 취한다. 즉 max((1, -1, 3), (0,0,0)은 (1, 0, 3)을 컴포넌트 별로 비교하여 큰 것을 반환한다는 것이다)
이것은 모든 파티클 포지션들이 cube안에 있도록 유지하고, 충돌가 resting contact(쉬고있는 접촉점) 둘 다를 처리한다. Verlet integration 전략의 아름다움은 대응되는 속도의 변화가 자동으로 처리될 것이라는 것이다. TimeStep()의 다음 호출에서, 그 속도는 자동적으로 표면의 normal direction에서 어떠한 컴포넌트도 포함하지 않도록 규제되어질 것이다. (0인 탄성계수와 대응된다). 그림 1을 보아라.
시도해보아라 - 직접적으로 normal direction인 속도를 취소할 필요가 없다. 위의 것이 어느정도 파티클들을 볼 때 사소한 것처럼 보일지라도, Verlet integration 전략의 강점은 constraints와 rigid bodies를 도입할 때 이제 빛나기 시작할 것이고, 명백해 질것이다.
4. Solving several concurrent constraints by relaxation
옷감에 대한 공통된 모델은 상호 연ㅇ결된 스프링과 파티클들의 간다한 시스템으로 구성되어 있다. 그러나 미분 방정식의 대응되는 시스템을 푸는 것은 항상 사소한 것은 아니다. 그것은 penalty-based systems과 같은 문제들 몇 가지를 겪는다: 만약 오직 간단한 integration 기법이 사용되다면 강한 스프링들은 불안정성을 만드는 stiff systems of equations으로 이끌게 된다. 또는 나쁜 성능이 된다. 그리고 이것도 고통이다. 역으로 약한 스프링들은 탄성적으로 천처럼 보이게 된다.
그러나 만약 우리가 그 스프링의 뻣뻣함이 무한이 되게하면 흥미로운 것이 발생한다. 그 시스템은 갑자기 매우 간단하고 빠른 접근법과 함께 안정된 방식으로 해결 가능하다. 그러나 우리가 옷감에 대해 계속해서 말하기전에, 이전의 예시를 다시 봐보자. 위에서 고려된 cube는 항상 만족해야만 하는 파티클 포지션에 대해 일방적인 constraints의 모음으로서 고려될 수 있다 (그 큐브의 한 면에 대해 하나씩):
x_i >= 0 and x_i <= 1000 for i = 1,2,3. (C1)
예시로, constraints는 particles들을 cube surfaces로 사영하여 offending positions을 간단히 수정하여 만족된다. (즉, 파티클들은 큐브 안에서 유지된다) (C1)을 만족시키기 위해, 우리는 다음의 슈도코드를 사용한다
/ Pseudo-code to satisfy (C1) for i = 1,2,3 set x_1 = min{max{x_i,0}, 1000}
어떤 사람은 이 프로세스를 파티클과 관통하는 표면사이에 stiff springs을 무한히 집어넣는 것으로 생각할지도 모른다. - 정확히 매우 강하고 적절히 damped되어서 끊임없이 그것들이 rest length zero를 도달하게 하는 스프링들
우리는 이제 길이가 100인 막대를 모델링하는 실험으로 확장한다. 우리는 두 개의 개별 파티클을 설정하야 (positions x1 and x2) 이것을 하고그리고 그것들이 100의 거리로 떨어지기를 요구한다. 수학적으로 표현하자면, 우리는 다음의 bilateral (Equality) constraint(제약)을 얻는다:
|x2 - x1| = 100 (C2)
비록 그 파티클들이 정확히 초기에 배치되었을지라도, 한 번의 적분 step후에, 그것들 사이의 separation distance 무효하게 될 지도 모른다. 다시 한 번 정확한 거리를 얻기 위해, 우리는 그것들을 (C2)에서 설명된 해집합으로 사영시켜 파티클들을 움직인다. 이것은 서로로부터 직접 파티클들을 밀어내거나 또는 그것들을 함께 가까이 잡아당겨서 처리된다. (잘못된 거리가 너무 작거나 또는 너무 큰 것에 기반으로). 그림 2를 보아라.
제약 (C2)를 만족시키는 슈도코드는
// Pseudo-code to satisfy (C2) delta = x2-x1; deltalength = sqrt(delta*delta); diff = (deltalength - restlength) / deltalength; x1 += delta * 0.5 * diff; x2 -= delta * 0.5 * diff;
delta는 한 벡터인 것을 주목해라. 그래서 delta * delta는 실제로 내적이다. restlength가 100이면서, 위의 슈도코드는 파티클들 서로를 분리하거나 잡아당길 것이다. 그것들이 그것들 사이의 정확한 100의 거리를 달성하도록 하기 위해서이다. 또 다시 우리는 마치 rest length 100인 매우 뻣뻣한 spring이 파티클들이 끊임없이 옳게 배치되도록 파티클 사이에 삽입된 것처럼 생각할지도 모른다.
이제 우리가 여전히 파티클들이 cube constraints를 만족하길 원한다고 가정하자. 그러나 그 stick constraint를 만족시켜서, 우리는 한 파티클을 큐브밖으로 밀어서 그 cube constraints의 하나 이상을 무효화할지도 모른다. 이 상황은 즉시 그 offending particle position을 그 cube surface로 다시 한 번 사영시켜서 해결될 수 있지만, 그러고나서 우리는 그 stick constraint를 또 다시 무효하게 한다.
정마로, 우리가 해야하는 것은 한 번에 모든 constraints에 대해 그 (C1)과 (C2) 둘 다를 해결하는 것이다. 이것은 연립방정식을 푸는 한 문제이다. 그러나, 우리는 LOCAL ITERATION으로 간접적으로 진행하는 것으 ㄹ선택한다. 우리는 간단히 여러 번 슈도코드의 두 조각들을 반복한다. 그 결과가 유용하기를 희망하면서. 이것은 다음의 코드를 만든다:
// Implements simulation of a stick in a box void ParticleSystem::SatisfyConstraints() { for (int i = 0; i < NUM_ITERATIONS; ++i) { for (int j = 0; j < NUM_PARTICLES; ++j) // for all particles { m_position[j] = glm::min(glm::max(m_position[j], glm::vec3(0.f, 0.f, 0.f)), glm::vec3(50.f, 50.f, 50.f)); } // Then satisfy(C2) glm::vec3 delta = m_position[1] - m_position[0]; float deltaLength = glm::length(delta); float diff = (deltaLength - m_restLength) / deltaLength; m_position[0] += delta * 0.5f * diff; m_position[1] -= delta * 0.5f * diff; } }
(두 파티클들의 초기화가 생략되었다.) 이 순수한 반복 접근법이 어느정도 단순해 보일지라도, 그것은 실제로 우리가 찾고있는 솔루션에 수렴한다는 것이 밝혀진다! 그 방식은 relaxation이라고 불려진다 (또는 너가 그것을 정확히 어떻게 하는지에 따라 Jacobi or Gauss-Seidel iteration). 그것은 연속적으로 다양한 local constraints들을 만족시키고 반복하여 작동한다. 만약 그 조건이 옳다면, 이것은 동시에 모든 constraints를 만족시키는 global configuration에 대해 수렴할 것이다. 그것은 많은 다른 상황에서 유용한데, 몇 가지 상호 의존적인 constraints가 동시에 만족되어야 하는 상황을 말한다.
필요한 반복의 개수는 물리 시뮬레이션 시스템과 동작의 양마다 다르다. 그것은 마지막 반복으로부터 변화를 측정하여 적응적으로(adaptive) 만들어질 수 있다. 만약 우리가 그 반복을 일찍 끝낸다면, 그 결과는 꽤 유요하지 않게 될지도 모른다. 그러나 Verlet scheme 때문에, 다음 프레임에서 그것은 아마도 더 나을 것이고, 다음 프레임에서 심지어 더 좋아진다. 이것은 일찍 끝내는 것이 모든 것을 파괴하지 않을 것이라는 것을 의미한다. 비록 그 최종 애니메이션이 어느정도 엉성하게 보일지라도.
Cloth simulation
stick constraint가 정말 hard spring으로 고려될 수 있다는 사실은 이 섹션의 초반에 그려진 cloth simulation에 대해 그것의 유용함을 명백하게 만들어야 한다. 예를들어, 천을 묘사하는 삼각형들의 한 육각형 메쉬가 구성되어졌다고 가정하자. 각 vertex에 대해 한 파티클은 초기화 되어지고, 각 edge에 대해, 두 상응하는 파티클들 사이의 stick constraint가 초기화 된다 (constraint의 "rest length"는 두 정점 사이의 간단히 초기 거리가 된다.)
HandleConstraints() 함수는 그러고나서 모든 constraints에 대해 relaxation을 사용한다. 그 relaxation loop는 몇 번 반복되어질 수 있다. 그러나, 좋게 보이는 애니메이션을 얻기 위해, 실제로 대부분의 cloth 조각들에 대해, 오직 한 번의 iteration이 필수적이다. 이것은 cloth simulation에서 time usage가 거의 N square root 연산과 수행되는 N division 의존한다는 것을 의미한다. (여기에서 N은 cloth mesh에서의 edges의 개수이다. 우리가 보듯이, 똑똑한 트릭은 이것을 frame update마다 N divisions로 만드는 것이 가능하다 - 이것은 정말 빠르고 어떤 이는 그것은 이보다 더빨라질 수 없다고 주장할지도 모른다.
// Implements simulation of a stick in a box void ParticleSystem::SatisfyConstraints() { for (int i = 0; i < NUM_ITERATIONS; ++i) { for (int j = 0; j < NUM_PARTICLES; ++j) // for all particles { m_position[j] = glm::min(glm::max(m_position[j], glm::vec3(-50.f, 0.f, -50.f)), glm::vec3(50.f, 50.f, 50.f)); } for (int j = 0; j < NUM_CONSTRAINTS; ++j) { Constraint& c = m_constraint[j]; glm::vec3 delta = m_position[c.particleB] - m_position[c.particleA]; float deltaLength = glm::length(delta); float diff = (deltaLength - c.restlength) / deltaLength; m_position[c.particleA] += delta * 0.5f * diff; m_position[c.particleB] -= delta * 0.5f * diff; } } }
for (int j = 0; j < 5; ++j) for (int i = 0; i < 5; ++i) firstP.push_back(glm::vec3((i - 2) * 5.f, j * 5.f, 0.f)); glm::vec3 testMap[5][5]; for (int j = 0; j < 5; ++j) for (int i = 0; i < 5; ++i) testMap[j][i] = glm::vec3((i - 2) * 5.f, j * 5.f, 0.f); int dx[4] = { -1, 1, 0, 0 }; int dy[4] = { 0, 0, -1, 1 }; bool isvisit[5][5] = { false, }; srand(100); std::vector<Constraint> conSet; for (int j = 0; j < 5; ++j) for (int i = 0; i < 5; ++i) { isvisit[j][i] = true; int y = j; int x = i; Constraint temp; temp.particleA = j * 5 + i; for (int k = 0; k < 4; ++k) { int newY = y + dy[k]; int newX = x + dx[k]; if (newX < 0 || newX >= 5 || newY < 0 || newY >= 5 || isvisit[newY][newX]) continue; temp.particleB = newY * 5 + newX; temp.restlength = 5.f + (rand() % 10) * 0.5232; conSet.push_back(temp); } }
우리는 이제 어떻게 square root operation을 제거할지를 이야기 한다. 만약 그 constraints가 모두 만족한다면, 우리는 특별한 constraint expression에서 이미 square root operation의 결과가 무엇인지 안다. 이름하여 대응되는 stick의 rest length ㄱ이다. 우리는 그 square root function을 근사하기 위해 이 사실을 사용할 수 있다. 수학적으로, 우리가 하는 것은 r*r인 rest length의 제곱에서 1차수 테일러 급수로 square root function을 근사하는 것이다. (이것은 초기 추정치 r로 한 Newton-Raphson iteration과 동일한 것이다). 몇 가지 다시 쓴 후에, 우리는 다음의 쉐도 코드를 얻는다:
delta = x2-x1; delta *= restlength * restlength / (delta * delta + restlength * restlength) - 0.5; x1 += delta; x2 -= delta;
만약 그 거리가 정확한다면 (즉, |delta| = restlength라면), 그러면 delta = (0,0,0) 을 얻고 어떠한 변화도 일어나지 않을 것이다.
constraint마다, 우리는 zero square roots를 사용한다. 그리고 그 제곱근 값 restlength * restlength는 심지어 미리 계산되어질 수 있다! 시간을 소비하는 연산을 사용하는 것은 이제 frame 당 N divisions으로 내려간다. (그리고 대응되는 메모리 접근들) - 그것은 이보다 더 빨라질 수 없고, 그 결과는 심지어 꽤 보기 좋다. 실제로, Hitman에서 그 cloth simulation의 전체 속도는 대개 rendering system에서 얼마나 많은 삼각형을 밀어내는 방식에 의해 제한되었다.
그 constraints는 한 번의 반복 후에 만족된다고 보장되지 않지만, Verlet integration scheme 때문에, 그 시스템은 빠르게 몇 프레임에 대해 정확한 상태로 수렴할 것이다. 실제로, 오직 한 번의 반복을 사용하고, 그 제곱근을 근사하는 것은 sticks가 완벽히 뻣뻣할 때 나타나는 stiffness를 제거한다.
전략적으로 선택된 이웃을 공유하는 정점들 사이에 support sticks를 두어서, cloth algorithm은 식물들을 simulate하도록 확장 되어질 수 있다. 또 다시, Hitman에서 relaxation loop의 한 번만이 충분 했었다 (사실, 그 낮응ㄴ 숫자는 식물에게 휘는 행동의 올바른 양을 주었다).
이 섹션에서 다루어진 그 코드와 방정식은 모든 파티클들이 동일한 질량을 갖는 것을 ㅏㄱ정한다. 물론, 다른 질량을 가진 파티클들을 모델링하는 것이 가능하다. 그 방정식은 조금 더 복잡하다.
particle masses와 관련해서 (C2)를 만족하기 위해서 다음의 코드를 사용한다:
// Pseudo-code to satisfy (C2) delta = x2-x1; deltalength = sqrt(delta * delta); diff = (deltalength - restlength) / (deltalength * (invmass1 + invmass2)); x1 += invmass1 * delta * diff; x2 -= invmass2 * delta * diff;
여기에서 invmass1과 invmass2는 두 질량의 수적인 역수이다. 만약 우리가 한 파티클이 움직일 수 없기를 원한다면, 간단히 그 파티클에 대해 invmass = 0으로 설정한다 (무한의 질량과 일치한다). 물론 위의 경우에 square root는 또한 속도 향상을 위해 근사되어질 수 있다.
5. Rigid bodies
rigid bodies의 움직임을 관리하는 방정식들은 현대 컴퓨터의 발명되기 오래 전에 발견되었다. 그 당시에 유용한 것이라고 말할 수 있기 위해서, 수학자들은 수식들을 symbolically하게 조작할 능력이 필요했었다. rigid bodies의 이론에서, 이것은 inertia tensors, angular momentum, torque, 방향을 나타내기 위한 쿼터니언 등 과 같은 실용적인 개념을 이끌었다. 그러나, 수적으로 엄청난 양의 데이터를 처리하는 현재의 능력으로, 그것은 그럴듯 해졌고, 어떤 경우에 심지어 시뮬레이션을 작동할 때 더 간단한 요소들을 계산을 분해하는데에 이점이 있었다. 3D rigid bodies의 경우에, 이것은 네 개의 파티클들과 6개의 constraints (4x3 - 6 = 6의 자유도의 정확한 양을 주는)에 의해 rigid body를 모델링 하는 것을 의미할 수 있다. 이것은 많은 측면을 간단하게 하고, 그리고 그것은 정확히 우리가 다음에서 할 것이다.
사면체를 생각하고, 네 개의 점 각각에 한 파티클을 두자. 게다가, 4면체에서 6개의 edges들의 각각에 대해, 이전의 섹션에서 논의 되었던 stick constraint같은 거리를 만들어라. 이것은 실제로 기본적으로 rigid body를 시뮬레이션 하기에 충분하다. 그 4면체는 cube world안에서 풀리게 할 수 있다. 그리고 그 Verlet integrator는 그것을 빠르게 움직이게 할 것이다. 그 함수 SatisfyConstraints()는 두 가지 것들을 신경쓴다: 1) 그 파티클들은 큐브내에 유지되어야 한다 (이전처럼), 그리고 2) 그 6개의 거리 constraints가 만족되어야 한다. 또 다시, 이것은 relaxation approach를 사용하여 처리될 수 있다; 3 or 4번의 반복이 최적의 square root approximation에 충분할 것이다.
(사면체의 모양이 나오게 된다)
이제 명백히, 일반적인 rigid bodies는 사면체의 충돌 순으로 행동하지 않는다 (삐록 그것들이 역학적으로 그렇게 할지라도). 또한 다른 문제가 있다: 현재, rigid body와 world exterior 사이의 충돌 탐지는 vertex만을 기반에 둔다. 즉, 만약 한 vertex가 world 밖에 있는 것이 발견된다면, 그것은 다시 안으로 사영된다. 이것은 world의 내부가 convex(볼록)하는 한 괜찮게 작동한다. 만약 그 world가 non-convex라면, 그러면 그 사면체와 world exterior는 실제로 서로를 관통할 수 있다. tetrahedron의 정점이 불법의 지역에 있는 것 없이 (그림 3을 보아라, 거기에서 삼각형은 사면체의 2D 유사체를 나타낸다). 이 문제는 다음에서 처리된다.
우리는 처음에 그 문제의 더 간단한 버전을 고려할 거싱다. 이전의 stick example을 고려해보자. world exterior가 그것에 작은 bump를 가지고 있다고 가정하자. 그 stick은 이제 두 개의 stick particles들이 world를 떠나는 것 없이 world exterior를 관통할 수 있다 (그림 4를 보아라). 우리는 collision detection engine을 구성하는 복잡함에는 가지 않을 것이다. 이것은 그 자체로 과학이기 때문이다. 대신에, 우리는 우리가 collision을 탐지하도록 해주는 이용가능한 subsytem이 있다고 가정한다. 게다가, 우리는 그 subsystem이 우리에게 penetration depth를 알려줄 수 있고, 두 충돌하는 물체의 각각의 관통점을 인식할 수 있다고 가정한다. (관통점과 관통 깊이의 한 정의는 이것과 같다: 관통 깊이 d_p는 그 두 오브젝트가 관통하지 못하게 막는 최단 거리이다. 만약 어떤 하나가 적절한 방향으로 거리 d_p로 그 오브젝트들 중 하나를 움직인다면. 관통점은 각 오브젝트가 정확히 그 다른 오브젝트를 닿는 각 오브젝트 위에 있는 지점이다. 이것은 앞에서 언급된 이동이 발생한 후에 있는 것이다.)
그림 4를 다시 봐보자. 여기에서 stick은 Verlet step후에 bump를 관통해 지나갔다. 그 충돌 엔진은 두 관통점 p와 q를 인식했다. 그림 4a에서, p는 실제로 particle 1의 위치와 같다, 즉 p = x1이다.
...
댓글 없음:
댓글 쓰기