충돌을 위한 SIMD

이전 글 SIMD Matters에서 저는 접촉 솔버를 더 빠르게 만들기 위해 그래프 컬러링으로 얻은 큰 이점을 설명했습니다. 같은 접근법이 Box3D에도 존재합니다. 저는 이 접근법을 “와이드 SIMD”라고 부르기를 좋아합니다. 핵심 아이디어는 여러 작업 단위를 동시에 처리하는 것입니다. 접촉 솔버에서는 이것이 네 개의 접촉점을 동시에 푸는 것을 의미합니다.

이것은 3-벡터(xyz)를 SIMD 레지스터에 넣고 표준 벡터 수학을 SIMD 인트린식으로 표현하는 “내로우 SIMD”와는 다릅니다. 내로우 SIMD도 유용할 수 있지만, 이득은 그렇게 분명하지 않습니다.

3차원에서는 2차원에는 없는 와이드 SIMD 활용 기회가 있습니다. PEEL에서 포팅한 볼록 더미 벤치마크를 생각해 봅시다. 이 벤치마크는 각각 32개 점을 가진 볼록 헐 5120개를 떨어뜨립니다.

Box3D는 박스를 헐로 취급하며 많은 벤치마크가 박스를 사용합니다. 박스에서의 성능은 좋았고, 일반적으로 비용의 대부분은 내로우 페이즈에 있지 않습니다. 하지만 32점 헐은 전혀 다른 짐승입니다. 이것을 “바위”라고 부르겠습니다. 아래 표는 박스와 바위를 비교한 헐 세부 사항을 보여줍니다.

Box3D는 충돌 검출에 Separating Axis Test를 사용합니다. 이것은 SAT로 줄여 부릅니다. SAT를 사용하면 형상들을 서로 밀어내는 데 사용할 최적의 특징들을 찾을 수 있고, 겹침을 제거하기 위해 정확히 얼마나 멀리 밀어야 하는지도 알 수 있습니다. 더 나아가 저는 이 결과를 사용해 접촉 법선과 접촉점을 계산합니다.

다른 물리 엔진들은 대신 거리 알고리즘 GJK를 사용하고, 겹침이 있을 때는 Expanding Polytope Algorithm 같은 보조 기법을 사용할 수 있습니다. 이것은 EPA라고도 알려져 있습니다.

저는 볼록 헐 충돌에 대해 SAT의 열렬한 지지자입니다. 왜냐하면 충돌 마진이 필요 없기 때문입니다. 형상들은 서로 바로 맞닿아 정지할 수 있습니다. GJK와 EPA 조합은 보통 더 빠른 GJK 영역 안에 머무르기 위해 형상들을 약간 떨어뜨려 두려 합니다. 이것은 시각적인 틈을 만들 수 있습니다. 또한 EPA는 수치적으로 취약할 수 있어서, EPA가 실패할 경우 물리 엔진은 종종 보조 수단이 필요합니다. 즉, 보조 수단을 위한 또 다른 보조 수단입니다. EPA는 본질적으로 볼록 헐을 계산하는 알고리즘이며, 입력 데이터는 납작한 얇은 조각일 수 있습니다. 이것은 볼록 헐 계산에 어려운 상황입니다. 그래서 두 번째 보조 수단이 필요합니다.

안타깝게도 3차원에서 SAT는 이차 복잡도를 가집니다. 두 헐 A와 B가 있으면, 충돌 알고리즘은 헐 A의 면들을 헐 B의 정점들에 대해 검사하고, 헐 B의 면들을 헐 A의 정점들에 대해 검사하며, 헐 A의 에지들을 헐 B의 에지들에 대해 검사해야 합니다. 최악의 경우에는 모든 조합을 평가해야 합니다.

에지-에지 조합의 수는 이차적으로 증가합니다. Gauss Map을 사용해 에지 검사를 빠르게 하는 몇 가지 기법이 있습니다. 자세한 내용은 Improvements to the Separating Axis Test를 참고하세요. 그럼에도 불구하고 에지-에지 검사는 전체 시뮬레이션을 쉽게 지배할 수 있습니다.

