An advanced hybrid cutting method with an improved state machine for surgical simulation

1.1. Backgrounds 

With the rapid development of computer technology, surgery training now is possible to be performed on the screens with haptic devices. The doctors could possibly control the virtual tools and manipulate the virtual organs with the haptic devices. This virtual surgery training is superior to the traditional surgery training in many aspects such as lowering the costs, avoiding the ethics problems, providing the realistic simulations of the organ movements, corresponding the scanned data with the real human bodies, and supporting the robust repeatable applications.

Dissecting the pathological tissue is a key operation in surgery simulation. However, few cutting methods that accurately modify soft-tissue models while maintain soft-tissue stability in real-time have been proposed so far. Cutting in the context of surgery simulation is a challenging research task and worthwhile to be pursued.

1.2. Related works 

In this subsection, we present the solution of how existing methods address the two main issues in cutting: how to model the incision and how to model the cutting procedure.

In the first place, in terms of modeling the incision to reconstruct the mesh topology, common methods can be categorized into decomposing or non-decomposing methods. Non-decomposing methods do not subdivide elements. Typical non-decomposing methods, such as Cauterize method [1], [2], [3], only erase the elements intersected along with the cutting path (Fig. 1a). These methods are intuitive but weak in realistic visualization and accuracy. There are some more elaborate ones such as nearest node method [15], [18]. As depicted in Fig. 1b, nodes nearest to the cut path are decoupled and detached from each other to approximate the cut. This method does not introduce new elements and the volume is minimally altered. However, it does not describe the cut as exactly as the user defines. In addition, the cut is jagged (rather than smooth). There is a similar approach, the nearest node snapping method [4], [5] with higher accuracy in incision representation. It displaces the duplicated nodes into the trajectory of the cutting tool (Fig. 1c). However it tends to generate irregularly shaped meshes which will be devastating to the numerical solutions in the soft-tissue modeling process.

View Large Image Download to PowerPoint

Fig. 1. Cutting methods without element decomposition: (a) element deletion, (b) cut path along the nearest nodes, and (c) nearest nodes shifted into the cut trajectory.

On the other hand, decomposing methods model the incisions by subdividing the elements, with the normal definition of a finite set of subdivision patterns. Several similar methods that only differ in their subdivision patterns have been proposed in the recent years and are most related to our research. In the works of [6], [7], [8], [9], a subdivision method with symmetric subdivision (SS) patterns (Fig. 2) is introduced. Its face subdivision schemes introduce two additional face midpoints from per incised face that are not essential to the subdivision, but lead to better symmetry of the decomposition. The effective simulation requires the generation of new elements to be as few as possible in the cutting process, so that a subdivision algorithm that uses minimal elements subdivision (MES) patterns [10], [11], [12], [13] was proposed. However, the MES patterns (Fig. 3) have a drawback that the mesh tends to become inhomogeneous with cutting, because the shapes of subdivision elements are more irregular than those of the results from the symmetric approaches.

View Large Image Download to PowerPoint

Fig. 2. The symmetric subdivision (SS) patterns.

View Large Image Download to PowerPoint

Fig. 3. The five minimal elements subdivision (MES) patterns used.

In the second place, in terms of modeling the cutting procedures, general methods fall into two categories: the progressive cutting and non-progressive cutting. Non-progressive cutting methods [8], [10], [11], [14], [15], [16] subdivide the elements after the tool leaves the elements. The cutting procedure is not visualized through the duration from the tool's first entry into the element until the tool's final exit. A noticeable lag occurs between the tool's actual position and the incision's position, especially for lowly refined meshes.

Progressive cutting methods [10], [17] avoid the lag-behind effect. It subdivides elements while the tool is still in intersection. The first proposed progressive approach [10] addressed the lag-behind problem by removing and replacing the temporary subdivisions. However, in this method, a large number of deletions and insertions are executed whether or not there are real temporary subdivision changes [7], causing a lot of unnecessary computation; therefore, it can hardly satisfy real-time needs. To address this problem, [7] introduces the usage of the Finite State Machine, which organizes and manages the pass-through of a tetrahedron from an undivided condition to a final subdivision by the state machine. Finite State Machine is also probable to handle recursive cutting.

