title: CPU-GPU mixed implementation of virtual node method for real-time interactive cutting of deformable objects using OpenCL.
abstract: OBJECTIVE
  Surgical simulators need to simulate interactive cutting of deformable objects in real time. The goal of this work was to design an interactive cutting algorithm that eliminates traditional cutting state classification and can work simultaneously with real-time GPU-accelerated deformation without affecting its numerical stability.
  
  
  METHODS
  A modified virtual node method for cutting is proposed. Deformable object is modeled as a real tetrahedral mesh embedded in a virtual tetrahedral mesh, and the former is used for graphics rendering and collision, while the latter is used for deformation. Cutting algorithm first subdivides real tetrahedrons to eliminate all face and edge intersections, then splits faces, edges and vertices along cutting tool trajectory to form cut surfaces. Next virtual tetrahedrons containing more than one connected real tetrahedral fragments are duplicated, and connectivity between virtual tetrahedrons is updated. Finally, embedding relationship between real and virtual tetrahedral meshes is updated. Co-rotational linear finite element method is used for deformation. Cutting and collision are processed by CPU, while deformation is carried out by GPU using OpenCL.
  
  
  RESULTS
  Efficiency of GPU-accelerated deformation algorithm was tested using block models with varying numbers of tetrahedrons. Effectiveness of our cutting algorithm under multiple cuts and self-intersecting cuts was tested using a block model and a cylinder model. Cutting of a more complex liver model was performed, and detailed performance characteristics of cutting, deformation and collision were measured and analyzed.
  
  
  CONCLUSIONS
  Our cutting algorithm can produce continuous cut surfaces when traditional minimal element creation algorithm fails. Our GPU-accelerated deformation algorithm remains stable with constant time step under multiple arbitrary cuts and works on both NVIDIA and AMD GPUs. GPU-CPU speed ratio can be as high as 10 for models with 80,000 tetrahedrons. Forty to sixty percent real-time performance and 100-200 Hz simulation rate are achieved for the liver model with 3,101 tetrahedrons. Major bottlenecks for simulation efficiency are cutting, collision processing and CPU-GPU data transfer. Future work needs to improve on these areas.
authors.affiliation: College of Information Engineering, Qingdao University, Qingdao, 266071, Shandong, People's Republic of China, shiyujia-qdu@qq.com.
authors.forename: Shiyu
authors.initials: S
authors.lastname: Jia
authors.forename: Weizhong
authors.initials: W
authors.lastname: Zhang
authors.forename: Xiaokang
authors.initials: X
authors.lastname: Yu
authors.forename: Zhenkuan
authors.initials: Z
authors.lastname: Pan
mesh_terms: D000465:Algorithms; D003196:Computer Graphics; D003198:Computer Simulation; D004548:Elasticity; D020342:Finite Element Analysis; D013502:General Surgery / Q000193:education*; D006801:Humans; D008099:Liver / Q000601:surgery*; D008962:Models, Theoretical; D012984:Software; D014584:User-Computer Interface; D014783:Viscosity