Keywords

1 Introduction

A fast soft tissue simulation is required of surgical simulators. In particular, in case presenting stable reaction force to users when grasping and touching organs, a higher update rate (about several hundred Hz) of the deformation simulation and the calculation of reaction force is required. In addition, in the surgery simulation, large object deformation that involves rotation often occurs [1]. Therefore, computationally efficient deformation simulation which can consider the geometric nonlinearity is required.

As a geometric nonlinear deformation model, there is Saint Venant Kirchhoff (StVK) Model [2]. Delingette [3] and Kikuuwe [4] have proposed efficient computation procedures for the StVK model by using the biquadratic and quadratic springs. However, it is difficult to reduce computation time due to discontinuous memory accesses in the computation.

Recently, in the field of computer graphics, corotated deformation models have been proposed [5]. In the corotated deformation model, the local coordinate system of each tetrahedral element is defined, and shape matching between the tetrahedral element at initial state and that at deformed state is performed. The component of rotational motion is then removed, and the deformation simulation using a linear finite element model is performed on the local coordinate system thus consideration of geometric nonlinearity becomes possible. However, there is a problem that a large amount of computation is required for this shape matching (extraction of the component of the rotational motion) [6].

As for the other acceleration approaches, (a) online re-mesh (multi-resolution model) [7, 8, 9] and (b) parallel computation [10] have been proposed. By applying these approaches to the corotated deformation model, further acceleration can be expected.

In this paper, a novel interactive nonlinear deformation simulation approach is proposed. In our approach, corotated deformation model and online re-mesh are used together. The elastic object is represented by a multi-resolution hierarchy of tetrahedral adaptive volume mesh. The tetrahedral adaptive volume mesh is locally refined by online re-mesh to concentrate the computational load into the regions that deform the most. To get a reduction in the number of times of shape matching, we used two different mesh resolutions. One is used for shape matching and the other is for linear finite element deformation simulation. Reduction of shape matching is realized by substituting the rotation of tetrahedra at deep depth for rotation of tetrahedra at shallow depth [11]. In addition, we propose the criterion for subdivision and simplification in the adaptive corotated deformation simulation.

In an evaluation experiment, we compare computation time, the accuracy of deformation and reaction force among (1) proposed approach, (2) linear finite element model (L-FEM), and (3) nonlinear finite element model in which StVK model is used (NL-FEM). Through these experiments, we show the effectiveness of our proposed approach.

2 Related Works

In this section, overviews of the online re-mesh deformation simulation and the corotated deformation model are stated.

2.1 Online Re-Mesh Using Tetrahedral Adaptive Mesh

In our past research, we proposed an online re-mesh approach [9] using tetrahedral adaptive mesh [12].

Our tetrahedral adaptive mesh is generated by the following procedure. Initially, the object model is enclosed with six root tetrahedral (Fig. 1). Then, as shown in Fig. 2, the root tetrahedra are recursively bisected by adding new nodes to the midpoints of the longest edges according to local features (e.g. non-uniformity of material properties, curvature of the isosurface). This subdivision process is repeated until the approximation accuracy of the whole model is satisfied.

Fig. 1
figure 1

Six root tetrahedra

Full size image
Fig. 2
figure 2

Binary refinement and simplification

Full size image

The online re-mesh approach uses this tetrahedral adaptive multi-resolution mesh, and recursively refines (bisects) or simplifies each tetrahedron according to the rate of elongation σ of the longest edge of the tetrahedron.

The advantages of our online re-mesh approach using the tetrahedral adaptive mesh are as follows.

  1. (1)

    Low computational cost: Computational complexity of this online re-mesh process is \( O\left( {{ \log }n} \right) \), where n is the division number of a side of an initial cube in Fig. 1. This is because of neighboring regions considered in the subdivision is limited.

  2. (2)

    High quality mesh: In our approach, only three types (TYPE0, 1 and 2) of tetrahedra are used. The lower limit of aspect ratio of these tetrahedra is 0.64. The upper limit of the radius-shortest edge ratio of these tetrahedra is 1.11.

  3. (3)

    Mesh isotropy: In our approach, mirror symmetric tetrahedra are recurrently generated, thus cancellation of affections of artifacts in the computation is possible.

2.2 Corotated Deformation Model

In the linear finite element model, the relationship between force vector \( {\mathbf{f}}_{T}^{{}} \) of four nodes of tetrahedron T and displacement vector \( {\mathbf{u}}_{T}^{{}} \) is described using the following equation,

$$ {\mathbf{K}}_{T}^{{}} {\mathbf{u}}_{T}^{{}} = {\mathbf{f}}_{T}^{{}} , $$
(1)

