基于谱分解的三角网格面的全排序

发布时间：2018-04-08 07:33

本文选题：谱分解　切入点：全序　出处：《中国科学技术大学》2017年硕士论文

【摘要】：随着科技的发展,网格数据模型越来越复杂。但是现在大部分网格还是采用传统的文件格式(OFF、OBJ)进行存储,只保留网格顶点、边、面的几何和拓扑信息,并没有考虑网格模型的布局相关性,所以网格模型中三角面的布局往往是很混乱的。对大型网格数据而言当其三角面布局很混乱,将会给它的后续处理带来很多麻烦。例如由于计算机内存的限制,大型网格数据不能完全加载在计算机主内存中。经典的Out-of-core思想是先把网格进行剖分,然后将剖分后的部分网格依次加载到主内存中,最后在内存中对部分网格进行相关的后续处理,例如网格压缩、渲染、网格简化、曲面光滑等。但是该思想的前提条件是网格三角面有一个很好的排序。三角带作为网格的一种表示形式。一方面,在没有改变原始网格的条件下,它可以作为网格三角面片的一种排序,使得网格三角面的布局相关性增加。另一方面,它在许多领域内有着重要的应用,比如能够加快CPU与GPU之间的数据传输,加速渲染,进行网格压缩,实现条纹纹理贴图等。为了得到网格的一个很好的三角带表示。首先利用经典的谱分解算法得到一个具有良好三角面片排序的网格(该网格称为流网格)。在这种排序下,网格三角面片沿着网格的一个主方向(垂直于网格的最大边界)螺旋排序,但是在该主方向的每个切面上网格三角面片的排序是混乱的。因此流网格的三角面片的顺序是一种偏序形式。针对流网格的不足,本文提出了一种新的遍历方法。其主要步骤为:首先在主方向的每个截面上让网格三角面片沿着某种特定的方向(逆时针或顺时针)排序,从而得到一个三角面布局是全序的三角网格;其次,在该全序的三角网格上通过深度优先搜索算法得到一系列三角带。因为该三角带的生长方向与得到的网格三角面的排序方向密切相关,所以此三角带是一种有序的三角带。在实验中,我们比较了大量网格模型在四种不同排序下的轨迹距离,载入-显示时间,及可视化结果。实验表明经过排序后网格的三角面布局相关性相比于流网格得到进一步的加强,而且网格有一个很好的三角带表示。
[Abstract]:With the development of science and technology, the grid data model becomes more and more complex.However, most of the grids are still stored in the traditional file format, only the geometric and topological information of the vertices, edges and surfaces of the grid are kept, and the layout correlation of the grid model is not considered.Therefore, the layout of the triangular surface in the mesh model is often very chaotic.For large grid data, when its triangular layout is very confusing, it will bring a lot of trouble to its subsequent processing.For example, due to computer memory constraints, large grid data can not be fully loaded into the computer's main memory.The classical idea of Out-of-core is to divide the mesh first, then load the partitioned grid into the main memory in turn, and then carry out some subsequent processing in memory, such as mesh compression, rendering, mesh simplification, etc.Smooth surfaces, etc.But the premise of this idea is that the triangular surface of the grid has a good sort.The triangle belt is a representation of the grid.On the one hand, without changing the original mesh, it can be used as a sort of grid triangulation, which increases the layout correlation of the mesh triangulation.On the other hand, it has important applications in many fields, such as speeding up data transmission between CPU and GPU, accelerating rendering, gridding compression and stripe texture mapping.In order to get a good triangular belt representation of the grid.Firstly, the classical spectral decomposition algorithm is used to obtain a mesh with good triangulation (this mesh is called flow mesh).In this sort, the mesh triangulation is arranged in a spiral direction along one of the main directions of the grid (the largest boundary perpendicular to the grid), but the sorting of the triangular mesh on each tangent plane in that principal direction is chaotic.Therefore, the order of triangular mesh is a form of partial order.In this paper, a new traversal method is proposed to overcome the shortage of stream mesh.The main steps are as follows: first, the triangular mesh is sorted in a certain direction (counterclockwise or clockwise) on each section of the main direction, so that a triangle is arranged in full order.A series of triangle bands are obtained by depth-first search algorithm on the full order triangular mesh.Because the growth direction of the triangle is closely related to the sorting direction of the resulting triangular surface, the triangle is an ordered triangle.In the experiment, we compare the trajectory distance, load-display time, and visualization results of a large number of grid models under four different sorting conditions.The experimental results show that the triangular layout correlation of the sorted grid is further enhanced than that of the flow mesh, and the mesh has a good triangular belt representation.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP391.41

【参考文献】