nach oben

International Journal of Computer Assisted Radiology and Surgery

Erschienen in:

01.09.2015 | Original Article

CPU–GPU mixed implementation of virtual node method for real-time interactive cutting of deformable objects using OpenCL

verfasst von: Shiyu Jia, Weizhong Zhang, Xiaokang Yu, Zhenkuan Pan

Erschienen in: International Journal of Computer Assisted Radiology and Surgery | Ausgabe 9/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Purpose

Surgical simulators need to simulate interactive cutting of deformable objects in real time. The goal of this work was to design an interactive cutting algorithm that eliminates traditional cutting state classification and can work simultaneously with real-time GPU-accelerated deformation without affecting its numerical stability.

Methods

A modified virtual node method for cutting is proposed. Deformable object is modeled as a real tetrahedral mesh embedded in a virtual tetrahedral mesh, and the former is used for graphics rendering and collision, while the latter is used for deformation. Cutting algorithm first subdivides real tetrahedrons to eliminate all face and edge intersections, then splits faces, edges and vertices along cutting tool trajectory to form cut surfaces. Next virtual tetrahedrons containing more than one connected real tetrahedral fragments are duplicated, and connectivity between virtual tetrahedrons is updated. Finally, embedding relationship between real and virtual tetrahedral meshes is updated. Co-rotational linear finite element method is used for deformation. Cutting and collision are processed by CPU, while deformation is carried out by GPU using OpenCL.

Results

Efficiency of GPU-accelerated deformation algorithm was tested using block models with varying numbers of tetrahedrons. Effectiveness of our cutting algorithm under multiple cuts and self-intersecting cuts was tested using a block model and a cylinder model. Cutting of a more complex liver model was performed, and detailed performance characteristics of cutting, deformation and collision were measured and analyzed.

Conclusions

Our cutting algorithm can produce continuous cut surfaces when traditional minimal element creation algorithm fails. Our GPU-accelerated deformation algorithm remains stable with constant time step under multiple arbitrary cuts and works on both NVIDIA and AMD GPUs. GPU–CPU speed ratio can be as high as 10 for models with 80,000 tetrahedrons. Forty to sixty percent real-time performance and 100–200 Hz simulation rate are achieved for the liver model with 3,101 tetrahedrons. Major bottlenecks for simulation efficiency are cutting, collision processing and CPU–GPU data transfer. Future work needs to improve on these areas.

Vorheriger Artikel Assessment of registration accuracy during computer-aided oncologic limb-salvage surgery

Nächster Artikel Ultrasound texture-based CAD system for detecting neuromuscular diseases

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Zerbato D, Baschirotto D, Baschirotto D, Botturi D, Fiorini P (2011) GPU-based physical cut in interactive haptic simulations. Int J Comput Assist Radiol Surg 6(2):265–272CrossRefPubMed

Cotin S, Delingette H, Ayache N (1999) Real-time elastic deformations of soft tissues for surgical simulation. IEEE Trans Vis Comput Graph 5(1):62–73CrossRef

Cotin S, Delingette H, Ayache N (2000) A hybrid elastic model allowing real time cutting, deformations and force-feedback for surgery training and simulation. Vis Comput 16(8):437–452CrossRef

Müller M, Dorsey J, McMillan L, Jagnow R, Cutler B (2002) Stable real-time deformations. In: Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on computer animation, pp 49–54

Müller M, Hennix BHM, Ratcliff J (2006) Position based dynamics. In: Proceedings of virtual reality interactions and physical simulations, pp 71–80

Bender J, Koschier D, Charrier P, Weber D (2014) Position-based simulation of continuous materials. Comput Graph 44:1–10CrossRef

Becker M, Ihmsen M, Teschner M (2009) Corotated SPH for deformable solids. In: Proceedings of the fifth eurographics conference on natural phenomena, pp 27–34

Steinemann D, Otaduy MA, Gross M (2009) Splitting meshless deforming objects with explicit surface tracking. Graph Models 71(6):209–220CrossRef

Pietroni N, Ganovelli F, Cignoni P, Scopigno R (2009) Splitting cubes—a fast and robust technique for virtual cutting. Vis Comput 25(3):227–239CrossRef

10.

Taylor ZA, Comas O, Cheng M, Passenger J, Hawkes DJ, Atkinson D, Ourselin S (2009) On modelling of anisotropic viscoelasticity for soft tissue simulation: numerical solution and GPU execution. Med Image Anal 13(2):234–244CrossRefPubMed

11.

Joldes GR, Wittek A, Miller K (2010) Real-time nonlinear finite element computations on GPU—application to neurosurgical simulation. Comput Methods Appl Mech Eng 199(49–52):3305–3314PubMedCentralCrossRefPubMed

12.

Dick C, Georgii J, Westermann R (2011) A real-time multigrid finite hexahedra method for elasticity simulation using CUDA. Simul Model Pract Theory 19(2):801–816CrossRef

13.

LeBlanc S, Boyer P, Joslin C (2014) Modelling and animation of impact and damage with smoothed particle hydrodynamics. Vis Comput 30(6–8):909–917CrossRef

14.

Wu J, Westermann R, Dick C (2014) Physically-based simulation of cuts in deformable bodies: a survey. Eurographics 2014 State-of-the-Art Report, pp 1–19

15.

