- Box3D는 복잡한 3D 볼록 껍질 충돌 검사에 와이드 SIMD를 적용해, 32개 점과 89개 모서리를 가진 물체 5,120개의 전체 시뮬레이션 시간을 절반 이하로 줄임
- 3D 분리축 정리(SAT) 는 두 껍질의 면-정점과 모서리-모서리 조합을 검사하며, Boulder-Boulder에서는 모서리 조합이 7,921개에 달해 이중 루프 비용이 시뮬레이션을 지배할 수 있음
- hullB의 모서리 4개를 SoA 형식으로 묶어 hullA의 모서리 하나와 동시에 검사하자, 1스레드·500스텝 실행 시간이 Scalar 40,706ms에서 SSE2 17,337ms, AVX2-Lite 15,762ms로 감소함
- 8스레드에서도 Scalar 5,292ms, SSE2 2,410ms, AVX2-Lite 2,277ms를 기록했으며, 이는 모서리 검사와 접촉 솔버를 모두 포함한 전체 시뮬레이션 측정치임
- 모서리가 12개뿐인 Box-Box 충돌은 설정 비용 때문에 효과가 거의 없지만, 파괴 효과 등에 쓰이는 복잡한 껍질에는 유용하며 향후 AVX2로 모서리 8개를 동시에 검사할 여지도 있음
SAT의 계산 비용과 SIMD 적용 방식
- Box3D의 와이드 SIMD는 xyz 벡터 하나를 SIMD 레지스터에 넣는 내로우 SIMD와 달리 여러 작업 단위를 동시에 처리함
- 접촉 솔버에서는 접촉점 4개를 한꺼번에 해결함
- 내로우 SIMD도 유용할 수 있지만 성능 향상은 와이드 SIMD만큼 분명하지 않음
- PEEL에서 이식한 Convex Pile 벤치마크는 각각 32개 점을 가진 볼록 껍질 5,120개를 떨어뜨림
- Box는 정점 8개, 면 6개, 모서리 12개로 구성됨
- Boulder는 정점 32개, 면 59개, 모서리 89개로 구성됨
- Box3D는 Box도 껍질로 처리하며, Box 중심 벤치마크에서는 일반적으로 내로우 페이즈가 주요 비용이 아니었음
- 충돌 감지에는 분리축 정리(SAT)를 사용함
- SAT는 충돌 여유 공간이 필요 없어 물체를 서로 직접 맞닿게 배치할 수 있음
- GJK와 EPA 조합은 더 빠른 GJK 영역을 유지하기 위해 물체를 조금 떨어뜨리는 경우가 있어 시각적 틈이 생길 수 있음
- EPA는 수치적으로 취약할 수 있고, 평평하고 얇은 입력으로 볼록 껍질을 계산해야 하므로 실패에 대비한 두 번째 대체 경로가 필요할 때도 있음
- 3D SAT는 두 껍질 A와 B에 대해 A의 면-B의 정점, B의 면-A의 정점, A의 모서리-B의 모서리를 검사하며 이차 복잡도를 보임
- Box-Box는 면-정점 6개, 정점-면 6개, 모서리-모서리 144개 조합임
- Boulder-Boulder는 각각 59개, 59개, 7,921개 조합임
- Gauss Map으로 모서리 검사를 줄일 수 있지만, 모서리-모서리 검사가 전체 시뮬레이션을 지배할 수 있음
- 관련 기법은 Improvements to the Separating Axis Test에서 확인할 수 있음
- SIMD가 효율적으로 동작하려면 데이터를 배열 구조(SoA) 로 준비해야 하므로, 모서리 12개짜리 껍질에서는 설정 비용 대비 이득이 크지 않음
- 모서리 89개씩을 비교하면
TestCrossProduct가 7,921회 호출됨 - 와이드 SIMD 구현은 hullA의 모서리 하나를 hullB의 모서리 4개가 담긴
EdgeWide와 동시에 검사함
- 모서리 89개씩을 비교하면
벤치마크 결과와 적용 범위
- AMD 7950X를 4.42GHz로 고정하고 1~8개 스레드에서 500스텝을 실행했으며, 각 수치는 4회 실행 중 최고 결과임
| 스레드 | Scalar | SSE2 | AVX2-Lite |
|---|---|---|---|
| 1 | 40,706ms | 17,337ms | 15,762ms |
| 2 | 20,799ms | 8,857ms | 8,131ms |
| 3 | 13,789ms | 5,946ms | 5,471ms |
| 4 | 10,324ms | 4,509ms | 4,084ms |
| 5 | 8,359ms | 3,675ms | 3,361ms |
| 6 | 6,958ms | 3,106ms | 2,843ms |
| 7 | 6,006ms | 2,697ms | 2,477ms |
| 8 | 5,292ms | 2,410ms | 2,277ms |
- SSE2는 Scalar보다 2배 이상 빠르며, 측정값에는 모서리-모서리 검사뿐 아니라 전체 시뮬레이션이 포함됨
- Scalar 열에서는 접촉 솔버도 Scalar 모드로 실행됨
- Box3D가 직접 구현한 SIMD 내장 함수는 SSE2뿐이지만, AVX2 아키텍처 활성화만으로도 AVX2-Lite의 추가 성능 향상을 얻음
- Box2D에는 AVX2 내장 함수도 있지만, AVX2를 지원하지 않는 CPU를 쓰는 사용자가 예상보다 많았음
- 향후 실제 AVX2 구현으로 모서리 8개를 동시에 검사할 수 있음
- Box3D는 저장 공간을 작게 유지하기 위해 껍질당 모서리를 최대 128개로 제한함
- 8비트 인덱스와 모서리당 두 개의 하프 에지를 사용하는 저장 방식에서 비롯된 제한임
- 복잡한 껍질을 메시로 변환하면 이차 증가 문제를 해결할 수 있지만 동적 물체에는 덜 적합해짐
- Box-Box 충돌에서는 SIMD 모서리 검사의 효과가 거의 없음
- 복잡한 껍질을 사용하는 파괴 시나리오 등에서는 충분한 성능 이득을 제공함