“Interactively Cutting and Constraining Vertices in Meshes Using Augmented Matrices” by Yeung, Crouch and Pothen

  • ©Yu Hong Yeung, Jessica Crouch, and Alex Pothen

Conference:


Type:


Title:

    Interactively Cutting and Constraining Vertices in Meshes Using Augmented Matrices

Session/Category Title: MESHES

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    We present a finite-element solution method that is well suited for interactive simulations of cutting meshes in the regime of linear elastic models. Our approach features fast updates to the solution of the stiffness system of equations to account for real-time changes in mesh connectivity and boundary conditions. Updates are accomplished by augmenting the stiffness matrix to keep it consistent with changes to the underlying model, without refactoring the matrix at each step of cutting. The initial stiffness matrix and its Cholesky factors are used to implicitly form and solve a Schur complement system using an iterative solver. As changes accumulate over many simulation timesteps, the augmented solution method slows down due to the size of the augmented matrix. However, by periodically refactoring the stiffness matrix in a concurrent background process, fresh Cholesky factors that incorporate recent model changes can replace the initial factors. This controls the size of the augmented matrices and provides a way to maintain a fast solution rate as the number of changes to a model grows. We exploit sparsity in the stiffness matrix, the right-hand-side vectors and the solution vectors to compute the solutions fast, and show that the time complexity of the update steps is bounded linearly by the size of the Cholesky factor of the initial matrix. Our complexity analysis and experimental results demonstrate that this approach scales well with problem size. Results for cutting and deformation of 3D linear elastic models are reported for meshes representing the brain, eye, and model problems with element counts up to 167,000; these show the potential of this method for real-time interactivity. An application to limbal incisions for surgical correction of astigmatism, for which linear elastic models and small deformations are sufficient, is included.

