[CG] Sweep and Prune 알고리즘(SAP)

sweep and prune은 교수님께서 특정 논문을 읽으라고 하셨을 때 본 방법입니다

하지만 한글 해석이 된 포스팅이 없어서 간단하게 번역하여 놓고 점점 추가 및 보완할 예정입니다

해당 포스팅은 https://github.com/mattleibow/jitterphysics/wiki/Sweep-and-Prune 을 한국어로 해석한 포스팅으로 문제가될 시 삭제하도록 하겠습니다

 

 

 

광역 충돌 시스템은 모든 물리 엔진의 핵심 과정 중 하나입니다.

이미 광역 충돌에 대해 놓친 게 있다면 광역 충돌시스템을 최적화하는 코드를 짜서 복구하기는 어렵습니다.

물리 엔진에서 충돌 단계에는 3가지가 있습니다.

 

1. Broadphase : 광대한 범위

- 여기서 어떤 충돌이 실제로 일어날 수 있는지를 감지하고, 충돌할 수 없는 충돌을 폐기합니다.

 

참고할만한 사이트 : https://developer.nvidia.com/gpugems/gpugems3/part-v-physics-simulation/chapter-32-broad-phase-collision-detection-cuda

Chapter 32. Broad-Phase Collision Detection with CUDA

 

2. Midphase : 중간 범위

- 구나 천 물체 같은 기하학적 단계에서의 충돌을 말합니다. 

 

3. Narrowphase : 좁은 범위

- 이 단계에서 실제 충돌 감지를 수행합니다.  교차점, 충돌 법선 또는 침투 깊이와 같은 충돌 데이터를 검색하는 작업을 합니다.

 

거의 모든 광역 시스템은 객체의 축 정렬된 경계 상자(aabb)를 사용합니다.

aabb는 꽤 빨리 계산될 수 있으며 교차점을 확인하는 것도 몇 줄의 코드로 수행됩니다.

 

참고할만한 사이트 : https://blog.naver.com/mycode333/50031266282

AABB와 AABB 충돌

 

그렇다면, 어떻게 하면 "겹치지 않는 쌍의 정렬 과정"을 가속화 할 수 있을까요?

충돌을 감지하기 위한 예전의 접근방식에 대해 몇 가지를 알아봅시다.

 

for (int i = 0; I < rigidBodies.Count; i++)
{
    for (int e = i; e < rigidBodies.Count; e++)
    {
        if (CheckBoundingBoxForOverlap(i, e))
            DetectNarrowPhase(i,e);
    }
}

그렇게 나쁘지는 않지만..

만약 10x10x10 충돌 감지 되는 큐브가 있다면 최상의 경우 수천 개의 충돌 가능한 쌍을 확인하여 위의 코드를 수행해야 합니다. 좁은 범위의 충돌 체크는 0.25백만 개를 체크해야합니다.

자연적으로 광역 범위는 O(n^2) 문제가 생기는데 이에 대해 무엇을 할 수 있을까요?

 

데이터 구조를 가속화해야 합니다.

웹에서 "광역상 충돌 탐지"를 검색하면 Sweep And Prune(SAP)접근법을 발견하게 된다.

많은 변형된 구현들이 있지만 분류한 다음 다듬는다(Prune)는 공통점이 있다.

 

SAP 알고리즘에서 가장 간단한 "flavor"를 지속되지 않는 단일 축 SAP에서 사용한다는 것이 무엇을 의미하는지 알아보자.

 

1. 공간 안의 모든 물체들은 "axisList"라는 목록 안에 들어있다. 경계상자의 시작을 이용해 한 개의 축(여기서는 X축)으로 리스트를 정렬한다. 따라서 물체 5의 가장 왼쪽 지점이 X축을 직접 볼 때 물체 6의 가장 왼쪽 지점보다 더 왼쪽에 있다는 것을 알 수 있다.

 

