“Interactive simulation of surgical needle insertion and steering” by Chentanez, Alterovitz, Ritchie, Cho, Hauser, et al. …

We present algorithms for simulating and visualizing the insertion and steering of needles through deformable tissues for surgical training and planning. Needle insertion is an essential component of many clinical procedures such as biopsies, injections, neurosurgery, and brachytherapy cancer treatment. The success of these procedures depends on accurate guidance of the needle tip to a clinical target while avoiding vital tissues. Needle insertion deforms body tissues, making accurate placement difficult. Our interactive needle insertion simulator models the coupling between a steerable needle and deformable tissue. We introduce (1) a novel algorithm for local remeshing that quickly enforces the conformity of a tetrahedral mesh to a curvilinear needle path, enabling accurate computation of contact forces, (2) an efficient method for coupling a 3D finite element simulation with a 1D inextensible rod with stick-slip friction, and (3) optimizations that reduce the computation time for physically based simulations. We can realistically and interactively simulate needle insertion into a prostate mesh of 13,375 tetrahedra and 2,763 vertices at a 25 Hz frame rate on an 8-core 3.0 GHz Intel Xeon PC. The simulation models prostate brachytherapy with needles of varying stiffness, steering needles around obstacles, and supports motion planning for robotic needle insertion. We evaluate the accuracy of the simulation by comparing against real-world experiments in which flexible, steerable needles were inserted into gel tissue phantoms.