References:


    1. Ugo Andreaus, Ivan Giorgio, and Angela Madeo. 2014. Modeling of the interaction between bone tissue and resorbable biomaterial as linear elastic materials with voids. Zeitschrift für angewandte Mathematik und Physik 66, 1, 209–237.
    2. K. Bathe. 1996. Finite Element Procedures. Prentice-Hall, Upper Saddle River, NJ.
    3. M. W. Benson and P. O. Federickson. 1982. Iterative solution of large sparse linear systems arising in certain multidimensional approximation problems. Utilitas Mathematica 22, 127–140.
    4. J. Berkley, G. Turkiyyah, D. Berg, M. Ganter, and S. Weghorst. 2004. Real-time finite element modeling for surgery simulation: An application to virtual suturing. IEEE Transactions on Visualization and Computer Graphics 10, 3, 314–325. DOI:http://dx.doi.org/10.1109/TVCG.2004.1272730 
    5. J. Berkley, S. Weghorst, H. Gladstone, G. Raugi, D. Berg, and M. Ganter. 1999. Banded matrix approach to finite element modeling for soft tissue simulation. Virtual Reality: Research, Development & Applications 4, 203–212.
    6. M. Bro-Nielsen. 1998. Finite element modeling in surgery simulation. Proceedings of the IEEE 86, 3, 490–503. DOI:http://dx.doi.org/10.1109/5.662874
    7. Morten Bro-Nielsen and Stephane Cotin. 1996. Real-time volumetric deformable models for surgery simulation using finite elements and condensation. Computer Graphics Forum 15, 3, 57–66. DOI:http://dx.doi.org/10.1111/1467-8659.1530057
    8. Yanqing Chen, Timothy A. Davis, William W. Hager, and Sivasankaran Rajamanickam. 2008. Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate. ACM Transactions on Mathematical Software 35, 22:1–22:14. 
    9. Nuttapong Chentanez, Ron Alterovitz, Daniel Ritchie, Lita Cho, Kris K. Hauser, Ken Goldberg, Jonathan R. Shewchuk, and James F. O’Brien. 2009. Interactive simulation of surgical needle insertion and steering. ACM Transactions on Graphics 28, 3, Article 88, 10 pages. DOI:http://dx.doi.org/10.1145/1531326.1531394 
    10. Stephane Cotin, Herve Delingette, and Nicholas Ayache. 1999. Real-time elastic deformations of soft tissues for surgery simulation. IEEE Transactions on Visualization and Computer Graphics 5, 1, 62–73. 
    11. Stephane Cotin, Herve Delingette, and Nicholas Ayache. 2000. A hybrid elastic model for real-time cutting, deformations, and force feedback for surgery training and simulation. The Visual Computer 16, 7, 437–452.
    12. Hadrien Courtecuisse, Jeremie Allard, Christian Duriez, and Stephane Cotin. 2010a. Asynchronous preconditioners for efficient solving of non-linear deformations. In Proceedings of Virtual Reality Interaction and Physical Simulation. 59–68.
    13. Hadrien Courtecuisse, Hoeryong Jung, Jeremie Allard, Christian Duriez, Doo Yong Lee, and Stphane Cotin. 2010b. GPU-based real-time soft tissue deformation with cutting and haptic feedback. Progress in Biophysics & Molecular Biology 103, 23, 159–168. DOI:http://dx.doi.org/10.1016/j.pbiomolbio.2010.09.016
    14. S. A. Cover, N. F. Ezquerra, J. F. O’Brien, R. Rowe, T. Gadacz, and E. Palm. 1993. Interactively deformable models for surgery simulation. IEEE Computer Graphics and Applicattions 13, 6, 68–75. DOI:http://dx.doi.org/10.1109/38.252559 
    15. J. R. Crouch and A. Cherry. 2007. Parametric eye models. In Medicine meets virtual reality, J. D. Westwood, R. S. Haluck, H. M. Hoffman, G. T. Mogel, R. Phillips, R. A. Robb, and K. G. Vosburgh (Eds.), Vol. 15. 91–93.
    16. J. R. Crouch, S. M. Pizer, E. L. Chaney, Yu-Chi Hu, G. S. Mageras, and M. Zaider. 2007. Automated finite element analysis for deformable registration of prostate images. IEEE Transactions on Medical Imaging 26, 10, 1379–1390. DOI:http://dx.doi.org/10.1109/TMI.2007.898810
    17. C. Dick, J. Georgii, and R. Westermann. 2011a. A hexahedral multigrid approach for simulating cuts in deformable objects. IEEE Transactions on Visualization and Computer Graphics 17, 11, 1663–1675. DOI:http://dx.doi.org/10.1109/TVCG.2010.268 
    18. Christian Dick, Joachim Georgii, and Rüdiger Westermann. 2011b. A real-time multigrid finite hexahedra method for elasticity simulation using CUDA. Simulation Modelling Practice & Theory 19, 2, 801–816.
    19. S. E. DiMaio and S. P. Salcudean. 2003. Needle insertion modeling and simulation. IEEE Transactions on Robotics and Automation 19, 5, 864–875. DOI:http://dx.doi.org/10.1109/TRA.2003.817044
    20. Simon P. DiMaio and S. E. Salcudean. 2002. Simulated interactive needle insertion. In Proceedings of IEEE Symposium on Haptic Interfaces Virtual Environment Teleoperator Systems, 344. 
    21. Florin Dobrian and Alex Pothen. 2006. Oblio: Design and performance. In Applied Parallel Computing. State of the Art in Scientific Computing, Jack Dongarra, Kaj Madsen, and Jerzy Wasniewski (Eds.). Lecture Notes in Computer Science, Vol. 3732. Springer, Berlin, 758–767. DOI:http://dx.doi.org/10.1007/11558958_92 
    22. C. Forest, Herve Delingette, and Nicholas Ayache. 2002. Cutting simulation of manifold volumetric meshes. In Proceedings of International Conference on Medical Image Computing and Computer-Assisted Intervention, Part II. Springer-Verlag, London, 235–244. 
    23. Andreas O. Frank, I. Alexander Twombly, Timothy J. Barth, and Jeffrey D. Smith. 2001. Finite element methods for real-time haptic feedback of soft-tissue models in virtual reality simulators. In Proceedings of IEEE Virtual Reality. 257. 
    24. Y. C. Fung. 1993. Biomechanics: Mechanical Properties of Living Tissues. Springer-Verlag.
    25. Amit Gefen, Ran Shalom, David Elad, and Yossi Mandel. 2009. Biomechanical analysis of the keratoconic cornea. Journal of the Mechanical Behavior of Biomedical Materials 2, 3, 224–236.
    26. Joachim Georgii and Rdiger Westermann. 2006. A multigrid framework for real-time simulation of deformable bodies. Computer and Graphics 30, 3, 408–415. DOI:http://dx.doi.org/10.1016/j.cag.2006.02.016 
    27. J. Gilbert. 1994. Predicting structure in sparse matrix computations. SIAM Journal on Matrix Analysis and Applications 15, 1, 62–79. 
    28. O. Goksel and S. E. Salcudean. 2011. Image-based variational meshing. IEEE Transactions on Medical Imaging 30, 1, 11–21. DOI:http://dx.doi.org/10.1109/TMI.2010.2055884
    29. W. W. Hager. 1989. Updating the inverse of a matrix. SIAM Review 31, 2, 221–239. DOI:http://dx.doi.org/10.1137/1031049 
    30. Florian Hecht, Yeon Jin Lee, Jonathan R. Shewchuk, and James F. O’Brien. 2012. Updated sparse Cholesky factors for corotational elastodynamics. ACM Transactions on Graphics 31, 1–13. 
    31. P.-A. Heng, Chun-Yiu Cheng, Tien-Tsin Wong, Yangsheng Xu, Yim-Pan Chui, Kai-Ming Chan, and Shiu-Kit Tso. 2004. A virtual-reality training system for knee arthroscopic surgery. IEEE Transactions on Information Technology in Biomedicine 8, 2, 217–227. DOI:http://dx.doi.org/10.1109/TITB.2004.826720 
    32. Alex Jahya, Martijn G. Schouten, Jurgen J. Fütterer, and Sarthak Misra. 2014. On the importance of modelling organ geometry and boundary conditions for predicting three-dimensional prostate deformation. Computer Methods in Biomechanics and Biomedical Engineering 17, 5, 497–506.
    33. Doug L. James and Dinesh K. Pai. 1999. ArtDefo: Accurate real time deformable objects. In Proceedings of ACM SIGGRAPH. 65–72. DOI:http://dx.doi.org/10.1145/311535.311542 
    34. Doug L. James and Dinesh K. Pai. 2003. Multiresolution Green’s function methods for interactive simulation of large-scale elastostatic objects. ACM Transactions on Graphics 22, 47–82. 
    35. Grand Roman Joldes, Adam Wittek, and Karol Miller. 2009. Suite of finite element algorithms for accurate computation of soft tissue deformation for surgical simulation. Medical Image Analysis 13, 6, 912–919. DOI:http://dx.doi.org/10.1016/j.media.2008.12.001
    36. Grand Roman Joldes, Adam Wittek, and Karol Miller. 2010. Real-time nonlinear finite element computations on GPU applications to neurosurgical simulation. Computer Methods on Applied Mechanics and Engineering 199, 4952, 3305–3314. DOI:http://dx.doi.org/10.1016/j.cma.2010.06.037
    37. Mateusz Maria Juszczyk, Luca Cristofolini, and Marco Viceconti. 2011. The human proximal femur behaves linearly elastic up to failure under physiological loading conditions. Journal of Biomechanics 44, 12, 2259–2266.
    38. Tony M. Keaveny, X. Edward Guo, Edward F. Wachtel, Thomas A. McMahon, and Wilson C. Hayes. 1994. Trabecular bone exhibits fully linear elastic behavior and yields at low strains. Journal of Biomechanics 27, 9, 1127–1136.
    39. Umut Koçak, Karljohan Lundin Palmerius, and Matthew Cooper. 2009. Dynamic deformation using adaptable, linked asynchronous FEM regions. In Proceedings of ACM Spring Conference on Computer Graphics. 197–204. DOI:http://dx.doi.org/10.1145/1980462.1980500 
    40. R. J. Lapeer, P. D. Gasson, and V. Karri. 2010. Simulating plastic surgery: From human skin tensile tests, through hyperelastic finite element models to real-time haptics. Progress in Biophysics & Molecular Biology 103, 23, 208–216. DOI:http://dx.doi.org/10.1016/j.pbiomolbio.2010.09.013
    41. C. Lederman, A. Joshi, I. Dinov, J. D. Van Horn, L. Vese, and A. Toga. 2010. Tetrahedral mesh generation for medical images with multiple regions using active surfaces. In IEEE International Symposium on Biomedical Imaging: From Nano to Macro. 436–439. DOI:http://dx.doi.org/10.1109/ISBI.2010.5490317 
    42. Bryan Lee, Dan C. Popescu, and Sebastien Ourselin. 2010. Topology modification for surgical simulation using precomputed finite element models based on linear elasticity. Progress in Biophysics & Molecular Biology 103, 23, 236–251. DOI:http://dx.doi.org/10.1016/j.pbiomolbio.2010.09.011
    43. Alex Lindblad and George Turkiyyah. 2007. A physically-based framework for real-time haptic cutting and interaction with 3D continuum models. In Proceedings of ACM Symposium on Solid and Physical Modeling. 421–429. DOI:http://dx.doi.org/10.1145/1236246.1236307 
    44. Richard J. Lipton, Donald J. Rose, and Robert E. Tarjan. 1979. Generalized nested dissection. SIAM Journal on Numerical Analysis 16, 2, 346–358.
    45. Joseph W. H. Liu. 1990. The role of elimination trees in sparse factorization. SIAM Journal on Matrix Analysis and Applications 11, 1, 134–172. 
    46. Stephanie Marchesseau, Tobias Heimann, Simon Chatelin, Remy Willinger, and Herv Delingette. 2010. Fast porous visco-hyperelastic soft tissue model for surgery simulation: Application to liver surgery. Progress in Biophysics and Molecular Biology 103, 23, 185–196. DOI:http://dx.doi.org/10.1016/j.pbiomolbio.2010.09.005
    47. M. Mikielewicz, R. Michael, G. Montenegro, L. Pinilla Cortes, and R. I. Barraquer. 2013. Elastic properties of human lens zonules as a function of age in presbyopes. Acta Ophthalmologica 91, s252, 0–0.
    48. A. Mohamed and C. Davatzikos. 2004. Finite element mesh generation and remeshing from segmented medical images. In IEEE International Symposium on Biomedical Imaging: Nano to Macro, Vol. 1. 420–423. DOI:http://dx.doi.org/10.1109/ISBI.2004.1398564
    49. Andrew Mor and Takeo Kanade. 2000. Modifying soft tissue models: Progressive cutting with minimal new element creation. In Medical Image Computing and Computer-Assisted Intervention, Scott Delp, Anthony DiGoia, and Branislav Jaramaz (Eds.). Lecture Notes in Computer Science, Vol. 1935. Springer, Berlin, CH412–CH412. 
    50. N. Mos, J. Dolbow, and T. Belytschko. 1999. A finite element method for crack growth without remeshing. International Journal for Numerical Methods in Engineering 46, 1, 131–150.
    51. Han-Wen Nienhuys and A. Frank van der Stappen. 2001. A surgery simulation supporting cuts and finite element deformation. In Proceedings of the 4th International Conference on Medical Image Computing and Computer-Assisted Intervention. Springer-Verlag, London, 145–152. 
    52. Igor Nikitin, Lialia Nikitina, Pavel Frolov, Gernot Goebbels, Martin Göbel, Stanislav Klimenko, and Gregory M. Nielson. 2002. Real-time simulation of elastic objects in virtual environments using finite element method and precomputed Green’s functions. In Proceedings of Eurographics Workshop on Virtual Environments. 47–52. 
    53. NVIDIA. 2015. CUDA 7.0 Performance Report. http://developer.download.nvidia.com/compute/cuda/compute-docs/cuda-performance-report.pdf.
    54. Guillaume Picinbono, Jean-Christophe Lombardo, Herv Delingette, and Nicholas Ayache. 2002. Improving realism of a surgery simulator: linear anisotropic elasticity, complex interactions and force extrapolation. The Journal of Visualization and Computer Animation 13, 3, 147–167. DOI:http://dx.doi.org/10.1002/vis.257
    55. M. Sedef, E. Samur, and C. Basdogan. 2006. Real-time finite-element simulation of linear viscoelastic tissue behavior based on experimental data. IEEE Computer Graphics and Applications 26, 6, 58–68. DOI:http://dx.doi.org/10.1109/MCG.2006.135 
    56. Guy Sela, Jacob Subag, Alex Lindblad, Dan Albocher, Sagi Schein, and Gershon Elber. 2007. Real-time haptic incision simulation using FEM-based discontinuous free-form deformation. Computer Aided Design 39, 8, 685–693. DOI:http://dx.doi.org/10.1016/j.cad.2007.05.011 
    57. D. Serby, Matthias Harders, and Gábor Székely. 2001. A new approach to cutting into finite element models. In Proceedings of the 4th International Conference on Medical Image Computing and Computer-Assisted Intervention. Springer-Verlag, London, 425–433. 
    58. J. Spillmann and M. Harders. 2012. Robust interactive collision handling between tools and thin volumetric objects. IEEE Transactions on Visualization and Computer Graphics 18, 8, 1241–1254. DOI:http://dx.doi.org/10.1109/TVCG.2011.151 
    59. D. Steinemann, M. Harders, M. Gross, and G. Szekely. 2006. Hybrid cutting of deformable solids. In IEEE Virtual Reality Conference. 35–42. DOI:http://dx.doi.org/10.1109/VR.2006.74 
    60. Demetri Terzopoulos and Kurt Fleischer. 1988. Modeling inelastic deformation: Viscoelasticity, plasticity, fracture. SIGGRAPH Computer Graphics 22, 4, 269–278. DOI:http://dx.doi.org/10.1145/378456.378522 
    61. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically deformable models. SIGGRAPH Computer Graphics 21, 4, 205–214. DOI:http://dx.doi.org/10.1145/37402.37427 
    62. M. Teschner, S. Kimmerle, B. Heidelberger, G. Zachmann, L. Raghupathi, A. Fuhrmann, M.-P. Cani, F. Faure, N. Magnenat-Thalmann, W. Strasser, and P. Volino. 2005. Collision detection for deformable objects. Computer Graphics Forum 24, 1, 61–81. DOI:http://dx.doi.org/10.1111/j.1467-8659.2005.00829.x
    63. Greg Turk and Marc Levoy. 1994. Zippered polygon meshes from range images. In Proceedings of ACM SIGGRAPH. 311–318. DOI:http://dx.doi.org/10.1145/192161.192241 
    64. George M. Turkiyyah, Wajih Bou Karam, Zeina Ajami, and Ahmad Nasri. 2011. Mesh cutting during real-time physical simulation. Computer Aided Design 43, 7, 809–819. DOI:http://dx.doi.org/10.1016/j.cad.2010.10.005 
    65. Lara M. Vigneron, Jacques G. Verly, and Simon K. Warfield. 2004. Modelling surgical cuts, retractions, and resections via extended finite element method. In Proceedings of the 7th International Conference on Medical Image Computing and Computer-Assisted Intervention, Part II. Christian Barillot, David R. Haynor, and Pierre Hellier (Eds.). Lecture Notes in Computer Science, Vol. 3217. Springer, Berlin, 311–318.
    66. Adam Wittek, Grand Joldes, Mathieu Couton, Simon K. Warfield, and Karol Miller. 2010. Patient-specific non-linear finite element modelling for predicting soft organ deformation in real-time; Application to non-rigid neuroimage registration. Progress in Biophysics and Molecular Biology 103, 23, 292–303. DOI:http://dx.doi.org/10.1016/j.pbiomolbio.2010.09.001
    67. Wen Wu and Pheng Ann Heng. 2004. A hybrid condensed finite element model with GPU acceleration for interactive 3D soft tissue cutting: Research Articles. Computer Animation and Virtual Worlds 15, 3–4, 219–227. DOI:http://dx.doi.org/10.1002/cav.v15:3/4 
    68. Wen Wu and Pheng Ann Heng. 2005. An improved scheme of an interactive finite element model for 3D soft-tissue cutting and deformation. The Visual Computer 21, 8, 707–716. DOI:http://dx.doi.org/10.1007/s00371-005-0310-6
    69. Xunlei Wu, Michael S. Downes, Tolga Goktekin, and Frank Tendick. 2001. Adaptive nonlinear finite elements for deformable body simulation using dynamic progressive meshes. In Proceedings of Eurographics, A. Chalmers and T.-M. Rhyne (Eds.). Vol. 20(3). Blackwell Publishing, 349–358.
    70. Xunlei Wu and Frank Tendick. 2004. Multigrid integration for interactive deformable body simulation. In Medical Simulation, Stephane Cotin and Dimitris Metaxas (Eds.). Lecture Notes in Computer Science, Vol. 3078. Springer, Berlin, 92–104.
    71. Xinyu Zhang and Y. J. Kim. 2012. Simple culling methods for continuous collision detection of deforming triangles. IEEE Transactions on Visualization and Computer Graphics 18, 7, 1146–1155. DOI:http://dx.doi.org/10.1109/TVCG.2011.120 
    72. Hualiang Zhong, Mark P. Wachowiak, and Terry M. Peters. 2005. Adaptive finite element technique for cutting in surgical simulation. Medical Imaging 2005: Visualization, Image-Guided Procedures, and Display 5744, 1, 604–611. DOI:http://dx.doi.org/10.1117/12.594379
    73. Yongning Zhu, Eftychios Sifakis, Joseph Teran, and Achi Brandt. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Transactions on Graphics 29, 2, Article 16, 18 pages. DOI:http://dx.doi.org/10.1145/1731047.1731054

ACM Digital Library Publication:


Overview Page: