SAT 알고리즘 기반 Convex Polygon 충돌 감지 및 물리 엔진 구현

Building a 2D Physics Engine From Scratch: SAT Collision Detection in C++ and SDL2

whomi9282026년 7월 1일5분intermediate

AI 요약

Context

단순 Bounding Circle 방식의 한계로 인해 다각형 형태의 정교한 충돌 감지가 불가능한 상황. 외부 라이브러리 없이 C++와 SDL2를 활용해 임의의 볼록 다각형(Convex Polygon) 간 상호작용을 처리하는 물리 엔진 설계 필요성 대두.

Separating Axis Theorem(SAT) 적용을 통한 임의의 볼록 다각형 간 충돌 여부 판별
모든 모서리의 법선 벡터를 투영 축으로 설정하여 겹침이 없는 축(Gap)을 찾는 조기 종료(Early Exit) 로직 구현
최소 중첩 축(Minimum Translation Vector)을 기반으로 충돌 깊이와 법선 벡터를 산출하여 물리적 반응의 기초 데이터 확보
Positional Correction과 Velocity Resolution을 분리한 2-Pass 구조 설계를 통해 충돌 시 발생하는 Jittering 및 Sticky 현상 제거
질량 기반 가중치(Mass-weighted)를 적용한 위치 보정 로직으로 객체 간 질량 차이에 따른 물리적 현실성 확보
법선 벡터의 방향성을 객체 간 거리 벡터와 대조하여 충돌체 간 반발 방향을 정밀하게 제어하는 Normal Direction Check 도입

실천 포인트

1. SAT 구현 시 모든 축을 검사하기 전 Gap 발견 즉시 반환하는 Early Exit 최적화 적용 여부 확인

2. 위치 보정과 속도 해결을 단일 단계로 처리하지 않고 분리하여 물리적 불안정성(Jitter) 제거

3. 단순 50:50 위치 보정이 아닌 질량 비율에 따른 가중치 적용 검토

4. O(n²) 복잡도를 가진 Brute-force 검사 단계에서 Spatial Partitioning 도입을 통한 성능 확장성 확보

태그