메쉬 간략화를 이용한 충돌검출 알고리즘 개발

국문 초록 (Abstract)

본 논문에서는 가상물체의 메쉬 단순화 알고리즘을 사용하는 그룹화 과정을 통해 빠르고 정확하게 충돌을 검출하기 위한 새로운 방법을 제안하였다. 그룹화는 많은 개수의 메쉬들을 가진 가상물체를 보다 적은 개수의 메쉬들을 가지는 작은 물체 부분들의 집합으로 나눔으로써 충돌검출에서 메쉬 검색을 보다 신속하고 용이하게 하기 위한 과정이다. 본 논문에서는 가상물체의 메쉬들을 간략화 면을 기반으로 하여 그룹화하고, 이를 바탕으로 바운딩 박스를 납작한 삼각기둥 형태로 생성하여 불필요한 공간을 최대한 없애 충돌 검출 성능을 향상시켰다.
햅틱에서의 충돌검출 시에는 햅틱장치의 제어점을 나타내는 HIP(Haptic Interface Point)가 충돌한 면을 찾기 위해 모든 면을 탐색해야 한다. 제시된 알고리즘을 적용하면 간략화한 각각의 큰 삼각형 메쉬에 속하는 원본 메쉬들을 그룹화하여 포함하는 납작한 삼각기둥의 바운딩 박스들을 먼저 검색하고, 만약 충돌이 일어난 것으로 검색된 바운딩 박스가 있으면 그에 속한 원본 메쉬들을 활성화하여 실제 충돌이 일어난 원본 메쉬를 찾는다. 본 논문에서는 기존 연구에서 제시되었던 구형의 바운딩 박스를 사용하는 경우와 형태를 비교하여 정밀도의 차이를 확인하였으며, 또한 시뮬레이션을 통해 그룹화 개수에 따른 충돌검출 속도를 비교하였다.

다국어 초록 (Multilingual Abstract)

In this paper, we propose a new collision detecting method which provides improved accuracy and speed through a grouping process of a virtual object via mesh simplification algorithm. Mesh grouping is a process of dividing a virtual object having large number of meshes into a set of small fragments. This process allows rapid and simple collision detection. This paper presents a unique method that will detect collision with speed and accuracy by taking advantage of grouping process using the mesh simplification algoritm of a virtual object. Based on this approach, we have enhanced the performance by generating the bounding box as a flat triangular box.
During collision detecting period in haptics loop, we should find the collision point of the HIP(Haptic Interface Point) among all the meshes of the virtual object. Applying the proposed algorithm, it first searches bounding boxes each of which include original meshes group belonging to each simplified triangle mesh. If there's a collision of HIP on the bounding box, the meshes in the group belonging to the bounding box are activated and the original mesh that the actual crash happened is searched and founded. By comparing the shapes of the proposed bounding boxes with sphere shape ones, we could find easily the differences of the two in accuracy. By computer simulation, it was shown that the collision detection algorithm is working well and is efficient in computing time.

목차 (Table of Contents)

• 논문 목차
• Ⅰ. 서 론 1
• Ⅱ. 관련 이론 및 기존 연구 3
• 2.1 햅틱 렌더링 3
• 2.2 충돌검출 3
• Ⅲ. 메쉬 간략화를 이용한 충돌검출 알고리즘 7
• 3.1 알고리즘의 개요 7
• 3.2 초기화 과정 8
• 3.3 충돌검출 구현 21
• 3.3.1 바운딩 박스에 HIP 침투 여부 판정 22
• 3.3.2 그룹 내의 메쉬 검색 과정 23
• Ⅳ. 알고리즘 수행 환경 및 결과 24
• 4.1 수행환경 24
• 4.1.1 PHANTom Omni 25
• 4.1.2 OpenHaptics Toolkit 25
• 4.1.3 OpenGL 25
• 4.1.4 OpenMesh 26
• 4.2 수행결과 26
• Ⅴ. 결론 32
• 참고문헌 34
• 영문요약 36