“축 하나로도 진단, 열여덟 축이면 해부”―2D SAT과 3D SAT가 여는 충돌 검출의 세계

[한국정보기술신문] 게임·로봇·CAD 엔진이 물체 간 충돌 여부를 판별할 때 가장 널리 쓰는 기하 알고리즘이 ‘Separating Axis Theorem’, 줄여서 SAT다.

정리는 간단하다. 두 볼록 물체가 실제로 겹치지 않았다면, 두 물체의 그림자가 겹치지 않는 어느 한 직선—‘분리축’—이 반드시 존재한다는 명제다.

평면(2D)과 공간(3D)의 SAT는 원리는 같지만, 필요한 분리축 후보 수와 계산 복잡도가 크게 다르다.

2D SAT는 HTML5·모바일 게임의 다각형 충돌 처리에, 3D SAT는 실시간 물리·로봇 매니퓰레이터·가상현실 모델 해석에 쓰이며 ‘엔진의 안전벨트’로 불린다.

1970년대 이론이었지만 OBBTree·BVH 같은 구조와 결합되며 1990년대 후반 산업 표준이 됐고, 2020년대 이르러서는 GPU 병렬화로 초당 수백만 쿼리를 소화한다.

Helly 정리에서 OBBTree까지

SAT의 뿌리는 1920년대 H. Helly가 증명한 ‘Helly 정리’—볼록 집합이 교차하지 않으면 분리 초평면이 존재한다—로 거슬러 올라간다.

1970년대 초창기 2D 게임 개발자는 AABB(축 정렬 박스)로 충돌을 점검했지만, 물체가 회전하자 AABB 방식의 오검이 폭증했다.

1996년 UNC 챈플힐 S. Gottschalk·M. Lin·D. Manocha가 발표한 OBBTree 논문이 “3D SAT+계층 구조”를 첫 구현해 업계 판도를 바꿨으며, 1999년 D. Eberly는 ‘Method of Separating Axes’ 기술서를 공개해 3D SAT 수식·코드를 대중화했다.

2005년 Christer Ericson의 『Real-Time Collision Detection』은 SAT 구현 노하우를 집대성해 “충돌 검출 바이블”로 자리 잡았다.

이후 dyn4j·Box2D·Bullet·sat.js 같은 오픈소스가 SAT 엔진을 표준 라이브러리로 제공, 교육·인디 생태계까지 확산했다.

볼록 다각형에 직교 축을 던지다

2D SAT는 두 볼록 다각형 A, B의 모든 변 법선을 후보 축으로 삼아 투영 구간이 겹치는지 검사한다.

투영 값은 내적(dot) 한 번으로 얻고, 구간이 비는 축이 발견되면 즉시 “충돌 없음”을 반환해 O(n+m) 복잡도를 달성한다.

원·다각형 혼합 충돌은 원 중심에서 각 변에 내린 법선을 추가 후보 축으로 삼아 동일 루틴에 통합한다.

오목 다각형은 볼록 부피로 분할한 뒤 파편 단위로 SAT를 호출해 문제를 해결한다.

2D SAT는 “모양·꼭짓점 수 무관, 한 가지 코드”라는 유지보수 이점 때문에 모바일 게임이 즐겨 채택한다.

단점은 고속 물체가 한 프레임 안에 축을 통과하면 스루 현상이 발생해, 시간 연속 SAT(Continuous SAT)를 추가 구현해야 한다는 점이다.

15개의 축, 그리고 그 이상

3D 상자 충돌의 기본 후보 축은 ‘A의 지역축 3개 + B의 지역축 3개 + 두 세트 교차 외적 9개’ 총 15개다.

다면체로 가면 각 면의 법선과 에지 교차 축까지 포함돼 수십 개 후보가 생기지만, CPU SIMD 최적화로 10 µs 이하 성능이 가능하다.

3D SAT는 투영 구간이 겹치는 축도 기록해 ‘최소 침투벡터(MTV)’를 계산, 물리 엔진이 반발·마찰을 산출할 수 있게 돕는다.