2. "activeList"라는 새로운 임시 리스트를 만들자. 이제 "axisList"의 다음 항목을 보고 "activeList"의 모든 항목과 비교한다.(현재는 단 하나) 만약 새 항목의 왼쪽이 더 크면 현재 "activeList"의 오른쪽 항목이 제거되고 "activeList"에서 현재 "activeList" 아이템이 제거된다. 그렇지 않으면 새 "axisList" 항목과 현재 "activeList" 항목 간의 충돌 가능성이 생긴다. 새 항목 자체를 "activeList"에 추가하고 "axisList"의 다음 항목을 계속하자.

 

 

출처 : https://github.com/mattleibow/jitterphysics/wiki/Sweep-and-Prune

 

이 접근법이 지속적이지 않다는 것을 알게된다. 정렬은 처음부터 모든 프레임에서 수행되며(quicksort 성능이 좋다) 한 축(여기에서는 X축)에 대해 정렬된다. 우리는 장면의 일관성을 이용하지 않는다.(한 프레임에서 장면이 많이 변하지 않을 가능성이 있다) 속도 향상은 어디서 오는가?

정답은 충돌 탐지는 검색 문제이기 때문이다. 그리고 사전 분류된 목록을 검색은 O(nlog(n)) 보다 빠르다.

이 쉬운 접근법을 구현하면 무차별 힘 알고리즘(brute force algorithm)에 비해 엄청난 속도 향상이 가능하다.

JigLib (Danny Chapman이 만든 코드)에서 C # (JigLibX)로 이식되었을 때, JigLib의 원래 버전은 무차별적인 힘과 매우 기본적인 그리드 접근법을 포함하고있었다.
존 와트는 위에서 설명한 코드를 정확하게 사용하는 프로젝트에 SAP 알고리즘을 적용했는데, 이는 복잡한 그리드 접근법을 쉽게 극복했다.

따라서 이 코드는 이미 꽤 잘 수행되지만, 그럼에도 불구하고 X축에서 모든 물체가 겹치면 런타임은 다시 O (n *2)이다.

(따라서, 대부분의 물체가 그곳에서 겹치기 때문에, 분리 축으로 up-축을 사용하지 마라)

 

Sweep and Prune을 하기 위한 더 복잡한(그리고 더 빠른) 접근법은 완전한 3축 검사를 하는 것이다.

두 물체가 충돌하면 세 축 모두 겹치는 경우에만 충돌한다 (분리 축 정리).

지속적 3Axis SAP는 다음과 같이 요약하여 작동한다.

우리는 세 개의 목록 (각 축 1에 대해)을 사용하고 삽입 정렬을 사용하여 정렬된 목록을 유지한다.

삽입 정렬은 거의 정렬된 목록에서 O(n)이다.

삽입 정렬 알고리즘의 스왑은 개체가 다른 본체와 중첩되기 시작/중지하는 것을 의미한다.

그래서 한 개의 해시 테이블을 겹쳐서 보관하고 각 프레임은 삽입구역을 하고 해시 테이블 구조를 업데이트하는 데 사용하는 변경사항만 보고받는다.

Jitter의 절차는 다음과 같다.

 

private void SortAxis(List<SweepPoint> axis)
{
    for (int j = 1; j < axis.Count; j++)
    {
        SweepPoint keyelement = axis[j];
        float key = keyelement.Value;
        
        int i = j - 1;
        
        while (i >= 0 && axis[i].Value > key)
        {
            SweepPoint swapper = axis[i];
            
            if (keyelement.Begin && !swapper.Begin)
            {
                if (CheckBoundingBoxes(swapper.Body, keyelement.Body))
                {
                    lock (fullOverlaps)
                    {
                        fullOverlaps.Add(new BroadphasePair(swapper.Body, keyelement.Body));
                    }
                }
            }
            
            if (!keyelement.Begin && swapper.Begin)
            {
                lock (fullOverlaps) 
                {
                    fullOverlaps.Remove(new BroadphasePair(swapper.Body, keyelement.Body));
                }
            }
            
            axis[i + 1] = swapper;
            i = i - 1;
        }
        axis[i + 1] = keyelement;
    }
}

 

 

