충돌 감지: 컴퓨터 비전의 시각적 교차점 이해

By Fouad Sabry

충돌 감지란 무엇입니까

충돌 감지는 둘 이상의 공간 객체(일반적으로 컴퓨터 그래픽 객체)의 교차점을 감지하는 계산 문제입니다. 이는 주로 컴퓨터 그래픽, 컴퓨터 게임, 컴퓨터 시뮬레이션, 로봇 공학 및 전산 물리학 등 다양한 컴퓨팅 분야에 적용됩니다. 충돌 감지는 계산 기하학의 고전적인 문제입니다. 충돌 감지 알고리즘은 2D 또는 3D 공간 개체에 대한 작동으로 나눌 수 있습니다.

혜택을 받는 방법

(I) 다음에 대한 통찰력 및 검증 주제:

1장: 충돌 감지

2장: 광선 추적(그래픽)

3장: 이진 공간 분할

장 4: 중심

5장: 분기 및 경계

6장: 소실점

7장: 쿼드트리

8장: 경계 볼륨

9장: 주기 감지

10장: 선 배열

(II) 충돌 감지에 관한 대중의 주요 질문에 답합니다.

(III) 다양한 분야에서 충돌 감지를 사용하는 실제 사례.

이 책의 대상 독자

전문가, 학부생 및 대학원생 , 매니아, 애호가 및 모든 종류의 충돌 감지에 대한 기본 지식이나 정보를 넘어서고 싶은 사람들.

 

 

• Language: 한국어
• Publisher: 10 억 지식이 걸립니다 [Korean]
• Release date: May 4, 2024

Book preview

1 장 : 충돌 감지

두 개 이상의 물체의 교차점을 감지하는 컴퓨터 문제를 충돌 감지라고 합니다. 충돌 감지는 계산 기하학의 고전적인 문제이며 다양한 컴퓨팅 영역, 특히 컴퓨터 그래픽, 컴퓨터 게임, 컴퓨터 시뮬레이션, 로봇 공학 및 계산 물리학에 적용됩니다. 2D 및 3D 충돌 감지 기술은 각각의 물체 크기로 구별할 수 있습니다.

물리적 시뮬레이션에는 당구와 같은 테스트 수행이 포함됩니다. 강체 운동과 탄성 충돌의 우산 아래에서 튀는 당구 공의 역학이 잘 이해됩니다. 상황에 대한 첫 번째 설명에는 당구대와 공에 대한 자세한 물리적 설명과 각 공의 시작 위치가 포함됩니다. 당구공에 가해지는 힘(종종 플레이어가 당구봉으로 공을 친 결과)이 주어지면 컴퓨터 프로그램을 사용하여 모든 공의 궤적, 정확한 움직임 및 최종 정지 위치를 결정하려고 합니다. 이 게임의 시뮬레이션에는 여러 모듈이 필요하며, 그 중 하나는 당구공 간의 정확한 충돌을 계산하는 역할을 합니다. 계산에서 약간의 부정확성은 이 예에서 볼 수 있듯이 당구공의 최종 위치에 극적인 변화를 초래합니다.

비디오 게임에 대한 기준은 비슷하지만 상당한 변화가 있습니다. 컴퓨터 시뮬레이션은 현실 세계의 물리학을 가능한 한 정확하게 모방해야 하는 반면, 컴퓨터 게임은 실제 물리학을 수용 가능한 방식으로, 실시간으로, 충분한 복원력으로 시뮬레이션해야 합니다. 결과 시뮬레이션이 게임 플레이어에게 만족스러우면 타협이 허용됩니다.

서로 다른 물리적 시뮬레이터는 충돌에 다르게 반응합니다. 일부는 재질의 부드러움을 사용하여 실제에서와 같이 후속 시간 단계에서 충돌을 해결할 힘을 계산합니다. 일부 재료의 경도로 인해 많은 처리 능력이 필요합니다. 일부 시뮬레이터는 선형 보간을 사용하여 충돌 시간을 추정하고 시뮬레이션을 롤백한 다음 보존 원칙을 기반으로 하는 보다 추상적인 접근 방식을 사용하여 충돌을 계산합니다.