복합 메시에는 SAT가 GJK와 함께 쓰인다. 엔진은 GJK로 “충돌 여부”를 빨리 파악한 뒤, 세부 MTV를 SAT로 구해 안정성을 높인다.

Ericson은 3D SAT의 부동소수점 오차를 줄이려면 축 길이를 1로 정규화하고 ε=1e-6 임계치를 도입하라고 조언한다.

고해상도 물체 충돌은 BVH나 OBBTree로 후보 면·에지를 줄인 뒤 잔여 파편만 SAT에 넘기는 ‘좁은 단계’ 전략을 쓴다.

Fail-Fast·벡터화·BVH

SAT 루틴은 첫 구간 불일치 축을 찾자마자 함수를 빠져나오는 Fail-Fast 접근으로 평균 계산량을 절반 가까이 줄인다.

2D 게임 엔진은 ‘AABB 브로드페이즈 → SAT 내로다운’ 2단계를 쓴다. 대부분 객체가 AABB 단계에서 탈락해 SAT 호출 자체가 희소해진다.

3D 엔진에서 SAT는 BVH 노드에 캐싱돼 상위 노드 분리 여부가 확인되면 하위 검사를 스킵, 지연 시간을 크게 줄인다.

2022년 SIGGRAPH 논문은 SAT 내적·외적을 GPU SIMD로 벡터화해 RTX 4090에서 초당 3.2 백만 쿼리를 달성했다고 보고했다.

벡터화 효과를 극대화하려면 축·투영 배열을 SoA(Structure of Arrays)로 재배치해 캐시 미스를 15 % 줄일 수 있다.

물리 엔진은 “축 재사용” 캐시를 두어 프레임 간 변위가 작을 때 이전 축 검사를 반복 활용해 CPU 사이클을 절감한다.

SAT가 움직임을 지배한다

유니티·언리얼 2D 물리 모듈은 Box2D 포크 위에 SAT 정밀 검사를 얹어 캐릭터·탄환 충돌을 처리한다.

인디 게임 Celeste는 오목 지형을 볼록 파편으로 분할해 SAT를 적용, “벽 타기” 모션의 오인식 문제를 해결했다.

AAA 타이틀 Horizon Forbidden West는 3D SAT+GJK 조합으로 거대 기계 생명체와 환경 메시의 다중 접촉점을 매 프레임 계산한다.

e스포츠 네트워크 게임은 SAT 루틴을 디터미니즘 프레임워크에 묶어 동기화 오차를 방지, “튕김 없는” 플레이를 구현한다.

VR·AR 엔진은 90 FPS 목표를 위해 SAT를 GPU Compute 쉐이더로 오프로드해 지연을 2 ms 이하로 유지한다.

교육용 HTML5 라이브러리 ‘sat.js’는 학생이 20줄 코드로 다각형 충돌 시각화를 체험하게 해 컴퓨터 그래픽스 입문 교재로 쓰인다.

산업에서 튀어나온 분리축

2024년 IEEE RA-Letters 논문은 3D SAT 기반 그리퍼 경로 최적화로 공장 로봇 충돌 회피 속도를 40 % 높였다고 보고했다.

자율주행 스태커 크레인 연구는 GPU SAT로 500 Hz 예측 루프를 달성, 컨테이너 야드 배치 효율을 8 % 향상시켰다.

CAD/BIM 소프트웨어는 구조물·설비 교차 충돌을 3D SAT로 자동 검증, 작업 시간을 70 % 단축했다는 튜토리얼 레포트가 공개됐다.

의료 로봇 카테터 경로 탐색에 3D SAT를 적용, 혈관 관통 위험 경로를 사전 제거해 수술 안전도를 높인 임상 파일럿이 학회에 실렸다.

3D 프린팅 소프트웨어는 적층 경로와 지지 구조 간 간섭을 SAT로 미리 판정, 실패율을 12 % 낮췄다.

