[發明專利]基于最遠點優化的藍噪聲網格生成方法

有效

• 申請號: 201410283442.1
• 申請日: 2014-06-23
• 公開（公告）號: CN104036552B
• 公開（公告）日: 2017-05-10
• 發明（設計）人: 嚴冬明;郭建偉;張曉鵬
• 申請（專利權）人: 中國科學院自動化研究所
• 主分類號: G06T17/30
• 分類號: G06T17/30
• 代理公司: 中科專利商標代理有限責任公司11021
• 代理人: 宋焰琴

1.一種基于最遠點優化的藍噪聲網格生成方法，其特征在于，該方法包括以下步驟：

步驟S1、由用戶指定采樣點數目n，在輸入的三角網格上根據密度函數進行隨機采樣，產生初始采樣點集

步驟S2、每次找到所述采樣點集中距離最近的一對采樣點，設其中一個采樣點為x_i，然后將點x_i移動到最遠點f的位置，重復執行上述步驟，直到找不到可以移動的采樣點；

步驟S3、利用優化后的采樣點集提取輸出的三角網格；

步驟S4、利用角度優化的方法，使得所述輸出的三角網格中每個三角形的角度范圍均為[30°,120°]；

所述步驟S2包括以下分步驟：

步驟S2.1、對于所述采樣點集X中的每一個點x_i，計算該采樣點的局部最小距離其中distance(x_i,x_j)表示采樣點x_i和x_j之間的距離；

步驟S2.2、將所述采樣點x_i移動到最遠點f的位置，如果所述最遠點f與采樣點x_i相同，則認為采樣點x_i沒有移動；

步驟S2.3、重復步驟S2.1和S2.2，直到所有采樣點都沒有移動，則迭代終止；

所述步驟S2.2包括以下分步驟：

步驟S2.2.1、根據每個采樣點的權重，計算采樣點集的三維Power圖，然后進一步計算該三維Power圖與輸入曲面網格三角形的交集，得到限制Power圖，其對偶三角化稱為限制正則三角化，限制正則三角化后得到限制正則三角形，所述權重定義為該點處的密度函數大小；

步驟S2.2.2、將采樣點x_i從采樣點集X中刪除，局部更新限制Power圖和限制正則三角化，計算每個正則三角形的頂點到其對應Power頂點的距離r，r的最大值記為r_max，對應的Power頂點記為最遠點f，如果 則在所述最遠點f處插入一個新的采樣點代替原來的采 樣點x_i，否則將采樣點x_i點重新插回到原來的位置。

2.根據權利要求1所述的方法，其特征在于，在所述步驟S2.2.2中，當刪除一個采樣點p時，首先刪除包含該采樣點p的限制正則三角形，然后找到所有受該采樣點p影響的輸入曲面網格三角形，并用其他的采樣點對這些輸入三角形進行重新分割裁剪，計算得到局部的限制Power圖和限制正則三角化。

3.根據權利要求1所述的方法，其特征在于，當在所述采樣點v處插入一個新采樣點時，首先刪除受采樣點v影響的限制正則三角形，然后在該采樣點v的鄰域內，對輸入曲面網格三角形重新計算局部限制Power圖和限制正則三角化。

4.根據權利要求1至3中任一項所述的方法，其特征在于，所述步驟S3為：首先計算優化后采樣點集的限制Power圖，然后對于限制Power圖的每個頂點，如果該頂點是兩個等分線(x_i,x_j)和(x_i,x_k)的交點，那么(x_i,x_j,x_k)就可以形成一個三角形Δx_ix_jx_k，其中x_i,x_j,x_k是三個采樣點；處理完所有的頂點便得到限制Power圖的對偶網格三角形。

5.根據權利要求1至3中任一項所述的方法，其特征在于，所述步驟S4為：首先找到輸出網格中所有包含小于30°角的壞角的壞三角形，對每一個壞三角形，其壞角對應的頂點記為x₁，與壞角相對的兩個頂點分別記為x₂和x₃，然后調整頂點x₂和x₃的權重為cwi，wi為對應頂點的原始權重，c為調整因子，取值范圍[0.4-0.8] ，然后依次處理頂點x₁、x₂和x₃，處理的順序是優先處理壞角對應的頂點,且每一次處理的過程為移動該點到其最遠點，該過程不斷進行直到所有的角度都大于30°。