{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,22]],"date-time":"2022-12-22T19:10:16Z","timestamp":1671736216212},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,3,27]],"date-time":"2021-03-27T00:00:00Z","timestamp":1616803200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,27]],"date-time":"2021-03-27T00:00:00Z","timestamp":1616803200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["501444-16"],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Adv. Model. and Simul. in Eng. Sci."],"published-print":{"date-parts":[[2021,12]]},"abstract":"Abstract<\/jats:title>Simulators for virtual surgery training need to perform complex calculations very quickly to provide realistic haptic and visual interactions with a user. The complexity is further increased by the addition of cuts to virtual organs, such as would be needed for performing tumor resection. A common method for achieving large performance improvements is to make use of the graphics hardware (GPU) available on most general-use computers. Programming GPUs requires data structures that are more rigid than on conventional processors (CPU), making that data more difficult to update. We propose a new method for structuring graph data, which is commonly used for physically based simulation of soft tissue during surgery, and deformable objects in general. Our method aligns all nodes of the graph in memory, independently from the number of edges they contain, allowing for local modifications that do not affect the rest of the structure. Our method also groups memory transfers so as to avoid updating the entire graph every time a small cut is introduced in a simulated organ. We implemented our data structure as part of a simulator based on a meshless method. Our tests show that the new GPU implementation, making use of the new graph structure, achieves a 10 times improvement in computation times compared to the previous CPU implementation. The grouping of data transfers into batches allows for a 80\u201390% reduction in the amount of data transferred for each graph update, but accounts only for a small improvement in performance. The data structure itself is simple to implement and allows simulating increasingly complex models that can be cut at interactive rates.<\/jats:p>","DOI":"10.1186\/s40323-021-00192-7","type":"journal-article","created":{"date-parts":[[2021,3,31]],"date-time":"2021-03-31T12:02:52Z","timestamp":1617192172000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["GPU-friendly data structures for real time simulation"],"prefix":"10.1186","volume":"8","author":[{"given":"Vincent","family":"Magnoux","sequence":"first","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-7157-7726","authenticated-orcid":false,"given":"Beno\u00eet","family":"Ozell","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,27]]},"reference":[{"key":"192_CR1","doi-asserted-by":"crossref","unstructured":"Bianchi G, Harders M, Sz\u00e9kely G. Mesh topology identification for mass-spring models. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. Springer; 2003. p. 50\u20138.","DOI":"10.1007\/978-3-540-39899-8_7"},{"issue":"8","key":"192_CR2","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/PL00007215","volume":"16","author":"S Cotin","year":"2000","unstructured":"Cotin S, Delingette H, Ayache N. A hybrid elastic model for real-time cutting, deformations, and force feedback for surgery training and simulation. Visual Computer. 2000;16(8):437\u201352.","journal-title":"Visual Computer."},{"issue":"2","key":"192_CR3","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1002\/nme.1620370205","volume":"37","author":"T Belytschko","year":"1994","unstructured":"Belytschko T, Lu YY, Gu L. Element-free Galerkin methods. Int J Numer Methods Eng. 1994;37(2):229\u201356.","journal-title":"Int J Numer Methods Eng"},{"issue":"2","key":"192_CR4","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.jvcir.2007.01.005","volume":"18","author":"M M\u00fcller","year":"2007","unstructured":"M\u00fcller M, Heidelberger B, Hennix M, Ratcliff J. Position based dynamics. J Visual Commun Image Represent. 2007;18(2):109\u201318.","journal-title":"J Visual Commun Image Represent"},{"issue":"2","key":"192_CR5","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1109\/MM.2008.31","volume":"28","author":"E Lindholm","year":"2008","unstructured":"Lindholm E, Nickolls J, Oberman S, Montrym J. NVIDIA Tesla: A Unified Graphics and Computing Architecture. IEEE Micro. 2008;28(2):39\u201355.","journal-title":"IEEE Micro."},{"issue":"8","key":"192_CR6","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1016\/j.simpat.2005.08.004","volume":"13","author":"J Georgii","year":"2005","unstructured":"Georgii J, Westermann R. Mass-spring systems on the GPU. Simul Modelling Practice Theory. 2005;13(8):693\u2013702.","journal-title":"Simul Modelling Practice Theory"},{"issue":"3\u20134","key":"192_CR7","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1002\/cav.24","volume":"15","author":"W Wu","year":"2004","unstructured":"Wu W, Heng PA. A hybrid condensed finite element model with GPU acceleration for interactive 3D soft tissue cutting. Computer Anim Virtual Worlds. 2004;15(3\u20134):219\u201327.","journal-title":"Computer Anim Virtual Worlds."},{"key":"192_CR8","doi-asserted-by":"publisher","first-page":"154","DOI":"10.4028\/www.scientific.net\/AMR.121-122.154","volume":"121\u2013122","author":"ZY Yuan","year":"2010","unstructured":"Yuan ZY, Ding YH, Zhang YY, Zhao JH. Real-time simulation of tissue cutting with CUDA based on GPGPU. Adv Mater Res. 2010;121\u2013122:154\u201361.","journal-title":"Adv Mater Res"},{"issue":"2","key":"192_CR9","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/s11548-010-0505-9","volume":"6","author":"D Zerbato","year":"2011","unstructured":"Zerbato D, Baschirotto D, Baschirotto D, Botturi D, Fiorini P. GPU-based physical cut in interactive haptic simulations. Int J Computer Assisted Radiol Surg. 2011;6(2):265\u201372.","journal-title":"Int J Computer Assisted Radiol Surg"},{"key":"192_CR10","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/978-3-540-70521-5_4","volume-title":"Simulation biomedical","author":"O Comas","year":"2008","unstructured":"Comas O, Taylor ZA, Allard J, Ourselin S, Cotin S, Passenger J. Efficient Nonlinear FEM for Soft Tissue Modelling and Its GPU Implementation within the Open Source Framework SOFA. In: Simulation Biomedical, editor. Simulation biomedical. Berlin: Springer; 2008. p. 28\u201339."},{"key":"192_CR11","doi-asserted-by":"crossref","unstructured":"Taylor ZA, Comas O, Cheng M, Passenger J, Hawkes DJ, Atkinson D, et\u00a0al. Modelling anisotropic viscoelasticity for real-time soft tissue simulation. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. Springer; 2008. p. 703\u2013710.","DOI":"10.1007\/978-3-540-85988-8_84"},{"key":"192_CR12","doi-asserted-by":"crossref","unstructured":"Yibo S, Hui X, Dehai Y. Improvements of GPU Implementation of Nonlinear Soft Tissue Deformation with CHAI 3D. In: 3rd International Conference on Multimedia Technology (ICMT-13). Atlantis Press; 2013. p. 1196\u20131203.","DOI":"10.2991\/icmt-13.2013.147"},{"issue":"6\u20138","key":"192_CR13","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1007\/s00371-019-01680-z","volume":"35","author":"J Pan","year":"2019","unstructured":"Pan J, Yang Y, Gao Y, Qin H, Si Y. Real-time simulation of electrocautery procedure using meshfree methods in laparoscopic cholecystectomy. Visual Computer. 2019;35(6\u20138):861\u201372.","journal-title":"Visual Computer."},{"issue":"4","key":"192_CR14","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1109\/TBME.2009.2038364","volume":"58","author":"RJ Lapeer","year":"2011","unstructured":"Lapeer RJ, Gasson PD, Karri V. A Hyperelastic Finite-Element Model of Human Skin for Interactive Real-Time Surgical Simulation. IEEE Trans Biomed Eng. 2011;58(4):1013\u201322.","journal-title":"IEEE Trans Biomed Eng"},{"issue":"2","key":"192_CR15","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1002\/cav.1543","volume":"25","author":"S Li","year":"2014","unstructured":"Li S, Zhao Q, Wang S, Hao A, Qin H. Interactive deformation and cutting simulation directly using patient-specific volumetric images. Computer Anim Virtual Worlds. 2014;25(2):155\u201369.","journal-title":"Computer Anim Virtual Worlds."},{"key":"192_CR16","unstructured":"Bosman J, Duriez C, Cotin S. Connective tissues simulation on GPU. In: VRIPHYS 13: 10th Workshop on Virtual Reality Interaction and Physical Simulation. Eurographics Association; 2013. p. 41\u201350."},{"issue":"3","key":"192_CR17","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s00371-008-0216-1","volume":"25","author":"N Pietroni","year":"2009","unstructured":"Pietroni N, Ganovelli F, Cignoni P, Scopigno R. Splitting cubes: a fast and robust technique for virtual cutting. Visual Computer. 2009;25(3):227\u201339.","journal-title":"Visual Computer."},{"issue":"2\u20133","key":"192_CR18","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.pbiomolbio.2010.09.016","volume":"103","author":"H Courtecuisse","year":"2010","unstructured":"Courtecuisse H, Jung H, Allard J, Duriez C, Lee DY, Cotin S. GPU-based real-time soft tissue deformation with cutting and haptic feedback. Progr Biophys Mol Biol. 2010;103(2\u20133):159\u201368.","journal-title":"Progr Biophys Mol Biol."},{"key":"192_CR19","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.cmpb.2019.03.018","volume":"175","author":"W Hou","year":"2019","unstructured":"Hou W, Liu PX, Zheng M. A new model of soft tissue with constraints for interactive surgical simulation. Computer Methods Progr Biomed. 2019;175:35\u201343.","journal-title":"Computer Methods Progr Biomed"},{"issue":"6","key":"192_CR20","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1007\/s11548-016-1373-8","volume":"11","author":"M Camara","year":"2016","unstructured":"Camara M, Mayer E, Darzi A, Pratt P. Soft tissue deformation for surgical simulation: a position-based dynamics approach. Int J Computer Assisted Radiol Surg. 2016;11(6):919\u201328.","journal-title":"Int J Computer Assisted Radiol Surg"},{"issue":"3\u20134","key":"192_CR21","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1002\/cav.1655","volume":"26","author":"J Pan","year":"2015","unstructured":"Pan J, Bai J, Zhao X, Hao A, Qin H. Real-time haptic manipulation and cutting of hybrid soft tissue models by extended position-based dynamics. Computer Animation Virtual Worlds. 2015;26(3\u20134):321\u201335.","journal-title":"Computer Animation Virtual Worlds."},{"issue":"2","key":"192_CR22","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1016\/j.simpat.2010.11.005","volume":"19","author":"C Dick","year":"2011","unstructured":"Dick C, Georgii J, Westermann R. A real-time multigrid finite hexahedra method for elasticity simulation using CUDA. Simul Modelling Practice Theory. 2011;19(2):801\u201316.","journal-title":"Simul Modelling Practice Theory."},{"key":"192_CR23","doi-asserted-by":"crossref","unstructured":"Fenz W, Dirnberger J. Real-time surgery simulation of intracranial aneurysm clipping with patient-specific geometries and haptic feedback. In: SPIE Medical Imaging. vol. 9415. International Society for Optics and Photonics; 2015. p. 94150H\u201394150H\u201310.","DOI":"10.1117\/12.2082053"},{"issue":"2","key":"192_CR24","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1002\/cnm.1407","volume":"27","author":"GR Joldes","year":"2011","unstructured":"Joldes GR, Wittek A, Miller K. An adaptive dynamic relaxation method for solving nonlinear finite element problems. Application to brain shift estimation. Int J Numer Methods Biomed Eng. 2011;27(2):173\u201385.","journal-title":"Int J Numer Methods Biomed Eng."},{"key":"192_CR25","doi-asserted-by":"crossref","unstructured":"Baraff D, Witkin A. Large steps in cloth simulation. In: Proceedings of the 25th annual conference on Computer graphics and interactive techniques. ACM; 1998. p. 43\u201354.","DOI":"10.1145\/280814.280821"},{"key":"192_CR26","doi-asserted-by":"crossref","unstructured":"Magnoux V, Ozell B. Real-time visual and physical cutting of a meshless model deformed on a background grid. Computer Animation and Virtual Worlds. 2020; p. e1929.","DOI":"10.1002\/cav.1929"},{"key":"192_CR27","doi-asserted-by":"crossref","unstructured":"Magnoux V, Ozell B. Dynamic Cutting of a Meshless Model for Interactive Surgery Simulation (in press). In: Salento AVR 2020: 7th International Conference on Augmented Reality, Virtual Reality and Computer Graphics; 2020.","DOI":"10.1007\/978-3-030-58468-9_9"}],"container-title":["Advanced Modeling and Simulation in Engineering Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s40323-021-00192-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s40323-021-00192-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s40323-021-00192-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,31]],"date-time":"2021-03-31T12:03:39Z","timestamp":1617192219000},"score":1,"resource":{"primary":{"URL":"https:\/\/amses-journal.springeropen.com\/articles\/10.1186\/s40323-021-00192-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,27]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["192"],"URL":"https:\/\/doi.org\/10.1186\/s40323-021-00192-7","relation":{},"ISSN":["2213-7467"],"issn-type":[{"value":"2213-7467","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,27]]},"assertion":[{"value":"13 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"Vincent Magnoux is a Ph.D. graduate from the department of Computer Engineering and Software Engineering at Polytechnique Montr\u00e9al. His research focuses on real time physically based simulation in virtual reality, with a particular interest in high performance and parallel computing. Beno\u00eet Ozell is an associate professor in the department of Computer Engineering and Software Engineering at Polytechnique Montr\u00e9al. His research interests include Computer Graphics, Scientific Visualization, Virtual Reality, Augmented Reality, Healthcare Simulations. ExternalRef removed","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Authors\u2019 information"}}],"article-number":"7"}}