3D Physics Engine

English

사용자 정의 3D 물리 엔진 (Custom 3D Physics Engine)

1. 프로젝트 개요

• 본 프로젝트는 Win32 API와 DirectX 12를 사용하여 C++로 구현된 종합적인 3D 물리 엔진 개발 사례를 보여줍니다.
• 주요 목표는 상용 미들웨어를 사용하지 않고 물리 시뮬레이션을 기초부터 설계함으로써, 현대 게임 개발에서 흔히 사용되는 강체 역학(Rigid Body Dynamics), 충돌 탐지 파이프라인 및 제약 조건 해소(Constraint Resolution) 전략에 대한 깊은 이해를 얻는 것이었습니다.
• 본 엔진은 견고한 하이브리드 충돌 해소(Hybrid Collision Resolution) 시스템, 최적화된 스윕 앤 프룬(Sweep and Prune, SAP) 광역 단계(Broad-phase), 그리고 복잡한 물리적 상호작용을 검증하기 위해 설계된 강력한 시각적 디버깅 도구(Visual Debugging Suite)를 특징으로 합니다.

핵심 기술 스택

• 언어: C++ (현대적인 C++17 표준)
• 그래픽/시스템: DirectX 12, Win32 API
• 주요 알고리즘: 스윕 앤 프룬(SAP), GJK, EPA, 순차적 임펄스 해결기(Sequential Impulse Solver), 연속 충돌 탐지(Continuous Collision Detection, CCD).

2. 아키텍처 및 파이프라인

• 시뮬레이션은 성능과 정확성의 균형을 맞추기 위해 설계된 다단계 파이프라인을 실행합니다.

1. 적분 (Integration)

• 중력, 외부 임펄스 및 사용자 개입을 포함하여 누적된 힘을 바탕으로 선속도와 각속도, 그리고 위치를 업데이트합니다.

2. 광역 단계 (Broad Phase)

• 축 정렬 알고리즘(스윕 앤 프룬)을 사용하여 충돌하지 않는 쌍을 빠르게 제거함으로써, 이후 단계의 계산 부하를 최소화합니다.

3. 협역 단계 (Narrow Phase)

• 정확한 교차 테스트를 위해 볼록 헐(Convex Hull) 알고리즘(GJK/EPA)을 활용하여 접촉점 및 법선을 포함한 충돌 매니폴드를 정밀하게 결정합니다.

4. 해소 (Resolution)

• 물리적 안정성을 보장하기 위해 순차적 임펄스 기반 해결기를 사용하여 기계적 제약 조건과 접촉 관통을 해결합니다.

3. 충돌 탐지

3.1. 광역 단계: 최적화된 스윕 앤 프룬 (SAP)

• 많은 수의 객체가 포함된 장면을 효율적으로 관리하기 위해 엔진은 스윕 앤 프룬(SAP) 알고리즘을 활용합니다.
• 여기서 구현된 중요한 최적화는 동적 축 선택(Dynamic Axis Selection)입니다.
  • 시스템은 고정된 축을 고수하는 대신, 매 프레임 객체의 공간적 분산을 평가하고 가장 넓게 퍼진 축을 따라 객체를 정렬합니다.
  • 이를 통해 투영 축 상의 중첩 구간 수를 최소화하여 오탐지(False Positives)를 크게 줄입니다.
