고급 물리 솔버를 활용한 시뮬레이션 및 성능 향상
2016년에 우리는 다양한 새로운 물리 제약 조건에 대한 지원을 추가하여, 개발자들이 새로운 솔버로 전환하도록 유도하고 물리 엔진의 창의적 기능을 확장했습니다. 새로 생성된 모든 장소는 기본적으로 PGS 솔버를 사용했으며, 기존 솔버로 되돌릴 수 있는 옵션도 제공되었습니다.
2018년 중반, 하이브리드 LDL-PGS 솔버를 도입하여 큰 질량 차이와 복잡한 메커니즘과 관련된 일부 안정성 문제를 해결했습니다. 이로 인해 기존 솔버는 더 이상 사용되지 않게 되었으며, 2019년에 완전히 비활성화되어 모든 장소가 자동으로 PGS로 마이그레이션되었습니다.
2019년에는 시뮬레이션을 연결된 시뮬레이션 부품 군으로 구성된 작업 단위로 분할하는 멀티스레딩 기술을 적용하여 성능을 더욱 향상시켰습니다. LDL과 관련된 성능 문제는 여전히 남아 있었으나, 2020년 초에 마침내 해결했습니다.
물리 엔진은 여전히 성능 향상을 위해 개선 및 최적화되고 있으며, 당분간 새로운 기능을 추가할 계획입니다.
물리 법칙 구현
물리 엔진의 주요 목적은 가상 환경에서 물체의 운동을 시뮬레이션하는 것입니다. 저희 물리 엔진에서는 강체이며, 서로 충돌하고 제약 조건을 갖는 물체들에 주목합니다.
물리 엔진은 충돌 감지와 해석이라는 두 단계로 구성됩니다. 충돌 감지는 강체와 관련된 기하학적 객체 간의 교차점을 찾아내어, 충돌 점, 법선 벡터, 침투 깊이와 같은 적절한 충돌 정보를 생성합니다. 그런 다음 해석기는 감지된 충돌과 사용자가 지정한 제약 조건의 영향을 받아 강체의 운동을 업데이트합니다.
운동은 에너지 보존 법칙이나 운동량 보존 법칙과 같은 물리 법칙을 솔버가 해석한 결과입니다. 하지만 이를 100% 정확하게 수행하는 것은 비용이 너무 많이 들기 때문에, 실시간으로 시뮬레이션하는 비결은 결과가 물리적으로 현실적일 경우 성능을 높이기 위해 근사치를 사용하는 것입니다. 운동의 기본 법칙이 합리적인 허용 오차 범위 내에서 유지된다면, 이러한 절충안은 컴퓨터 게임 시뮬레이션에 있어 전적으로 수용 가능합니다.
작은 단계로 나누기
물리 엔진의 핵심 개념은 시간 단계(time-stepping)를 사용하여 운동을 이산화하는 것입니다. 제약이 있는 강체와 제약이 없는 강체의 운동 방정식을 직접적이고 정확하게 미분적분하는 것은 매우 어렵습니다. 이산화 과정은 운동을 작은 시간 단위로 세분화하며, 이때 방정식을 단순화하고 선형화하여 근사적으로 풀 수 있게 합니다. 즉, 각 시간 단계마다 제약 관계에 관여하는 강체의 관련 부분들의 운동이 선형적으로 근사화됩니다.
선형화된 문제는 해결하기가 더 쉽지만, 회전 운동과 같은 비선형적 거동이 포함된 시뮬레이션에서는 드리프트가 발생합니다. 나중에 드리프트를 줄이고 시뮬레이션의 현실감을 높이는 완화 방법을 살펴보겠습니다.
해결
이 애니메이션은 PGS 솔버가 반복 과정의 각 단계에서 물체의 위치를 어떻게 변경하는지 보여줍니다. 목표는 각 단계에서 질량 중심을 유지하면서 볼-소켓 제약 조건을 준수하는 위치를 찾는 것입니다(이는 IK 드래거에서 사용하는 위치 기반 솔버의 한 유형입니다). 이 예제는 간단한 해를 구할 수 있지만, PGS의 원리를 잘 보여주는 사례입니다. 각 단계에서 솔버는 제약 조건 중 하나를 고정하고 다른 하나는 위반되도록 둡니다. 몇 번의 반복 후, 물체들은 올바른 위치에 매우 근접하게 됩니다. 이 방법의 특징은 일부 강체들이 최종 위치 주변에서 진동하는 것처럼 보인다는 점이며, 특히 더 무거운 물체와의 상호작용을 결합할 때 두드러집니다. 반복 횟수가 충분하지 않으면, 노란색 부분이 두 제약 조건 중 하나가 극심하게 위반되는, 육안으로 보아도 비정상적인 상태로 남을 수 있습니다. 이를 '높은 질량비 문제'라고 부르며, 이는 불안정성과 폭발을 유발하기 때문에 물리 엔진의 골칫거리였습니다. 반복 횟수를 너무 많이 하면 솔버가 너무 느려지고, 너무 적으면 불안정해집니다. 이 두 가지 사이의 균형을 맞추는 것은 고통스럽고 긴 과정이었습니다.
완화 전략
솔버의 부정확성은 주로 두 가지 원인에서 비롯됩니다: 시간 단계(time-stepping)와 반복 계산(iterative solving)입니다(부동소수점 드리프트도 있지만, 앞의 두 가지에 비하면 사소한 문제입니다). 이러한 부정확성은 시뮬레이션에 오류를 유발하여 올바른 경로에서 벗어나게 만듭니다. 속도 차이나 에너지 손실처럼 일부 편차는 용인될 수 있지만, 불안정성, 과도한 에너지 증가, 제약 조건의 이탈 등은 그렇지 않습니다.
따라서 솔버의 복잡성 상당 부분은 계산 오차의 영향을 최소화하기 위한 방법의 구현에서 비롯됩니다. 최종 구현에서는 기존의 전략과 새로운 완화 전략을 일부 함께 사용합니다:
- 웜 스타팅(Warm starting): 반복 솔버의 수렴 속도를 높이기 위해 이전 시간 단계의 해를 시작점으로 사용
- 사후 안정화(Post-stabilization): 제약 조건의 편차를 방지하기 위해 시스템을 제약 매니폴드로 다시 투영하는 과정
- 정규화: 제약 조건에 유연성을 추가하여 해가 존재하고 유일함을 보장
- 사전 조건화: 선형 하위 시스템에 대한 정확한 해를 사용하여 복잡한 메커니즘의 안정성을 향상시킵니다
전략 1, 2, 3은 상당히 전통적인 방법이지만, 3번 전략은 저희가 개선하고 완성했습니다. 또한 4번 전략이 전례가 없는 것은 아니지만, 실제 적용 사례는 본 적이 없습니다. 저희는 대규모 스파스 제약 행렬을 위한 독자적인 분해 방법과 이를 PGS와 결합하는 새로운 효율적인 방식을 사용합니다. 그 결과 구현된 방법은 순수 PGS에 비해 속도가 약간 느릴 뿐이지만, 등식 제약에서 비롯된 선형 시스템이 정확히 풀리도록 보장합니다. 결과적으로 등식 제약은 시간 이산화에서 비롯된 드리프트만 겪게 됩니다. 저희 방법에 대한 자세한 내용은 제 GDC 2020 발표 자료에 수록되어 있습니다. 현재 저희는 부등식 제약 및 충돌에 적용되는 직접법을 연구하고 있습니다.
더 자세한 정보
전통적으로 관절 기구에는 두 가지 수학적 모델이 존재합니다. 하나는 Featherstone이 주도한 축소 좌표법으로, 각 관절의 자유도를 매개변수화하는 방식이며, 다른 하나는 라그랑주 형식을 사용하는 전체 좌표법입니다.
저희는 두 번째 방식을 채택하고 있습니다. 이는 제약이 덜할 뿐만 아니라 수학적 처리와 구현이 훨씬 간단하기 때문입니다.
Roblox 엔진은 이전에 사용되던 페널티 기반 방법과 달리, 제약 조건의 동적 응답을 계산하기 위해 분석적 방법을 사용합니다. 분석적 방법은 Baraff(1989)에서 처음 소개되었으며, 여기서 이 방법은 등식 제약 조건과 비등식 제약 조건을 일관된 방식으로 모두 다루는 데 사용되었습니다. Baraff는 접촉 모델을 2차 계획법으로 공식화할 수 있음을 관찰했으며, 경험적 해법(우리 솔버에서 사용하는 방법은 아님)을 제시했습니다.
우리는 힘 기반 공식화 대신, Mirtich-Canny(1995)가 처음 도입하고 Stewart-Trinkle(1996)이 더욱 개선한 속도 공간에서의 충격량 기반 공식화를 사용합니다. 이 방법은 다양한 접촉 유형의 처리를 통합하며, 마찰이 있는 접촉에 대한 해의 존재를 보장합니다. 각 시간 단계에서, 제약 조건과 충돌은 제약 임펄스로 인한 속도의 순간적 변화를 적용함으로써 유지됩니다. 임펄스 기반 시뮬레이션이 왜 우수한지에 대한 훌륭한 설명은 Catto(2014)의 GDC 발표 자료에 포함되어 있습니다.
마찰이 없는 접촉은 Baraff(1994)에 기술된 대로 선형 보완 문제(LCP)를 사용하여 모델링됩니다. 마찰은 Projected Gauss-Seidel의 반복 과정과 교차하며 마찰 원뿔에 대한 비선형 투영으로 추가됩니다.
제약 조건에 위치 오차를 유발하는 수치적 드리프트는 Cline-Pai 2003에서 제안한 의사 속도를 이용한 사후 안정화 기법으로 해결됩니다. 이는 위치 공간에서 두 번째 LCP를 해결하여 시스템을 제약 매니폴드로 다시 투영하는 과정을 포함합니다.
LCP는 Catto(2005)에 의해 널리 알려진 PGS/임펄스 솔버(Catto 2009 참조)를 사용하여 해결됩니다. 이 방법은 반복적이며, 각 개별 제약 조건을 순차적으로 고려하여 독립적으로 해결합니다. 많은 반복을 거치고 이상적인 조건에서 시스템은 전역 해로 수렴합니다.
또한, 등식 제약 조건의 높은 질량비 문제는 등식 제약 조건 행렬의 스파스 LDL 분해를 사용하여 PGS를 사전 조건화함으로써 해결됩니다. 제약 조건 행렬의 밀집 부분 행렬은 우리가 '바디 분할(Body Splitting)'이라고 부르는 방법을 사용하여 스파스화됩니다. 이는 Baraff 1996에서 사용된 LDL 분해와 유사하지만, 더 일반적인 기계 시스템을 허용하며 제약 공간에서 시스템을 해결합니다. 더 자세한 내용은 제 GDC 2020 발표 자료를 참고하시기 바랍니다.
본 솔버의 아키텍처는 Guendelman-Bridson-Fedkiw의 아이디어를 따르며, 여기서 속도 및 위치 스텝핑은 제약 조건 해결 단계와 분리되어 있습니다. 시간 순서는 다음과 같습니다:
- 속도 계산
- 속도 공간 및 위치 공간에서의 제약 조건 해결
- 위치 전진
이 방식은 유효한 속도만 통합하고, 외부 힘 적용 시 지연 시간을 제한하면서도 수치적 드리프트로 인한 미미한 제약 조건 위반은 허용한다는 장점이 있습니다.
강체 시뮬레이션에 대한 훌륭한 참고 자료로는 최근 무료로 공개된 Erleben 2005 저서가 있습니다. 물리 기반 애니메이션에 관한 온라인 강의, 물리 엔진 구축에 대한 Nilson Souto의 블로그, 현대적인 솔버 기법에 대한 Erin Catto의 훌륭한 GDC 발표 자료, 그리고 질문을 올리기 좋은 장소인 Bullet Physics Forum이나 GameDev와 같은 포럼을 찾아보실 수 있습니다.
결론
게임 물리 시뮬레이션 분야는 흥미롭고 도전적인 많은 문제들을 제시합니다. 여기서 우리는 흥미로운 수학과 물리학을 깊이 있게 배우고, 현대적인 최적화 기법을 활용할 기회를 얻을 수 있습니다. 이는 수학, 물리학, 소프트웨어 공학이 긴밀하게 결합된 게임 개발의 한 분야입니다.
Roblox에 훌륭한 강체 물리 엔진이 있더라도, 개선하고 최적화할 수 있는 부분은 여전히 존재합니다. 또한, 저희는 파쇄, 변형, 소프트바디, 천, 공기역학, 물 시뮬레이션과 같은 흥미로운 신규 프로젝트들을 진행 중입니다.
로블록스(Roblox Corporation)나 이 블로그는 어떠한 회사나 서비스도 추천하거나 지지하지 않습니다. 또한, 이 블로그에 포함된 정보의 정확성, 신뢰성 또는 완전성에 대해 어떠한 보증이나 약속도 하지 않습니다.
이 블로그 게시물은 원래 로블록스 테크 블로그에 게시되었습니다.
