Abstract: The main methods of MC algorithm is how to improve the accuracy of isosurface extraction and topological approximation. We present a new law in this study to solve the internal ambiguity. This algorithm is an improved version of the Chernyaev method. The algorithm permits the construction of a triangle model, the topology of which coincides exactly with the topology of the isosurface of the trilinear function. The algorithm can extract isosurface exactly and lay a solid foundation for topological approximation. It is intuitional and simple than the original algorithm.
INTRODUCTION
Currently, the 3D-Reconstruction algorithm of 2D images is mainly based on surface rendering. The marching cubes method (Lorensen and Cline, 1987) is considered as the basic method for surface rendering in medical applications. Because the algorithm’s principle is simple and it is easy to realize, it is widely used. But not for a long time since the algorithm is proposed by Durst (1988) found that the algorithm is topological ambiguity (Lopes and Brodlie, 2003). Since then, numbers of scholars have carried on a large amount of research on how to avoid connection uncertainty of isosurface (Liang and Caiming, 2006). Nielsen (2003) analyzed the topological ambiguity on the surface of the cubes and adopt a new technique of asymptote to solve the problem (Nielson, 2003). Natarajan (1994) used saddle point judge method to resolve the ambiguity on a face and inside a cube together. Chernyaev (1995) used an algorithm to transfer the resolving of internal ambiguity into the resolving ambiguity on a face (Liu, 2006), the algorithm is easier than Natarajan’s method. This study provides the theoretical derivation of the algorithm in details and on the basis of which an improving method to the original algorithm is given, it is intuitional and simple than the original algorithm.
THE THEORY OF MC ALGORITHM
Definition 1: Sampling in three dimensional space R3, the sampling space is ΔX, Δy, ΔZ, respectively, then f(i, j, k) represents the volume data. A cube or cell is made by eight adjacent sampling vertex.
Definition 2: Isosurface is a set of points, these points have same value. it can be described as:
| (1) |
where, c is constant.
Definition 3: A value of a vertex is a vertex’s value of a function in volume data, we designated a vertex as positive (negative) if the vertex’s value is positive (negative), or in (out) a isosurface.
The MC-method processes one cell at a time. It determines how the isosurface intersects a given cell and then moves to the next cell. Since, there are eight nodes in each cube and every node can be in two states, that they are inside or outside the isosurface, there are 28 = 256 different arrangements of a cube relative to the isosurface. However, most of the arrangements are topologically equivalent and by rotation and/or by switching the states (in/out) of the nodes, they can be related to one of the 15 configurations shown in Fig. 1 (Qin, 2001).
THE INTERNAL AMBIGUITY OF MC AND ELIMINATING ALGORITHM
Without modification, the MC method can produce some erroneous results consisting of isosurfaces with holes, because there are two possibilities connection of the four vertices on the common face. Analysing the MC algorithm we can find that an ambiguity arises if a face has two positive and two negative diagonally opposed nodes. We call such a face an ambiguous face as is shown in Fig. 2.
| Fig. 1: | Original lookup table |
| Fig. 2: | Ambiguous face |
| Fig. 3: | Internal ambiguity |
Although, there is no ambiguous face in a cell, the nodes could be joined inside the cell. In this case, we shall say that the configuration has an internal ambiguity (Fig. 3).
In Fig. 3, there are no ambiguous faces for this configuration, but there can be two different cases: in one case the diagonal nodes are completely separated, in the other case they are joined inside the cell.
On how to avoid internal ambiguity of isosurface, Natarajan use saddle point judgement method to resolve the ambiguity on a face and inside a cube together, Chernyaev (1995) transfer the internal ambiguity into ambiguity on a face, the algorithm is easier than Natarajan’s method, but the derivative process is incomplete. In this study, we give the complete derivative process and on this basis a new judge method is presented.
| Fig. 4: | Resolving the internal ambiguity |
Definition 4: We shall designate two nodes of the same sign as non-separated or joined if there is a path from one node to the other, along which the trilinear function does not change sign. If such a path does not exist, we shall designate these nodes as separated.
The Chernyaev (1995) method of eliminating internal ambiguity is described as follows: If inside a cube there are two areas of the same sign, which are separated on the faces but are joined inside the cube, then there exists a plane parallel to a face that on the ambiguous face, formaed by the intersection of this plane with the cube, the nodes of a given sign are joined.
As shown in Fig. 4, the parallel plane AtBtCtDt lies between face A0B0C0D0 and A1B1C1D1, if A0C1 are joined inside the cube, then AtCt must be joined in face AtBtCtDt. Next we will derive how to decide two nodes are joined in a face.
Let A(0, 0), B(1, 0), C(0, 1), D(1, 1) represent the values at the nodes of an ambiguous face ABCD, we can obtain the value of any points in the face by using the bilinear interpolant function as follows:
| (2) |
Because the isosurface is F(s, t) = α, let F(s, t)-α = 0, we can obtain function:
Let
We have function:
| (3) |
The function represents a hyperbola, where,
Assuming α = 0, we have:
Then we get the law of two nodes are joined in a face: if BD-AC = 0, AC are joined; else AC are separated.
So, if we want to judge whether AtCt are joined, it must be:
| (4) |
Where:
| (5) |
Substituting Eq. 5 into Eq. 4 we have a squared inequality.
| (6) |
Where:
Then we get the law of two nodes are joined inside a cube:
| (7) |
IMPROVING THE CHERNYAEV ALGORITHM
Liu (2006) pointed that Chernyaev didn’t give a prove of the law’s correctness. We present a new law in this study to solve the internal ambiguity based on literature.
Theorem 1: If two nodes of the same sign are non-separated or joined inside a cube, their same sign neighborhood must coincide with each other.
Proof: As is shown in Fig. 5, A0C1 are two nodes inside the cube, assume f1 and f2 are two neighborhood of A0C1, they have the same sign. Because A0C1 are joined, then there must be have only one face that the nodes of a given sign are joined. So, f1 and f2 coincide with each other.
Theorem 2: There are two nodes t1 and t2 which located in the edges of two same sign nodes, the nodes are need to judge if they are joined, when t1>t2, the two nodes’ neighborhood coincide with each other.
Proof: As is shown in Fig. 5, at any time we can find two nodes t1 and t2, which located in the edges of the two same sign nodes, the cubes changed there sign at t1 and t2, such as edge A0A1 changed there sign from positive into negative at t1. While edge C0C1 changed there sign from negative into positive at t2. Because A0C1 are joined, so only at the case of t1>t2, the neighborhood of nodes A0 and C1 coincide with each other.
| Fig. 5: | The theory of improving algorithm |
Based on the above theorem, we take t1 and t2 as the nodes where f(t1) = f(t2) = 0, tm = 1/2(t1+t2), then the law of two nodes are joined inside a cube can be described as follow:
| (8) |
Advantage of the algorithm is that: first, the law is available at any case; second, this method has the characteristics of less calculation, high velocity, high efficiency and etc. The disadvantage is that some case may be missed, but it is only a very little case.
CONCLUSION
We present a new law in this study to solve the internal ambiguity. This algorithm is an improved version of the Chernyaev (1995) method. Present method is intuitional and simple than the original algorithm. But as the original algorithm, the modifications we have suggested for ambiguous faces add considerable complexity to the MC method. So, how often do these configurations arise? We have test the frequency of occurrence of the various configurations for several data sets, then the answer is that they certainly do occur in real data sets, but not very often.