1. Abolhassani, N., Patel, R. V., and Moallem, M. 2007. Needle insertion into soft tissue: A survey. Medical Engineering & Physics 29, 4 (May), 413–431.Google Scholar
2. Akima, H. 1970. A new method of interpolation and smooth curve fitting based on local procedures. J. ACM 17, 4 (Oct.), 589–602. Google ScholarDigital Library
3. Allard, J., Cotin, S., Faure, F., Bensoussan, P.-J., Poyer, F., Duriez, C., Delingette, H., and Grisoni, L. 2007. SOFA—An open source framework for medical simulation. In Medicine Meets Virtual Reality 15, IOS Press, 13–18.Google Scholar
4. Alterovitz, R., and Goldberg, K. 2008. Motion Planning in Medicine: Optimization and Simulation Algorithms for Image-Guided Procedures, vol. 50 of Springer Tracts in Advanced Robotics. Springer, Berlin, Germany. Google ScholarDigital Library
5. Alterovitz, R., Pouliot, J., Taschereau, R., Hsu, I.-C., and Goldberg, K. 2003. Simulating needle insertion and radioactive seed implantation for prostate brachytherapy. In Medicine Meets Virtual Reality 11, IOS Press, 19–25.Google Scholar
6. Alterovitz, R., Goldberg, K., and Okamura, A. M. 2005. Planning for steerable bevel-tip needle insertion through 2D soft tissue with obstacles. In IEEE International Conference on Robotics and Automation, 1652–1657.Google Scholar
7. Alterovitz, R., Siméon, T., and Goldberg, K. 2007. The stochastic motion roadmap: A sampling framework for planning with Markov motion uncertainty. In Robotics: Science and Systems III, 233–241.Google Scholar
8. Bargteil, A. W., Wojtan, C., Hodgins, J. K., and Turk, G. 2007. A finite element method for animating large viscoplastic flow. ACM Transactions on Graphics 26, 3 (July), 16:1–16:8. Google ScholarDigital Library
9. Bergou, M., Wardetzky, M., Robinson, S., Audoly, B., and Grinspun, E. 2008. Discrete elastic rods. ACM Transactions on Graphics 27, 3 (Aug.), 63:1–63:12. Google ScholarDigital Library
10. Bertails, F., Audoly, B., Cani, M.-P., Querleux, B., Leroy, F., and Lévêque, J.-L. 2006. Super-helices for predicting the dynamics of natural hair. ACM Transaction on Graphics 25, 3 (July), 1180–1187. Google ScholarDigital Library
11. Bertails, F. 2009. Linear time super-helices. Computer Graphics Forum 28, 2 (Apr.), 417–426.Google ScholarCross Ref
12. Cavusoglu, M. C., Göktekin, T. G., and Tendick, F. 2006. GiPSi: A framework for open source/open architecture software development for organ level surgical simulation. IEEE Transactions on Information Technology in Biomedicine 10, 2 (Apr.), 312–322. Google ScholarDigital Library
13. Crouch, J. R., Schneider, C. M., Wainer, J., and Okamura, A. M. 2005. A velocity-dependent model for needle insertion in soft tissue. In Medical Image Computing and Computer-Assisted Intervention, vol. 3749 of LNCS. Springer, Berlin, Oct., 624–632. Google ScholarDigital Library
14. Cuthill, E., and McKee, J. 1969. Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 24th National Conference, ACM, New York, 157–172. Google ScholarDigital Library
15. Debunne, G., Desbrun, M., Cani, M.-P., and Barr, A. 2000. Adaptive simulation of soft bodies in real-time. In Computer Animation 2000, 15–20. Google ScholarDigital Library
16. Dehghan, E., and Salcudean, S. E. 2007. Needle insertion point and orientation optimization in non-linear tissue with application to brachytherapy. In 2007 IEEE International Conference on Robotics and Automation, 2267–2272.Google Scholar
17. DiMaio, S. P., and Salcudean, S. E. 2005. Needle steering and motion planning in soft tissues. IEEE Transactions on Biomedical Engineering 52, 6 (June), 965–974.Google ScholarCross Ref
18. Gallagher, A. G., Ritter, E. M., Champion, H., Higgins, G., Fried, M. P., Moses, G., Smith, C. D., and Satava, R. M. 2005. Virtual reality simulation for the operating room: Proficiency-based training as a paradigm shift in surgical skills training. Annals of Surgery 241, 2 (Feb.), 364–372.Google ScholarCross Ref
19. Goksel, O., Salcudean, S. E., and DiMaio, S. P. 2006. 3D simulation of needle-tissue interaction with application to prostate brachytherapy. Computer Aided Surgery 11, 6 (Nov.), 279–288.Google ScholarCross Ref
20. Goktekin, T. G., Bargteil, A. W., and O’Brien, J. F. 2004. A method for animating viscoelastic fluids. ACM Transactions on Graphics 23, 3 (Aug.), 463–467. Google ScholarDigital Library
21. Grégoire, M., and Schömer, E. 2006. Interactive simulation of one-dimensional flexible parts. Proceedings of the 2006 Symposium on Solid and Physical Modeling, 95–103 (June). Google ScholarDigital Library
22. Hauser, K., Alterovitz, R., Chentanez, N., Okamura, A., and Goldberg, K. 2009. Feedback control for steering needles through 3D deformable tissue using helical paths. In Robotics: Science and Systems V.Google Scholar
23. Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the 2004 Symposium on Computer Animation, 131–140. Google ScholarDigital Library
24. Irving, G., Schroeder, C., and Fedkiw, R. 2007. Volume conserving finite element simulations of deformable models. ACM Transactions on Graphics 26, 3, 13:1–13:6. Google ScholarDigital Library
25. Karypis, G., and Kumar, V. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing 20, 1 (Aug.), 359–392. Google ScholarDigital Library
26. Klingner, B. M., and Shewchuk, J. R. 2007. Aggressive tetrahedral mesh improvement. In Proceedings of the 16th International Meshing Roundtable, 3–23.Google Scholar
27. Kohn, L. T., Corrigan, J. M., and Donaldson, M. S. 2000. To Err Is Human: Building a Safer Health System. New York: National Academy.Google Scholar
28. Krouskop, T. A., Wheeler, T. M., Kallel, F., Garria, B. S., and Hall, T. 1998. Elastic moduli of breast and prostate tissues under compression. Ultrasonic Imaging 20, 4 (Oct.), 260–274.Google ScholarCross Ref
29. Labelle, F., and Shewchuk, J. R. 2007. Isosurface stuffing: Fast tetrahedral meshes with good dihedral angles. ACM Transactions on Graphics 26, 3 (July), 57:1–57:10. Google ScholarDigital Library
30. Lindblad, A., and Turkiyyah, G. 2007. A physically-based framework for real-time haptic cutting and interaction with 3D continuum models. In Proceedings of the 2007 Symposium on Solid and Physical Modeling, ACM, New York, 421–429. Google ScholarDigital Library
31. Loock, A., and Schömer, E. 2001. A virtual environment for interactive assembly simulation: From rigid bodies to deformable cables. In 5th World Multiconference on Systemics, Cybernetics and Informatics, 325–332.Google Scholar
32. Marchal, M., Promayon, E., and Troccaz, J. 2006. Simulating prostate surgical procedures with a discrete soft tissue model. In Third Eurographics Workshop in Virtual Reality Interactions and Physical Simulations, 109–118.Google Scholar
33. Marcia, R. F. 2008. On solving sparse symmetric linear systems whose definiteness is unknown. Applied Numerical Mathematics 58, 4 (Apr.), 449–458. Google ScholarDigital Library
34. Mendoza, C., and Laugier, C. 2003. Simulating soft tissue cutting using finite element models. In 2003 IEEE International Conference on Robotics and Automation, 1109–1114.Google Scholar
35. Müller, M., and Gross, M. H. 2004. Interactive virtual materials. In Graphics Interface 2004, 239–246. Google ScholarDigital Library
36. Müller, M., Dorsey, J., McMillan, L., Jagnow, R., and Cutler, B. 2002. Stable real-time deformations. In Proceedings of the 2002 Symposium on Computer Animation, ACM, New York, 49–54. Google ScholarDigital Library
37. Nienhuys, H.-W., and van der Stappen, A. F. 2001. A surgery simulation supporting cuts and finite element deformation. In Medical Image Computing and Computer-Assisted Intervention, 4th International Conference, 153–160. Google ScholarDigital Library
38. Nienhuys, H.-W., and van der Stappen, A. 2004. A computational technique for interactive needle insertions in 3D nonlinear material. In IEEE International Conference on Robotics and Automation, vol. 2, 2061–2067.Google Scholar
39. O’Brien, J. F., and Hodgins, J. K. 1999. Graphical modeling and animation of brittle fracture. In Computer Graphics (SIGGRAPH ’99 Proceedings), ACM Press, New York, 137–146. Google ScholarDigital Library
40. O’Brien, J. F., Bargteil, A. W., and Hodgins, J. K. 2002. Graphical modeling and animation of ductile fracture. In Computer Graphics (SIGGRAPH 2002 Proceedings), 291–294. Google ScholarDigital Library
41. Pai, D. K. 2002. STRANDS: Interactive simulation of thin solids using Cosserat models. Computer Graphics Forum 21, 3 (Sept.), 347–352.Google ScholarCross Ref
42. Paige, C. C., and Saunders, M. A. 1975. Solution of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis 12, 4 (Sept.), 617–629.Google ScholarCross Ref
43. Parthasarathy, V. N., Graichen, C. M., and Hathaway, A. F. 1994. A comparison of tetrahedron quality measures. Finite Elements in Analysis and Design 15, 3 (Jan.), 255–261. Google ScholarDigital Library
44. Picinbono, G., Delingette, H., and Ayache, N. 2003. Non-linear anisotropic elasticity for real-time surgery simulation. Graphical Models 65, 5 (Sept.), 305–321. Google ScholarDigital Library
45. Reed, K. B., Kallem, V., Alterovitz, R., Goldberg, K., Okamura, A. M., and Cowan, N. J. 2008. Integrated planning and image-guided control for planar needle steering. In Proceedings of the Second IEEE/RAS-EMBS International Conference on Biomedical Robotics and Biomechatronics, 819–824.Google Scholar
46. Satava, R. M. 2005. Identification and reduction of surgical error using simulation. Minimally Invasive Therapy & Allied Technologies 14, 4–5 (Sept.), 257–261.Google Scholar
47. Seymour, N. E., Gallagher, A. G., Roman, S. A., O’Brien, M. K., Bansal, V. K., Andersen, D. K., and Satava, R. M. 2002. Virtual reality training improves operating room performance: Results of a randomized, double-blinded study. Annals of Surgery 236, 4 (Oct.), 458–463.Google ScholarCross Ref
48. Sifakis, E., Shinar, T., Irving, G., and Fedkiw, R. 2007. Hybrid simulation of deformable solids. In Proceedings of the 2007 Symposium on Computer Animation, 81–90. Google ScholarDigital Library
49. Simone, C., and Okamura, A. M. 2002. Modeling of needle insertion forces for robot-assisted percutaneous therapy. In IEEE International Conference on Robotics and Automation, 2085–2091.Google Scholar
50. Spillmann, J., and Teschner, M. 2007. CORDE: Cosserat rod elements for the dynamic simulation of one-dimensional elastic objects. In Proceedings of the 2007 Symposium on Computer Animation, Eurographics Association, 63–72. Google ScholarDigital Library
51. Spillmann, J., and Teschner, M. 2008. An adaptive contact model for the robust simulation of knots. Computer Graphics Forum 27, 2 (April), 497–506.Google ScholarCross Ref
52. Taschereau, R., Pouliot, J., Roy, J., and Tremblay, D. 2000. Seed misplacement and stabilizing needles in transperineal permanent prostate implants. Radiotherapy and Oncology 55, 1 (Apr.), 59–63.Google ScholarCross Ref
53. Taylor, R. H. 2006. A perspective on medical robotics. Proceedings of the IEEE 94, 9 (Sept.), 1652–1664.Google ScholarCross Ref
54. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In Computer Graphics (SIGGRAPH ’87 Proceedings), 205–214. Google ScholarDigital Library
55. Vidal, F. P., John, N. W., Healey, A. E., and Gould, D. A. 2008. Simulation of ultrasound guided needle puncture using patient specific data with 3D textures and volume haptics. Computer Animation and Virtual Worlds 19, 2 (May), 111–127. Google ScholarDigital Library
56. Wang, X., and Fenster, A. 2004. A virtual reality based 3D real-time interactive brachytherapy simulation of needle insertion and seed implantation. In 2004 IEEE International Symposium on Biomedical Imaging, 280–283.Google Scholar
57. Webster III, R. J., Memisevic, J., and Okamura, A. M. 2005. Design considerations for robotic needle steering. In 2005 IEEE International Conference on Robotics and Automation, 3588–3594.Google Scholar
58. Webster III, R. J., Okamura, A. M., Cowan, N. J., Chirikjian, G. S., Goldberg, K., and Alterovitz, R., 2005. Distal bevel-tip needle control device and algorithm. U.S. patent application number 11/436, 995, May.Google Scholar
59. Webster III, R. J., Kim, J. S., Cowan, N. J., Chirikjian, G. S., and Okamura, A. M. 2006. Nonholonomic modeling of needle steering. Int. Journal of Robotics Research 25, 5–6 (May), 509–525. Google ScholarDigital Library
60. Wojtan, C., and Turk, G. 2008. Fast viscoelastic behavior with thin features. ACM Transactions on Graphics 27, 3 (Aug.), 47:1–47:8. Google ScholarDigital Library