Full Facet Ordering Based On Spectral Decomposition For Triangular Meshes

With the development of science and technology,mesh models become more and more complicated.However,most of them are stored in traditional file formats(OFF,OBJ,etc.),which only provides the geometric and topological information of the ver-tices,edges,faces of the mesh without taking the coherence in the layout of a mesh into account.In these mesh file formats,the layout of the geometric primitives is usually randomly ordered,which brings a big burden for the subsequent processing of mesh models especially for large mesh models.Due to the limited computer memory,large meshes can not be completely loaded into the main memory,the classical out-of-core idea is to divide the mesh into several parts,and each part is loaded into the memory step by step in order to implement related subsequent processing such as mesh com-pression,rendering,mesh simplification,and surface smoothing,but the prerequisite of the algorithm is that the facet layout of the mesh has a good coherence.Triangular strip is a good representation form of the mesh.On the one hand,when the original mesh is not changed,it can be used to sort triangular faces and strengthen the coherence in the facet layout of the mesh.On the other hand,it has many advantages in several fields.Firstly,it can accelerate the data transformation process between CPU and GPU;secondly,it can accelerate the rendering process;in addition,it can also be used for mesh compression and stripe texture mapping.In order to generate a triangular strip rerepresentation for a triangular mesh,we firstly use the classical spectral decomposition algorithm to generate a well sorted mesh which is called a stream mesh.In this stream mesh,the triangular faces are sorted along the principal direction which is perpendicular to the largest boundary of the triangular mesh,but faces on each tangent plane along the principal direction is disordered,so the whole triangular faces are generally partial ordered.To tackle this issue,in this paper,we propose a novel traversal algorithm which can be conducted by two following steps.Firstly,for the the faces on each section along the principal direction,we sort them along a fixed direction(counterclockwise or clockwise),which leads to a total ordered layout of the faces.Secondly,a series of ordered triangle strips can be obtained by the depth-first search algorithm among the ordered facets.Owing to the strong correlation between the growing direction of these triangle strips and the sorting direction of the triangular faces,these triangular strips are ordered.To verify our algorithm,we compare our method with the spectral decomposition method in terms of track distance,load-display time and visualization results using four different kinds of sorting types respectively.From the experimental results we can see that our method is superior to the spectral decomposition method and it can generate a satisfactory triangular strip.