[논문]변형 물체를 위한 GPU 기반 병렬 충돌 감지

성낙준; 김민상; 홍민; 최유주

doi:10.3745/ktsde.2018.7.1.25

[국내논문] 변형 물체를 위한 GPU 기반 병렬 충돌 감지
GPU-Based Parallel Collision Detection for Deformable Objects 원문보기

정보처리학회논문지. KIPS transactions on software and data engineering. 소프트웨어 및 데이터 공학, v.7 no.1, 2018년, pp.25 - 32

성낙준 (순천향대학교 컴퓨터학과) , 김민상 (순천향대학교 컴퓨터학과) , 홍민 (순천향대학교 컴퓨터소프트웨어공학과) , 최유주 (서울미디어대학원대학교 뉴미디어학부)

초록
AI-Helper

변형물체 시뮬레이션은 강체 시뮬레이션에 비해 많은 연산량을 요구하기 때문에 효과적인 충돌 검사 방법을 필요하다. 그러나 CPU 기반의 충돌 검사 알고리즘을 그대로 GPU 환경에 적용할 경우 GPU의 성능을 제대로 사용할 수 없기 때문에 GPU 환경에 최적화된 충돌 감지 알고리즘과 자료구조가 필요하다. 따라서 본 연구에서는 변형 물체 표현을 위해 널리 사용되고 있는 질량-스프링 시스템을 위한 GPU 기반의 병렬 충돌 감지 알고리즘을 제안한다. 제안하는 방법은 AABB-옥트리 구조를 이용한 GPU 기반의 컬링 알고리즘을 통해 충돌 감지 비용을 줄이는 병렬 알고리즘과 자료 구조를 사용하였다. 본 연구에서는 모든 삼각형 쌍의 충돌을 병렬로 검사하는 기존 방법과의 비교실험을 통하여 제안 알고리즘의 효율성을 입증하였다. 실험결과, 제안된 방법은 기존의 방법에 비해서 평균 약 24%의 성능 개선을 보였다. 따라서 제안하는 방법을 통해서 변형 물체에 대한 실시간 시뮬레이션의 성능 개선이 가능할 것으로 기대한다.

Abstract ▼ AI-Helper

Due to heavy computational cost, deformable object simulation requires more effective collision detection method than rigid body simulation. However, when the CPU-based collision detection algorithm is purely applied to the GPU environment, the collision detection algorithm and the data structure optimized for the GPU environment are essential because the performance of the GPU can not be used properly. Therefore, we propose a GPU-based parallel collision detection algorithm for mass-spring system which is widely used for deformable object representation in this paper. The proposed method uses a parallel algorithm and data structure to reduce collision detection cost through GPU-based curling algorithm using AABB-Octree structure. In this paper, we prove the effectiveness of the proposed method by comparing the intersection test of all triangle pairs in parallel. The results of experimental tests show that the proposed method improves the performance by about 24% on average. Therefore, it is expected that the proposed method can improve the performance of real-time simulation for deformable objects.

Keyword

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

그러나 이러한 기법들도 GPU에 맞는 방식을 통해 수행되지 않으면 CPU방식보다 연산의 속도가 느리기 때문에, 최적화된 GPU 기반의 알고리즘의 구현이 필요한 상황이다. 따라서 본 연구에서는 GPU에 최적화된 충돌 감지 알고리즘과 더불어 변형 물체 시뮬레이션의 연산 속도 개선 방법에 관해 연구를 수행한다. 본 논문의 2장에서는 이와 관련된 연구들에 대한 논의를 수행하며, 3장에서는 GPU 기반 병렬 충돌 감지에 대한 알고리즘 설계 및 구현 결과에 관해 설명한다.
본 논문은 변형 물체 시뮬레이션의 성능 개선을 위한 GPU 기반 병렬 충돌 감지 알고리즘에 관한 연구 결과를 나타낸다. GPU의 성능이 상승함에 따라 더 높은 해상도의 변형 물체를 시뮬레이션 할 수 있으나, 이에 맞는 효과적인 병렬 알고리즘이 필요한 상황이다.
본 연구에서는 GPU 환경에 적합한 자료구조 설계 및 파이프라인 설계를 통해 1차 적인 성능 개선을 수행하였으며, 바운딩 박스를 활용한 GPU 기반 컬링 알고리즘의 설계를 통해 충돌 검사 연산의 속도를 향상시킬 수 있었다. 더욱이 본 연구를 통해 변형 객체의 움직임을 GPU 기반 병렬처리 기법으로 처리할 때, 병렬성을 높이기 위한 SSBO의 구성과 각 컴퓨트 쉐이더의 컴퓨트 스페이스 구성방법에 대하여 제시하였다. 추후 본 연구의 결과를 바탕으로 다양한 충돌 검사 연산에 적용을 통한 성능 개선이 가능할 것으로 예상한다.