일부는 선형 보간(Newton의 접근 방식)을 반복하여 시뮬레이션의 나머지 부분보다 훨씬 더 정밀하게 충돌 시간을 계산합니다. 시간적 일관성을 활용하는 충돌 감지는 항공 교통 관제와 같이 CPU 수요를 크게 증가시키지 않고도 점점 더 미세한 시간 단계를 허용합니다.

비탄성 충돌 후에 슬라이딩 및 정지의 특수 상태가 발생할 수 있으며, Open Dynamics Engine은 제약 조건을 사용하여 이를 모델링합니다. 제약 조건은 관성을 방지하고 결과적으로 불안정성을 방지합니다. 장면 그래프를 통해 휴식을 구현하면 드리프트를 방지할 수 있습니다.

즉, 물리적 시뮬레이터는 일반적으로 사후(충돌이 발생한 후) 또는 선험적으로(충돌이 발생하기 전)(충돌이 발생하기 전) 충돌을 감지합니다. 사후적 충돌과 선험적 충돌 감지 알고리즘의 구분 외에도 거의 모든 최신 충돌 감지 알고리즘은 계층적으로 구성됩니다. 일반적으로 a posteriori 및 a priori 대신 discrete 및 continuous가 사용됩니다.

사후 시뮬레이션에서는 물리적 시뮬레이션이 약간 진행된 다음 물체가 겹치는지 또는 눈에 띄게 교차하는 것으로 간주되는지 여부가 결정됩니다. 각 시뮬레이션 단계에서 교차하는 모든 물체의 위치와 궤적은 충돌을 설명하기 위해 고정됩니다. 이 방법은 일반적으로 정확한 충격 순간을 놓치고 사후에만 감지하기 때문에 사후라고 합니다.

선험적 접근 방식에는 물리적 물체의 궤적을 매우 정확하게 예측할 수 있는 충돌 감지 알고리즘이 있습니다. 충돌의 순간은 정밀하게 계산되며, 물리적 물체는 결코 실제로 충돌하지 않습니다. 이를 선험적이라고 하는데, 충돌 감지 방법이 물리적 물체의 구성을 업데이트하기 전에 충돌 순간을 계산하기 때문입니다.

사후 접근법의 주요 장점은 다음과 같습니다. 간단한 물리적 바디 목록이 알고리즘에 제공되고 프로그램은 교차하는 바디 목록을 생성합니다. 충돌 감지 기술은 마찰, 탄성 또는 비탄성 충돌 또는 변형 가능한 물체에 대한 지식이 필요하지 않습니다. 더욱이, 사후적 알고리즘은 선험적 알고리즘보다 한 차원 더 단순합니다. 시간 변수는 사후 문제에서 생략되며, 이는 선험적 알고리즘을 필요로 합니다.

반면, 사후 알고리즘은 물리적으로 잘못된 교차점을 복구해야 하는 수정 단계에서 문제를 나타냅니다. 또한 개별 단계가 너무 크면 충돌이 인식되지 않을 수 있으므로 충분히 빠르거나 작은 경우 오브젝트가 다른 단계를 통과할 수 있습니다.

선험적 알고리즘의 장점은 정밀도와 일관성이 향상된다는 것입니다. 물리적 시뮬레이션을 충돌 감지 방법에서 분리하는 것은 어렵습니다(불가능하지는 않지만). 그러나 가장 간단한 상황을 제외한 모든 상황에서, 두 물체가 충돌할 때를 예측하는 문제(주어진 시작 데이터)에는 닫힌 형식의 솔루션이 없으며 일반적으로 수치 근 찾기가 필요합니다.

예를 들어, 테이블 위에 놓인 꽃병은 접촉하거나 충돌하지만 뛰어내리거나 상호 침투하지 않습니다. 휴식 접촉은 항상 특정 처리를 요구합니다 : 두 물체가 충돌 (사후 적) 또는 미끄러짐 (선험적)이고 상대 속도가 임계 값보다 작 으면 마찰이 가해지고 두 물체가 장면 그래프의 동일한 분기에 배치됩니다.