만약 당신이 전형적인 SAP 데이터 구조의 모든 세부사항에 관심이 있다면, 나는 피에르 테르디만이 쓴 훌륭한 기사를 읽을 것을 추천한다.

그렇지 않다면 각 프레임에 "A가 축 C에서 B와 겹친다"는 정보나 "A가 축 C에서 B의 중첩을 중지했다"는 정보만 전달받으면 X, Y 또는 Z축이 될 수 있다.

처음 이것을 시행했을 때, 나는 내가 받는 값싼 결과에 매우 만족했고, 그리고 나서 실수를 했다. 나는 각각의 쌍이 얼마나 중복되는지를 기억하는 데이터 구조를 구현했다.

겹치는 횟수가 3회(모든 축에서 겹치는 횟수가 1회임을 의미)인 경우, 물체는 충돌한다.

이것은 효과가 있지만 끔찍하다.

한 축에 겹치는 쌍의 수는 매우 높을 수 있으므로 중복 계수 = 1인 수천 개의 잠재적 겹치는 쌍을 저장해야 한다. 단지 몇 개만 두 번째 축에 겹치고 겹치는 횟수가 2이고, 세 번째 축에 겹치는 횟수는 3이라는 것을 깨닫는다.

결국 런타임은 O(nlogn)였지만 메모리 사용량은 O(n^2)이었다(내 사전 구조를 죽이는 것) – 내가 이 결함을 처음 한 것은 아니라고 하자.

이 문제의 해결책은 간단하다. 아무것도 저장하지 마라.

한 축이 중첩을 보고하는 경우 저렴한 전체 경계 상자 확인 – 양수일 경우 해당 쌍을 풀오버랩에 추가하십시오.

한 축에 두 개의 몸체가 분리되어 있다고 보고된 경우, 풀오버랩에서 쌍을 제거하십시오. (이것은 위의 코드로 행해진다.) 따라서 SAP에 사용되는 메모리는 다시 O(n)에 지나지 않음

("CollisionSystemPersistent"에서 Jitter의 구현을 찾을 수 있음) SAP.cs".)

 

지속적인 Sweep and Prune 알고리즘의 단점 중 하나는 많은 비활성 객체를 가진 정말 큰 세계를 경험한다는 것이다.

총알이 정적인 물체가 많은 마을을 관통하는 것을 상상해보라.

각 물체(총탄으로부터 수마일 떨어져 있어도)와 탄환 자체 사이에 교환이 있다

이 문제는 그리드(광범위 단계)를 구성하는 여러 개의 소형 SAP를 사용하여 해결할 수 있다.

내가 알아차린 또 다른 문제는 광선과 경계 상자 질의가 효율적으로 수행될 수 없다는 것이다.

레이캐스팅의 경우, 정렬된 세 개의 목록은 균일하지 않은 복셀 그리드로 해석될 수 있으므로, 주문한 레이 쿼리를 얻을 수 있다.

이것은 실제로는 다소 느리다. 왜냐하면 많은 복셀 그리드가 비어 있고 초기 타격을 받은 광선에 대한 해결책일 뿐이기 때문이다. 단지 각 물체에 대해 거친 힘 검사를 하는 것이 종종 더 빠르기 때문이다.

또 다른 문제는 장면에 하나의 큰 물체(대개 지면이나 레벨)가 포함되어 있다는 것이다.
이 개체의 끝점은 완전히 왼쪽에 있고 목록 오른쪽에 있다.

스위프 포인트에 저장된 추가 정보가 없으면 개체가 훨씬 더 큰 엔티티의 끝점에 의해 둘러싸이는지 여부를 효율적으로 감지할 수 있는 방법이 없다.