제안 방법

이후 SSBO와 컴퓨트 쉐이더(Compute Shader)를 생성한다. 오브젝트는 복셀에 의한 충돌 컬링을 거친 후 충돌이 일어난 복셀에 저장된 서로 다른 오브젝트간의 삼각형 집합간의 충돌 검사를 수행한다. 그리고 각 오브젝트의 렌더링을 수행한다.
컴퓨트 쉐이더(0), (1), (2)는 충돌 검사에 관련된 연산을 수행하는 컴퓨트 쉐이더이며, 컴퓨트 쉐이더(3), (4), (5)는 질량-스프링 시스템을 구성하는데 사용되는 컴퓨트 쉐이더이다. 본 연구에서는 이러한 12개의 SSBO와 6개의 컴퓨트 쉐이더를 통해서 시뮬레이션 연산을 병렬로 수행한다. 또한 본 연구 에서는 복셀 계층 구조를 사용하기 위해서 k-트리의 일종인 옥트리(Octree : 8-Tree)를 사용한다.
본 연구에서는 이러한 12개의 SSBO와 6개의 컴퓨트 쉐이더를 통해서 시뮬레이션 연산을 병렬로 수행한다. 또한 본 연구 에서는 복셀 계층 구조를 사용하기 위해서 k-트리의 일종인 옥트리(Octree : 8-Tree)를 사용한다. 옥트리를 구성하는 정보는 AABB(Axis Aligned Bounding Box)를 사용하며, 전처리 과정에서 각 오브젝트의 바운딩 박스 정보를 초기화한다.
옥트리를 구성하는 정보는 AABB(Axis Aligned Bounding Box)를 사용하며, 전처리 과정에서 각 오브젝트의 바운딩 박스 정보를 초기화한다. 본 연구에서는 효과적인 복셀 기반 컬링을 수행하기 위해서 3-레벨 옥트리 구조를 사용하였으며, 해당 구조는 각 오브젝트마다 64개의 리프 노드(leaf node) 바운딩 박스를 가진다.
복셀 기반의 컬링을 수행하기 위해서 가장 먼저 BBUpdate 컴퓨트 쉐이더를 호출해 각 박스가 가지는 표면 삼각형을 순회하며 바운딩 박스의 Min, Max 데이터를 업데이트한다. 업데이트가 종료된 이후 BBCollision 컴퓨트 쉐이더의 호출을 통해 서로 다른 오브젝트간의 바운딩 박스끼리의 충돌 검사를 수행하며, 이때 컴퓨트 쉐이더는 AABB 대 AABB의 충돌 검사 알고리즘을 이용한다[14-16].
복셀 기반의 컬링을 수행하기 위해서 가장 먼저 BBUpdate 컴퓨트 쉐이더를 호출해 각 박스가 가지는 표면 삼각형을 순회하며 바운딩 박스의 Min, Max 데이터를 업데이트한다. 업데이트가 종료된 이후 BBCollision 컴퓨트 쉐이더의 호출을 통해 서로 다른 오브젝트간의 바운딩 박스끼리의 충돌 검사를 수행하며, 이때 컴퓨트 쉐이더는 AABB 대 AABB의 충돌 검사 알고리즘을 이용한다[14-16]. 각 컴퓨트 쉐이더의 의사 코드는 다음과 같다.
각 객체 별로 64개의 AABB 바운딩 박스를 3.2절에서 설명한 방법에 따라 정의하고, 객체간 모든 AABB 바운딩 박스의 쌍에 대한 충돌 검사를 BBCollision 컴퓨트 쉐이더에서 수행한 다. BBCollision 컴퓨트 쉐이더에서는 바운딩 박스간 충돌 검사의 결과를 Table 1의 (11)BoundingBox Mask SSBO에 저장한다.
즉, 두 객체의 충돌 감지를 위해 BBCollision 컴퓨트 쉐이더는 64 x 64 컴퓨트 공간(compute space)을 정의한다. 컴퓨트 쉐이더의 gl_GlobalInvocationID의 x와 y의 값을 통하여 충돌 감지를 수행할 바운딩 박스의 인덱스와 충돌감지 결과를 저장할 BoundingBox Mask SSBO의 인덱스를 계산한다. 이와 같은 인덱스 공식을 통해 동시에 모든 바운딩 박스 쌍에 대한 충돌 검사를 수행하고 그 결과를 BoundingBox Mask SSBO에 저장할 수 있다.
3절에서 객체간 충돌 검사 성능을 개선하기 위해 복셀 기반의 컬링 방법[17-19]을 사용하였다. 즉, 충돌이 발생한 바운딩 박스들이 포함하고 있는 삼각형들의 쌍만을 선별하여 삼각형-삼각형 충돌 검사를 수행한다. 삼각형 쌍의 충돌 검사를 수행하는 Table 2의 (2)Triangle-Triangle Intersection 컴퓨트 쉐이더는 전처리 단계에서 기 구축한 Table 1의 (9) BoundingBox Face List SSBO의 크기에 비례하여 워크 그룹을 구축한다.
본 연구에서 수행한 충돌 시뮬레이션은 초기에 두 물체 사이에 일정 거리를 두고 떨어져 있도록 위치시킨다. 이후 점차 상대 모델의 위치로 이동하며 교차하도록 설정하였다.
이후 점차 상대 모델의 위치로 이동하며 교차하도록 설정하였다. 각 실험에서는 매 프레임 마다 삼각형 교차 테스트를 병렬로 처리하는 일반적인 방법과 본 연구를 통해 제안한 방법을 이용해 동일한 상황을 시뮬레이션 하도록 한다. 이후 시뮬레이션에 소요되는 총 실행 시간을 측정해 일반적인 방법과 제안한 방법의 성능을 비교한다.
각 실험에서는 매 프레임 마다 삼각형 교차 테스트를 병렬로 처리하는 일반적인 방법과 본 연구를 통해 제안한 방법을 이용해 동일한 상황을 시뮬레이션 하도록 한다. 이후 시뮬레이션에 소요되는 총 실행 시간을 측정해 일반적인 방법과 제안한 방법의 성능을 비교한다. 다음 Fig.
각각의 실험은 Wire-Frame상태로 렌더링 하여 결과를 출력하였으며, 충돌이 나타날 경우 충돌이 일어난 표면 쌍의 색상을 변경하도록 구성하였다. 보다 정확한 시간 측정을 수행하기 위해 충돌 전, 충돌 상태, 충돌 후의 프레임을 각각 1,500프레임 정도 수행되도록 시스템을 설정하였다.
각각의 실험은 Wire-Frame상태로 렌더링 하여 결과를 출력하였으며, 충돌이 나타날 경우 충돌이 일어난 표면 쌍의 색상을 변경하도록 구성하였다. 보다 정확한 시간 측정을 수행하기 위해 충돌 전, 충돌 상태, 충돌 후의 프레임을 각각 1,500프레임 정도 수행되도록 시스템을 설정하였다.