그렇다면 이 에지-에지 코드는 어떻게 생겼을까요? 기본 수준에서는 대략 이렇게 보입니다:

for (Edge edgeA : hullA.edges)
{
    for (Edge edgeB : hullB.edges)
    {
        TestCrossProduct(edgeA, edgeB);
    }
}

각 헐에 에지가 12개뿐이라면, SIMD는 약간의 준비 작업이 필요하기 때문에 이것에 SIMD를 적용해도 큰 이득은 없습니다. SIMD가 잘 작동하려면 데이터가 structure of arrays 형식(SoA)이어야 합니다.

하지만 각 헐에 에지가 89개라면 이야기가 극적으로 달라집니다. TestCrossProduct 호출이 7921번 있습니다. 와이드 SIMD를 사용하면 헐A의 에지 하나를 헐B의 에지 네 개와 동시에 검사할 수 있습니다. 대략 이런 모습입니다:

for (Edge edgeA : hullA.edges)
{
    for (EdgeWide edgeWideB : hullB.edgesWide)
    {
        TestCrossProductWide(edgeA, edgeWideB);
    }
}

이 코드 조각에는 숨겨진 세부 사항이 많으며, 궁금하다면 Box3D 코드를 살펴볼 수 있습니다. 하지만 여기서 제가 답하려는 질문은 이것입니다. 충돌 검출에서 SIMD를 신경 써야 할까요? 네, 결과가 있습니다! 아래는 500 스텝 실행의 총 밀리초를 기록한 볼록 더미 벤치마크 결과입니다. AMD 7950x에서 CPU를 4.42GHz로 고정한 상태로 1개에서 8개 스레드까지 테스트했습니다. 결과는 4회 실행 중 최고값입니다.

SSE2는 스칼라보다 두 배 이상 빠릅니다! 이 시간 측정은 에지-에지 검사만이 아니라 전체 시뮬레이션에 대한 것임을 기억하세요. 또한 스칼라 열은 접촉 솔버도 스칼라 모드로 실행된다는 뜻입니다. 즉, 이것이 시뮬레이션의 전체 그림입니다.

Box3D는 SSE2 인트린식만 구현합니다. Box2D에서는 AVX2 인트린식도 가지고 있지만, 놀랍게도 AVX2를 지원하지 않는 CPU를 가진 사용자가 꽤 많았습니다. 그럼에도 불구하고 Box3D에서 AVX2 아키텍처만 활성화해도 AVX2-Lite 열이 보여주듯 좋은 이득이 있습니다. 공짜 성능 향상은 언제나 반갑습니다. 앞으로는 한 번에 8개 에지를 검사하는 진짜 AVX2 구현도 시도해 볼 수 있습니다.

이 벤치마크는 에지 89개를 가진 32점 헐을 나타냅니다. 점 개수가 더 늘어나면 SAT는 분명 압도당할 것처럼 보입니다. 다행히 Box3D에는 에지 128개라는 엄격한 제한이 있습니다. 이 제한은 이미 존재했고, 헐 저장소를 작게 유지하기 위한 이유와 관련이 있습니다(8비트 인덱스와 에지당 두 개의 하프 에지). 다소 놀랍게도 복잡한 헐을 메시에 변환하면 이차 증가 문제를 해결할 수 있지만, 그러면 그 형상은 동적 바디에 덜 적합해집니다.

SIMD 에지 검사가 박스-박스에도 의미 있는 변화를 주었는지 궁금할 수 있습니다. 안타깝게도 거의 효과가 없습니다. 이 최적화는 복잡한 헐에만 도움이 되는 것으로 보입니다. 그런 헐은 파괴 같은 여러 시나리오에서 나타날 수 있습니다. 따라서 이것은 Box3D에 추가할 가치가 있습니다.

마지막으로, 여기 비디오 비교와 프레임 시간의 나란한 비교가 있습니다.

Video 3