• 구현 하이라이트:
  • 중첩된 본체의 활성 목록(Active List)을 유지함으로써 메모리 안전성을 보장하고 검사를 방지합니다.

    void SweepAndPrune1D(const Body* bodies, const int numBodies, std::vector<collisionPair_t>& finalPairs, const float deltaSecond) {
        // 최적화: 밀집된 장면에서 스택 오버플로를 방지하기 위해 std::vector 사용
        std::vector<pseudoBody_t> sortedBodies(numBodies * 2);
  
        // 1. 경계 계산 및 최적의 축 선택
        SortBodiesBounds(bodies, numBodies, sortedBodies.data(), deltaSecond);
  
        // 2. 활성 목록 방식을 이용한 충돌 쌍 구축 (O(N + K))
        BuildPairs(finalPairs, sortedBodies.data(), numBodies);
    }
  
    void BuildPairs(std::vector<collisionPair_t>& collisionPairs, const pseudoBody_t* sortedBodies, const int numBodies) {
        // 참고: finalPairs는 호출자(BroadPhase)에서 초기화됨
        std::vector<int> activeList; // 현재 중첩된 본체들의 ID 저장
  
        const int doubleNumBodies = numBodies * 2;
        for (int i = 0; i < doubleNumBodies; ++i) {
            const pseudoBody_t& targetBody = sortedBodies[i];
            int bodyId = targetBody.id;
  
            if (targetBody.isMin) {
                // 본체가 스윕 축에 진입: 현재 활성화된 모든 본체와 쌍을 생성
                for (int activeId : activeList) {
                    collisionPair_t pair;
                    pair.a = std::min(bodyId, activeId);
                    pair.b = std::max(bodyId, activeId);
                    collisionPairs.push_back(pair);
                }
                activeList.push_back(bodyId);
            } else {
                // 본체가 스윕 축을 벗어남: 활성 목록에서 제거
                auto it = std::remove_if(activeList.begin(), activeList.end(),
                    [bodyId](int id) { return id == bodyId; });
                activeList.erase(it, activeList.end());
            }
        }
    }
  

3.2. 협역 단계: GJK & EPA

• 볼록 다면체 간의 정밀한 충돌 탐지를 위해 엔진은 GJK(Gilbert-Johnson-Keerthi) 알고리즘을 채택합니다.
• 교차 테스트:
  • GJK는 구성 공간 객체(Configuration Space Object, CSO) 내부에 심플렉스(Simplex)를 반복적으로 구축하여 원점을 포함하는지 여부를 판단합니다.
• 접촉 생성:
  • 충돌 시, EPA(Expanding Polytope Algorithm)가 실행되어 심플렉스를 CSO 경계까지 확장함으로써 관통 깊이와 접촉 법선을 계산합니다.
• 구체(Sphere)와 같이 성능이 중요한 기본 도형의 경우, 비싼 GJK 반복 계산을 우회하기 위해 특화된 대수적 테스트(Ray-Sphere, Sphere-Sphere)가 구현되어 있습니다.

4. 하이브리드 충돌 해소

• 엔진은 충돌 상황에 따라 감지된 접촉을 서로 다른 해결기에 지능적으로 배분합니다.

4.1. 연속 충돌 탐지 (CCD)

• 고속 물체가 기하 구조를 통과하는 “터널링 현상”을 완화하기 위해 예측 임펄스 해결기(Predictive Impulse Solver)가 구현되었습니다.
• 메커니즘:
  • 시스템은 동적 객체에 대한 충돌 시간(Time of Impact, TOI)을 계산합니다.
• 실행:
  • 접촉은 TOI 순으로 정렬됩니다.
  • 시뮬레이션은 가장 이른 충돌 시간($TOI > 0$)까지 진행되어 충돌을 해결한 후 이를 반복합니다.
  • 이를 통해 빠르게 움직이는 물체가 정적인 환경과 올바르게 상호작용하도록 보장합니다.

4.2. 순차적 임펄스 해결기

• 정적 접촉($TOI > 0$) 및 기계적 제약 조건(조인트, 정지 접촉)을 위해 반복적 제약 조건 해결기(Iterative Constraint Solver)가 사용됩니다.
• 이 해결기는 복잡한 적재 상황에서 안정성을 확보하기 위해 이전 프레임의 해를 초기 추정값으로 사용하는 “웜 스타팅(Warm Starting)” 기법을 적용합니다.

5. 시각적 디버깅 도구

• 물리 프로그래밍에서 엄격한 시각적 검증이 매우 중요하다는 점을 인식하여, 런타임 검사 도구(Runtime Inspection Tools) 개발에 상당한 비중을 두었습니다.

5.1. 성능 모니터

• 실시간 성능 그래프가 현재 FPS와 CPU 부하를 추적합니다.
• 이는 스트레스 테스트 중 최적화 기법의 효율성에 대한 즉각적인 피드백을 제공합니다.

5.2. 대화형 객체 검사기

• 사용자는 시뮬레이션을 일시 중지하고 마우스 피킹을 통해 객체를 선택할 수 있습니다.