where \( {\mathbf{K}}_{T}^{{}} \) is an element stiffness matrix of tetrahedron T.

In contrast, in the corotated deformation model, the relationship between force vector \( {\mathbf{f}}_{T}^{c} \) of four nodes of tetrahedron T and position vector \( {\mathbf{x}}_{T}^{{}} \) is described using the following equation,

$$ {\mathbf{R}}_{T}^{{}} {\mathbf{K}}_{T}^{{}} \left( {{\mathbf{R}}_{T}^{ - 1} {\mathbf{x}}_{T}^{{}} - {\mathbf{x}}_{T}^{0} } \right) = {\mathbf{f}}_{T}^{c} , $$
(2)

where \( {\mathbf{R}}_{T}^{{}} \) and \( {\mathbf{x}}_{T}^{0} \) are the rotation matrix and the initial position vector of tetrahedron T, respectively.

In this model, large deformation which involves rotation (geometrical nonlinearity) can be considered, however, the computational cost of the extraction of \( {\mathbf{R}}_{T}^{{}} \) becomes a problem.

3 Adaptive and Corotated Deformation Model

In this section, approaches to reduce shape matching which is realized by substituting the rotation of tetrahedra at deep depth for rotation of tetrahedra at shallow depth are proposed.

3.1 Reducing Shape Matching Computation Using Hierarchical Structure

As stated in the previous section, the six root tetrahedra are recursively bisected and then the binary tree is constructed in the tetrahedral adaptive mesh generation. In this process, two child tetrahedra are generated from one parent tetrahedron and four grandchild tetrahedra are generated from one parent tetrahedron and so on. Therefore rotation matrices of these child or grandchild or descendant terahedra are nearly equal to that of their ancestor tetrahedra.

In this paper, we propose an approach to reduce the shape matching computation. This is realized by substituting the rotation matrices of descendant tetrahedra for rotation matrices of ancestor tetrahedra. In our previous online re-mesh approach, suitable resolutions of tetrahedra which can approximate when given accurate criterion are selected online and are used for the deformation simulation. In contrast, in this approach, as shown in Fig. 3, suitable resolutions of tetrahedra for the rotation extraction are separately selected online. If the difference of rotation between neighboring tetrahedra is large, in other words, the curvature of the object is large, high resolution tetrahedra should be used for rotation extraction. In other parts, low resolution tetrahedra should be used for rotation extraction and substitute the rotation matrices of descendant tetrahedra for rotation matrices of these selected tetrahedra. By using this approach, we can reduce the number of times of shape matching computation.

Fig. 3
figure 3

Tetrahedra for rotation extraction and deformation simulation

Full size image

3.2 Criterion for Subdivision and Simplification in the Adaptive Corotated Deformation Simulation

In this paper, we also propose a criterion for subdivision and simplification in the adaptive corotated deformation simulation. As an index of difference of rotation of neighboring tetrahedron, we propose the square of the Frobenius norm of difference of rotation matrices of neighboring tetrahedron. The relationship between the square of the Frobenius norm of difference matrix between rotation matrix \( {\mathbf{R}}^{{T_{n} }} \) of tetrahedron T n and rotation matrix \( {\mathbf{R}}^{{T_{m} }} \) of neighboring tetrahedron T m and difference of rotation θ between of tetrahedron T n and neighboring tetrahedron T m is described as follows.

$$ \left\| {{\mathbf{R}}^{{T_{m} }} - {\mathbf{R}}^{{T_{n} }} } \right\|_{\text{F}}^{2} \,= \,4\left( {1 - { \cos }\theta } \right). $$
(3)

If rotation matrix \( {\mathbf{R}}^{{T_{n} }} \) of tetrahedron T n and rotation matrix \( {\mathbf{R}}^{{T_{m} }} \) of whose neighboring tetrahedron T m satisfy Eq. (4), these tetrahedra should be subdivided, where θ max and F max are subdivision threshold of the rotation matrix and the Frobenius norm, respectively. Otherwise, if they satisfy Eq. (5), these tetrahedra should be simplified, where θ min and F min are simplification threshold of the rotation matrix and the Frobenius norm, respectively.

$$ \left\| {{\mathbf{R}}^{{T_{m} }} - {\mathbf{R}}^{{T_{n} }} } \right\|_{\text{F}}^{2} > = 4\left( {1 - { \cos }\theta_{max} } \right) = F_{max} $$
(4)
$$ \left\| {{\mathbf{R}}^{{T_{m} }} - {\mathbf{R}}^{{T_{n} }} } \right\|_{\text{F}}^{2} < = 4\left( {1 - { \cos }\theta_{min} } \right) = F_{min} $$
(5)