여러 물체 간의 충돌을 감지하는 기존의 방법은 매우 느립니다. 분명히 모든 객체를 다른 모든 객체와 비교하는 것은 효과가 있지만 객체 수가 많을 때는 낭비입니다. 각 면을 다른 모든 면과 비교하여 기존 방식으로 복잡한 형상 객체를 서로 확인하는 것은 시간이 많이 걸리는 프로세스입니다. 따라서 이 문제에 대한 해결책을 신속하게 해결하기 위해 상당한 연구가 수행되었습니다.

많은 응용 분야에서 물리적 물체의 구성은 한 시간 단계에서 다음 단계로 거의 변하지 않습니다. 많은 물체가 움직이지 않을 수 있습니다. 이전 시간 단계에서 수행된 계산을 현재 시간 단계에서 활용할 수 있도록 알고리즘이 생성되어 더 빠른 계산이 가능합니다.

대략적인 수준의 충돌 감지에서 목표는 잠재적으로 충돌할 수 있는 개체 쌍을 식별하는 것입니다. 이 커플은 추가 조사가 필요합니다. 캘리포니아 대학교 버클리 캠퍼스(University of California, Berkeley)[1]의 밍 C. 린(Ming C. Lin)은 그림의 모든 n개 물체에 대해 축에 정렬된 경계 상자를 사용하여 이 목적을 위해 고성능의 초기 방법을 만들었습니다.

각 상자는 세 개의 간격(즉, 1, 2, 3)의 곱으로 표시되며, 상자는 )입니다

I_{1}\times I_{2}\times I_{3}=[a_{1},b_{1}]\times [a_{2},b_{2}]\times [a_{3},b_{3}]

.

스윕 및 정리는 경계 상자의 충돌 감지를 위한 일반적인 기술입니다.

이러한 상자가 두 개 있고 I_{1}\times I_{2}\times I_{3} J_{1}\times J_{2}\times J_{3} intersect if 뿐만 아니라 I_{1} intersects J_{1} , I_{2} intersects J_{2} 및 I_{3} intersects J_3 .

한 시간 단계에서 다음 시간 단계로, 만약 I_{k} 에 교차하면 J_{k} , 다음 시간 단계에서 계속 중첩될 가능성이 매우 높습니다.

마찬가지로, 이전 시간 단계에서 교차하지 않았다면 지금 교차하지 않을 것이며 앞으로도 계속 교차하지 않을 것입니다.

따라서 이 문제를 교차하는 간격이 존재하는 이미지에서 이미지로 추적하는 문제로 단순화합니다.

세 개의 간격 목록(각 축에 하나씩)이 있고 모든 목록의 길이가 동일합니다(각 목록의 길이가 경계 n 상자의 수량이기 때문에). 모든 목록에서 각 간격은 목록의 다른 모든 간격과 교차할 수 있습니다.

따라서 모든 목록에 대해 n\times n 0과 1의 M=(m_{{ij}}) 행렬 을 갖게됩니다 : 간격 m_{ij} 과 교차하면 i 1, j 두 선이 교차하지 않으면 0입니다.

우리의 추정에 따르면, M 구간 목록과 관련된 행렬은 한 시간 단계에서 다음 시간 단계로 본질적으로 변경되지 않은 상태로 유지됩니다.

이를 활용하기 위해 실제로 간격 목록은 레이블이 지정된 끝점 목록으로 유지됩니다.

목록의 각 항목에는 간격의 끝점 좌표와 해당 간격을 식별하는 고유한 정수가 포함됩니다.

그런 다음 목록이 좌표별로 정렬되고 진행하면서 행렬을 업데이트 합니다 M .

경계 상자의 구성이 한 시간 단계에서 다음 단계로 크게 변경되지 않는 경우 이 방법이 매우 빠르게 실행될 것이라고 생각하는 것은 어렵지 않습니다.

의상 시뮬레이션과 같은 변형 가능한 몸체의 경우, 아래에 설명된 대로 보다 전문화된 쌍별 가지치기 전략을 사용하는 것이 실용적이지 않을 수 있습니다. N-바디 가지치기 접근 방식이 달성할 수