[發明專利]一種漸進最優的三角網格重復頂點快速去除方法

有效

• 申請號: 201310376046.9
• 申請日: 2013-08-26
• 公開（公告）號: CN103425787A
• 公開（公告）日: 2013-12-04
• 發明（設計）人: 王文珂;王攀;蔡勛;李思昆;曾亮;沈恩亞;王懷暉;劉華海
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 國防科技大學專利服務中心 43202
• 代理人: 郭敏

1.一種漸進最優的三角網格重復頂點快速去除方法，其特征在于包括以下步驟：

第一步，申請兩個長度為3n的一維數組T與S，T與S中的元素為三角頂點，初始化各個頂點為0，其中n為幾何圖形三角面片個數，T與S每個元素大小為三個32位浮點數；初始化數組V_x、V_xy、V_xyz為長度3n的數組，每個元素為三個32位浮點數；初始化頂點索引數組F為長度3n的數組，每個元素為一個32位整數，F中的元素初始化為0；

第二步，初始化變量i＝0，istr=0；

第三步，采用二分查找方法查找T，去除V中的重復頂點v_i，得到沒有重復頂點的數組T，V是存放3n個三角形頂點的數組，每個頂點由三個32位浮點數構成，每個浮點數指每個頂點的X坐標、Y坐標、Z坐標，每三個頂點再組成一組，表示一個三角面片，共計n個三角面片，方法是：

3.1讀取V中的頂點v_i＝{x_i,y_i,z_i}，x_i,y_i,z_i分別為v_i的X坐標、Y坐標、Z坐標；

3.2根據頂點v_i(x_i,y_i,z_i)的X坐標值x_i大小，采用二分查找方法查找T中的頂點，若在T中找到了X坐標值等于x_i的頂點，將T中的X坐標值為x_i的頂點全放入集合V_x，轉3.3；若在T中未找到X坐標值等于x_i的頂點，將此時二分查找方法得到的位置值賦給變量istr，轉第五步；

3.3在V_x中根據頂點v_i(x_i,y_i,z_i)的Y坐標值y_i大小，利用二分查找方法查找與y_i相同的頂點，若在V_x中找到Y坐標值等于y_i的頂點，將Y坐標值為y_i的頂點全放入集合V_xy，轉3.4；若在V_x中找不到Y坐標值等于y_i的頂點，將此時二分查找方法得到的位置值賦給變量istr，轉第五步；

3.4在V_xy中根據頂點v_i(x_i,y_i,z_i)的Z坐標值z_i大小，利用二分查找方法查找與z_i相同的頂點，若在V_xy中找到Z坐標值等于z_i的頂點，將Z坐標值為z_i的頂點全放入集合V_xyz，記集合V_xyz中第一個元素是數組T中的第istr個元素，轉第四步；若在V_xy中找不到Z坐標值等于z_i的頂點，將此時二分查找方法得到的位置值賦給變量istr，轉第五步；

第四步，如果V_xyz不為空，則說明頂點v_i為T中存貯的重復的頂點，執行第六步；若V_xyz為空，則說明頂點v_i目前不是重復頂點，執行第五步；

第五步，將頂點v_i插入數組T：采用英特爾流式單指令多數據擴展指令集4即SSE4指令集技術，復制數組T中的元素集合T[istr,m]到臨時緩沖數組S[istr+1,m+1]中，然后將v_i復制到數組T中序號為istr的元素的位置即作為元素T[istr]，再復制S[istr+1,m+1]到T[istr+1,m+1]，所述T[istr,m]是指數組T中，第istr個元素到第m個元素之間的一段連續空間上的所有數組元素，T[istr+1,m+1]是指數組T中，第istr+1個元素到第m+1個元素之間的一段連續空間上的所有數組元素，S[istr+1,m+1]是指數組S中，第istr+1個元素到第m+1個元素之間的一段連續空間上的所有數組元素；

第六步，令i＝i+1并清空集合V_x、V_xy、V_xyz，若i＞3n-1則執行第七步，否則轉第三步；

第七步，設置計數變量Counter=0，i=0；

第八步，在原始頂點集合V中選取頂點v_i，使用二分查找方法查找T，分別沿X、Y、Z方向在集合T中查找頂點v_i，方法是：

8.1讀取集合V中的頂點v_i＝{x_i,y_i,z_i}；

8.2根據頂點v_i(x_i,y_i,z_i)的X坐標值x_i大小，采用二分查找方法查找T中的頂點，在T中找到X坐標值等于x_i的頂點，將T中的X坐標值為x_i的頂點全放入集合V_x，轉8.3；

8.3在V_x集合中根據頂點v_i(x_i,y_i,z_i)的Y坐標值y_i利用二分查找方法查找與v_i具有相同y_i頂點，將Y坐標值為y_i的頂點全放入集合V_xy，轉8.4；

8.4在集合V_xy中根據頂點v_i(x_i,y_i,z_i)的Z坐標值z_i大小利用二分查找方法查找與v_i具有相同z_i的頂點，將Z坐標值為z_i的頂點v'_i在數組T中的序號賦給變量Idx_xyz，轉第九步；

第九步，將變量Idx_xyz的值賦給頂點索引數組F中序號為Counter的元素F[Counter]；

第十步，計數變量Counter增1,i增1，并清空集合V_x、V_xy；

第十一步，判斷i是否大于3n-1，若i大于3n-1，說明所有頂點已經處理，得到了正確的頂點索引數組F，轉第十二步，否則轉第八步；

第十二步，輸出沒有重復頂點的頂點數組T與頂點索引數組F，結束。