속성 검사기

• 검사기 패널은 선속도/각속도, 질량, 방향을 포함한 실시간 물리적 속성을 보여줍니다.

기즈모 조작

• 선택된 객체는 3D 기즈모를 사용하여 이동하거나 회전할 수 있습니다.
• 조작 후 안정성을 보장하기 위해 물리 상태(속도 초기화)가 자동으로 관리됩니다.

5.3. 심층 접촉 시각화

• 협역 단계와 해결기의 정확성을 검증하기 위해 엔진은 상세한 시각화 모드를 제공합니다.

충돌 메타데이터 시각화

• 와이어프레임 렌더링 모드:
  • 객체 중첩 시 시각적 폐색(Visual Occlusion)을 완화하기 위해, 시스템은 활성 엔티티와 그에 연관된 충돌 쌍에 대해 와이어프레임 렌더링 모드를 지원합니다.
  • 이를 통해 시뮬레이션의 내부 상태를 지속적으로 가시화할 수 있습니다.

  

• 매니폴드 및 프리미티브 식별 (Manifold & Primitive Identification):
  • 접촉 데이터: 개별 접촉점은 적색 큐브 마커로 렌더링되며, 이에 따른 충돌 법선(Collision Normals)은 황색 벡터로 투영되어 수학적 연산 결과에 대한 실증적 검증을 용이하게 합니다.
  • 프리미티브 강조: 다면체(Polyhedral) 형상의 경우, 내로우 페이즈(Narrow-phase) 알고리즘에 의해 식별된 특정 기하학적 프리미티브(삼각형)가 청색으로 강조되어 접촉 매니폴드 형성에 기여하는 정확한 표면을 구분합니다.

  

충돌 결과 트리 UI (Hit Result Tree UI)

• 다중 충돌이 발생할 때 트리 뷰 UI가 모든 접촉 쌍을 정리하여 개발자가 특정 매니폴드를 격리하고 검사할 수 있도록 합니다.
• 특정 접촉점을 선택하면 계층 구조 내의 해당 서브트리가 자동으로 강조됩니다.

5.4. 프레임별 히스토리 (되감기/리플레이)

• 순환 상태 버퍼 (Circular State Buffer):
  • 고속 충돌 이벤트의 분석을 용이하게 하기 위해, 최근 120 프레임의 권한 있는(authoritative) 시뮬레이션 상태(트랜스폼, 속도)를 캐싱하는 순환 이력 버퍼(Circular History Buffer)가 구현되었습니다.
• 분리된 실행 (Detached Execution):
  • 능동적 물리 스테핑:
    • 엔진은 복원된 임의의 과거 프레임에서 시작하는 능동적 물리 시뮬레이션을 지원합니다.
    • 이를 통해 개발자는 메인 게임 루프에 영향을 주지 않고 일시 정지된 환경에서 충돌 해결 로직을 테스트할 수 있습니다.
  • 상태 복원:
    • 이 되감기 단계에서 수행된 모든 시뮬레이션 스텝은 투기적 데이터로 간주됩니다.
    • 라이브 세션 재개 시, 엔진은 이러한 변경 사항을 폐기하고 가장 최신의 캐시된 상태를 다시 로드하여 원본 게임플레이 타임라인의 연속성을 보장합니다.

  

6. 스트레스 테스트 및 검증

• 다양한 조건에서 엔진의 성능과 안정성을 벤치마킹하기 위해 전용 스트레스 테스트 장면이 제작되었습니다.

6.1. 테스트 환경 설정

• 이 장면은 다양한 하위 시스템을 테스트하기 위해 구성 가능한 매개변수를 제공합니다.
• 밀도 (Dense vs. Sparse): 객체 간격을 제어합니다.
  • Dense (밀집): SAP 중첩 검사를 엄격하게 테스트하기 위해 객체들을 촘촘하게 배치합니다.

  

  • Sparse (희소): 컬링(Culling) 효율성을 검증하기 위해 객체들을 분산시킵니다.

  

• 형상 선택:
  • Sphere (구체): 해석적 충돌 알고리즘을 테스트합니다.
  • Diamond (볼록 다면체): GJK/EPA 알고리즘의 성능을 테스트합니다.

  

