{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:28:06Z","timestamp":1763458086056,"version":"3.45.0"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,2,19]],"date-time":"2017-02-19T00:00:00Z","timestamp":1487462400000},"content-version":"vor","delay-in-days":366,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1218916"],"award-info":[{"award-number":["CCF-1218916"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2016,5,25]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2856317","type":"journal-article","created":{"date-parts":[[2016,2,22]],"date-time":"2016-02-22T08:07:16Z","timestamp":1456128436000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Interactively Cutting and Constraining Vertices in Meshes Using Augmented Matrices"],"prefix":"10.1145","volume":"35","author":[{"given":"Yu-Hong","family":"Yeung","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, IN"}]},{"given":"Jessica","family":"Crouch","sequence":"additional","affiliation":[{"name":"Old Dominion University, Norfolk, VA"}]},{"given":"Alex","family":"Pothen","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN"}]}],"member":"320","published-online":{"date-parts":[[2016,2,19]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00033-014-0403-z"},{"volume-title":"Finite Element Procedures","author":"Bathe K.","key":"e_1_2_2_2_1","unstructured":"K. Bathe. 1996. Finite Element Procedures. Prentice-Hall, Upper Saddle River, NJ."},{"key":"e_1_2_2_3_1","first-page":"127","article-title":"Iterative solution of large sparse linear systems arising in certain multidimensional approximation problems","volume":"22","author":"Benson M. W.","year":"1982","unstructured":"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.","journal-title":"Utilitas Mathematica"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2004.1272730"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01418156"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.662874"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.1530057"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531394"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.764872"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00007215"},{"key":"e_1_2_2_12_1","volume-title":"Proceedings of Virtual Reality Interaction and Physical Simulation. 59--68","author":"Courtecuisse Hadrien","year":"2010","unstructured":"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."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.pbiomolbio.2010.09.016"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.252559"},{"key":"e_1_2_2_15_1","volume-title":"Vosburgh (Eds.)","volume":"15","author":"Crouch J. R.","unstructured":"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."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMI.2007.898810"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.268"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.simpat.2010.11.005"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2003.817044"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/795682.797534"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11558958_92"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/646926.710089"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/580521.835862"},{"volume-title":"Biomechanics: Mechanical Properties of Living Tissues","author":"Fung Y. C.","key":"e_1_2_2_24_1","unstructured":"Y. C. Fung. 1993. Biomechanics: Mechanical Properties of Living Tissues. Springer-Verlag."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmbbm.2008.07.002"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2006.02.016"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479887139455"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMI.2010.2055884"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1031049"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2231816.2231821"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITB.2004.826720"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1080\/10255842.2012.694876"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/311535.311542"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/588272.588278"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.media.2008.12.001"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","unstructured":"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","DOI":"10.1016\/j.cma.2010.06.037"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jbiomech.2011.05.038"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9290(94)90053-1"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1980462.1980500"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.pbiomolbio.2010.09.013"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISBI.2010.5490317"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.pbiomolbio.2010.09.011"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236246.1236307"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0611010"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.pbiomolbio.2010.09.005"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1755-3768.2013.S080.x"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISBI.2004.1398564"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/646923.710372"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0207(19990910)46:1<131::AID-NME726>3.0.CO;2-J"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/646924.709054"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/509709.509718"},{"key":"e_1_2_2_53_1","unstructured":"NVIDIA. 2015. CUDA 7.0 Performance Report. http:\/\/developer.download.nvidia.com\/compute\/cuda\/compute-docs\/cuda-performance-report.pdf."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1002\/vis.257"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.2006.135"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2007.05.011"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/646924.759802"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.151"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/VR.2006.74"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/378456.378522"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/37402.37427"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2005.00829.x"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/192161.192241"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2010.10.005"},{"key":"e_1_2_2_65_1","volume-title":"Warfield","author":"Vigneron Lara M.","year":"2004","unstructured":"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."},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.pbiomolbio.2010.09.001"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1002\/cav.v15:3\/4"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-005-0310-6"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00527"},{"key":"e_1_2_2_70_1","series-title":"Lecture Notes in Computer Science","volume-title":"Multigrid integration for interactive deformable body simulation","author":"Wu Xunlei","unstructured":"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."},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.120"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.594379"},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/1731047.1731054"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2856317","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2856317","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2856317","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:17:15Z","timestamp":1763457435000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2856317"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,19]]},"references-count":73,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,5,25]]}},"alternative-id":["10.1145\/2856317"],"URL":"https:\/\/doi.org\/10.1145\/2856317","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2016,2,19]]},"assertion":[{"value":"2014-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}