發(fā)布時間：2018-04-08 07:33

  本文選題：譜分解　切入點：全序　出處：《中國科學技術(shù)大學》2017年碩士論文

【摘要】：隨著科技的發(fā)展,網(wǎng)格數(shù)據(jù)模型越來越復(fù)雜。但是現(xiàn)在大部分網(wǎng)格還是采用傳統(tǒng)的文件格式(OFF、OBJ)進行存儲,只保留網(wǎng)格頂點、邊、面的幾何和拓撲信息,并沒有考慮網(wǎng)格模型的布局相關(guān)性,所以網(wǎng)格模型中三角面的布局往往是很混亂的。對大型網(wǎng)格數(shù)據(jù)而言當其三角面布局很混亂,將會給它的后續(xù)處理帶來很多麻煩。例如由于計算機內(nèi)存的限制,大型網(wǎng)格數(shù)據(jù)不能完全加載在計算機主內(nèi)存中。經(jīng)典的Out-of-core思想是先把網(wǎng)格進行剖分,然后將剖分后的部分網(wǎng)格依次加載到主內(nèi)存中,最后在內(nèi)存中對部分網(wǎng)格進行相關(guān)的后續(xù)處理,例如網(wǎng)格壓縮、渲染、網(wǎng)格簡化、曲面光滑等。但是該思想的前提條件是網(wǎng)格三角面有一個很好的排序。三角帶作為網(wǎng)格的一種表示形式。一方面,在沒有改變原始網(wǎng)格的條件下,它可以作為網(wǎng)格三角面片的一種排序,使得網(wǎng)格三角面的布局相關(guān)性增加。另一方面,它在許多領(lǐng)域內(nèi)有著重要的應(yīng)用,比如能夠加快CPU與GPU之間的數(shù)據(jù)傳輸,加速渲染,進行網(wǎng)格壓縮,實現(xiàn)條紋紋理貼圖等。為了得到網(wǎng)格的一個很好的三角帶表示。首先利用經(jīng)典的譜分解算法得到一個具有良好三角面片排序的網(wǎng)格(該網(wǎng)格稱為流網(wǎng)格)。在這種排序下,網(wǎng)格三角面片沿著網(wǎng)格的一個主方向(垂直于網(wǎng)格的最大邊界)螺旋排序,但是在該主方向的每個切面上網(wǎng)格三角面片的排序是混亂的。因此流網(wǎng)格的三角面片的順序是一種偏序形式。針對流網(wǎng)格的不足,本文提出了一種新的遍歷方法。其主要步驟為:首先在主方向的每個截面上讓網(wǎng)格三角面片沿著某種特定的方向(逆時針或順時針)排序,從而得到一個三角面布局是全序的三角網(wǎng)格;其次,在該全序的三角網(wǎng)格上通過深度優(yōu)先搜索算法得到一系列三角帶。因為該三角帶的生長方向與得到的網(wǎng)格三角面的排序方向密切相關(guān),所以此三角帶是一種有序的三角帶。在實驗中,我們比較了大量網(wǎng)格模型在四種不同排序下的軌跡距離,載入-顯示時間,及可視化結(jié)果。實驗表明經(jīng)過排序后網(wǎng)格的三角面布局相關(guān)性相比于流網(wǎng)格得到進一步的加強,而且網(wǎng)格有一個很好的三角帶表示。
[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.
【學位授予單位】：中國科學技術(shù)大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP391.41

【參考文獻】

相關(guān)期刊論文 前5條

1 秦愛紅;石教英;;基于混合模式緩存優(yōu)化的三角形條帶化[J];計算機輔助設(shè)計與圖形學學報;2011年06期

2 張潔;吳佳澤;鄭昌文;胡曉惠;;應(yīng)用哈密頓回路的三角網(wǎng)格拓撲壓縮[J];計算機輔助設(shè)計與圖形學學報;2013年05期

3 胡建偉;劉利剛;;保持特征的對偶網(wǎng)格構(gòu)造方法[J];計算機輔助設(shè)計與圖形學學報;2015年03期

4 魏瀟然;耿國華;張雨禾;;幾何信息預(yù)測的三角網(wǎng)格模型拓撲壓縮[J];西安電子科技大學學報;2015年05期

5 郭鳳華;張彩明;焦文江;;網(wǎng)格參數(shù)化研究進展[J];軟件學報;2016年01期

，

本文編號：1720631