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

在審

• 申請號: 202010135438.6
• 申請日: 2020-03-02
• 公開（公告）號: CN111368420A
• 公開（公告）日: 2020-07-03
• 發明（設計）人: 陳浩川;陳中貴;曹娟
• 申請（專利權）人: 廈門大學
• 主分類號: G06F30/20
• 分類號: G06F30/20
• 代理公司: 廈門南強之路專利事務所(普通合伙) 35200
• 代理人: 馬應森

一種GPU加速的參數曲線弧長計算及弧長參數化方法，涉及計算機輔助設計領域。提供數據的存儲方式與GPU的數據存取方式友好，指令分歧率小，減少時間消耗的一種GPU加速的參數曲線弧長計算及弧長參數化方法。包括以下步驟：輸入參數曲線的數量、每條參數曲線區間段的個數以及曲線參數；等分參數小區間段；構建弧長表；從弧長表中取出曲線弧長；輸入待求解弧長參數化的弧長值及其所在的曲線編號；確定該弧長所在的搜索區間；使用基于二進制位操作加速二叉樹遍歷回溯的深度優先搜索，將搜索區間的長度縮小到不大于用戶指定的誤差范圍；將最終搜索區間中點作為弧長所對應的參數輸出。具有更高的可并行性，更為適合GPU的SIMT架構。

技術領域

本發明涉及計算機輔助設計領域，尤其是涉及一種GPU加速的參數曲線弧長計算及弧長參數化方法。

背景技術

參數曲線的弧長計算和弧長參數化廣泛地應用在運動控制、路徑規劃等問題之中。

參數曲線C(u)的弧長函數定義為從最小參數值u₀起到參數t為止的，曲線逐點切線即一階導矢模長之積分，即弧長公式其反方向的任務，給出弧長a，由弧長函數的逆函數求出對應的參數t，即t＝A^-1(a)，稱之為弧長參數化。

由于參數曲線的形式較復雜，其弧長公式往往無法化簡為只用初等函數表達的解析形式，因此無論求解曲線弧長還是弧長參數化都難以直接計算。

傳統的CPU方法[1]，使用遞歸算法求解弧長，若其不滿足用戶指定的精度條件，則將曲線以二分法進行細化，然后求解每一個細化后區間的弧長，直到滿足精度條件為止。在遞歸計算的過程中，按次序記錄下每個滿足精度條件的區間的弧長及端點，稱作弧長表。最終的弧長為所有滿足精度條件的弧長相加得到。在求解弧長參數化問題時，首先在弧長表中查找弧長對應的參數區間，然后在區間中遞歸地查找弧長所對應的參數，即二分區間、保留其中弧長所在的區間、在該區間中繼續搜索直到滿足用戶指定的誤差條件為止。

在弧長計算和弧長參數化中，將區間進行二分并計算其弧長本質上是二叉樹的遍歷任務。在每個區間中計算弧長時，有多種求積分近似解的方法，例如高斯-勒讓德求積法(Gauss-LegendreQuadrature)([1]Guenter B,Parent R.Computing the arc length ofparametric curves[J].IEEE Computer Graphics and Applications,1990,10(3):0-78)、折線逼近法(PolylineMethod)、辛普森法(SimpsonMethod)和文森特-福西法(Vincent-ForseyRule)([2]Vincent S,Forsey D.Fast and Accurate Parametric CurveLength Computation[J].2001；[3]Floater M S,Rasmussen A F.Point-based methodsfor estimating the length of a parametric curve[J].Journal of Computationaland Applied Mathematics,2006,196(2):512-522)。

傳統的CPU方法采用遞歸方法計算弧長、求解弧長參數化，這種方法由于計算量高，因此在需要較長的計算時間，并且其方法相比于GPU的單指令多線程(SIMT)架構，具有函數調用開銷大、指令分歧率高、占用局部存儲存儲空間多等多種缺點。并且方法中的弧長表動態構建，需要在運行時對其存儲空間進行動態分配和釋放，在GPU中開銷較大，因此并不適合直接移植到GPU中。

發明內容

本發明的目的在于針對現有技術存在的上述不足，提供數據的存儲方式與GPU的數據存取方式友好，指令分歧率小，減少時間消耗的一種GPU加速的參數曲線弧長計算及弧長參數化方法。

本發明包括以下步驟：