대상 데이터

본 연구에서 수행한 실험의 환경은 다음 Table 3과 같다. 병렬 충돌 감지 방법의 실험을 수행한 GPU는 V-RAM 8GB를 제공하는 GTX1070 모델을 사용하였으며, GPGPU 파이프라인을 구성하기 위해 OpenGL4.3(GLSL 4.3)을 사용 하였다. 실험에 사용된 모델의 정보는 다음 Table 4와 같으며 모델들은 Tetgen을 통해 사면체 모델로 생성하였다.
3)을 사용 하였다. 실험에 사용된 모델의 정보는 다음 Table 4와 같으며 모델들은 Tetgen을 통해 사면체 모델로 생성하였다.

이론/모형

컴퓨트 쉐이더에서 효과적인 연산을 수행하기 위해 오브젝트의 부가적인 정보들을 SSBO[8]에 저장하여 사용한다. 다른 오브젝트간의 표면 삼각형 충돌 검사를 수행하기 위해서 복셀 기반 컬링의 결과를 저장하는 SSBO(11)과 표면 삼각형 쌍의 정보를 담는 SSBO(10)를 사용한다. 각 SSBO의 데이터를 활용해 병렬 연산을 수행하는 컴퓨트 쉐이더의 명세는 다음과 같다.
3.3절에서 객체간 충돌 검사 성능을 개선하기 위해 복셀 기반의 컬링 방법[17-19]을 사용하였다. 즉, 충돌이 발생한 바운딩 박스들이 포함하고 있는 삼각형들의 쌍만을 선별하여 삼각형-삼각형 충돌 검사를 수행한다.

성능/효과