• 초기 높이:
  • 초기 높이를 수정하여 위치 에너지를 조절함으로써 고속 충돌 안정성과 적재 동작을 테스트할 수 있습니다.

  

6.2. 최적화 검증

• 광역 단계 최적화의 런타임 토글 기능을 통해 스윕 앤 프룬(SAP) 알고리즘과 브루트 포스(Brute-force) 기준 방식 간의 즉각적인 A/B 테스트가 가능합니다.
• 이 설정은 다양한 공간 분포에 따른 알고리즘의 효율성을 검증합니다.

밀집 시나리오 (Dense Scenario)

• 밀집 구성에서는 객체들이 촘촘하게 모여 있어 공간적 중첩도가 높습니다.

• 분석:
  • 위 그림에서 관찰되듯이, 밀집 시나리오에서는 성능 차이가 미미합니다.
  • 객체 농도가 높기 때문에 광역 단계 전략에 관계없이 잠재적인 충돌 쌍의 수가 높게 유지됩니다.
  • 결과적으로 SAP 알고리즘이 쌍을 효과적으로 제거하지 못하며, 계산 부하가 주로 협역 단계에 집중됩니다.

희소 시나리오 (Sparse Scenario)

• 희소 구성에서는 객체들이 장면 전체에 넓게 분포되어 있습니다.

• 분석:
  • 이 시나리오에서는 성능 격차가 뚜렷해집니다.
  • SAP 알고리즘은 상호작용하지 않는 멀리 떨어진 객체들을 효과적으로 제거하여 안정적인 프레임 속도를 유지합니다.
  • 반면, 브루트 포스 방식은 복잡도로 인해 성능이 크게 저하되며, 멀리 떨어진 객체 간의 충돌을 확인하느라 연산 주기를 낭비합니다.

7. 샌드박스 장면 (Sandbox Scene)

• 샌드박스 장면은 제약 조건 해결기의 안정성과 다재다능함을 확인하기 위해 전형적인 시뮬레이션 시나리오를 보여주는 종합 검증 환경 역할을 합니다.

7.1. 시뮬레이션 시나리오

상자 쌓기 (Stacked Boxes)

• 이는 반복적 해결기의 수렴성과 안정성을 검증합니다.
• 특히 수직 적재 중 지터(Jitter) 현상을 방지하는 데 있어 “웜 스타팅”의 효과를 테스트합니다.

체인 (Chain)

• 거리 제약 조건(Distance Constraints)과 오차 보정을 테스트합니다.
• 이 시나리오는 중력과 인장력 하에서도 링크가 늘어나지 않고 연결 상태를 유지하는지 확인합니다.

이동 플랫폼 (Moving Platform)

• 운동학적 본체(Kinematic bodies, 무한 질량)와 동적 본체 간의 상호작용을 검증합니다.
• 이동하는 표면에서의 마찰력 적용 및 상대 속도 처리를 테스트합니다.

회전자 (Rotator)

• 각속도 적분 및 충돌 반응을 보여줍니다.
• 이 시나리오는 동적 객체가 고속으로 회전하는 운동학적 장애물의 충돌에 어떻게 반응하는지 테스트합니다.

래그돌 (Ragdoll)

• 이는 복잡한 관절 시스템(Articulated System) 테스트입니다.
• 계층적 변환과 조화롭게 작동하는 다중 제약 조건(조인트 및 제한 범위)의 안정성을 검증합니다.

8. 향후 발전 방향

• 엔진의 기능과 성능을 더욱 향상시키기 위해 다음과 같은 개선 사항이 계획되어 있습니다.

협역 단계 최적화

• 지속적인 접촉에서 계산 오버헤드를 줄이기 위해 GJK에 시간적 일관성(Temporal Coherence) 또는 고급 캐싱 기법을 구현합니다.

샌드박스 케이스 추가

• 복잡한 복합 형상과 추가적인 제약 조건 유형(예: 볼앤소켓, 슬라이더)을 도입합니다.

스트레스 테스트 형상 추가

• 더 넓은 범위의 충돌 기본 도형을 검증하기 위해 캡슐(Capsule) 및 원기둥(Cylinder)을 테스트 제품군에 포함합니다.

Top