Abstract
A method of lossless geometry compression on the coordinates of the vertexes for grid model is presented. First, the 3D coordinates are pre-processed to be transformed into a specific form. Then these 3D coordinates are changed into 1D data by making the three coordinates of a vertex represented by only a position number, which is made of a large integer. To minimize the integers, they are sorted and the differences between two adjacent vertexes are stored in a vertex table. In addition to the technique of geometry compression on coordinates, an improved method for storing the compressed topological data in a facet table is proposed to make the method more complete and efficient. The experimental results show that the proposed method has a better compression rate than the latest method of lossless geometry compression, the Isenburg-Lindstrom-Snoeyink method. The theoretical analysis and the experiment results also show that the important decompression time of the new method is short. Though the new method is explained in the case of a triangular grid, it can also be used in other forms of grid model.
1. Introduction
The triangular mesh provides one of the most popular representation for 3D graphic models. This is largely because its mathematical simplicity allows rapid rendering of triangular datasets, which in turn has led to wide availability for the triangular rendering hardware. In addition, the triangular mesh serves as a sort of lowest common denominator for computer models, since almost any model representation (spline, implicit-surface, volumetric) may be converted with arbitrary accuracy to a triangular mesh. For these and other reasons, the triangular models are the most common representation for the visualization of medical, scientific and CAD datasets. A triangular mesh consists of two different types of data: the topological data, which specifies the connectivity of the mesh and the geometrical data, which describes the information associated with each individual vertex or triangle. In addition, there are also mesh properties such as the texture coordinates, the material attributes etc.
With the development of technology, modern 3D digital photography and 3D scanning systems can acquire both the geometry and the appearance of complex and real-world objects. These techniques generate huge volumes of 3D object geometry data. Therefore, how to manage, process and manipulate the large polygonal mesh becomes a big problem. A lot of approaches have been used to alleviate this problem. Over the past several years a tremendous amount of work has been done on mesh simplification, multiple levels of detail and progressive mesh. At the same time, lots of work has been done on mesh compression. The need for more compact mesh representations has motivated researchers to develop techniques for the compression of connectivity [1–4], geometry [5–8] and properties [9–12]. Almost all the connectivity compression techniques are lossless, while most of the geometry compression methods are not. Lossy compression is often not acceptable scientific and engineering applications where lossless compression is desired. In the literature [13], a method is described for the compression of a floating-point coordinate with predictive coding in a lossless manner. The predicted and the actual floating-point values are divided into sign, exponent and mantissa and their corrections are compressed separately with context-based arithmetic coding. In the literature [14], a method for lossless geometry compression for steady state and time-varying irregular grids is also proposed.
In this paper, we explore a new method for the lossless compression of geometry. The 3D coordinates are pre-processed by quantizing them into the integer form losslessly and then changed into 1D data of a large integer. The integers will be sorted by ascending order, and the difference between the two adjacent large integers can be represented by one to three integer/integers. In addition, an improved method for storing compressed topological data into the facet table is proposed to make the method more complete and efficient. Although the new method is explained in the case of a triangle grid, it can also be used in other grids.
2. Change Three Dimensional Coordinates into One Dimension
We know that the length of a memory unit is limited so that the data it can store are discrete. To represent a space model, the positions of 3D points (grid points), which can be used are discrete. Suppose that the limits of the coordinates x, y and z of the vertex of a model are (Xmin,Xmax), (Ymin,Ymax) and (Zmin,Zmax) and the coordinates are d decimal digits at most. We can calculate that there are (Xmax-Xmin+1)×(Ymax-Ymin+1)×(Zmax-Zmin+1)×103d positions for the vertex of these coordinate's limits.
We number these positions in order of x, y and z coordinates. In this way, each position in 3D space has a sequence number, or in the reverse order. The case of changing the 2D coordinates into 1D (the coordinates have 1 decimal digits) is shown in Figure 1. The relationship between the position number s and the x, y and z coordinates of the corresponding grid point is as follows
where Lx= Xmax-Xmin, Ly=Ymax-Ymin.
Changing 2D coordinates into 1D (the coordinates have 1 decimal digits)
The process of changing the 3D coordinates into 1D reduces three coordinates to one position number without reducing the precise coordinate value. There may be quite a large number of grid points and therefore the position number may be very large cases where some coordinates of the vertex are very small while some others are very large. The position number may be large enough to occupy two or three memory units, which reduces the effect of the compression. It is obvious that there are a lot of redundancy cells that cannot be used. Suppose the coordinate is represented by The coordinates are changed into the unitary exponent form. The least exponent is subtracted from each of the coordinate values in the unitary exponent form to avoid the minus exponent. The exponent is moved left and the mantissa right by separating them with a point. This will be regarded as a float number.
After pre-processing, the size of a grid cell is10-d and the level of the number of cells in total is (e1+e2)/10-d = (e1+e2)×10d. This level is obviously much less than that before the pre-processing, which reduces the values of the position numbers. Let us take an example to illustrate the process. Suppose that the maximum and the minimum (the limits) of the coordinate values of a model are 20.2805 and −0.000899085 and the least exponent is -e2=−5. Firstly, these two limits are changed into the unitary exponent form as 0.202805×102 and −0.899085×10-3. Then subtract –5 from exponent 2 and –3, which makes them positive 7 and 2. Finally these two limits are saved as 7.202805 and −2.899085. All coordinate values between the limits are pre-processed in this way before they are changed into 1D. In this way, the level of the number of the cells in total is reduced from 20.281399085×1011 to 10.101890×106.
3. Compression in Saving the One Dimension Data
To represent an object model, at least a vertex table and a facet table are needed. The vertex table is used to contain the vertexes of the model. One item (vertex) has three data sets, i.e., the x, y and z coordinates. The table is shown in Figure 2.
The original vertex table
The procedure of making the new compressed vertex table is as follows. Firstly the three coordinates of each vertex stored in the original vertex table are changed into the position number si. Then the numbers are sorted in ascending order. At last, the difference Δi between each number and its previous number is stored in a table (except the first number, which is stored in the first unit of the table). This results in the compressed vertex table, as shown in Figure 3.
Compressed vertex table
Since the differences between the neighbouring numbers are stored in the compressed vertex table, most of them can be contained in one unit. This is why the compressed vertex table uses less data. The lengths of the units in the original vertex table and in the compressed vertex table are equal. For example, if float data are used in the original vertex table, long integer data are used in the compressed vertex table. Both of them are 32 bits.
Since the position number obtained from the three coordinates of a vertex is very large, three units at most are needed to store it (we have used a multi-unit arithmetic program to compute it). Theoretically, some of the differences may still need three units to be saved. We use a negative to represent the higher units overstepping one unit. A negative number here means its absolute value should combine with the next number to form a large number, as shown by the ith vertex in Figure 3.
The sequence of the vertexes in the original vertex table is different from that in the compressed vertex table. We know that a grid model cannot be changed by the sequence of its vertexes in the table. It can only be distorted by the change in vertex location and the topologic relations between the vertexes. We take the sequence after sorting as the original sequence, which means that we will arrange the original vertex table in this sequence if we make a grid model ourselves. The vertex table gotten back from the compressed vertex table is in this sequence.
The decompressing of the compressed vertex table is simple. Each difference is added by the last number beginning from the first number to obtain the position numbers. Then a reverse changing from the position numbers to the coordinates x, y and z is taken. This is the reverse calculation of the formula.
All decompressing requires the expense of time. The time needed for the decompressing of this compressed vertex table is very small. When the table is transferred on the Internet, the received package of data can be decompressed while receiving the following on the receiving computer. This is because only the last number is needed to decompress a number.
4. Organization of the Facet Table
Triangular facet modelling is the most often used method for grid modelling. Therefore, the proposed method will be described in the case of the triangular facet modelling. The vertex numbers of the three vertexes of each facet are stored in the original facet table, as shown in Figure 4.
The original facet table
We want to re-arrange the sequence of the facets to make two facets with a common edge next to each other by searching through the facet table. The re-arrangement of the sequence of the facets in the facet table does not make change to the model as in the case of the vertex table.
The process is as follows. At first, the facet, which has a common edge, defined by a2 and a3 with the first facet is searched for. It is stored in the second section of the facet table if it is found. Suppose the other vertex is v2. The three vertexes should be saved in the order a2, a3, v2 in the second section. Next the facet, which has a common edge and is defined by a3 and v2 with the facet in the second section, is searched for. It is stored in the third section of the facet table if it is found. Suppose the other vertex is v3. The three vertexes should be saved in the order a3, v2, v3 in the third section. The rest may be deduced by an analogy, as shown in Figure 5.
The rearranged facet table
We can see from Figure 5 that the first two vertexes of each facet are the last two vertexes of the last facet. The proposed compression method is to store only the third vertex, not the first two vertexes, for each facet, implying the first two vertexes of this facet are the last two vertexes of the last facet. In this way, the compressed facet table is made as shown in Figure 6.
The compressed facet table
What will we do if a facet, which shares the edge defined by the last two vertexes of the facet under considering, cannot be found (for example we come to the border of the model)? We know that the first edge defined by the first two vertexes of each facet is shared by the last facet. It cannot be shared again. Now the second edge defined by the second and the third vertexes cannot be shared by a facet. The only choice is the third edge defined by the third and the first vertexes.
The idea of representing a facet by one vertex in the facet table was first proposed by Deering [6]. There are three types of vertexes R, O and M, so that two bits are needed in each vertex unit to save its type. Comparatively, there are only two types of vertexes, positive and negative, in our improved method above. In this way, only one bit is used for the sign and no bit operation is used.
5. Optimization of the Compression Method
For some large models, there are still some differences between the 1D position numbers, which need more than one unit to be saved even after the above compressing process. To make the compression rate higher, the following technique can be used.
The 3D space limited by Xmax, Xmin, Ymax, Ymin, Zmax, Zmin is subdivided into subspaces. The subspaces should be numbered and each vertex of the model belongs to a subspace. The way of sorting the vertexes is: sorting on subspace numbers firstly and then sorting on the differences of the 1D position numbers of the vertexes in the cases where they are in the same subspace. In this way, the 1D position numbers are made smaller.
6. Experiment Result and Analysis
The new compression algorithm and the Isenburg-Lindstrom-Snoeyink algorithm [13] have been implemented in VC++6.0 on a PC with 2.53GHz. The Isenburg-Lindstrom-Snoeyink algorithm is compared with the new algorithm because it is a recently published and efficient algorithm for lossless geometry compression (a smaller number of other lossless geometry compression algorithms can be found). The same four models represented in [13] are used here for experiments. Table 1 shows the number of vertexes and facets of the four models. Among them the Golf Club is the smallest one, the Hip is a larger one, the Happy Buddha is a larger one and the Lucy is the largest one.
Number of vertexes and facets of the 4 models represented in the experiment
Table 2 shows the bits per vertex of the experiments for comparison and the histogram of it is shown in Figure 7. Both of them show that the new algorithm needs fewer bits for the same model than the Isenburg-Lindstrom-Snoeyink algorithm except for the tiny model (Golf Club).
Bits per vertex of the new algorithm and the Isenburg-Lindstrom-Snoeyink algorithm
Bits per vertex of the new algorithm and the Isenburg-Lindstrom-Snoeyink algorithm
Table 3 shows the compression ratio of the experiments for comparison and the histogram of it is shown in Figure 8. Both of them show that the compression ratio of the new algorithm is less for the same model than the Isenburg-Lindstrom-Snoeyink algorithm except for the tiny model (Golf Club). It can be calculated that the average ratio of compression on the vertex table is 0.561, the average ratio of compression on the facet table is 0.396 and the average ratio of compression as a whole is 0.452.
Compression ratio of the new algorithm and the Isenburg-Lindstrom-Snoeyink algorithm
Compression ratio of the new algorithm and the Isenburg-Lindstrom-Snoeyink algorithm
Table 4 shows the compressing time of the experiments for comparison and the histogram of it is shown in Figure 9. Both of them show that the new algorithm needs more compressing time for the same model than the Isenburg-Lindstrom-Snoeyink algorithm.
Compressing time of the new algorithm and the Isenburg-Lindstrom-Snoeyink algorithm
Compression time of the new algorithm and the Isenburg-Lindstrom-Snoeyink algorithm
Table 5 shows the decompressing time of the experiments for comparison and the histogram of it is shown in Figure 10. Both of them show that the new algorithm needs less decompressing time for the same model than the Isenburg-Lindstrom-Snoeyink algorithm.
Decompressing time of the new algorithm and the Isenburg-Lindstrom-Snoeyink algorithm
Decompression time of the new algorithm and the Isenburg-Lindstrom-Snoeyink algorithm
Figure 7 and Figure 8 show that, except for the Golf Club, the compression radio of the proposed method is better than the Isenburg-Lindstrom-Snoeyink algorithm. Figure 9 and Figure 10 show that although the new algorithm needs more time than the Isenburg-Lindstrom-Snoeyink algorithm for compression, it uses less time for de-compression, which determines the efficiency in practical use.
The models we selected for experiments in the paper are comprehensive, from a tiny model to a large model. The method we proposed is worse when it's used on the model Golf Club because the model Golf Club is a tiny model which has less vertexes and will be rarely used in the fact application. For the common practical models, the method we proposed is better than the Isenburg-Lindstrom-Snoeyink algorithm.
The proposed method is a lossless compressing method. There is no difference between the models before and after the compression, so that no figure of models generated by the proposed method is shown.
Now we analyse the time complexity of the compressing and decompressing process. In the compressing process of the vertex table, the main calculations lie in the sorting of the position numbers. Therefore, the time complexity is O (NlogN). The decompression of the vertex table can be implemented by traversing the compressed vertex table once, so the time complexity is O (N).
7. Conclusion
A lossless compression method for grid models has been presented. Although the proposed method is described on the triangular facet grid model, the basic idea can be used for compressing other grid models. Furthermore, the idea of changing the 3D coordinates into 1D and storing the difference of the adjacent 1D numbers after sorting can be applied in other fields.
As well as the method of changing the 3D coordinates into 1D for compression, a revised technique of organizing the facet table has been given to improve compression.
The experiment results show that the new algorithm is more efficient than another typical lossless compression algorithm, the Isenburg-Lindstrom-Snoeyink algorithm.
All compression needs the expense of time. To reduce the time, a main consideration is needed for the decompression. Both theoretical analysis and experiment results show that the time needed for decompression by the proposed method is short. This time is even less when the method is used to transfer the models on the Internet because the decompression can be done at the same time as receiving the model, since the decompression of this method is done by a sequence from the beginning.
Footnotes
8. Acknowledgments
This work was supported by the National Natural Science Foundation of China (60675008), the National Natural Science Foundation of Liaoning Province (201102042) and the Fundamental Research Funds for the Central Universities (DC12010107). Thanks to Dr. Martin Isenburge for providing us with the models Golf Club and Hip. We also thank Stanford Computer Graphics Laboratory for the other two models Happy Buddha and Lucy.