[發(fā)明專利]一種GPU加速的參數(shù)曲線弧長計算及弧長參數(shù)化方法

在審

• 申請?zhí)枺?/td>: 202010135438.6
• 申請日: 2020-03-02
• 公開（公告）號: CN111368420A
• 公開（公告）日: 2020-07-03
• 發(fā)明（設(shè)計）人: 陳浩川;陳中貴;曹娟
• 申請（專利權(quán)）人: 廈門大學(xué)
• 主分類號: G06F30/20
• 分類號: G06F30/20
• 代理公司: 廈門南強之路專利事務(wù)所(普通合伙) 35200
• 代理人: 馬應(yīng)森

1.一種GPU加速的參數(shù)曲線弧長計算及弧長參數(shù)化方法，其特征在于包括以下步驟：

1)輸入?yún)?shù)曲線的數(shù)量、每條參數(shù)曲線區(qū)間段的個數(shù)以及曲線參數(shù)；

2)將每一個區(qū)間段等分為N份首尾相接的參數(shù)“小區(qū)間段”；

3)構(gòu)建“小區(qū)間弧長表”和“區(qū)間弧長表”；

4)每條曲線對應(yīng)的區(qū)間弧長表中的最后一項為弧長，將其輸出；

5)輸入待求解弧長參數(shù)化的弧長值及其所在的曲線編號i；

6)確定該弧長所在的“搜索區(qū)間”，初始化搜索任務(wù)，每個弧長的搜索區(qū)間的初始化由1個GPU線程完成；

7)使用“基于二進制位操作加速二叉樹遍歷回溯的深度優(yōu)先搜索”，將搜索區(qū)間的長度縮小到不大于用戶指定的誤差范圍ξ，每個弧長的弧長參數(shù)化由1個GPU線程完成；

8)將最終搜索區(qū)間中點作為弧長所對應(yīng)的參數(shù)輸出。

2.如權(quán)利要求1所述一種GPU加速的參數(shù)曲線弧長計算及弧長參數(shù)化方法，其特征在于在步驟1)中，所述輸入?yún)?shù)曲線應(yīng)滿足如下要求：每條曲線與其他曲線彼此獨立；每條曲線包括一個或若干個由用戶指定的參數(shù)“區(qū)間段”，每個區(qū)間段上的曲線上點及切線的計算與其他區(qū)間段彼此獨立，在同一區(qū)間段內(nèi)曲線上不同參數(shù)的點及切線的計算彼此獨立。

3.如權(quán)利要求1所述一種GPU加速的參數(shù)曲線弧長計算及弧長參數(shù)化方法，其特征在于在步驟2)中，所述小區(qū)間段的劃分方法為：N為16、32、64、128或256，所有的區(qū)間段的劃分時所取的N均相同；劃分時，令每一個小區(qū)間段均保存該小區(qū)間段對應(yīng)的參數(shù)區(qū)間端點值[u_cij,u_ci(j+1)]、曲線編號i、區(qū)間段編號j以及曲線在該區(qū)間段上的參數(shù)值P(C_ij)，使得每一個小區(qū)間段均可被獨立計算。

4.如權(quán)利要求1所述一種GPU加速的參數(shù)曲線弧長計算及弧長參數(shù)化方法，其特征在于在步驟3)中，所述構(gòu)建“小區(qū)間弧長表”和“區(qū)間弧長表”的具體方法為：

步驟31.采用“雙階段的廣度優(yōu)先搜索”計算滿足用戶指定誤差ε的曲線在該小區(qū)間段上的弧長值；小區(qū)間段弧長的計算結(jié)果按順序存儲，稱為“小區(qū)間弧長表”，其排序優(yōu)先級為，曲線編號區(qū)間段編號小區(qū)間段首端點值；

步驟32.計算小區(qū)間弧長表中每個區(qū)間段的弧長的前綴和，存儲，稱之為小區(qū)間弧長表；

步驟33.計算每條曲線各個區(qū)間段所對應(yīng)的小區(qū)間弧長表中每個區(qū)間的最后一項的前綴和，按順序存儲，稱為“區(qū)間弧長表”，排序優(yōu)先級為，曲線編號區(qū)間段編號。

5.如權(quán)利要求4所述一種GPU加速的參數(shù)曲線弧長計算及弧長參數(shù)化方法，其特征在于在步驟31中，所述“雙階段的廣度優(yōu)先搜索”在搜索時所使用的節(jié)點包括待求弧長的區(qū)間的首尾端點值α和β；所在曲線編號i；所在區(qū)間段編號j；區(qū)間段所對應(yīng)曲線的參數(shù)信息P(C_ij)；上一層搜索中，計算該節(jié)點的父節(jié)點的線程的編號pid；節(jié)點的父節(jié)點的弧長pal。