Interactive simulation of surgical needle insertion and steering

ABSTRACT

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.

REFERENCES

• 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.
• 2: Hiroshi Akima, A New Method of Interpolation and Smooth Curve Fitting Based on Local Procedures, Journal of the ACM (JACM), v.17 n.4, p.589-602, Oct. 1970 [doi>10.1145/321607.321609]
• 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.
• 4: Ron Alterovitz , Ken Goldberg, Motion Planning in Medicine: Optimization and Simulation Algorithms for Image-Guided Procedures, Springer Publishing Company, Incorporated, 2008
• 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.
• 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.
• 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.
• 8: Adam W. Bargteil , Chris Wojtan , Jessica K. Hodgins , Greg Turk, A finite element method for animating large viscoplastic flow, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 9: Miklós Bergou , Max Wardetzky , Stephen Robinson , Basile Audoly , Eitan Grinspun, Discrete elastic rods, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 10: Florence Bertails , Basile Audoly , Marie-Paule Cani , Bernard Querleux , Frédéric Leroy , Jean-Luc Lévêque, Super-helices for predicting the dynamics of natural hair, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 11: Bertails, F. 2009. Linear time super-helices. Computer Graphics Forum 28, 2 (Apr.), 417--426.
• 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.
• 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.
• 14: E. Cuthill , J. McKee, Reducing the bandwidth of sparse symmetric matrices, Proceedings of the 1969 24th national conference, p.157-172, August 26-28, 1969 [doi>10.1145/800195.805928]
• 15: Gilles Debunne , Marie-Paule Cani , Mathieu Desbrun , Alan Barr, Adaptive Simulation of Soft Bodies in Real-Time, Proceedings of the Computer Animation, p.15, May 03-05, 2000
• 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.
• 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.
• 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.
• 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.
• 20: Tolga G. Goktekin , Adam W. Bargteil , James F. O'Brien, A method for animating viscoelastic fluids, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 21: Mireille Grégoire , Elmar Schömer, Interactive simulation of one-dimensional flexible parts, Proceedings of the 2006 ACM symposium on Solid and physical modeling, June 06-08, 2006, Cardiff, Wales, United Kingdom [doi>10.1145/1128888.1128902]
• 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.
• 23: G. Irving , J. Teran , R. Fedkiw, Invertible finite elements for robust simulation of large deformation, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028541]
• 24: Geoffrey Irving , Craig Schroeder , Ronald Fedkiw, Volume conserving finite element simulations of deformable models, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 25: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 26: Klingner, B. M., and Shewchuk, J. R. 2007. Aggressive tetrahedral mesh improvement. In Proceedings of the 16th International Meshing Roundtable, 3--23.
• 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.
• 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.
• 29: François Labelle , Jonathan Richard Shewchuk, Isosurface stuffing: fast tetrahedral meshes with good dihedral angles, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 30: Alex Lindblad , George Turkiyyah, A physically-based framework for real-time haptic cutting and interaction with 3D continuum models, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China [doi>10.1145/1236246.1236307]
• 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.
• 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.
• 33: Roummel F. Marcia, On solving sparse symmetric linear systems whose definiteness is unknown, Applied Numerical Mathematics, v.58 n.4, p.449-458, April, 2008 [doi>10.1016/j.apnum.2007.01.014]
• 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.
• 35: Matthias Müller , Markus Gross, Interactive virtual materials, Proceedings of Graphics Interface 2004, p.239-246, May 17-19, 2004, London, Ontario, Canada
• 36: Matthias Müller , Julie Dorsey , Leonard McMillan , Robert Jagnow , Barbara Cutler, Stable real-time deformations, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545269]
• 37: Han-Wen Nienhuys , A. Frank van der Stappen, A Surgery Simulation Supporting Cuts and Finite Element Deformation, Proceedings of the 4th International Conference on Medical Image Computing and Computer-Assisted Intervention, p.145-152, October 14-17, 2001
• 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.
• 39: James F. O'Brien , Jessica K. Hodgins, Graphical modeling and animation of brittle fracture, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.137-146, July 1999 [doi>10.1145/311535.311550]
• 40: James F. O'Brien , Adam W. Bargteil , Jessica K. Hodgins, Graphical modeling and animation of ductile fracture, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 41: Pai, D. K. 2002. STRANDS: Interactive simulation of thin solids using Cosserat models. Computer Graphics Forum 21, 3 (Sept.), 347--352.
• 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.
• 43: V. N. Parthasarathy , C. M. Graichen , A. F. Hathaway, A comparison of tetrahedron quality measures, Finite Elements in Analysis and Design, v.15 n.3, p.255-261, Jan. 1994 [doi>10.1016/0168-874X(94)90033-7]
• 44: Guillaume Picinbono , Hervé Delingette , Nicholas Ayache, Non-linear anisotropic elasticity for real-time surgery simulation, Graphical Models, v.65 n.5, p.305-321, September 2003 [doi>10.1016/S1524-0703(03)00045-6]
• 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.
• 46: Satava, R. M. 2005. Identification and reduction of surgical error using simulation. Minimally Invasive Therapy & Allied Technologies 14, 4--5 (Sept.), 257--261.
• 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.
• 48: Eftychios Sifakis , Tamar Shinar , Geoffrey Irving , Ronald Fedkiw, Hybrid simulation of deformable solids, Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 02-04, 2007, San Diego, California
• 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.
• 50: J. Spillmann , M. Teschner, CoRdE: Cosserat rod elements for the dynamic simulation of one-dimensional elastic objects, Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 02-04, 2007, San Diego, California
• 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.
• 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.
• 53: Taylor, R. H. 2006. A perspective on medical robotics. Proceedings of the IEEE 94, 9 (Sept.), 1652--1664.
• 54: Demetri Terzopoulos , John Platt , Alan Barr , Kurt Fleischer, Elastically deformable models, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.205-214, August 1987
• 55: F. P. Vidal , N. W. John , A. E. Healey , D. A. Gould, Simulation of ultrasound guided needle puncture using patient specific data with 3D textures and volume haptics, Computer Animation and Virtual Worlds, v.19 n.2, p.111-127, May 2008 [doi>10.1002/cav.v19:2]
• 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.
• 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.
• 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.
• 59: Robert J. Webster, III , Jin Seob Kim , Noah J. Cowan , Gregory S. Chirikjian , Allison M. Okamura, Nonholonomic Modeling of Needle Steering, International Journal of Robotics Research, v.25 n.5-6, p.509-525, May-June 2006 [doi>10.1177/0278364906065388]
• 60: Chris Wojtan , Greg Turk, Fast viscoelastic behavior with thin features, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Animation

Keywords:
coupled simulation, needle insertion, real-time finite element methods, surgical simulation