Bielser D, Maiwald VA, Gross MH (1999) Interactive cuts through 3-dimensional soft tissue. Comput Graph Forum 18(3):31–38CrossRef

16.

Bielser D, Gross MH (2000) Interactive simulation of surgical cuts. In: Proceedings of pacific graphics, pp 116–125

17.

Mor AB (2001) Progressive cutting with minimal new element creation of soft tissue models for interactive surgical simulation. Doctoral dissertation. Robotics Institute, Carnegie Mellon University

18.

Steinemann D, Harders M, Gross M, Szekely G (2006) Hybrid cutting of deformable solids. In: Proceedings of IEEE conference on virtual reality, pp 35–42

19.

Bielser D, Glardon P, Teschner M, Gross M (2004) A state machine for real-time cutting of tetrahedral meshes. Graph Models 66(6):398–417CrossRef

20.

Zhang J, Gu L, Li X, Fang M (2009) An advanced hybrid cutting method with an improved state machine for surgical simulation. Comput Medical Imaging Graph 33(1):63–71CrossRef

21.

Metzger MC, Gissler M, Asal M, Teschner M (2009) Simultaneous cutting of coupled tetrahedral and triangulated meshes and its application in orbital reconstruction. Int J Comput Assist Radiol Surg 4(5):409–416CrossRefPubMed

22.

Molino N, Bao Z, Fedkiw R (2004) A virtual node algorithm for changing mesh topology during simulation. In: ACM transactions on graphics—proceedings of the 2004 SIGGRAPH conference 2004, vol 23(3), pp 385–392

23.

Sifakis E, Der KG, Fedkiw R (2007) Arbitrary cutting of deformable tetrahedralized objects. In: Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on computer animation, pp 73–80

24.

Jeřábková L, Kuhlen T (2009) Stable cutting of deformable objects in virtual environments using xfem. IEEE Comput Graph Appl 29(2):61–71CrossRefPubMed

25.

Turkiyyah GM, Karam WB, Ajami Z, Nasri A (2011) Mesh cutting during real-time physical simulation. Comput Aided Des 43(7):809–819CrossRef

26.

Kaufmann P, Martin S, Botsch M, Grinspun E, Gross M (2009) Enrichment textures for detailed cutting of shells. In: ACM transactions on graphics—proceedings of ACM SIGGRAPH 2009, vol 28(3), pp 50:1–50:10

27.

Jeřábková L, Bousquet G, Barbier S, Faure F, Allard J (2010) Volumetric modeling and interactive cutting of deformable bodies. Prog Biophys Mol Biol 103(2–3):217–224CrossRefPubMed

28.

Dick C, Georgii J, Westermann R (2011) A hexahedral multigrid approach for simulating cuts in deformable objects. IEEE Trans Vis Comput Graph 17(11):1663–1675

29.

Seiler M, Steinemann D, Spillmann J, Harders M (2011) Robust interactive cutting based on an adaptive octree simulation mesh. Vis Comput 27(6–8):519–529CrossRef

30.

Wu J, Dick C, Westermann R (2013) Efficient collision detection for composite finite element simulation of cuts in deformable bodies. Vis Comput 29(6–8):739–749CrossRef

31.

Wu W, Heng PA (2005) An improved scheme of an interactive finite element model for 3D soft-tissue cutting and deformation. Vis Comput 21(8–10):707–716CrossRef

32.

Courtecuisse H, Jung H, Allard J, Duriez C, Lee DY, Cotin S (2010) GPU-based real-time soft tissue deformation with cutting and haptic feedback. Prog Biophys Mol Biol 103(2–3):159–168CrossRefPubMed

33.

Teschner M, Heidelberger B, Mueller M, Pomeranets D, Gross M (2003) Optimized spatial hashing for collision detection of deformable objects. In: Proceedings of vision, modeling, and visualization, pp 47–54

34.

Heidelberger B, Teschner M, Keiser R, Mueller M, Gross M (2004) Consistent penetration depth estimation for deformable collision response. In: Proceedings of vision, modeling, and visualization, pp 339–346

35.

Jean-Marc S, Marc D, Denis R, Christian M, Denis L (2005) Modelling liver tissue properties using a non-linear visco-elastic model. Med Image Anal 9(2):103–112CrossRef

Titel: CPU–GPU mixed implementation of virtual node method for real-time interactive cutting of deformable objects using OpenCL
verfasst von: Shiyu Jia
Weizhong Zhang
Xiaokang Yu
Zhenkuan Pan
Publikationsdatum: 01.09.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: International Journal of Computer Assisted Radiology and Surgery / Ausgabe 9/2015
Print ISSN: 1861-6410
Elektronische ISSN: 1861-6429
DOI: https://doi.org/10.1007/s11548-014-1147-0

Springer Professional

Abstract

Purpose

Methods

Results

Conclusions

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 9/2015

Assessment of registration accuracy during computer-aided oncologic limb-salvage surgery

Quantification of fibrous cap thickness in intracoronary optical coherence tomography with a contour segmentation method based on dynamic programming

Continuous roadmapping in liver TACE procedures using 2D–3D catheter-based registration

LapOntoSPM: an ontology for laparoscopic surgeries and its application to surgical phase recognition

Preoperative planning and real-time assisted navigation by three-dimensional individual digital model in partial nephrectomy with three-dimensional laparoscopic system

Computer-aided analysis of prostate multiparametric MR images: an unsupervised fusion-based approach