Although the progressive cutting prevents a lag-behind effect and yields a visually better result, it is more complex in concerns of time and storage for the management of temporary subdivisions. Additionally, it presents more instability problems to the soft-tissue simulation, since many small and degenerated tetrahedrons will be generated during its temporary subdivisions. Degenerated elements will also be produced via subdivision when a cut occurs near vertices or edges. They are over-flattened in shape or contain edges with very unbalanced aspect ratios. Degeneracy devastates the simulation stability, since the numerical solvers for the soft-tissue simulation do not cope very well with these inhomogeneous parts of the mesh. From this perspective, non-progressive cutting methods are superior in that they neither have to deal with the stability problems from temporal subdivisions nor have to require the storage of additional states and temporary subdivision information from the state machine.

1.3. Our approach 

A hybrid cutting approach combining progressive and non-progressive cutting algorithms is proposed in this paper, where progressive cutting is applied on the outer and the non-progressive cutting is applied on the inner part of the target organ. The efficiency and stability of subsequent soft-tissue simulation could be significantly increased when the visual performance remains as good as that of progressive cutting.

Some other advanced techniques to further improve the stability and efficiency are integrated. We combined nearest node snapping and sub-division methods to avoid generation of narrow or small tetrahedrons in our volume mesh. In addition, an improved state-machine with shortest path pre-calculation and short-cut transition is proposed for more computational efficiency.

The paper is organized as follows: the hybrid cutting details are introduced in Section 2; Section 3 gives the experimental result to demonstrate the performance of our algorithm. Section 4 discusses the proposed approach compared with the existing methods while conclusion and summary are in Section 5.

2.1. Hybrid cutting combining progressive and non-progressive methods 

The novel hybrid cutting method combines both the advantages in visual reality of progressive cutting and the benefits of the non-progressive method which has the superiority in performance and stability. The fundamental concept of this method is differentiating the surface from the core of the model (Fig. 4), and cutting the outer margin of tetrahedrons progressively, the inner core of the soft-tissue model non-progressively. The outer margin of the model's hull is defined as the tetrahedrons that share a surface point and the inner core is the other. By employing this hybrid scheme, the impression of a smooth cut is generated. Therefore the user has the mainly synchronized visual impression of the outer hull of the model while a more efficient algorithm is being used in the inner core.

View Large Image Download to PowerPoint

Fig. 4. Division of the volume mesh: the surface tetrahedrons of the outer hull (gray part) in the model are cut progressively. For the core part (light red part) of the model non-progressive subdivision is applied. (The surface tetrahedron is defined as the tetrahedrons who share a surface vertex.)

For the outer hull of the model (the dark-gray field in Fig. 4), the progressive cutting is realized via an optimized Finite State Machine algorithm as described in the following subsections. At the same time, it is deployed with the SS patterns since SS patterns provide the user with better flexibility to define the cut path. The state transition could be done by a series of mirror and rotation operations using SS patterns [7].

For the inner core of the model (the lighter field of Fig. 4), non-progressively subdivisions are employed with the MES patterns in order to reduce the mesh complexity. Non-progressive cutting can also be integrated into the Finite State Machine in which it has only a start state and an end state. MES is deployed according to the end states of the state machine. Degenerated tetrahedrons will still emerge when cutting is performed close to a vertex or an edge. To increase stability, the snapping method is implemented in the non-progressive cutting part to solve the degeneracy problem.

2.2. Optimized state machine with shortest paths pre-computation and improved shortcut transitions 

The Finite State Machine is used to conduct the progressive cutting as well as non-progressive cutting. The cutting state machine consists of five parts:

(1)S: a finite, non-empty set of states;

(2)S0: one initial state s0, which is an element of S;

(3)I: that holds a specific intersection occurrence, on edges or faces;

(4)δ: a state transition function: S×I→S, that maps states from one to another with the input of certain intersection occurrence;

(5)F: a set of final states referred to as end states, with (F→S) (for non-progressive cutting, there are only two valid states, the start state and the end state).

The state transitions mean the changeovers from one state to another. A state transition results from a specific operation which will replace the interior of the tetrahedron by a substructure. The overview of our proposed state machine is shown in Fig. 5.

View Large Image Download to PowerPoint

Fig. 5. The conceptual overview of our state machine implementation.

