For many years, collision detection has been of one of major issues in computer graphics. Various approaches have been developed to detect interpenetration between object. Especially, Collision detection of deformable object is an essential component in interactive physically-based simulation which is a rapidly growing research area. One of the major simulations for collision detection is surgery simulation. In such environments, collisions among deformable organs have to be detected and resolved. Furthermore, collisions between surgical tools and deformable tissue have to be processed fast with high accuracy. Since interactive behavior of surgery simulation environments is essential, efficient algorithms for deformable collision detection are required.
Distance field is one of efficient methods to detect collision between objects in simulation. The distance field is defined as 3D uniform grid where each grid point has the signed shortest distance from the surface of an object within the distance field. The sign of the shortest surface distance of a grid point denotes whether the grid point is inside or outside the object. In addition, it is possible to compute the shortest surface distance of any point within the distance field by using interpolation of grid points’ shortest surface distance. Therefore, when an object comes inside another object’s distance field, the distance field fast computes the distance between them and detects collision. Although distance field provides highly robust collision detection, its update is not fast enough for interactive simulation because the shortest surface distance of all grid point are recomputed.
In this paper, we present an approach to detect collision of deformable object based on grid cells of distance field. The approach allows using distance field for collision detection of deformable object by developing a method to update distance field during run time. The approach first defines each grid cell as one of boundary cell, interior cell, and exterior cell based on the distance from the surface. By using the type of grid cell instead of shortest surface distance of grid point, we develop a fast method to detect the collision between objects. In addition, because it is enough to update the type of grid cell only, the update of distance field is fast enough during run time.
The proposed approach is applied to Cholecystectomy simulation which is one of common surgeries. Also, the approach is compared with well-spread collision detection model, namely Bounding Volume Hierarchies.
물체 간의 충돌 검사는 지난 수십 년부터 컴퓨터 그래픽스 분야에서 가장 중요하게 여겨지는 문제 중 하나이다. 이에 따라 물체들 사이의 충돌을 빠르고 정확하게 계산하기 위한 많은 연구들이 진행되었다. 특히, 변형체의 충돌 검사는 물리 환경 및 사용자와의 상호 작용을 반영하는 시뮬레이션에서 중요하게 여겨지고 있다. 이러한 시뮬레이션 중 하나는 수술 시뮬레이션이다. 해당 시뮬레이션에서는 변형하는 인체 장기와 수술 도구 사이의 충돌 검사뿐만 아니라 인체 장기들 사이의 충돌 검사가 빠르고 정확하게 계산되어야 한다.
이렇듯 현재 개발 및 사용되는 시뮬레이션에서 변형체의 상호 작용이 중요하게 여겨지고 때문에, 변형체들의 충돌 검사를 위한 효율적인 알고리즘의 중요성이 대두되고 있다. 거리 영역(Distance Field)은 물체들 사이의 충돌 여부를 빠르게 계산할 수 있는 효율적인 방법 중 하나이다. 거리 영역은 3차원 균일 격자로 정의되고, 각 격자 점은 해당 격자 안에 포함되어 있는 물체와의 최소 거리 값을 저장하고 있다. 또한, 각 격자 점의 최소 표면거리 값은 부호를 가지고 있는데, 물체의 내부에 있는 격자 점은 음수인 최소 표면거리 값을 가지고, 반대의 경우 양수인 최소 표면거리 값을 갖는다. 이러한 격자 점이 가진 최소 표면거리 값을 보간하여 해당 격자 안의 모든 점에 대한 최소 표면거리 값을 계산한다. 따라서, 한 물체가 다른 물체의 거리 영역 안으로 들어올 경우, 거리 영역은 해당하는 두 물체 사이의 최소 거리 값을 빠르게 계산하고 충돌 여부를 검사할 수 있다. 비록 거리 영역이 충돌 여부를 빠르게 계산할 수 있지만, 물체가 변형할 경우 이를 반영하기 위한 거리 영역의 업데이트는 매우 느리다는 단점이 있다. 이는 해당 격자 안의 모든 격자 점이 가진 최소 표면거리 값을 업데이트해야 하기 때문이다.
본 논문에서는 거리 영역의 격자 셀을 이용한 변형체의 실시간 충돌 검사 방법을 제안한다. 이 방법은 거리 영역의 장점을 유지하면서도 업데이트 성능을 향상시킨다. 이를 위해서 제안한 방법은 먼저 격자 셀을 표면과의 거리에 따라 표면 셀, 내부 셀, 외부 셀의 세 가지 영역으로 구분한다. 이러한 격자 셀의 위치 정보를 바탕으로 변형체의 충돌 여부를 빠르게 검사한다. 또한, 격자 셀의 위치 정보만을 빠르게 업데이트함으로써 기존의 거리 영역 업데이트에 비해 비약적으로 빠른 업데이트 결과를 가진다.
본 논문에서는 이러한 제안 방법을 이용하여 실제 수술 시뮬레이션 중 하나인 담낭 절제 수술을 구현하였을 뿐만 아니라 변형체의 충돌 검사를 위해 기존에 사용되었던 충돌 검사 방법과 비교하였다. 이를 통하여 제안한 방법의 기여 방안 및 장단점을 분석하였다.