전문가들은 “SAT는 단순 기하 루틴에서 ‘스마트 제조 안전 모듈’로 격상됐다”고 평가한다.

오차·스루·데이터 폭발

부동소수점 오차는 평행 축에서 외적 |v×w|이 ε보다 작아 분리축이 사라지는 ‘축 붕괴’ 문제를 낳는다. Ericson은 ε=1e-6 회피 기법을 제시했다.

초고속 탄환·차량은 한 프레임에 축을 통과해 버그를 일으키므로, 시간 연속 SAT(CSAT) 혹은 CCD(Continuous Collision Detection)가 필요하다.

복잡 메시의 면·에지 수가 늘면 후보 축이 폭증, 메모리와 파이프라인 병목이 생긴다. BVH와 지역성 최적화가 필수다.

다층 캐릭터 스킨·의상 시뮬레이션은 ‘얇은 천’이 속을 뚫는 클리핑 현상을 완전히 막지 못해, 엔진들은 SAT 후 처리 보정 알고리즘을 추가한다.

SAT는 볼록성 가정을 전제로 한다. 비볼록·변형 메쉬 지원 연구가 활발하지만 실시간 구현은 아직 실험 단계다.

머신러닝으로 충돌 후보를 예측해 SAT 호출 빈도를 줄이는 하이브리드 기법이 2023년 SIGGRAPH Asia에서 제안됐지만, 안정성 검증이 과제다.

SAT·GJK·EPA, 언제 쓸까

GJK는 볼록 다체 최소 거리를 구하지만 초기 Simplex 의존성이 커 수행 시간이 변동적이다. EPA는 침투 깊이를 정확히 계산하지만 SAT보다 연산량이 많아 실시간 게임에 단독 사용되긴 어렵다.

실측 벤치마크에 따르면 20꼭짓점 이하 객체는 SAT가 GJK보다 15 % 빠르지만, 꼭짓점이 100개를 넘으면 GJK가 우위로 역전된다.

엔진들은 ‘AABB → SAT/GJK → EPA’ 다단계를 배치해 “빠른 거절·안정적 반응” 균형을 노린다.

SAT의 강점은 MTV를 쉽게 얻어 반발·마찰 벡터 계산이 편하고, 코드 근거가 직관적이라 디버깅이 용이하다는 점이다.

결정적으로 SAT는 2D·3D·GPU·FPGA 어느 환경에서도 일관된 수학으로 구현 가능해 교육·산업 양쪽에서 ‘첫 선택’이 된다.

GPU, 양자, 그리고 ‘비볼록 SAT’

2024년 SIGGRAPH 논문 ‘SAT-RT’는 레이 트레이싱 가속기를 활용한 축 검사로 초당 1억 테스트를 시연, 대규모 군집 시뮬레이션 가능성을 보여줬다.

양자 연산 연구팀은 분리축 후보를 비트맵으로 인코딩해 Grover 탐색을 도입, O(√n) 거리로 단축하는 프로토타입을 발표했다.

ROS 2는 2024년 ‘L-티르소’ 릴리스에 GPU SAT-BVH 플러그인을 통합, 드론·AMR(자율 이동 로봇) 개발 파이프라인을 자동화했다.

학계는 “변형·비볼록 메쉬에 대한 실시간 SAT”를 목표로 위상 변환 검출, 동적 축 업데이트 연구를 진행 중이다.

메타버스·혼합현실·디지털트윈이 폭발하면 충돌 검출 수요는 더욱 증가, ‘얇고 복잡한’ 객체에서 SAT 개선이 핵심 과제가 될 전망이다.

요컨대 SAT는 단순한 기하 정리에서 출발했지만, 2025년 현재도 “모든 실시간 충돌 시스템의 중심축”으로 진화 중이다. 앞으로도 벡터화·AI·양자 가속 등과 만나 안전한 가상·물리 세계를 떠받칠 가능성이 크다.

한국정보기술신문 실감형콘텐츠분과 박성빈 기자 news@kitpa.org