충돌이 일어난 물체 1의 표면 색상을 color(1,0,0)로 칠하며, 물체 2의 표면 색상을 color(0,0,1)로 표현하였다. 이를 통해 본 시스템의 충돌 검사 연산이 원활하게 수행되고 있음을 가시적으로 확인 할 수 있었다.
실험의 결과 기존의 모든 삼각형 쌍의 교차 테스트를 병렬로 수행하는 일반적인 방법(Original Method)은 Phase 1 의 경우 평균 3.5384초, Phase 2의 경우 1.5643초의 수행 시간을 소모하였다. 그러나 본 연구를 통해 제안된 방법(Our Method)은 Phase 1의 경우 2.
5643초의 수행 시간을 소모하였다. 그러나 본 연구를 통해 제안된 방법(Our Method)은 Phase 1의 경우 2.8328초, Phase 2의 경우 1.2863초의 수행 시간을 소모하였다. 이는 모델의 크기가 작은 Phase 2에서 평균 21.
2863초의 수행 시간을 소모하였다. 이는 모델의 크기가 작은 Phase 2에서 평균 21.61%의 성능 개선을 가져왔으며, 모델의 크기가 큰 Phase 1에서 평균 24.9%의 성능 개선을 가져왔다. 이는 물체의 크기가 커질수록 더욱 효과적인 알고리즘임을 나타낸다.
GPU의 성능이 상승함에 따라 더 높은 해상도의 변형 물체를 시뮬레이션 할 수 있으나, 이에 맞는 효과적인 병렬 알고리즘이 필요한 상황이다. 본 연구에서는 GPU 환경에 적합한 자료구조 설계 및 파이프라인 설계를 통해 1차 적인 성능 개선을 수행하였으며, 바운딩 박스를 활용한 GPU 기반 컬링 알고리즘의 설계를 통해 충돌 검사 연산의 속도를 향상시킬 수 있었다. 더욱이 본 연구를 통해 변형 객체의 움직임을 GPU 기반 병렬처리 기법으로 처리할 때, 병렬성을 높이기 위한 SSBO의 구성과 각 컴퓨트 쉐이더의 컴퓨트 스페이스 구성방법에 대하여 제시하였다.

후속연구

더욱이 본 연구를 통해 변형 객체의 움직임을 GPU 기반 병렬처리 기법으로 처리할 때, 병렬성을 높이기 위한 SSBO의 구성과 각 컴퓨트 쉐이더의 컴퓨트 스페이스 구성방법에 대하여 제시하였다. 추후 본 연구의 결과를 바탕으로 다양한 충돌 검사 연산에 적용을 통한 성능 개선이 가능할 것으로 예상한다.

질의응답

핵심어	질문	논문에서 추출한 답변
	변형물체 시뮬레이션에서 효과적인 충돌 검사 방법이 필요한 이유는?	변형물체 시뮬레이션은 강체 시뮬레이션에 비해 많은 연산량을 요구하기 때문에 효과적인 충돌 검사 방법을 필요하다. 그러나 CPU 기반의 충돌 검사 알고리즘을 그대로 GPU 환경에 적용할 경우 GPU의 성능을 제대로 사용할 수 없기 때문에 GPU 환경에 최적화된 충돌 감지 알고리즘과 자료구조가 필요하다.
	GPU 환경에 최적화된 충돌 감지 알고리즘과 자료구조가 필요한 이유는?	변형물체 시뮬레이션은 강체 시뮬레이션에 비해 많은 연산량을 요구하기 때문에 효과적인 충돌 검사 방법을 필요하다. 그러나 CPU 기반의 충돌 검사 알고리즘을 그대로 GPU 환경에 적용할 경우 GPU의 성능을 제대로 사용할 수 없기 때문에 GPU 환경에 최적화된 충돌 감지 알고리즘과 자료구조가 필요하다. 따라서 본 연구에서는 변형 물체 표현을 위해 널리 사용되고 있는 질량-스프링 시스템을 위한 GPU 기반의 병렬 충돌 감지 알고리즘을 제안한다.
	질량-스프링 시스템을 위한 GPU 기반의 병렬 충돌 감지 알고리즘은 무엇을 사용하였나?	따라서 본 연구에서는 변형 물체 표현을 위해 널리 사용되고 있는 질량-스프링 시스템을 위한 GPU 기반의 병렬 충돌 감지 알고리즘을 제안한다. 제안하는 방법은 AABB-옥트리 구조를 이용한 GPU 기반의 컬링 알고리즘을 통해 충돌 감지 비용을 줄이는 병렬 알고리즘과 자료 구조를 사용하였다. 본 연구에서는 모든 삼각형 쌍의 충돌을 병렬로 검사하는 기존 방법과의 비교실험을 통하여 제안 알고리즘의 효율성을 입증하였다.

저자의 다른 논문 :

LOADING...

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증