[發明專利]一種無數據共享沖突的二維流線并行放置方法

有效

• 申請號: 201210326395.5
• 申請日: 2012-09-05
• 公開（公告）號: CN102930587A
• 公開（公告）日: 2013-02-13
• 發明（設計）人: 張文耀;寧建國
• 申請（專利權）人: 北京理工大學
• 主分類號: G06T13/80
• 分類號: G06T13/80
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種無數據共享沖突的二維流線并行放置方法，其特征在于，包括以下步驟：

步驟1、對于給定的二維流場，按照下述方式構造兩個覆蓋該流場定義域的正交控制網格，其中一個網格用于控制流線種子點的選取，令其為G_S，另一個網格用于控制流線的追蹤，令其為G_T；不失一般性，令G_S和G_T的網格單元都是正方形的，G_S的網格單元邊長為γ，G_T的網格單元邊長為λ；γ和λ可以根據實際需要設定，但是兩者之間必須滿足約束條件：γ=n*λ，其中n是大于等于3的正整數；構造好控制網格G_S和G_T之后，將兩個網格的所有網格單元都標記為空白狀態，與此同時，將控制網格G_S中的空白四聯通區域定義為有效播種區域VSA，將控制網格G_T中的空白四聯通區域定義為局部追蹤區域LTA；

步驟2、將控制網格G_S初始化為一個VSA，令其為VSA₀；將控制網格G_T初始化為一個LTA，令其為LTA₀；

步驟3、啟動一個處理部件，令其為PE₀，將步驟2中的LTA₀指派給PE₀，由PE₀執行步驟4-10，完成LTA₀的流線放置以及相關處理工作；

步驟4、令處理部件當前處理的LTA為CurLTA，在CurLTA內選取一個流線種子點；

步驟5、根據步驟4得到的流線種子點，計算并得到經過該點的流線；在計算流線的過程中，如果流線延伸到流場邊界、速度為零的臨界點、或者是控制網格G_T中被標記為填充狀態的網格單元時，該流線的計算過程就終止；

步驟6、將步驟5得到的流線作為新流線放置到流場中，為該流線設置飽和帶和隔離帶，以便控制流線之間的最大間隔距離和最小間隔距離；

步驟7、在CurLTA內，查找有效的LTA，即至少包含一個VSA的LTA；如果沒有找到有效的LTA，則轉向步驟9；

步驟8、根據步驟7得到的LTA的數目，啟動相應數量的處理部件，并將步驟7得到的LTA，分別指派給不同的處理部件，由這些處理部件并行執行步驟4-10，完成各自所負責的LTA的流線放置以及相關處理工作；

步驟9、結束CurLTA的流線放置以及相關處理工作，釋放CurLTA；

步驟10、處理部件進入等待狀態，直到被指派新的LTA而轉向步驟4，或者是因其他處理部件的處理工作都結束了而轉向步驟11；

步驟11、最后，結束整個并行流線放置過程，完成所有流線放置工作。

2.根據權利要求1所述的一種無數據共享沖突的二維流線并行放置方法，其特征在于，步驟3中所述的處理部件是指邏輯上能夠獨立運行的計算裝置，可以是計算機、CPU、CPU內核、進程或者是線程，包括但不限于這些內容。

3.根據權利要求1所述的一種無數據共享沖突的二維流線并行放置方法，其特征在于，步驟4中所述流線種子點選取方法為：在CurLTA所包含的VSA中選取一個面積最大的VSA，令其為VSA_MAX；計算VSA_MAX內所有網格單元的中心坐標的平均值，將其作為一個新的坐標點；如果該點位于VSA_MAX內，則選擇該點為流線種子點，否則分別計算過新坐標點的水平直線和垂直直線與VSA_MAX相交的線段，選取其中最長線段的中點作為流線種子點；如果所選取的流線種子點在控制網格G_T中對應的網格單元被標記為填充狀態，即非空白狀態，則將其調整為該點在控制網格G_S中對應網格單元的中心點。

4.根據權利要求1所述的一種無數據共享沖突的二維流線并行放置方法，其特征在于，步驟5中流線的計算方法包括但不限于中點算法、歐拉算法和龍格-庫塔算法等。

5.根據權利要求1所述的一種無數據共享沖突的二維流線并行放置方法，其特征在于，步驟6中設置流線飽和帶的方法是：在控制網格G_S中將該流線所觸及的所有網格單元標記為填充狀態。

6.根據權利要求1所述的一種無數據共享沖突的二維流線并行放置方法，其特征在于，步驟6中設置流線隔離帶的方法是：在控制網格G_T中將該流線所觸及的所有網格單元標記為填充狀態；然后掃描這些已填充的網格單元，將每個網格單元上下左右的相鄰網格單元也標記為填充狀態，其中已標記為填充狀態的網格單元不做重復標記。