Simulating realistic fractures in deforming models is one of the main challenges in computer animation, sculpting in CAD, virtual surgery, etc. Simulating such complex phenomena requires collision detection methods to avoid any inter-collisions among deforming models and self-collisions within each deforming model. Moreover, fractures change the mesh connectivity , in addition to changing the geometry. Also, at a fracture or merge event, multiple parts of the same object can appear in a close proximity, causing a higher computation time for collision detection. As a result, collision detection including self-collision detection is typically the main computational bottleneck of simulating these complex phenomena.
In this thesis, we present a collision detection method for complex and large-scale fracturing models that have geometric and topological changes. We first propose a novel dual-cone culling method to improve the performance of collision detection, especially self-collision detection among fracturing models. Our dual-cone culling method has a small computational overhead and a conservative algorithm. Combined with bounding volume hierarchies (BVHs), our dual-cone culling method becomes approximate. However, we found that our method does not miss any collisions in the tested benchmarks. We also propose a novel, selective restructuring method that improves the overall performance of collision detection and reduces performance degradations at fracturing events. Our restructuring method is based on a culling efficiency metric that measures the expected number of overlap tests of a BVH. To further reduce the performance degradations at fracturing events, we also propose a novel, fast BVH construction method that builds multiple levels of the hierarchy in one iteration using a grid and hashing. We test our method with four different large-scale deforming benchmarks. Compared to the state-of-the-art methods, our method shows a more stable performance for collision detection by improving the performance by a factor of up to two orders of magnitude at frames when deforming models change their mesh topologies.
찢어지거나 깨지는 물체의 현실적인 시뮬레이션은 컴퓨터 시뮬레이션 분야의 도전적인 과제이다. 이런 복잡한 현상의 시뮬레이션에서 물체간의 충돌과 물체 내에서의 충돌의 탐지 방법은 필수적인 요소이다. 나아가, 깨짐이나 찢어짐은 메시로 표현된 삼차원 물체의 모양 뿐만 아니라 그 연결성까지도 변화시킨다. 그리고 깨진 이후의 물체 조각들은 일반적으로 가깝게 위치하게 되고, 이는 충돌 검출에 소요되는 시간을 증가시킨다. 이런 이유로 물체 내 충돌을 포함한 충돌 검출 기법은 복잡한 현상의 시뮬레이션에서 병목 현상을 초래한다.
본 학위 논문에서는, 모양과 연결성이 바뀔 수 있는 물체, 즉 깨지거나 찢어지는 물체에 대한 효율적인 충돌검출 기법을 소개한다. 우리는 먼저 물체 내 충돌 검출에서 사용되는 새로운 컬링 기법인 dual-cone 방법을 제안한다. dual-cone 방법은 효율적으로 물체 내 충돌이 없는 지점을 찾아내는 방법이다. 바운딩 볼륨 계층구조 (bounding volume hierarchy, BVH)와 결합된 dual-cone 방법은 이론적으로 근사적 방법이 되지만, 실험적 결과로 충돌을 놓치지 않음을 보였다. 두 번째로, 우리는 새로운 BVH의 선택적 재구성 (selective restructuring) 방법을 제안한다. 이 BVH 재구성 방법은 충돌 검출의 전체적인 성능을 향상 시킬 뿐 아니라, 물체가 깨지거나 찢어지는 것과 같은 연결성이 붕괴 될 때 발생하는 큰 성능 저하를 줄인다. 이 BVH 재구성 방법은 예상 겹침 검사 (expected overlap test) 의 횟수로 정의되는 새로운 컬링 효율성 메트릭 (culling efficiency metric) 을 기반으로 한다. BVH를 재구성 할 때의 성능 하락을 방지하기 위해서 우리는 격자와 해싱 (grid and hashing) 을 이용한 빠른 BVH 구성 방법을 제안한다. 본 방법은 4개의 실험 환경에서 실험되었으며, 현재 세계적으로 가장 뛰어난 기술과 비교하여서 깨짐이나 찢어짐이 있을 때, 200배 이상의 성능 향상을 보인다.
