스위프 및 프루닝

Sweep and prune

물리적 시뮬레이션에서 스위프 앤 프루닝은 충돌 감지 중에 충돌 여부를 확인해야 하는 고체 쌍의 수를 제한하기 위해 사용되는 광범위한 위상 알고리즘이다(예: 교차).이는 여러 임의 축을 따라 각 솔리드의 경계 볼륨의 시작(하한)과 끝(상한)을 정렬하여 수행됩니다.솔리드가 이동함에 따라 솔리드의 시작과 끝이 겹칠 수 있습니다.두 솔리드의 경계 볼륨이 모든 축에서 겹치면 보다 정확하고 시간이 많이 걸리는 알고리즘에 의해 테스트되도록 플래그가 지정됩니다.

스위프 및 프루닝은 고체가 두 시뮬레이션 단계 사이에서 유의하게 이동하지 않을 가능성이 높기 때문에 시간적 일관성을 이용합니다.그 때문에, 각 단계에서, 비교적 적은 연산 조작으로, 경계 볼륨의 정렬 리스트를 갱신할 수 있다.삽입 정렬과 같이 거의 정렬된 목록을 빠르게 정렬하는 정렬 알고리즘이 특히 이 용도로 유용합니다.

사용되는 바운딩 볼륨의 종류에 따라 솔리드가 방향을 바꿀 때마다 바운딩 볼륨 치수를 업데이트해야 합니다.이를 피하기 위해 시간적 일관성을 사용하여 적은 연산으로 경계 볼륨 지오메트리의 변경 사항을 계산할 수 있습니다.또 다른 접근방식은 경계구 또는 다른 방향의 독립적인 경계 볼륨을 사용하는 것이다.

스위프 앤 프루닝은 정렬과 [1]스위프라고도 알려져 있는데,[2] 1992년 데이비드 바라프의 박사 논문에서 이런 식으로 언급되었다.나중에 Jonathan D의 I-COLide에 관한 1995년 논문과 같은 작업을 한다.Cohen 등은 이 알고리즘을 sweep and prune이라고 부릅니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Ericson, Christer (2005), Real-time collision detection, Morgan Kaufmann series in interactive 3D technology, Amsterdam: Elsevier, pp. 329–338, ISBN 978-1-55860-732-3
  2. ^ Baraff, D. (1992), Dynamic Simulation of Non-Penetrating Rigid Bodies, (Ph. D thesis), Computer Science Department, Cornell University, pp. 52–56
  3. ^ Cohen, Jonathan D.; Lin, Ming C.; Manocha; Ponamgi, Madhav K. (April 9–12, 1995), I–COLLIDE: an Interactive and Exact Collision Detection System for Large Scale Environments) (PDF), Proceedings of the 1995 Symposium on Interactive 3D Graphics (Monterey, CA), pp. 189–196

외부 링크


Stub icon

이 컴퓨터 기사는 스텁입니다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.