Nuttapong Chentanez
James F. O'Brien
Skip Abstract Section
Skip Supplemental Material SectionAbstract
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.
Supplemental Material
Available for Download
zip
88-208.zip (179 MB)
The zip file contains the companion video of our paper.
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Bertails, F. 2009. Linear time super-helices. Computer Graphics Forum 28, 2 (Apr.), 417--426.Google ScholarCross Ref
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Klingner, B. M., and Shewchuk, J. R. 2007. Aggressive tetrahedral mesh improvement. In Proceedings of the 16th International Meshing Roundtable, 3--23.Google Scholar
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Müller, M., and Gross, M. H. 2004. Interactive virtual materials. In Graphics Interface 2004, 239--246. Google ScholarDigital Library
- 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
- 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
- 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
- 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
- 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
- Pai, D. K. 2002. STRANDS: Interactive simulation of thin solids using Cosserat models. Computer Graphics Forum 21, 3 (Sept.), 347--352.Google ScholarCross Ref
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Taylor, R. H. 2006. A perspective on medical robotics. Proceedings of the IEEE 94, 9 (Sept.), 1652--1664.Google ScholarCross Ref
- Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In Computer Graphics (SIGGRAPH '87 Proceedings), 205--214. Google ScholarDigital Library
- 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
- 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
- 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
- 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
- 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
- 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
Index Terms
- Interactive simulation of surgical needle insertion and steering
Recommendations
Interactive simulation of surgical needle insertion and steering
SIGGRAPH '09: ACM SIGGRAPH 2009 papersWe 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,...
Simulation of biopsy bevel-tipped needle insertion into soft-gel
AbstractPlanning and practice of surgical procedures can be improved through the use of modelling. This study provides an insight into the biopsy needle (i.e. hollow cannula) and needle-tissue interactions using a modelling approach, thus ...
Graphical abstractDisplay Omitted
Highlights- A finite element model was developed to enable correct estimation of the needle tissue interaction during needle insertion.
Comments