Parallelized collision detection with applications in virtual bone machining. (May 2020)

• Record Type: Journal Article
• Authors: Faieghi, Mohammadreza; Tutunea-Fatan, O. Remus; Eagleson, Roy
• Is Part Of: Computer methods and programs in biomedicine. Volume 188(2020)
• Publication Date: 2020-05
• Subjects: Collision detection -- Haptics -- Virtual reality -- Surgery simulation -- Orthopedic procedures; Medicine -- Computer programs -- Periodicals; Biology -- Computer programs -- Periodicals; Computers -- Periodicals; Medicine -- Periodicals; Médecine -- Logiciels -- Périodiques; Biologie -- Logiciels -- Périodiques; Biology -- Computer programs; Medicine -- Computer programs; Periodicals; Electronic journals; 610.28
• DOI: 10.1016/j.cmpb.2019.105263
• Languages: English
• ISSNs: 0169-2607

Abstract

Highlights: A new data-parallel variant of the voxmap point shell method has been developed for real-time collision detection and subsequent material removal. The use of a simple contiguous array coupled with an invertible 3D to 1D mapping leads to an implicit definition of voxmap that enables a fast access to voxels and efficient material removal without significant memory overheads. The rapid estimation of possible intersection volume enables an early cull of unnecessary threads and thereby significantly speeds up the developed algorithm, especially when involved in peripheral collision scenarios. The algorithm is characterized by a low sensitivity to voxmap resolution, thus enabling collision detection on voxel sets that could be as large as the available computing memory. Abstract: Background and objectives: Virtual reality surgery simulators have been proved effective for training in several surgical disciplines. Nevertheless, this technology is presently underutilized in orthopaedics, especially for bone machining procedures, due to the limited realism in haptic simulation of bone interactions. Collision detection is an integral part of surgery simulators and its accuracy and computational efficiency play a determinant role on the fidelity of simulations. To address this, the primary objective of this study was to develop a new algorithm that enables faster and more accurate collision detection within 1 ms (required for stable haptic rendering) in order to facilitate the improvement of the realism of virtual bone machining procedures. Methods: The core of the developed algorithm is constituted by voxmap point shell method according to which tool and osseous tissue geometries were sampled by points and voxels, respectively. The algorithm projects tool sampling points into the voxmap coordinates and compute an intersection condition for each point-voxel pair. This step is massively parallelized using Graphical Processing Units and it is further accelerated by an early culling of the unnecessary threads as instructed by the rapid estimation of the possible intersection volume. A contiguous array was used for implicit definition of voxmap in order to guarantee a fast access to voxels and thereby enable efficient material removal. A sparse representation of tool points was employed for efficient memory reductions. The effectiveness of the algorithm was evaluated at various bone sampling resolutions and was compared with prior relevant implementations. Results: The results obtained with an average hardware configuration have indicated that the developed algorithm is capable to reliably maintain < 1 ms running time in severe tool-bone collisions, both sampled at 1024 3 resolutions. The results also showed the algorithm running time has a low sensitivity to bone sampling resolution. The comparisons performed suggested that the proposed approach is significantly faster than comparable methods while relying on lower or similar memory requirements. Conclusions: The algorithm proposed through this study enables a higher numerical efficiency and is capable to significantly enlarge the maximum resolution that can be used by high fidelity/high realism haptic simulators targeting surgical orthopaedic procedures.