Haptic Collision Detection on Highly Complex Medical Data Structures

Abstract

Nowadays, the planning procedure for orthognathic surgery consists of a manual workflow which relies on cost and time consuming tasks. The burden that this procedure has on the surgeon and the medical staff can be reduced by substituting the current procedure with a digital workflow. In the novel workflow the surgeon uses a haptic feedback device to mimic the haptic information perceived from the manual procedure. However, highly complex 3D medical scan models of the upper and lower jaw are needed to reproduce a realistic feeling. These complex models stress the need for an efficient collision detection algorithm to obtain the necessary update rate of at least 1 kHz for haptic feedback devices. In this paper the potential of the Inner Sphere Tree (IST) data structure is analyzed for application in the orthognathic surgery digital planning workflow. An open-source C++ program is developed on the CHAI3D platform for the implementation and evaluation of the IST. For the evaluation, the detection speed, but also the accuracy of the collision detection, in terms of the error introduced by the proximity of the minimum distance between bounding volume hierarchies (BVHs), are taken into consideration. Various tree traversal algorithms, distance and backtracking, are implemented and evaluated. Finally, a multi-point tree traversal algorithm is developed to find multiple contact-points between two ISTs. Due to the added optimizations and by using these tree traversal algorithms, the required update speed is reached.