Computation of the Frobenius norm is easy, thus fast computation of Eq. (4) and (5) is possible.

4 Evaluation Experiments

In this section, we perform evaluation experiments using two experimental models (cuboid and liver models). Through these experiments, we confirm the accuracy (deformation and reaction force) and computation time.

4.1 Experimental Model and Experimental Equipment

As experimental models, cuboid model (64 × 64 × 192 mm) and liver model were used. Figure 4 shows a cuboid model (all tetrahedra are TYPE0, subdivision level was 6, the number of nodes was 325, the number of tetrahedra was 1152.) We used Young’s modulus E = 0.5 [kPa], Poisson ratio ν = 0.49, density ρ = 10 [\( {\text{Kg}}/{\text{m}}^{3} \)].

Fig. 4
figure 4

Experimentl model (cuboid model)

Full size image

Figure 5 shows our experimental equipment. For whole computation, we used a PC (CPU: Intel Core i7-2760QM 2.4 GHz, Memory: 8 GB, OS: Scientific Linux 6.1). A haptic loop (which included processes of deformation simulation, online re-mesh and presentation of reaction force) run at 1 [kHz]. A visual loop run at 30 [Hz] asynchronously. Reaction force was presented by a force feedback device (Sensable PHANToM omni).

Fig. 5
figure 5

Experimental equipment

Full size image

We compared the accuracy (deformation and reaction force) and computation time among (1) proposed approach, (2) linear finite element model (L-FEM), and (3) nonlinear finite element model in which StVK model was used (NL-FEM).

4.2 Evaluation 1 (Evaluation of Deformation)

Simulation of bending the cuboid (curvature of the cuboid model was almost constant) was performed by applying displacement boundary conditions to nodes on both ends of the cuboid model. We compared the deformation and computation time among (1) proposed approach, (2) linear finite element model (L-FEM), and (3) nonlinear finite element model in which StVK model was used (NL-FEM).

Table 1 shows maximum, minimum and average error of displacement of all nodes at different threshold F max which were used for rotation extraction. Figure 6a shows simulation results of deformation, and the bold (red) wireframe shows that these terahedra were used for rotation extraction. We can find that the error in volume increment was observed in the result of L-FEM. In contrast, results by using the proposed approach was similar to NL-FEM. In the proposed approach, except in case θ max  = 25.8 [deg], maximum of the average of error of displacement was 0.4 [mm].

Table 1 Errors of displacement [mm]
Full size table
Fig. 6
figure 6

Results (cuboid model was bended to almost constant curvature) a Deformation b Computation time [ms]

Full size image

Figure 6b shows result of computation time. We can find that the computation time of rotation extraction was decreased in case that larger threshold θ max was used. Computation time of each online re-mesh process was 0.015 [ms].

4.3 Evaluation 2 (Evaluation of Reaction Force)

We evaluated reaction force when the user was interacting with a deformable object (a cuboid model). The sinusoidal displacement boundary condition u was applied to a node of the cuboid model, as follows:

$$ {\text{u}} = \left( {0.0, 50{ \sin }0.072k\frac{\pi }{180}, 0.0} \right), $$

where k was a number of simulation cycle.

Figure 7a, b show result of deformation and intensity reaction force, respectively. We can find that the reaction force was very smooth, even if our approach was used.

Fig. 7
figure 7

Results (sinusoidal displacement boundary condition was applied to a node of the cuboid model) a Deformation b Reaction force

Full size image

4.4 Evaluation 3 (Surgery Simulation)

We are also developing an embedded deformation model in order to simulate inhomogeneous elastic objects like a liver with a vascular system [13]. It is possible to apply this proposed approach to the embedded deformation model.

Figure 8 shows results of linear FEM (L-FEM) and our proposed approach where a gallbladder was grasped and pulled. In both simulation, the embedded deformation model was also used. In L-FEM, volume increment of gallbladder was observed. In case of proposed approach, the users did not feel any unpleasant reaction force.

Fig. 8
figure 8

Results of surgery simulation a L-FEM b Proposed approach

Full size image

5 Conclusions

In this paper, we proposed a novel interactive nonlinear deformation simulation approach for surgery simulation. In our approach, corotated deformation model and online re-mesh are used in combination. To get a reduction in the number of times of shape matching, we used two different mesh resolutions. In addition, we proposed the criterion for subdivision and simplification in the adaptive corotated deformation simulation.

In current implementation, the tensor mass model approach [14] was used in the deformation simulation. This means that the forward difference method was used as a solver and the computational cost per one simulation cycle becomes low, however, a higher update rate is required to maintain stable simulation. In the future, we will apply proposed approach to another solver which uses backward difference method. Also, we are planning to investigate a GPU implementation of the proposed approach.