Cutting in deformable objects

By Han-Wen Nienhuys.

Introduction

Flight simulators, such as the one on the picture, are used today to train pilots. This has many advantages, as it is much cheaper than a real plane and much safer when anything goes wrong. (Picture from NASA Glenn Research center, Controls and Dynamics Technology Branch)

Like pilots, surgeons have a great responsibility, and training surgeons is expensive, and can be dangerous or difficult. For example, minimally invasive procedures are difficult to learn: here, surgical instruments are introduced into the body through small apertures. There is little room for hand-eye coordination, and also little tactile feedback. It is difficult to learn how to perform such operations.

The aim of surgery simulation is to provide surgeons with virtual patients and surgical tools: tools and patients that respond realistically enough to be instructive.

Simulating surgery on-line is a challenging multidisciplinary problem: it brings together advanced software, special hardware, medicine and mathematics. The mechanics of living tissue are very complex, much more than structural materials such as steel or concrete. The amount of CPU time available is limited because of the interactive nature of the application. When a surgeon pushes virtual tissue, it should respond directly. To top that, handling the required 3D meshes is a hard task. All-in-all this a interesting problem, where real world applications, practical engineering and theoretical science meet.

(Picture from INRIA Projet Epidaure)

My research

To make such systems reality, one needs a lot of engineering background and have access to medical doctors, dedicated programmers and special purpose hardware. Our CS department is better known for its theoretical papers on computational geometry, so me doing this research here is a slightly paradoxical situation.

My way out of this paradox is to focus on "fundamental" questions for interactive surgery simulation systems. Note that fundamental is in quotes on purpose. Against the background of the involved disciplines---FEM modeling, mesh generation, nonlinear optimization and continuum mechanics -- the questions and problems to be addressed are mundane. Nevertheless, finding the simple solutions among all the advanced research in these rich fields, and integrating them into one coherent big answer was much harder than I imagined.

The basic premise for taking a fundamental stance, is that surgery involves the combination of a deforming object, and changes to that deforming object, in other words ``cutting in deformable objects.'' This means that the following ideas must be combined:

• The Finite Element Method for computing deformations of 3D objects.
• Unconstrained (nonlinear) optimization techniques for solving the FEM equations.
• Manipulations of tetrahedral meshes to support operations such as cutting.

Overview

• My first attempts at combining these elements are described in publications at EuroGraphics 2000 and MICCAI 2001. I used linear elasticity and solved the equations using the conjugate gradient algorithm. This was done instead of the much more popular mass-spring system. A simple form of cutting (that produced a jagged cut surface) was also implemented. Later versions also incorporated a node repositioning scheme. This produced a nice incision, but unfortunately it also flattened mesh elements. (more...)
• Simulated soft material may collide with itself. The first step to preventing this, is detecting such collisions. A speed up for hierarchical bounding volume for deformable objects with cuts has been investigated for a MSc. project by Peter Bozarov. (more ...)
• I have worked on using static iterative methods for computing nonlinear deformations. This was a lot of work to implement and get right, but fortunately, the conclusion can be stated succinctly: it works, and it works as well as a dynamic method or better. (more ... )
  
• The performance of relaxation algorithms is intimately related to characteristics of the mesh. Therefore simulated surgical procedures should leave mesh quality as high as possible, and size as low as possible. We propose a technique for incorporating Delaunay flips into a cutting routine. This technique generates better meshes than subdivision for 2D cuts. It also works for 3D surfaces. (more ... )
  
  
• It has been demonstrated previously that simulating needle insertions in soft tissue is useful for training and planning purposes. However, the approach followed is limited to 2D linear material. We have experimented with techniques that make generalizations to 3D nonlinear tissue feasible. (more ... )
  
  
• This extension to 3d needle insertion was indeed implemented, and shows promise: it works as expected. (more ... )

Publications

The results of my search for the big answer will hopefully be in my PhD. thesis, but some parts of it have been already been documented.

• Han-Wen Nienhuys and A. Frank van der Stappen, Combining finite element deformation with cutting for surgery simulations, (gzipped PS, 990k, abstract, citeseer page), Eurographics 2000, Short Presentations.
• Han-Wen Nienhuys and A. Frank van der Stappen, A surgery simulation supporting cuts and finite element deformation, presented in the oral presentation stream at MICCAI 2001 ( 400k gzipped PS, abstract, citeseer page).

• Han-Wen Nienhuys and A. Frank van der Stappen, Supporting cuts and finite element deformation in interactive surgery simulation. Tech Report 2001/16 ( 300k PDF, citeseer page). This report describes the work of the previous paper in more detail.
• Han-Wen Nienhuys and A. Frank van der Stappen, A Delaunay approach to interactive cutting in triangulated surfaces. Paper presented at WAFR 2002 (820k PDF)

• Han-Wen Nienhuys and A. Frank van der Stappen, A Delaunay approach to interactive cutting in triangulated surfaces. Technical report UU-CS-2002-044. This report contains more details than the conference paper. (800k PDF, citeseer page).
• Han-Wen Nienhuys, Cutting in deformable objects. Phd Thesis, Utrecht University, 2003. (more information)
• Han-Wen Nienhuys and A. Frank van der Stappen, Maintaining mesh connectivity using a simplex-based data structure . Technical report UU-CS-2003-018. (140k PDF).
• Han-Wen Nienhuys and A. Frank van der Stappen, Interactive needle insertions in 3D nonlinear material . Technical report UU-CS-2003-019. (530k PDF).
• Han-Wen Nienhuys and A. Frank van der Stappen, A computational technique for interactive needle insertions in 3D nonlinear material , IEEE International Conference on Robotics and Automation, 2004.

A BibTeX bibliography file is available here.

Software

Read these additional notes first.

• FEM (linear/nonlinear, static/dynamic, pluggable material models) and naive volumetric cutting.
• 2D cutting
• 3D surface cutting
• 3D needle insertion, failed
• 2D and 3D needle insertion

Background

This research is carried out at the Center for Geometry, Imaging and Virtual Environments of the Institute for information and computing sciences under auspices of the Dutch research school ASCI. Frank van der Stappen is the daily supervisor, Mark Overmars is the executive supervisor.