A state transition is conducted by a series of Subdivision, Mirror and Rotation operations [7]. In real application, the cutting may pass over several transitions in one time step, for instance, from 0×00 to 0×B2 in one time step. Therefore, to carry out the correct subdivision sequence, it is necessary to find out all the intermediate states between the two states. To minimize operations, we seek the shortest path between the two states and conduct subdivision according to the state sequence.

Since the state machine graph does not change during run-time, it is worthwhile to pre-calculate all the possible shortest paths for the set {(x, y)|x, y∈S} and store them in a look up table (LUT) at the program's start. The breadth-first search (BFS) is employed to seek the shortest paths between any two states from valid sequences. BFS builds up a predecessor array which holds all the valid shortest paths in the graph. Then, for a given start and goal state, the transition sequences can be looked up with the help of the predecessor matrix. The LUT increases the efficiency dramatically.

In case that the state machine jumps from the initial state directly to end state in one time step, it is unnecessary to carry out all the intermediate transformations. Therefore, the state machine is extended by what we refer to as shortcut transitions. At present, the shortcuts are implemented for state transitions from state 0×00 to 0×A3, 0×B3, 0×C3, 0×D3, and 0×E3, respectively, which are from the initial state to the end states. MES patterns are used for these shortcut transitions to reduce element count. The shortcut operations avoid the unnecessary realization of costly state transformation at the same time.

2.3. The work flow and the implementation of hybrid cutting 

The complete work flow of the hybrid cutting algorithm is shown in Fig. 6. The cutting tool is defined by a line segment, which functions as the cutting edge and can be moved freely through 3D space. It is flexible to form a lot of virtual scalpels. For example, a curved cutting edge can be formed by a series of linked segments. The cut path P(ti, ti+1) is a surface approximated by a strip of triangles, swept by the cutting tool's movement during a time interval [ti, ti+1]; i=0,…,n. Where [ti, ti+1] are discrete time steps and the cutting tool's head and tail coordinates are known at each time step.

View Large Image Download to PowerPoint

Fig. 6. The work flow of the hybrid cutting.

At first, the state graph and the shortest paths of any valid transition sequences are pre-calculated and stored in a LUT. Second, tetrahedrons are added to the penetrated list if any of whose faces or edges is in intersection with the cut path at the current time step. The penetrated list also holds tetrahedrons which are still under temporary subdivision.

Hereafter, for each tetrahedron in the penetrated list, if no new intersections were found, intersections’ coordinates are adjusted as well as the tool entry point (ENP) and tool exit point (EXP). Otherwise, the tetrahedron is checked for state change due to new intersections. If the new state is valid, a query to the LUT of shortest paths is performed to fetch the sequence of transitions. If the new state is an End State and the previous state is a Start State, no transition operation needs to be carried out. At the same time, MES patterns are used instead of SS patterns in this case. For non-progressive cutting, the only possible transition is that from the start state to the end state. Since the hybrid cutting processes the outer hull of the model non-progressively, the shortcuts from the start state to the end states can highly improve performance by eliminating a lot of unnecessary intermediate transitions.

To prevent recursive subdivision, a keep-back list is maintained to record the ids of tetrahedrons undergoing temporary sub-division and to prevent recursive subdivision from them. Intersection occurrences, States and States transitions are all stored as digit codes for fast mapping.

3.1. Experiments setup 

Our experiments are conducted on the standard PC equipped with 1.25GB RAM, an AMD Athlon 64-bit CPU and an nVidia Geforce 8600 graphics card with 512MB display memory. The meshing and cutting methods are implemented by C++. For the visualization of the model and the cutting tool, the open source graphics library VTK is employed. User interface and graphics pipeline are developed in Python.

3.2. Impact of the hybrid cutting on the mesh complexity 

The diagram in Fig. 7 compares the element increase of the ordinary SS, with that of our shortcut-improved subdivision approach and with that of our hybrid cutting approach. The standard SS almost triples the initial number of tetrahedrons after the cutting. The shortcut-improved SS leads to an improvement but still doubles the initial number of tetrahedrons. The hybrid cutting yields the best performance in that it generates only 1.5 times as many elements as the initial number.

View Large Image Download to PowerPoint

Fig. 7. The overall element increase in the kidney model over the period of the cut with SS and MES implementations. Hybrid cutting generates much less mesh elements than the ordinary SS approach, although the short cut improved algorithm clearly leads to an improvement.

3.3. Impact of the hybrid cutting on the mesh quality 

