Electrical and Computer Engineering Publications
Parallelized collision detection with applications in virtual bone machining
Document Type
Article
Publication Date
5-1-2020
Volume
188
Journal
Computer Methods and Programs in Biomedicine
URL with Digital Object Identifier
10.1016/j.cmpb.2019.105263
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 10243 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.