상호충돌검사 기반 병렬충돌검사 방법 및 컴퓨터 판독가능 매체

Abstract

본 발명은 영상처리에 관한 것으로서, 보다 구체적으로는 영상에서 물체의 충돌 감지를 위한 태스크 분배 방법에 관한 것이다. 본 발명에 따른 충돌 검출 방법은 컴퓨터 시스템에서 수행되는 씬(scene)에 포함된 물체 사이의 충돌을 검출하기 위한 방법으로서, 각 물체들의 기하학적 정보에 기초하여 각 물체들에 대한 바운딩 볼륨 체계(bounding volume hierarchies, BVH)를 생성하는 단계, 각 물체들의 BVH들에 기초한 메인 BVH를 생성하는 단계, 메인 BVH에서 상호 무관성이 성립하는 노드들을 루트로 하는 복수의 서브트리를 추출하는 단계, 복수의 서브트리에 구성된 노드들을 복수의 스레드(thread)에 각각 분배하는 단계, 및 복수의 서브트리에 구성된 노드들을 자식 노드로 하는 부모 노드에 대한 물체 간 충돌검사를 수행하기 위하여, 복수의 서브트리에 구성된 노드 쌍의 집합인 ICTPS(inter collision test pair set)를 생성하는 단계를 포함한다. BVH, BV, CCD, HPCCD, 충돌 검사, ICT(inter collision test)