Computer Graphics & Geometry
Jinjin Hong, Lixia Yan, Jiaoying Shi
State Key Lab. of CAD&CG,
Zhejiang University Hangzhou, 310027, P.R.China
E-mail: hongjj@cad.zju.edu.cn
, jyshi@cad.zju.edu.cn , jyshi@cad.zju.edu.cn
Abstract
In VISC the volume models may consiste of a large number of tetrahedrons. It is often required to reduce the number of tetrahedrons for approximating such objects. In this paper we present a new algorithm to reduce the number of tetrahedrons in a tetrahedron-based volume model. The key advantages of the new algorithm are: (1) it is simple to implement; (2) high reduction rates and excellent results can be achieved; (3) It allows a user defined simplification rate to generate a multi-resolution representation. This algorithm has been used in different application areas such as volume rendering, finite elements computation.Keywords: Tetrahedron, Simplification, Mesh, Finite Element.
2. The Volume Data
Volume visualization is a methodology used for realizing the inner structure and complex behavior of 3D volume objects. The Element in a volume data set can be a tetrahedron (called 4-nodes), a pentahedron (called 6-nodes), or a hexahedron (called 8-nodes). Tetrahedron data are most popularly used to approximate a volume model because of their ability to form any polyhedrons discretionarily. According to our paper, three types of tetrahedrons are defined, see Figure 1. Assume E0 and E1 are two parallel planes where each vertex of a tetrahedron is located:
Figure 1: The T0, T1 and T2 tetrahedrons.
Figure 2: Decomposition of a hexahedron.
3. Dscription of the Algorithm.Differing from the traditional surface simplification, our volume simplification algorithm not only simplify complexity of the surface but the internal volume data as well. Sharp edges of the volume model must be preserved in course of simplification. In addition, the simplified tetrahedron mesh should be more regular than the original mesh in order that the post-processing such as force analysis, conflict detection, deformation computation and volume rendering can take advantage of its regularity. The input objects that our algorithm can accept and process are layered tetrahedrons gained from 3D reconstruction of layered scanning images (MRI or CT images). A layered tetrahedron is defined as a tetrahedron with vertices only on two adjoining planes parallel with each other, see Figure 3.
3.1. The Main Loop Our simplification algorithm will establish a multi-resolution
volume model depending on the user requirements of simplification rate. In this
section, we adopt a layered simplification approach benefited from the
independency of tetrahedrons between two arbitrary layers. After the original
data and user defined simplification rate r have been read, the number of
simplified layers Ls 
as well as the average number of simplified tetrahedrons per layer Ts
is calculated as:
(1)
(2)
where r is a user defined simplification rate which is percentage of the reduced number of simplified tetrahedrons and the number of original tetrahedrons.LT is the number of original layers and Ls the number of simplified layers.Ti denotes the number of original tetrahedrons in layer i and Ts the average number of simplified tetrahedrons per layer. Our algorithm starts by fetching M layers of tetrahedrons from the input (M =LT/Ls), once the manipulation to these tetrahedrons is completed, one layer of newly-generated tetrahedrons is output. We finish when all of the original tetrahedral data are processed. Therefore, the manipulation to each M layers of tetrahedrons is what we are interested in. First, all of the tetrahedrons are classified into two categories: border tetrahedrons and non-border (internal) tetrahedrons. We define the former as a tetrahedron that includes the surface facets of a volume model and the latter as a tetrahedron not including any surface facets. Next, a vertex removal approach is introduced to simplify those border tetrahedrons and the preservation of sharp edges should be considered. Then a number of hexahedrons will be substituted for those non-border tetrahedrons. Finally, the resulting hole between the simplified surface and substituent hexahedrons is filled with tetrahedrons. More detailed discussion can be seen in the following. Let Tetra1, Tetra2, … , TetraM denote tetrahedrons in layer 1, 2, … , M, with vertices located in M+1 layers denoting Layer0, Layer1, … , LayerM.
Figure 3: A layered tetrahedron model.
Tetrahedron V1V2V3V4 and V5V6V7V8 are called non-border (internal) tetrahedron and border tetrahedron respectively if the former does not include the model’s surface facet while the latter does.
3.2. Surface SimplificationOur border tetrahedral simplification is a typical surface simplification algorithm, that is, it starts with the original surface and successively simplifies it. It removes vertices from Layer1 to Layer(M-1) and retriangulates the resulting holes until no further vertices can be removed. The triangle mesh left, with all vertices in Layer0 or LayerM, therefore, is the simplified surface that we need. Figure 4 illustrate if we remove a vertex Vr from the surface its adjacent triangles are removed and the remaining hole is retriangulated.
Figure 4: Removing vertex Vr and retriangulating the
remaining hole. 
Figure 5: The simplified surface where all of vertices are in Layer0 or LayerM. We call a triangle T0-triangle if its base-side in Layer0, otherwise call it T1-triangle.
3.2.1. Vertex RemovingOne of the crucial parts in the algorithm is vertex removal because in this
step not only have the vertices to be removed but also the new triangle mesh is
built to approximate the surface. As Figure 4, let Crbe the
triangle set where each triangle adjoins the vertex Vr in
Layer(n), 
and
Sr the new triangle set produced by removing the vertex Vrand
triangulating the hole V1V2V3V4V5V6.
Since there are only two vertices V3 and V5
belonging to Layer(n) in Cr, we connect them with their
adjacent vertices to form two triangles 
and 
. The rest
hole V1V2V4V5
is then filled with triangles 
,
with
base-sides in Layer(n+1) or Layer(n-1) . All of these triangles combine to form
Sr that we finally need. Yet there exist some other algorithms
to construct triangle mesh, e.g. the surface reconstruction by extracting the
contour lines of Layer0 and LayerM, the main disadvantage of those algorithms is
that they are more complicated and time-consuming. Also, it’s hard to handle
topology ambiguity of the complicated volume model.
3.3. Hexahedron Mesh Construction
In this section we substitute regular hexahedrons for the internal
tetrahedrons. The algorithm proceeds firstly by constructing a closing box for M
layers of original tetrahedrons. The closing box is divide into 
(3) sub-hexahedrons where Ts is the number of simplified
tetrahedrons per layer. According to the tetrahedron each hexahedron includes,
it falls into 3 classifications: A-hexahedron which does not includes any
tetrahedrons of original model, B-hexahedron which at least includes one border
tetrahedron and C-hexahedrons which only includes non-border tetrahedrons. We
adopt all C-hexahedrons and subdivide each of them into 6 tetrahedrons as the
simplified non-border tetrahedrons.
Figure 6: Dividing the closing box of the original data into N*N hexahedrons.
3.4. Filling The Resulting HoleThe main problem in this section is how to fill the resulting hole between the simplified surface and hexahedrons we built with tetrahedrons (Figure 7a). While, in general, this is a very complicated task, it can be easily solved by keeping track of the correspondence between the simplified surface and hexahedrons. The correspondence is the clue to this problem. It allows all vertices in surface to be counterclockwise sorted and assigned as V00, V01, V02, V03… if they belong to Layer1 or as V10, V11, V12, V13... if they belong to LayerM. Correspondingly, each vertex in hexahedron mesh’s surface should also be sorted counterclockwise and assigned as M00, M01, M02, M03...or M10, M11, M12, M13.... Note that in Figure 5, we define two kinds of triangles in simplified surface: T0-triangle with base-side in Layer0 and T1-trinangle with base-side in LayerM. The essential steps of hole filling algorithm are as follows:
Figure 7: (a) is the resulting hole between the simplified surface and hexahedron mesh. (b) is a method to fill the resulting hole.
(1) We start with an arbitrary T0-triangle in the
simplified surface and search for its adjacent triangle counterclockwise until
we reach a T1-triangle. The combination of those continuous T0 and T1 triangles
is defined as a triangle-set unit B0. For example, two
T0-triangles 
,
and one
T1-triangle Lr form a triangle-set unit B0,
see Figure 7(b). Then we have to search every arris counterclockwise in the
hexahedron mesh’s surface to find an arris M0iM1i
that is nearest to B0. The distance between an arris
M0iM1i and a triangle-set unit B0
is defined by 
(4) where 
is
the distance between a point M and a triangle-set unit B0 defined
by 
(5) where 
, 
are the vectors of vertices M0i and M1i
respectively; 
indicates the plane equation 
of each triangle in B0 . Note that 
.
Now that we have got a polyhedron 
,
we can divide it into several T0-tetrahedrons 
,
, one
T2-tetrahedron 
,
and one T1-tetrahedron 
to fill the resulting hole, see Figure 8(a). Indicated
B0 to be used.
Figure 8: Decomposition of a hexahedron.
(2) If the next triangle adjacent to B0
is a T1-triangle, keep on searching for T1-triangles counterclockwise in the
simplified surface until we reach a T0-triangle, thus the next triangle-set unit
B1 , contrary to B0 , is the combination of
several T1-triangles and one T0-triangle. Otherwise if the triangle adjacent to
B0 is a T0-triangle, B 1 is combined
with several T0-triangles and one T1-triangel. Once in the hexahedron mesh’s
surface an arris M0j M1j that’s
nearest to B 1 is found, decomposition is done showed in
Figure 8(b). A polyhedron 
is divide into several T1-tetrahedrons V11 V12M1jV02,
V12 V13M1jV02, one
T2-tetrahedron V03 V02V13M1j
and one T0-tetrahedron V02 V03M0jM1j.
Indicate B1 to be used. In order to void tetrahedron
intersecting, each counterclockwise search must resume the previous search from
the previous ending position, and moreover, any arrises or triangle-set units
having been indicated used must not be searched once again. (3) 
is a pentahedron which is divided into 3 tetrahedrons to fill the hole, see
Figure 7. Indicate arrises M0i M0i, M0i+1 M1i+1...M0j M1j
to be used. (4) Repeat step (1), (2), (3) until we reach the triangle-set
unit B0 again.
We complete when the resulting hole is filled without any gaps.
The rest triangles between the final triangle-set unit B0f and first triangle-set unit B0 can not always form a triangle-set unit. We distinguish two cases assuming that the last triangle of Bf is a T1-triangle.
Case 1: If the rest triangles are several T1-triangles (Figure 9a), we have to insert same number of T1-tetrahedrons between Bf and B0 (Figure 10a).
Case 2: If the rest triangles are several T0-triangles instead (Figure 9b), we will insert same number of T0-tetrahedrons and one T2-tetrahedron between Bf and B0 (Figure 10b).
It should also be considered that C-hexahedrons do not exist if the user defined simplification rate are high enough. That case can also be solved using our simplification algorithm by degrading all C-hexahedrons to one arris.
Figure 9: The rest triangles between 
and 
.
Figure 10: Tetrahedron insertion.
In (a), we add two T1-tetrahedrons V5V6V7V2, V7V6V8V2 to polyhedron V1V2V3V4V5V6 while in (b) we add two T0-tetrahedrons V2V7V3V6, V7V8V3V6 and one T2-tetrahedron V5V6V8V7 to it.
4. Results.An example is given to illustrate the results of our tetrahedron simplification algorithm, which have been very encouraging and are summarized below. Figure 11 illustrates tetrahedron mesh hierarchy of a pelvis with 16104 tetrahedrons. The original model, showed in Figure 11(a), is simplified with different simplified rate of 50%, 75%, 90%, 95%, 99%, so the resulting number of tetrahedrons in the simplified model is reduced. The simplified model is quit similar to the original one when the simplification rate is below 75%, and it’s acceptable when simplification rate is 90%, and some main features still can be preserved when simplification rate rise to 99%. The simplification results are presented in Table 1, with the index specifying the corresponding model in Figure 11.
Table 1: Simplification of a pelvis mode
| Index | Simplification rate | Layers | Vertices | Tetrahedrons |
| (a) | Original model | 23 | 2764 | 16104 |
| (b) | 50% | 23 | 1674 | 7302 |
| (c) | 75% | 12 | 661 | 2671 |
| (d) | 90% | 8 | 344 | 1227 |
| (e) | 95% | 6 | 232 | 714 |
| (f) | 99% | 3 | 84 | 179 |
Figure 11: Simplifed models with different simplification rate. (a) is the original model; (b), (c), (d), (e), (f) is the simplified ones with simplified rates of 50%, 75%, 90%, 95%, 99% respectively.
5. Conclusion.We have described an algorithm for solving tetrahedron simplification problem. The strengths of our method are that it (a) works for volume data; (b) can preserve sharp edges; (c) establish a multi-resolution volume data; (d) is easy to implement. This tetrahedron simplification algorithm has been applied to our virtual surgery simulation system. One we are currently exploring, is the use of multi-resolution object hierarchies in collision detection, cutting and suturing. The idea here is to recursively do operations among the multi-resolution description of object, starting from the lowest resolution representations and moving up to the higher resolutions. Furthermore, this hierarchical approach can be interrupted allowing us to trade accuracy for speed.
Acknowledgements.Our special thanks go to Chiyi Cheng and Jianning Wang for their numerous useful suggestions. We are also grateful to the anonymous reviewers for their useful comments. This project is granted by the National Natural Science Foundation of China.
ReferencesComputer Graphics & Geometry