The mesh quality is one of the most important factors for the stable simulation of soft tissue. In other words, the mesh should have tetrahedrons homogeneous in size or volume. For a single tetrahedron, it should have balanced edge lengths. Therefore, two terms are used to measure the impact of the cutting on the mesh quality: the tetra volume deviation and the edge aspect ratio.

The average volume deviation (AvgD) is measured in percentage, which gives evidence about the relative volume quality of the entire mesh, independent of the mesh size. It is calculated by

(1)

Fig. 8 plots the values of AvgD during the cut. The diagram illustrates that the cut with SS results in a high rise of the AvgD value. Hereby the shortcut-improved algorithm has a slighter slope. The hybrid cutting achieves a much better AvgD at all times. Fig. 8 also shows the effect of the snapping on mesh quality. In both our hybrid method and the non-progressive MES method, snapping results in a more gently inclined slope of the AvgD curve. The hybrid cutting with 15% snapping threshold results in a final 73.6% AvgD, which is 5.4% higher than the result of non-progressive MES method with same threshold.

View Large Image Download to PowerPoint

Fig. 8. The average volume deviation (AVD) for all methods over the duration of the cut.

The mesh quality for single tetrahedron is measured by MaxAR (max aspect ratio) of edge distance which is defined as

(2)

(3)

Fig. 9 shows the value of QAR over the duration of a sample cut. Both curves of the SS approaches have a strong decay of the QAR value. The local aspect ratio quality for all tetrahedrons is 0.38 after the standard progressive subdivision. It is 0.415 after the sample cut with shortcut-improved MES. The decay for hybrid cutting is considerably slighter. The QAR is at 0.469 after the cut and indicates much better shaped tetrahedrons. A further improvement is achieved by using snapping with our hybrid approach. The final value of QAR is 0.472 with a snapping threshold 5%, whereas it is 0.482 with a threshold 15%. Compared to the standard non-progressive MES with snapping, the snapped hybrid cutting performs only slightly weaker. The final average MaxAR value for 5% snapped MES is 0.476. For 15% snapping threshold it lies at 0.495.

View Large Image Download to PowerPoint

Fig. 9. The averaged maximal edge aspect ratio (QAR) of all tetrahedrons in the mesh over the duration of the cut.

3.4. Algorithm efficiency 

In the following part, we measure the efficiency by the number of operations that are used for the management of temporary subdivisions. The column diagram in Fig. 10 shows the comparison of the overall number of deletion and update operations among three different algorithms over a cut with the same interval. The number of operations is plotted on the y-axis. The x-axis shows two types of operations used for the realization of temporary subdivision replacements. We compare the standard progressive cutting approach via SS with our implementation of non-progressive cutting using MES and with our hybrid cutting approach.

View Large Image Download to PowerPoint

Fig. 10. The comparison of the number of two types of operations used for the realization of temporary subdivision replacements with different methods for a same sample cut.

With our implementation of MES via the state framework, it is possible to avoid four out of five deletion operations. Those deletion operations are substituted by less expensive update operations. Since non-progressive cutting does not replace temporary subdivisions, none of the temporary substitution or deletion needs to be applied with non-progressive cutting. Our hybrid cutting that combines progressive and non-progressive cutting, avoids even more deletion and update operations.

3.5. Visual performance 

Fig. 11 shows a sample cut employing hybrid cutting to dissect a part of a simulated kidney tumor. The dissected part is dotted in red in Fig. 11a. It is illustrated that after the cutting, the tumor is completely dissected into two parts. The cut surface is smooth and continuous even snapping is used (Fig. 11b).

View Large Image Download to PowerPoint

Fig. 11. The visual result of dissecting a part of kidney tumor using hybrid cutting method.

Fig. 12 compares the visual performance of three cutting methods during cutting process. a, b and c are the volume views of non-progressive cutting, progressive cutting and hybrid cutting, respectively. The green line represents the cutting tool. In non-progressive cutting (a), a visible lag-behind appears between the tool and the incision. Therefore, there is a noticeable non-continuity in the surface view of non-progressive cutting (d). In complete progressive cutting (b), the tool fits exactly with the cut surface. In our hybrid cutting (c), the lag-behind just exists in the inner area. The cutting tool fits perfectly in the surface area. Therefore, the visual performance in the surface view of hybrid cutting (f) is exactly the same as the performance of progressive cutting (e).

