Real Time Collision Detection - Chapter 2 : Collision Detection Design Issues
Chapter 2. Collision Detection Design Issues
효율적인 충돌 탐지 시스템을 설계하는 것은 퍼즐을 맞추는 것과 같다. 큰 그림이 나타나기 전에 많은 조각들이 연결되어야한다.
비슷한 방식으로, 이 책의 대부분은 충돌 탐지에 대한 다른 접근법을 다루는 개별 부분을 조사하는 것과 관련이 있다.
큰 그림은 책의 과정에서 분명해질 것이다. 이 장에서는 접근법 중 하나를 선택할 때 고려해야 할 여러 가지 문제와 이러한 접근법의
구성 요소가 어떻게 관련되는지를 간략하게 설명한다. 이 장에서는 또한 다음 장에서 정의되고 설명되는 많은 용어를 소개한다.
여기에 언급 된 항목에 대한 자세한 내용은 이 책의 나머지 장에서 제공된다.
2.1 Collision Algorithm Design Factors
충돌 감지 시스템을 설계 할 때 선택 사항에 영향을 미치는 몇 가지 요인이 있다. 이러한 요소는 다음 범주로 나뉜다.
1. 응용 프로그램 도메인 표현 : 장면과 그 객체에 사용된 기하학적 표현은 사용된 알고리즘에 직접적인 영향을 미친다.
이러한 표현에 대한 제한이 줄어들면 보다 일반적인 충돌 감지 솔루션을 사용해야하며 가능한 성능 파급 효과가 있다.
2. 다른 유형의 쿼리 : 일반적으로 주제별 쿼리 유형 및 결과는 쿼리를 얻기 위해 더 많은 계산 작업이 필요하다.
특정 쿼리를 지원하려면 추가 데이터 구조가 필요할 수 있다. 모든 개체 유형이 모든 쿼리 유형을 지원하는 것은 아니다.
3. 환경 시뮬레이션 매개 변수 : 시뮬레이션 자체에 충돌 감지 시스템에 직접적인 영향을 미치는 몇 가지 매개 변수가
포함되어 있다. 여기에는 얼마나 많은 객체가 있는지, 객체의 상대적 크기와 위치, 이동 여부 및 이동 방법, 상호 침투
허용 여부, 경직 여부 등이 포함된다.
4. 성능 : 실시간 충돌 감지 시스템은 엄격한 시간 및 크기 제한 하에 작동한다. 시간과 공간이 항상 균형을 이루는 경우
명시된 성능 요구 사항을 충족시키기 위해 일반적으로 여러 기능이 균형을 이룬다.
5. 견고성 : 모든 응용프로그램이 동일한 수준의 물리적 시뮬레이션을 필요로 하지는 않는다. 예를 들어, 벽돌을 서로
위에 겹쳐 놓으면 농구 코트에서 튀는 농구보다 충돌 감지 시스템에서 훨씬 더 정교하다. 공이 너무 일찍 또는 다소
큰 각도로 튀는 경우는 눈에 띄지 않지만 적층된 벽돌의 접점을 계산할 때 발생하는 사소한 오류조차도 천천히
상호 침투하거나 서로 떨어져 나가기 쉽다.
6. 구현 및 사용의 용이함 : 대부분의 프로젝트는 time frame에 있다. 충돌 감지 시스템의 일정 잡기 기능은 시스템을
완료하고 정시에 사용할 수 없는 경우 아무런 의미가 없다. 구현의 단순성에 관한 결정은 어떤 접근법이 취해지는데
큰 역할을 한다.
이러한 문제는 이 장의 나머지 부분에서 더 자세히 설명한다.
2.2 Application Domain Representation
적절한 충돌 감지 알고리즘을 선택하려면 장면과 그 객체에 사용될 기하학적 표현의 유형을 고려하는 것이 중요하다.
이 절에서는 다양한 객체 표현, 모델링 기하학 대신 단순화 된 기하학을 사용할 수 있는 방법 및 응용 프로그램별 지식을 통해
일반적인 솔루션보다 특수화 된 솔루션을 사용하는 방법에 대해 간략하게 설명한다.
2.2.1 Object Representations
현재의 하드웨어는 삼각형을 기본 렌더링 프리미티브로 사용한다. 결과적으로 다각형 표현은 장면 및 장면 객체뿐만 아니라
해당 충돌 형상에 대한 자연스러운 선택이다. 가장 일반적인 폴리곤 표현은 폴리곤 수프이다. 하나의 폴리곤이 다른 폴리곤과
어떻게 연관되어 있는지를 지정하는 연결 정보가 없는 폴리곤의 정렬되지 않은 콜렉션이다. 고유한 제약이 없기 때문에 폴리곤
수프는 아티스트와 레벨 디자이너에게 매력적인 표현이다. 폴리곤 수프에서 작동하는 알고리즘은 모든 폴리곤 컬렉션에 적용되지만
추가 정보에 의존하는 것보다 덜 효율적이고 덜 강력하다. 예를 들어, 폴리곤 수프에는 객체의 "안쪽"에 관한 정보가 포함되어 있지
않으므로 객체가 실수로 다른 객체 내부에 잘못 처리되었는지 쉽게 알 수 없다. 언급된 추가 정보에는 어떤 모서리가 어떤 꼭지점에
연결되어 있고, 어떤 면이 주어진 면에 연결되어 있는지 객체가 닫힌 솔리드를 형성하든 객체가 볼록 또는 오목인지 여부 등이
포함 될 수 있다.
다각형은 가장자리에서 서로 연결되어 다각형 메쉬라는 더 큰 다각형 표면을 형성 할 수 있다. 다각형 메쉬 모음에서 객체를 작성하는
것은 기하학적 모델을 작성하는 가장 일반적인 방법 중 하나이다. (그림 2.1).
다각형 객체는 정점, 모서리, 면으로 정의된다. 이런 방식으로 구성 될 때 객체는 명시적 표현을 가지고 있다고 한다.
암시적 객체는 구체, 원추, 원통, 타원체, 토리 및 기타 방식으로 명시적으로 정의되지 않지만 수학 표현식을 통해 암시적으로 정의되는
기타 기하 프리미티브를 나타낸다.
암시적 객체는 quick rejection culling을 위해 장면 객체의 대략적인 근사값으로 사용될 수 있다.
2.2.2 Collision Versus Rendering Geometry
렌더링 구조를 충돌 시스템에 직접 전달할 수도 있지만 충돌 감지가 수행되는 별도의 geometry(형상)을 갖는 것이 더 나은 이유가 있다.
1. 그래픽 플랫폼이 렌더링 지오메트리가 너무 복잡해져서 충돌 감지 또는 물리를 수행하는데 사용하기 어려워졌다.
또한, 충돌이 얼마나 정확해야하는지에 관해서는 일반적으로 한게가 있다. 따라서 렌더링에 사용된 것과 동일한 지오메트리를
사용하는 대신 단순한 프록시 지오메트리를 대신해 충돌 감지를 대체 할 수 있다. 예를 들어, 게임의 경우 오브젝트 복잡성에
관계없이 게임 오브젝트를 나타내기 위해 구 및 큐브와 같은 간단한 기하학적 모양에 의존하는 것이 일반적이다.
프록시 개체가 충돌하면 실제 개체도 충돌하는 것으로 간주된다. 이러한 단순한 기하학적 모양 또는 경계 체적은 사용된
기하학적 표현과 상관없이 충돌 쿼리를 가속화하는데 자주 사용된다. 일반적으로 경계 볼륨은 형상을 완전히 캡슐화하기
위해 만들어진다. 경계 체적에 대해서는 4장에서 자세히 설명한다.
2. 현대적인 하드웨어의 경우 기하학적 모양이 특정 렌더링 형식(예 : 삼각형 스트립 및 인덱싱된 정점 버퍼)에 존재하지 않으므로
빠른 렌더링이 가능하지만 충돌 감지는 불가능하다. 디코딩된 데이터를 재사용을 위해 캐시 할 수 있는 경우에도 즉시 이러한
구조를 디코딩하는 대신 특수 충돌 지오메트리를 제공하는 것이 더 효율적이다. 또한, 그래픽 하드웨어는 종종 삼각형 전용 형식을
시행한다. 충돌 지오메트리의 경우 비 삼각형이 아닌 프리미티브를 지원해 효율성을 유지할 수 있다.
3. 렌더링 지오메트리 및 충돌 지오메트리에 필요한 데이터 및 데이터 구성이 크게 달라질 수도 있다. 정적 렌더링 데이터는 재질별로
정렬 될 수 있지만 충돌 데이터는 일반적으로 공간적으로 구성된다. 렌더링 지오메트리에는 재질 정보, 정점 색상 및 텍스처 좌표와
같은 포함된 데이터가 필요하지만 충돌 지오메트리에는 관련 표면 속성이 필요하다. 둘을 분리하고 모든 충돌 관련 정보를 함께
유지하면 충돌 데이터가 작아진다. 데이터가 작을수록 데이터 캐시 일관성이 향상되므로 효율성이 향상된다.
4. 어느 정도의 collision geometry는 디자인에 따라 달라질 수 있다. 예를 들어, 스노우 보드 게임에서 무릎 파우더 스노우는
눈 표면 렌더링된 표현에서 2피트 아래의 충돌 표면에 의해 모델링 될 수 있다. 발목이 깊게 흔들리는 잔디밭을 걷거나 허리 깊은
어두운 물에 걸어가는 것도 비슷하게 처리 할 수 있다. 렌더링 지오메트리가 충돌 지오메트리로 사용 되더라도 충돌 지오메트리
데이터 세트에서 일부 렌더링 지오메트리를 제외시키는 기능이 있어야한다.
5. 포사(forsimulation)의 목적으로 충돌 데이터가 표시되지 않을 수 있다. 충돌 형상이 해당 렌더링 형상보다 작은 경우 영구
메모리 공간은 그러므로 감소되었다.
6. 원래 기하학은 다각형 수프 또는 메쉬로 제공 될 수 있지만 시뮬레이션에는 솔리드 객체 표현이 필요하다. 이 경우 솔리드
프록시 지오메트리를 계산하는 것이 원래의 기하학적 표현을 어떻게든 고착시키는 것보다 훨씬 쉽다.
그러나 별도의 충돌 형상을 사용하면 몇 가지 잠재적인 단점이 있다.
1. 데이터 중복 제거(주로 정점)로 인해 추가 메모리가 사용된다. 이 문제는 선형 형상 캐싱을 사용해 렌더링 지오메트리에서
즉석에서 충돌 지오메트리의 일부 또는 전체를 생성해 완화할 수 있다.
2. 비슷한 형상의 두 세트를 생산하고 유지하려면 추가 작업이 필요할 수 있다. 수동으로 프록시 지오메트리를 작성하면
디자이너가 이를 작성하는 일정이 손상된다. 도구로 작성된 경우 충돌 시스템을 사용할 수 있게되기 전에 해당 도구를
작성해야한다. 또한, 도구 출력을 수동으로 수정해야하는 경우 변경 사항을 도구와 원본 데이터 세트로 다시 전달해야한다.
3. 별도로 빌드하고 유지 보수하는 경우 렌더링 및 충돌 형상이 위치에서 일치하지 않을 수 있다. 충돌 지오메트리가 렌더링
지오메트리와 동일한 볼륨을 채우지 않을 때, 객체는 다른 객체의 표면으로 부분적으로 사라지거나 부동하게 될 수 있다.
2.2.3 Collision Algorithm Specialization
하나의 포괄적인 충돌 감지 시스템을 갖추는 대신 특정 시나리오에 맞는 특수 충돌 시스템을 제공하는 것이 좋다.
전문화가 관련된 곳의 예는 입자 충돌이다. 보통의 충돌 시스템을 통해 입자를 하나씩 보내지 않고, 파티클들이 파티클 그룹으로
형성되고 충돌할 수 있도록 상황에 따라 더 잘 처리되고 제출된다. 충돌 부족이 눈에 띄지 않는 경우 입자가 충돌에서 제외될 수도 있다.
또 다른 예는 객체와 다른 객체 사이 및 객체와 장면 사이의 충돌을 탐지하는 벼도의 알고리즘을 사용하는 것이다.
object-object 충돌은 플레이어 캐릭터와 빠르게 움직이는 발사체가 다른 오브젝트와 다르게 처리되도록 더욱 전문화 될 수 있다.
예를 들어, 모든 오브젝트가 항상 플레이어 캐릭터와 충돌하는 경우는 일반 충돌 시스템에 플레이어 캐릭터를 삽입하는 대신
하드 코딩 테스트로 처리하는 것이 좋다.
거대 세계의 시뮬레이션도 고려해라. 작은 세계의 경우, 충돌 데이터는 항상 메모리에 유지 될 수 있다. 그러나 크고 매끄러운 세계의
경우, 충돌 데이터는 항상 메모리에 유지 될 수 있다. 그러나 크고 매끄러운 세계의 경우 충돌 데이터는 세계가 통과 할 때마다
로드되고 언로드되어야한다. 후자의 경우, 세계 구조와 분리된 객체를 갖는 것은 다시 매력적인 선택이므로 객체는 세계 구조의 변화에
영향을 받지 않는다. 개체와 세계를 보유하기위한 별도의 구조를 가질 때 발생할 수 있는 단점은 쿼리가 이제는 하나의 데이터 구조가 아닌
두 개의 데이터 구조를 통과한다는 것이다.