# SIMD로 충돌 감지 가속하기

> Clean Markdown view of GeekNews topic #31717. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=31717](https://news.hada.io/topic?id=31717)
- GeekNews Markdown: [https://news.hada.io/topic/31717.md](https://news.hada.io/topic/31717.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2026-07-23T10:01:33+09:00
- Updated: 2026-07-23T10:01:33+09:00
- Original source: [box2d.org](https://box2d.org/posts/2026/07/simd-for-collision/)
- Points: 1
- Comments: 1

## Topic Body

- 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](https://github.com/Pierre-Terdiman/PEEL_PhysX_Edition)에서 이식한 Convex Pile 벤치마크는 각각 32개 점을 가진 볼록 껍질 **5,120개**를 떨어뜨림
  - Box는 정점 8개, 면 6개, 모서리 12개로 구성됨
  - Boulder는 정점 32개, 면 59개, 모서리 89개로 구성됨
  - Box3D는 Box도 껍질로 처리하며, Box 중심 벤치마크에서는 일반적으로 내로우 페이즈가 주요 비용이 아니었음
- 충돌 감지에는 [분리축 정리(SAT)](https://en.wikipedia.org/wiki/Hyperplane_separation_theorem)를 사용함
  - SAT로 물체를 분리할 최적 특징과 필요한 이동 거리를 구하고, 접촉 법선과 접촉점도 계산함
  - 다른 물리 엔진은 [GJK](https://en.wikipedia.org/wiki/Gilbert%E2%80%93Johnson%E2%80%93Keerthi_distance_algorithm)와 겹침 처리용 [EPA](https://graphics.stanford.edu/courses/cs468-01-fall/Papers/van-den-bergen.pdf)를 조합하기도 함
- 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](https://en.wikipedia.org/wiki/Gauss_map)으로 모서리 검사를 줄일 수 있지만, 모서리-모서리 검사가 전체 시뮬레이션을 지배할 수 있음
  - 관련 기법은 [Improvements to the Separating Axis Test](https://cairnc.github.io/posts/improvements-to-the-separating-axis/)에서 확인할 수 있음
- SIMD가 효율적으로 동작하려면 데이터를 **배열 구조(SoA)** 로 준비해야 하므로, 모서리 12개짜리 껍질에서는 설정 비용 대비 이득이 크지 않음
  - 모서리 89개씩을 비교하면 `TestCrossProduct`가 7,921회 호출됨
  - 와이드 SIMD 구현은 hullA의 모서리 하나를 hullB의 모서리 4개가 담긴 `EdgeWide`와 동시에 검사함

### 벤치마크 결과와 적용 범위
- 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 모서리 검사의 효과가 거의 없음
  - 복잡한 껍질을 사용하는 **파괴 시나리오** 등에서는 충분한 성능 이득을 제공함

## Comments



### Comment 62251

- Author: neo
- Created: 2026-07-23T10:01:34+09:00
- Points: 1

###### [Lobste.rs 의견들](https://lobste.rs/s/gkcjic/simd_for_collision) 
- **SIMD**는 simdutf나 simdjson처럼 복잡한 프로젝트 때문에 어렵게 보이지만, 평범한 루프를 한 번에 N바이트씩 처리하는 기본 패턴은 의외로 단순함  
  상수를 각 레인에 복제하고 벡터 누산기를 초기화한 뒤, 벡터 폭만큼 입력을 순회하며 비교·연산하고, 결과를 축약하거나 저장한 다음 남은 원소를 기존 스칼라 루프로 처리하면 됨  
  실제 프로젝트에서 `0xF` 이하의 값을 찾는 조기 종료 루프를 이 방식으로 바꿔 하드웨어에 따라 **2~16배 처리량 향상**을 얻었음  
  컴파일러가 단순하고 규칙적인 산술 루프는 자동 벡터화할 수 있지만, 조기 종료와 비교 마스크, 축약, 첫 실패 레인 탐색이 결합된 변환은 안정적으로 찾아내지 못함. 자세한 내용은 https://llvm.org/docs/Vectorizers.html 에 있음  
  자동 벡터화는 수십 년간 연구됐는데도 실제 컴파일러가 여전히 기회를 자주 놓침: https://arxiv.org/abs/2406.04693  
  기본 패턴에 익숙해지면 스칼라 루프만큼 자연스럽게 작성할 수 있으므로 더 많은 개발자가 배우고 언어도 이를 위한 도구를 제공해야 함. 확장한 글은 https://mitchellh.com/writing/everyone-should-know-simd 에 있음
  - SIMD를 제대로 활용하려면 **구조체 배열(AoS)** 보다 **배열 구조체(SoA)** 가 필요한지 궁금함. AoS는 추가 복사와 마스킹 때문에 이점이 사라질 듯하며, CPU마다 지원 명령어가 다른 상황에서 단일 SIMD 인터페이스를 어떻게 구성하는지도 의문임  
    런타임이 대상 아키텍처의 모든 명령어별 구현과 SIMD 미지원 CPU용 대체 구현을 함께 제공해야 하는지, 아니면 특정 명령어 집합만 대상으로 삼는지 알고 싶음
  - 관련 연구 프로젝트인 [Halide](https://halide-lang.org/)를 특히 좋아하며, 더 많은 프로젝트에서 활용되기를 바람
  - 최근 **자동 벡터화 연구**가 실제 컴파일러에 얼마나 배포됐는지 궁금함  
    예전에는 연구용 개념 증명에 그치거나 일부 Fortran 컴파일러에만 들어가고, 주류 컴파일러에는 구현되지 않는 경우가 많았던 것으로 기억함