View Large Image Download to PowerPoint

Fig. 12. Comparison of the visual effects of three methods: a and d: the volume view and surface view of non-progressive cutting (there is a visible lag-behind between the cut tool and the incision). b and e: of progressive cutting (the cut tool and the incision fit exactly on and inside the surface). c and f: of our hybrid cutting (the cut tool fit the incision on the surface but not in the inner core).

Fig. 13 shows the application of the hybrid cutting in the virtual laparoscopic system. The real-world surgical tools are modeled into virtual surgical tools, including a cutter and forceps.

View Large Image Download to PowerPoint

Fig. 13. Cutting application in the surgical simulation system.

4.1. Hybrid cutting 

In the previous section, we illustrated the results of our hybrid cutting method from four aspects: the impact on the mesh complexity, the impact on the mesh quality, the algorithm efficiency and the visual performance. The results presented are comparison among the three methods, the progressive, the non-progressive, and the hybrid cutting, accompanying with three incision-modeling patterns, the SS, the MES and the snapping patterns.

On the impact on the mesh complexity and mesh quality, hybrid cutting shows a performance close to the non-progressive cutting. Progressive cutting with standard SS patterns declines the mesh quality and increases the mesh complexity much more rapidly than the other two. The progressive cutting gives user the exact accurate incision model which fits perfectly with the cut tool even in the invisible inner part of the cut object. In addition, the SS patterns give the user a high degree of freedom to choose a random cut path. However, the cost is also high because SS introduces a large number of new irregularly shaped elements while progressive cutting causes a lot of temporary subdivisions. The SS declines the mesh quality rapidly and the progressive-cutting lowers the efficiency largely. From the experiments to test the algorithm efficiency, we can see that the number of operations in progressive cutting is several folds of the number in hybrid cutting. Therefore, in real application, the progressive cutting can be very slow although its original target is to eliminate the visual lag-behind in non-progressive cutting.

Considering visual feedback, the hybrid approach provides the user with a progressive or even more realistic result because of the real-time efficiency. Therefore, it is worthwhile to acquire a balanced schema such as the hybrid cutting. In addition, actually, hybrid cutting does not sacrifice visual reality for efficiency because the inner part of the organ is not seen in most cases.

The short cut in the improved state machine also leads to an improvement. It eliminates some unnecessary SS and uses MES instead. Since MES results in less new elements and irregularly shaped tetrahedrons than SS results in, the short cut improves the state machine on its impact on both the mesh complexity and mesh quality. The combination of snapping patterns and the subdivision patterns also introduces another advance. Node snapping is used instead of tetrahedron subdivision when the cut is near a vertex. Therefore, it avoids the generation of degenerated tetrahedrons which is catastrophic for the soft-tissue simulation. As shown in Fig. 8, Fig. 9, combination of snapping highly promotes the stability although it results in a slighter increase or decrease in the elements number.

4.2. Clinical experience 

Five experienced doctors from Shanghai Renji Hospital are invited to test our system independently. The doctors are requested to use the IMMERSION laparoscopic tools (by INITION Ltd., 79 Leonard Street, London EC2A 4QS, UK) to perform cutting operation nine times, each cutting simulations method (progressive, non-progressive and the hybrid) three times. Because the objects under simulated laparoscope are highly scaled, a minor inaccuracy becomes noticeable. Therefore, the lag-behind effect of the non-progressive cutting is an observable visible drawback. Three doctors of five reported that the cutting program cannot tell them the correct location of the cutting tool in non-progressive cutting procedure. They cannot make sure whether the cutting tool collides with the organ. Afterwards, progressive cutting using standard SS method shows even a worse performance. Because of the inefficiency in computing time, all the five doctors reported that the program is too slow. There was an obvious lag-behind between their operation and the program's rendering. Because of the high cost in computation, progressive cutting method can hardly achieve the real-time rendering. Therefore, the lag-behind in progressive cutting is even more obvious than that in non-progressive cutting. On the other hand, our hybrid cutting shows the best performance. In the visible surface, the incision accurately fits the position of the cutting tool and the operation is pretty fluent. The hidden lag-behind in the invisible inner part of the organ is unnoticeable. Therefore, our hybrid cutting proved to be the superior method in all the three methods.